Index: llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp +++ llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp @@ -58,10 +58,10 @@ // Provides a sorting function based on the execution order of two instructions. struct SortByDFSIn { private: - DenseMap &DFSNumber; + DenseMap &DFSNumber; public: - SortByDFSIn(DenseMap &D) : DFSNumber(D) {} + SortByDFSIn(DenseMap &D) : DFSNumber(D) {} // Returns true when A executes before B. bool operator()(const Instruction *A, const Instruction *B) const { @@ -72,18 +72,10 @@ // // assert(A != B); - const BasicBlock *BA = A->getParent(); - const BasicBlock *BB = B->getParent(); - unsigned NA = DFSNumber[BA]; - unsigned NB = DFSNumber[BB]; - if (NA < NB) - return true; - if (NA == NB) { - // Sort them in the order they occur in the same basic block. - BasicBlock::const_iterator AI(A), BI(B); - return std::distance(AI, BI) < 0; - } - return false; + unsigned ADFS = DFSNumber.lookup(A); + unsigned BDFS = DFSNumber.lookup(B); + assert (ADFS && ADFS); + return ADFS < BDFS; } }; @@ -201,10 +193,6 @@ VN.setMemDep(MD); bool Res = false; - unsigned I = 0; - for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) - DFSNumber.insert({BB, ++I}); - // FIXME: use lazy evaluation of VN to avoid the fix-point computation. while (1) { // FIXME: only compute MemorySSA once. We need to update the analysis in @@ -212,6 +200,12 @@ MemorySSA M(F, AA, DT); MSSA = &M; + // Perform DFS Numbering of instructions. + unsigned I = 0; + for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) + for (auto &Inst: *BB) + DFSNumber.insert({&Inst, ++I}); + auto HoistStat = hoistExpressions(F); if (HoistStat.first + HoistStat.second == 0) { return Res; @@ -223,6 +217,9 @@ VN.clear(); } Res = true; + + // DFS numbers change when instructions are hoisted: clear and recompute. + DFSNumber.clear(); } return Res; @@ -233,7 +230,7 @@ AliasAnalysis *AA; MemoryDependenceResults *MD; const bool OptForMinSize; - DenseMap DFSNumber; + DenseMap DFSNumber; BBSideEffectsSet BBSideEffects; MemorySSA *MSSA; int HoistedCtr; @@ -295,16 +292,14 @@ } /* Return true when I1 appears before I2 in the instructions of BB. */ - bool firstInBB(BasicBlock *BB, const Instruction *I1, const Instruction *I2) { - for (Instruction &I : *BB) { - if (&I == I1) - return true; - if (&I == I2) - return false; - } - - llvm_unreachable("I1 and I2 not found in BB"); + bool firstInBB(const Instruction *I1, const Instruction *I2) { + assert (I1->getParent() == I2->getParent()); + unsigned I1DFS = DFSNumber.lookup(I1); + unsigned I2DFS = DFSNumber.lookup(I2); + 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) { @@ -328,7 +323,7 @@ return true; // It is only harmful to hoist when the use is before OldPt. - if (firstInBB(UBB, MU->getMemoryInst(), OldPt)) + if (firstInBB(MU->getMemoryInst(), OldPt)) return true; } @@ -442,7 +437,7 @@ if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D)) if (auto *UD = dyn_cast(D)) - if (firstInBB(DBB, NewPt, UD->getMemoryInst())) + if (firstInBB(NewPt, UD->getMemoryInst())) // Cannot move the load or store to NewPt above its definition in D. return false; @@ -519,7 +514,7 @@ if (BB == HoistBB) { NewHoistBB = HoistBB; - NewHoistPt = firstInBB(BB, Insn, HoistPt) ? Insn : HoistPt; + NewHoistPt = firstInBB(Insn, HoistPt) ? Insn : HoistPt; } else { NewHoistBB = DT->findNearestCommonDominator(HoistBB, BB); if (NewHoistBB == BB) Index: llvm/trunk/test/Transforms/GVN/hoist.ll =================================================================== --- llvm/trunk/test/Transforms/GVN/hoist.ll +++ llvm/trunk/test/Transforms/GVN/hoist.ll @@ -631,17 +631,18 @@ ; should be hoisted. ; CHECK-LABEL: @hoistStores ; CHECK: zext -; CHECK: trunc -; CHECK: getelementptr -; CHECK: load -; CHECK: getelementptr -; CHECK: store -; CHECK: load -; CHECK: load -; CHECK: zext -; CHECK: add -; CHECK: store -; CHECK: br +; CHECK-NEXT: trunc +; CHECK-NEXT: getelementptr +; CHECK-NEXT: load +; CHECK-NEXT: getelementptr +; CHECK-NEXT: getelementptr +; CHECK-NEXT: store +; CHECK-NEXT: load +; CHECK-NEXT: load +; CHECK-NEXT: zext +; CHECK-NEXT: add +; CHECK-NEXT: store +; CHECK-NEXT: br ; CHECK: if.then ; CHECK: br