Refine the loop rotation's API

[jinlin]

Summary

The following changes addresses the following two issues.

1. The existing loop rotation pass contains both loop latch simplification and loop rotation. So one flag RotationOnly is added to be passed to the loop rotation pass.
2. The threshold value is initialized with MAX_UINT since the loop rotation utility should not have threshold limit.

[efriedma]

include/llvm/Transforms/Utils/LoopRotationUtils.h

30 ↗

(On Diff #142222)

It would be better to have a separate API for latch simplification, rather than a boolean parameter to LoopRotation.

lib/Transforms/Utils/LoopRotationUtils.cpp

215 ↗

(On Diff #142222)

This is a heuristic.

226 ↗

(On Diff #142222)

This is a heuristic.

538 ↗

(On Diff #142222)

This is a heuristic.

[jinlin]

include/llvm/Transforms/Utils/LoopRotationUtils.h

30 ↗

(On Diff #142222)

If someone is interested in having a new API for latch simplification, he can feel free to add it. The purpose of my change is to provide an API for the loop rotation.

lib/Transforms/Utils/LoopRotationUtils.cpp

215 ↗

(On Diff #142222)

This is not heuristic. According to the comments, the loop header is not loop exit means that the loop has been rotated or is not suitable for loop rotation.

226 ↗

(On Diff #142222)

I believe the condition L->isLoopExiting(OrigLatch) is always false at this place.

However, I can add one more flag to indicate that the profitability check should be skipped here.

538 ↗

(On Diff #142222)

This is not heuristic. The reason the loop rotation gives up at this place is because the implementation of loop rotation has some limitation and it cannot convert this kind of loop into do-while loop.

[efriedma]

include/llvm/Transforms/Utils/LoopRotationUtils.h

30 ↗

(On Diff #142222)

Even if you don't actually need the latch-simplification API, it would make the rotation API easier to understand. But you can leave it like this for now.

The new arguments need to be documented.

lib/Transforms/Utils/LoopRotationUtils.cpp

215 ↗

(On Diff #142222)

You're right, sorry. (I guess you technically could clone the header in other cases, but it wouldn't really be "rotation" in the traditional sense.)

538 ↗

(On Diff #142222)

Checking anything other than isSafeToSpeculativelyExecute() is a heuristic; the actual transform doesn't depend on anything else. That said, I guess it isn't useful to control this heuristic if you're not going to separate out the latch simplification API.

[jinlin]

include/llvm/Transforms/Utils/LoopRotationUtils.h

30 ↗

(On Diff #142222)

Many thanks for your review. I have updated the comments.

lib/Transforms/Utils/LoopRotationUtils.cpp

538 ↗

(On Diff #142222)

I see. Many thanks for your explanation.

[jinlin]

There is no progress with this review. I wonder whether I need to provide some additional information to move things forward.

[efriedma]

LGTM

[jinlin]

Thanks Eli for your review.

llvm/trunk/include/llvm/Transforms/Utils/LoopRotationUtils.h

 class AssumptionCache;
 class DominatorTree;
 class Loop;
 class LoopInfo;
 class ScalarEvolution;
 struct SimplifyQuery;
 class TargetTransformInfo;
 
-/// \brief Convert a loop into a loop with bottom test.
-bool LoopRotation(Loop *L, unsigned MaxHeaderSize, LoopInfo *LI,
-                  const TargetTransformInfo *TTI, AssumptionCache *AC,
-                  DominatorTree *DT, ScalarEvolution *SE,
-                  const SimplifyQuery &SQ);
+/// \brief Convert a loop into a loop with bottom test. It may
+/// perform loop latch simplication as well if the flag RotationOnly
+/// is false. The flag Threshold represents the size threshold of the loop
+/// header. If the loop header's size exceeds the threshold, the loop rotation
+/// will give up. The flag IsUtilMode controls the heuristic used in the
+/// LoopRotation. If it is true, the profitability heuristic will be ignored.
+bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
+                  AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE,
+                  const SimplifyQuery &SQ, bool RotationOnly,
+                  unsigned Threshold, bool IsUtilMode);
 
 } // namespace llvm
 
 #endif

llvm/trunk/lib/Transforms/Scalar/LoopRotation.cpp

 
 PreservedAnalyses LoopRotatePass::run(Loop &L, LoopAnalysisManager &AM,
                                       LoopStandardAnalysisResults &AR,
                                       LPMUpdater &) {
   int Threshold = EnableHeaderDuplication ? DefaultRotationThreshold : 0;
   const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
   const SimplifyQuery SQ = getBestSimplifyQuery(AR, DL);
 
-  bool Changed =
-      LoopRotation(&L, Threshold, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE, SQ);
+  bool Changed = LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE, SQ,
+                              false, Threshold, false);
 
   if (!Changed)
     return PreservedAnalyses::all();
 
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
     auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
     auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     auto *SE = SEWP ? &SEWP->getSE() : nullptr;
     const SimplifyQuery SQ = getBestSimplifyQuery(*this, F);
-    return LoopRotation(L, MaxHeaderSize, LI, TTI, AC, DT, SE, SQ);
+    return LoopRotation(L, LI, TTI, AC, DT, SE, SQ, false, MaxHeaderSize,
+                        false);
   }
 };
 }
 
 char LoopRotateLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
                     false)
 
 Pass *llvm::createLoopRotatePass(int MaxHeaderSize) {
   return new LoopRotateLegacyPass(MaxHeaderSize);
 }

llvm/trunk/lib/Transforms/Utils/LoopRotationUtils.cpp

 class LoopRotate {
   const unsigned MaxHeaderSize;
   LoopInfo *LI;
   const TargetTransformInfo *TTI;
   AssumptionCache *AC;
   DominatorTree *DT;
   ScalarEvolution *SE;
   const SimplifyQuery &SQ;
+  bool RotationOnly;
+  bool IsUtilMode;
 
 public:
   LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
              const TargetTransformInfo *TTI, AssumptionCache *AC,
-             DominatorTree *DT, ScalarEvolution *SE, const SimplifyQuery &SQ)
+             DominatorTree *DT, ScalarEvolution *SE, const SimplifyQuery &SQ,
+             bool RotationOnly, bool IsUtilMode)
       : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),
-        SQ(SQ) {}
+        SQ(SQ), RotationOnly(RotationOnly), IsUtilMode(IsUtilMode) {}
   bool processLoop(Loop *L);
 
 private:
   bool rotateLoop(Loop *L, bool SimplifiedLatch);
   bool simplifyLoopLatch(Loop *L);
 };
 } // end anonymous namespace
 
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
 
   // If the loop latch already contains a branch that leaves the loop then the
   // loop is already rotated.
   if (!OrigLatch)
     return false;
 
   // Rotate if either the loop latch does *not* exit the loop, or if the loop
   // latch was just simplified. Or if we think it will be profitable.
-  if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch &&
+  if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode == false &&
       !shouldRotateLoopExitingLatch(L))
     return false;
 
   // Check size of original header and reject loop if it is very big or we can't
   // duplicate blocks inside it.
   {
     SmallPtrSet<const Value *, 32> EphValues;
     CodeMetrics::collectEphemeralValues(L, AC, EphValues);
bool LoopRotate::simplifyLoopLatch(Loop *L) {
   return true;
 }
 
 /// Rotate \c L, and return true if any modification was made.
 bool LoopRotate::processLoop(Loop *L) {
   // Save the loop metadata.
   MDNode *LoopMD = L->getLoopID();
 
+  bool SimplifiedLatch = false;
+
   // Simplify the loop latch before attempting to rotate the header
   // upward. Rotation may not be needed if the loop tail can be folded into the
   // loop exit.
-  bool SimplifiedLatch = simplifyLoopLatch(L);
+  if (!RotationOnly)
+    SimplifiedLatch = simplifyLoopLatch(L);
 
   bool MadeChange = rotateLoop(L, SimplifiedLatch);
   assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&
          "Loop latch should be exiting after loop-rotate.");
 
   // Restore the loop metadata.
   // NB! We presume LoopRotation DOESN'T ADD its own metadata.
   if ((MadeChange || SimplifiedLatch) && LoopMD)
     L->setLoopID(LoopMD);
 
   return MadeChange || SimplifiedLatch;
 }
 
 
 /// The utility to convert a loop into a loop with bottom test.
-bool llvm::LoopRotation(Loop *L, unsigned MaxHeaderSize, LoopInfo *LI,
-                        const TargetTransformInfo *TTI, AssumptionCache *AC,
-                        DominatorTree *DT, ScalarEvolution *SE,
-                        const SimplifyQuery &SQ) {
-  LoopRotate LR(MaxHeaderSize, LI, TTI, AC, DT, SE, SQ);
+bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
+                        AssumptionCache *AC, DominatorTree *DT,
+                        ScalarEvolution *SE, const SimplifyQuery &SQ,
+                        bool RotationOnly = true,
+                        unsigned Threshold = unsigned(-1),
+                        bool IsUtilMode = true) {
+  LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, SQ, RotationOnly, IsUtilMode);
 
   return LR.processLoop(L);
 }