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

[Mark Shannon]

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.

Mark.

> Nick
> 
>> Scheduling this pass after -correlated-propagation results for example in
>> 5759 lines of bitcode being removed from 403.gcc.
>>
>> Ciao, Duncan.
>>
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> .
>