Index: llvm/include/llvm/IR/Dominators.h =================================================================== --- llvm/include/llvm/IR/Dominators.h +++ llvm/include/llvm/IR/Dominators.h @@ -191,6 +191,11 @@ /// Returns true if edge \p BBE1 dominates edge \p BBE2. bool dominates(const BasicBlockEdge &BBE1, const BasicBlockEdge &BBE2) const; + /// Given a set of instructions, return the nearest instruction that dominates + /// all of them. + Instruction * + findNearestCommonDominatorInst(ArrayRef Insns) const; + // Ensure base class overloads are visible. using Base::isReachableFromEntry; Index: llvm/lib/IR/Dominators.cpp =================================================================== --- llvm/lib/IR/Dominators.cpp +++ llvm/lib/IR/Dominators.cpp @@ -340,6 +340,37 @@ return dominates(BBE1, BBE2.getStart()); } +Instruction *DominatorTree::findNearestCommonDominatorInst( + ArrayRef Insns) const { + assert(!Insns.empty() && "Should be at least one instruction!"); + auto It = Insns.begin(); + Instruction *CommonDom = *It++; + for (auto E = Insns.end(); It != E; ++It) { + Instruction *Curr = *It; + BasicBlock *CurrBB = Curr->getParent(); + // Case 1: instructions from the same block. Pick the top one. + if (CurrBB == CommonDom->getParent()) { + if (Curr->comesBefore(CommonDom)) + CommonDom = Curr; + continue; + } + + // Case 2: different blocks. Pick the common dominator of their blocks. + // Case 2a: Curr's block dominates best found. Pick Curr as common dom. + // Case 2b: CommonDom's parent dominates Curr's block. No update needed. + // Case 2c: The common dominator of these blocks is neither of the + // instructions parents. In this case, the nearest instruction that + // dominates both of them is CurrBB's terminator. + BasicBlock *CommonDomBB = + findNearestCommonDominator(CurrBB, CommonDom->getParent()); + if (CommonDomBB == CurrBB) + CommonDom = Curr; + else if (CommonDomBB != CommonDom->getParent()) + CommonDom = CommonDomBB->getTerminator(); + } + return CommonDom; +} + //===----------------------------------------------------------------------===// // DominatorTreeAnalysis and related pass implementations //===----------------------------------------------------------------------===// Index: llvm/unittests/IR/DominatorTreeTest.cpp =================================================================== --- llvm/unittests/IR/DominatorTreeTest.cpp +++ llvm/unittests/IR/DominatorTreeTest.cpp @@ -1100,3 +1100,60 @@ EXPECT_TRUE(DT->dominates(C, U)); }); } + +TEST(DominatorTree, InstructionCommonDominator) { + StringRef ModuleString = "define i32 @f(i1 %cond, i32* %p) {\n" + " bb0:\n" + " %a = load i32, i32* %p\n" + " %b = load i32, i32* %p\n" + " %c = load i32, i32* %p\n" + " br i1 %cond, label %bb1, label %bb2\n" + " bb1:\n" + " br label %bb3\n" + " bb2:\n" + " br label %bb3\n" + " bb3:\n" + " ret i32 4" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + + runWithDomTree(*M, "f", + [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { + Function::iterator FI = F.begin(); + + BasicBlock *BB0 = &*FI++; + auto It = BB0->begin(); + Instruction *A = &*It++; + Instruction *B = &*It++; + Instruction *C = &*It++; + Instruction *Term0 = BB0->getTerminator(); + Instruction *Term1 = (*FI++).getTerminator(); + Instruction *Term2 = (*FI++).getTerminator(); + Instruction *Term3 = (*FI++).getTerminator(); + + EXPECT_EQ(A, DT->findNearestCommonDominatorInst({ A, B })); + EXPECT_EQ(A, DT->findNearestCommonDominatorInst({ A, B, C })); + EXPECT_EQ(B, DT->findNearestCommonDominatorInst({ C, B })); + + EXPECT_EQ(A, DT->findNearestCommonDominatorInst({ A, A })); + EXPECT_EQ(B, DT->findNearestCommonDominatorInst({ B, B })); + EXPECT_EQ(C, DT->findNearestCommonDominatorInst({ C, C })); + + EXPECT_EQ(Term0, DT->findNearestCommonDominatorInst({ Term0 })); + EXPECT_EQ(Term1, DT->findNearestCommonDominatorInst({ Term1 })); + EXPECT_EQ(Term2, DT->findNearestCommonDominatorInst({ Term2 })); + EXPECT_EQ(Term3, DT->findNearestCommonDominatorInst({ Term3 })); + + EXPECT_EQ(Term0, DT->findNearestCommonDominatorInst({ Term1, Term2 })); + EXPECT_EQ(Term0, DT->findNearestCommonDominatorInst({ Term1, Term3 })); + EXPECT_EQ(Term0, DT->findNearestCommonDominatorInst({ Term2, Term3 })); + EXPECT_EQ(Term0, + DT->findNearestCommonDominatorInst({ Term1, Term2, Term3 })); + + EXPECT_EQ(B, + DT->findNearestCommonDominatorInst({ Term1, Term2, Term3, B })); + }); +}