[GVN][NFC] Refactor code and add description for GVN object

[ksyx]

Summary

In this revision:

• Added descriptions for the GVN object.
  • The original comment says a "good summary of algorithm implemented by this GVN object" is required, but I am not sure how deep to get into this description. Thus, the description I added focused on the work done and relationships among methods.
• Moved the code assigning new value number into a new method to improve code tidiness.
• Since a if statement before a line deleted guaranteed that StoreOffset + StoreSize >= LoadOffset + LoadSize, it is guaranteed that StoreOffset + StoreSize > LoadOffset so the being removed in this revision might be redundant.
• Fix typos and spaces.

[ksyx]

fix: unable to apply patch

[ksyx]

fix: clang-format failed

[lattner]

The patch looks reasonable to me, but I'm no longer a competent reviewer for this area.

[nikic]

Just FYI, recently work on NewGVN has started again, so that's where the focus will (hopefully) be in the future.

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

112

I think this comment would do better in the cpp file, closer to the implementation.

116

I don't think this is needed, this is just general pass setup.

122

reversed order -> reverse post-order (or just RPO)

131

was -> is

llvm/lib/Transforms/Utils/VNCoercion.cpp

217

Looks right to me, feel free to just commit this separately.

[ksyx]

In D100179#2681672, @nikic wrote:

Just FYI, recently work on NewGVN has started again, so that's where the focus will (hopefully) be in the future.

That’s fine. By the way, will it be changed into something like LegacyGVN or just remove the whole?

[ksyx]

apply suggestions from code review.

[ksyx]

ping :)

[ksyx]

Ping :)
Please tell me if there is anything that could be improved, thanks!

[mstorsjo]

The bit that was split off and committed as rGc35e8185d8c170c20e28956e0c9f3c1be895fefb was not an NFC, it broke compilation of one file for me: https://martin.st/temp/vlc-preproc.c

$ clang -target armv7-w64-mingw32 -w -c -O2 vlc-preproc.c 
clang: ../lib/Transforms/Utils/VNCoercion.cpp:475: llvm::Value* llvm::VNCoercion::getLoadValueForLoad(llvm::LoadInst*, unsigned int, llvm::Type*, llvm::Instruction*, const llvm::DataLayout&): Assertion `SrcVal-isSimple() && "Cannot widen volatile/atomic load!"' failed.

I'd suggest reverting that patch until this issue is sorted out.

[ksyx]

In D100179#3130694, @mstorsjo wrote:

The bit that was split off and committed as rGc35e8185d8c170c20e28956e0c9f3c1be895fefb was not an NFC, it broke compilation of one file for me: https://martin.st/temp/vlc-preproc.c

$ clang -target armv7-w64-mingw32 -w -c -O2 vlc-preproc.c 
clang: ../lib/Transforms/Utils/VNCoercion.cpp:475: llvm::Value* llvm::VNCoercion::getLoadValueForLoad(llvm::LoadInst*, unsigned int, llvm::Type*, llvm::Instruction*, const llvm::DataLayout&): Assertion `SrcVal-isSimple() && "Cannot widen volatile/atomic load!"' failed.

I'd suggest reverting that patch until this issue is sorted out.

Thanks for your feedback! I am going to figure out that when I had time and I will revert it soon.

[ksyx]

@mstorsjo

Reproduced. The commit is reverted now. Please check if the compilation goes back to normal. Sorry for inconvenience.

Reversion: 72b5138d37d7ec799301e29e9c1eaaa1630be161

[mstorsjo]

In D100179#3131335, @ksyx wrote:

@mstorsjo

Reproduced. The commit is reverted now. Please check if the compilation goes back to normal. Sorry for inconvenience.

Reversion: 72b5138d37d7ec799301e29e9c1eaaa1630be161

Thanks, now it does seem to build correctly again.

[ksyx]

@mstorsjo

I have made fix to my patch and your problem seemly to be solved in my local test. Please check again and thanks for feedback again.

[build]$ bin/clang -target armv7-w64-mingw32 -w -c -O2 vlc-preproc.c
[build]$ echo $?
0

I think I may add some checks sometime.

[mstorsjo]

In D100179#3144293, @ksyx wrote:

@mstorsjo

I have made fix to my patch and your problem seemly to be solved in my local test. Please check again and thanks for feedback again.

[build]$ bin/clang -target armv7-w64-mingw32 -w -c -O2 vlc-preproc.c
[build]$ echo $?
0

I think I may add some checks sometime.

Thanks, the original case seems to still build fine now.

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

struct GVNOptions {
 
