[LAA] Relax restrictions on early exits in loop structure

[reames]

Summary

This is a preparation patch for supporting multiple exits in the loop vectorizer, by itself it should be purely NFC. This patch moves the loop structure checks from LAA to their respective consumers (where duplicates don't already exist).

Why do this? Well, after auditing the code, I can't actually find anything in LAA itself which relies on having all instructions within a loop execute an equal number of times. This patch simply makes this explicit so that if one consumer - say LV in the near future (hopefully) - wants to handle a broader class of loops, it can do so.

[reames]

ping

[reames]

ping

[Ayal]

This looks good to me, adding some minor comments. Thanks!

I can't actually find anything in LAA itself which relies on having all instructions within a loop execute an equal number of times.

Well, LAA's RuntimePointerChecking::insert() relies on getBackedgeTakenCount() to provide "the" trip-count, which may vary for distinct instructions if the loop is not bottom-tested. But it does provide an upper-bound for all instructions, i.e., a safe, conservative value. In other words, a slightly tighter runtime check could potentially be provided for pointers accessed one less iteration, appearing 'below' the exiting block.

(where duplicates don't already exist)

LV indeed checks for single-exit-at-bottom by itself, in LVL.canVectorize*(). Curious to see this restriction being lifted! It is somewhat related to "massaging" inner loops when vectorizing an outer loop.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1789

Note: these DEBUG messages get lost.

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

673

This existing !getExitBlock() check indeed saves us from introducing an additional !getExitingBlock() check; worth a comment, here and/or in LoopInfo?
Note that L may have a single exit block B and multiple exiting blocks - all jumping to B. But getExitBlock() returns false for such an L, in contrast to getUniqueExitBlock() which returns true. I.e., getExitBlock() does imply getExitingBlock().

679

May be worth noting in the patch summary that some ORE and LAA debug messages are added and dropped, respectively.

684

Hoist or remove above comment?

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

630

Does this (TODO?) comment imply that in present/future this limitation can/should be dropped?

[fhahn]

LGTM, thanks! It looks like there are some formatting issues, please re-format before landing.

In D92066#2450541, @Ayal wrote:

I can't actually find anything in LAA itself which relies on having all instructions within a loop execute an equal number of times.

Well, LAA's RuntimePointerChecking::insert() relies on getBackedgeTakenCount() to provide "the" trip-count, which may vary for distinct instructions if the loop is not bottom-tested. But it does provide an upper-bound for all instructions, i.e., a safe, conservative value. In other words, a slightly tighter runtime check could potentially be provided for pointers accessed one less iteration, appearing 'below' the exiting block.

That matches my understanding as well. The current approach should be conservatively correct, with potential for making LAA smarter when it comes to reasoning about dependences only along certain exit paths in the future.

[reames]

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

630

I was thinking of it more as explaining why a random check exists. Someone interested could certainly relax this, I have no intention to pursue.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

bool LoopAccessInfo::canAnalyzeLoop() {
   if (TheLoop->getNumBackEdges() != 1) {
     LLVM_DEBUG(
         dbgs() << "LAA: loop control flow is not understood by analyzer\n");
     recordAnalysis("CFGNotUnderstood")
         << "loop control flow is not understood by analyzer";
     return false;
   }
 
-  // We must have a single exiting block.
-  if (!TheLoop->getExitingBlock()) {
-    LLVM_DEBUG(
-        dbgs() << "LAA: loop control flow is not understood by analyzer\n");
-    recordAnalysis("CFGNotUnderstood")
-        << "loop control flow is not understood by analyzer";
-    return false;
-  }
-
-  // We only handle bottom-tested loops, i.e. loop in which the condition is
-  // checked at the end of each iteration. With that we can assume that all
-  // instructions in the loop are executed the same number of times.
-  if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
-    LLVM_DEBUG(
-        dbgs() << "LAA: loop control flow is not understood by analyzer\n");
-    recordAnalysis("CFGNotUnderstood")
-        << "loop control flow is not understood by analyzer";
-    return false;
-  }
-
   // ScalarEvolution needs to be able to find the exit count.
   const SCEV *ExitCount = PSE->getBackedgeTakenCount();
   if (ExitCount == PSE->getSE()->getCouldNotCompute()) {
     recordAnalysis("CantComputeNumberOfIterations")
         << "could not determine number of loop iterations";
     LLVM_DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n");
     return false;
   }

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

public:
   /// Try to distribute an inner-most loop.
   bool processLoop(std::function<const LoopAccessInfo &(Loop &)> &GetLAA) {
     assert(L->isInnermost() && "Only process inner loops.");
 
     LLVM_DEBUG(dbgs() << "\nLDist: In \""
                       << L->getHeader()->getParent()->getName()
                       << "\" checking " << *L << "\n");
 
     if (!L->getExitBlock())
       return fail("MultipleExitBlocks", "multiple exit blocks");
     if (!L->isLoopSimplifyForm())
       return fail("NotLoopSimplifyForm",
                   "loop is not in loop-simplify form");
+    if (!L->isRotatedForm())
+      return fail("NotBottomTested",
+                  "loop is not bottom tested");
 
     BasicBlock *PH = L->getLoopPreheader();
 
     // LAA will check that we only have a single exiting block.
     LAI = &GetLAA(*L);
 
     // Currently, we only distribute to isolate the part of the loop with
     // dependence cycles to enable partial vectorization.
     if (LAI->canVectorizeMemory())
       return fail("MemOpsCanBeVectorized",
                   "memory operations are safe for vectorization");
 

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

for (Loop *TopLevelLoop : LI)
     for (Loop *L : depth_first(TopLevelLoop))
       // We only handle inner-most loops.
       if (L->isInnermost())
         Worklist.push_back(L);
 
   // Now walk the identified inner loops.
   bool Changed = false;
   for (Loop *L : Worklist) {
+    // Match historical behavior
+    if (!L->isRotatedForm() || !L->getExitingBlock())
+      continue;
     // The actual work is performed by LoadEliminationForLoop.
     LoadEliminationForLoop LEL(L, &LI, GetLAI(*L), &DT, BFI, PSI);
     Changed |= LEL.processLoop();
   }
   return Changed;
 }
 
 namespace {

llvm/lib/Transforms/Utils/LoopVersioning.cpp

for (Loop *TopLevelLoop : *LI)
     for (Loop *L : depth_first(TopLevelLoop))
       // We only handle inner-most loops.
       if (L->isInnermost())
         Worklist.push_back(L);
 
   // Now walk the identified inner loops.
   bool Changed = false;
   for (Loop *L : Worklist) {
+    if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||
+  !L->getExitingBlock())
+      continue;
     const LoopAccessInfo &LAI = GetLAA(*L);
-    if (L->isLoopSimplifyForm() && !LAI.hasConvergentOp() &&
+    if (!LAI.hasConvergentOp() &&
         (LAI.getNumRuntimePointerChecks() ||
          !LAI.getPSE().getUnionPredicate().isAlwaysTrue())) {
       LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L,
                           LI, DT, SE);
       LVer.versionLoop();
       LVer.annotateLoopWithNoAlias();
       Changed = true;
     }