Index: include/llvm/IR/Dominators.h =================================================================== --- include/llvm/IR/Dominators.h +++ include/llvm/IR/Dominators.h @@ -143,6 +143,9 @@ /// /// This performs the special checks necessary if Def and User are in the same /// basic block. Note that Def doesn't dominate a use in Def itself! + + /// Note: These functions are deprecated and will be removed, please use the + /// versions in OrderedInstructions instead. bool dominates(const Instruction *Def, const Use &U) const; bool dominates(const Instruction *Def, const Instruction *User) const; bool dominates(const Instruction *Def, const BasicBlock *BB) const; Index: include/llvm/Transforms/Scalar/NaryReassociate.h =================================================================== --- include/llvm/Transforms/Scalar/NaryReassociate.h +++ include/llvm/Transforms/Scalar/NaryReassociate.h @@ -88,6 +88,7 @@ #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Utils/OrderedInstructions.h" namespace llvm { class NaryReassociatePass : public PassInfoMixin { @@ -155,6 +156,7 @@ AssumptionCache *AC; const DataLayout *DL; DominatorTree *DT; + std::unique_ptr OI; ScalarEvolution *SE; TargetLibraryInfo *TLI; TargetTransformInfo *TTI; Index: include/llvm/Transforms/Utils/OrderedInstructions.h =================================================================== --- include/llvm/Transforms/Utils/OrderedInstructions.h +++ include/llvm/Transforms/Utils/OrderedInstructions.h @@ -39,8 +39,9 @@ /// Constructor. OrderedInstructions(DominatorTree *DT) : DT(DT) {} - /// Return true if first instruction dominates the second. + /// Return true if first instruction dominates the second instruction/use. bool dominates(const Instruction *, const Instruction *) const; + bool dominates(const Instruction *, const Use &) const; /// Invalidate the OrderedBasicBlock cache when its basic block changes. /// i.e. If an instruction is deleted or added to the basic block, the user Index: lib/Transforms/Scalar/NaryReassociate.cpp =================================================================== --- lib/Transforms/Scalar/NaryReassociate.cpp +++ lib/Transforms/Scalar/NaryReassociate.cpp @@ -175,7 +175,7 @@ TLI = TLI_; TTI = TTI_; DL = &F.getParent()->getDataLayout(); - + OI.reset(new OrderedInstructions(DT)); bool Changed = false, ChangedInThisIteration; do { ChangedInThisIteration = doOneIteration(F); @@ -500,7 +500,7 @@ // during rewriting. if (Value *Candidate = Candidates.back()) { Instruction *CandidateInstruction = cast(Candidate); - if (DT->dominates(CandidateInstruction, Dominatee)) + if (OI->dominates(CandidateInstruction, Dominatee)) return CandidateInstruction; } Candidates.pop_back(); Index: lib/Transforms/Utils/OrderedInstructions.cpp =================================================================== --- lib/Transforms/Utils/OrderedInstructions.cpp +++ lib/Transforms/Utils/OrderedInstructions.cpp @@ -12,21 +12,79 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/Utils/OrderedInstructions.h" +#include "llvm/IR/Instructions.h" using namespace llvm; /// Given 2 instructions, use OrderedBasicBlock to check for dominance relation /// if the instructions are in the same basic block, Otherwise, use dominator -/// tree. -bool OrderedInstructions::dominates(const Instruction *InstA, - const Instruction *InstB) const { - const BasicBlock *IBB = InstA->getParent(); +/// tree dominate routines. +bool OrderedInstructions::dominates(const Instruction *Def, + const Instruction *User) const { + bool OldResult = DT->dominates(Def, User); + const auto *DefBB = Def->getParent(); + const auto *UseBB = User->getParent(); + assert(DefBB && UseBB); + // Any unreachable use is dominated, even if Def == User. + if (!DT->isReachableFromEntry(UseBB)) { + assert(OldResult == true); + return true; + } + + // Unreachable definitions don't dominate anything. + if (!DT->isReachableFromEntry(DefBB)) { + assert(OldResult == false); + return false; + } + + // An instruction doesn't dominate a use in itself. + if (Def == User) { + assert(OldResult == false); + return false; + } + + if (isa(Def)) { + assert(OldResult == DT->dominates(Def, UseBB)); + return DT->dominates(Def, UseBB); + } + + if (DefBB != UseBB) { + assert(OldResult == DT->dominates(Def->getParent(), User->getParent())); + return DT->dominates(Def->getParent(), User->getParent()); + } + // Use ordered basic block to do dominance check in case the 2 instructions // are in the same basic block. - if (IBB == InstB->getParent()) { - auto OBB = OBBMap.find(IBB); - if (OBB == OBBMap.end()) - OBB = OBBMap.insert({IBB, make_unique(IBB)}).first; - return OBB->second->dominates(InstA, InstB); + auto OBB = OBBMap.find(DefBB); + if (OBB == OBBMap.end()) + OBB = OBBMap.insert({DefBB, make_unique(DefBB)}).first; + assert(OldResult == OBB->second->dominates(Def, User)); + return OBB->second->dominates(Def, User); +} + +bool OrderedInstructions::dominates(const Instruction *Def, + const Use &U) const { + bool OldResult = DT->dominates(Def, U); + if (Def == U.getUser()) { + assert(OldResult == false); + return false; + } + + // PHI node uses appear at the end of the block they come from. + if (auto *PN = dyn_cast(U.getUser())) { + auto *DefBB = Def->getParent(); + auto *UseBB = PN->getIncomingBlock(U); + assert(DefBB && UseBB); + if (DefBB != UseBB) { + assert(OldResult == DT->dominates(DefBB, UseBB)); + return DT->dominates(DefBB, UseBB); + } + // This mirrors the behavior of DominatorTree, which assumed no ordering + // among existing phi nodes. + if (isa(U.getUser())) { + assert(OldResult == true); + return true; + } } - return DT->dominates(InstA->getParent(), InstB->getParent()); + assert(OldResult == dominates(Def, cast(U.getUser()))); + return dominates(Def, cast(U.getUser())); } Index: lib/Transforms/Utils/PredicateInfo.cpp =================================================================== --- lib/Transforms/Utils/PredicateInfo.cpp +++ lib/Transforms/Utils/PredicateInfo.cpp @@ -504,11 +504,12 @@ // to ensure we dominate all of our uses. Always insert right before the // relevant instruction (terminator, assume), so that we insert in proper // order in the case of multiple predicateinfo in the same block. + CallInst *PIC = nullptr; if (isa(ValInfo)) { IRBuilder<> B(getBranchTerminator(ValInfo)); Function *IF = Intrinsic::getDeclaration( F.getParent(), Intrinsic::ssa_copy, Op->getType()); - CallInst *PIC = + PIC = B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++)); PredicateMap.insert({PIC, ValInfo}); Result.Def = PIC; @@ -519,10 +520,11 @@ IRBuilder<> B(PAssume->AssumeInst); Function *IF = Intrinsic::getDeclaration( F.getParent(), Intrinsic::ssa_copy, Op->getType()); - CallInst *PIC = B.CreateCall(IF, Op); + PIC = B.CreateCall(IF, Op); PredicateMap.insert({PIC, ValInfo}); Result.Def = PIC; } + OI.invalidateBlock(PIC->getParent()); } return RenameStack.back().Def; } @@ -659,7 +661,7 @@ DEBUG(dbgs() << "Found replacement " << *Result.Def << " for " << *VD.U->get() << " in " << *(VD.U->getUser()) << "\n"); - assert(DT.dominates(cast(Result.Def), *VD.U) && + assert(OI.dominates(cast(Result.Def), *VD.U) && "Predicateinfo def should have dominated this use"); VD.U->set(Result.Def); }