   /// Enables or disables use of MemDepAnalysis.
   GVNOptions &setMemDep(bool MemDep) {
     AllowMemDep = MemDep;
     return *this;
   }
 };
 
 /// The core GVN pass object.
-///
-/// FIXME: We should have a good summary of the GVN algorithm implemented by
-/// this particular pass here.
 class GVN : public PassInfoMixin<GVN> {
   GVNOptions Options;
 
 public:
   struct Expression;
 
   GVN(GVNOptions Options = {}) : Options(Options) {}
 
   /// Run the pass over the function.
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   /// This removes the specified instruction from
   /// our various maps and marks it for deletion.
   void markInstructionForDeletion(Instruction *I) {
     VN.erase(I);
     InstrsToErase.push_back(I);
   }
 
   DominatorTree &getDominatorTree() const { return *DT; }
   AAResults *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
   MemoryDependenceResults &getMemDep() const { return *MD; }
 
   bool isPREEnabled() const;
   bool isLoadPREEnabled() const;
   bool isLoadInLoopPREEnabled() const;
   bool isLoadPRESplitBackedgeEnabled() const;
   bool isMemDepEnabled() const;
class ValueTable {
     // value number to the index of Expression in Expressions. We use it
     // instead of a DenseMap because filling such mapping is faster than
     // filling a DenseMap and the compile time is a little better.
     uint32_t nextExprNumber = 0;
 
     std::vector<Expression> Expressions;
     std::vector<uint32_t> ExprIdx;
 
-    // Value number to PHINode mapping. Used for phi-translate in scalarpre.
+    // Value number to PHINode mapping. Used for phi-translate in scalar PRE.
     DenseMap<uint32_t, PHINode *> NumberingPhi;
 
-    // Cache for phi-translate in scalarpre.
+    // Cache for phi-translate in scalar PRE.
     using PhiTranslateMap =
         DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;
     PhiTranslateMap PhiTranslateTable;
 
     AAResults *AA = nullptr;
     MemoryDependenceResults *MD = nullptr;
     DominatorTree *DT = nullptr;
 
public:
     uint32_t lookup(Value *V, bool Verify = true) const;
     uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred,
                             Value *LHS, Value *RHS);
     uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock,
                           uint32_t Num, GVN &Gvn);
     void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
     bool exists(Value *V) const;
     void add(Value *V, uint32_t num);
+    uint32_t assignNewValueNum(Value *V);
     void clear();
     void erase(Value *v);
     void setAliasAnalysis(AAResults *A) { AA = A; }
     AAResults *getAliasAnalysis() const { return AA; }
     void setMemDep(MemoryDependenceResults *M) { MD = M; }
     void setDomTree(DominatorTree *D) { DT = D; }
     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
     void verifyRemoved(const Value *) const;

llvm/lib/Transforms/Scalar/GVN.cpp

 
 /// add - Insert a value into the table with a specified value number.
 void GVN::ValueTable::add(Value *V, uint32_t num) {
   valueNumbering.insert(std::make_pair(V, num));
   if (PHINode *PN = dyn_cast<PHINode>(V))
     NumberingPhi[num] = PN;
 }
 
+/// assignNewValueNum - Insert a value into the table with nextValueNumber
+/// and returns the ValueNumber assigned.
+uint32_t GVN::ValueTable::assignNewValueNum(Value *V) {
+  valueNumbering[V] = nextValueNumber;
+  if (PHINode *PN = dyn_cast<PHINode>(V))
+    NumberingPhi[nextValueNumber] = PN;
+  return nextValueNumber++;
+}
+
 uint32_t GVN::ValueTable::lookupOrAddCall(CallInst *C) {
   if (AA->doesNotAccessMemory(C)) {
     Expression exp = createExpr(C);
     uint32_t e = assignExpNewValueNum(exp).first;
     valueNumbering[C] = e;
     return e;
   } else if (MD && AA->onlyReadsMemory(C)) {
     Expression exp = createExpr(C);
     auto ValNum = assignExpNewValueNum(exp);
     if (ValNum.second) {
       valueNumbering[C] = ValNum.first;
       return ValNum.first;
     }
 
     MemDepResult local_dep = MD->getDependency(C);
 
-    if (!local_dep.isDef() && !local_dep.isNonLocal()) {
-      valueNumbering[C] =  nextValueNumber;
-      return nextValueNumber++;
-    }
+    if (!local_dep.isDef() && !local_dep.isNonLocal())
+      return assignNewValueNum(C);
 
     if (local_dep.isDef()) {
-      // For masked load/store intrinsics, the local_dep may actully be
+      // For masked load/store intrinsics, the local_dep may actually be
       // a normal load or store instruction.
       CallInst *local_cdep = dyn_cast<CallInst>(local_dep.getInst());
 
       if (!local_cdep ||
-          local_cdep->getNumArgOperands() != C->getNumArgOperands()) {
-        valueNumbering[C] = nextValueNumber;
-        return nextValueNumber++;
-      }
+          local_cdep->getNumArgOperands() != C->getNumArgOperands())
+        return assignNewValueNum(C);
 
       for (unsigned i = 0, e = C->getNumArgOperands(); i < e; ++i) {
         uint32_t c_vn = lookupOrAdd(C->getArgOperand(i));
         uint32_t cd_vn = lookupOrAdd(local_cdep->getArgOperand(i));
-        if (c_vn != cd_vn) {
-          valueNumbering[C] = nextValueNumber;
-          return nextValueNumber++;
-        }
+        if (c_vn != cd_vn)
+          return assignNewValueNum(C);
       }
 
       uint32_t v = lookupOrAdd(local_cdep);
       valueNumbering[C] = v;
       return v;
     }
 
     // Non-local case.
for (unsigned i = 0, e = deps.size(); i != e; ++i) {
         cdep = NonLocalDepCall;
         continue;
       }
 
       cdep = nullptr;
       break;
     }
 
