Page MenuHomePhabricator

WIP! [CFG] Create a new removeUnreachable utility that updates the dom in place
Needs ReviewPublic

Authored by davide on Jul 7 2017, 2:08 PM.

Details

Summary

This implements the algorithm suggested in https://reviews.llvm.org/D35028#800177 with a slight variation/implementation detail. We could have BBs which don't have corresponding nodes in the dominator, so we need to handle that case as well. We also need an additional worklist for the dead block to avoid iterator invalidation issues (or at least, this was the easiest way I could think how to solve this problem).
This is WIP for two reasons:

  1. I want the utility to have a better name for the utility [but I need to think about it, suggestions welcome]
  2. I want to test it a little more. It passes the testsuite & bootstrap, but I'll try on something else I have available internally.

Diff Detail

Event Timeline

davide created this revision.Jul 7 2017, 2:08 PM
dberlin added inline comments.Jul 9 2017, 8:32 AM
lib/Transforms/Utils/Local.cpp
1711

Note that if the dom tree is up to date, it would suffice to do:

for (auto *BB : nodes(DT))

Live.insert(BB->getBlock())

or whatever

But IIRC, in your case, the dominator tree is *not* up to date, right?

davide added inline comments.Jul 9 2017, 9:43 AM
lib/Transforms/Utils/Local.cpp
1711

I guess we could introduce this invariant, if the caller passes a Dom that's always up-to-date? (otherwise, realistically, there's little point in trying to update an already stale dominator).

kuhar added inline comments.Jul 9 2017, 5:05 PM
lib/Transforms/Utils/Local.cpp
1716

Isn't the size known to be F.size() - Live.size() at this point? Worklist could start with this capacity.

efriedma added inline comments.Jul 10 2017, 4:24 PM
lib/Transforms/Utils/Local.cpp
1727

I'm pretty sure N is always null here if the domtree is up-to-date.

1730

The dropAllReferences call is redundant; the destructor for BasicBlock calls it for you.

An unreachable block can have reachable successors; you need to use removePredecessor to fix them up properly.

kuhar resigned from this revision.Sep 30 2019, 9:49 AM