[LoopPeel] Allow partial unrolling for profile-based peeling

[ikudrin]

Summary

As for now, the loop is unrolled if the profile-based trip count is not greater than a limit, which is 7 by default; i.e. no iterations are peeled off for a loop that has the estimation of 8. The patch is based on the idea that a bit longer loop can still benefit from extracting several first iterations. The longer the loop, the lower the effect of the extraction, so if the trip count is estimated to be more than twice the threshold, the optimization is not applied.

[ikudrin]

A bit of the context. After D71990, we noticed that one of our tests became slower and did not benefit from PGO. The test has a loop that is executed exactly 8 times, and, before the patch, it was (partially) unrolled but after the patch, the loop is preserved in the compact form.

[davidxl]

For loops with trip count between maxPeelCount and 2*maxPeelCount, this patch enables partial peeling of the loop for maxPeelCount iterations. This feels very aggressive and can be detrimental to performance: 1) increased icache footprint; 2) more pressure to BPU and 3) the back branch of the remaining loop may become less predictable.

What is the motivation case for such a change?

[ikudrin]

In D123865#3454386, @davidxl wrote:

For loops with trip count between maxPeelCount and 2*maxPeelCount, this patch enables partial peeling of the loop for maxPeelCount iterations. This feels very aggressive and can be detrimental to performance: 1) increased icache footprint; 2) more pressure to BPU and 3) the back branch of the remaining loop may become less predictable.

What is the motivation case for such a change?

I've described the motivation in my first comment. I believe that the concerns are the same for any peeling strategy based on the trip count. And if there is a consensus that a loop with 7 trip counts can be optimized, why 8-trip-count loop can't be optimized in the same way? So, the patch provides a smooth transition between what is optimized and what is not. That should work better than a strict border.

[davidxl]

Have you analyzed the root cause of the performance regression (with performance counters)? Is it due to other missed optimizations without the peeling or is it due to side effects such as loop alignment?

Changes like this one is very likely to cause regressions in other workload, so it might better to solve the problem with tuning options (which are there for a reason). Longer term, I'd like to see more sophisticated cost/benefit analysis implemented which will also be target dependent.

[ikudrin]

Our test was for AArch64, so there should be no effects like loop alignment, if I understand you right. I couldn't find a benchmark to test the change against, so I prepared an artificial one based on LLVM test suite/SingleSource/Benchmarks/Adobe-C++/loop-unroll.cpp. I saw the performance gain 10%-30% depending on the iterations count (on x86_64). But I understand that that test is probably biased, so if you recommend some commonly recognized public benchmark that might be suitable for the case, I would try it. As for a more deep analysis, could you share some examples so I can grab some ideas from them?

[davidxl]

In D123865#3454607, @ikudrin wrote:

Our test was for AArch64, so there should be no effects like loop alignment, if I understand you right.

Alignment related uArch quirks is much less likely to happen, but is still possible.

I couldn't find a benchmark to test the change against, so I prepared an artificial one based on LLVM test suite/SingleSource/Benchmarks/Adobe-C++/loop-unroll.cpp. I saw the performance gain >10%-30% depending on the iterations count (on x86_64). But I understand that that test is probably biased, so if you recommend some commonly recognized public benchmark that might be suitable for >the case, I would try it. As for a more deep analysis, could you share some examples so I can grab some ideas from them?

You want to try programs with large instruction working set and are built with PGO. Lacking those, at least SPEC06 or SPEC17

As regard the analysis, you can try perf events like cycles, retired instructions, retired taken branches, branch-mispredictions etc to help you understand the improvement better.

[ikudrin]

Unfortunatelly, I do not have access to SPEC tests. I checked with 7zip-benchmark and found that Compressing speed is slightly improved with this patch while Decompressing is slightly degraded. But I have to note that compared to a Release build, PGO one is worse even without the patch.

As for my own tests, I noticed that the performance gain with unrolled loops results from the generated code that has less instructions. In one sample, there was no need to reserve a register for the loop counters and as in each iteration the value of the counter was known, there was no instructions for increment the counter and the comparison instructions used an immediate value instead of comparing with the register; all that made the code path shorter. In another example, the subsequent iterations used overlapped data from the memory. Both compact and unrolled version loaded the data to a set of registers, but the compact version had to shift values in registers in each iteration, so that they are placed each time in the predefined registers, while unrolled version just used instructions which work this different set of registers in each iteration. Thus, unrolling again helped to find a way to generate a code with less instructions for each peeled iteration.

