[NewGVN] Update dominator tree for unreachable blocks.

[fhahn]

Summary

The dominator tree has to be updated after all instructions for an
unreachable block have been removed.

This patch should fix all NewGVN test failures with EXPENSIVE_CHECKS.

[fhahn]

lib/Transforms/Scalar/NewGVN.cpp

1911

Another possibility would be to add a function to recursively erase all nodes dominated by BB. What do you think?

[• dberlin]

Yeah, we discovered this yesterday.

The underlying issue is twofold

1. changeToUnreachable is supposed to be local, but modifies the CFG :(
2. You can't insert unreachableinst except as a terminator.

I'm torn here. Chandler's suggestion was to preserve the CFG. That will work, actually, right up until we add PRE.
Then we are going to split critical edges for sure.
(though we definitely miss some optimizations due to not splitting critical edges right now, it's just more common with PRE).

Current GVN does not preserve CFG.
If we want to preserve CFG, we should do a store of undef to null (which simplifycfg will transform into unreachable) and revert the original patch.

NewGVN is also an analysis with an elimination pass tacked on (and built so we can eventually split it up that way). The analysis should not modify the CFG for sure, but it isn't right now, so that's okay.
This is about the elimination part, and whether non-PRE should try to preserve CFG.

Chandler, your thoughts welcome on whether it's worth trying to preserve CFG in the case we don't do PRE

[• dberlin]

(also, many thanks for tackling this. :P)

[fhahn]

Ah

In D29252#659701, @dberlin wrote:

2. You can't insert unreachableinst except as a terminator.

Ah, I was wondering about that :)

[chandlerc]

In D29252#659701, @dberlin wrote:

Yeah, we discovered this yesterday.

The underlying issue is twofold

1. changeToUnreachable is supposed to be local, but modifies the CFG :(
2. You can't insert unreachableinst except as a terminator.

I'm torn here. Chandler's suggestion was to preserve the CFG. That will work, actually, right up until we add PRE.
Then we are going to split critical edges for sure.
(though we definitely miss some optimizations due to not splitting critical edges right now, it's just more common with PRE).

Current GVN does not preserve CFG.
If we want to preserve CFG, we should do a store of undef to null (which simplifycfg will transform into unreachable) and revert the original patch.

NewGVN is also an analysis with an elimination pass tacked on (and built so we can eventually split it up that way). The analysis should not modify the CFG for sure, but it isn't right now, so that's okay.
This is about the elimination part, and whether non-PRE should try to preserve CFG.

Chandler, your thoughts welcome on whether it's worth trying to preserve CFG in the case we don't do PRE

There is no fundamental reason you should preserve the CFG. The reason I suggest it whenever possible is only because it allows us to cache many more analyses. You can update domtree, but the number of analyses you get to preserve by preserving the CFG goes up *substantially* and you don't want to try to update all of them.

That said,, as long as this is one big pass, as you say, you'll want to split critical edges in part of it, etc. Don't stress about it in that context.

If you're going to split this, I think it is fairly likely that some reduced transformation passes will want to preserve the CFG so they can be relatively non-disruptive to analyses. Some use cases off the top of my head:

• GVNHoist style code motion seems likely to want to leave analyses in tact
• I'd love to have a fast, small LoopGVN that could be run in the middle of the loop pipeline to catch incremental improvements that allow subsequent loop passes to be more effective
• Some of the places we currently use EarlyCSE

Anyways, all of this seems pretty forward-looking, so I don't think it should necessarily decide what you do right now, just something to keep in mind as things progress. If there are easy ways to set the pass up for this long term, might be worthwhile.

[fhahn]

@davide should I abandon this review now you opened https://llvm.org/bugs/show_bug.cgi?id=31801 ?

[davide]

In D29252#660418, @fhahn wrote:

@davide should I abandon this review now you opened https://llvm.org/bugs/show_bug.cgi?id=31801 ?

No, I think something like this should go in anyway. PR30801 tracks a more general problem that will require time to be addressed properly.

[• dberlin]

For now i think we should revert the original change and insert the store, unless someone has evidence that doing something else produces actual performance improvement, instead of just looking nicer

We can always burn this bridge again when we come to it.

[fhahn]

Sure that sounds like the simpler fix. Go for it.

[davide]

An alternative version of this was committed, feel free to close whenever you want.

[davide]

An alternative version was committed. Resigning so this gets out of my queue.

[fhahn]

Already fixed.

lib/Transforms/Scalar/NewGVN.cpp

#endif
   // Delete all unreachable blocks.
   auto UnreachableBlockPred = [&](const BasicBlock &BB) {
     return !ReachableBlocks.count(&BB);
   };
 
   for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
     DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
                  << " is unreachable\n");
+    std::vector<BasicBlock *> OldSuccessors(succ_begin(&BB), succ_end(&BB));
+
     deleteInstructionsInBlock(&BB);
+
+    // Update immediate dominator of successors of BB, which have only a single
+    // predecessor after removing all instruction from BB.
+    for (auto *Succ : OldSuccessors) {
+      if (BasicBlock *OnlyPred = Succ->getSinglePredecessor()) {
+        if (DT->getNode(OnlyPred))
+          DT->changeImmediateDominator(Succ, OnlyPred);
+      }
+    }
     Changed = true;
   }
 
+  // Erase unreachable blocks from the dominator tree.
+  for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
+    DomTreeNode *DTN = DT->getNode(&BB);
+    if (!DTN)
+      continue;
+
+    // If BB has a predecessor in the CFG, we have to keep it in the dominator
+    //  tree.
+    if (pred_begin(&BB) != pred_end(&BB))
+      continue;
+
+    SmallVector<DomTreeNode *, 8> Children(DTN->begin(), DTN->end());
+    // Temporarily change the immediate dominator for all nodes immediately
+    // dominated by BB, so we can erase BB from the dominator tree. Those
+    // nodes should be unreachable as well and will be deleted in future
+    // iterations of the outer loop.
+    for (auto *DI : Children)
+      DT->changeImmediateDominator(DI, DT->getRootNode());
+
+    DT->eraseNode(&BB);
+  }
+
   cleanupTables();
   return Changed;
 }
 
 bool NewGVN::runOnFunction(Function &F) {
   if (skipFunction(F))
     return false;
   return runGVN(F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),

test/Transforms/NewGVN/2007-07-25-NestedLoop.ll

-; RUN: opt < %s -newgvn | llvm-dis
+; RUN: opt < %s -newgvn -verify-dom-info | llvm-dis
 
   %struct.TypHeader = type { i32, %struct.TypHeader**, [3 x i8], i8 }
 
 define %struct.TypHeader* @LtRec(%struct.TypHeader* %hdL, %struct.TypHeader* %hdR) {
 entry:
   br i1 false, label %bb556.preheader, label %bb534.preheader
 
 bb534.preheader:    ; preds = %entry

test/Transforms/NewGVN/2007-07-30-PredIDom.ll

-; RUN: opt < %s -newgvn | llvm-dis
+; RUN: opt < %s -newgvn -verify-dom-info | llvm-dis
 
   %"struct.Block::$_16" = type { i32 }
   %struct.Exp = type { %struct.Exp_*, i32, i32, i32, %struct.Exp*, %struct.Exp*, %"struct.Exp::$_10", %"struct.Block::$_16", %"struct.Exp::$_12" }
   %"struct.Exp::$_10" = type { %struct.Exp* }
   %"struct.Exp::$_12" = type { %struct.Exp** }
   %struct.Exp_ = type { i32, i32, i32, i32, %struct.Id* }
   %struct.Id = type { i8*, i32, i32, i32, %"struct.Id::$_13" }
   %"struct.Id::$_13" = type { double }

test/Transforms/NewGVN/cond_br.ll

-; RUN: opt -basicaa -newgvn -S < %s | FileCheck %s
+; RUN: opt -basicaa -newgvn -verify-dom-info -S < %s | FileCheck %s
 @y = external global i32
 @z = external global i32
 
 ; Function Attrs: nounwind ssp uwtable
 define void @foo(i32 %x) {
 ; CHECK: @foo(i32 %x)
 ; CHECK: %.pre = load i32, i32* @y
 ; CHECK: call void @bar(i32 %.pre)