This is an archive of the discontinued LLVM Phabricator instance.

[Dominators][AMDGPU] Don't use virtual exit node in findNearestCommonDominator. Cleanup MachinePostDominators.
ClosedPublic

Authored by kuhar on Sep 24 2019, 11:03 AM.

Details

Summary

This patch fixes a bug that originated from passing a virtual exit block (nullptr) to MachinePostDominatorTee::findNearestCommonDominator and resulted in assertion failures inside its callee. It also applies a small cleanup to the class.

The patch introduces a new function in PDT that given a list of MachineBasicBlocks finds their NCD. The new overload of findNearestCommonDominator handles virtual root correctly.

Note that similar handling of virtual root nodes is not necessary in (forward) DominatorTrees, as right now they don't use virtual roots.

Diff Detail

Repository
rL LLVM

Event Timeline

kuhar created this revision.Sep 24 2019, 11:03 AM
Herald added a project: Restricted Project. · View Herald Transcript
hliao added a subscriber: hliao.Sep 24 2019, 12:20 PM
hliao added inline comments.
llvm/lib/CodeGen/MachinePostDominators.cpp
59 ↗(On Diff #221562)

no need to (expensive) check every BB is not null. findNearestCommonDomniator asserts on both of them are non-null.

67 ↗(On Diff #221562)

the logic here is weird. if virtual root is the NCD, that means there's no real NCD. but, breaking here returns wrong NCD. need to return nullptr explicitly here

kuhar updated this revision to Diff 221575.Sep 24 2019, 12:34 PM
kuhar marked an inline comment as done.
kuhar edited the summary of this revision. (Show Details)

Small cleanup.

kuhar added inline comments.Sep 24 2019, 12:35 PM
llvm/lib/CodeGen/MachinePostDominators.cpp
59 ↗(On Diff #221562)

This should be a very quick scan over the vector of blocks, not more expensive than the inner check.
The intention was twofold:

  1. Document the blocks cannot be nullptr.
  2. Fail quickly where the contract is first violated.
67 ↗(On Diff #221562)

Virtual root is a real PDT node, but not a real basic block. The basic block value is nullptr and this is was will be returned.
I will update it to return nullptr explicitly, if that's easier to follow.

kuhar updated this revision to Diff 221582.Sep 24 2019, 1:32 PM
kuhar retitled this revision from [Dominators][AMDGPU] Don't use virtual exit node in findNearestCommonDominator to [Dominators][AMDGPU] Don't use virtual exit node in findNearestCommonDominator. Cleanup MachinePostDominators..
hliao requested changes to this revision.Sep 24 2019, 2:02 PM
hliao added inline comments.
llvm/lib/CodeGen/MachinePostDominators.cpp
53 ↗(On Diff #221582)

the assertion here is still redundant, as findNearestCommonDominator also asserts on both operands must not be null.

This revision now requires changes to proceed.Sep 24 2019, 2:02 PM
kuhar updated this revision to Diff 221596.Sep 24 2019, 2:07 PM
kuhar marked an inline comment as done.
hliao requested changes to this revision.Sep 24 2019, 2:09 PM
hliao added inline comments.
llvm/lib/CodeGen/MachinePostDominators.cpp
59 ↗(On Diff #221562)

assertions are added to capture abnormal behaviors. we don't need to check abnormal behaviors early and "quick".

This revision now requires changes to proceed.Sep 24 2019, 2:09 PM
kuhar marked an inline comment as done.Sep 24 2019, 2:12 PM
hliao accepted this revision.Sep 24 2019, 5:28 PM

LGTM

This revision is now accepted and ready to land.Sep 24 2019, 5:28 PM
kuhar updated this revision to Diff 221751.Sep 25 2019, 6:45 AM

Fix a typo.

This revision was automatically updated to reflect the committed changes.