[GlobalOpt] Remove unreachable blocks before optimizing a function

[davide]

Summary

LLVM's definition of dominance allows instructions that are cyclic in unreachable blocks, e.g.:

%pat = select i1 %condition, @global, i16* %pat

because any instruction dominates an instruction in a block that's not reachable from entry.
So, remove unreachable blocks from the function, because a) there's no point in analyzing them and b) GlobalOpt should otherwise grow some more complicated logic to break these cycles.

Couple of notes:

1. This test is clearly generated by a fuzzer, so it might not show up in a real world pipeline (where I think we might run GlobalDCE before GlobalOpt).
2. I wasn't able to measure an increase in compile time after this change, when e.g. self-hosting clang with LTO & with some internal benchmarks.

[davide]

Updated revision description (phab doesn't seem to send a new mail for that).

[efriedma]

It looks like analyzeGlobal might need some sort of protection against visiting an instruction twice anyway? Without unreachable code, you can't end up in an infinite loop, but you could still visit an instruction many times.

lib/Transforms/IPO/GlobalOpt.cpp

2038 ↗

(On Diff #105316)

I think you need to do something to preserve the domtree here. (Either that, or move this earlier so it never runs after we access the domtree.)

[davide]

lib/Transforms/IPO/GlobalOpt.cpp

2038 ↗

(On Diff #105316)

I thought about this for a bit, and, maybe I'm tilting at windmills here.
Is it enough to move this code earlier in the function (maybe at the beginning of optimizeGlobalsInModule ?)

e.g.

• we have a cached dominator tree and we call removeUnreachableBlocks before accessing the dominator
• after the blocks are removed we call LookupDomTree and we get back a stale dominator unless we invalidate it explicitly (and we should do that only if removeUnreachableBlocks actually removed something)?

If my understanding is incorrect, please forgive me :)

[efriedma]

lib/Transforms/IPO/GlobalOpt.cpp

2038 ↗

(On Diff #105316)

That description looks essentially correct.

Looking a bit more, I don't think you can solve this by just moving the code to the beginning of optimizeGlobalsInModule; it looks like LookupDomTree actually uses DominatorTreeWrapperPass/DominatorTreeAnalysis, so it returns a domtree computed by an earlier pass.

Should be sufficient to just recompute the domtree if removeUnreachableBlocks makes changes. (Might be possible to optimize this, but not easily; removeUnreachableBlocks can actually change the dominators for reachable code.)

[davide]

Updated after Eli's feedback. I'll change analyzeGlobals to not revisit instructions as a follow up if you're okay with it.
Thanks for taking the time to review this change.

[efriedma]

LGTM. (I don't really like calling recalculate, but it's the best alternative available here at the moment.)

[• dberlin]

Yeah, this is a very clear case where we should make removeUnreachableBlocks use the new incremental API, and declare victory.

[• dberlin]

Actually, thinking about this more, i'm confused.

removeUnreachableBlocks does silly things (it computes liveness and blah blah blah blah) and modifies the CFG, but those silly things are irrelevant to the problem here.

The following should suffice to fix these bugs without explicitly recalculating the dom tree:

Walk blocks using  RPO iterator, put them in Live set

For each block in function not in Live:
  if (Processed.count(X)) skip it.

  for X in depth_first (DT->getNode(block)):
       Processed.insert(X)
        for (BasicBlock *Successor : successors(X))
          Successor->removePredecessor(X);
        if (LVI)
          LVI->eraseBlock(X);
        DT->eraseBlock(DT->getNode(X))
        X->dropAllReferences();
        X->eraseFromParent();

You have to erase the blocks in the dom tree leaves first.

Otherwise, this is just "find forward unreachable blocks, delete them" (the code is from removeUnreachableBlocks)

By definition, any block dominated by an unreachable block is also forward unreachable, so we just process them as part of the depth first walk.

[• dberlin]

In D35028#800177, @dberlin wrote:

for X in depth_first (DT->getNode(block)):

the depth_first here should be post_order, i forgot depth_first is preorder

[davide]

In D35028#800178, @dberlin wrote:

In D35028#800177, @dberlin wrote:

for X in depth_first (DT->getNode(block)):

the depth_first here should be post_order, i forgot depth_first is preorder

Flip, I literally committed this at the same time you posted the new version :)
I'll work on a new version and submit a new patch

[efriedma]

I guess we could add removeUnreachableBlocksAndDontDoAnythingElse() which only erases stuff which isn't reachable from the entry block, and doesn't do the other stuff removeUnreachableBlocks() does, sure. Updating the domtree in that case is trivial because unreachable blocks don't have domtree nodes in the first place.

[davide]

In D35028#800177, @dberlin wrote:

Actually, thinking about this more, i'm confused.

removeUnreachableBlocks does silly things (it computes liveness and blah blah blah blah) and modifies the CFG, but those silly things are irrelevant to the problem here.

The following should suffice to fix these bugs without explicitly recalculating the dom tree:

Walk blocks using  RPO iterator, put them in Live set

For each block in function not in Live:
  if (Processed.count(X)) skip it.

  for X in depth_first (DT->getNode(block)):
       Processed.insert(X)
        for (BasicBlock *Successor : successors(X))
          Successor->removePredecessor(X);
        if (LVI)
          LVI->eraseBlock(X);
        DT->eraseBlock(DT->getNode(X))
        X->dropAllReferences();
        X->eraseFromParent();

You have to erase the blocks in the dom tree leaves first.

Otherwise, this is just "find forward unreachable blocks, delete them" (the code is from removeUnreachableBlocks)

By definition, any block dominated by an unreachable block is also forward unreachable, so we just process them as part of the depth first walk.

This is https://reviews.llvm.org/D35142

llvm/trunk/lib/Transforms/IPO/GlobalOpt.cpp

for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
     if (!F->hasName() && !F->isDeclaration() && !F->hasLocalLinkage())
       F->setLinkage(GlobalValue::InternalLinkage);
 
     if (deleteIfDead(*F, NotDiscardableComdats)) {
       Changed = true;
       continue;
     }
 
+    // LLVM's definition of dominance allows instructions that are cyclic
+    // in unreachable blocks, e.g.:
+    // %pat = select i1 %condition, @global, i16* %pat
+    // because any instruction dominates an instruction in a block that's
+    // not reachable from entry.
+    // So, remove unreachable blocks from the function, because a) there's
+    // no point in analyzing them and b) GlobalOpt should otherwise grow
+    // some more complicated logic to break these cycles.
+    // Removing unreachable blocks might invalidate the dominator so we
+    // recalculate it.
+    if (!F->isDeclaration()) {
+      if (removeUnreachableBlocks(*F)) {
+        auto &DT = LookupDomTree(*F);
+        DT.recalculate(*F);
+        Changed = true;
+      }
+    }
+
     Changed |= processGlobal(*F, TLI, LookupDomTree);
 
     if (!F->hasLocalLinkage())
       continue;
     if (isProfitableToMakeFastCC(F) && !F->isVarArg() &&
         !F->hasAddressTaken()) {
       // If this function has a calling convention worth changing, is not a
       // varargs function, and is only called directly, promote it to use the

llvm/trunk/test/Transforms/GlobalOpt/pr33686.ll

+; RUN: opt -S -globalopt %s | FileCheck %s
+
+; CHECK-LABEL: define void @beth
+; CHECK-NEXT:   entry:
+; CHECK-NEXT:   ret void
+; CHEC-NEXT:  }
+
+@glob = external global i16, align 1
+
+define void @beth() {
+entry:
+  ret void
+
+notreachable:
+  %patatino = select i1 undef, i16* @glob, i16* %patatino
+  br label %notreachable
+}