Handle non-unique edges in edge-dominance

[anemet]

Summary

This removes a quadratic behavior in assert-enabled builds.

GVN propagates the equivalence from a condition into the blocks guarded by the
condition. E.g. for 'if (a == 7) { ... }', 'a' will be replaced in the block
with 7. It does this by replacing all the uses of 'a' that are dominated by
the true edge.

For a switch with N cases and U uses of the value, this will mean N * U calls
to 'dominates'. Asserting isSingleEdge in 'dominates' make this N^2 * U
because this function checks for the uniqueness of the edge. I.e. traverses
each edge between the SwitchInst's block and the cases.

The change removes the assert and makes 'dominates' works correctly in the
presence of non-unique edges.

This brings build time down by an order of magnitude for an input that has
~10k cases in a switch statement.

[davide]

Can you provide such a test?

[anemet]

In D33584#765339, @davide wrote:

Can you provide such a test?

Do you mean in the testsuite as part of the patch?

[davide]

In D33584#765343, @anemet wrote:

In D33584#765339, @davide wrote:

Can you provide such a test?

Do you mean in the testsuite as part of the patch?

Adding that to the testsuite, if it's not there, would be great.
If you can attach it here (or point a location where I can fetch, I'd like to run it under a profiler :)

[anemet]

In D33584#765358, @davide wrote:

Adding that to the testsuite, if it's not there, would be great.
If you can attach it here (or point a location where I can fetch, I'd like to run it under a profiler :)

I can't really share the code as is but should be able to generate something that demonstrates the issue.

I don't think we want to add it to the LLVM tests though. I.e. what would be the failure mode?

[davide]

In D33584#765359, @anemet wrote:

In D33584#765358, @davide wrote:

Adding that to the testsuite, if it's not there, would be great.
If you can attach it here (or point a location where I can fetch, I'd like to run it under a profiler :)

I can't really share the code as is but should be able to generate something that demonstrates the issue.

Sure.

I don't think we want to add it to the LLVM tests though. I.e. what would be the failure mode?

Maybe not the llvm-test suite, but test-suite [this: https://github.com/llvm-mirror/test-suite] (as it's starting to include testcases to show compile time regressions).

[• dberlin]

As I said last year, i believe, we should just remove this assert.
It doesn't help anything. The callers literally can't handle it any better if they want real dominance answers.
There isn't anywhere else in llvm we assert because "a thing may become quadratic if you do dumb things", and the assert itself is quadratic.

[anemet]

In D33584#765763, @dberlin wrote:

As I said last year, i believe, we should just remove this assert.
It doesn't help anything. The callers literally can't handle it any better if they want real dominance answers.

I thought GVN was a good counter example which bails early in the presence of duplicated edges: https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/GVN.cpp#L1733

There isn't anywhere else in llvm we assert because "a thing may become quadratic if you do dumb things", and the assert itself is quadratic.

Is it the problem that dominates is quadratic or that it returns the wrong answer in the presence of duplicated edges?

[• dberlin]

In D33584#765895, @anemet wrote:

In D33584#765763, @dberlin wrote:

As I said last year, i believe, we should just remove this assert.
It doesn't help anything. The callers literally can't handle it any better if they want real dominance answers.

I thought GVN was a good counter example which bails early in the presence of duplicated edges: https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/GVN.cpp#L1733

This is not actually any more efficient than dominance would have answered it.
Both have to do precisely the same thing:
Look at the predecessors and see if any are the same :)
That has the same time bound no matter how you do it.
At least how LLVM has implemented "edge dominance", an edge does not dominate a block unless (basically) start dominates end and start, end is unique.
(i'm ignoring critical edges here for a moment).

The uniqueness test takes the same time no matter whether the caller does it or dominates does it.

There isn't anywhere else in llvm we assert because "a thing may become quadratic if you do dumb things", and the assert itself is quadratic.

Is it the problem that dominates is quadratic or that it returns the wrong answer in the presence of duplicated edges?

I believe it is now broken, but it was not before.
Before, it was only quadratic over multiple calls
IE i repeatedly query the same set.
Most callers only make one call.

It has always been quadratic in the critical edge case.

It is possible to make both edge dominance and critical edge dominance constant time by a variety of methods if we wanted.
A trivial one for edge dominance:

1. Have the dom tree maintain a set of non-singular edges that it builds at construction time.

Return false if it's in the set.

another not so trivial:

2. convert the multiple edges into the equivalent block form using virtual basic blocks.

Given LLVM defines edge dominance in a way that means non-unique edges never dominate their end, this is a waste of time.

For critical edges, there are also a number of ways by adding virtual links or blocks or ... to the dom tree.

Also note:
GVN deliberately does *not* compute dominance answers for the other single edge case.
(see propagateequality and isOnlyReachableViaThisEdge).

FWIW: Using edge dominance for all of this is also, IMHO, not a great idea, but i'm ignoring that.

[anemet]

@davide, I have an ll file for you. On my box, with an assert-enabled opt it gives:

$ time ./bin/opt -gvn many-cases.ll -o /dev/null

real 1m48.190s
user 1m47.337s
sys 0m0.447s

with the patch:

$ time ./bin/opt -gvn many-cases.ll -o /dev/null

real 0m0.556s
user 0m0.353s
sys 0m0.042s

many-cases.ll6 MBDownload

[anemet]

Removed the asserts. As Danny put it:

"Given LLVM defines edge dominance in a way that means non-unique edges never dominate their end, this is a waste of time."

In other words, there is no need for an assert here since it's not the case
that the answer would be wrong or would take more time to compute than for
unique edges. It's simply that the answer would always be non-dominance by
how domininance of edges is defined.

Also added a comment the explain the situation with non-unique edges.

[• dberlin]

Note: i haven't thought out whether the pred test it does in most places will actually give the right answer.
At one point, it tested whether the edge was unique and returned false, this got turned into the current assert.
You may have to add that back.

If that is too slow, we could add the non-singular edge set and invalidate/recompute it. It should suffice to invalidate it anywhere we invalidate the dfs numbers.
Then, like dominates calls updateDFSNumber if they are invalid and it hits 32 queries, these function could do something similar and call updateNonSingleEdges if they are queried too much.

It's worth noting that the (edge, phi use) case is theoretically wrong after your xhange, right now, but it may not matter.

The above code will now claim that dominates(edge, phi use) is "true" for *any* use from the same block, when there are multiple incoming edges to the phi.
that *would* definitely be wrong if we allowed something like
bb1:
switch x {
case 1 : goto bb2;
case 2 : goto bb2;
}
bb2:
phi([1, bb1], [2, bb1]).

Because right now it will claim the second edge dominates the first use, etc.
However, we only allow multiple same-block edges to a phi if the values are the same:
bb1:
switch x {
case 1 : goto bb2;
case 2 : goto bb2;
}
bb2:
phi([x, bb1], [x, bb1]).

So i'm not sure returning true will break anything.
It may :)

[sanjoy]

In D33584#766056, @anemet wrote:

Removed the asserts. As Danny put it:

"Given LLVM defines edge dominance in a way that means non-unique edges never dominate their end, this is a waste of time."

In other words, there is no need for an assert here since it's not the case
that the answer would be wrong or would take more time to compute than for
unique edges. It's simply that the answer would always be non-dominance by
how domininance of edges is defined.

I'm not sure I agree with this. To be clear, say we have:

bb0:
  br i1 undef, label %bb1, label %bb1

bb1;
  ...

are you suggesting that dominates([bb0->bb1], bb1) will be false anyway, and there is no specific need to check isSingleEdge() at all? That does not seem to be the case -- I think DominatorTree::dominates([bb0->bb1], bb1) will return true. I think you need to change the loop in dominates over preds(End) to return false if the if (BB == Start) condition is taken more than once.

The external property this affects is cases like

bb0:
  br i1 %cond, label %bb1, label ...

bb1;
  ...

Today if the bb0 -> bb1 edge dominates some use of %cond then said use can be replaced with i1 true, but with your change that will no longer hold.

[• dberlin]

In D33584#766122, @sanjoy wrote:

In D33584#766056, @anemet wrote:

Removed the asserts. As Danny put it:

"Given LLVM defines edge dominance in a way that means non-unique edges never dominate their end, this is a waste of time."

In other words, there is no need for an assert here since it's not the case
that the answer would be wrong or would take more time to compute than for
unique edges. It's simply that the answer would always be non-dominance by
how domininance of edges is defined.

I'm not sure I agree with this. To be clear, say we have:

bb0:
  br i1 undef, label %bb1, label %bb1

bb1;
  ...

are you suggesting that dominates([bb0->bb1], bb1) will be false anyway, and there is no specific need to check isSingleEdge() at all?

yes, the current callers will all do the equivalent of returning false.

See isReachableOnlyByThisEdge, and the GVN case pointed out earlier.

> That does not seem to be the case -- I think DominatorTree::dominates([bb0->bb1], bb1) will return true.

This is the part where i said the patch is likely broken.
The thing we did before the assert was to return false if !singleEdge.

Hence my comment that "i'm not sure the pred loop will check what we need to have the same behavior we used to"

Today if the bb0 -> bb1 edge dominates some use of %cond then said use can be replaced with i1 true, but with your change that will no longer hold.

Today, any caller that asks if edge bb0->bb1 dominates some use of cond, it will assert :)

It will not return true ;)
Previous to the assert, we returned false.
This is why it says:
"// Assert that we have a single edge. We could handle them by simply
returning false. "

Now, you are right that there are situation we *could* return true, but we wouldn't :)

[sanjoy]

In D33584#766167, @dberlin wrote:

Today if the bb0 -> bb1 edge dominates some use of %cond then said use can be replaced with i1 true, but with your change that will no longer hold.

Today, any caller that asks if edge bb0->bb1 dominates some use of cond, it will assert :)

