[GVN] Preserve MemorySSA if it is available.

[fhahn]

Summary

Preserve MemorySSA if it is available before running GVN.

DSE with MemorySSA will run closely after GVN. If GVN and 2 other
passes preserve MemorySSA, DSE can re-use MemorySSA used by LICM
when doing LTO.

[fhahn]

Use createMemoryAccessAfter with the appropriate defining access.

[asbirlea]

Not exactly the path I had in mind (working on newGVN was), but that's a longer avenue and I'm curious to see the compile-time impact of preserving MSSA :-)

llvm/lib/Transforms/Scalar/GVN.cpp

1342

I don't think this is right. Def can be a MemoryUse and that should not be a defining access.
I *think* it should take
MemoryAccess *Def2=isa<MemoryUse>(Def)? Def->getDefiningAccess():Def;
(with some proper var renaming)

This also shows MSSA should have an assert checking for this internally, I'll have to add that.

Please also add a MSSA verification at the end of the pass

if (MSSA && VerifyMemorySSA)
   MSSA->verifyMemorySSA();

2220

Optional or std::unique_ptr?
Previous cases used unique ptr, with MSSAU.get() passed as argument below.

[fhahn]

Fix MemorySSA update for PRE loads. They are inserted just before the terminator, so we can just use createAccessInBB with BeforeTerminator position and the defining access of the original load.

In D86534#2243422, @asbirlea wrote:

Not exactly the path I had in mind (working on newGVN was), but that's a longer avenue and I'm curious to see the compile-time impact of preserving MSSA :-)

Ideally NewGVN would be ready, but unfortunately there are still a few bigger issues. I intend to pick this back up after wrapping up a few other things.

Preserving MemorySSA is crucial to stay compile-time competitive with LTO, geomean ReleaseLTO -0.58%, ReleaseLTO (link only) -1.24%

http://llvm-compile-time-tracker.com/compare.php?from=d24856f1e0485c1a619528359e3cfd3dc8d15857&to=062412e79fcfedf2cf004433e42036b0333e3f83&stat=instructions

[fhahn]

This comment has been deleted.

llvm/lib/Transforms/Scalar/GVN.cpp

1342

yes this was not entirely right. I think we can simply use createMemoryAccessInBB, as we insert just before the terminator. LI is always a MemoryUse, so the defining access of the the new load should be just the defining access of the original load.

This seems to work fine with building SPEC2000/SPEC2006/MultiSource with expensive MemSSA verification.

2220

Are you suggesting to use a unique_ptr in runImpl to manage a dynamically allocated updater in runImpl? I am not sure if that would be a big advantage, as constructing the Updater unconditionally on the stack should be quite cheap and we don't have to worry about dynamic allocations.

[asbirlea]

llvm/lib/Transforms/Scalar/GVN.cpp

1342

Regarding the comment: "Get the defining access of the original load. The inserted loads are guaranteed to load from the same definition."

I thought about this when adding the comment, and I was going to suggest exactly this. But, thinking further, I don't think setting the defining access as LI's defining access is always correct.
Assume MSSA is further used, then the defining access used here may decide further optimizations. For example, it may say that it's ok to hoist NewLoad above LI, even though LI may be volatile and a MemoryDef in the MSSA representation.

Come to think about it, if LI is volatile, so will NewLoad, so this should check NewLoad's access and use insertDef if that's the case, because accesses further down will need updating then.

If LI is always removed (NewLoad is a replacement), and it's always a use, then it's correct to use LI's defining access. But I don't understand GVN's innards enough at this point to make this assessment.

2220

Sure, that works.

2280

Remove braces.

llvm/test/Transforms/GVN/preserve-memoryssa.ll

3 ↗

