GVN-hoist: avoid calling MemoryLocation::get() on a call (PR30499)

[sebpop]

Summary

For some reason in the cleanup or in the change I did to use the MemorySSA.cpp interface, I introduced more calls to MemoryLocation::get() without checking whether the instruction was a call.
I will apply this patch on top of yesterday's fix (that got reverted.)
This should fix the ICE in Chromium builds.

llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h

 };
 
 inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) {
   return upward_defs_iterator(Pair);
 }
 
 inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
 
+// Return true when MD may alias MU, return false otherwise.
+bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
+                         AliasAnalysis &AA);
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_MEMORYSSA_H

llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp

 // 2. In some cases reduce critical path (by exposing more ILP).
 //
 // Hoisting may affect the performance in some cases. To mitigate that, hoisting
 // is disabled in the following cases.
 // 1. Scalars across calls.
 // 2. geps when corresponding load/store cannot be hoisted.
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Transforms/Scalar.h"
-#include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/MemorySSA.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "gvn-hoist"
 
 STATISTIC(NumHoisted, "Number of instructions hoisted");
static cl::opt<int> MaxNumberOfBBSInPath(
     cl::desc("Max number of basic blocks on the path between "
              "hoisting locations (default = 4, unlimited = -1)"));
 
 static cl::opt<int> MaxDepthInBB(
     "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
     cl::desc("Hoist instructions from the beginning of the BB up to the "
              "maximum specified depth (default = 100, unlimited = -1)"));
 
-static cl::opt<int> MaxChainLength(
-    "gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
+static cl::opt<int>
+    MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
                    cl::desc("Maximum length of dependent chains to hoist "
                             "(default = 10, unlimited = -1)"));
 
 namespace {
 
 // Provides a sorting function based on the execution order of two instructions.
 struct SortByDFSIn {
 private:
   DenseMap<const Value *, unsigned> &DFSNumber;
 
bool operator()(const Instruction *A, const Instruction *B) const {
     unsigned ADFS, BDFS;
     if (BA == BB) {
       ADFS = DFSNumber.lookup(A);
       BDFS = DFSNumber.lookup(B);
     } else {
       ADFS = DFSNumber.lookup(BA);
       BDFS = DFSNumber.lookup(BB);
     }
-    assert (ADFS && BDFS);
+    assert(ADFS && BDFS);
     return ADFS < BDFS;
   }
 };
 
 // A map from a pair of VNs to all the instructions with those VNs.
 typedef DenseMap<std::pair<unsigned, unsigned>, SmallVector<Instruction *, 4>>
     VNtoInsns;
 // An invalid value number Used when inserting a single value number into
bool run(Function &F) {
     VN.setAliasAnalysis(AA);
     VN.setMemDep(MD);
     bool Res = false;
     // Perform DFS Numbering of instructions.
     unsigned BBI = 0;
     for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
       DFSNumber[BB] = ++BBI;
       unsigned I = 0;
-      for (auto &Inst: *BB)
+      for (auto &Inst : *BB)
         DFSNumber[&Inst] = ++I;
     }
 
     int ChainLength = 0;
 
     // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
     while (1) {
       if (MaxChainLength != -1 && ++ChainLength >= MaxChainLength)
while (1) {
         // hoist all scalars dependent on the hoisted ld/st.
         VN.clear();
 
       Res = true;
     }
 
     return Res;
   }
+
 private:
   GVN::ValueTable VN;
   DominatorTree *DT;
   AliasAnalysis *AA;
   MemoryDependenceResults *MD;
   MemorySSA *MSSA;
   const bool OptForMinSize;
   const bool HoistingGeps;
for (auto It = df_begin(HoistBB), E = df_end(HoistBB); It != E;) {
       ++It;
     }
 
     return true;
   }
 
   /* Return true when I1 appears before I2 in the instructions of BB.  */
   bool firstInBB(const Instruction *I1, const Instruction *I2) {
-    assert (I1->getParent() == I2->getParent());
+    assert(I1->getParent() == I2->getParent());
     unsigned I1DFS = DFSNumber.lookup(I1);
     unsigned I2DFS = DFSNumber.lookup(I2);
-    assert (I1DFS && I2DFS);
+    assert(I1DFS && I2DFS);
     return I1DFS < I2DFS;
   }
 
-  // Return true when there are users of Def in BB.
-  bool hasMemoryUseOnPath(MemoryAccess *Def, const BasicBlock *BB,
-                          const Instruction *OldPt) {
-    const BasicBlock *DefBB = Def->getBlock();
-    const BasicBlock *OldBB = OldPt->getParent();
+  // Return true when there are memory uses of Def in BB.
+  bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
+                    const BasicBlock *BB) {
+    const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
+    if (!Acc)
+      return false;
 
-    for (User *U : Def->users())
-      if (auto *MU = dyn_cast<MemoryUse>(U)) {
-        // FIXME: MU->getBlock() does not get updated when we move the instruction.
-        BasicBlock *UBB = MU->getMemoryInst()->getParent();
-        // Only analyze uses in BB.
-        if (BB != UBB)
-          continue;
+    Instruction *OldPt = Def->getMemoryInst();
+    const BasicBlock *OldBB = OldPt->getParent();
+    const BasicBlock *NewBB = NewPt->getParent();
+    bool ReachedNewPt = false;
 
-        // A use in the same block as the Def is on the path.
-        if (UBB == DefBB) {
-          assert(MSSA->locallyDominates(Def, MU) && "def not dominating use");
-          return true;
-        }
+    for (const MemoryAccess &MA : *Acc)
+      if (const MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
+        Instruction *Insn = MU->getMemoryInst();
 
-        if (UBB != OldBB)
-          return true;
+        // Do not check whether MU aliases Def when MU occurs after OldPt.
+        if (BB == OldBB && firstInBB(OldPt, Insn))
+          break;
 
-        // It is only harmful to hoist when the use is before OldPt.
-        if (firstInBB(MU->getMemoryInst(), OldPt))
+        // Do not check whether MU aliases Def when MU occurs before NewPt.
+        if (BB == NewBB) {
+          if (!ReachedNewPt) {
+            if (firstInBB(Insn, NewPt))
+              continue;
+            ReachedNewPt = true;
+          }
+        }
+        if (defClobbersUseOrDef(Def, MU, *AA))
           return true;
       }
 
     return false;
   }
 
   // Return true when there are exception handling or loads of memory Def
-  // between OldPt and NewPt.
+  // between Def and NewPt.  This function is only called for stores: Def is
+  // the MemoryDef of the store to be hoisted.
 
   // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
   // return true when the counter NBBsOnAllPaths reaces 0, except when it is
   // initialized to -1 which is unlimited.
-  bool hasEHOrLoadsOnPath(const Instruction *NewPt, const Instruction *OldPt,
-                          MemoryAccess *Def, int &NBBsOnAllPaths) {
+  bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
+                          int &NBBsOnAllPaths) {
     const BasicBlock *NewBB = NewPt->getParent();
-    const BasicBlock *OldBB = OldPt->getParent();
+    const BasicBlock *OldBB = Def->getBlock();
     assert(DT->dominates(NewBB, OldBB) && "invalid path");
-    assert(DT->dominates(Def->getBlock(), NewBB) &&
+    assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
            "def does not dominate new hoisting point");
 
     // Walk all basic blocks reachable in depth-first iteration on the inverse
     // CFG from OldBB to NewBB. These blocks are all the blocks that may be
     // executed between the execution of NewBB and OldBB. Hoisting an expression
     // from OldBB into NewBB has to be safe on all execution paths.
     for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
       if (*I == NewBB) {
         // Stop traversal when reaching HoistPt.
         I.skipChildren();
         continue;
       }
 
       // Impossible to hoist with exceptions on the path.
       if (hasEH(*I))
         return true;
 
       // Check that we do not move a store past loads.
-      if (hasMemoryUseOnPath(Def, *I, OldPt))
+      if (hasMemoryUse(NewPt, Def, *I))
         return true;
 
       // Stop walk once the limit is reached.
       if (NBBsOnAllPaths == 0)
         return true;
 
       // -1 is unlimited number of blocks on all paths.
       if (NBBsOnAllPaths != -1)
bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
     if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
       if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
         if (firstInBB(NewPt, UD->getMemoryInst()))
           // Cannot move the load or store to NewPt above its definition in D.
           return false;
 
     // Check for unsafe hoistings due to side effects.
     if (K == InsKind::Store) {
-      if (hasEHOrLoadsOnPath(NewPt, OldPt, D, NBBsOnAllPaths))
+      if (hasEHOrLoadsOnPath(NewPt, dyn_cast<MemoryDef>(U), NBBsOnAllPaths))
         return false;
     } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
       return false;
 
     if (UBB == NewBB) {
       if (DT->properlyDominates(DBB, NewBB))
         return true;
       assert(UBB == DBB);
private:
   }
 
   // Same as allOperandsAvailable with recursive check for GEP operands.
   bool allGepOperandsAvailable(const Instruction *I,
                                const BasicBlock *HoistPt) const {
     for (const Use &Op : I->operands())
       if (const auto *Inst = dyn_cast<Instruction>(&Op))
         if (!DT->dominates(Inst->getParent(), HoistPt)) {
-          if (const GetElementPtrInst *GepOp = dyn_cast<GetElementPtrInst>(Inst)) {
+          if (const GetElementPtrInst *GepOp =
+                  dyn_cast<GetElementPtrInst>(Inst)) {
             if (!allGepOperandsAvailable(GepOp, HoistPt))
               return false;
             // Gep is available if all operands of GepOp are available.
           } else {
             // Gep is not available if it has operands other than GEPs that are
             // defined in blocks not dominating HoistPt.
             return false;
           }
         }
     return true;
   }
 
   // Make all operands of the GEP available.
   void makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
                          const SmallVecInsn &InstructionsToHoist,
                          Instruction *Gep) const {
-    assert(allGepOperandsAvailable(Gep, HoistPt) && "GEP operands not available");
+    assert(allGepOperandsAvailable(Gep, HoistPt) &&
+           "GEP operands not available");
 
     Instruction *ClonedGep = Gep->clone();
     for (unsigned i = 0, e = Gep->getNumOperands(); i != e; ++i)
       if (Instruction *Op = dyn_cast<Instruction>(Gep->getOperand(i))) {
 
         // Check whether the operand is already available.
         if (DT->dominates(Op->getParent(), HoistPt))
           continue;
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<MemorySSAWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<MemorySSAWrapperPass>();
   }
 };
 } // namespace
 
-PreservedAnalyses GVNHoistPass::run(Function &F,
-                                    FunctionAnalysisManager &AM) {
+PreservedAnalyses GVNHoistPass::run(Function &F, FunctionAnalysisManager &AM) {
   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
   AliasAnalysis &AA = AM.getResult<AAManager>(F);
   MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
   MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
   GVNHoist G(&DT, &AA, &MD, &MSSA, F.optForMinSize());
   if (!G.run(F))
     return PreservedAnalyses::all();
 

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

if (MLOC.IsCall)
                               MLOC.getCS().getCalledValue()));
     return hash_combine(
         MLOC.IsCall, DenseMapInfo<MemoryLocation>::getHashValue(MLOC.getLoc()));
   }
   static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) {
     return LHS == RHS;
   }
 };
