[MemorySSA] LCSSA preserves MemorySSA.

[asbirlea]

Summary

Enabling MemorySSA in the old pass manager leads to MemorySSA being run
twice due to the fact that LCSSA and LoopSimplify do not preserve
MemorySSA. This is the first step to address that: target LCSSA.

LCSSA does not make any changes that invalidate MemorySSA, so it
preserves it by design. It must preserve AA as well, for this to hold.

After this patch, MemorySSA is still run twice.
Step two follows: target LoopSimplify.

[efriedma]

lib/Transforms/Utils/LCSSA.cpp

418

This variable is unused?

[asbirlea]

Simplify patch to only rpeserve and not require.

[asbirlea]

Rebase.

[chandlerc]

Mostly questions around the AA manager preservation, see inline.

include/llvm/Analysis/LoopAnalysisManager.h

64–66

You should move the definition as well as the declaration.

It does make sense to me to put this in MemorySSA.cpp itself -- its something a bunch of users of it need to coordinate about, including the loop analysis manager.

lib/Transforms/Utils/LCSSA.cpp

492–493

Should the AA manager just preserve itself instead so that this isn't so confusing for users?

[asbirlea]

lib/Transforms/Utils/LCSSA.cpp

492–493

Sure? I though it was stateless already, so preserved by default, but I'm unclear how to mark that.

This got me *very* confused in the first iteration of this patch, when I noticed a new AAManager being built for the LoopPassManager. Why would that happen?

[chandlerc]

lib/Transforms/Utils/LCSSA.cpp

492–493

It really should be, but it isn't built that way yet. This should probably be a preparatory patch. It'll just involve removing the check for the AAManager itself in the AAResults::invalidate method and adding relevant documentation.

Would be good to very explicitly document that all the AAs need to be registered *before* the AAManager is run in that case.

[asbirlea]

Rebase on top of D60914, remove the need to preserve AAManager.

[chandlerc]

LGTM

include/llvm/Analysis/LoopAnalysisManager.h

struct LoopStandardAnalysisResults {
   DominatorTree &DT;
   LoopInfo &LI;
   ScalarEvolution &SE;
   TargetLibraryInfo &TLI;
   TargetTransformInfo &TTI;
   MemorySSA *MSSA;
 };
 
-/// Enables memory ssa as a dependency for loop passes.
-extern cl::opt<bool> EnableMSSALoopDependency;
-
 /// Extern template declaration for the analysis set for this IR unit.
 extern template class AllAnalysesOn<Loop>;
 
 extern template class AnalysisManager<Loop, LoopStandardAnalysisResults &>;
 /// The loop analysis manager.
 ///
 /// See the documentation for the AnalysisManager template for detail
 /// documentation. This typedef serves as a convenient way to refer to this

include/llvm/Analysis/MemorySSA.h

 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <utility>
 
 namespace llvm {
 
+/// Enables memory ssa as a dependency for loop passes.
+extern cl::opt<bool> EnableMSSALoopDependency;
+
 class Function;
 class Instruction;
 class MemoryAccess;
 class MemorySSAWalker;
 class LLVMContext;
 class raw_ostream;
 
 namespace MSSAHelpers {

lib/Analysis/LoopAnalysisManager.cpp

 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
 namespace llvm {
-/// Enables memory ssa as a dependency for loop passes in legacy pass manager.
-cl::opt<bool> EnableMSSALoopDependency(
-    "enable-mssa-loop-dependency", cl::Hidden, cl::init(false),
-    cl::desc("Enable MemorySSA dependency for loop pass manager"));
-
 // Explicit template instantiations and specialization definitions for core
 // template typedefs.
 template class AllAnalysesOn<Loop>;
 template class AnalysisManager<Loop, LoopStandardAnalysisResults &>;
 template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>;
 template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop,
                                          LoopStandardAnalysisResults &>;
 

lib/Analysis/MemorySSA.cpp

cl::desc("The maximum number of stores/phis MemorySSA"
              "will consider trying to walk past (default = 100)"));
 
 // Always verify MemorySSA if expensive checking is enabled.
 #ifdef EXPENSIVE_CHECKS
 bool llvm::VerifyMemorySSA = true;
 #else
 bool llvm::VerifyMemorySSA = false;
 #endif
+/// Enables memory ssa as a dependency for loop passes in legacy pass manager.
+cl::opt<bool> llvm::EnableMSSALoopDependency(
+    "enable-mssa-loop-dependency", cl::Hidden, cl::init(false),
+    cl::desc("Enable MemorySSA dependency for loop pass manager"));
+
 static cl::opt<bool, true>
     VerifyMemorySSAX("verify-memoryssa", cl::location(VerifyMemorySSA),
                      cl::Hidden, cl::desc("Enable verification of MemorySSA."));
 
 namespace llvm {
 
 /// An assembly annotator class to print Memory SSA information in
 /// comments.

lib/Transforms/Utils/LCSSA.cpp

 #include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Utils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #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");
 
LCSSAWrapperPass() : FunctionPass(ID) {
     initializeLCSSAWrapperPassPass(*PassRegistry::getPassRegistry());
   }
 
   // Cached analysis information for the current function.
   DominatorTree *DT;
   LoopInfo *LI;
   ScalarEvolution *SE;
 
   bool runOnFunction(Function &F) override;
   void verifyAnalysis() const override {
     // 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) {
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addPreservedID(LoopSimplifyID);
     AU.addPreserved<AAResultsWrapperPass>();
     AU.addPreserved<BasicAAWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addPreserved<ScalarEvolutionWrapperPass>();
     AU.addPreserved<SCEVAAWrapperPass>();
     AU.addPreserved<BranchProbabilityInfoWrapperPass>();
+    AU.addPreserved<MemorySSAWrapperPass>();
 
     // This is needed to perform LCSSA verification inside LPPassManager
     AU.addRequired<LCSSAVerificationPass>();
     AU.addPreserved<LCSSAVerificationPass>();
   }
 };
 }
 
if (!formLCSSAOnAllLoops(&LI, DT, SE))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<BasicAA>();
   PA.preserve<GlobalsAA>();
   PA.preserve<SCEVAA>();
   PA.preserve<ScalarEvolutionAnalysis>();
   // BPI maps terminators to probabilities, since we don't modify the CFG, no
   // updates are needed to preserve it.
   PA.preserve<BranchProbabilityAnalysis>();
+  PA.preserve<MemorySSAAnalysis>();
   return PA;
 }