This is an archive of the discontinued LLVM Phabricator instance.

[VPlan] Switch default graph traits to be recursive, update VPDomTree.
ClosedPublic

Authored by fhahn on Dec 21 2022, 3:27 PM.

Details

Summary

This updates the GraphTraits specialization for VPBlockBase to recurse
through VPRegionBlocks.

This in turn enables using VPDominatorTree to query dominance between
any block in a plan. This should enable additional use cases, including
improvements to def-use verification and porting IR-based transforms
that rely on the dominator tree.

Specifically, this change means that for regions, the entry and exit
blocks dominate the successors of the region.

Depends on D140512 and D142162.

Diff Detail

Event Timeline

fhahn created this revision.Dec 21 2022, 3:27 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 21 2022, 3:27 PM
fhahn requested review of this revision.Dec 21 2022, 3:27 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 21 2022, 3:27 PM
fhahn updated this revision to Diff 487316.Jan 9 2023, 12:52 AM

Add VPDominatorTree::getParent specialization, add tests for findNearestCommonDominator.

Ayal added inline comments.Jan 18 2023, 5:21 AM
llvm/lib/Transforms/Vectorize/VPlan.h
451

who's using ParentPtrTy? Parent itself is still a VPRegionBase*...

2119

Is the above FIXME related to the current changes which include front below, and/or a good time to address?

llvm/lib/Transforms/Vectorize/VPlanCFG.h
63

who's using this reference?

263

Should this inverse use something like VPAllPredecessorsIterator?

Would be good to test the order of an inverse iterator.

274

GraphTraits for Regions removed as no longer needed?

279

commented-out code to be removed?

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp
63

nit: ascii art at the ends of the two lines above which represent a cycle, may look better using

     __
 \  /  \
R1BB3   |
 /  \__/

where all incoming edges appear on top and all outgoing edges appear on bottom.

(A cycle deserves a region, here and below. When all loop back arcs are captured inside loop regions the HCFG is a (hierarchical) DAG)

72

nit: // }

111

Also
EXPECT_TRUE(VPDT.dominates(R1BB4, R2BB1));
EXPECT_FALSE(VPDT.dominates(R1BB3, R2BB1));
?

161

Here's a good place to build a dominator tree and check its edges?

fhahn updated this revision to Diff 490303.Jan 18 2023, 2:48 PM
fhahn marked 10 inline comments as done.

Address comments, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h
451

This is a workaround for the issue that the dominator tree base classes rely on NodeT::getParent() to return a container type that all nodes share, like Function for basic blocks.

But for VPBlockBase it returns the parent region which may be nullptr. To have a DT spanning all regions in a plan, the parent needs to be VPlan.

There probably are other options to address this, D141260 is just a relatively simple/non-invasive way to get things to build and work. Now that we seem to be converging on cross region DTs, we should iron out the workaround as well

2119

Yes, it might be good to address this FIXME now. I'll look into it.

llvm/lib/Transforms/Vectorize/VPlanCFG.h
63

It is used by iterator_facade_base with bidirectional_iterator_tag

263

I think the inverse is only needed for DT updates and post-dominators. We don't use either at the moment, I updated all implementations here to use llvm_unreachable and added a TODO. But it should not be needed for DT functionality we need to get started.

274

Yep

279

removed, thanks!

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp
63

Improved the ASCII art, thanks!

(A cycle deserves a region, here and below. When all loop back arcs are captured inside loop regions the HCFG is a (hierarchical) DAG)

The intention of the test is to make sure cycles in the graph are handled. We could forbid explicit cycles in the verifier though?

72

Updated, thanks!

111

added, thanks!

161

Updated code here to check the immediate dominators, which is more compact. I retained the dominance checks above.

Ayal accepted this revision.Jan 19 2023, 5:50 AM

Looks good to me, with a few minor nits.

llvm/lib/Transforms/Vectorize/VPlan.h
451

OK, worth leaving behind a comment?

llvm/lib/Transforms/Vectorize/VPlanCFG.h
63

OK, worth a comment?

263

Very well.

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp
61

nit: this also checks the children order, in addition to dominance relation.

63

Currently cycles should be captured in regions so that, e.g., VPRegionBlock::execute() would allocate loops, and this is arguably the approach going forward. So it would probably be better to forbid explicit cycles for now.

This revision is now accepted and ready to land.Jan 19 2023, 5:50 AM
fhahn marked 4 inline comments as done.Jan 20 2023, 7:36 AM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/VPlan.h
451

This has been removed in the latest version based on D142162

llvm/lib/Transforms/Vectorize/VPlanCFG.h
63

Added, thanks!

263

I missed uploading the part, should be fixed. in the latest version.

llvm/unittests/Transforms/Vectorize/VPDomTreeTest.cpp
63

Sounds good, I can prepare a follow-up.

fhahn updated this revision to Diff 490850.Jan 20 2023, 7:38 AM
fhahn marked 4 inline comments as done.

Rebased on top of D142162 and added comment, thanks!

fhahn edited the summary of this revision. (Show Details)Jan 20 2023, 7:39 AM
fhahn updated this revision to Diff 490885.Jan 20 2023, 8:49 AM

Rebased again after changes to D142162.

fhahn updated this revision to Diff 491301.Jan 23 2023, 4:13 AM

Rebase before landing

This revision was landed with ongoing or failed builds.Jan 23 2023, 6:01 AM
This revision was automatically updated to reflect the committed changes.