[Mono-dev] [PATCH] A "fastpath" dead code elimination

[Massimiliano Mantione]

On Tue, 2005-11-15 at 15:14 -0500, Miguel de Icaza wrote:
> Hello,
> 
> > The alias analysis pass has O(n) complexity (n = code size), it is
> > just a linear sweep on the list of instructions.
> > Then, deadce operates one BB at a time, scanning the code linearly
> > and using the liveness bits as start/end conditions (so it is O(n)
> > as well).
> 
> Is there is a threshold that will disable the optimization from running?

Of course :-)
If you do not provide the "deadce" flag, it will not be used.
And even if we'll decide to enable it by default, it will be enough
to specify "-O=-deadce" to switch it off.

I didn't explain much of how the patch is coded, and/or how it can
be used, so here are some more details.



With this patch applied, -O=deadce activates fastpath deadce, unless
some other flag (for now either "ssapre" or "abcrem") required ssa.
In this case, the "traditional" ssa deadce is used.
However, I added one new flag: "ssa", which forces ssa construction.
If this is used, then "deadce" will default to the ssa one.
Note, however, that if "deadce" has been specified, and "ssa" is in
some way required (at least one of "ssapre", "abcrem" or "ssa" was
specified), it can *still* happen that some method will fall back to
use fastpath deadce: this happens if ssa was disabled because of
aliasing.

Now, I *know* this sounds confusing at first.
Here's the rationale: the idea is that the JIT should do what the
user "means" with the flags.
So, if the user asks "deadce", the JIT does its best to do deadce.
This is the same thing that happens now for consprop and copyprop,
which have both ssa and "fast" versions, which are not equally
effective but are called the same.
And as soon as I'll commit the HSSA patch, there will be one "hssa"
flag as well (at least it works so in my tree).
So one will be able to choose betwen "fastpath", "ssa" and "hssa"
deadce, using "-O=deadce", "-O=ssa,deadce" or "-O=hssa,deadce".
Of course in the long run ssa will go away and will be replaced
by hssa, but at least for testing in between this can work.

The alternative would be having one different flag for each "kind"
of optimization, like "fastdeadce", "hssadeadce"...
However, this way the number of flags will get too high (and also
ugly) with hssa.
And consprop and copyprop already work this way (we use the same
flags for the ssa and "fast" versions), so I decided go go on with
the same philosophy.



About the implementation... there's not much to say, the algorithms
are "classical", no rocket science here ;-)

I tried not too mess up too much the liveness code, which is for
sure the more impacted by this patch.
I made so that the same code works both with and without aliasing
information.
When aliasing has been computed, it is possible to obtain one list
of "affected variables" for each MonoInst, and liveness uses that
to understand the effect of the inst on each variable.
On the other hand, without aliasing info, the code relied on the
presence of MONO_SSA_* flags to see what each instruction was doing
and each instruction could have effect on just *one* local.
In this case I decided to keep one list node as local variable, and
use it to build a "one element" list of "affected variables".
This way all the "logic" of liveness has been transformed to use
those "affected variables" lists, and a small preamble takes the
real list if aliasing has been computed, or builds the "one element"
list otherwise.
So the patch is a bit hard to read, but it's not so terrible IMHO.
And yes, I know that I'm slowing liveness computation a bit this
way, but it's just a bit, and we have the advantage of not "forking"
the liveness code!

If anything isn't clear, just ask ;-)

Ciao,
  Massi