[DomTree][NFC] Introduce function that finds common dom of multiple instructions

[mkazantsev]

Summary

This patch adds function findNearestCommonDominatorInst that, for a given
set of instructions, finds their nearest dominating instruction.

[mkazantsev]

Fixed bug with duplicating instructions in the list. Added relative checks.

[skatkov]

llvm/lib/IR/Dominators.cpp

348

What if you meet PHi node?

352

Introduce a variable for: CommonDom->getParent()
It appears three time in a loop.

[mkazantsev]

Added elaborate comments & tests with Phis.

[mkazantsev]

llvm/lib/IR/Dominators.cpp

348

Added comment explaining how we handle phis, added respective tests.

[asbirlea]

Algorithm lgtm.
+ @kuhar for additional review.

[skatkov]

Thanks! LGTM.

Probably it makes sense to wait a bit for @kuhar review as @asbirlea requested.

[kuhar]

As an alternative implementation, have you considered teaching DomTree::findNCD to work with multiple basic blocks first, and then using this to implement the multi-instruction findNCD?
The algorithm would be like this: create a vector VBB of BB of all instructions, find its NCD, case split on the NCD and VBB being the same block or not.

llvm/include/llvm/IR/Dominators.h

206–207

Does this work for invoke instructions? I'm thinking of a situation when two instructions are in a block whose immediate dominator ends with an invoke but the invoke result is not available for these two instructions.

[kuhar]

llvm/lib/IR/Dominators.cpp

344

nit: please add some vowels. Why not Instructions?

373

Maybe assert that CommDom actually dominates all Insns when EXPENSIVE_CHECKS are enabled?

[mkazantsev]

llvm/include/llvm/IR/Dominators.h

206–207

We don't guarantee that the result will be available. We only guarantee that this invoke will be executed before we reach each of the points in arg list.

[mkazantsev]

In D91767#2408334, @kuhar wrote:

As an alternative implementation, have you considered teaching DomTree::findNCD to work with multiple basic blocks first, and then using this to implement the multi-instruction findNCD?
The algorithm would be like this: create a vector VBB of BB of all instructions, find its NCD, case split on the NCD and VBB being the same block or not.

I was considering that, but don't really see how it's useful. The existing code makes N iterations, for which of them it either calls comesBefore or findNCD (findNCD will be called as many times as many different blocks there is - 1).

In the proposed solution, I'll need to:

• FIll the set of blocks (because API of findNCD needs blocks)
• Call multi-arg findNCD (which will call two-arg NCD same amount of times)
• make comesBefore queries for all instructions in topmost block.

Effectively it's always the same number of findNCD queries, overhead on set creation and potentially less number of comesBefore queries (in my solution we do it in all blocks). So overhead on set filling doesn't seem worth saving some number of cheap comesBefore queries in general case. So I just don't see why this alternative solution is better.

[kuhar]

In D91767#2410439, @mkazantsev wrote:

I was considering that, but don't really see how it's useful. The existing code makes N iterations, for which of them it either calls comesBefore or findNCD (findNCD will be called as many times as many different blocks there is - 1).

In the proposed solution, I'll need to:

• FIll the set of blocks (because API of findNCD needs blocks)
• Call multi-arg findNCD (which will call two-arg NCD same amount of times)
• make comesBefore queries for all instructions in topmost block.

Effectively it's always the same number of findNCD queries, overhead on set creation and potentially less number of comesBefore queries (in my solution we do it in all blocks). So overhead on set filling doesn't seem worth saving some number of cheap comesBefore queries in general case. So I just don't see why this alternative solution is better.

I was thinking more in terms of API design, not algorithmic efficiency. To me it seems like there's a clear boundary between block-level and instruction-level analysis here and I propose to separate the concerns more if this doesn't complicate the implementation. I think that finding the NCD of multiple blocks should be useful by itself; there was even a question about it on llvm-dev fairly recently: https://groups.google.com/g/llvm-dev/c/TZ3MCpwO5Yg/m/Z4MfZz_jBAAJ.

llvm/include/llvm/IR/Dominators.h

206–207

I'd find it very surprising if the result of findNCDInst returned an instruction that didn't dominate an argument.

Note that dominates is defined above as:

/// In particular, it is worth noting that:
///  * Non-instruction Defs dominate everything.
///  * Def does not dominate a use in Def itself (outside of degenerate cases
///    like unreachable code or trivial phi cycles).
///  * Invoke/callbr Defs only dominate uses in their default destination.
bool dominates(const Value *Def, const Use &U) const;

[skatkov]

llvm/include/llvm/IR/Dominators.h

206–207

As I understand this function is not about def and use at all while in the doc you mentioned it is about def-use chain.

And why do you think that result of this function does not dominate any of arguments? It does to my understanding if consider this as an extension of Basic Block domination definition.

[skatkov]

llvm/include/llvm/IR/Dominators.h

206–207

Does it make sense to explicitly mention in the doc function that it is not about def-use chain but about instructions and use an example with invoke to emphasize it to avoid confusion and incorrect usage of this utility function?

[kuhar]

llvm/include/llvm/IR/Dominators.h

206–207

As I understand this function is not about def and use at all while in the doc you mentioned it is about def-use chain.

Yeah, you are right.

And why do you think that result of this function does not dominate any of arguments?

By 'an argument' I meant any instruction in Insns, not the type Argument.

It does to my understanding if consider this as an extension of Basic Block domination definition.

I got tripped of that this generalizes some existing function that checks if an instruction dominates another instruction. But now that you pointed out that the two-argument dominates operates on instructions and *uses*, I see that this is not the case.

Where do you plan to use findNCDInst? I'm trying to understand why bool dominates(Inst, Inst) and Inst findNCDInst(Inst, Inst) haven't been used before.

