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

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

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
}

Jeff Kunkel

On Mon, Feb 7, 2011 at 8:37 AM, Duncan Sands <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>> 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
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110207/54394dc4/attachment.html>

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