[LCSSA] Use linear algorithm for isRecursivelyLCSSAForm

[igor-laevsky]

Summary

Currently 'isRecursivelyLCSSAForm' has quadratic complexity on the number of
loop basic blocks. This caused by the fact that in each recursion level we will
visit all blocks from the current loop and all of it's sub-loops. On the next
recursive call we will step into one of the sub-loops and revisit same basic blocks.
We can address that by limiting iteration only on the blocks which are located
directly in the current loop. We know that all sub-loops will be checked by the
following recursive process.

This change is motivated by the 10x slow-down on one of our internal loop
intensive tests (Release+Asserts build). It started to happen after introduction
of the additional lcssa verification - https://github.com/llvm-mirror/llvm/commit/79e702086510fa7b52de178354eab34a7f641025

Unfortunately even with this change we are still experiencing huge slow down. I think
this may be the result of calling LCSSAWrapperPass::verifyAnalysis for the whole
function for each loop. Maybe there is a way we can more efficiently structure this code?

[mzolotukhin]

Hi Igor,

Thanks for working on this! I have two concerns/thoughts:

1. Is it actually equivalent to the original implementation? It looks so, but we need to check the corner cases and be 100% sure that it's the case. Usually the bugs we detect with such verifiers are in corner cases.
2. If it's equivalent to the original, why do we need to be recursive at all? We can go through all blocks of the given loop but for each block find the innermost loop containing it and check if the value isn't used outside of it. What do you think?

As for the slowdown, we can put it under some flag, but I'm a bit reluctant to it - we've found quite a few bugs when we started to verify LCSSA, and it's good to have it turned on by default. And unfortunately checking only the current loop is not sufficient, because transformations can change outer loops.

Thanks,
Michael

[reames]

In D25364#564603, @mzolotukhin wrote:

2. If it's equivalent to the original, why do we need to be recursive at all? We can go through all blocks of the given loop but for each block find the innermost loop containing it and check if the value isn't used outside of it. What do you think?

I really like this framing. Rather than asking whether each sub-loop is in LCSSA, we would essentially ask whether each BB is in LCSSA w.r.t. it's inner most containing loop. Because we know all of the blocks within a sub-loop are also contained within an outer loop, this gives us the transitive property we need.

However, it does look like we don't currently verify the contains relation for sub-loops. This may be covered by the off by default LoopInfo.verify(), but it's not directly enforced. Not sure we need to block this patch on that fact, but the lack of verification makes me a bit nervous.

[reames]

In D25364#564896, @reames wrote:

However, it does look like we don't currently verify the contains relation for sub-loops.

Correction: This is checked by verifyLoop

[igor-laevsky]

Thanks for the comments!

Michael, your second point seems very reasonable. Please take a look at the updated diff. I kept the original name "isRecursivelyLCSSAForm", despite that function is no longer recursive. I think it still describes the process fairly well.

I agree that putting LCSSAWrapperPass::verifyAnalysis under a flag isn't a good way to deal with the slowdown. Can't we apply same technique as was used for the verifyLoop (https://github.com/llvm-mirror/llvm/blob/93e6e5414ded14bcbb233baaaa5567132fee9a0c/lib/Analysis/LoopPass.cpp#L219)? I.e add explicit verification inside LPPassManager for each of the top-level loops.

[mzolotukhin]

Hi Igor,

The patch looks good to me, thank you for doing this!

I agree that putting LCSSAWrapperPass::verifyAnalysis under a flag isn't a good way to deal with the slowdown. Can't we apply same technique as was used for the verifyLoop (https://github.com/llvm-mirror/llvm/blob/93e6e5414ded14bcbb233baaaa5567132fee9a0c/lib/Analysis/LoopPass.cpp#L219)? I.e add explicit verification inside LPPassManager for each of the top-level loops.

Do I understand it correctly, that we'll be checking LCSSA only for the current loop after each loop-pass? I think it should be sufficient, because if a pass breaks LCSSA, we should fail when LPM proceeds to the parent loop. However, for the sake of easier debugging I would prefer to allow full verification as we have it right now too, probably under -verify-loop-info as well (or under another flag). It really helps to find the broken pass faster.

Thanks,
Michael

[igor-laevsky]

Hi Michael,

Do I understand it correctly, that we'll be checking LCSSA only for the current loop after each loop-pass? I think it should be sufficient, because if a pass breaks LCSSA, we should fail when LPM proceeds to the parent loop. However, for the sake of easier debugging I would prefer to allow full verification as we have it right now too, probably under -verify-loop-info as well (or under another flag). It really helps to find the broken pass faster.

Yes, this is the plan. I will send patch up for review in a nearest future.

include/llvm/Analysis/LoopInfo.h

public:
   /// variable.
   ///
   PHINode *getCanonicalInductionVariable() const;
 
   /// Return true if the Loop is in LCSSA form.
   bool isLCSSAForm(DominatorTree &DT) const;
 
   /// Return true if this Loop and all inner subloops are in LCSSA form.
-  bool isRecursivelyLCSSAForm(DominatorTree &DT) const;
+  /// When 'LI' is null this function has quadratic complexity on the number
+  /// of loop blocks. Linear algorithm is used otherwise.
+  bool isRecursivelyLCSSAForm(DominatorTree &DT,
+                              const LoopInfo *LI = nullptr) const;
 
   /// Return true if the Loop is in the form that the LoopSimplify form
   /// transforms loops to, which is sometimes called normal form.
   bool isLoopSimplifyForm() const;
 
   /// Return true if the loop body is safe to clone in practice.
   bool isSafeToClone() const;
 

lib/Analysis/LoopInfo.cpp

if (ConstantInt *CI =
                 Inc->getOperand(0) == PN)
             if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
               if (CI->equalsInt(1))
                 return PN;
   }
   return nullptr;
 }
 
