[SimpleLoopUnswich] Fix a bug on ComputeUnswitchedCost with partial unswitch

[jaykang10]

Summary

There was a bug from cost calculation for partially invariant unswitch.

The costs of non-duplicated blocks are substracted from the total LoopCost, so anything that is duplicated should *not* be counted.

On omnetpp of SPEC2017, more functions are inlined with new pass manager's inliner against legacy pass manager one.

It causes bigger unswitch cost and I have found my update of the cost calculation is wrong from it.

A test case is updated because it has multiple unswitch candidates and the different candidate is picked up.

[jaykang10]

Added a test case to explain what was wrong

[jaykang10]

@fhahn @jonpa I was able to see the speedup on omnetpp of SPEC2017 with this patch.

I have added a test case to explain what was wrong.

If you need something more, please let me know.

[jaykang10]

@fhahn @jonpa If possible, can we push this change please?

[jaykang10]

@fhahn @jonpa I am sorry for ping.

[fhahn]

In D103816#2816343, @jaykang10 wrote:

@fhahn @jonpa I am sorry for ping.

There's no need to be sorry for pinging, but I would suggest to stick to the the common practices for the LLVM project (https://llvm.org/docs/Contributing.html#how-to-submit-a-patch), even if it means waiting a bit longer:

The common courtesy ‘ping’ rate is once a week. Please remember that you are asking for valuable time from other professional developers.

[jaykang10]

In D103816#2816446, @fhahn wrote:

In D103816#2816343, @jaykang10 wrote:

@fhahn @jonpa I am sorry for ping.

There's no need to be sorry for pinging, but I would suggest to stick to the the common practices for the LLVM project (https://llvm.org/docs/Contributing.html#how-to-submit-a-patch), even if it means waiting a bit longer:

The common courtesy ‘ping’ rate is once a week. Please remember that you are asking for valuable time from other professional developers.

@fhahn Thanks for your kind reply. I will follow it.

[jaykang10]

Rebased

[jaykang10]

@fhahn @jonpa Can we push this change please?

[sanwou01]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2871

Isn't this always true for a partial unswitch? If there is a partial unswitch candidate, PartialIVCondBranch will be the terminator of the loop header. When ComputeUnswitchedCost is called for a partial unswitch TI is *also* the terminator of the loop header. Did I miss something?

FWIW I also think that the previous condition is always true: for a partial unswitch, there is always at least one instruction in InstToDuplicate. (again, the terminator of the loop header!)

[sanwou01]

I think I managed to figure out what's going on here in the end, but it would help to explain what the bug is in the commit message, something like:

The costs of non-duplicated blocks are substracted from the total LoopCost, so anything that is duplicated should *not* be counted.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2872–2877

Agreed here!

[jaykang10]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2871

Isn't this always true for a partial unswitch? If there is a partial unswitch candidate, PartialIVCondBranch will be the terminator of the loop header. When ComputeUnswitchedCost is called for a partial unswitch TI is *also* the terminator of the loop header. Did I miss something?

It is correct. The candidate of PartialIVCondBranch is the terminator of the loop header. However, there could be multiple unswitch candidates which are fully or partially loop invariant. In this case, we need to check whether the candidate is partially invariant or not. You can see the example on
partial_unswitch_exiting_block_with_multiple_unswitch_candidates test function.

FWIW I also think that the previous condition is always true: for a partial unswitch, there is always at least one instruction in InstToDuplicate. (again, the terminator of the loop header!)

As we can see on hasPartialIVCondition, we add instructions such as CMP, LOAD or GEP into InstToDuplicate for partially invariant cases. For fully invariant cases, logical OR, logical AND, True, False or loop invariant conditions are added.

As we can see on below comment, we need to check the cost of duplicated successors. The duplicated successors are different according to the fully or partially invariant instructions.

// If this is a partial unswitch candidate, then it must be a conditional
// branch with a condition of either `or`, `and`, their corresponding
// select forms or partially invariant instructions. In that case, one of
// the successors is necessarily duplicated, so don't even try to remove
// its cost.

