Page MenuHomePhabricator

[Dominators] Delete UpdateLevelsAfterInsertion in edge insertion of depth-based search for release builds
ClosedPublic

Authored by MaskRay on Feb 18 2019, 10:15 PM.

Details

Summary

After insertion of (From, To), v is affected iff
depth(NCD)+1 < depth(v) && path P from To to v exists where every w on P s.t. depth(v) <= depth(w)

All affected vertices change their idom to NCD.

If a vertex u has changed its depth, it must be a descendant of an
affected vertex v. Its depth must have been updated by UpdateLevel()
called by setIDom() of the first affected ancestor.

So UpdateLevelsAfterInsertion and its bookkeeping variable VisitedNotAffectedQueue are redundant.
Run them only in debug builds as a sanity check.

Diff Detail

Repository
rL LLVM

Event Timeline

MaskRay created this revision.Feb 18 2019, 10:15 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 18 2019, 10:15 PM
MaskRay updated this revision to Diff 187307.Feb 18 2019, 10:19 PM
MaskRay edited the summary of this revision. (Show Details)

Update description

kuhar accepted this revision.Feb 19 2019, 6:13 AM
This revision is now accepted and ready to land.Feb 19 2019, 6:13 AM
kuhar added a comment.Feb 19 2019, 6:32 AM

As a sanity check, to account for possible bugs somewhere else, have you tried adding an assertion ensuring that levels don't change in the function?

MaskRay updated this revision to Diff 187482.Feb 19 2019, 6:01 PM
MaskRay retitled this revision from [Dominators] Delete UpdateLevelsAfterInsertion used in edge insertion of depth-based search to [Dominators] Delete UpdateLevelsAfterInsertion in edge insertion of depth-based search for release builds.
MaskRay edited the summary of this revision. (Show Details)

assert TN->getLevel() == TN->getIDom()->getLevel()+1 in debug builds

This revision was automatically updated to reflect the committed changes.