[VPlan] Verify scalar types in VPlanVerifier. NFCI (#122679)

VTypeAnalysis contains some assertions which can be useful for reasoning
that the types of various operands match.

This patch teaches VP

[VPlan] Verify scalar types in VPlanVerifier. NFCI (#122679)

VTypeAnalysis contains some assertions which can be useful for reasoning
that the types of various operands match.

This patch teaches VPlanVerifier to invoke VTypeAnalysis to check them,
and catches some issues with VPInstruction types that are also fixed
here:

* Handles the missing cases for CalculateTripCountMinusVF,
CanonicalIVIncrementForPart and AnyOf
* Fixes ICmp and ActiveLaneMask to return i1 (to align with `icmp` and
`@llvm.get.active.lane.mask` in the LangRef)

The VPlanVerifier unit tests also need to be fleshed out a bit more to
satisfy the stricter assertions

show more ...

Reland "[LoopVectorizer] Add support for partial reductions" with non-phi operand fix. (#121744)

This relands the reverted #120721 with a fix for cases where neither
reduction operand are the reduct

Reland "[LoopVectorizer] Add support for partial reductions" with non-phi operand fix. (#121744)

This relands the reverted #120721 with a fix for cases where neither
reduction operand are the reduction phi. Only
63114239cc8d26225a0ef9920baacfc7cc00fc58 and
63114239cc8d26225a0ef9920baacfc7cc00fc58 are new on top of the reverted
PR.

---------

Co-authored-by: Nicholas Guy <nicholas.guy@arm.com>

show more ...

Revert "Reland "[LoopVectorizer] Add support for partial reductions" (#120721)"

This reverts commit c858bf620c3ab2a4db53e84b9365b553c3ad1aa6 as it casuse optimization crash on -O2, see https://githu

Revert "Reland "[LoopVectorizer] Add support for partial reductions" (#120721)"

This reverts commit c858bf620c3ab2a4db53e84b9365b553c3ad1aa6 as it casuse optimization crash on -O2, see https://github.com/llvm/llvm-project/pull/120721#issuecomment-2563192057

show more ...

Reland "[LoopVectorizer] Add support for partial reductions" (#120721)

This re-lands the reverted #92418

When the VF is small enough so that dividing the VF by the scaling
factor results in 1, the

Reland "[LoopVectorizer] Add support for partial reductions" (#120721)

This re-lands the reverted #92418

When the VF is small enough so that dividing the VF by the scaling
factor results in 1, the reduction phi execution thinks the VF is scalar
and sets the reduction's output as a scalar value, tripping assertions
expecting a vector value. The latest commit in this PR fixes that by
using `State.VF` in the scalar check, rather than the divided VF.

---------

Co-authored-by: Nicholas Guy <nicholas.guy@arm.com>

show more ...

[VPlan] Use inferScalarType in VPInstruction::ResumePhi codegen (NFC).

Use VPlan-based type analysis to retrieve type of phi node. Also adds
missing type inference for ResumePhi and ComputeReduction

[VPlan] Use inferScalarType in VPInstruction::ResumePhi codegen (NFC).

Use VPlan-based type analysis to retrieve type of phi node. Also adds
missing type inference for ResumePhi and ComputeReductionResult opcodes.

show more ...

Revert "[LoopVectorizer] Add support for partial reductions (#92418)"

This reverts commit 060d62b48aeb5080ffcae1dc56e41a06c6f56701.

It looks like this is triggering an assertion when build llvm-tes

Revert "[LoopVectorizer] Add support for partial reductions (#92418)"

This reverts commit 060d62b48aeb5080ffcae1dc56e41a06c6f56701.

It looks like this is triggering an assertion when build llvm-test-suite
on ARM64 macOS.

Reproducer from MultiSource/Benchmarks/Ptrdist/bc/number.c

target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-n32:64-S128-Fn32"
target triple = "arm64-apple-macosx15.0.0"

define void @test(i64 %idx.neg, i8 %0) #0 {
entry:
br label %while.body

while.body: ; preds = %while.body, %entry
%n1ptr.0.idx131 = phi i64 [ %n1ptr.0.add, %while.body ], [ %idx.neg, %entry ]
%n2ptr.0.idx130 = phi i64 [ %n2ptr.0.add, %while.body ], [ 0, %entry ]
%sum.1129 = phi i64 [ %add99, %while.body ], [ 0, %entry ]
%n1ptr.0.add = add i64 %n1ptr.0.idx131, 1
%conv = sext i8 %0 to i64
%n2ptr.0.add = add i64 %n2ptr.0.idx130, 1
%1 = load i8, ptr null, align 1
%conv97 = sext i8 %1 to i64
%mul = mul i64 %conv97, %conv
%add99 = add i64 %mul, %sum.1129
%cmp94 = icmp ugt i64 %n1ptr.0.idx131, 0
%cmp95 = icmp ne i64 %n2ptr.0.idx130, -1
%2 = and i1 %cmp94, %cmp95
br i1 %2, label %while.body, label %while.end.loopexit

while.end.loopexit: ; preds = %while.body
%add99.lcssa = phi i64 [ %add99, %while.body ]
ret void
}

attributes #0 = { "target-cpu"="apple-m1" }

> opt -p loop-vectorize
Assertion failed: ((VF.isScalar() || V->getType()->isVectorTy()) && "scalar values must be stored as (0, 0)"), function set, file VPlan.h, line 284.

show more ...

[LoopVectorizer] Add support for partial reductions (#92418)

Following on from https://github.com/llvm/llvm-project/pull/94499, this
patch adds support to the Loop Vectorizer to emit the partial red

[LoopVectorizer] Add support for partial reductions (#92418)

Following on from https://github.com/llvm/llvm-project/pull/94499, this
patch adds support to the Loop Vectorizer to emit the partial reduction
intrinsics where they may be beneficial for the target.

---------

Co-authored-by: Samuel Tebbs <samuel.tebbs@arm.com>

show more ...

[VPlan] Use variadic isa<> in a few more places. NFC (#119538)

[VPlan] Introduce VPScalarPHIRecipe, use for can & EVL IV codegen (NFC). (#114305)

Introduce a general recipe to generate a scalar phi. Lower
VPCanonicalIVPHIRecipe and VPEVLBasedIVRecipe to VPScal

[VPlan] Introduce VPScalarPHIRecipe, use for can & EVL IV codegen (NFC). (#114305)

Introduce a general recipe to generate a scalar phi. Lower
VPCanonicalIVPHIRecipe and VPEVLBasedIVRecipe to VPScalarIVPHIrecipe
before plan execution, avoiding the need for duplicated ::execute
implementations. There are other cases that could benefit, including
in-loop reduction phis and pointer induction phis.

Builds on a similar idea as
https://github.com/llvm/llvm-project/pull/82270.

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

show more ...

[VPlan] Generalize type inference for binary/cast/shift/logic. NFC (#116173)

[LV][VPlan] Use VF VPValue in VPVectorPointerRecipe (#110974)

Refactors VPVectorPointerRecipe to use the VF VPValue to obtain the
runtime VF, similar to #95305.

Since only reverse vector pointer

[LV][VPlan] Use VF VPValue in VPVectorPointerRecipe (#110974)

Refactors VPVectorPointerRecipe to use the VF VPValue to obtain the
runtime VF, similar to #95305.

Since only reverse vector pointers require the runtime VF, the patch
sets VPUnrollPart::PartOpIndex to 1 for vector pointers and 2 for
reverse vector pointers. As a result, the generation of reverse vector
pointers is moved into a separate recipe.

show more ...

[VPlan] Use VPWidenIntrinsicRecipe to vp.select. (#110489)

Use VPWidenIntrinsicRecipe
(https://github.com/llvm/llvm-project/pull/110486)
to create vp.select intrinsics. This potentially offers an

[VPlan] Use VPWidenIntrinsicRecipe to vp.select. (#110489)

Use VPWidenIntrinsicRecipe
(https://github.com/llvm/llvm-project/pull/110486)
to create vp.select intrinsics. This potentially offers an alternative
to duplicating EVL recipes for all existing recipes.

There are some recipes that will need duplicates (at least at the
moment), due to extra code-gen needs (e.g. widening loads and stores).
But in cases the intrinsic can directly be used, creating the widened
intrinsic directly would reduce the need to duplicate some recipes.


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

show more ...

[VPlan] Introduce VPWidenIntrinsicRecipe to separate from libcall. (#110486)

This patch splits off intrinsic hanlding to a new
VPWidenIntrinsicRecipe. VPWidenIntrinsicRecipes only need access to th

[VPlan] Introduce VPWidenIntrinsicRecipe to separate from libcall. (#110486)

This patch splits off intrinsic hanlding to a new
VPWidenIntrinsicRecipe. VPWidenIntrinsicRecipes only need access to the
intrinsic ID to widen and the scalar result type (in case the intrinsic
is overloaded on the result type). It does not need access to an
underlying IR call instruction or function.

This means VPWidenIntrinsicRecipe can be created easily without access
to underlying IR.

show more ...

[VPlan] Add getSCEVExprForVPValue util, use to get trip count SCEV (NFC) (#94464)

Add a new getSCEVExprForVPValue utility which can be used to get a SCEV
expression for a VPValue. The initial imple

[VPlan] Add getSCEVExprForVPValue util, use to get trip count SCEV (NFC) (#94464)

Add a new getSCEVExprForVPValue utility which can be used to get a SCEV
expression for a VPValue. The initial implementation only returns SCEVs
for live-in IR values (by constructing a SCEV based on the live-in IR
value) and VPExpandSCEVRecipe. This is enough to serve its first use,
getting a SCEV for a VPlan's trip count, but will be extended in the
future.

It also removes createTripCountSCEV, as the new helper can be used to
retrieve the SCEV from the VPlan.

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

show more ...

[LV] Support binary and unary operations with EVL-vectorization (#93854)

The patch adds `VPWidenEVLRecipe` which represents `VPWidenRecipe` + EVL
argument. The new recipe replaces `VPWidenRecipe` i

[LV] Support binary and unary operations with EVL-vectorization (#93854)

The patch adds `VPWidenEVLRecipe` which represents `VPWidenRecipe` + EVL
argument. The new recipe replaces `VPWidenRecipe` in
`tryAddExplicitVectorLength` for each binary and unary operations.
Follow up patches will extend support for remaining cases, like `FCmp`
and `ICmp`

show more ...

[VPlan] Move properlyDominates to VPDominatorTree (NFCI).

This allows for easier re-use in additional places in the future. Also
move code to VPlanAnalysis.cpp

[LV][EVL] Support in-loop reduction using tail folding with EVL. (#90184)

Following from #87816, add VPReductionEVLRecipe to describe vector
predication reduction.

Address one of TODOs from #761

[LV][EVL] Support in-loop reduction using tail folding with EVL. (#90184)

Following from #87816, add VPReductionEVLRecipe to describe vector
predication reduction.

Address one of TODOs from #76172.

show more ...

[VPlan] Collect ephemeral values for VPlan.

Port collectEphemeralValues to VPlan as collectEphemeralRecipesForVPlan,
use it in willGenerateVectors. This fixes a regression caused by
29b8b72117 for l

[VPlan] Collect ephemeral values for VPlan.

Port collectEphemeralValues to VPlan as collectEphemeralRecipesForVPlan,
use it in willGenerateVectors. This fixes a regression caused by
29b8b72117 for loops where the only vector values are ephemeral.

show more ...

[LV] Move check if any vector insts will be generated to VPlan. (#96622)

This patch moves the check if any vector instructions will be generated
from getInstructionCost to be based on VPlan. This s

[LV] Move check if any vector insts will be generated to VPlan. (#96622)

This patch moves the check if any vector instructions will be generated
from getInstructionCost to be based on VPlan. This simplifies
getInstructionCost, is more accurate as we check the final result and
also allows us to exit early once we visit a recipe that generates
vector instructions.

The helper can then be re-used by the VPlan-based cost model to match
the legacy selectVectorizationFactor behavior, this fixing a crash and
paving the way to recommit
https://github.com/llvm/llvm-project/pull/92555.

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

show more ...

[VPlan] Generalize type inference for binary VPInstructions (NFC).

Generalize logic to set the result type for ops where the result type
and the types of all operands match. Use it to support any un

[VPlan] Generalize type inference for binary VPInstructions (NFC).

Generalize logic to set the result type for ops where the result type
and the types of all operands match. Use it to support any unary and
binops.

show more ...

VPlan: add missing case for LogicalAnd; fix crash (#93553)

VPTypeAnalysis::inferScalarTypeForRecipe is missing the case for
VPInstruction::LogicalAnd, due to which the test
vplan-incomplete-cases.

VPlan: add missing case for LogicalAnd; fix crash (#93553)

VPTypeAnalysis::inferScalarTypeForRecipe is missing the case for
VPInstruction::LogicalAnd, due to which the test
vplan-incomplete-cases.ll crashes. Add this missing case, and move the
test in vplan-infer-not-or-type.ll to vplan-incomplete-cases.ll, showing
correct codegen for trip-counts 2 and 3.

show more ...

[VPlan] Model FOR extract of exit value in VPlan. (#93395)

This patch introduces a new ExtractFromEnd VPInstruction opcode to
extract the value of a FOR for users outside the loop (i.e. in the
sca

[VPlan] Model FOR extract of exit value in VPlan. (#93395)

This patch introduces a new ExtractFromEnd VPInstruction opcode to
extract the value of a FOR for users outside the loop (i.e. in the
scalar loop's exits). This moves the first part of fixing first order
recurrences to VPlan, and removes some additional code to patch up
live-outs, which is now handled automatically.

The majority of test changes is due to changes in the order of which the
extracts are generated now. As we are now using VPTransformState to
generate the extracts, we may be able to re-use existing extracts in the
loop body in some cases. For scalable vectors, in some cases we now have
to compute the runtime VF twice, as each extract is now independent, but
those should be trivial to clean up for later passes (and in line with
other places in the code that also liberally re-compute runtime VFs).

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

show more ...

[VPlan] Add scalar inferencing support for addrspace cast (#92107)

Fixes https://github.com/llvm/llvm-project/issues/91434

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

[VPlan] Add scalar inferencing support for Not and Or insns (#89160)

Fixes #87394.

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

[VPlan] Introduce recipes for VP loads and stores. (#87816)

Introduce new subclasses of VPWidenMemoryRecipe for VP
(vector-predicated) loads and stores to address multiple TODOs from
https://githu

[VPlan] Introduce recipes for VP loads and stores. (#87816)

Introduce new subclasses of VPWidenMemoryRecipe for VP
(vector-predicated) loads and stores to address multiple TODOs from
https://github.com/llvm/llvm-project/pull/76172

Note that the introduction of the new recipes also improves code-gen for
VP gather/scatters by removing the redundant header mask. With the new
approach, it is not sufficient to look at users of the widened canonical
IV to find all uses of the header mask.

In some cases, a widened IV is used instead of separately widening the
canonical IV. To handle that, first collect all VPValues representing header
masks (by looking at users of both the canonical IV and widened inductions
that are canonical) and then checking all users (recursively) of those header
masks.

Depends on https://github.com/llvm/llvm-project/pull/87411.

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

show more ...