Index: include/llvm/Transforms/Utils/Local.h =================================================================== --- include/llvm/Transforms/Utils/Local.h +++ include/llvm/Transforms/Utils/Local.h @@ -290,7 +290,9 @@ /// \brief Replace each use of 'From' with 'To' if that use is dominated by /// the given edge. Returns the number of replacements made. unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, - const BasicBlockEdge &Edge); + const BasicBlockEdge &Root); +unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, + const BasicBlock *BB); } // End llvm namespace #endif Index: lib/IR/Dominators.cpp =================================================================== --- lib/IR/Dominators.cpp +++ lib/IR/Dominators.cpp @@ -144,10 +144,11 @@ bool DominatorTree::dominates(const BasicBlockEdge &BBE, const BasicBlock *UseBB) const { - // Assert that we have a single edge. We could handle them by simply - // returning false, but since isSingleEdge is linear on the number of - // edges, the callers can normally handle them more efficiently. - assert(BBE.isSingleEdge()); + assert(BBE.isSingleEdge() && + "We could handle multiple edges by simply " + "returning false, but since isSingleEdge is linear on the number of " + "edges," + " the callers can normally handle them more efficiently."); // If the BB the edge ends in doesn't dominate the use BB, then the // edge also doesn't. @@ -194,10 +195,11 @@ } bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const { - // Assert that we have a single edge. We could handle them by simply - // returning false, but since isSingleEdge is linear on the number of - // edges, the callers can normally handle them more efficiently. - assert(BBE.isSingleEdge()); + assert(BBE.isSingleEdge() && + "We could handle multiple edges by simply " + "returning false, but since isSingleEdge is linear on the number of " + "edges," + " the callers can normally handle them more efficiently."); Instruction *UserInst = cast(U.getUser()); // A PHI in the end of the edge is dominated by it. Index: lib/Transforms/Scalar/GVN.cpp =================================================================== --- lib/Transforms/Scalar/GVN.cpp +++ lib/Transforms/Scalar/GVN.cpp @@ -725,7 +725,8 @@ bool splitCriticalEdges(); BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); bool replaceOperandsWithConsts(Instruction *I) const; - bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root); + bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, + bool DominatesByEdge); bool processFoldableCondBr(BranchInst *BI); void addDeadBlock(BasicBlock *BB); void assignValNumForDeadCode(); @@ -1776,7 +1777,7 @@ // This property is only true in dominated successors, propagateEquality // will check dominance for us. - Changed |= propagateEquality(V, True, Edge); + Changed |= propagateEquality(V, True, Edge, false); } if (auto *CmpI = dyn_cast(V)) { @@ -2087,8 +2088,9 @@ /// The given values are known to be equal in every block /// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with /// 'RHS' everywhere in the scope. Returns whether a change was made. -bool GVN::propagateEquality(Value *LHS, Value *RHS, - const BasicBlockEdge &Root) { +/// If DominatesByEdge is false, then it means that it is dominated by Root.End. +bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, + bool DominatesByEdge) { SmallVector, 4> Worklist; Worklist.push_back(std::make_pair(LHS, RHS)); bool Changed = false; @@ -2145,7 +2147,10 @@ // LHS always has at least one use that is not dominated by Root, this will // never do anything if LHS has only one use. if (!LHS->hasOneUse()) { - unsigned NumReplacements = replaceDominatedUsesWith(LHS, RHS, *DT, Root); + unsigned NumReplacements = DominatesByEdge ? + replaceDominatedUsesWith(LHS, RHS, *DT, Root) : + replaceDominatedUsesWith(LHS, RHS, *DT, Root.getEnd()); + Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; } @@ -2216,8 +2221,9 @@ if (Num < NextNum) { Value *NotCmp = findLeader(Root.getEnd(), Num); if (NotCmp && isa(NotCmp)) { - unsigned NumReplacements = - replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root); + unsigned NumReplacements = DominatesByEdge ? + replaceDominatedUsesWith(LHS, RHS, *DT, Root) : + replaceDominatedUsesWith(LHS, RHS, *DT, Root.getEnd()); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; } @@ -2291,11 +2297,11 @@ Value *TrueVal = ConstantInt::getTrue(TrueSucc->getContext()); BasicBlockEdge TrueE(Parent, TrueSucc); - Changed |= propagateEquality(BranchCond, TrueVal, TrueE); + Changed |= propagateEquality(BranchCond, TrueVal, TrueE, true); Value *FalseVal = ConstantInt::getFalse(FalseSucc->getContext()); BasicBlockEdge FalseE(Parent, FalseSucc); - Changed |= propagateEquality(BranchCond, FalseVal, FalseE); + Changed |= propagateEquality(BranchCond, FalseVal, FalseE, true); return Changed; } @@ -2317,7 +2323,7 @@ // If there is only a single edge, propagate the case value into it. if (SwitchEdges.lookup(Dst) == 1) { BasicBlockEdge E(Parent, Dst); - Changed |= propagateEquality(SwitchCond, i.getCaseValue(), E); + Changed |= propagateEquality(SwitchCond, i.getCaseValue(), E, true); } } return Changed; Index: lib/Transforms/Utils/Local.cpp =================================================================== --- lib/Transforms/Utils/Local.cpp +++ lib/Transforms/Utils/Local.cpp @@ -1349,3 +1349,23 @@ } return Count; } + +unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, + DominatorTree &DT, + const BasicBlock *BB) { + assert(From->getType() == To->getType()); + + unsigned Count = 0; + for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); + UI != UE;) { + Use &U = *UI++; + auto *I = cast(U.getUser()); + if (DT.dominates(BB, I->getParent())) { + U.set(To); + DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as " + << *To << " in " << *U << "\n"); + ++Count; + } + } + return Count; +}