Page MenuHomePhabricator

Teach DTU to recalculate DT/PDT automatically when EntryBB is changed
Needs ReviewPublic

Authored by NutshellySima on Feb 13 2019, 8:56 AM.

Details

Summary

Previously, after the EntryBB is changed, due to restrictions of the DominatorTree, it is needed to call recalculate() explicitly.
This patch teaches DTU to detect the change of EntryBB when calling applyUpdates/insertEdge*/deleteEdge*/*deleteBB/getDT/getPDT/flush and recalculate available trees if it is needed, which makes DTU more friendly to use.

Diff Detail

Event Timeline

NutshellySima created this revision.Feb 13 2019, 8:56 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 13 2019, 8:56 AM

This is much cleaner, I like this very much. Originally adding the method recalculate() was a compromise. With this change do we even need the public recalculate()method? Does it ever make sense to make a new entry BB that has zero successors?

kuhar added a comment.Feb 13 2019, 9:07 AM

Seems like a nice improvement!

llvm/include/llvm/Analysis/DomTreeUpdater.h
245

Maybe NeedToRecalculate?

259

checkIfRootChanged?

264

internalRecalculate

llvm/include/llvm/Support/GenericDomTree.h
252

Why do we need this? maybe it would be better to expose/use some other function? Tree root can be accessed with the getRoots function.

kuhar added a comment.Feb 13 2019, 9:09 AM

I believe that a real fix would be to always create a virtual root in DomTree and support fast rerooting, but that requires much more implementation and testing effort.

This is much cleaner, I like this very much. Originally adding the method recalculate() was a compromise. With this change do we even need the public recalculate()method? Does it ever make sense to make a new entry BB that has zero successors?

recalculate() can be deprecated. But there are still edge cases, for example, when we only insert a new block to be the entry block or move a block up to be the entry block, it is still needed to call flush() to detect this change. (But I don't see usage like the above scenario I mentioned currently.)

recalculate() can be deprecated. But there are still edge cases, for example, when we only insert a new block to be the entry block or move a block up to be the entry block, it is still needed to call flush() to detect this change. (But I don't see usage like the above scenario I mentioned currently.)

If there are still edge cases then we need to keep it as a last-ditch method of resetting the DTU state without creating a new class instance. It might be a good idea to add documentation stating the interface isn't meant to be used except as a last-ditch fix that cannot be addressed by any other means.

mkazantsev added inline comments.Feb 14 2019, 10:09 PM
llvm/include/llvm/Analysis/DomTreeUpdater.h
257

Should we do it for PDT when exit block is changed?

kuhar added inline comments.Feb 14 2019, 10:19 PM
llvm/include/llvm/Analysis/DomTreeUpdater.h
257

PDT's root never changes -- we use a virtual exit node to support multiple exits. DT should be handled in the same way IMO, but that's a lot of work.

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