Kenneth Zadeck wrote:
Mark Mitchell wrote:
Kenneth Zadeck wrote:
The majority of the new bugs were places where the rest of the
compiler was just not expecting to see auto inc or dec instructions.
If you want to take on doing this kind of extension, be prepared for
the additional cost.
Kenny, do you have any pointers to autoincrement algorithms in the
literature? I can see how using some of the obvious global analysis
can spot things like a store followed on all paths by an add to the
pointer, and prove that there are no intervening uses of the pointer,
and therefore note that could could merge the addition with the store
to do a post-increment -- but is there anything especially clever out
there?
Thanks,
Remember that we are not really talking about pointers here, even
though the values that are computed are used as pointers. The things
that are combined are pseudo register expressions, so there is no
rocket science here, not any involvement with aliases.
Given that kind of simplification, this is a simple meet over all
paths problem. If all paths that reach some "suitable point" (the
load or store that can accommodate the inc or dec) increment or
decrement the register in the same way and moving that inc or dec will
not create an inc or dec free path, you are free to move combine the
inc into the suitable point.
This is a very simplified instance of code motion or commoning. The
simplification is that it is goal directed. The goal is to move the
inc insns to the "suitable points".
As far as literature, i do not know any off the top of my head, but
this is a classic meet over all paths kind of dataflow problem. I
would rather solve it in ssa form than using dataflow equations but
that is my bias and unfortunately is not an option until we get fuds
put into the back end.
Kenny
there is actually one nit of this that makes a dataflow solution easier
than a fud or ssa version.
uses of the index variable kill it.
consider the straight line code
a <- a + 1
...<- a
x[a]
you would like to combine the a<-a+1 with the x[a], but you cannot
because it would mean changing the use of ...<-a into ...<-a-1. This
is a loss. ssa and fuds are not good at detecting this kind of thing
without futzing with statement numbers and and domination and such where
if you solve it as a dataflow problem, you can make the ...<-a be in the
kill set.
kenny