-    if (!cdep) {
-      valueNumbering[C] = nextValueNumber;
-      return nextValueNumber++;
-    }
+    if (!cdep)
+      return assignNewValueNum(C);
+
+    if (cdep->getNumArgOperands() != C->getNumArgOperands())
+      return assignNewValueNum(C);
 
-    if (cdep->getNumArgOperands() != C->getNumArgOperands()) {
-      valueNumbering[C] = nextValueNumber;
-      return nextValueNumber++;
-    }
     for (unsigned i = 0, e = C->getNumArgOperands(); i < e; ++i) {
       uint32_t c_vn = lookupOrAdd(C->getArgOperand(i));
       uint32_t cd_vn = lookupOrAdd(cdep->getArgOperand(i));
-      if (c_vn != cd_vn) {
-        valueNumbering[C] = nextValueNumber;
-        return nextValueNumber++;
-      }
+      if (c_vn != cd_vn)
+        return assignNewValueNum(C);
     }
 
     uint32_t v = lookupOrAdd(cdep);
     valueNumbering[C] = v;
     return v;
-  } else {
-    valueNumbering[C] = nextValueNumber;
-    return nextValueNumber++;
-  }
+  } else
+    return assignNewValueNum(C);
 }
 
 /// Returns true if a value number exists for the specified value.
 bool GVN::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 GVN::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;
-    return nextValueNumber++;
-  }
+  if (!isa<Instruction>(V))
+    return assignNewValueNum(V);
 
   Instruction* I = cast<Instruction>(V);
   Expression exp;
   switch (I->getOpcode()) {
     case Instruction::Call:
       return lookupOrAddCall(cast<CallInst>(I));
     case Instruction::FNeg:
     case Instruction::Add:
switch (I->getOpcode()) {
     case Instruction::ShuffleVector:
     case Instruction::InsertValue:
     case Instruction::GetElementPtr:
       exp = createExpr(I);
       break;
     case Instruction::ExtractValue:
       exp = createExtractvalueExpr(cast<ExtractValueInst>(I));
       break;
-    case Instruction::PHI:
-      valueNumbering[V] = nextValueNumber;
-      NumberingPhi[nextValueNumber] = cast<PHINode>(V);
-      return nextValueNumber++;
     default:
-      valueNumbering[V] = nextValueNumber;
-      return nextValueNumber++;
+      return assignNewValueNum(V);
   }
 
   uint32_t e = assignExpNewValueNum(exp).first;
   valueNumbering[V] = e;
   return e;
 }
 
 /// Returns the value number of the specified value. Fails if
bool GVN::isLoadPRESplitBackedgeEnabled() const {
   return Options.AllowLoadPRESplitBackedge.getValueOr(
       GVNEnableSplitBackedgeInLoadPRE);
 }
 
 bool GVN::isMemDepEnabled() const {
   return Options.AllowMemDep.getValueOr(GVNEnableMemDep);
 }
 
