Unroll of loops with constant bounds

[evstupac]

Summary

The patch limit unroll of loops with constant bounds by current threshold reducing unroll factor to minimum power-of-2.
Previously we gave up on unrolling if there were no unroll factor that is modulo of TripCount or could exceed threshold if there is such.

[mzolotukhin]

Hi Evgeny,

Please find some comments inline.

Thanks,
Michael

lib/Transforms/Scalar/LoopUnrollPass.cpp

646–651

Do I understand it correctly that with this change we start to unroll every loop if it's possible at all (some of them with remainder)? If that's correct, have you measured performance, compile time, and code size impact of this change? Also, it might make sense to limit it to O3.

test/Transforms/LoopUnroll/partial-unroll-const-bounds.ll

2

You probably don't want to run opt ... -O2 in this test. O2 will run the entire optimization pipeline, while we only want loop-unroll.

20

Please pass the test through opt -instnamer to replace names like %0 with some symbolic names. These digit names make it harder to change the test in future.

Also, you probably could only remove almost all instructions from the body to make the test smaller. If you run only loop-unroll, nothing will optimize that to ret void, so it would be fine.

[evstupac]

Hi Michael,

Thanks for the review.
Please find my responses inline.

Thanks,
Evgeny

lib/Transforms/Scalar/LoopUnrollPass.cpp

646–651

The change allows unroll only for loops that satisfy threshold limit. There are not much cases where this hits. On spec2000 I've got almost all build same or <0.1% code size changes.
Without the changes it happens that the same loop with unknown bounds get unrolled, but with constant no.
For example when we have prime TripCount we'll not found Count that is modulo of TripCount.

for (i = 0; i < 17; i++)

I don't see any reason why we should restrict unroll in the case if we are in threshold limits.

As for remainder - there is no such by default. As we know remainder TripCount (it is constant) we can jump into the middle of the loop first.

The other point is that now we check threshold limit only at entrance. So potentially we can find unroll factor which exceed threshold limit.

test/Transforms/LoopUnroll/partial-unroll-const-bounds.ll

2

"-O2" makes CHECK statements easier. However I agree it is not required here. I'll fix the test.

20

Ok. Will update.

[mzolotukhin]

test/Transforms/LoopUnroll/partial-unroll-const-bounds.ll

2

You could add some specific passes after yours. You probably need just something like -dce -instcombine -simplifycfg - some tests do this. Adding the entire "-O2" might introduce undesired side effects from e.g. running loop-unroll twice.

[evstupac]

Test updated.
I've created my own names instead of %0 and %1. Hope this is ok.
As for instructions in loop I'd like to leave some there (to disable full unrolling).

[mzolotukhin]

LGTM. Please run the patch through clang-format prior to committing, it looks like there are some missing spaces etc.

Michael

[evstupac]

rebased, passed clang-format

[evstupac]

removed check (LoopSize - 2) * Count + 2 > UP.PartialThreshold

as at this point (LoopSize - 2) * Count + 2 <= max (UP.PartialThreshold, 3). So only UP.PartialThreshold equal to 2 can make comparison above true.

[mzolotukhin]

Since you've already got LGTM, you could proceed with checking it in (no need to wait for another explicit LGTM in this case).

Michael

lib/Transforms/Scalar/LoopUnrollPass.cpp

if (!AllowPartial && !CountSetExplicitly) {
       return false;
     }
     if (UP.PartialThreshold != NoThreshold &&
         UnrolledSize > UP.PartialThreshold) {
       // Reduce unroll count to be modulo of TripCount for partial unrolling.
       Count = (std::max(UP.PartialThreshold, 3u) - 2) / (LoopSize - 2);
       while (Count != 0 && TripCount % Count != 0)
         Count--;
+      if (Count <= 1 || (LoopSize - 2) * Count + 2 > UP.PartialThreshold) {
+        // If there is no Count that is modulo of TripCount or we still
+        // exceed threshold, set Count to largest power-of-two factor that
+        // satisfies the threshold limit.
+        Count = (std::max(UP.PartialThreshold, 3u)-2) / (LoopSize-2);
+        UnrolledSize = (LoopSize - 2) * Count + 2;
+        while (Count != 0 && UnrolledSize > UP.PartialThreshold) {
+          Count >>= 1;
+          UnrolledSize = (LoopSize - 2) * Count + 2;
+        }
+      }
     }
   } else if (Unrolling == Runtime) {
     if (!AllowRuntime && !CountSetExplicitly) {
       DEBUG(dbgs() << "  will not try to unroll loop with runtime trip count "
                    << "-unroll-runtime not given\n");
       return false;
     }
 

test/Transforms/LoopUnroll/partial-unroll-const-bounds.ll

+; RUN: opt < %s -S -unroll-threshold=20 -loop-unroll -unroll-allow-partial | FileCheck %s
+
+; The Loop TripCount is 9. However unroll factors 3 or 9 exceed given threshold.
+; The test checks that we choose a smaller, power-of-two, unroll count and do not give up on unrolling.
+
+; CHECK: for.body:
+; CHECK: store
+; CHECK: for.body.1:
+; CHECK: store
+
+define void @foo(i32* nocapture %a, i32* nocapture readonly %b) nounwind uwtable {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %ld = load i32, i32* %arrayidx, align 4
+  %idxprom1 = sext i32 %ld to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %a, i64 %idxprom1
+  %st = trunc i64 %indvars.iv to i32
+  store i32 %st, i32* %arrayidx2, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 10
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}