-bool Loop::isLCSSAForm(DominatorTree &DT) const {
-  for (BasicBlock *BB : this->blocks()) {
+// Return true if the Loop is in LCSSA form.
+// When 'LI' is non-null we only check blocks located directly inside 'L' and
+// not in one of it's sub-loops.
+// This functionality is used in 'isRecursivelyLCSSAForm' to prevent us
+// from re-checking basic blocks from the nested loops.
+static bool isLCSSAFormImpl(const Loop &L, DominatorTree &DT,
+                            const LoopInfo *LI) {
+  for (BasicBlock *BB : L.blocks()) {
     for (Instruction &I : *BB) {
       // Tokens can't be used in PHI nodes and live-out tokens prevent loop
       // optimizations, so for the purposes of considered LCSSA form, we
       // can ignore them.
       if (I.getType()->isTokenTy())
         continue;
 
+      // Only visit blocks located directly inside the current loop
+      if (LI && LI->getLoopFor(BB) != &L)
+        continue;
+
       for (Use &U : I.uses()) {
         Instruction *UI = cast<Instruction>(U.getUser());
         BasicBlock *UserBB = UI->getParent();
         if (PHINode *P = dyn_cast<PHINode>(UI))
           UserBB = P->getIncomingBlock(U);
 
         // Check the current block, as a fast-path, before checking whether
         // the use is anywhere in the loop.  Most values are used in the same
         // block they are defined in.  Also, blocks not reachable from the
         // entry are special; uses in them don't need to go through PHIs.
         if (UserBB != BB &&
-            !contains(UserBB) &&
+            !L.contains(UserBB) &&
             DT.isReachableFromEntry(UserBB))
           return false;
       }
     }
   }
 
   return true;
 }
 
-bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT) const {
-  if (!isLCSSAForm(DT))
+bool Loop::isLCSSAForm(DominatorTree &DT) const {
+  return isLCSSAFormImpl(*this, DT, nullptr);
+}
+
+bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT,
+                                  const LoopInfo *LI /* = nullptr */) const {
+  if (!isLCSSAFormImpl(*this, DT, LI))
     return false;
 
-  return all_of(*this,
-                [&](const Loop *L) { return L->isRecursivelyLCSSAForm(DT); });
+  return all_of(
+      *this, [&](const Loop *L) { return L->isRecursivelyLCSSAForm(DT, LI); });
 }
 
 bool Loop::isLoopSimplifyForm() const {
   // Normal-form loops have a preheader, a single backedge, and all of their
   // exits have all their predecessors inside the loop.
   return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
 }
 

lib/Transforms/Scalar/IndVarSimplify.cpp

 /// current expressions.
 ///
 /// This is mostly redundant with the regular IndVarSimplify activities that
 /// happen later, except that it's more powerful in some cases, because it's
 /// able to brute-force evaluate arbitrary instructions as long as they have
 /// constant operands at the beginning of the loop.
 void IndVarSimplify::rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
   // Check a pre-condition.
-  assert(L->isRecursivelyLCSSAForm(*DT) && "Indvars did not preserve LCSSA!");
+  assert(L->isRecursivelyLCSSAForm(*DT, LI) &&
+         "Indvars did not preserve LCSSA!");
 
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getUniqueExitBlocks(ExitBlocks);
 
   SmallVector<RewritePhi, 8> RewritePhiSet;
   // Find all values that are computed inside the loop, but used outside of it.
   // Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
   // the exit blocks of the loop to find them.

 }
 
 //===----------------------------------------------------------------------===//
 //  IndVarSimplify driver. Manage several subpasses of IV simplification.
 //===----------------------------------------------------------------------===//
 
 bool IndVarSimplify::run(Loop *L) {
   // We need (and expect!) the incoming loop to be in LCSSA.
-  assert(L->isRecursivelyLCSSAForm(*DT) && "LCSSA required to run indvars!");
+  assert(L->isRecursivelyLCSSAForm(*DT, LI) &&
+         "LCSSA required to run indvars!");
 
   // If LoopSimplify form is not available, stay out of trouble. Some notes:
   //  - LSR currently only supports LoopSimplify-form loops. Indvars'
   //    canonicalization can be a pessimization without LSR to "clean up"
   //    afterwards.
   //  - We depend on having a preheader; in particular,
   //    Loop::getCanonicalInductionVariable only supports loops with preheaders,
   //    and we're in trouble if we can't find the induction variable even when
#endif
   // trip count and therefore can further simplify exit values in addition to
   // rewriteLoopExitValues.
   rewriteFirstIterationLoopExitValues(L);
 
   // Clean up dead instructions.
   Changed |= DeleteDeadPHIs(L->getHeader(), TLI);
 
   // Check a post-condition.
-  assert(L->isRecursivelyLCSSAForm(*DT) && "Indvars did not preserve LCSSA!");
+  assert(L->isRecursivelyLCSSAForm(*DT, LI) &&
+         "Indvars did not preserve LCSSA!");
 
   // Verify that LFTR, and any other change have not interfered with SCEV's
   // ability to compute trip count.
 #ifndef NDEBUG
   if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
     SE->forgetLoop(L);
     const SCEV *NewBECount = SE->getBackedgeTakenCount(L);
     if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) <

