Index: llvm/include/llvm/IR/Dominators.h =================================================================== --- llvm/include/llvm/IR/Dominators.h +++ llvm/include/llvm/IR/Dominators.h @@ -191,6 +191,26 @@ /// 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. It is defined for instructions A and B as follows: + /// + /// - If A and B are from the same block, their common dom is either A or B + /// which comes first in the order of precedence. Note: there is no + /// precedence before two Phis from the same basic block. For two Phis, we + /// return one of them that comes first in order defined by `comesBefore`. + /// + /// - If A and B are in different blocks and there is a dominance relation + /// between those blocks, return either A or B which lies in the dominating + /// block. + /// + /// - If there is no dominance relation between A and B's blocks, return the + /// terminator of the nearest block that dominates both of them. + /// + /// This relation is transitive, so it can easily be generalized to more than + /// two instructions. + Instruction * + findNearestCommonDominatorInst(ArrayRef Instruction) 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,57 @@ return dominates(BBE1, BBE2.getStart()); } +Instruction *DominatorTree::findNearestCommonDominatorInst( + ArrayRef Instructions) const { + assert(!Instructions.empty() && "Should be at least one instruction!"); + auto It = Instructions.begin(); + Instruction *CommonDom = *It++; + for (auto E = Instructions.end(); It != E; ++It) { + Instruction *Curr = *It; + BasicBlock *CurrBB = Curr->getParent(); + BasicBlock *CommonDomBB = CommonDom->getParent(); + // Case 1: instructions from the same block. Pick the instruction that + // comes first in order defined by `comesBefore`. + if (CurrBB == CommonDomBB) { + 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 *NewCommonDomBB = + findNearestCommonDominator(CurrBB, CommonDomBB); + if (NewCommonDomBB == CurrBB) + CommonDom = Curr; + else if (NewCommonDomBB != CommonDomBB) + CommonDom = NewCommonDomBB->getTerminator(); + } + +#ifdef EXPENSIVE_CHECKS + // Make sure that we dominate every instruction. + for (auto *I : Instructions) { + // One of instructions in the list is fine. + if (CommonDom == I) + continue; + + // For instructions in the same block, CommonDom must come first. We cannot + // call `dominates` because there is no dominance between two Phis from the + // same block. + if (CommonDom->getParent() == I->getParent()) + assert(CommonDom->comesBefore(I) && "Not a dominator!"); + else + assert(dominates(CommonDom, I) && "Not a dominator!"); + } +#endif // EXPENSIVE_CHECKS + + 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,88 @@ 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" + " %d = load i32, i32* %p\n" + " %e = load i32, i32* %p\n" + " br label %bb3\n" + " bb2:\n" + " %f = load i32, i32* %p\n" + " %g = load i32, i32* %p\n" + " br label %bb3\n" + " bb3:\n" + " %phi1 = phi i32 [%d, %bb1], [%f, %bb2]\n" + " %phi2 = phi i32 [%e, %bb1], [%g, %bb2]\n" + " ret i32 4" + "}\n"; + + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + + runWithDomTree(*M, "f", + [&](Function &Fn, DominatorTree *DT, PostDominatorTree *PDT) { + Function::iterator FI = Fn.begin(); + + BasicBlock *BB0 = &*FI++; + BasicBlock *BB1 = &*FI++; + BasicBlock *BB2 = &*FI++; + BasicBlock *BB3 = &*FI++; + + auto It = BB0->begin(); + Instruction *A = &*It++; + Instruction *B = &*It++; + Instruction *C = &*It++; + Instruction *Term0 = BB0->getTerminator(); + + It = BB1->begin(); + Instruction *D = &*It++; + Instruction *E = &*It++; + Instruction *Term1 = BB1->getTerminator(); + + It = BB2->begin(); + Instruction *F = &*It++; + Instruction *G = &*It++; + Instruction *Term2 = BB2->getTerminator(); + + It = BB3->begin(); + Instruction *Phi1 = &*It++; + Instruction *Phi2 = &*It++; + Instruction *Term3 = BB3->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 })); + + EXPECT_EQ(D, DT->findNearestCommonDominatorInst({ E, D })); + EXPECT_EQ(F, DT->findNearestCommonDominatorInst({ G, F })); + EXPECT_EQ(Term0, DT->findNearestCommonDominatorInst({ D, F })); + EXPECT_EQ(Phi1, DT->findNearestCommonDominatorInst({ Phi1, Phi2 })); + EXPECT_EQ(Phi1, DT->findNearestCommonDominatorInst({ Phi2, Phi1 })); + }); +}