Index: llvm/include/llvm/Transforms/Scalar/GVN.h =================================================================== --- llvm/include/llvm/Transforms/Scalar/GVN.h +++ llvm/include/llvm/Transforms/Scalar/GVN.h @@ -111,8 +111,40 @@ /// The core GVN pass object. /// -/// FIXME: We should have a good summary of the GVN algorithm implemented by -/// this particular pass here. +/// Each GVN pass is raised by public method \c GVN::run which runs +/// GVN on a function and returns a \c PreservedAnalyses object. +/// This method takes analysis result from argument \c AM with type +/// \c FunctionAnalysisManager. The method then calls \c runImpl to +/// start working on the function. +/// +/// 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 order 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 was 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. class GVN : public PassInfoMixin { GVNOptions Options; @@ -157,10 +189,10 @@ std::vector Expressions; std::vector 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 NumberingPhi; - // Cache for phi-translate in scalarpre. + // Cache for phi-translate in scalar PRE. using PhiTranslateMap = DenseMap, uint32_t>; PhiTranslateMap PhiTranslateTable; @@ -199,6 +231,7 @@ 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; } Index: llvm/lib/Transforms/Scalar/GVN.cpp =================================================================== --- llvm/lib/Transforms/Scalar/GVN.cpp +++ llvm/lib/Transforms/Scalar/GVN.cpp @@ -395,6 +395,15 @@ 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(V)) + NumberingPhi[nextValueNumber] = PN; + return nextValueNumber++; +} + uint32_t GVN::ValueTable::lookupOrAddCall(CallInst *C) { if (AA->doesNotAccessMemory(C)) { Expression exp = createExpr(C); @@ -411,29 +420,23 @@ 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(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); @@ -472,31 +475,24 @@ 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. @@ -509,10 +505,8 @@ if (VI != valueNumbering.end()) return VI->second; - if (!isa(V)) { - valueNumbering[V] = nextValueNumber; - return nextValueNumber++; - } + if (!isa(V)) + return assignNewValueNum(V); Instruction* I = cast(V); Expression exp; @@ -565,13 +559,8 @@ case Instruction::ExtractValue: exp = createExtractvalueExpr(cast(I)); break; - case Instruction::PHI: - valueNumbering[V] = nextValueNumber; - NumberingPhi[nextValueNumber] = cast(V); - return nextValueNumber++; default: - valueNumbering[V] = nextValueNumber; - return nextValueNumber++; + return assignNewValueNum(V); } uint32_t e = assignExpNewValueNum(exp).first; @@ -900,10 +889,10 @@ } 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' @@ -2162,7 +2151,7 @@ /// 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(I)) return false; Index: llvm/lib/Transforms/Utils/VNCoercion.cpp =================================================================== --- llvm/lib/Transforms/Utils/VNCoercion.cpp +++ llvm/lib/Transforms/Utils/VNCoercion.cpp @@ -204,18 +204,6 @@ 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;