Serious performance regression -- some tree optimizer questions

[Daniel Berlin]

On Thu, 13 Jan 2005, Zdenek Dvorak wrote:

> Hello,
>
> one more note:
>
>>>  But by taking the optimizations into account at once,
>>> you are able to get better results.
>>
>> I'm pretty sure if we combined PRE, DCE, GVN, CCP, and everything else
>> into hyper-global-mega-pass, we could get better results too :).
>
> This analogy is obviously nonsense.  While the optimizations you mention
> have very little in common,

Actually, they all do have a lot in common, and very closely related. 
They are all in fact, mostly the same thing, which is removing
computations by proving value equivalence, to either some existing 
computating, or to a constant.
I'm very surprised you don't see that.

PRE is an extension of GVN to paths where an expression is not completely 
available but could be.
CCP is simply a different form of GVN that does optimistic gvn using a 
lattice.
You can subsume CCP with a very smart GVN, and in fact, it's been done 
before.
As a side effect of CCP/smartGVN, you can perform DCE by simply removing 
the statements you never get to visit (IE those with no immediate uses).
If you iterated CCP, you would eventually remove all the same statements 
as DCE.

You could easily create a pass that performed GVN + PRE + DCE + CCP 
together, because they are all very closely related problems.
They all interact quite heavily.
Without GVN or  CCP, your DCE won't be very effective, because even though 
the result is constant, because you haven't replaced it with that 
constant/other computation, DCE won't remove the useless computations.
etc
--dan