Index: include/llvm/Transforms/Utils/OrderedInstructions.h =================================================================== --- include/llvm/Transforms/Utils/OrderedInstructions.h +++ include/llvm/Transforms/Utils/OrderedInstructions.h @@ -35,6 +35,11 @@ /// The dominator tree of the parent function. DominatorTree *DT; + /// Return true if the first instruction comes before the second in the + /// same basic block. It will create an ordered basic block, if it does + /// not yet exist in OBBMap. + bool localComesBefore(const Instruction *, const Instruction *) const; + public: /// Constructor. OrderedInstructions(DominatorTree *DT) : DT(DT) {} @@ -42,6 +47,12 @@ /// Return true if first instruction dominates the second. bool dominates(const Instruction *, const Instruction *) const; + /// Return true if the first instruction comes before the second in the + /// dominator tree DFS traversal if they are in different basic blocks, + /// or if the first instruction comes before the second in the same basic + /// block. + bool comesBefore(const Instruction *, const Instruction *) 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 /// should call this function to invalidate the OrderedBasicBlock cache for Index: lib/Transforms/Utils/OrderedInstructions.cpp =================================================================== --- lib/Transforms/Utils/OrderedInstructions.cpp +++ lib/Transforms/Utils/OrderedInstructions.cpp @@ -14,19 +14,38 @@ #include "llvm/Transforms/Utils/OrderedInstructions.h" using namespace llvm; +bool OrderedInstructions::localComesBefore(const Instruction *InstA, + const Instruction *InstB) const { + assert(InstA->getParent() == InstB->getParent() && + "Instructions must be in the same basic block"); + + const BasicBlock *IBB = InstA->getParent(); + auto OBB = OBBMap.find(IBB); + if (OBB == OBBMap.end()) + OBB = OBBMap.insert({IBB, make_unique(IBB)}).first; + return OBB->second->dominates(InstA, InstB); +} + /// 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(); // 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); - } + if (InstA->getParent() == InstB->getParent()) + return localComesBefore(InstA, InstB); return DT->dominates(InstA->getParent(), InstB->getParent()); } + +bool OrderedInstructions::comesBefore(const Instruction *InstA, + const Instruction *InstB) const { + // Use ordered basic block in case the 2 instructions are in the same basic + // block. + if (InstA->getParent() == InstB->getParent()) + return localComesBefore(InstA, InstB); + + DomTreeNode *DA = DT->getNode(InstA->getParent()); + DomTreeNode *DB = DT->getNode(InstB->getParent()); + return DA->getDFSNumIn() < DB->getDFSNumIn(); +} Index: lib/Transforms/Utils/PredicateInfo.cpp =================================================================== --- lib/Transforms/Utils/PredicateInfo.cpp +++ lib/Transforms/Utils/PredicateInfo.cpp @@ -118,7 +118,7 @@ return false; if (ArgA && ArgB) return ArgA->getArgNo() < ArgB->getArgNo(); - return OI.dominates(cast(A), cast(B)); + return OI.comesBefore(cast(A), cast(B)); } // This compares ValueDFS structures, creating OrderedBasicBlocks where @@ -557,6 +557,7 @@ ValueDFS_Compare Compare(OI); // Compute liveness, and rename in O(uses) per Op. for (auto *Op : OpsToRename) { + LLVM_DEBUG(dbgs() << "Visiting " << *Op << "\n"); unsigned Counter = 0; SmallVector OrderedUses; const auto &ValueInfo = getValueInfo(Op); Index: test/Transforms/Util/PredicateInfo/ordering.ll =================================================================== --- /dev/null +++ test/Transforms/Util/PredicateInfo/ordering.ll @@ -0,0 +1,78 @@ +; RUN: opt -print-predicateinfo -analyze -debug < %s 2>&1 | FileCheck %s + +declare void @use(i32) + +; Make sure we are visiting the values to build predicate infos for in a +; deterministic order. +define i32 @test12(i32 %x, i32 %y) { +; CHECK: Visiting i32 %x +; CHECK: Visiting i32 %y +; CHECK: Visiting %lcmp = icmp eq i32 %x, 0 +; CHECK: Visiting %lcmp2 = icmp slt i32 %y, 1000 +; CHECK: Visiting %lcmp3 = icmp slt i32 %y.0, 900 +; CHECK: Visiting %lcmp4 = icmp slt i32 %y.0.1, 700 +; CHECK: Visiting %lcmp5 = icmp slt i32 %y.0.1.2, 700 +; CHECK: Visiting %lcmp6 = icmp slt i32 %y.0.1.2.3, 700 +; CHECK: Visiting %lcmp7 = icmp slt i32 %y.0.1.2.3.4, 700 +; CHECK: Visiting %rcmp = icmp eq i32 %x, 0 +entry: + br i1 undef, label %left, label %right + +left: + %lcmp = icmp eq i32 %x, 0 + br i1 %lcmp, label %left_cond_true, label %left_cond_false + +left_cond_true: + %lcmp2 = icmp slt i32 %y, 1000 + br i1 %lcmp2, label %left_cond_true2, label %left_ret + +left_cond_true2: + call void @use(i32 %y) + %lcmp3 = icmp slt i32 %y, 900 + br i1 %lcmp3, label %left_cond_true3, label %left_ret + +left_cond_true3: + call void @use(i32 %y) + %lcmp4 = icmp slt i32 %y, 700 + br i1 %lcmp4, label %left_cond_true4, label %left_ret + +left_cond_true4: + call void @use(i32 %y) + %lcmp5 = icmp slt i32 %y, 700 + br i1 %lcmp5, label %left_cond_true5, label %left_ret + +left_cond_true5: + call void @use(i32 %y) + %lcmp6 = icmp slt i32 %y, 700 + br i1 %lcmp6, label %left_cond_true6, label %left_ret + +left_cond_true6: + call void @use(i32 %y) + %lcmp7 = icmp slt i32 %y, 700 + br i1 %lcmp7, label %left_cond_true7, label %left_ret + +left_cond_true7: + ret i32 %y + +left_cond_false: + br label %left_ret + +left_ret: + %lres = phi i32 [ %x, %left_cond_true ], [ %x, %left_cond_false ], [ %x, %left_cond_true2 ], [ %x, %left_cond_true3 ], [ %x, %left_cond_true4 ], [ %x, %left_cond_true5 ], [ %x, %left_cond_true6 ] + + ret i32 %lres + +right: + %rcmp = icmp eq i32 %x, 0 + br i1 %rcmp, label %right_cond_true, label %right_cond_false + +right_cond_true: + br label %right_ret + +right_cond_false: + br label %right_ret + +right_ret: + %rres = phi i32 [ %x, %right_cond_true ], [ %x, %right_cond_false ] + ret i32 %rres +}