[davidxl]

In D123865#3468077, @ikudrin wrote:

Unfortunatelly, I do not have access to SPEC tests. I checked with 7zip-benchmark and found that Compressing speed is slightly improved with this patch while Decompressing is slightly degraded. But I have to note that compared to a Release build, PGO one is worse even without the patch.

As for my own tests, I noticed that the performance gain with unrolled loops results from the generated code that has less instructions. In one sample, there was no need to reserve a register for the loop counters and as in each iteration the value of the counter was known, there was no instructions for increment the counter and the comparison instructions used an immediate value instead of comparing with the register; all that made the code path shorter. In another example, the subsequent iterations used overlapped data from the memory. Both compact and unrolled version loaded the data to a set of registers, but the compact version had to shift values in registers in each iteration, so that they are placed each time in the predefined registers, while unrolled version just used instructions which work this different set of registers in each iteration. Thus, unrolling again helped to find a way to generate a code with less instructions for each peeled iteration.

Thanks for the analysis. That matches what I expected -- which circles back to my original question -- how do we know the new limit is generally better than the old limit? It really depends on the cost-benefit analysis. There are workloads (as demonstrated by the Decompressing case) which gets hurt.

On the other hand, the patch itself (the restructuring part) looks good -- it makes the code cleaner. I suggest you commit the restructuring part first (e.g. by removing the *2 multiplier part). I think it is better to keep the default setting unchanged until a better analysis in place.

[ikudrin]

• Extract an NFCI part into D124388

In D123865#3468366, @davidxl wrote:

Thanks for the analysis. That matches what I expected -- which circles back to my original question -- how do we know the new limit is generally better than the old limit? It really depends on the cost-benefit analysis. There are workloads (as demonstrated by the Decompressing case) which gets hurt.

On the other hand, the patch itself (the restructuring part) looks good -- it makes the code cleaner. I suggest you commit the restructuring part first (e.g. by removing the *2 multiplier part). I think it is better to keep the default setting unchanged until a better analysis in place.

I am not sure I understand why this patch requires any additional analysis compared to what is already implemented. The existing heuristic states that extracting up to 7 iterations for loops with estimated loop counts up to 7 is beneficial. The new heuristic is that peeling the same 7 iterations for loops with estimated loop counts slightly greater than 7 is still beneficial. They are still the same 7 iterations, with exactly the same profit. If the analysis is required, it should be applied to the whole idea of peeling loops based on the estimated trip counts.

llvm/lib/Transforms/Utils/LoopPeel.cpp

void llvm::computePeelCount(Loop *L, unsigned LoopSize,
   // If we don't know the trip count, but have reason to believe the average
   // trip count is low, peeling should be beneficial, since we will usually
   // hit the peeled section.
   // We only do this in the presence of profile information, since otherwise
   // our estimates of the trip count are not reliable enough.
   if (L->getHeader()->getParent()->hasProfileData()) {
     if (violatesLegacyMultiExitLoopCheck(L))
       return;
-    Optional<unsigned> PeelCount = getLoopEstimatedTripCount(L);
-    if (!PeelCount)
+    Optional<unsigned> EstimatedTripCount = getLoopEstimatedTripCount(L);
+    if (!EstimatedTripCount)
       return;
 
-    LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is " << *PeelCount
-                      << "\n");
+    LLVM_DEBUG(dbgs() << "Profile-based estimated trip count is "
+                      << *EstimatedTripCount << "\n");
 
-    if (*PeelCount) {
-      if ((*PeelCount + AlreadyPeeled <= UnrollPeelMaxCount) &&
-          (LoopSize * (*PeelCount + 1) <= Threshold)) {
-        LLVM_DEBUG(dbgs() << "Peeling first " << *PeelCount
-                          << " iterations.\n");
-        PP.PeelCount = *PeelCount;
+    if (*EstimatedTripCount) {
+      // Even if we cannot peel all estimated iterations, partial peeling also
+      // seems beneficial, but only to some extent.
+      if (*EstimatedTripCount + AlreadyPeeled <= MaxPeelCount * 2 &&
+          AlreadyPeeled < MaxPeelCount) {
+        unsigned PeelCount =
+            std::min(*EstimatedTripCount, MaxPeelCount - AlreadyPeeled);
+        LLVM_DEBUG(dbgs() << "Peeling first " << PeelCount << " iterations.\n");
+        PP.PeelCount = PeelCount;
         return;
       }
-      LLVM_DEBUG(dbgs() << "Requested peel count: " << *PeelCount << "\n");
       LLVM_DEBUG(dbgs() << "Already peel count: " << AlreadyPeeled << "\n");
       LLVM_DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
-      LLVM_DEBUG(dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1)
-                        << "\n");
+      LLVM_DEBUG(dbgs() << "Loop cost: " << LoopSize << "\n");
       LLVM_DEBUG(dbgs() << "Max peel cost: " << Threshold << "\n");
+      LLVM_DEBUG(dbgs() << "Max peel count by cost: "
+                        << (Threshold / LoopSize - 1) << "\n");
     }
   }
 }
 
 /// Update the branch weights of the latch of a peeled-off loop
 /// iteration.
 /// This sets the branch weights for the latch of the recently peeled off loop
 /// iteration correctly.

