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

[Nick Lewycky]

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.

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