I see what you mean -- since we're only changing behavior in the case we'd have failed an assert before (i.e. before this change), the behavior change is correct by definition.

Now, you are right that there are situation we *could* return true, but we wouldn't :)

We wouldn't return true today (i.e. without this patch), but we would return true once this patch is applied. I was trying to argue that it makes more sense to return false for non-unique edges, since it preserves the "if the bb0 -> bb1 edge dominates some use of %cond then said use can be replaced with i1 true" reasoning. The reasoning holds today on all of the cases where the antecedent, "if the bb0 -> bb1 edge dominates some use of %cond", is valid (i.e. does not assert). With this change, we will make the antecedent valid in some cases where that implication won't hold, which is what I'm suggesting we avoid.

[anemet]

I certainly agree that if we're not returning false for the non-unique edge case then that will cause bugs later on.

Can I add unit-tests for edge-domination somehow? I am trying to test this with allowing non-unique edges in GVN but that won't fly as regression test.

[sanjoy]

In D33584#766182, @anemet wrote:

I certainly agree that if we're not returning false for the non-unique edge case then that will cause bugs later on.

Can I add unit-tests for edge-domination somehow? I am trying to test this with allowing non-unique edges in GVN but that won't fly as regression test.

I'd just go with a regular C++ test case in unittests/

