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

[Duncan Sands]

Hi Jeff,

> Are you sure this is really advantageous? '%c' is only one variable, but when
> you add the constant propagation, '%c' and false/true are two different
> variables. Thus

the example was explanatory, not typical.  In fact I didn't ever see returns
being split like this in practice.  What I do see typically is branches
being eliminated.  For example, consider the effect on bzip2: 36 branches are
completely removed, 1 is changed from conditional to unconditional, various
bits of dead code are eliminated (not a lot, 4 stores and a few computations).
I chose this example randomly, but it's typical of what I see elsewhere.

Ciao, Duncan.


>
>   define i1 @t1(i1 %c) {
>     br i1 %c, label %t, label %f
>   t:
>     ret i1 %c
>   f:
>     ret i1 %c
>   }
> should be
>    br i1 R0, label %t, label %f
> t:
>    ret R0
> f:
>    ret R0
>
> However, with your pass
>   define i1 @t1(i1 %c) {
>     br i1 %c, label %t, label %f
>   t:
>     ret i1 true
>   f:
>     ret i1 false
>   }
> will be
>   define i1 @t1(i1 %c) {
>     br i1 R0, label %t, label %f
>   t:
>     R1 = true
>     ret i1 R1
>   f:
>     R1 = false
>     ret i1 R1
>   }
>
> I am thinking X86 where '%c' would be allocated a register and the false/true
> statement would be allocated a different register which would be EAX/AX on the
> x86 machine.
>
> Honestly, I believe this pattern could be conditional constant propagation
> / conditional re-materialization in the spiller. LLVM uses the spiller to
> propagate constants. This pass would be useful to identify some conditional
> re-materializations. You should look into hacking the spiller and see if this
> can be added to it.
>
> - My 2 cents,
> Jeff Kunkel
>
> On Mon, Feb 7, 2011 at 7:50 AM, Duncan Sands <baldrick at free.fr
> <mailto:baldrick at free.fr>> wrote:
>
>     Hi all, I wrote a little pass (attached) which does the following: if it sees a
>     conditional branch instruction then it replaces all occurrences of the condition
>     in the true block with "true" and in the false block with "false".  Well, OK, it
>     is a bit more sophisticated (and a bit more careful!) than that but you get the
>     idea.  It will turn this
>       define i1 @t1(i1 %c) {
>         br i1 %c, label %t, label %f
>       t:
>         ret i1 %c
>       f:
>         ret i1 %c
>       }
>     into this
>       define i1 @t1(i1 %c) {
>         br i1 %c, label %t, label %f
>       t:
>         ret i1 true
>       f:
>         ret i1 false
>       }
>     for example.  Curiously enough LLVM doesn't seem to have a pass that does this.
>     I took a look at the effect on the testsuite by scheduling a run of this pass
>     just after each run of -correlated-propagation.  In spite of being so simple
>     (not to say simplistic) it has an enormous positive impact on Ada code and a
>     substantial positive impact throughout the LLVM test-suite (I didn't check that
>     programs still work after running the pass, so it could be that it has such a
>     big effect because it is wrong!).
>
>     So... should this kind of logic be incorporated into LLVM?  Perhaps as part of
>     an existing pass like -correlated-propagation?
>
>     It would be easy to make the pass a bit more powerful.  For example if the
>     condition was "X == 0" then it could also replace X with 0 everywhere in the
>     true block.
>
>     Ciao, Duncan.
>
>     PS: This was inspired by PR9004.
>
>     _______________________________________________
>     LLVM Developers mailing list
>     LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> http://llvm.cs.uiuc.edu
>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>