This is an archive of the discontinued LLVM Phabricator instance.

[GlobalOpt] Remove unreachable blocks before optimizing a function
ClosedPublic

Authored by davide on Jul 5 2017, 12:25 PM.

Details

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.

Diff Detail

Event Timeline

davide created this revision.Jul 5 2017, 12:25 PM
davide edited the summary of this revision. (Show Details)

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

efriedma edited edge metadata.Jul 5 2017, 1:05 PM

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

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 added inline comments.Jul 5 2017, 1:44 PM
lib/Transforms/IPO/GlobalOpt.cpp
2038

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 added inline comments.Jul 5 2017, 2:04 PM
lib/Transforms/IPO/GlobalOpt.cpp
2038

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 this revision to Diff 105338.Jul 5 2017, 2:24 PM

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 accepted this revision.Jul 5 2017, 3:12 PM

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

This revision is now accepted and ready to land.Jul 5 2017, 3:12 PM
dberlin edited edge metadata.Jul 5 2017, 3:14 PM

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

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.

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

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

This revision was automatically updated to reflect the committed changes.
davide added a comment.Jul 5 2017, 3:30 PM
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

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 added a comment.Jul 7 2017, 2:11 PM

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