[Dominators] Don't treat multi-edge as dominating

[nikic]

Summary

In https://github.com/llvm/llvm-project/blob/d2edca6276d1715a02d1144eae577b3d79673d67/llvm/include/llvm/IR/Dominators.h#L201-L202 we say:

If BBE is not a unique edge between start and end of the edge, it can
never dominate the use.

And the code starting at https://github.com/llvm/llvm-project/blob/d2edca6276d1715a02d1144eae577b3d79673d67/llvm/lib/IR/Dominators.cpp#L222 does handle it this way.

However, we also have two special cases for edge-phi domination and edge-edge domination, where we consider a multi-edge to be dominating. This patch makes them non-dominating, as we don't know which edge of the multi-edge we're querying.

I'm somewhat unsure about this change, because the resulting semantics could be considered somewhat odd (an edge does not dominate itself if it is a multi-edge), but I think they match the documentation and are at least self-consistent.

[nikic]

Ping

[kuhar]

I'm not too sure about the semantics either. I think it might be easier to think about if we tie this back to regular graphs without multi-edges.

My guess is that the original intention was to treat multi-edges as the same logical graph edge. With this abstraction, the existing behavior seems correct to me.

What you are proposing sounds to me similar to adding a virtual node in the middle of each duplicate edge. Is this a reasonable interpretation? If yes, this patch would appear fine to me, but I'm not sure if it's logically consistent with all the other code that may still rely on the old abstraction.

llvm/lib/IR/Dominators.cpp

 }
 
 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
   Instruction *UserInst = cast<Instruction>(U.getUser());
   // A PHI in the end of the edge is dominated by it.
   PHINode *PN = dyn_cast<PHINode>(UserInst);
   if (PN && PN->getParent() == BBE.getEnd() &&
       PN->getIncomingBlock(U) == BBE.getStart())
-    return true;
+    return BBE.isSingleEdge();
 
   // Otherwise use the edge-dominates-block query, which
   // handles the crazy critical edge cases properly.
   const BasicBlock *UseBB;
   if (PN)
     UseBB = PN->getIncomingBlock(U);
   else
     UseBB = UserInst->getParent();
bool DominatorTree::isReachableFromEntry(const Use &U) const {
   // Everything else uses their operands in their own block.
   return isReachableFromEntry(I->getParent());
 }
 
 // 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 BBE1.isSingleEdge();
   return dominates(BBE1, BBE2.getStart());
 }
 
 //===----------------------------------------------------------------------===//
 //  DominatorTreeAnalysis and related pass implementations
 //===----------------------------------------------------------------------===//
 //
 // This implements the DominatorTreeAnalysis which is used with the new pass

llvm/unittests/IR/DominatorTreeTest.cpp

runWithDomTree(*M, "f",
 
     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, SwitchEdgeDomination) {
+  StringRef ModuleString =
+      "define i32 @f(i32 %i, i32 *%p) {\n"
+      "bb0:\n"
+      "   store i32 %i, i32 *%p\n"
+      "   switch i32 %i, label %bb2 [\n"
+      "     i32 0, label %bb1\n"
+      "     i32 1, label %bb1\n"
+      "   ]\n"
+      " bb1:\n"
+      "   %phi = phi i32 [ 2, %bb0 ], [ 3, %bb0 ]\n"
+      "   ret i32 1\n"
+      " bb2:\n"
+      "   ret i32 4\n"
+      "}\n";
+
+  // Parse the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  runWithDomTree(*M, "f",
+                 [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
+    Function::iterator FI = F.begin();
+
+    BasicBlock *BB0 = &*FI++;
+    BasicBlock *BB1 = &*FI++;
+    BasicBlock *BB2 = &*FI++;
+    Instruction &Phi = *BB1->begin();
+
+    BasicBlockEdge E01(BB0, BB1);
+    BasicBlockEdge E02(BB0, BB2);
+
+    EXPECT_TRUE(DT->dominates(E02, E02));
+    EXPECT_FALSE(DT->dominates(E02, E01));
+    EXPECT_FALSE(DT->dominates(E01, E02));
+    // Does not dominate, because it is a multi-edge.
+    EXPECT_FALSE(DT->dominates(E01, E01));
+
+    // Similarly, multi-edge phi uses are not dominated.
+    EXPECT_FALSE(DT->dominates(E01, Phi.getOperandUse(0)));
+    EXPECT_FALSE(DT->dominates(E01, Phi.getOperandUse(1)));
+  });
+}
+
 TEST(DominatorTree, ValueDomination) {
   StringRef ModuleString = R"(
     @foo = global i8 0
     define i8 @f(i8 %arg) {
       ret i8 %arg
     }
   )";