[LLVMdev] why LoopUnswitch pass does not constant fold conditional branch and merge blocks (original) (raw)

Chen Li meloli87 at gmail.com
Thu Jul 16 16:10:01 PDT 2015

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

More information about the llvm-dev mailing list