[Hexagon] peel loops with runtime small trip counts

[iajbar]

Summary

For Hexagon, peeling loops with small runtime trip count is beneficial for our benchmarks. We set PeelCount in HexagonTargetInfo.cpp and we use PeelCount set by the target for computing the desired peel count.

[mkazantsev]

lib/Transforms/Scalar/LoopUnrollPass.cpp

803

I don't think it is correct. computePeelCount will set PeelCount to 0 if the loop is unpeelable, and you are forcing it to some value without checking this fact.

[mkazantsev]

test/Transforms/LoopUnroll/Hexagon/peel-small-loop.ll

7

Please add a test where you force peel count to 2 and the loop cannot be peeled, I believe it will expose a bug.

[iajbar]

lib/Transforms/Scalar/LoopUnrollPass.cpp

803

There is another call to canPeel() in peelLoop(). In the case of a target sets the peel count to Non zero, then the loop won’t get peel if it’s invalid to be peeled.

[mkazantsev]

lib/Transforms/Scalar/LoopUnrollPass.cpp

803

1. This still need a test that ensures this behavior preserves.
2. Actually, to me it looks quite strange, and I'd rather prefer having canPeel in peelLoop as assert in future. It makes no sense to make the same set of checks in two different places that go after one another.

I suggest you to move your logic inside computePeelCount and return the number of peeled iterations set by your platform-specific code *after* you check that the loop can be peeled. This will allow to replace the check in peelLoop with assertion later.

lib/Transforms/Utils/LoopUnrollPeel.cpp

480

1. Why it is not a part of canPeel?
2. This is not connected to your logic about setting peel count in target. This should be a separate patch with justification and tests for this very change.

[mkazantsev]

lib/Transforms/Scalar/LoopUnrollPass.cpp

803

I have submitted https://reviews.llvm.org/D44919 for review to get rid of this second check, I believe this is how it should work.

[fhahn]

lib/Transforms/Scalar/LoopUnrollPass.cpp

803

How about changing computePeelCount to take the maximum of the passed in peelCount and the compute peel count? That seems to be in line with how other unroll settings are handled.

For example, if computePeelCount finds a higher peel count, shouldn't that one be used?

Also note that even settings like UnrollForcePeelCount are only applied after the other calculations could not find a peel count.

[iajbar]

I addressed the comments from Max and Florian.

[mkazantsev]

lib/Transforms/Utils/LoopUnrollPeel.cpp

223–224

You only need preset peel count in one place. How about remembering it into a variable in the beginning of the method, zeroing UP.PeelCount and using the variable where you need it? Then you will not need to zero UP.PeelCount before every return.

[mkazantsev]

test/Transforms/LoopUnroll/Hexagon/peel-small-loop.ll

7

I still ask you to add such a test.

[iajbar]

Thanks Max. Please note that this patch also fixes a bug as well. Without this patch, the value passed by the flag -unroll-peel-count was ignored.

test/Transforms/LoopUnroll/Hexagon/peel-small-loop.ll

7

There is already a test that check this case: test/Transforms/LoopUnroll/peel-loop-irreducible.ll.

[mkazantsev]

LGTM

[mkazantsev]

I think this patch may cause some inefficiencies in terms of compile time and generated code in case if unroller decides to make full unrolling or partial unrolling with user-forced number of iterations, see discussion of D44919. However it is not a correctness issue, i.e. resulting code will still produce right results.

Currently it fails by assert after the logic has changed, to fix it I propose to add canPeel check before forcing peel count.

[iajbar]

Thank you very much Max for your review. I tried to zero UP.PeelCount before every return from computeUnrollCount that stands before computePeelCount and it causes test/Transforms/LoopUnroll/pr33437.ll to fail. This test expects to peel a loop first and than unrolling it.

[mkazantsev]

Ok, then it seems to be expected behavior in some cases (which is strange to me, but OK). Then we can just add canPeel check to this patch to avoid crash. As I said before, checking this before setting peel count is reasonable by itself.

[iajbar]

I committed this patch with canPeel() check before setting PeelCount in Hexagon Target. Thank you very much Max for your Review.

lib/Target/Hexagon/HexagonTargetTransformInfo.cpp

HexagonTTIImpl::getPopcntSupport(unsigned IntTyWidthInBit) const {
   // to 64 bits.
   return TargetTransformInfo::PSK_FastHardware;
 }
 
 // The Hexagon target can unroll loops with run-time trip counts.
 void HexagonTTIImpl::getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
                                              TTI::UnrollingPreferences &UP) {
   UP.Runtime = UP.Partial = true;
+  if (SE.getSmallConstantTripCount(L) == 0 &&
+      SE.getSmallConstantMaxTripCount(L) > 0 &&
+      SE.getSmallConstantMaxTripCount(L) <= 5) {
+    UP.PeelCount = 2;
+    UP.AllowPeeling = true;
+  }
 }
 
 unsigned HexagonTTIImpl::getNumberOfRegisters(bool vector) const {
   return vector ? 0 : 32;
 }
 
 unsigned HexagonTTIImpl::getPrefetchDistance() const {
   return getST()->getL1PrefetchDistance();

lib/Transforms/Scalar/LoopUnrollPass.cpp

cl::desc("If the runtime tripcount for the loop is lower than the "
              "threshold, the loop is considered as flat and will be less "
              "aggressively unrolled."));
 
 static cl::opt<bool>
     UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden,
                        cl::desc("Allows loops to be peeled when the dynamic "
                                 "trip count is known to be low."));
 
