[LLVMdev] why LoopUnswitch pass does not constant fold conditional branch and merge blocks

[Chen Li]

Hi,

I have a general question on LoopUnswtich pass.

Consider the following IR snippet:

define i32 @test(i1 %cond) {
  br label %loop_begin

loop_begin:
  br i1 %cond, label %loop_body, label %loop_exit

loop_body:
  br label %do_something

do_something:
  call void @some_func() noreturn nounwind
  br label %loop_begin

loop_exit:
  ret i32 0
}
declare void @some_func() noreturn

After running it through "opt -loop-unswitch -S", it unswitched loop on %cond and produced result like this:

define i32 @test(i1 %cond) {
  br i1 %cond, label %..split_crit_edge, label %.loop_exit.split_crit_edge

.loop_exit.split_crit_edge:                       ; preds = %0
  br label %loop_exit.split

..split_crit_edge:                                ; preds = %0
  br label %.split

.split:                                           ; preds = %..split_crit_edge
  br label %loop_begin

loop_begin:                                       ; preds = %do_something, %.split
  br i1 true, label %loop_body, label %loop_exit

loop_body:                                        ; preds = %loop_begin
  br label %do_something

do_something:                                     ; preds = %loop_body
  call void @some_func() #1
  br label %loop_begin

loop_exit:                                        ; preds = %loop_begin
  br label %loop_exit.split

loop_exit.split:                                  ; preds = %.loop_exit.split_crit_edge, %loop_exit
  ret i32 0
}

We see it did not constant fold "br i1 true, label %loop_body, label %loop_exit" and merge %loop_body into %loop_begin. 

My understanding is that later llvm passes (likely -simplifycfg) will cleanup the code properly and doing this in LoopUnswtich pass is duplicated. However, consider the following case:

define i32 @test(i32* %var, i1 %cond1, i1 %cond2) {
  br label %loop_begin

loop_begin:  
  br i1 %cond1, label %continue, label %loop_exit

continue:
  %var_val = load i32, i32* %var
  br i1 %cond2, label %do_something, label %loop_exit  

do_something:
  call void @some_func() noreturn nounwind
  br label %loop_begin

loop_exit:
  ret i32 0
}

Assume you don't have enough budget to do non-trivial loop unswtich (for test purpose, set -loop-unswitch-threshold=0 with opt), the result would be:

define i32 @test(i32* %var, i1 %cond1, i1 %cond2) {
  br i1 %cond1, label %..split_crit_edge, label %.loop_exit.split_crit_edge

.loop_exit.split_crit_edge:                       ; preds = %0
  br label %loop_exit.split

..split_crit_edge:                                ; preds = %0
  br label %.split

.split:                                           ; preds = %..split_crit_edge
  br label %loop_begin

loop_begin:                                       ; preds = %do_something, %.split
  br i1 true, label %continue, label %loop_exit

continue:                                         ; preds = %loop_begin
  %var_val = load i32, i32* %var
  br i1 %cond2, label %do_something, label %loop_exit

do_something:                                     ; preds = %continue
  call void @some_func() #1
  br label %loop_begin

loop_exit:                                        ; preds = %continue, %loop_begin
  br label %loop_exit.split

loop_exit.split:                                  ; preds = %.loop_exit.split_crit_edge, %loop_exit
  ret i32 0
}

The remaining loop (%loop_begin) in the result actually contains a trivial unswitch condition (on %cond2), which should always unswitch because there is no code growth. However, because the branch in loop header is not constant folded and %continue is not merged into %loop_begin, LoopUnswtich pass can not recongnize the trivial unswitch condition (in the current implementation, trivial unswitch condition must be loop header’s terminator). If this is the last LoopUnswtich pass in the optimization pipeline, we will miss the trivial unswitch opportunity. 

So would it be reasonable to add branch constant folding into LoopUnswtich pass for this kind of cases?

thanks,
chen