llvm dev - Feb 2011 - [LLVMdev] A small pass to constant fold branch conditions in destination blocks

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

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
> .
>

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