[• dberlin]

In D33584#766174, @sanjoy wrote:

In D33584#766167, @dberlin wrote:

Today if the bb0 -> bb1 edge dominates some use of %cond then said use can be replaced with i1 true, but with your change that will no longer hold.

Today, any caller that asks if edge bb0->bb1 dominates some use of cond, it will assert :)

I see what you mean -- since we're only changing behavior in the case we'd have failed an assert before (i.e. before this change), the behavior change is correct by definition.

Now, you are right that there are situation we *could* return true, but we wouldn't :)

We wouldn't return true today (i.e. without this patch), but we would return true once this patch is applied. I was trying to argue that it makes more sense to return false for non-unique edges, since it preserves the "if the bb0 -> bb1 edge dominates some use of %cond then said use can be replaced with i1 true" reasoning. The reasoning holds today on all of the cases where the antecedent, "if the bb0 -> bb1 edge dominates some use of %cond", is valid (i.e. does not assert). With this change, we will make the antecedent valid in some cases where that implication won't hold, which is what I'm suggesting we avoid.

Oh yeah, i think we are all in violent agreement about the latter. We need to turn it back into a check that returns false, one way or the other.

[anemet]

In D33584#766183, @sanjoy wrote:

In D33584#766182, @anemet wrote:

I certainly agree that if we're not returning false for the non-unique edge case then that will cause bugs later on.

Can I add unit-tests for edge-domination somehow? I am trying to test this with allowing non-unique edges in GVN but that won't fly as regression test.

I'd just go with a regular C++ test case in unittests/

OK, will do. Thanks, guys!

[anemet]

This version handles edge-dominance in the presence of non-unique edges.

[sanjoy]

lgtm

unittests/IR/DominatorTreeTest.cpp

302 ↗