+extern cl::opt<unsigned> UnrollForcePeelCount;
+
 static cl::opt<bool> UnrollUnrollRemainder(
   "unroll-remainder", cl::Hidden,
   cl::desc("Allow the loop remainder to be unrolled."));
 
 // This option isn't ever intended to be enabled, it serves to allow
 // experiments to check the assumptions about when this kind of revisit is
 // necessary.
 static cl::opt<bool> UnrollRevisitChildLoops(
if (getUnrolledLoopSize(LoopSize, UP) < UP.Threshold) {
           TripMultiple = UP.UpperBound ? 1 : TripMultiple;
           return ExplicitUnroll;
         }
       }
     }
   }
 
   // 4th priority is loop peeling
+  if (UP.PeelCount == 0 || UnrollForcePeelCount.getNumOccurrences() != 0)
+    // Only compute UP.PeelCount if the target or the user has not reset the
+    // default value 0.
     computePeelCount(L, LoopSize, UP, TripCount, SE);
   if (UP.PeelCount) {
     UP.Runtime = false;
     UP.Count = 1;
     return ExplicitUnroll;
   }
 
   // 5th priority is partial unrolling.
   // Try partial unroll only when TripCount could be staticaly calculated.

lib/Transforms/Utils/LoopUnrollPeel.cpp

 #define DEBUG_TYPE "loop-unroll"
 
 STATISTIC(NumPeeled, "Number of loops peeled");
 
 static cl::opt<unsigned> UnrollPeelMaxCount(
     "unroll-peel-max-count", cl::init(7), cl::Hidden,
     cl::desc("Max average trip count which will cause loop peeling."));
 
-static cl::opt<unsigned> UnrollForcePeelCount(
+cl::opt<unsigned> UnrollForcePeelCount(
     "unroll-force-peel-count", cl::init(0), cl::Hidden,
     cl::desc("Force a peel count regardless of profiling information."));
 
 // Designates that a Phi is estimated to become invariant after an "infinite"
 // number of loop iterations (i.e. only may become an invariant if the loop is
 // fully unrolled).
 static const unsigned InfiniteIterationsToInvariance =
     std::numeric_limits<unsigned>::max();
static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount,
 
   return DesiredPeelCount;
 }
 
 // Return the number of iterations we want to peel off.
 void llvm::computePeelCount(Loop *L, unsigned LoopSize,
                             TargetTransformInfo::UnrollingPreferences &UP,
                             unsigned &TripCount, ScalarEvolution &SE) {
   assert(LoopSize > 0 && "Zero loop size is not allowed!");
   UP.PeelCount = 0;
   if (!canPeel(L))
     return;
 
   // Only try to peel innermost loops.
   if (!L->empty())
     return;
 
   // Here we try to get rid of Phis which become invariants after 1, 2, ..., N

 /// for the bulk of dynamic execution, can be further simplified by scalar
 /// optimizations.
 bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
                     ScalarEvolution *SE, DominatorTree *DT,
                     AssumptionCache *AC, bool PreserveLCSSA) {
   if (!canPeel(L))
     return false;
 
+  // Only try to peel innermost loops.
+  if (!L->empty())
+    return false;
+
   LoopBlocksDFS LoopBlocks(L);
   LoopBlocks.perform(LI);
 
   BasicBlock *Header = L->getHeader();
   BasicBlock *PreHeader = L->getLoopPreheader();
   BasicBlock *Latch = L->getLoopLatch();
   BasicBlock *Exit = L->getUniqueExitBlock();
 

test/Transforms/LoopUnroll/Hexagon/peel-small-loop.ll

+; RUN: opt -loop-unroll -mtriple=hexagon -S < %s | FileCheck %s
+; Check that the loop is peeled twice for Hexagon.
+; CHECK: while.body.peel
+; CHECK: while.body.peel2
+
+%struct.STREAM = type { %union.anon, i32, i32 }
+%union.anon = type { i32* }
+
+define void @function(%struct.STREAM* nocapture readonly %b) local_unnamed_addr {
+entry:
+  %bitPtr3 = getelementptr inbounds %struct.STREAM, %struct.STREAM* %b, i32 0, i32 2
+  %0 = load i32, i32* %bitPtr3, align 4
+  %cmp11 = icmp ult i32 %0, 32
+  br i1 %cmp11, label %while.body.preheader, label %do.end
+
+while.body.preheader:
+  %value2 = getelementptr inbounds %struct.STREAM, %struct.STREAM* %b, i32 0, i32 1
+  %1 = load i32, i32* %value2, align 4
+  %w = getelementptr inbounds %struct.STREAM, %struct.STREAM* %b, i32 0, i32 0, i32 0
+  %2 = load i32*, i32** %w, align 4
+  br label %while.body
+
+while.body:
+  %bitPtr.014 = phi i32 [ %add, %while.body ], [ %0, %while.body.preheader ]
+  %value.013 = phi i32 [ %shl, %while.body ], [ %1, %while.body.preheader ]
+  %ptr.012 = phi i32* [ %incdec.ptr, %while.body ], [ %2, %while.body.preheader ]
+  %add = add nuw i32 %bitPtr.014, 8
+  %shr = lshr i32 %value.013, 24
+  %incdec.ptr = getelementptr inbounds i32, i32* %ptr.012, i32 1
+  store i32 %shr, i32* %ptr.012, align 4
+  %shl = shl i32 %value.013, 8
+  %cmp = icmp ult i32 %add, 17
+  br i1 %cmp, label %while.body, label %do.end
+
+do.end:
+  ret void
+}
+