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

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

Adding folding of constant branches to the unswitcher seems likes it would be a perfectly reasonable enhancement. For context, it's worth restating that the unswitcher is used in trivial-only mode in the standard O2 pipeline. We only enable non-trivial unswitch if -O3 is specified.

The complication I'd watch out for is that folding such branches might eliminate the loop entirely. The unswitcher clearly already has to handle the case of "1 loop -> 1 loop + 1 non-loop", but I'm not sure it would correctly handle "1 loop -> 2 non-loops". In particular, I'm not sure what the interaction with the LoopPassManager is here. Taking a look at LoopDeletionPass might be a good source of information.

Philip

Looking into this further, this may be as simple as extending the SimplifyCode function already used in LoopUnswitch.

Philip

Adding folding of constant branches to the unswitcher seems likes it would be a perfectly reasonable enhancement. For context, it's worth restating that the unswitcher is used in trivial-only mode in the standard O2 pipeline. We only enable non-trivial unswitch if -O3 is specified.

The complication I'd watch out for is that folding such branches might eliminate the loop entirely. The unswitcher clearly already has to handle the case of "1 loop -> 1 loop + 1 non-loop", but I'm not sure it would correctly handle "1 loop -> 2 non-loops". In particular, I'm not sure what the interaction with the LoopPassManager is here. Taking a look at LoopDeletionPass might be a good source of information.

Thinking about it further, I don’t think it’s possible to eliminate the loop entirely. Loop unswtich applies on conditional branch and splits the original loop to 2 loops based on *true* condition and *false* condition of the branch (by *true* I mean the branch goes into the loop, and *false* to exit the loop). For trivial cases, folding the *false* condition will eliminate the loop, but folding the *true* condition will create an infinite loop with an unconditional branch to the loop header. So I don’t think this should be a problem for LoopPassManager. I will take a deep look at both LoopDeletionPass and SimplifyCode function in LoopUnswitch.

thanks,
chen