[DomTree] Accept Value as Def (NFC)
authorNikita Popov <nikita.ppv@gmail.com>
Sat, 17 Oct 2020 18:54:53 +0000 (20:54 +0200)
committerNikita Popov <nikita.ppv@gmail.com>
Thu, 22 Oct 2020 16:32:03 +0000 (18:32 +0200)
Non-instruction defs like arguments, constants or global values
always dominate all instructions/uses inside the function. This
case currently needs to be treated separately by the caller, see
https://reviews.llvm.org/D89623#inline-832818 for an example.

This patch makes the dominator tree APIs accept a Value instead of
an Instruction and always returns true for the non-Instruction case.

A complication here is that BasicBlocks are also Values. For that
reason we can't support the dominates(Value *, BasicBlock *)
variant, as it would conflict with dominates(BasicBlock *, BasicBlock *),
which has different semantics. For the other two APIs we assert
that the passed value is not a BasicBlock.

Differential Revision: https://reviews.llvm.org/D89632

llvm/include/llvm/IR/Dominators.h
llvm/lib/IR/Dominators.cpp
llvm/unittests/IR/DominatorTreeTest.cpp

index a335e3c..08dbcca 100644 (file)
@@ -165,12 +165,21 @@ class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
   // Ensure base-class overloads are visible.
   using Base::dominates;
 
-  /// Return true if Def dominates a use in User.
+  /// Return true if value Def dominates use U, in the sense that Def is
+  /// available at U, and could be substituted as the used value without
+  /// violating the SSA dominance requirement.
   ///
-  /// This performs the special checks necessary if Def and User are in the same
-  /// basic block. Note that Def doesn't dominate a use in Def itself!
-  bool dominates(const Instruction *Def, const Use &U) const;
-  bool dominates(const Instruction *Def, const Instruction *User) const;
+  /// 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;
+  /// Return true if value Def dominates all possible uses inside instruction
+  /// User. Same comments as for the Use-based API apply.
+  bool dominates(const Value *Def, const Instruction *User) const;
+  // Does not accept Value to avoid ambiguity with dominance checks between
+  // two basic blocks.
   bool dominates(const Instruction *Def, const BasicBlock *BB) const;
 
   /// Return true if an edge dominates a use.
index be2c2ff..0fd0554 100644 (file)
@@ -115,8 +115,14 @@ bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
 // dominates - Return true if Def dominates a use in User. This performs
 // the special checks necessary if Def and User are in the same basic block.
 // Note that Def doesn't dominate a use in Def itself!
-bool DominatorTree::dominates(const Instruction *Def,
+bool DominatorTree::dominates(const Value *DefV,
                               const Instruction *User) const {
+  const Instruction *Def = dyn_cast<Instruction>(DefV);
+  if (!Def) {
+    assert(!isa<BasicBlock>(DefV) && "Should not be called with basic blocks");
+    return true; // Arguments, constants, globals dominate everything.
+  }
+
   const BasicBlock *UseBB = User->getParent();
   const BasicBlock *DefBB = Def->getParent();
 
@@ -250,7 +256,13 @@ bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
   return dominates(BBE, UseBB);
 }
 
-bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
+bool DominatorTree::dominates(const Value *DefV, const Use &U) const {
+  const Instruction *Def = dyn_cast<Instruction>(DefV);
+  if (!Def) {
+    assert(!isa<BasicBlock>(DefV) && "Should not be called with basic blocks");
+    return true; // Arguments, constants, globals dominate everything.
+  }
+
   Instruction *UserInst = cast<Instruction>(U.getUser());
   const BasicBlock *DefBB = Def->getParent();
 
index afb620f..21f11c8 100644 (file)
@@ -1071,3 +1071,32 @@ TEST(DominatorTree, EdgeDomination) {
     EXPECT_TRUE(DT->dominates(E23, E23));
   });
 }
+
+TEST(DominatorTree, ValueDomination) {
+  StringRef ModuleString = R"(
+    @foo = global i8 0
+    define i8 @f(i8 %arg) {
+      ret i8 %arg
+    }
+  )";
+
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  runWithDomTree(*M, "f",
+                 [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
+    Argument *A = F.getArg(0);
+    GlobalValue *G = M->getNamedValue("foo");
+    Constant *C = ConstantInt::getNullValue(Type::getInt8Ty(Context));
+
+    Instruction *I = F.getEntryBlock().getTerminator();
+    EXPECT_TRUE(DT->dominates(A, I));
+    EXPECT_TRUE(DT->dominates(G, I));
+    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));
+  });
+}