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

[Duncan Sands]

Hi Jeff, sorry my example was misleading.

> Then I misunderstood it's purpose. I see now that constant propagation could
> remove branches because you know a value is true. I was looking at the problem
> through my 'register allocator' lens. Here is a more expressive example of what
> you are doing.
>
> define i1 @t1(i1 %c) {
>     br i1 %c, label %t, label %f
> t:
>     br i1 %c, label %t2, label %f2
> t2:
>    code...
>    ret something
> f2:
>    code...
>    ret something
>
> f:
>     br i1 %c, label %t3, label %f3
> t3:
>    code...
>    ret something
> f3:
>    code...
>    ret something
>   }
>
> Would be changed into:
> define i1 @t1(i1 %c) {
>     br i1 %c, label %t2, label %f3
> t2:
>    code...
>    ret something
> f3:
>    code...
>    ret something
> }

Yes that's exactly what it would do, and this happens a lot in practice.  The
reason that it fires a lot in Ada code for example if that the code is full of
compiler generated checks (eg: every array access is checked) and the checks
often end up being repeated (eg: because you access the same array element
twice).  Now all the later checks are eliminated if they are implied by the
earlier checks.

Ciao, Duncan.

>
> Jeff Kunkel
> On Mon, Feb 7, 2011 at 8:37 AM, Duncan Sands <baldrick at free.fr
> <mailto:baldrick at free.fr>> wrote:
>
>     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>
>         <mailto: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>
>         <mailto:LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>>
>         http://llvm.cs.uiuc.edu
>
>         http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
>