[Dominators] Use Instruction::comesBefore for block-local queries, NFC

[vsk]

Summary

Use the lazy instruction ordering facility for block-local dominance
queries. IIUC this was just left out of https://reviews.llvm.org/D51664
as it was rebased.

[kuhar]

LGTM

[rnk]

lgtm

I don't think it got lost in the rebase, I just never actually did this, the obvious thing. The next cleanup is to get rid of OrderedInstructions which is now a glorified wrapper of DominatorTree.

[kuhar]

llvm/lib/IR/Dominators.cpp

284

This code makes every user that is a phi be dominated by the def?
So if we have two phis, the one that comes later may be said to dominate its predecessor?

Not sure if I got confused here, but this looks fishy to me. Do we need this if at all?

[vsk]

llvm/lib/IR/Dominators.cpp

284

Yes, that's what this is doing, and no, I'm not sure this is /really/ needed.

IIUC all phis in a block are thought to execute "instantly, together". The verifier tries to make this clear by enforcing grouping of phis at the start of a block. Perhaps this is part of the enforcement mechanism, by making phi1 dom phi2 = phi2 dom phi1?

I find this inherently confusing, fwiw it's mentioned as a motivation for basic block arguments in the SIL/MLIR docs.

[kuhar]

llvm/lib/IR/Dominators.cpp

284

Ugh. But what happens when a phi has an incoming value that is another phi? Consider this pseudocode:

llvm
; predecessors %A, %B
%a = phi i32, [0, %A], [%b, %B]
%b = phi i32  [1, %A], [%2, %B]

The use of b in a's definition is considered valid from the perspective of dominance according to this code. Quickly glancing the llvm language reference I don't see anything saying you cannot use a phi value from the same basic block as an incoming value in another phi.

[vsk]

llvm/lib/IR/Dominators.cpp

284

Thanks for the example. That's.. weird. But, yes, I think that is allowed under the "phis execute instantly, together" interpretation. I've added a unit test that shows this.

[kuhar]

llvm/lib/IR/Dominators.cpp

284

Great, thanks for including this, especially since this isn't a part of your change.

Note that the unit test is not exectly what I described, though: in my example, the first phi was forward-referencing the second phi. I'll try to follow up on this in a separe revision this weekend of the next week.

[kuhar]

llvm/lib/IR/Dominators.cpp

284

Hi @vsk,

I've just checked this and both the pattern I described and the one that you added in the test are invalid; there's verification rules and LIT tests that make sure phi nodes in the same block don't cross-reference each other. Empirically, removing this special case for phi nodes breaks lots of existing tests.

llvm/lib/IR/Dominators.cpp

bool DominatorTree::dominates(const Instruction *Def,
   // A PHI is dominated only if the instruction dominates every possible use in
   // the UseBB.
   if (isa<InvokeInst>(Def) || isa<PHINode>(User))
     return dominates(Def, UseBB);
 
   if (DefBB != UseBB)
     return dominates(DefBB, UseBB);
 
-  // Loop through the basic block until we find Def or User.
-  BasicBlock::const_iterator I = DefBB->begin();
-  for (; &*I != Def && &*I != User; ++I)
-    /*empty*/;
-
-  return &*I == Def;
+  return Def->comesBefore(User);
 }
 
 // true if Def would dominate a use in any instruction in UseBB.
 // note that dominates(Def, Def->getParent()) is false.
 bool DominatorTree::dominates(const Instruction *Def,
                               const BasicBlock *UseBB) const {
   const BasicBlock *DefBB = Def->getParent();
 
bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
   // If the def and use are in different blocks, do a simple CFG dominator
   // tree query.
   if (DefBB != UseBB)
     return dominates(DefBB, UseBB);
 
   // Ok, def and use are in the same block. If the def is an invoke, it
   // doesn't dominate anything in the block. If it's a PHI, it dominates
   // everything in the block.
   if (isa<PHINode>(UserInst))
     return true;
 
-  // Otherwise, just loop through the basic block until we find Def or User.
-  BasicBlock::const_iterator I = DefBB->begin();
-  for (; &*I != Def && &*I != UserInst; ++I)
-    /*empty*/;
-
-  return &*I != UserInst;
+  return Def->comesBefore(UserInst);
 }
 
 bool DominatorTree::isReachableFromEntry(const Use &U) const {
   Instruction *I = dyn_cast<Instruction>(U.getUser());
 
   // ConstantExprs aren't really reachable from the entry block, but they
   // don't need to be treated like unreachable code either.
   if (!I) return true;

llvm/unittests/IR/DominatorTreeTest.cpp

 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
                                               StringRef ModuleStr) {
   SMDiagnostic Err;
   std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
   assert(M && "Bad assembly?");
   return M;
 }
 
+TEST(DominatorTree, PHIs) {
+  StringRef ModuleString = R"(
+      define void @f() {
+      bb1:
+        br label %bb1
+      bb2:
+        %a = phi i32 [0, %bb1], [1, %bb2]
+        %b = phi i32 [2, %bb1], [%a, %bb2]
+        br label %bb2
+      };
+  )";
+
+  // Parse the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  runWithDomTree(*M, "f",
+                 [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
+                   auto FI = F.begin();
+                   ++FI;
+                   BasicBlock *BB2 = &*FI;
+                   auto BI = BB2->begin();
+                   Instruction *PhiA = &*BI++;
+                   Instruction *PhiB = &*BI;
+
+                   // Phis are thought to execute "instantly, together".
+                   EXPECT_TRUE(DT->dominates(PhiA, PhiB));
+                   EXPECT_TRUE(DT->dominates(PhiB, PhiA));
+                 });
+}
+
 TEST(DominatorTree, Unreachable) {
   StringRef ModuleString =
       "declare i32 @g()\n"
       "define void @f(i32 %x) personality i32 ()* @g {\n"
       "bb0:\n"
       "  %y1 = add i32 %x, 1\n"
       "  %y2 = add i32 %x, 1\n"
       "  %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n"