[mkazantsev]

You can find the planned user in dependencies stack: https://reviews.llvm.org/D90456

I need the common dom to find the latest context where we can prove predicate so that it's also true for all given instructions.

[mkazantsev]

llvm/include/llvm/IR/Dominators.h

206–207

The user of this: D90456.

I don't need def-use notion here, just precedence in execution flow.

[kuhar]

In D91767#2410450, @mkazantsev wrote:

You can find the planned user in dependencies stack: https://reviews.llvm.org/D90456

I need the common dom to find the latest context where we can prove predicate so that it's also true for all given instructions.

What do you think about defining and implementing bool dominates(Inst, Inst) at the same time (or before) findNCDInst? IMO it's awkward to explain what finding the NCD of instructions means without first defining dominance between instructions. Then you can use that definition as a post-condition for findNCDInst and check that the result dominates all Insns. Similarly, I'd also implement findNCD for multiple blocks first and then use it in the version for instructions. Otherwise I'd see it as building something very specific without laying out all the foundations first.

[mkazantsev]

In D91767#2410454, @kuhar wrote:

In D91767#2410450, @mkazantsev wrote:

You can find the planned user in dependencies stack: https://reviews.llvm.org/D90456

I need the common dom to find the latest context where we can prove predicate so that it's also true for all given instructions.

What do you think about defining and implementing bool dominates(Inst, Inst) at the same time (or before) findNCDInst?

It will have a signature clash with existing dominates(def, use). For that, we first need to rename existing dominates (including all its users across the code) into something like defUseAvailable, and only then implement this. It's a massive refactoring of whole DomTree which I definitely don't want to be blocked on. As you see, as set of changes is currently waiting for this patch.

We can make this, but separately, as follow-up, after the changes are unblocked, if it makes sense.

[mkazantsev]

llvm/lib/IR/Dominators.cpp

373

dominates(def, use) has a slightly different semantics and fails for dominates(x, x). I also think ther will be tricky corner cases when it will fail when both args are Phis from the same block.

[mkazantsev]

I see the deep API problem here now. Current dominates(Value *, Instruction *) should not be called like that (at least because it returns false for dominates(X, X)). It has a different semantics, and should be called something like "canBeUserOf".

The clear definition of dominance between two instructions is also something fishy. Specifically, it is fishy for Phi nodes from the same block (there is no precedence between them). Maybe the best name to express what we need in this patch would be comesBefore.

It looks like a vast rework of whole DomTree API. I'm OK doing that, but do not want to have my patches waiting for this API rework (they honestly don't need). Let's unblock this branch first and then think how to name it better.

[mkazantsev]

Added expensive asserts;
Renamed Insns->Instructions

Further rework, I think, should go separately, because it affects code outside this one.

[mkazantsev]

Fixed check (as expected, dominates fails for two Phis from the same block).

[kuhar]

In D91767#2410579, @mkazantsev wrote:

I see the deep API problem here now. Current dominates(Value *, Instruction *) should not be called like that (at least because it returns false for dominates(X, X)). It has a different semantics, and should be called something like "canBeUserOf".

The clear definition of dominance between two instructions is also something fishy. Specifically, it is fishy for Phi nodes from the same block (there is no precedence between them). Maybe the best name to express what we need in this patch would be comesBefore.

It looks like a vast rework of whole DomTree API. I'm OK doing that, but do not want to have my patches waiting for this API rework (they honestly don't need). Let's unblock this branch first and then think how to name it better.

I see three ways forward:

1. Propose the renaming of the existing .dominates functions on llvm-dev and to that before this work.
2. Add instruction-level dominance function, but call it differently to avoid name collision, e.g., dominatesInst. Use this in this revision and propose refactoring afterwards.
3. Implement findNCDInst as a free function where it's actually necessary. Maybe this notion of dominance and NCD of instructions is domain-specific enough that there's not much value in adding this to DominatorTree?

I'd be most comfortable with (2) or (3).

[mkazantsev]

Let's go with 3. The idea was to share this code if someone might need it. I'm totally fine if it's written every time in different places whenever someone needs this logic.

llvm/include/llvm/IR/Dominators.h

public:
   ///
   /// If BBE is not a unique edge between start and end of the edge, it can
   /// never dominate the use.
   bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
   bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
   /// 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 *> Instruction) const;
+
   // Ensure base class overloads are visible.
   using Base::isReachableFromEntry;
 
   /// Provide an overload for a Use.
   bool isReachableFromEntry(const Use &U) const;
 
   // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
   void viewGraph(const Twine &Name, const Twine &Title);

llvm/lib/IR/Dominators.cpp

 // Edge BBE1 dominates edge BBE2 if they match or BBE1 dominates start of BBE2.
 bool DominatorTree::dominates(const BasicBlockEdge &BBE1,
                               const BasicBlockEdge &BBE2) const {
   if (BBE1.getStart() == BBE2.getStart() && BBE1.getEnd() == BBE2.getEnd())
     return true;
   return dominates(BBE1, BBE2.getStart());
 }
 
+Instruction *DominatorTree::findNearestCommonDominatorInst(
+    ArrayRef<Instruction *> 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
 //===----------------------------------------------------------------------===//
 //
 // This implements the DominatorTreeAnalysis which is used with the new pass
 // manager. It also implements some methods from utility passes.
 //
 //===----------------------------------------------------------------------===//

llvm/unittests/IR/DominatorTreeTest.cpp

runWithDomTree(*M, "f",
     EXPECT_TRUE(DT->dominates(C, I));
 
     const Use &U = I->getOperandUse(0);
     EXPECT_TRUE(DT->dominates(A, U));
     EXPECT_TRUE(DT->dominates(G, U));
     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<Module> 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 }));
+  });
+}