lib/Transforms/Utils/LCSSA.cpp

struct LCSSAWrapperPass : public FunctionPass {
   // Cached analysis information for the current function.
   DominatorTree *DT;
   LoopInfo *LI;
   ScalarEvolution *SE;
 
   bool runOnFunction(Function &F) override;
   void verifyAnalysis() const override {
     assert(
-        all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); }) &&
+        all_of(*LI,
+               [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, LI); }) &&
         "LCSSA form is broken!");
   };
 
   /// This transformation requires natural loop information & requires that
   /// loop preheaders be inserted into the CFG.  It maintains both of these,
   /// as well as the CFG.  It also requires dominator information.
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();

lib/Transforms/Utils/LoopSimplify.cpp

if (PreserveLCSSA) {
     // Fix LCSSA form for L. Some values, which previously were only used inside
     // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
     // in corresponding exit blocks.
     // We don't need to form LCSSA recursively, because there cannot be uses
     // inside a newly created loop of defs from inner loops as those would
     // already be a use of an LCSSA phi node.
     formLCSSA(*L, *DT, LI, SE);
 
-    assert(NewOuter->isRecursivelyLCSSAForm(*DT) &&
+    assert(NewOuter->isRecursivelyLCSSAForm(*DT, LI) &&
            "LCSSA is broken after separating nested loops!");
   }
 
   return NewOuter;
 }
 
 /// \brief This method is called when the specified loop has more than one
 /// backedge in it.
bool LoopSimplify::runOnFunction(Function &F) {
   AssumptionCache *AC =
       &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 
   bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 #ifndef NDEBUG
   if (PreserveLCSSA) {
     assert(DT && "DT not available.");
     assert(LI && "LI not available.");
-    bool InLCSSA =
-        all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+    bool InLCSSA = all_of(
+        *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, LI); });
     assert(InLCSSA && "Requested to preserve LCSSA, but it's already broken.");
   }
 #endif
 
   // Simplify each loop nest in the function.
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
     Changed |= simplifyLoop(*I, DT, LI, SE, AC, PreserveLCSSA);
 
 #ifndef NDEBUG
   if (PreserveLCSSA) {
-    bool InLCSSA =
-        all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+    bool InLCSSA = all_of(
+        *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, LI); });
     assert(InLCSSA && "LCSSA is broken after loop-simplify.");
   }
 #endif
   return Changed;
 }
 
 PreservedAnalyses LoopSimplifyPass::run(Function &F,
                                         FunctionAnalysisManager &AM) {