+/// This method is called by a pass manager to start a GVN pass on a
+/// function which will call method \c runImpl to start optimizing.
+///
+/// The method \c runImpl first merges basic blocks to enable more
+/// optimizing opportunity and then runs optimization iterations
+/// by calling method \c IterateOnFunction until no more optimization
+/// possible. Within this method, the basic blocks are visited in
+/// a reversed post order (RPO) by calling method \c processBlock, which
+/// will elinimate duplicate PHI nodes, replace equality using information
+/// from \c assume intrinsics and call \c processInstruction method.
+///
+/// Within \c processInstruction method, it tries to a) simplify
+/// instruction, b) record information from the uses of assume
+/// instruction, c) optimize load instructions as described below,
+/// d) propagate equality information for branch and switch instructions,
+/// and e) do general value numbering and replacing. The process of load
+/// instruction is supported by method \c AnalyzeLoadAvailability which
+/// analyzes whether a load could be eliminated by using its depedency
+/// information, generating an available value if that is possible. That
+/// value is then being materialized into \c Value* by the method
+/// \c MaterializeAdjustedValue when utilizing this available value.
+///
+/// While processing non-local loads, \c ConstructSSAForLoadSet
+/// will construct SSA form with available values gotten from analysis
+/// and return the value should be used in the place of that load. The SSA
+/// functionality was provided by the SSAUpdater in \c Utils/SSAUpdater .
+///
+/// Besides the optimization work described above, partial redundancy
+/// elimination (PRE) is also performed if enabled. The values involved
+/// in the optimization process above are managed using the class ValueTable
+/// nestly defined in the definition of this GVN object.
 PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
   // FIXME: The order of evaluation of these 'getResult' calls is very
   // significant! Re-ordering these variables will cause GVN when run alone to
   // be less effective! We should fix memdep and basic-aa to not exhibit this
   // 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);
if (isSimpleValue()) {
     }
   } else if (isCoercedLoadValue()) {
     LoadInst *Load = getCoercedLoadValue();
     if (Load->getType() == LoadTy && Offset == 0) {
       Res = Load;
     } else {
       Res = getLoadValueForLoad(Load, Offset, LoadTy, InsertPt, DL);
       // We would like to use gvn.markInstructionForDeletion here, but we can't
-      // because the load is already memoized into the leader map table that GVN
-      // tracks.  It is potentially possible to remove the load from the table,
-      // but then there all of the operations based on it would need to be
-      // rehashed.  Just leave the dead load around.
+      // because the load is already memorized into the leader map table that
+      // GVN tracks.  It is potentially possible to remove the load from the
+      // table, but then there all of the operations based on it would need to
+      // be rehashed.  Just leave the dead load around.
       gvn.getMemDep().removeInstruction(Load);
       LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset
                         << "  " << *getCoercedLoadValue() << '\n'
                         << *Res << '\n'
                         << "\n\n\n");
     }
   } else if (isMemIntrinValue()) {
     Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,
bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
   }
 
   return Changed;
 }
 
 /// When calculating availability, handle an instruction
 /// by inserting it into the appropriate sets
 bool GVN::processInstruction(Instruction *I) {
-  // Ignore dbg info intrinsics.
+  // Ignore debug info intrinsics.
   if (isa<DbgInfoIntrinsic>(I))
     return false;
 
   // If the instruction can be easily simplified then do so now in preference
   // to value numbering it.  Value numbering often exposes redundancies, for
   // example if it determines that %y is equal to %x then the instruction
   // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
   const DataLayout &DL = I->getModule()->getDataLayout();

llvm/lib/Transforms/Utils/VNCoercion.cpp

static int analyzeLoadFromClobberingWrite(Type *LoadTy, Value *LoadPtr,
   // If the Load isn't completely contained within the stored bits, we don't
   // have all the bits to feed it.  We could do something crazy in the future
   // (issue a smaller load then merge the bits in) but this seems unlikely to be
   // valuable.
   if (StoreOffset > LoadOffset ||
       StoreOffset + StoreSize < LoadOffset + LoadSize)
     return -1;
 
-  // If the load and store are to the exact same address, they should have been
-  // a must alias.  AA must have gotten confused.
-  // FIXME: Study to see if/when this happens.  One case is forwarding a memset
-  // to a load from the base of the memset.
-
-  // If the load and store don't overlap at all, the store doesn't provide
-  // anything to the load.  In this case, they really don't alias at all, AA
-  // must have gotten confused.  The if statement above ensure the condition
-  // that StoreOffset <= LoadOffset.
-  if (StoreOffset + int64_t(StoreSize) <= LoadOffset)
-    return -1;
-
   // Okay, we can do this transformation.  Return the number of bytes into the
   // store that the load is.
   return LoadOffset - StoreOffset;
 }
 
 /// This function is called when we have a
 /// memdep query of a load that ends up being a clobbering store.
 int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr,