improving auto increment expressions detection across basic blocks.

[Kenneth Zadeck]

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