llvm/test/Transforms/LoopUnroll/peel-loop-conditions-pgo-2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -loop-unroll -loop-unroll -verify-dom-info -debug-only=loop-unroll -unroll-peel-max-count=7 2>&1 | FileCheck %s
 ; REQUIRES: asserts
 
 declare void @f1()
 declare void @f2()
 
 ; Check that we can peel off iterations that make conditions true.
 ; The second invocation of loop-unroll will NOT do profile based peeling of
-; remained iterations because the total number of peeled iterations exceeds
-; threashold specified with -unroll-peel-max-count=7.
+; remaining iterations because the total number of iterations exceeds the
+; doubled threshold specified with -unroll-peel-max-count=7.
 define void @test2(i32 %k) !prof !4 {
 ; CHECK: Loop Unroll: F[test2] Loop %for.body
 ; CHECK: PEELING loop %for.body with iteration count 2!
 ; CHECK-NOT: llvm.loop.unroll.disable
 for.body.lr.ph:
   br label %for.body
 
 for.body:
for.inc:
   %cmp = icmp slt i32 %inc, %k
   br i1 %cmp, label %for.body, label %for.end, !llvm.loop !1, !prof !3
 
 for.end:
   ret void
 }
 
 !1 = distinct !{!1}
-!3 = !{!"branch_weights", i32 8, i32 1}
+!3 = !{!"branch_weights", i32 14, i32 1}
 !4 = !{!"function_entry_count", i64 1}

llvm/test/Transforms/LoopUnroll/peel-loop-conditions-pgo-3.ll

+; RUN: opt < %s -S -loop-unroll -loop-unroll -verify-dom-info -debug-only=loop-unroll -unroll-peel-max-count=7 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+declare void @f1()
+declare void @f2()
+
+; Check that we can peel off iterations that make conditions true.
+; The second invocation of loop-unroll will do profile-based peeling of remaining
+; iterations and will partially peel them so that the total number of peeled
+; iterations does not exceed the threshold specified with -unroll-peel-max-count=7.
+define void @test2(i32 %k) !prof !4 {
+; CHECK: Loop Unroll: F[test2] Loop %for.body
+; CHECK: PEELING loop %for.body with iteration count 2!
+; CHECK: PEELING loop %for.body with iteration count 5!
+; CHECK: llvm.loop.unroll.disable
+for.body.lr.ph:
+  br label %for.body
+
+for.body:
+  %i.05 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %cmp1 = icmp ult i32 %i.05, 2
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  call void @f1()
+  br label %for.inc
+
+if.else:
+  call void @f2()
+  br label %for.inc
+
+for.inc:
+  %inc = add nsw i32 %i.05, 1
+  %cmp = icmp slt i32 %inc, %k
+  br i1 %cmp, label %for.body, label %for.end, !llvm.loop !1, !prof !3
+
+for.end:
+  ret void
+}
+
+!1 = distinct !{!1}
+!3 = !{!"branch_weights", i32 13, i32 1}
+!4 = !{!"function_entry_count", i64 1}