[LCSSA] Perform LCSSA verification only for current loop nest

[igor-laevsky]

Summary

This change continues fixing compile time issues with LCSSA verification (started in https://reviews.llvm.org/D25364)

Currently after running pass on a single loop-nest we run LCSSA verification for all
loops in the function. This proves to be overly expensive and often not needed since
we were changing only single loop nest. Instead I propose to adopt same technique as was
used for the LoopInfo verification. We will explicitly call LCSSA verification for each
loop nest as part of the LPPassManager iteration.

This is a bit non trivial due to the fact that not all loop passes require LCSSA. See
LoopPassPrinter for example. This means that before doing verification we need to check
if LCSSA was preserved by the current pass. In order to do this we can ask "mustPreserveAnalysisID(LCSSAID)".
Unfortunately LCSSA is part of the TransformsUtils library which depends on Analysis
library and we can't reference LCSSAID without introducing cyclic library dependence.

In order to overcome this problem I've added new analysis pass called "LCSSAVerificationPass".
It's transitively required by the LCSSA transform and preserved by all loop passes. It's
only purpose is to indicate to the LPPassManager when we need to run LCSSA verification
and when we don't.

This solution feels a bit wrong and error prone (it's enough to forget to preserve
LCSSAVerificationPass in order to miss verification). However we discussed this in
the "LCSSA verification for the top-level loops" llvm-dev thread and it seemed like
the best one.

[igor-laevsky]

ping?

[mzolotukhin]

Hi Igor,

Sorry for the delay in review. We've discussed this issue already, and the patch does seem like what we agreed on (modulo minor nitpicks).

However, I still feel uneasy about a couple of things. First, adding an extra fake pass for LCSSA verification looks really awkward (I have read the explanation you provided). Second, this all is caused by the fact that not all passes currently require LCSSA, but I'd rather change that, even independently on the patch in question. Do we have other loop passes, except the printer pass, that don't require LCSSA?

Also, related, but not affecting the patch question: what are the slowdowns that you see with full verification after you fixed the recursive verification routine?

I think that this patch can be committed so that your work is no longer affected by the slowdowns, but I would like to continue this discussion and consider other solutions again.

Thanks,
Michael

include/llvm/Analysis/LoopPass.h

160

s/lcssa/LCSSA/

include/llvm/InitializePasses.h

171

This change looks unnecessary (there are no spaces before & in lines below anyway).

lib/Transforms/Utils/LCSSA.cpp

336

s/lcssa/LCSSA/
Let's be consistent :-)

[igor-laevsky]

Hi Michael,

Thanks for the comments!

With linearized implementation of the LCSSA verification we were still experiencing slowdown of the same order of magnitude (10x).

Besides printers there are IVUsers, LoopExtractor and LoopStrengthReduce passes which don't require LCSSA. I don't think it's a big problem if we add explicit LCSSA dependence to them. My biggest concern was about loop printers because there we really want to print ir exactly as it is. It would seem quite unexpected if printer pass will suddenly transform the IR.

include/llvm/Analysis/LoopPass.h

public:
   void deleteSimpleAnalysisLoop(Loop *L);
 
 private:
   std::deque<Loop *> LQ;
   LoopInfo *LI;
   Loop *CurrentLoop;
 };
 
+// This pass is required by the LCSSA transformation. It is used inside
+// LPPassManager to check if current pass preserves lcssa form, and if it does
+// pass manager calls lcssa verification for the current loop.
+struct LCSSAVerificationPass : public FunctionPass {
+  static char ID;
+  LCSSAVerificationPass() : FunctionPass(ID) {
+    initializeLCSSAVerificationPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override { return false; }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+};
+
 } // End llvm namespace
 
 #endif

include/llvm/InitializePasses.h

 void initializeInstrProfilingLegacyPassPass(PassRegistry &);
 void initializeInstructionCombiningPassPass(PassRegistry&);
 void initializeInstructionSelectPass(PassRegistry &);
 void initializeInterleavedAccessPass(PassRegistry &);
 void initializeInternalizeLegacyPassPass(PassRegistry&);
 void initializeIntervalPartitionPass(PassRegistry&);
 void initializeJumpThreadingPass(PassRegistry&);
 void initializeLCSSAWrapperPassPass(PassRegistry &);
-void initializeLegacyLICMPassPass(PassRegistry&);
+void initializeLCSSAVerificationPassPass(PassRegistry &);
+void initializeLegacyLICMPassPass(PassRegistry &);
 void initializeLazyBranchProbabilityInfoPassPass(PassRegistry&);
 void initializeLazyBlockFrequencyInfoPassPass(PassRegistry&);
 void initializeLazyValueInfoWrapperPassPass(PassRegistry&);
 void initializeLegalizerPass(PassRegistry&);
 void initializeLibCallsShrinkWrapLegacyPassPass(PassRegistry&);
 void initializeLintPass(PassRegistry&);
 void initializeLiveDebugValuesPass(PassRegistry&);
 void initializeLiveDebugVariablesPass(PassRegistry&);

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeSCEVAAWrapperPassPass(Registry);
   initializeScalarEvolutionWrapperPassPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);
   initializeTypeBasedAAWrapperPassPass(Registry);
   initializeScopedNoAliasAAWrapperPassPass(Registry);