(On Diff #288705)

; REQUIRES: asserts

[fhahn]

Also handle the case that LI could be a MemoryDef.

[fhahn]

llvm/lib/Transforms/Scalar/GVN.cpp

1342

Come to think about it, if LI is volatile, so will NewLoad, so this should check NewLoad's access and use insertDef if that's the case, because accesses further down will need updating then.

Oh right, I did not consider that LI could actually be a MemoryDef itself (e.g. volatile load)! I adjusted the code, to use the MemoryAcc for LI directly if it is a def and the defining access otherwise. I also updated the code to use insertDef, if the new access is actually a MemoryDef. I don't think GVN currently does load PRE for volatile loads, but it is probably better to handle all possible cases here. I updated the comment as well.

If LI is always removed (NewLoad is a replacement), and it's always a use, then it's correct to use LI's defining access. But I don't understand GVN's innards enough at this point to make this assessment.

I am not sure myself if it is removed in all cases, but it is probably better to be conservative. If the load gets removed, the memory access gets also removed and the the updating mechanism should take care of that.

[fhahn]

Handle case when the new load is a memorydef.

[fhahn]

Add MemorySSA to preserved set for NPM too.

[asbirlea]

Changes look good.
Please also test with EXPENSIVE_CHECKS. The additional MSSA verifications there can unearth missed changes.

[fhahn]

In D86534#2253736, @asbirlea wrote:

Changes look good.
Please also test with EXPENSIVE_CHECKS. The additional MSSA verifications there can unearth missed changes.

Thanks, I did a bootstrap build of LLVM with expensive MemorySSA verification and the test-suite with the set of patches to preserve MemSSA. The tests here and D86651 are from problems surfaced through that testing :)

[uabelho]

Hi!

The following crashes for me with this patch
opt -memoryssa -gvn -early-cse-memssa -S -o - foo.ll

with foo.ll being just

define void @f() {
entry:
  unreachable
}

I get

opt: ../lib/IR/LegacyPassManager.cpp:657: void llvm::PMTopLevelManager::setLastUser(ArrayRef<llvm::Pass *>, llvm::Pass *): Assertion `AnalysisPass && "Expected analysis pass to exist."' failed.

[fhahn]

In D86534#2256179, @uabelho wrote:

Hi!

The following crashes for me with this patch
opt -memoryssa -gvn -early-cse-memssa -S -o - foo.ll

with foo.ll being just

define void @f() {
entry:
  unreachable
}

I get

opt: ../lib/IR/LegacyPassManager.cpp:657: void llvm::PMTopLevelManager::setLastUser(ArrayRef<llvm::Pass *>, llvm::Pass *): Assertion `AnalysisPass && "Expected analysis pass to exist."' failed.

Thanks for the report. Looks like there is a problem with MemorySSAWrapperPass depending on AAResultsWrapperPass, which is not explicitly preserved by GVN. The problem can be solved by explicitly requiring AAResultsWrapperPass in EarlyCSE or by preserved AAResultsWrapper pass in GVN. I put up a patch for review/discussion for the best place to fix: D87137

llvm/include/llvm/Transforms/Scalar/GVN.h

 class CallInst;
 class Constant;
 class ExtractValueInst;
 class Function;
 class FunctionPass;
 class IntrinsicInst;
 class LoadInst;
 class LoopInfo;
+class MemorySSA;
+class MemorySSAUpdater;
 class OptimizationRemarkEmitter;
 class PHINode;
 class TargetLibraryInfo;
 class Value;