[jaykang10]

In D103816#2832771, @sanwou01 wrote:

I think I managed to figure out what's going on here in the end, but it would help to explain what the bug is in the commit message, something like:

The costs of non-duplicated blocks are substracted from the total LoopCost, so anything that is duplicated should *not* be counted.

Sorry for inconvenient, let me add a comment in commit message.

[sanwou01]

Sorry for inconvenient, let me add a comment in commit message.

No worries! I feel like I learned quite a bit about how this code works now!

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2871

With !FullUnswitch, we know that we are considering a partial unswitch candidate. Could there be multiple *partial* unswitch candidates? Currently, it looks like there can only be a single partial unswitch candidate per loop, but maybe that's not necessarily true?

[jaykang10]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2871

Um... you are right. !FullUnswitch means we assume logical OR, logical AND and partially invariant instructions.
Let me remove the if (PartialIVCondBranch == &TI).

[jaykang10]

Following comments from @sanwou01, updated patch.

[sanwou01]

Thanks, LGTM!

[jaykang10]

In D103816#2833140, @sanwou01 wrote:

Thanks, LGTM!

I appreciate your review! After checking the performance number from omnetpp of SPEC2017 with last change, let me push this change.

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

for (BasicBlock *SuccBB : successors(&BB)) {
       if (!FullUnswitch) {
         auto &BI = cast<BranchInst>(TI);
         if (match(BI.getCondition(), m_LogicalAnd())) {
           if (SuccBB == BI.getSuccessor(1))
             continue;
         } else if (match(BI.getCondition(), m_LogicalOr())) {
           if (SuccBB == BI.getSuccessor(0))
             continue;
-        } else if (!PartialIVInfo.InstToDuplicate.empty()) {
+        } else if (PartialIVCondBranch == &TI) {
           if (PartialIVInfo.KnownValue->isOneValue() &&
-              SuccBB == BI.getSuccessor(1))
+              SuccBB == BI.getSuccessor(0))
             continue;
           else if (!PartialIVInfo.KnownValue->isOneValue() &&
-                   SuccBB == BI.getSuccessor(0))
+                   SuccBB == BI.getSuccessor(1))
             continue;
         }
       }
 
       // This successor's domtree will not need to be duplicated after
       // unswitching if the edge to the successor dominates it (and thus the
       // entire tree). This essentially means there is no other path into this
       // subtree and so it will end up live in only one clone of the loop.
       if (SuccBB->getUniquePredecessor() ||

llvm/test/Transforms/SimpleLoopUnswitch/partial-unswitch.ll

 
 ; There could be multiple unswitch candidates which include partially invariant
 ; condition. When the exiting block is selected as best unswitch one, clone loop
 ; blocks.
 define i32 @partial_unswitch_exiting_block_with_multiple_unswitch_candidates(i32 %0, i32 %1, i32* %ptr) {
 ; CHECK-LABEL: @partial_unswitch_exiting_block_with_multiple_unswitch_candidates(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[EXIT_COND:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
-; CHECK-NEXT:    br i1 [[EXIT_COND]], label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
-; CHECK:       entry.split.us:
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[PTR:%.*]], align 16
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 41
-; CHECK-NEXT:    br i1 [[TMP3]], label [[ENTRY_SPLIT_US_SPLIT:%.*]], label [[ENTRY_SPLIT_US_SPLIT_US:%.*]]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[ENTRY_SPLIT:%.*]], label [[ENTRY_SPLIT_US:%.*]]
+; CHECK:       entry.split.us:
+; CHECK-NEXT:    br i1 [[EXIT_COND]], label [[ENTRY_SPLIT_US_SPLIT_US:%.*]], label [[ENTRY_SPLIT_US_SPLIT:%.*]]
 ; CHECK:       entry.split.us.split.us:
 ; CHECK-NEXT:    br label [[LOOP_US_US:%.*]]
 ; CHECK:       loop.us.us:
 ; CHECK-NEXT:    br label [[EXITING_US_US:%.*]]
 ; CHECK:       exiting.us.us:
 ; CHECK-NEXT:    br label [[LOOP_US_US]]
 ; CHECK:       entry.split.us.split:
 ; CHECK-NEXT:    br label [[LOOP_US:%.*]]
 ; CHECK:       loop.us:
-; CHECK-NEXT:    [[VAL_US:%.*]] = load i32, i32* [[PTR]], align 16
-; CHECK-NEXT:    [[IF_COND_US:%.*]] = icmp ult i32 [[VAL_US]], 41
-; CHECK-NEXT:    br i1 [[IF_COND_US]], label [[IF_THEN_US:%.*]], label [[EXITING_US:%.*]]
-; CHECK:       if.then.us:
-; CHECK-NEXT:    store i32 [[TMP1:%.*]], i32* [[PTR]], align 16
-; CHECK-NEXT:    br label [[EXITING_US]]
+; CHECK-NEXT:    br label [[EXITING_US:%.*]]
 ; CHECK:       exiting.us:
-; CHECK-NEXT:    br label [[LOOP_US]], !llvm.loop [[LOOP10:![0-9]+]]
+; CHECK-NEXT:    br label [[EXIT_SPLIT_US:%.*]]
+; CHECK:       exit.split.us:
+; CHECK-NEXT:    [[RET_VAL_US:%.*]] = phi i32 [ 1, [[EXITING_US]] ]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[VAL:%.*]] = load i32, i32* [[PTR]], align 16
 ; CHECK-NEXT:    [[IF_COND:%.*]] = icmp ult i32 [[VAL]], 41
 ; CHECK-NEXT:    br i1 [[IF_COND]], label [[IF_THEN:%.*]], label [[EXITING:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i32 [[TMP1]], i32* [[PTR]], align 16
+; CHECK-NEXT:    store i32 [[TMP1:%.*]], i32* [[PTR]], align 16
 ; CHECK-NEXT:    br label [[EXITING]]
 ; CHECK:       exiting:
-; CHECK-NEXT:    br label [[EXIT:%.*]]
-; CHECK:       exit:
+; CHECK-NEXT:    br i1 [[EXIT_COND]], label [[LOOP]], label [[EXIT_SPLIT:%.*]], !llvm.loop [[LOOP10:![0-9]+]]
+; CHECK:       exit.split:
 ; CHECK-NEXT:    [[RET_VAL:%.*]] = phi i32 [ 1, [[EXITING]] ]
-; CHECK-NEXT:    ret i32 [[RET_VAL]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[DOTUS_PHI:%.*]] = phi i32 [ [[RET_VAL]], [[EXIT_SPLIT]] ], [ [[RET_VAL_US]], [[EXIT_SPLIT_US]] ]
+; CHECK-NEXT:    ret i32 [[DOTUS_PHI]]
 ;
 entry:
   %exit.cond = icmp ne i32 %0, 0
   br label %loop
 
 loop:
   %val = load i32, i32* %ptr, align 16
   %if.cond = icmp ult i32 %val, 41
   br i1 %if.cond, label %if.then, label %exiting
 
 if.then:
   store i32 %1, i32* %ptr, align 16
   br label %exiting
 
 exiting:
   br i1 %exit.cond, label %loop, label %exit
 
 exit:
   %ret.val = phi i32 [ 1, %exiting ]
   ret i32 %ret.val
 }
 
+; The path with noclobber block is only duplicated so we need to calculate only
+; the cost of the path with noclobber.
+define i32 @partial_unswitch_true_successor_for_cost_calculation(i32* %ptr, i32 %N) {
+; CHECK-LABEL: @partial_unswitch_true_successor_for_cost_calculation(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 100
+; CHECK-NEXT:    br i1 [[TMP1]], label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK:       entry.split.us:
+; CHECK-NEXT:    br label [[LOOP_HEADER_US:%.*]]
+; CHECK:       loop.header.us:
+; CHECK-NEXT:    [[IV_US:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT_US]] ], [ [[IV_NEXT_US:%.*]], [[LOOP_LATCH_US:%.*]] ]
+; CHECK-NEXT:    br label [[NOCLOBBER_US:%.*]]
+; CHECK:       noclobber.us:
+; CHECK-NEXT:    br label [[LOOP_LATCH_US]]
+; CHECK:       loop.latch.us:
+; CHECK-NEXT:    [[C_US:%.*]] = icmp ult i32 [[IV_US]], [[N:%.*]]
+; CHECK-NEXT:    [[IV_NEXT_US]] = add i32 [[IV_US]], 1
+; CHECK-NEXT:    br i1 [[C_US]], label [[LOOP_HEADER_US]], label [[EXIT_SPLIT_US:%.*]]
+; CHECK:       exit.split.us:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       entry.split:
+; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
+; CHECK:       loop.header:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
+; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[PTR]], align 4
+; CHECK-NEXT:    [[SC:%.*]] = icmp eq i32 [[LV]], 100
+; CHECK-NEXT:    br i1 [[SC]], label [[NOCLOBBER:%.*]], label [[CLOBBER:%.*]]
+; CHECK:       noclobber:
+; CHECK-NEXT:    br label [[LOOP_LATCH]]
+; CHECK:       clobber:
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    call void @clobber()
+; CHECK-NEXT:    br label [[LOOP_LATCH]]
+; CHECK:       loop.latch:
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[IV]], [[N]]
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    br i1 [[C]], label [[LOOP_HEADER]], label [[EXIT_SPLIT:%.*]], !llvm.loop [[LOOP11:![0-9]+]]
+; CHECK:       exit.split:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 10
+;
+entry:
+  br label %loop.header
+
+loop.header:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ]
+  %lv = load i32, i32* %ptr
+  %sc = icmp eq i32 %lv, 100
+  br i1 %sc, label %noclobber, label %clobber
+
+noclobber:
+  br label %loop.latch
+
+clobber:
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  call void @clobber()
+  br label %loop.latch
+
+loop.latch:
+  %c = icmp ult i32 %iv, %N
+  %iv.next = add i32 %iv, 1
+  br i1 %c, label %loop.header, label %exit
+
+exit:
+  ret i32 10
+}
+
 ; CHECK: [[LOOP0]] = distinct !{[[LOOP0]], [[UNSWITCH_PARTIAL_DISABLE:![0-9]+]]}
 ; CHECK: [[UNSWITCH_PARTIAL_DISABLE]] = !{!"llvm.loop.unswitch.partial.disable"}
 ; CHECK: [[LOOP2]] = distinct !{[[LOOP2]], [[UNSWITCH_PARTIAL_DISABLE]]}
 ; CHECK: [[LOOP3]] = distinct !{[[LOOP3]], [[UNSWITCH_PARTIAL_DISABLE]]}
 ; CHECK: [[LOOP4]] = distinct !{[[LOOP4]], [[UNSWITCH_PARTIAL_DISABLE]]}
 ; CHECK: [[LOOP5]] = distinct !{[[LOOP5]], [[UNSWITCH_PARTIAL_DISABLE]]}
 ; CHECK: [[LOOP6]] = distinct !{[[LOOP6]], [[UNSWITCH_PARTIAL_DISABLE]]}
 ; CHECK: [[LOOP7]] = distinct !{[[LOOP7]], [[UNSWITCH_PARTIAL_DISABLE]]}
 ; CHECK: [[LOOP8]] = distinct !{[[LOOP8]], [[UNSWITCH_PARTIAL_DISABLE]]}
 ; CHECK: [[LOOP9]] = distinct !{[[LOOP9]], [[UNSWITCH_PARTIAL_DISABLE]]}
 ; CHECK: [[LOOP10]] = distinct !{[[LOOP10]], [[UNSWITCH_PARTIAL_DISABLE]]}
+; CHECK: [[LOOP11]] = distinct !{[[LOOP11]], [[UNSWITCH_PARTIAL_DISABLE]]}