[DomTree] Accept Value as Def (NFC)

[nikic]

Summary

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.

[jdoerfert]

I like this. might be able to clean up some call sites with this. I wait a bit for other opinions.

[kuhar]

Interesting idea.

The first question that comes to my mind is what does it mean for and value to dominate a use.
The function-level comment says:

/// Return true if Def dominates a use in User.

this is clear when thinking about CFG-level graph dominance, but globals and arguments are not really present in the CFG. I guess the intention is to actually check if a value is always 'available' before a use, i.e., either executes (as an instruction) in the same function, or 'statically' available in the module. Is this consistent with your patch and understanding, @nikic?

If that's the case, I guess a theoretical way to tie it back to dominance would be to say that these values are defined in the virtual CFG entry which dominates all 'real' function entries (currently exactly one in LLVM IR). We don't currently have virtual entry nodes in dominators, but adding them would have other benefits too (faster re-rooting, support for multiple entry points).

[nikic]

In D89632#2339531, @kuhar wrote:

Interesting idea.

The first question that comes to my mind is what does it mean for and value to dominate a use.
The function-level comment says:

/// Return true if Def dominates a use in User.

this is clear when thinking about CFG-level graph dominance, but globals and arguments are not really present in the CFG. I guess the intention is to actually check if a value is always 'available' before a use, i.e., either executes (as an instruction) in the same function, or 'statically' available in the module. Is this consistent with your patch and understanding, @nikic?

Yes, that's the interpretation I have in mind. I think this is also consistent with the interpretation of existing DominatorTree methods. The CFG-level concept of graph dominance is only really applicable to the base API operating on basic blocks, while other APIs perform reasoning in terms of value availability. For example, if you ask whether an invoke dominates an instruction in the unwind block, then the graph-level interpretation would tell you "yes". However, the DomTree API will actually tell you "no", because it knows that the invoke result is only available in the success block.

[kuhar]

OK, thanks for the clarification. Can you update the function-level comment with an explanation like this?

[nikic]

Extend API comments a bit.

[kuhar]

Thanks for updating the comments.

One corner case: how does dominance work over global values (possibly with initializers)? Is it possible to have invalid IR where a global has a broken initializer, but dominates answers true? I don't know this part of IR very well and am not sure if such issues are possible or not.

[nikic]

In D89632#2342719, @kuhar wrote:

One corner case: how does dominance work over global values (possibly with initializers)? Is it possible to have invalid IR where a global has a broken initializer, but dominates answers true? I don't know this part of IR very well and am not sure if such issues are possible or not.

I can't say I'm particularly familiar with details of globals either. Here's the relevant bit of LangRef on the question of globals and dominance:

As SSA values, global variables define pointer values that are in scope (i.e. they dominate) all basic blocks in the program. Global variables always define a pointer to their “content” type because they describe a region of memory, and all memory objects in LLVM are accessed through pointers.

Because globals (as SSA values) refer to the pointer to the global, rather than the value of the global, I don't think the well-formedness of the initializer really comes into play here (though I'm also not sure in what way globals initializers can be "broken" in LLVM).

[asbirlea]

Allowing the dominates call to accept any Value can lead to unexpected errors, because there can be classes that are derived from Value that have nothing to do with the IR or the DT in some cases, and for those the result will always be true instead of an error or an assert. Pruning all such cases to include in the internal assert also doesn't make sense to me.

For example, all MemoryAccesss in MemorySSA are Values, but their use-user chains are isolated to their own "island" (a use of a MemoryAccess must be another MemoryAccess). A DT.dominate() call with a MemoryAccess as the first argument wouldn't make any sense, and should not be allowed, but the new API will accept it and return true.
Again, this is just an example, and many more may be added in the future, so it wouldn't make sense to assert inside the DT dominate call the DefV is not a MemoryAccess.

I think a better option is to add APIs for some of the specific cases you're looking for, for example a Constant (GlobalValue is subclassed already) or an Argument.
Even a generic API for Value should check for the specific cases known to be ok and return true for those, and then assert for anything else.

[nikic]

In D89632#2348338, @asbirlea wrote:

Allowing the dominates call to accept any Value can lead to unexpected errors, because there can be classes that are derived from Value that have nothing to do with the IR or the DT in some cases, and for those the result will always be true instead of an error or an assert. Pruning all such cases to include in the internal assert also doesn't make sense to me.

For example, all MemoryAccesss in MemorySSA are Values, but their use-user chains are isolated to their own "island" (a use of a MemoryAccess must be another MemoryAccess). A DT.dominate() call with a MemoryAccess as the first argument wouldn't make any sense, and should not be allowed, but the new API will accept it and return true.
Again, this is just an example, and many more may be added in the future, so it wouldn't make sense to assert inside the DT dominate call the DefV is not a MemoryAccess.

I think a better option is to add APIs for some of the specific cases you're looking for, for example a Constant (GlobalValue is subclassed already) or an Argument.
Even a generic API for Value should check for the specific cases known to be ok and return true for those, and then assert for anything else.

APIs for specific cases don't really make sense to me: If I know in advance that something is an Argument or Constant, there's no point in performing a domination check, as the result is known in advance. The point of accepting a Value* here is that you can pick an arbitrary IR value and perform a dominance check on it, without having to perform dyn_casts in advance.

Of course, this is only meaningful for values that appear as normal instruction operands, i.e. other instructions, arguments and constants. Using this with anything else is not meaningful, and I do agree that the assertion should reflect that. I've adjusted it to check for Constant/Argument only in https://github.com/llvm/llvm-project/commit/c0e8c94373b4e97d2eecc53bb16d22e085b73948.

With the stricter assertion, does this seem reasonable to you? We have many APIs that accept Value*s, and I daresay that nearly all of them wouldn't know what to do with a MemoryAccess*, so I don't see this as a fundamental problem as long as such arguments are properly rejected rather than silently misbehaving.

[asbirlea]

Thank you for the fix.

llvm/include/llvm/IR/Dominators.h

public:
 
   /// Handle invalidation explicitly.
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &);
 
   // 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.
   ///
   /// 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;

llvm/lib/IR/Dominators.cpp

bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
   auto PAC = PA.getChecker<DominatorTreeAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
            PAC.preservedSet<CFGAnalyses>());
 }
 
 // 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();
 
   // Any unreachable use is dominated, even if Def == User.
   if (!isReachableFromEntry(UseBB))
     return true;
 
   // Unreachable definitions don't dominate anything.
bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
   const BasicBlock *UseBB;
   if (PN)
     UseBB = PN->getIncomingBlock(U);
   else
     UseBB = UserInst->getParent();
   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();
 
   // Determine the block in which the use happens. PHI nodes use
   // their operands on edges; simulate this by thinking of the use
   // happening at the end of the predecessor block.
   const BasicBlock *UseBB;
   if (PHINode *PN = dyn_cast<PHINode>(UserInst))

llvm/unittests/IR/DominatorTreeTest.cpp

runWithDomTree(*M, "f",
     EXPECT_FALSE(DT->dominates(E13, E23));
 
     EXPECT_FALSE(DT->dominates(E23, E01));
     EXPECT_FALSE(DT->dominates(E23, E02));
     EXPECT_FALSE(DT->dominates(E23, E13));
     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));
+  });
+}