[VPlan] Support multi-exit loops in HCFG builder.

Update HCFG construction to support multi-exit loops. If there is no
unique exit block, map the middle block of the initial plan to the exit
block f

[VPlan] Support multi-exit loops in HCFG builder.

Update HCFG construction to support multi-exit loops. If there is no
unique exit block, map the middle block of the initial plan to the exit
block from the latch.

This further unifies HCFG construction and prepares for use to also
build an initial VPlan (VPlan0) for inner loops.

Effectively NFC as this isn't used on the default code path yet.

show more ...

[VPlan] Refactor HCFG builder to preserve original vector latch (NFC).

Update HCFG builder to preserve the original latch block of the initial
VPlan, ensuring there is always a latch.

It also skips

[VPlan] Refactor HCFG builder to preserve original vector latch (NFC).

Update HCFG builder to preserve the original latch block of the initial
VPlan, ensuring there is always a latch.

It also skips creating the BranchOnCond for the latch of the top-level
loop, instead of removing it later. Exiting via the latch is controlled
by later recipes.

This further unifies HCFG construction and prepares for use to also
build an initial VPlan (VPlan0) for inner loops.

show more ...

[LV] Align debug location of the widen-phi to the original phi. (#120338)

This patch align the debug location of the widen-phi to the debug
location of original phi.

Split from: #120054

[VPlan] Manage created blocks directly in VPlan. (NFC) (#120918)

This patch changes the way blocks are managed by VPlan. Previously all
blocks reachable from entry would be cleaned up when a VPlan

[VPlan] Manage created blocks directly in VPlan. (NFC) (#120918)

This patch changes the way blocks are managed by VPlan. Previously all
blocks reachable from entry would be cleaned up when a VPlan is
destroyed. With this patch, each VPlan keeps track of blocks created for
it in a list and this list is then used to delete all blocks in the list
when the VPlan is destroyed. To do so, block creation is funneled
through helpers in directly in VPlan.

The main advantage of doing so is it simplifies CFG transformations, as
those do not have to take care of deleting any blocks, just adjusting
the CFG. This helps to simplify
https://github.com/llvm/llvm-project/pull/108378 and
https://github.com/llvm/llvm-project/pull/106748.

This also simplifies handling of 'immutable' blocks a VPlan holds
references to, which at the moment only include the scalar header block.

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

show more ...

[VPlan] Update HCFG builder after 72937203dd3b to fix leak.

Update buildPlainCFG to re-use the vector and latch VPBBs created as
part of the initial skeleton in 72937203dd3b.

This should fix the le

[VPlan] Update HCFG builder after 72937203dd3b to fix leak.

Update buildPlainCFG to re-use the vector and latch VPBBs created as
part of the initial skeleton in 72937203dd3b.

This should fix the leak sanitizer failure discovered by
https://lab.llvm.org/buildbot/#/builders/52/builds/619.

show more ...

[VPlan] Rename getVPValueOrAddLiveIn -> getOrAddLiveIn (NFCI).

The helper now only deals with live-ins, clarify the name.

[VPlan] Use VPBuilder to create BranchOnCond in VPHCFGBuilder.

This simplifies the code to create the recipe slightly as well as
properly retaining the debug location of the input IR.

[VPlan] Merge main VPlan verifer with HCFG verifier.

Unify VPlan verifiers in verifyVPlanIsValid. This adds verification for
various properties on blocks to the verifier used for VPlans generated
by

[VPlan] Merge main VPlan verifer with HCFG verifier.

Unify VPlan verifiers in verifyVPlanIsValid. This adds verification for
various properties on blocks to the verifier used for VPlans generated
by the inner loop vectorizer. It also adds def-use checks for the
verifier used in the VPlan native path.

This drops the separate flag to enable HCFG verification. Instead, all
VPlans are verified once they have been created, if assertions are
enabled.

This also removes VPWidenPHIRecipe from VPHeaderPHIRecipe; it is used to
model any phi node in the native path.

show more ...

[LV] Skipping all debug instructions when native vplan is enabled (#77413)

The following internal error occurred when using native vplan to
vectorize the program with the debug info generation.

[LV] Skipping all debug instructions when native vplan is enabled (#77413)

The following internal error occurred when using native vplan to
vectorize the program with the debug info generation.

Assertion `!isa<DbgInfoIntrinsic>(CI) && "DbgInfoIntrinsic should have been dropped during VPlan construction"' failed.

This patch ignored all debug instructions to fix the error when native
vplan is enabled.

show more ...

[LV] Stability fix for outerloop vectorization (#68118)

HCFG builder doesn't correctly handle cases when non-outermost loop is
requested to be vectorized

[Original] Differential Revision: https:

[LV] Stability fix for outerloop vectorization (#68118)

HCFG builder doesn't correctly handle cases when non-outermost loop is
requested to be vectorized

[Original] Differential Revision: https://reviews.llvm.org/D150700

show more ...

[VPlan] Move initial skeleton construction to createInitialVPlan. (NFC)

This patch moves creating the middle VPBBs and an initial empty
vector loop region for the top-level loop to createInitialVPl

[VPlan] Move initial skeleton construction to createInitialVPlan. (NFC)

This patch moves creating the middle VPBBs and an initial empty
vector loop region for the top-level loop to createInitialVPlan.

This consolidates code to create the initial VPlan skeleton and enables
adding other bits outside the main region during initial VPlan
construction. In particular, D150398 will add the exit check & branch to
the middle block.

Reviewed By: Ayal

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

show more ...

[VPlan] Simplify HCFG construction of region blocks (NFC).

Update the logic to update the successors and predecessors of region
blocks directly. This adds special handling for header and latch block

[VPlan] Simplify HCFG construction of region blocks (NFC).

Update the logic to update the successors and predecessors of region
blocks directly. This adds special handling for header and latch blocks
in place, and removes the separate loop to fix up the region blocks.

Helps to simplify D158333.

Reviewed By: Ayal

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

show more ...

[VPlan] Ensure start value of phis is the first op at construction (NFC)

Header phi recipes have the start value (incoming from outside the loop)
as first operand. This wasn't the case for VPWidenPH

[VPlan] Ensure start value of phis is the first op at construction (NFC)

Header phi recipes have the start value (incoming from outside the loop)
as first operand. This wasn't the case for VPWidenPHIRecipes. Instead
the start value was picked during execute() by doing extra work.

To be in line with other recipes, ensure the operand order is as
expected during construction.

show more ...

[llvm] Fix duplicate word typos. NFC

Those fixes were taken from https://reviews.llvm.org/D137338

[VPlan] Remove setEntry to avoid leaks when replacing entry.

Update the HCFG builder to directly connect the created CFG to the
existing Plan's entry. This allows removing `setEntry`, which can caus

[VPlan] Remove setEntry to avoid leaks when replacing entry.

Update the HCFG builder to directly connect the created CFG to the
existing Plan's entry. This allows removing `setEntry`, which can cause
leaks when the existing entry is replaced.

Should fix
https://lab.llvm.org/buildbot/#/builders/5/builds/33455/steps/13/logs/stdio

show more ...

Recommit "[VPlan] Unify Value2VPValue and VPExternalDefs maps (NFCI)."

This reverts the revert commit 8c2276f89887d0a27298a1bbbd2181fa54bbb509.

The updated patch re-orders the getDefiningRecipe che

Recommit "[VPlan] Unify Value2VPValue and VPExternalDefs maps (NFCI)."

This reverts the revert commit 8c2276f89887d0a27298a1bbbd2181fa54bbb509.

The updated patch re-orders the getDefiningRecipe check in getVPalue to avoid
a use-after-free.

Original commit message:

Before this patch, a VPlan contained 2 mappings for Values -> VPValue:
1) Value2VPValue and 2) VPExternalDefs.

This duplication is unnecessary and there are already cases where
external defs are added to Value2VPValue. This patch replaces all uses
of VPExternalDefs with Value2VPValue.

It clarifies the naming of getOrAddVPValue (to getOrAddExternalVPValue)
and addVPValue (to addExternalVPValue).

At the moment, this is NFC, but will enable additional simplifications
in D147783.

Depends on D147891.

Reviewed By: Ayal

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

show more ...

Revert "[VPlan] Unify Value2VPValue and VPExternalDefs maps (NFCI)."

Asan detects heap-use-after-free, see D147892.

This reverts commit 4fc190351e5af901b6107d162d07e1fbca90934f.
This reverts commit

Revert "[VPlan] Unify Value2VPValue and VPExternalDefs maps (NFCI)."

Asan detects heap-use-after-free, see D147892.

This reverts commit 4fc190351e5af901b6107d162d07e1fbca90934f.
This reverts commit 668045eb77628be13e448ffbb855473ffca1cc43.

show more ...

[VPlan] Unify Value2VPValue and VPExternalDefs maps (NFCI).

Before this patch, a VPlan contained 2 mappings for Values -> VPValue:
1) Value2VPValue and 2) VPExternalDefs.

This duplication is unnece

[VPlan] Unify Value2VPValue and VPExternalDefs maps (NFCI).

Before this patch, a VPlan contained 2 mappings for Values -> VPValue:
1) Value2VPValue and 2) VPExternalDefs.

This duplication is unnecessary and there are already cases where
external defs are added to Value2VPValue. This patch replaces all uses
of VPExternalDefs with Value2VPValue.

It clarifies the naming of getOrAddVPValue (to getOrAddExternalVPValue)
and addVPValue (to addExternalVPValue).

At the moment, this is NFC, but will enable additional simplifications
in D147783.

Depends on D147891.

Reviewed By: Ayal

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

show more ...

[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 ...

[Transforms] Fix comment typos (NFC)

[VPlan] Inline variable into assertion. NFC.

Avoids a warning in release builds
llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp:311:14: warning: unused variable 'BrCond' [-Wunused-variable]

[VPlan] Inline variable into assertion. NFC.

Avoids a warning in release builds
llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp:311:14: warning: unused variable 'BrCond' [-Wunused-variable]
Value *BrCond = Br->getCondition();

show more ...

[VPlan] Replace CondBit with BranchOnCond VPInstruction.

This patch removes CondBit and Predicate from VPBasicBlock. To do so,
the patch introduces a new branch-on-cond VPInstruction opcode to model

[VPlan] Replace CondBit with BranchOnCond VPInstruction.

This patch removes CondBit and Predicate from VPBasicBlock. To do so,
the patch introduces a new branch-on-cond VPInstruction opcode to model
a branch on a condition explicitly.

This addresses a long-standing TODO/FIXME that blocks shouldn't be users
of VPValues. Those extra users can cause issues for VPValue-based
analyses that don't expect blocks. Addressing this fixme should allow us
to re-introduce 266ea446ab7476.

The generic branch opcode can also be used in follow-up patches.

Depends on D123005.

Reviewed By: Ayal

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

show more ...

[VPlan] Use region for each loop in native path.

This patch updates the VPlan native path to use VPRegionBlocks for all
loops in a loop nest. Up to now, only the outermost loop used a region.

This

[VPlan] Use region for each loop in native path.

This patch updates the VPlan native path to use VPRegionBlocks for all
loops in a loop nest. Up to now, only the outermost loop used a region.

This is a step towards unifying both paths and keep things consistent
between them. It also prepares various code-gen parts for modeling the
pre-header in the inner loop vectorizer (D121624).

Reviewed By: Ayal

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

show more ...

[VPlan] Remove unused native utilities incompatible with nested regions.

The implementations of VPlanDominatorTree, VPlanLoopInfo and VPlanPredicator
are all incompatible with modeling loops in VPla

[VPlan] Remove unused native utilities incompatible with nested regions.

The implementations of VPlanDominatorTree, VPlanLoopInfo and VPlanPredicator
are all incompatible with modeling loops in VPlans as region without
explicit back-edges.

Those pieces are not actively used and only exercised by a few gtest
unit tests. They are at the moment blocking progress towards unifying
the native and inner-loop vectorizer paths in D121624 and D123005.

I think we should not block forward progress on unused pieces of code,
so this patch removes the utilities for now. The plan is to re-introduce
them as needed in a way that is compatible with the unified VPlan scheme
used in both the inner loop vectorizer and the native path.

Reviewed By: sguggill

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

show more ...

[VPlan] Use Exiting-block instead of Exit-block terminology (NFC).

In LLVM's common loop terminology, an exit block is a block outside a
loop with a predecessor inside the loop. An exiting block is

[VPlan] Use Exiting-block instead of Exit-block terminology (NFC).

In LLVM's common loop terminology, an exit block is a block outside a
loop with a predecessor inside the loop. An exiting block is a block
inside the loop which branches to an exit block outside the loop.

This patch updates a few places where VPlan was using ExitBlock for a
block exiting a region. Those instances have been updated to use
ExitingBlock.

Reviewed By: Ayal

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

show more ...