-}
-
-namespace {
-struct UpwardsMemoryQuery {
-  // True if our original query started off as a call
-  bool IsCall;
-  // The pointer location we started the query with. This will be empty if
-  // IsCall is true.
-  MemoryLocation StartingLoc;
-  // This is the instruction we were querying about.
-  const Instruction *Inst;
-  // The MemoryAccess we actually got called with, used to test local domination
-  const MemoryAccess *OriginalAccess;
-
-  UpwardsMemoryQuery()
-      : IsCall(false), Inst(nullptr), OriginalAccess(nullptr) {}
-
-  UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
-      : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) {
-    if (!IsCall)
-      StartingLoc = MemoryLocation::get(Inst);
-  }
-};
-
-static bool lifetimeEndsAt(MemoryDef *MD, const MemoryLocation &Loc,
-                           AliasAnalysis &AA) {
-  Instruction *Inst = MD->getMemoryInst();
-  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
-    switch (II->getIntrinsicID()) {
-    case Intrinsic::lifetime_start:
-    case Intrinsic::lifetime_end:
-      return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), Loc);
-    default:
-      return false;
-    }
-  }
-  return false;
-}
 
 enum class Reorderability { Always, IfNoAlias, Never };
 
 /// This does one-way checks to see if Use could theoretically be hoisted above
 /// MayClobber. This will not check the other way around.
 ///
 /// This assumes that, for the purposes of MemorySSA, Use comes directly after
 /// MayClobber, with no potentially clobbering operations in between them.
static Reorderability getLoadReorderability(const LoadInst *Use,
   bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent;
   bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(),
                                                      AtomicOrdering::Acquire);
   if (SeqCstUse || MayClobberIsAcquire)
     return Reorderability::Never;
   return Result;
 }
 
-static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysis &AA,
-                                                   const Instruction *I) {
-  // If the memory can't be changed, then loads of the memory can't be
-  // clobbered.
-  //
-  // FIXME: We should handle invariant groups, as well. It's a bit harder,
-  // because we need to pay close attention to invariant group barriers.
-  return isa<LoadInst>(I) && (I->getMetadata(LLVMContext::MD_invariant_load) ||
-                              AA.pointsToConstantMemory(I));
-}
-
 static bool instructionClobbersQuery(MemoryDef *MD,
                                      const MemoryLocation &UseLoc,
                                      const Instruction *UseInst,
                                      AliasAnalysis &AA) {
   Instruction *DefInst = MD->getMemoryInst();
   assert(DefInst && "Defining instruction not actually an instruction");
 
   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
if (auto *UseLoad = dyn_cast<LoadInst>(UseInst)) {
         return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad));
       }
     }
   }
 
   return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod;
 }
 
