[GVN] MemorySSA for GVN: use the incoming memory state in the value numbers

[asbirlea]

A very broad comment for a smooth transition

• the patches should be split into changes to GVN independent of the switch, e.g. a) factoring out components/methods where the differences between MSSA and MD occur and b) things that need to be added for the transition
• we should keep the MD implementation and have a flag for switching between the current one and the MSSA one being added
• once the flag flip sticks, then we'd remove the MD implementation

[chill]

In D115160#3259460, @asbirlea wrote:

A very broad comment for a smooth transition

• the patches should be split into changes to GVN independent of the switch, e.g. a) factoring out components/methods where the differences between MSSA and MD occur and b) things that need to be added for the transition
• we should keep the MD implementation and have a flag for switching between the current one and the MSSA one being added
• once the flag flip sticks, then we'd remove the MD implementation

Ack.

[chill]

llvm/lib/Transforms/Scalar/GVN.cpp

474

I looked at this part and it looks correct:

• if we have !AA->doesNotAccesMemory(C) we have to assign a new unique value number to account for the possibility that the call does volatile accesses or has some other form of non-determinism.
• otherwise, if the call does not access memory, then the current memory state can't affect the return value, so we won't include it in the value number
• otherwise, we hash the memory state too.

Nevertheless, it can be rearranged a little bit.

[asbirlea]

llvm/lib/Transforms/Scalar/GVN.cpp

2252

I'm not clear if BB always has a MemoryPhi. It's possible for a node to have PhiNodes, and no MemoryPhis.

if (!MPhi)
  return Num;

For getting the incoming value, there's an API:

MemoryAccess *MA = MPhi->getIncomingValueForBlock(Pred);

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

class ValueTable {
     uint32_t nextExprNumber = 0;
 
     std::vector<Expression> Expressions;
     std::vector<uint32_t> ExprIdx;
 
     // Value number to PHINode mapping. Used for phi-translate in scalarpre.
     DenseMap<uint32_t, PHINode *> NumberingPhi;
 
+    // Value number to BasicBlock mapping. Used for phi-translate across
+    // MemoryPhis.
+    DenseMap<uint32_t, BasicBlock *> NumberingBB;
+
     // Cache for phi-translate in scalarpre.
     using PhiTranslateMap =
         DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;
     PhiTranslateMap PhiTranslateTable;
 
     AAResults *AA = nullptr;
     MemoryDependenceResults *MD = nullptr;
+    MemorySSA *MSSA = nullptr;
     DominatorTree *DT = nullptr;
 
     uint32_t nextValueNumber = 1;
 
     Expression createExpr(Instruction *I);
     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
                              Value *LHS, Value *RHS);
     Expression createExtractvalueExpr(ExtractValueInst *EI);
+    Expression createCallExpr(CallInst *C);
+    void addMemoryStateArg(Instruction *I, Expression &E);
     uint32_t lookupOrAddCall(CallInst *C);
+    uint32_t lookupOrAddLoadStore(Instruction *I);
     uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
                               uint32_t Num, GVNPass &Gvn);
     bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
                           const BasicBlock *PhiBlock, GVNPass &Gvn);
     std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
     bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVNPass &Gvn);
 
   public:
public:
     void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
     bool exists(Value *V) const;
     void add(Value *V, uint32_t num);
     void clear();
     void erase(Value *v);
     void setAliasAnalysis(AAResults *A) { AA = A; }
     AAResults *getAliasAnalysis() const { return AA; }
     void setMemDep(MemoryDependenceResults *M) { MD = M; }
+    void setMemorySSA(MemorySSA *M) { MSSA = M; }
     void setDomTree(DominatorTree *D) { DT = D; }
     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
     void verifyRemoved(const Value *) const;
   };
 
 private:
   friend class gvn::GVNLegacyPass;
   friend struct DenseMapInfo<Expression>;

llvm/lib/Transforms/Scalar/GVN.cpp

GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) {
   // For GEPs, disambiguate based on the source element type, which is not
   // implied by the result type with opaque pointers. (Conversely, the source
   // element type together with the operand types does imply the result type.)
   if (const auto *GEP = dyn_cast<GetElementPtrInst>(I))
     e.type = GEP->getSourceElementType();
   else
     e.type = I->getType();
   e.opcode = I->getOpcode();
-  if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(I)) {
-    // gc.relocate is 'special' call: its second and third operands are
-    // not real values, but indices into statepoint's argument list.
-    // Use the refered to values for purposes of identity.
-    e.varargs.push_back(lookupOrAdd(GCR->getOperand(0)));
-    e.varargs.push_back(lookupOrAdd(GCR->getBasePtr()));
-    e.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
-  } else {
-    for (Use &Op : I->operands())
-      e.varargs.push_back(lookupOrAdd(Op));
-  }
+
   if (I->isCommutative()) {
     // Ensure that commutative instructions that only differ by a permutation
     // of their operands get the same value number by sorting the operand value
     // numbers.  Since commutative operands are the 1st two operands it is more
     // efficient to sort by hand rather than using, say, std::sort.
     assert(I->getNumOperands() >= 2 && "Unsupported commutative instruction!");
     if (e.varargs[0] > e.varargs[1])
       std::swap(e.varargs[0], e.varargs[1]);
GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) {
   } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
     ArrayRef<int> ShuffleMask = SVI->getShuffleMask();
     e.varargs.append(ShuffleMask.begin(), ShuffleMask.end());
   }
 
   return e;
 }
 
+GVNPass::Expression GVNPass::ValueTable::createCallExpr(CallInst *C) {
+  Expression E;
+  E.type = C->getType();
+  E.opcode = C->getOpcode();
+  if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(C)) {
+    // gc.relocate is 'special' call: its second and third operands are
+    // not real values, but indices into statepoint's argument list.
+    // Use the refered to values for purposes of identity.
+    E.varargs.push_back(lookupOrAdd(GCR->getOperand(0)));
+    E.varargs.push_back(lookupOrAdd(GCR->getBasePtr()));
+    E.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
+    return E;
+  }
+
+  for (Use &Op : C->operands())
+    E.varargs.push_back(lookupOrAdd(Op));
+
+  if (C->isCommutative()) {
+    // There are commutative instrinsic calls.
+    assert(C->getNumOperands() >= 2 && "Unsupported commutative instruction!");
+    if (E.varargs[0] > E.varargs[1])
+      std::swap(E.varargs[0], E.varargs[1]);
+    E.commutative = true;
+  }
+
+  return E;
+}
+
 GVNPass::Expression GVNPass::ValueTable::createCmpExpr(
     unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) {
   assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
          "Not a comparison!");
   Expression e;
   e.type = CmpInst::makeCmpResultType(LHS->getType());
   e.varargs.push_back(lookupOrAdd(LHS));
   e.varargs.push_back(lookupOrAdd(RHS));

 
 /// add - Insert a value into the table with a specified value number.
 void GVNPass::ValueTable::add(Value *V, uint32_t num) {
   valueNumbering.insert(std::make_pair(V, num));
   if (PHINode *PN = dyn_cast<PHINode>(V))
     NumberingPhi[num] = PN;
 }
 