(On Diff #100807)

Any reason why these can't be EXPECT_TRUE and EXPECT_FALSE?

llvm/trunk/include/llvm/IR/Dominators.h

public:
   const BasicBlock *getStart() const {
     return Start;
   }
 
   const BasicBlock *getEnd() const {
     return End;
   }
 
+  /// Check if this is the only edge between Start and End.
   bool isSingleEdge() const;
 };
 
 template <> struct DenseMapInfo<BasicBlockEdge> {
   using BBInfo = DenseMapInfo<const BasicBlock *>;
 
   static unsigned getHashValue(const BasicBlockEdge *V);
 
public:
 
   /// \brief 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 dominates(const Instruction *Def, const Use &U) const;
   bool dominates(const Instruction *Def, const Instruction *User) const;
   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;
 
   // Ensure base class overloads are visible.
   using Base::isReachableFromEntry;
 
   /// \brief Provide an overload for a Use.
   bool isReachableFromEntry(const Use &U) const;

llvm/trunk/lib/IR/Dominators.cpp

if (const auto *II = dyn_cast<InvokeInst>(Def)) {
     return dominates(E, UseBB);
   }
 
   return dominates(DefBB, UseBB);
 }
 
 bool DominatorTree::dominates(const BasicBlockEdge &BBE,
                               const BasicBlock *UseBB) const {
-  // Assert that we have a single edge. We could handle them by simply
-  // returning false, but since isSingleEdge is linear on the number of
-  // edges, the callers can normally handle them more efficiently.
-  assert(BBE.isSingleEdge() &&
-         "This function is not efficient in handling multiple edges");
-
   // If the BB the edge ends in doesn't dominate the use BB, then the
   // edge also doesn't.
   const BasicBlock *Start = BBE.getStart();
   const BasicBlock *End = BBE.getEnd();
   if (!dominates(End, UseBB))
     return false;
 
   // Simple case: if the end BB has a single predecessor, the fact that it
bool DominatorTree::dominates(const BasicBlockEdge &BBE,
   //      .      NormalDest
   //      .
   //
   // Given the definition of dominance, NormalDest is dominated by X iff X
   // dominates all of NormalDest's predecessors (X, B, C in the example). X
   // trivially dominates itself, so we only have to find if it dominates the
   // other predecessors. Since the only way out of X is via NormalDest, X can
   // only properly dominate a node if NormalDest dominates that node too.
+  int IsDuplicateEdge = 0;
   for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
        PI != E; ++PI) {
     const BasicBlock *BB = *PI;
-    if (BB == Start)
+    if (BB == Start) {
+      // If there are multiple edges between Start and End, by definition they
+      // can't dominate anything.
+      if (IsDuplicateEdge++)
+        return false;
       continue;
+    }
 
     if (!dominates(End, BB))
       return false;
   }
   return true;
 }
 
 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
-  // Assert that we have a single edge. We could handle them by simply
-  // returning false, but since isSingleEdge is linear on the number of
-  // edges, the callers can normally handle them more efficiently.
-  assert(BBE.isSingleEdge() &&
-         "This function is not efficient in handling multiple edges");
-
   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;
 
   // Otherwise use the edge-dominates-block query, which

llvm/trunk/unittests/IR/DominatorTreeTest.cpp

runWithDomTree(
             BasicBlock::Create(F.getContext(), "new_entry", &F, BB0);
         BranchInst::Create(BB0, NewEntry);
         EXPECT_EQ(F.begin()->getName(), NewEntry->getName());
         EXPECT_TRUE(&F.getEntryBlock() == NewEntry);
         DT->setNewRoot(NewEntry);
         DT->verifyDomTree();
       });
 }
+
+TEST(DominatorTree, NonUniqueEdges) {
+  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"
+      "   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, DominatorTreeBase<BasicBlock> *PDT) {
+        Function::iterator FI = F.begin();
+
+        BasicBlock *BB0 = &*FI++;
+        BasicBlock *BB1 = &*FI++;
+        BasicBlock *BB2 = &*FI++;
+
+        const TerminatorInst *TI = BB0->getTerminator();
+        assert(TI->getNumSuccessors() == 3 && "Switch has three successors");
+
+        BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0));
+        assert(Edge_BB0_BB2.getEnd() == BB2 &&
+               "Default label is the 1st successor");
+
+        BasicBlockEdge Edge_BB0_BB1_a(BB0, TI->getSuccessor(1));
+        assert(Edge_BB0_BB1_a.getEnd() == BB1 && "BB1 is the 2nd successor");
+
+        BasicBlockEdge Edge_BB0_BB1_b(BB0, TI->getSuccessor(2));
+        assert(Edge_BB0_BB1_b.getEnd() == BB1 && "BB1 is the 3rd successor");
+
+        EXPECT_TRUE(DT->dominates(Edge_BB0_BB2, BB2));
+        EXPECT_FALSE(DT->dominates(Edge_BB0_BB2, BB1));
+
+        EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1));
+        EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1));
+
+        EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2));
+        EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2));
+      });
+}