-
 /// A private "module" namespace for types and utilities used by GVN. These
 /// are implementation details and should not be used by clients.
 namespace gvn LLVM_LIBRARY_VISIBILITY {
 
 struct AvailableValue;
 struct AvailableValueInBlock;
 class GVNLegacyPass;
 
private:
   MemoryDependenceResults *MD = nullptr;
   DominatorTree *DT = nullptr;
   const TargetLibraryInfo *TLI = nullptr;
   AssumptionCache *AC = nullptr;
   SetVector<BasicBlock *> DeadBlocks;
   OptimizationRemarkEmitter *ORE = nullptr;
   ImplicitControlFlowTracking *ICF = nullptr;
   LoopInfo *LI = nullptr;
+  MemorySSAUpdater *MSSAU = nullptr;
 
   ValueTable VN;
 
   /// A mapping from value numbers to lists of Value*'s that
   /// have that value number.  Use findLeader to query it.
   struct LeaderTableEntry {
     Value *Val;
     const BasicBlock *BB;
private:
 
   using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
   using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
   using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
 
   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
                MemoryDependenceResults *RunMD, LoopInfo *LI,
-               OptimizationRemarkEmitter *ORE);
+               OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
 
   /// Push a new Value to the LeaderTable onto the list for its value number.
   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
     LeaderTableEntry &Curr = LeaderTable[N];
     if (!Curr.Val) {
       Curr.Val = V;
       Curr.BB = BB;
       return;

llvm/lib/Transforms/Scalar/GVN.cpp

 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
   // behavior, but until then don't change the order here.
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
   auto *MemDep =
       isMemDepEnabled() ? &AM.getResult<MemoryDependenceAnalysis>(F) : nullptr;
   auto *LI = AM.getCachedResult<LoopAnalysis>(F);
+  auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
-  bool Changed = runImpl(F, AC, DT, TLI, AA, MemDep, LI, &ORE);
+  bool Changed = runImpl(F, AC, DT, TLI, AA, MemDep, LI, &ORE,
+                         MSSA ? &MSSA->getMSSA() : nullptr);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<GlobalsAA>();
   PA.preserve<TargetLibraryAnalysis>();
   if (LI)
     PA.preserve<LoopAnalysis>();
for (const auto &PredLoad : PredLoads) {
     BasicBlock *UnavailablePred = PredLoad.first;
     Value *LoadPtr = PredLoad.second;
 
     auto *NewLoad = new LoadInst(
         LI->getType(), LoadPtr, LI->getName() + ".pre", LI->isVolatile(),
         LI->getAlign(), LI->getOrdering(), LI->getSyncScopeID(),
         UnavailablePred->getTerminator());
     NewLoad->setDebugLoc(LI->getDebugLoc());
+    if (MSSAU) {
+      auto *NewAccess = MSSAU->createMemoryAccessInBB(
+          NewLoad, nullptr, NewLoad->getParent(), MemorySSA::BeforeTerminator);
+      MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);
+    }
 
     // Transfer the old load's AA tags to the new load.
     AAMDNodes Tags;
     LI->getAAMetadata(Tags);
     if (Tags)
       NewLoad->setAAMetadata(Tags);
 
     if (auto *MD = LI->getMetadata(LLVMContext::MD_invariant_load))
bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) {
   Value *V = IntrinsicI->getArgOperand(0);
 
   if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
     if (Cond->isZero()) {
       Type *Int8Ty = Type::getInt8Ty(V->getContext());
       // Insert a new store to null instruction before the load to indicate that
       // this code is not reachable.  FIXME: We could insert unreachable
       // instruction directly because we can modify the CFG.
-      new StoreInst(UndefValue::get(Int8Ty),
+      auto *NewS = new StoreInst(UndefValue::get(Int8Ty),
                                  Constant::getNullValue(Int8Ty->getPointerTo()),
                                  IntrinsicI);
+      if (MSSAU) {
+        auto *NewDef = MSSAU->createMemoryAccessInBB(
+            NewS, nullptr, NewS->getParent(), MemorySSA::BeforeTerminator);
+        MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/true);
+      }
     }
     if (isAssumeWithEmptyBundle(*IntrinsicI))
       markInstructionForDeletion(IntrinsicI);
     return false;
   } else if (isa<Constant>(V)) {
     // If it's not false, and constant, it must evaluate to true. This means our
     // assume is assume(true), and thus, pointless, and we don't want to do
     // anything more here.
bool GVN::processLoad(LoadInst *L) {
 
   AvailableValue AV;
   if (AnalyzeLoadAvailability(L, Dep, L->getPointerOperand(), AV)) {
     Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this);
 
     // Replace the load!
     patchAndReplaceAllUsesWith(L, AvailableValue);
     markInstructionForDeletion(L);
+    if (MSSAU)
+      MSSAU->removeMemoryAccess(L);
     ++NumGVNLoad;
     reportLoadElim(L, AvailableValue, ORE);
     // Tell MDA to rexamine the reused pointer since we might have more
     // information after forwarding it.
     if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
       MD->invalidateCachedPointerInfo(AvailableValue);
     return true;
   }
bool GVN::processInstruction(Instruction *I) {
   markInstructionForDeletion(I);
   return true;
 }
 
 /// runOnFunction - This is the main transformation entry point for a function.
 bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                   const TargetLibraryInfo &RunTLI, AAResults &RunAA,
                   MemoryDependenceResults *RunMD, LoopInfo *LI,
-                  OptimizationRemarkEmitter *RunORE) {
+                  OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {
+  MemorySSAUpdater Updater(MSSA);
   AC = &RunAC;
   DT = &RunDT;
   VN.setDomTree(DT);
   TLI = &RunTLI;
   VN.setAliasAnalysis(&RunAA);
   MD = RunMD;
   ImplicitControlFlowTracking ImplicitCFT;
   ICF = &ImplicitCFT;
   this->LI = LI;
   VN.setMemDep(MD);
   ORE = RunORE;
   InvalidBlockRPONumbers = true;
+  MSSAU = MSSA ? &Updater : nullptr;
 
   bool Changed = false;
   bool ShouldContinue = true;
 
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   // Merge unconditional branches, allowing PRE to catch more
   // optimization opportunities.
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
     BasicBlock *BB = &*FI++;
 
-    bool removedBlock = MergeBlockIntoPredecessor(BB, &DTU, LI, nullptr, MD);
+    bool removedBlock = MergeBlockIntoPredecessor(BB, &DTU, LI, MSSAU, MD);
     if (removedBlock)
       ++NumGVNBlocks;
 
     Changed |= removedBlock;
   }
 
   unsigned Iteration = 0;
   while (ShouldContinue) {
bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
   // we can't do this until PRE's critical edge splitting updates memdep.
   // Actually, when this happens, we should just fully integrate PRE into GVN.
 
   cleanupGlobalSets();
   // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
   // iteration.
   DeadBlocks.clear();
 
   return Changed;
 }
 
 bool GVN::processBlock(BasicBlock *BB) {
   // FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
   // (and incrementing BI before processing an instruction).
   assert(InstrsToErase.empty() &&
          "We expect InstrsToErase to be empty across iterations");
   if (DeadBlocks.count(BB))
if (!AtStart)
       --BI;
 
     for (auto *I : InstrsToErase) {
       assert(I->getParent() == BB && "Removing instruction from wrong block?");
       LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n');
       salvageKnowledge(I, AC);
       salvageDebugInfo(*I);
       if (MD) MD->removeInstruction(I);
+      if (MSSAU)
+        MSSAU->removeMemoryAccess(I);
       LLVM_DEBUG(verifyRemoved(I));
       ICF->removeInstruction(I);
       I->eraseFromParent();
     }
     InstrsToErase.clear();
 
     if (AtStart)
       BI = BB->begin();
if (NumWithout != 0) {
     // on the function.
     unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);
     if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
       toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
       return false;
     }
     // We need to insert somewhere, so let's give it a shot
     PREInstr = CurInst->clone();
+    assert(!isa<LoadInst>(PREInstr));
     if (!performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo)) {
       // If we failed insertion, make sure we remove the instruction.
       LLVM_DEBUG(verifyRemoved(PREInstr));
       PREInstr->deleteValue();
       return false;
     }
   }
 
