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,26 @@ 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; + if (dominates(Curr, CommonDom)) + // If current instruction dominates the previously found, pick it as new + // common dominator. + CommonDom = Curr; + else if (!dominates(CommonDom, Curr)) + // If there is no dominance relation between them, pick the terminator of + // their common dominator block as the common dominator instruction. + CommonDom = findNearestCommonDominator( + CommonDom->getParent(), Curr->getParent())->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,54 @@ 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(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})); + }); +}