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

[Chen Li]

> On Jul 17, 2015, at 2:45 PM, Philip Reames <listmail at philipreames.com> wrote:
> 
> 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




> 
> Philip
> 
> 
> 
> On 07/16/2015 04:10 PM, Chen Li wrote:
>> 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
>> 
>>  
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>