+  initializeLCSSAVerificationPassPass(Registry);
 }
 
 void LLVMInitializeAnalysis(LLVMPassRegistryRef R) {
   initializeAnalysis(*unwrap(R));
 }
 
 void LLVMInitializeIPA(LLVMPassRegistryRef R) {
   initializeAnalysis(*unwrap(R));

lib/Analysis/LoopPass.cpp

 // This file implements LoopPass and LPPassManager. All loop optimization
 // and transformation passes are derived from LoopPass. LPPassManager is
 // responsible for managing LoopPasses.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/LoopPassManager.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/OptBisect.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
for (Loop *I : reverse(*L))
     addLoopIntoQueue(I, LQ);
 }
 
 /// Pass Manager itself does not invalidate any analysis info.
 void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
   // become part of LPPassManager.
   Info.addRequired<LoopInfoWrapperPass>();
+  Info.addRequired<DominatorTreeWrapperPass>();
   Info.setPreservesAll();
 }
 
 /// run - Execute all of the passes scheduled for execution.  Keep track of
 /// whether any of the passes modifies the function, and if so, return true.
 bool LPPassManager::runOnFunction(Function &F) {
   auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
   LI = &LIWP.getLoopInfo();
+  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   bool Changed = false;
 
   // Collect inherited analysis from Module level pass manager.
   populateInheritedAnalysis(TPM->activeStack);
 
   // Populate the loop queue in reverse program order. There is no clear need to
   // process sibling loops in either forward or reverse order. There may be some
   // advantage in deleting uses in a later loop before optimizing the
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
         // instead of relying on LoopInfo::verifyLoop since LoopInfo
         // is a function pass and it's really expensive to verify every
         // loop in the function every time. That level of checking can be
         // enabled with the -verify-loop-info option.
         {
           TimeRegion PassTimer(getPassTimer(&LIWP));
           CurrentLoop->verifyLoop();
         }
+        // Here we apply same reasoning as in the above case. Only difference
+        // is that LPPassManager might run passes which do not require LCSSA
+        // form (LoopPassPrinter for example). We should skip verification for
+        // such passes.
+        if (mustPreserveAnalysisID(LCSSAVerificationPass::ID))
+          CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI);
 
         // Then call the regular verifyAnalysis functions.
         verifyPreservedAnalysis(P);
 
         F.getContext().yield();
       }
 
       removeNotPreservedAnalysis(P);
if (F->hasFnAttribute(Attribute::OptimizeNone)) {
     // FIXME: Report this to dbgs() only once per function.
     DEBUG(dbgs() << "Skipping pass '" << getPassName()
           << "' in function " << F->getName() << "\n");
     // FIXME: Delete loop from pass manager's queue?
     return true;
   }
   return false;
 }
+
+char LCSSAVerificationPass::ID = 0;
+INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
+                false, false)
+

lib/Transforms/Utils/LCSSA.cpp

 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "lcssa"
 
 STATISTIC(NumLCSSA, "Number of live out of a loop variables");
 
+#ifdef EXPENSIVE_CHECKS
+static bool VerifyLoopLCSSA = true;
+#else
+static bool VerifyLoopLCSSA = false;
+#endif
+static cl::opt<bool,true>
+VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA),
+                    cl::desc("Verify loop lcssa form (time consuming)"));
+
 /// Return true if the specified block is in the list.
 static bool isExitBlock(BasicBlock *BB,
                         const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
   return is_contained(ExitBlocks, BB);
 }
 
 /// For every instruction from the worklist, check to see if it has any uses
 /// that are outside the current loop.  If so, insert LCSSA PHI nodes and
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, *LI); }) &&
+    // This check is very expensive. On the loop intensive compiles it may cause
+    // up to 10x slowdown. Currently it's disabled by default. LPPassManager
+    // always does limited form of the lcssa verification. Similar reasoning
+    // was used for the LoopInfo verifier.
+    if (VerifyLoopLCSSA) {
+      assert(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();
 
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addPreservedID(LoopSimplifyID);
     AU.addPreserved<AAResultsWrapperPass>();
     AU.addPreserved<BasicAAWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addPreserved<ScalarEvolutionWrapperPass>();
     AU.addPreserved<SCEVAAWrapperPass>();
+
+    // This is needed to perform LCSSA verification inside LPPassManager
+    AU.addRequired<LCSSAVerificationPass>();
+    AU.addPreserved<LCSSAVerificationPass>();
   }
 };
 }
 
 char LCSSAWrapperPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LCSSAVerificationPass)
 INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
                     false, false)
 
 Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
 char &llvm::LCSSAID = LCSSAWrapperPass::ID;
 
 /// Transform \p F into loop-closed SSA form.
 bool LCSSAWrapperPass::runOnFunction(Function &F) {

lib/Transforms/Utils/LoopUtils.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) {
   // We must also preserve LoopSimplify and LCSSA. We locally access their IDs
   // here because users shouldn't directly get them from this header.
   extern char &LoopSimplifyID;
   extern char &LCSSAID;
   AU.addRequiredID(LoopSimplifyID);
   AU.addPreservedID(LoopSimplifyID);
   AU.addRequiredID(LCSSAID);
   AU.addPreservedID(LCSSAID);
+  // This is used in the LPPassManager to perform LCSSA verification on passes
+  // which preserve lcssa form
+  AU.addRequired<LCSSAVerificationPass>();
+  AU.addPreserved<LCSSAVerificationPass>();
 
   // Loop passes are designed to run inside of a loop pass manager which means
   // that any function analyses they require must be required by the first loop
   // pass in the manager (so that it is computed before the loop pass manager
   // runs) and preserved by all loop pasess in the manager. To make this
   // reasonably robust, the set needed for most loop passes is maintained here.
   // If your loop pass requires an analysis not listed here, you will need to
   // carefully audit the loop pass manager nesting structure that results.