[LLVMdev] A small pass to constant fold branch conditions in destination blocks

[Owen Anderson]

On Feb 8, 2011, at 1:15 AM, Mark Shannon wrote:

> Nick Lewycky wrote:
>> Duncan Sands wrote:
>>> Here is a new and improved version that also does the following: if the
>>> condition for a conditional branch has the form "A && B" then A, B and the
>>> condition are all replaced with "true" in the true destination (similarly
>>> for || conditions in the false destination). Also, if the condition has
>>> the form "X == Y" then X is replaced by Y everywhere in the true
>>> destination
>>> (likewise if it is "X != Y" then X is replaced by Y everywhere in the false
>>> destination). Completely untested for correctness!
>> 
>> Not to discourage you, but you're reinventing predsimplify.
>> 
>> What PS did was find branches (or switches) where the target block was 
>> uniquely dominated by a single case, then assign %cond = true/false (or 
>> %switchval = const) and then walk up propagating that condition upwards 
>> (ie., if %cond = and i1 %a, %b then %a and %b are true, and if %a = icmp 
>> eq i32 %a, i32 0 then PS would immediately find all uses of %a dominated 
>> by that branch and replace them with 0 on the spot). After walking up, 
>> you would walk down again with what you learned; for example you may 
>> have done %A = add %X, %Y way early on and know in this lower branch 
>> that %Y is 0, now %A = %X. PS had a full comparison lattice (not-equals, 
>> signed-lessthan-unsigned-greaterthan) and also grew constant range 
>> analysis (x < y implies x != -1 and y != 0).
>> 
>> While I know PS removed tons of code from the .ll I was never really 
>> able to detect a runtime performance improvement; my guess is that while 
>> I was killing off lots of dead code it didn't impact the performance of 
>> the live code much or at all.
>> 
> 
> Killing off lots of dead code is going to improve compile time,
> since code-gen time tends to dominate optimise time.
> 
> Improving compile time is important for those of us using the JIT compiler.

Except PredSimplify was also a big compile time sink, and didn't make up for any benefits it gave on that front.

--Owen