Re: improving auto increment expressions detection across basic blocks.

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

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