bool GVN::performScalarPRE(Instruction *CurInst) {
   if (MD && Phi->getType()->isPtrOrPtrVectorTy())
     MD->invalidateCachedPointerInfo(Phi);
   VN.erase(CurInst);
   removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
 
   LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
   if (MD)
     MD->removeInstruction(CurInst);
+  if (MSSAU)
+    MSSAU->removeMemoryAccess(CurInst);
   LLVM_DEBUG(verifyRemoved(CurInst));
   // FIXME: Intended to be markInstructionForDeletion(CurInst), but it causes
   // some assertion failures.
   ICF->removeInstruction(CurInst);
   CurInst->eraseFromParent();
   ++NumGVNInstr;
 
   return true;

 
 /// Split the critical edge connecting the given two blocks, and return
 /// the block inserted to the critical edge.
 BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
   // GVN does not require loop-simplify, do not try to preserve it if it is not
   // possible.
   BasicBlock *BB = SplitCriticalEdge(
       Pred, Succ,
-      CriticalEdgeSplittingOptions(DT, LI).unsetPreserveLoopSimplify());
+      CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());
   if (MD)
     MD->invalidateCachedPredecessors();
   InvalidBlockRPONumbers = true;
   return BB;
 }
 
 /// Split critical edges found during the previous
 /// iteration that may enable further optimization.
 bool GVN::splitCriticalEdges() {
   if (toSplit.empty())
     return false;
   do {
     std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val();
     SplitCriticalEdge(Edge.first, Edge.second,
-                      CriticalEdgeSplittingOptions(DT, LI));
+                      CriticalEdgeSplittingOptions(DT, LI, MSSAU));
   } while (!toSplit.empty());
   if (MD) MD->invalidateCachedPredecessors();
   InvalidBlockRPONumbers = true;
   return true;
 }
 
 /// Executes one iteration of GVN
 bool GVN::iterateOnFunction(Function &F) {
public:
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
 
+    auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
     return Impl.runImpl(
         F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
         getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
         getAnalysis<AAResultsWrapperPass>().getAAResults(),
         Impl.isMemDepEnabled()
             ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()
             : nullptr,
         LIWP ? &LIWP->getLoopInfo() : nullptr,
-        &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
+        &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),
+        MSSAWP ? &MSSAWP->getMSSA() : nullptr);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     if (Impl.isMemDepEnabled())
       AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
 
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addPreserved<TargetLibraryInfoWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
+    AU.addPreserved<MemorySSAWrapperPass>();
   }
 
 private:
   GVN Impl;
 };
 
 char GVNLegacyPass::ID = 0;