[VPlan] Move VPBlockUtils to VPlanUtils.h (NFC)

Nothing in VPlan.h directly uses VPBlockUtils.h. Move it out to the more
appropriate VPlanUtils.h to reduce the size of the widely included VPlan.h.

[VPlan] Generalize collectUsersInExitBlocks for multiple exit bbs. (#115066)

Generalize collectUsersInExitBlock to collecting exit users in multiple
exit blocks. Exit blocks are leaf nodes in the V

[VPlan] Generalize collectUsersInExitBlocks for multiple exit bbs. (#115066)

Generalize collectUsersInExitBlock to collecting exit users in multiple
exit blocks. Exit blocks are leaf nodes in the VPlan (without
successors) except the scalar header.

Split off in preparation for
https://github.com/llvm/llvm-project/pull/112138

PR: https://github.com/llvm/llvm-project/pull/115066

show more ...

[VPlan] Remove unnecessary includes from VPlan.h (NFC).

Clean up some unnecessary includes from VPlan.h, which is imported in
multiple files.

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

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

This in turn enables using VPDo

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

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.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D140513

show more ...

[Dominators] Introduce DomTreeNodeTraits to allow customization. (NFC)

This patch introduces DomTreeNodeTraits for customization. Clients can implement
DomTreeNodeTraitsCustom to provide custom Pare

[Dominators] Introduce DomTreeNodeTraits to allow customization. (NFC)

This patch introduces DomTreeNodeTraits for customization. Clients can implement
DomTreeNodeTraitsCustom to provide custom ParentPtr, getEntryNode and getParent.
There's also a default specialization if DomTreeNodeTraitsCustom is not implemented,
that assume a Function-like NodeT. This is what is used for the existing DominatorTree
and MachineDominatorTree.

The main motivation for this patch is using DominatorTreeBase across all
regions of a VPlan, see D140513.

Reviewed By: kuhar

Differential Revision: https://reviews.llvm.org/D142162

show more ...

[VPlan] Add vp_depth_first_deep (NFC)

Similar to vp_depth_first_shallow (D140512) add vp_depth_first_deep to
make existing code clearer and more compact.

Reviewed By: Ayal

Differential Revision: h

[VPlan] Add vp_depth_first_deep (NFC)

Similar to vp_depth_first_shallow (D140512) add vp_depth_first_deep to
make existing code clearer and more compact.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D142055

show more ...

[VPlan] Add vp_depth_first_shallow + graph traits for wrapper(NFC)

This patch adds a new VPBlockShallowTraversalWrapper struct to
provide graph traits specialization that do not traverse through
VPR

[VPlan] Add vp_depth_first_shallow + graph traits for wrapper(NFC)

This patch adds a new VPBlockShallowTraversalWrapper struct to
provide graph traits specialization that do not traverse through
VPRegionBlocks. This matches the behavior of the existing traits for
plain VPBlockBase and is a step before moving the graph traits for
VPBlockBase to traverse through VPRegionBlocks to enable cross region
support in VPDominatorTree.

Depends on D140511.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D140512

show more ...

[VPlan] Disconnect VPRegionBlock from successors in graph iterator(NFCI)

This updates the VPAllSuccessorsIterator to not connect the
VPRegionBlock itself to its successors. The successors are connec

[VPlan] Disconnect VPRegionBlock from successors in graph iterator(NFCI)

This updates the VPAllSuccessorsIterator to not connect the
VPRegionBlock itself to its successors. The successors are connected to
the exit block of the region. At the moment, this doesn't change any
exisint functionality.

But the new schema ensures the following property when used for
VPDominatorTree:

1. Entry & exit blocks of regions dominate the successors of the region.

This allows for convenient checking of dominance between defs and uses
that are not defined in the same region. I will share a follow-up patch
to use it for the VPDominatorTree soon.

Depends on D140500.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D140511

show more ...

[VPlan] Remove unnecessary getNumSuccessors call (NFC).

If ParentWithSuccs is nullptr, the number of successors is guaranteed to
be 0. Simplify the code as suggested by @Ayal in D140511.

[VPlan] Move GraphTraits definitions to separate header (NFC).

This reduces the size of VPlan.h and avoids future growth of the file
when the graph traits are extended in future patches.

Reviewed B

[VPlan] Move GraphTraits definitions to separate header (NFC).

This reduces the size of VPlan.h and avoids future growth of the file
when the graph traits are extended in future patches.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D140500

show more ...