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

[Jeff Kunkel]

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>