Page MenuHomePhabricator

[Dominators] Introduce batch updates
ClosedPublic

Authored by kuhar on Aug 1 2017, 12:22 PM.

Details

Summary

This patch introduces a way of informing the (Post)DominatorTree about multiple CFG updates that happened since the last tree update. This makes performing tree updates much easier, as it internally takes care of applying the updates in lockstep with the (virtual) updates to the CFG, which is done by reverse-applying future CFG updates.

The batch updater is able to remove redundant updates that cancel each other out. In the future, it should be also possible to reorder updates to reduce the amount of work needed to perform the updates.

Diff Detail

Event Timeline

kuhar created this revision.Aug 1 2017, 12:22 PM
brzycki accepted this revision.Aug 3 2017, 8:25 AM

The work I am doing to preserve dominance over JumpThreading.cpp and Local.cpp will directly benefit from this new interface. When inserting/removing conditional branch or invoke terminators the only valid option was to perform DT->recalculate(*F) which is expensive. In the case of conditional branches this is also fairly frequent. Being able to queue both insertions and deletions also minimizes the fixup calls.

Kuba, I saw your comments saying the new interface is, in general, more efficient to apply a single batch update vs Insert/Delete. Is it worth the effort for callers to *not* call .applyUpdates() when we know our vector is of size = 1?

include/llvm/Support/GenericDomTreeConstruction.h
83

"using them to gets us" is confusing and grammatically incorrect. I think you meant to say something like "using them gets us a partial snapshot of the..."

This revision is now accepted and ready to land.Aug 3 2017, 8:25 AM
kuhar added a comment.Aug 3 2017, 8:31 AM

Kuba, I saw your comments saying the new interface is, in general, more efficient to apply a single batch update vs Insert/Delete. Is it worth the effort for callers to *not* call .applyUpdates() when we know our vector is of size = 1?

In that case, the batch updater would do a fair bit of set up work, so I'd recommend calling insert/deleteEdge directly. It should be possible to make this a special case in the batch updater, but I'm not sure if that'd make a real-world difference anywhere.

kuhar updated this revision to Diff 110511.Aug 9 2017, 5:24 PM

Fix a bug with not hiding duplicate children.
Rebase the patch to ToT.

This revision was automatically updated to reflect the committed changes.