This is an archive of the discontinued LLVM Phabricator instance.

[VPlan] Add GraphTraits impl to traverse through VPRegionBlock.

Authored by fhahn on Apr 9 2021, 4:00 AM.



This patch adds a new iterator to traverse through VPRegionBlocks and a
GraphTraits specialization using the iterator to traverse through

Because there is already a GraphTraits specialization for VPBlockBase *
and co, a new VPBlockRecursiveTraversalWrapper helper is introduced.
This allows us to provide a new GraphTraits specialization for that
type. Users can use the new recursive traversal by using this wrapper.

The graph trait visits both the entry block of a region, as well as all
its successors. Exit blocks of a region implicitly have their parent
region's successors. This ensures all blocks in a region are visited
before any blocks in a successor region when doing a reverse post-order
traversal of the graph.

Diff Detail

Event Timeline

fhahn created this revision.Apr 9 2021, 4:00 AM
fhahn requested review of this revision.Apr 9 2021, 4:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 9 2021, 4:00 AM
Herald added a subscriber: vkmr. · View Herald Transcript
a.elovikov added inline comments.Apr 12 2021, 11:26 AM

IMO, having a work "successors" in the name would help in understanding the logic behind this. I've caught myself on a though that at some point reading the code below I've forgotten that we only go through the "successors" of a a block and not through the whole graph.


I'd probably spell it as

`BlockTy const Block`


`BlockTy * const Block`

Can we rename it to SuccessorIdx? Do I understand the purpose of the field correctly?


What if the block's parent is a region that is an exit as well? Shouldn't we recursively go up the chain of such exits? Same throughout other methods (e.g. end).


I'd prefer to use const_cast magic here, instead of duplicating the code.


Wow, that is nice. I was only aware of the approach with named traits and then defining helper function to pass that trait explicitly to traversal. Your approach is much clearer.



llvm::copy(depth_first(...), std::back_inserter(FromIterator));

Can you please add an ASCII graph drawing here similar to the one above?


Can we either modify this test or add another one with some non-linear CFG inside R2?


nit: I think llvm::copy or outlining the region into a temporary auto variable would help with readability here.

a.elovikov added inline comments.Apr 12 2021, 11:30 AM

Would it be possible to pass just const VPBlockBase * here? Is the argument here what is usually defined as using GraphType = <something>?

fhahn updated this revision to Diff 337831.Apr 15 2021, 10:53 AM
fhahn marked 5 inline comments as done.

Addressed comments, thanks!


I changed the name to VPAllSuccessorsIterator. WDY?


Unfortunately it looks like the RPOT helpers uses std::copy, which requires the assignment operator, which is not compatible with making Block const, but I may be missing some workaround?


Yep, that's not handled properly at the moment! I also realized that the case where the region is the last block in the graph was not handled properly, as we would not enter the region itself. Both issues should be fixed now.


Using const_cast did not seem to work well with the graph traits, so I added a templated version. WDYT?


I think this needs to match the type GraphTraits is defined for. Otherwise this cannot be used directly with the wrapper object and it may cause additional problems because there's a GraphTraits specialization for const VPBlockBase *.


I added another block and a cycle.


I simplified and unified the construction.

I think it's functionally correct now, just have a few suggestions to simplify the code a little bit.

Thanks for the updates!


Strictly speaking, returning Current isn't returning any parents

Maybe rename to getBlockWithSuccs?


I don't understand the purpose of T1 here yet. I'll continue reading assuming

template <typename T>
static auto deref(T *Ptr)

nit: Ptr->Block is used three times, might be beneficial to outline to a variable with explicit type (VPBlockBase?)


I think doing this unconditionally would just work. The current implementation of getFirstParentWithSuccs returns Ptr->block if it has successors.


That would work, but please add the comment near the templated version what this template paramter is used for (to support const/non-const versions). I assume it would be the deref function, right?


I think it should be just ParentWithSuccs ? ParentWithSuccs->getNumSuccessors() : 0 after implementing the suggestion above about renaming the method.

fhahn updated this revision to Diff 339670.Apr 22 2021, 9:07 AM
fhahn marked 3 inline comments as done.

Address comments, thanks!

fhahn updated this revision to Diff 339671.Apr 22 2021, 9:09 AM
fhahn marked an inline comment as done.

Remove unneeded explicit types when calling deref.


Thanks, I updated the name as suggested.


I think this was needed to make things build, because otherwise Clang failed to determine the correct return type of the function. But I updated the code now to pass the block and index in directly, requiring only one template argument.


Block is passed in directly now, so the template can be simplified.

a.elovikov accepted this revision.Apr 22 2021, 9:20 AM

LGTM, thanks!

This revision is now accepted and ready to land.Apr 22 2021, 9:20 AM
This revision was landed with ongoing or failed builds.Apr 23 2021, 9:27 AM
This revision was automatically updated to reflect the committed changes.

LGTM, thanks!

Thank you very much for taking a look!