[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 ↗

(On Diff #139743)

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 ↗

(On Diff #139743)

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 ↗

(On Diff #139743)

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

490

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 ↗

(On Diff #139743)

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 ↗

(On Diff #139743)

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

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;
+  // Only try to peel innermost loops with small runtime trip counts.
+  if (L && L->empty() &&
+      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/Utils/LoopUnrollPeel.cpp

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!");
+  if (!canPeel(L)) {
     UP.PeelCount = 0;
-  if (!canPeel(L))
     return;
+  }
 
   // Only try to peel innermost loops.
-  if (!L->empty())
+  if (!L->empty()) {
+    UP.PeelCount = 0;
     return;
+  }
 
   // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
   // iterations of the loop. For this we compute the number for iterations after
   // which every Phi is guaranteed to become an invariant, and try to peel the
   // maximum number of iterations among these values, thus turning all those
   // Phis into invariants.
   // First, check that we can peel at least one iteration.
   if (2 * LoopSize <= UP.Threshold && UnrollPeelMaxCount > 0) {
     // Store the pre-calculated values here.
     SmallDenseMap<PHINode *, unsigned> IterationsToInvariance;
     // Now go through all Phis to calculate their the number of iterations they
     // need to become invariants.
-    unsigned DesiredPeelCount = 0;
+    // Start the max computation with the UP.PeelCount value set by the target
+    // in TTI.getUnrollingPreferences or by the flag -unroll-peel-count.
+    unsigned DesiredPeelCount = UP.PeelCount;
     BasicBlock *BackEdge = L->getLoopLatch();
     assert(BackEdge && "Loop is not in simplified form?");
     for (auto BI = L->getHeader()->begin(); isa<PHINode>(&*BI); ++BI) {
       PHINode *Phi = cast<PHINode>(&*BI);
       unsigned ToInvariance = calculateIterationsToInvariance(
           Phi, L, BackEdge, IterationsToInvariance);
       if (ToInvariance != InfiniteIterationsToInvariance)
         DesiredPeelCount = std::max(DesiredPeelCount, ToInvariance);
if (DesiredPeelCount > 0) {
                    << " some Phis into invariants.\n");
       UP.PeelCount = DesiredPeelCount;
       return;
     }
   }
 
   // Bail if we know the statically calculated trip count.
   // In this case we rather prefer partial unrolling.
-  if (TripCount)
+  if (TripCount) {
+    UP.PeelCount = 0;
     return;
+  }
 
   // If the user provided a peel count, use that.
   bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
   if (UserPeelCount) {
     DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
                  << " iterations.\n");
     UP.PeelCount = UnrollForcePeelCount;
     return;
   }
 
   // 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 (UP.AllowPeeling && L->getHeader()->getParent()->hasProfileData()) {
     Optional<unsigned> PeelCount = getLoopEstimatedTripCount(L);
-    if (!PeelCount)
+    if (!PeelCount) {
+      UP.PeelCount = 0;
       return;
+    }
 
     DEBUG(dbgs() << "Profile-based estimated trip count is " << *PeelCount
                  << "\n");
 
     if (*PeelCount) {
       if ((*PeelCount <= UnrollPeelMaxCount) &&
           (LoopSize * (*PeelCount + 1) <= UP.Threshold)) {
         DEBUG(dbgs() << "Peeling first " << *PeelCount << " iterations.\n");
         UP.PeelCount = *PeelCount;
         return;
       }
       DEBUG(dbgs() << "Requested peel count: " << *PeelCount << "\n");
       DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
       DEBUG(dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1) << "\n");
       DEBUG(dbgs() << "Max peel cost: " << UP.Threshold << "\n");
     }
   }
+  UP.PeelCount = 0;
 }
 
 /// \brief 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. 
 /// Our goal is to make sure that:
 /// a) The total weight of all the copies of the loop body is preserved.

 /// optimizations.
 bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
                     ScalarEvolution *SE, DominatorTree *DT,
                     AssumptionCache *AC, bool PreserveLCSSA) {
   if (!canPeel(L))
     return false;
 
   LoopBlocksDFS LoopBlocks(L);
   LoopBlocks.perform(LI);
 
   BasicBlock *Header = L->getHeader();
   BasicBlock *PreHeader = L->getLoopPreheader();
   BasicBlock *Latch = L->getLoopLatch();
   BasicBlock *Exit = L->getUniqueExitBlock();
 
   Function *F = Header->getParent();
 

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
+}
+