+// Return true when MD may alias MU, return false otherwise.
+bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
+                         AliasAnalysis &AA) {
+  Instruction *UseInst = MU->getMemoryInst();
+  MemoryLocation UseLoc;
+  if (ImmutableCallSite(UseInst))
+    UseLoc = MemoryLocation();
+  else
+    UseLoc = MemoryLocation::get(UseInst);
+  return instructionClobbersQuery(MD, UseLoc, UseInst, AA);
+}
+}
+
+namespace {
+struct UpwardsMemoryQuery {
+  // True if our original query started off as a call
+  bool IsCall;
+  // The pointer location we started the query with. This will be empty if
+  // IsCall is true.
+  MemoryLocation StartingLoc;
+  // This is the instruction we were querying about.
+  const Instruction *Inst;
+  // The MemoryAccess we actually got called with, used to test local domination
+  const MemoryAccess *OriginalAccess;
+
+  UpwardsMemoryQuery()
+      : IsCall(false), Inst(nullptr), OriginalAccess(nullptr) {}
+
+  UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
+      : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) {
+    if (!IsCall)
+      StartingLoc = MemoryLocation::get(Inst);
+  }
+};
+
+static bool lifetimeEndsAt(MemoryDef *MD, const MemoryLocation &Loc,
+                           AliasAnalysis &AA) {
+  Instruction *Inst = MD->getMemoryInst();
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
+    switch (II->getIntrinsicID()) {
+    case Intrinsic::lifetime_start:
+    case Intrinsic::lifetime_end:
+      return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), Loc);
+    default:
+      return false;
+    }
+  }
+  return false;
+}
+
+static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysis &AA,
+                                                   const Instruction *I) {
+  // If the memory can't be changed, then loads of the memory can't be
+  // clobbered.
+  //
+  // FIXME: We should handle invariant groups, as well. It's a bit harder,
+  // because we need to pay close attention to invariant group barriers.
+  return isa<LoadInst>(I) && (I->getMetadata(LLVMContext::MD_invariant_load) ||
+                              AA.pointsToConstantMemory(I));
+}
+
 static bool instructionClobbersQuery(MemoryDef *MD, MemoryUse *MU,
                                      const MemoryLocOrCall &UseMLOC,
                                      AliasAnalysis &AA) {
   // FIXME: This is a temporary hack to allow a single instructionClobbersQuery
   // to exist while MemoryLocOrCall is pushed through places.
   if (UseMLOC.IsCall)
     return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(),
                                     AA);

llvm/trunk/test/Transforms/GVNHoist/pr30216.ll

+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+
+; Make sure the two stores @B do not get hoisted past the load @B.
+
+; CHECK-LABEL: define i8* @Foo
+; CHECK: store
+; CHECK: store
+; CHECK: load
+; CHECK: store
+
+@A = external global i8
+@B = external global i8*
+
+define i8* @Foo() {
+  store i8 0, i8* @A
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  store i8* null, i8** @B
+  ret i8* null
+
+if.else:
+  %1 = load i8*, i8** @B
+  store i8* null, i8** @B
+  ret i8* %1
+}
+
+; Make sure the two stores @B do not get hoisted past the store @GlobalVar.
+
+; CHECK-LABEL: define i8* @Fun
+; CHECK: store
+; CHECK: store
+; CHECK: store
+; CHECK: store
+; CHECK: load
+
+@GlobalVar = internal global i8 0
+
+define i8* @Fun() {
+  store i8 0, i8* @A
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  store i8* null, i8** @B
+  ret i8* null
+
+if.else:
+  store i8 0, i8* @GlobalVar
+  store i8* null, i8** @B
+  %1 = load i8*, i8** @B
+  ret i8* %1
+}

llvm/trunk/test/Transforms/GVNHoist/pr30499.ll

+; RUN: opt -S -gvn-hoist < %s
+
+define void @_Z3fn2v() #0 {
+entry:
+  %a = alloca i8*, align 8
+  %b = alloca i32, align 4
+  %0 = load i8*, i8** %a, align 8
+  store i8 0, i8* %0, align 1
+  %1 = load i32, i32* %b, align 4
+  %tobool = icmp ne i32 %1, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = call i64 @_Z3fn1v() #2
+  %conv = trunc i64 %call to i32
+  store i32 %conv, i32* %b, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  %2 = load i8*, i8** %a, align 8
+  store i8 0, i8* %2, align 1
+  ret void
+}
+
+; Function Attrs: nounwind readonly
+declare i64 @_Z3fn1v() #1
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind readonly }