+// Include the incoming memory state into the hash for the instruction. If the
+// incoming memory state is:
+// * LiveOnEntry, add the value number of the entry block
+// * a MemoryPhi, add the value number of the basic block,
+//   corresponding to that MemoryPhi
+// * a MemoryDef, add the value number of the memory setting
+//   instruction.
+void GVNPass::ValueTable::addMemoryStateArg(Instruction *I, Expression &E) {
+  assert(MSSA && "Function should not be called without MemorySSA");
+  assert(MSSA->getMemoryAccess(I) && "Instruction does not access memory");
+  MemoryAccess *MA = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(I);
+
+  uint32_t N = 0;
+  if (isa<MemoryPhi>(MA))
+    N = lookupOrAdd(MA->getBlock());
+  else if (MSSA->isLiveOnEntryDef(MA))
+    N = lookupOrAdd(&I->getFunction()->getEntryBlock());
+  else
+    N = lookupOrAdd(cast<MemoryDef>(MA)->getMemoryInst());
+  E.varargs.push_back(N);
+}
+
 uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) {
   if (AA->doesNotAccessMemory(C)) {
-    Expression exp = createExpr(C);
+    Expression exp = createCallExpr(C);
     uint32_t e = assignExpNewValueNum(exp).first;
     valueNumbering[C] = e;
     return e;
-  } else if (MD && AA->onlyReadsMemory(C)) {
-    Expression exp = createExpr(C);
+  }
+
+  if (MSSA) {
+    if (AA->onlyReadsMemory(C)) {
+      Expression E = createCallExpr(C);
+      addMemoryStateArg(C, E);
+      uint32_t VN = assignExpNewValueNum(E).first;
+      valueNumbering[C] = VN;
+      return VN;
+    }
+    valueNumbering[C] = nextValueNumber;
+    return nextValueNumber++;
+  }
+
+  if (MD && AA->onlyReadsMemory(C)) {
+    Expression exp = createCallExpr(C);
     auto ValNum = assignExpNewValueNum(exp);
     if (ValNum.second) {
       valueNumbering[C] = ValNum.first;
       return ValNum.first;
     }
 
     MemDepResult local_dep = MD->getDependency(C);
 
if (MD && AA->onlyReadsMemory(C)) {
     valueNumbering[C] = v;
     return v;
   } else {
     valueNumbering[C] = nextValueNumber;
     return nextValueNumber++;
   }
 }
 
+uint32_t GVNPass::ValueTable::lookupOrAddLoadStore(Instruction *I) {
+  if (MSSA == nullptr) {
+    valueNumbering[I] = nextValueNumber;
+    return nextValueNumber++;
+  }
+
+  Expression E;
+  E.type = I->getType();
+  E.opcode = I->getOpcode();
+  for (Use &Op : I->operands())
+    E.varargs.push_back(lookupOrAdd(Op));
+  addMemoryStateArg(I, E);
+
+  uint32_t N = assignExpNewValueNum(E).first;
+  valueNumbering[I] = N;
+  return N;
+}
+
 /// Returns true if a value number exists for the specified value.
 bool GVNPass::ValueTable::exists(Value *V) const {
   return valueNumbering.count(V) != 0;
 }
 
 /// lookup_or_add - Returns the value number for the specified value, assigning
 /// it a new number if it did not have one before.
 uint32_t GVNPass::ValueTable::lookupOrAdd(Value *V) {
   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
   if (VI != valueNumbering.end())
     return VI->second;
 
   if (!isa<Instruction>(V)) {
     valueNumbering[V] = nextValueNumber;
+    if (MSSA) {
+      if (auto *BB = dyn_cast<BasicBlock>(V))
+        NumberingBB[nextValueNumber] = BB;
+    }
     return nextValueNumber++;
   }
 
   Instruction* I = cast<Instruction>(V);
   Expression exp;
   switch (I->getOpcode()) {
     case Instruction::Call:
       return lookupOrAddCall(cast<CallInst>(I));
case Instruction::GetElementPtr:
       break;
     case Instruction::ExtractValue:
       exp = createExtractvalueExpr(cast<ExtractValueInst>(I));
       break;
     case Instruction::PHI:
       valueNumbering[V] = nextValueNumber;
       NumberingPhi[nextValueNumber] = cast<PHINode>(V);
       return nextValueNumber++;
+    case Instruction::Load:
+    case Instruction::Store:
+      return lookupOrAddLoadStore(I);
     default:
       valueNumbering[V] = nextValueNumber;
       return nextValueNumber++;
   }
 
   uint32_t e = assignExpNewValueNum(exp).first;
   valueNumbering[V] = e;
   return e;
uint32_t GVNPass::ValueTable::lookupOrAddCmp(unsigned Opcode,
   return assignExpNewValueNum(exp).first;
 }
 
 /// Remove all entries from the ValueTable.
 void GVNPass::ValueTable::clear() {
   valueNumbering.clear();
   expressionNumbering.clear();
   NumberingPhi.clear();
+  NumberingBB.clear();
   PhiTranslateTable.clear();
   nextValueNumber = 1;
   Expressions.clear();
   ExprIdx.clear();
   nextExprNumber = 0;
 }
 
 /// Remove a value from the value numbering.
 void GVNPass::ValueTable::erase(Value *V) {
   uint32_t Num = valueNumbering.lookup(V);
   valueNumbering.erase(V);
   // If V is PHINode, V <--> value number is an one-to-one mapping.
   if (isa<PHINode>(V))
     NumberingPhi.erase(Num);
+  else if (isa<BasicBlock>(V))
+    NumberingBB.erase(Num);
 }
 
 /// verifyRemoved - Verify that the value is removed from all internal data
 /// structures.
 void GVNPass::ValueTable::verifyRemoved(const Value *V) const {
   for (DenseMap<Value*, uint32_t>::const_iterator
          I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
     assert(I->first != V && "Inst still occurs in value numbering map!");

 }
 
 /// Translate value number \p Num using phis, so that it has the values of
 /// the phis in BB.
 uint32_t GVNPass::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
                                                const BasicBlock *PhiBlock,
                                                uint32_t Num, GVNPass &Gvn) {
   if (PHINode *PN = NumberingPhi[Num]) {
+    if (PN->getParent() != PhiBlock)
+      return Num;
     for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
-      if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred)
+      if (PN->getIncomingBlock(i) == Pred)
         if (uint32_t TransVal = lookup(PN->getIncomingValue(i), false))
           return TransVal;
     }
     return Num;
   }
 
+  if (BasicBlock *BB = NumberingBB[Num]) {
+    assert(MSSA && "NumberingBB is non-empty only when using MemorySSA");
+    // Value numbers of basic blocks are used to represent memory state in
+    // load/store instructions and read-only function calls when said state is
+    // set by a MemoryPhi.
+    if (BB != PhiBlock)
+      return Num;
+    MemoryPhi *MPhi = MSSA->getMemoryAccess(BB);
+    for (unsigned I = 0, N = MPhi->getNumIncomingValues(); I != N; ++I) {
+      if (MPhi->getIncomingBlock(I) != Pred)
+        continue;
+      MemoryAccess *MA = MPhi->getIncomingValue(I);
+      if (auto *PredPhi = dyn_cast<MemoryPhi>(MA))
+        return lookupOrAdd(PredPhi->getBlock());
+      if (MSSA->isLiveOnEntryDef(MA))
+        return lookupOrAdd(&BB->getParent()->getEntryBlock());
+      return lookupOrAdd(cast<MemoryUseOrDef>(MA)->getMemoryInst());
+    }
+    llvm_unreachable(
+        "CFG/MemorySSA mismatch: predecessor not found among incoming blocks");
+  }
+
   // If there is any value related with Num is defined in a BB other than
   // PhiBlock, it cannot depend on a phi in PhiBlock without going through
   // a backedge. We can do an early exit in that case to save compile time.
   if (!areAllValsInBB(Num, PhiBlock, Gvn))
     return Num;
 
   if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
     return Num;
if (Exp.varargs[0] > Exp.varargs[1]) {
       if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
         Exp.opcode = (Opcode << 8) |
                      CmpInst::getSwappedPredicate(
                          static_cast<CmpInst::Predicate>(Exp.opcode & 255));
     }
   }
 
   if (uint32_t NewNum = expressionNumbering[Exp]) {
-    if (Exp.opcode == Instruction::Call && NewNum != Num)
+    if (MSSA == nullptr && Exp.opcode == Instruction::Call && NewNum != Num)
       return areCallValsEqual(Num, NewNum, Pred, PhiBlock, Gvn) ? NewNum : Num;
     return NewNum;
   }
   return Num;
 }
 
 /// Erase stale entry from phiTranslate cache so phiTranslate can be computed
 /// again.
bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
   VN.setDomTree(DT);
   TLI = &RunTLI;
   VN.setAliasAnalysis(&RunAA);
   MD = RunMD;
   ImplicitControlFlowTracking ImplicitCFT;
   ICF = &ImplicitCFT;
   this->LI = LI;
   VN.setMemDep(MD);
+  VN.setMemorySSA(MSSA);
   ORE = RunORE;
   InvalidBlockRPONumbers = true;
   MemorySSAUpdater Updater(MSSA);
   MSSAU = MSSA ? &Updater : nullptr;
 
   bool Changed = false;
   bool ShouldContinue = true;
 

llvm/test/Analysis/ValueTracking/gep-negative-issue.ll

 ; RUN: opt -gvn -S < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-p100:128:64:64-p101:128:64:64"
 target triple = "x86_64-unknown-linux-gnu"
 
 %ArrayImpl = type { i64, i64 addrspace(100)*, [1 x i64], [1 x i64], [1 x i64], i64, i64, double addrspace(100)*, double addrspace(100)*, i8, i64 }
 %_array = type { i64, %ArrayImpl addrspace(100)*, i8 }
 
-define void @test(i64 %n_chpl) {
+define void @test(%_array* %p) {
 entry:
   ; First section is some code
-  %0 = getelementptr inbounds %_array, %_array* null, i32 0, i32 1
+  %0 = getelementptr inbounds %_array, %_array* %p, i32 0, i32 1
   %1 = load %ArrayImpl addrspace(100)*, %ArrayImpl addrspace(100)** %0
   %2 = getelementptr inbounds %ArrayImpl, %ArrayImpl addrspace(100)* %1, i32 0, i32 8
   %3 = load double addrspace(100)*, double addrspace(100)* addrspace(100)* %2
   %4 = getelementptr inbounds double, double addrspace(100)* %3, i64 -1
   ; Second section is that code repeated
-  %x0 = getelementptr inbounds %_array, %_array* null, i32 0, i32 1
+  %x0 = getelementptr inbounds %_array, %_array* %p, i32 0, i32 1
   %x1 = load %ArrayImpl addrspace(100)*, %ArrayImpl addrspace(100)** %x0
   %x2 = getelementptr inbounds %ArrayImpl, %ArrayImpl addrspace(100)* %x1, i32 0, i32 8
   %x3 = load double addrspace(100)*, double addrspace(100)* addrspace(100)* %x2
   %x4 = getelementptr inbounds double, double addrspace(100)* %x3, i64 -1
   ; These two stores refer to the same memory location
   ; Even so, they are expected to remain separate stores here
   store double 0.000000e+00, double addrspace(100)* %4
   store double 0.000000e+00, double addrspace(100)* %x4