[LV][NFC] Refactor structures used to maintain uncountable exit info (#123219)

I've removed the HasUncountableEarlyExit variable, since we can
already determine whether or not a loop has an early e

[LV][NFC] Refactor structures used to maintain uncountable exit info (#123219)

I've removed the HasUncountableEarlyExit variable, since we can
already determine whether or not a loop has an early exit by seeing
if we found an uncountable exit.

I have also deleted the old UncountableExitingBlocks and
UncountableExitBlocks lists and replaced them with a single
uncountable edge. This means we don't need to worry about keeping the
list entries in sync and makes it clear which exiting block
corresponds to which exit block.

show more ...

[LV] Only check isVectorizableEarlyExitLoop with multiple exits. (#121994)

Currently we emit early-exit related debug messages/remarks even when
there is a single exit. Update to only check isVecto

[LV] Only check isVectorizableEarlyExitLoop with multiple exits. (#121994)

Currently we emit early-exit related debug messages/remarks even when
there is a single exit. Update to only check isVectorizableEarlyExitLoop
if there isn't a single exit block.

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

show more ...

[LV] Teach LoopVectorizationLegality about struct vector calls (#119221)

This is a split-off from #109833 and only adds code relating to checking
if a struct-returning call can be vectorized.

Th

[LV] Teach LoopVectorizationLegality about struct vector calls (#119221)

This is a split-off from #109833 and only adds code relating to checking
if a struct-returning call can be vectorized.

This initial patch only allows the case where all users of the struct
return are `extractvalue` operations that can be widened.

```
%call = tail call { float, float } @foo(float %in_val)
%extract_a = extractvalue { float, float } %call, 0
%extract_b = extractvalue { float, float } %call, 1
```

Note: The tests require the VFABI changes from #119000 to pass.

show more ...

[NFC][TargetTransformInfo][VectorUtils] Consolidate `isVectorIntrinsic...` api (#117635)

- update `VectorUtils:isVectorIntrinsicWithScalarOpAtArg` to use TTI for
all uses, to allow specifiction of

[NFC][TargetTransformInfo][VectorUtils] Consolidate `isVectorIntrinsic...` api (#117635)

- update `VectorUtils:isVectorIntrinsicWithScalarOpAtArg` to use TTI for
all uses, to allow specifiction of target specific intrinsics
- add TTI to the `isVectorIntrinsicWithStructReturnOverloadAtField` api
- update TTI api to provide `isTargetIntrinsicWith...` functions and
consistently name them
- move `isTriviallyScalarizable` to VectorUtils

- update all uses of the api and provide the TTI parameter

Resolves #117030

show more ...

[LoopVectorize] Use new single string variant of reportVectorizationFailure (#120414)

[VPlan] Dispatch to multiple exit blocks via middle blocks. (#112138)

A more lightweight variant of
https://github.com/llvm/llvm-project/pull/109193,
which dispatches to multiple exit blocks via t

[VPlan] Dispatch to multiple exit blocks via middle blocks. (#112138)

A more lightweight variant of
https://github.com/llvm/llvm-project/pull/109193,
which dispatches to multiple exit blocks via the middle blocks.

The patch also introduces a bit of required scaffolding to enable
early-exit vectorization, including an option. At the moment, early-exit
vectorization doesn't come with legality checks, and is only used if the
option is provided and the loop has metadata forcing vectorization. This
is only intended to be used for testing during bring-up, with @david-arm
enabling auto early-exit vectorization plugging in the changes from
https://github.com/llvm/llvm-project/pull/88385.

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

show more ...

Check hasOptSize() in shouldOptimizeForSize() (#112626)

[LV] Vectorize histogram operations (#99851)

This patch implements autovectorization support for the 'all-in-one'
histogram intrinsic, which seems to have more support than the
'standalone' intrin

[LV] Vectorize histogram operations (#99851)

This patch implements autovectorization support for the 'all-in-one'
histogram intrinsic, which seems to have more support than the
'standalone' intrinsic. See
https://discourse.llvm.org/t/rfc-vectorization-support-for-histogram-count-operations/74788/
for an overview of the work and my notes on the tradeoffs between the
two approaches.

show more ...

[LoopVectorize] Address comments on PR #107004 left post-commit (#109300)

* Rename Speculative -> Uncountable and update tests.
* Add comments explaining why it's safe to ignore the predicates when

[LoopVectorize] Address comments on PR #107004 left post-commit (#109300)

* Rename Speculative -> Uncountable and update tests.
* Add comments explaining why it's safe to ignore the predicates when
building up a list of exiting blocks.
* Reshuffle some code to do (hopefully) cheaper checks first.

show more ...

[Analysis] Teach isDereferenceableAndAlignedInLoop about SCEV predicates (#106562)

Currently if a loop contains loads that we can prove at compile time
are dereferenceable when certain conditions a

[Analysis] Teach isDereferenceableAndAlignedInLoop about SCEV predicates (#106562)

Currently if a loop contains loads that we can prove at compile time
are dereferenceable when certain conditions are satisfied the function
isDereferenceableAndAlignedInLoop will still return false because
getSmallConstantMaxTripCount will return 0 when SCEV predicates
are required. This patch changes getSmallConstantMaxTripCount to take
an optional Predicates pointer argument so that we can permit
functions such as isDereferenceableAndAlignedInLoop to consider more
cases.

show more ...

[LoopVectorize] Silence unused variable warning

[LoopVectorize] Teach LoopVectorizationLegality about more early exits (#107004)

This patch is split off from PR #88385 and concerns only the code
related to the legality of vectorising early exit

[LoopVectorize] Teach LoopVectorizationLegality about more early exits (#107004)

This patch is split off from PR #88385 and concerns only the code
related to the legality of vectorising early exit loops. It is the first
step in adding support for vectorisation of a simple class of loops that
typically involves searching for something, i.e.

for (int i = 0; i < n; i++) {
if (p[i] == val)
return i;
}
return n;

or

for (int i = 0; i < n; i++) {
if (p1[i] != p2[i])
return i;
}
return n;

In this initial commit LoopVectorizationLegality will only consider
early exit loops legal for vectorising if they follow these criteria:

1. There are no stores in the loop.
2. The loop must have only one early exit like those shown in the above
example. I have referred to such exits as speculative early exits, to
distinguish from existing support for early exits where the
exit-not-taken count is known exactly at compile time.
3. The early exit block dominates the latch block.
4. The latch block must have an exact exit count.
5. There are no loads after the early exit block.
6. The loop must not contain reductions or recurrences. I don't see
anything fundamental blocking vectorisation of such loops, but I just
haven't done the work to support them yet.
7. We must be able to prove at compile-time that loops will not contain
faulting loads.

Tests have been added here:

Transforms/LoopVectorize/AArch64/simple_early_exit.ll

show more ...

[LV] Check for vector-to-scalar casts in legalizer (#106244)

The code makes assumptions later on the operations and their inputs
being scalar in the loops that are processed, so we should make sure

[LV] Check for vector-to-scalar casts in legalizer (#106244)

The code makes assumptions later on the operations and their inputs
being scalar in the loops that are processed, so we should make sure
this is the case in the legalizer.

show more ...

[LV] Fix emission of debug message in legality check (#101924)

Successful vectorization message is emitted even
after "Result" is false. "Result" = false indicates failure of one of
the legality c

[LV] Fix emission of debug message in legality check (#101924)

Successful vectorization message is emitted even
after "Result" is false. "Result" = false indicates failure of one of
the legality check and thus
successful message should not be printed.

show more ...

[NFC] Cleanup in ADT and Analysis headers. (#104484)

Remove unused directly includes and forward declarations in ADT and
Analysis headers.

[LV] Support generating masks for switch terminators. (#99808)

Update createEdgeMask to created masks where the terminator in Src is a
switch. We need to handle 2 separate cases:

1. Dst is not t

[LV] Support generating masks for switch terminators. (#99808)

Update createEdgeMask to created masks where the terminator in Src is a
switch. We need to handle 2 separate cases:

1. Dst is not the default desintation. Dst is reached if any of the
cases with destination == Dst are taken. Join the conditions for each
case where destination == Dst using a logical OR.
2. Dst is the default destination. Dst is reached if none of the cases
with destination != Dst are taken. Join the conditions for each case
where the destination is != Dst using a logical OR and negate it.

Edge masks are created for every destination of cases and/or
default when requesting a mask where the source is a switch.

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

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

show more ...

[SCEV] Use const SCEV * explicitly in more places.

Use const SCEV * explicitly in more places to prepare for
https://github.com/llvm/llvm-project/pull/91961. Split off as suggested.

LV/Legality: fix style after cursory reading (NFC) (#100363)

[Transforms] Use range-based for loops (NFC) (#99607)

Revert "[LV] Autovectorization for the all-in-one histogram intrinsic" (#98493)

Reverts llvm/llvm-project#91458 to deal with post-commit reviewer
requests.

[LV] Autovectorization for the all-in-one histogram intrinsic (#91458)

This patch implements limited loop vectorization support for the 'all-in-one' histogram intrinsic. The feature is disabled by d

[LV] Autovectorization for the all-in-one histogram intrinsic (#91458)

This patch implements limited loop vectorization support for the 'all-in-one' histogram intrinsic. The feature is disabled by default, and when enabled will only vectorize if there are no other users of values in the gather-modify-scatter sequence.

show more ...

[LV] Split checking if tail-folding is possible, collecting masked ops. (#77612)

Introduce new canFoldTail helper which only checks if tail-folding is
possible, but without modifying MaskedOps.

[LV] Split checking if tail-folding is possible, collecting masked ops. (#77612)

Introduce new canFoldTail helper which only checks if tail-folding is
possible, but without modifying MaskedOps.

Just because tail-folding is possible doesn't mean the tail will be
folded; that's up to the cost-model to decide. Separating the check if
tail-folding is possible and preparing for tail-folding makes sure that
MaskedOps is only populated when tail-folding is actually selected.

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

show more ...

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it does

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it doesn't exist...

`getModule()->getDataLayout()` is also a common (the most common?)
reason why code has to include the Module.h header.

show more ...

[LAA] Use PSE::getSymbolicMaxBackedgeTakenCount. (#93499)

Update LAA to use PSE::getSymbolicMaxBackedgeTakenCount which returns
the minimum of the countable exits.

When analyzing dependences and

[LAA] Use PSE::getSymbolicMaxBackedgeTakenCount. (#93499)

Update LAA to use PSE::getSymbolicMaxBackedgeTakenCount which returns
the minimum of the countable exits.

When analyzing dependences and computing runtime checks, we need the
smallest upper bound on the number of iterations. In terms of memory
safety, it shouldn't matter if any uncomputable exits leave the loop,
as long as we prove that there are no dependences given the minimum of
the countable exits. The same should apply also for generating runtime
checks.

Note that this shifts the responsiblity of checking whether all exit
counts are computable or handling early-exits to the users of LAA.

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

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

show more ...

[LV,LAA] Don't vectorize loops with load and store to invar address.

Code checking stores to invariant addresses and reductions made an
incorrect assumption that the case of both a load & store to t

[LV,LAA] Don't vectorize loops with load and store to invar address.

Code checking stores to invariant addresses and reductions made an
incorrect assumption that the case of both a load & store to the same
invariant address does not need to be handled.

In some cases when vectorizing with runtime checks, there may be
dependences with a load and store to the same address, storing a
reduction value.

Update LAA to separately track if there was a store-store and a
load-store dependence with an invariant addresses.

Bail out early if there as a load-store dependence with invariant
address. If there was a store-store one, still apply the logic checking
if they all store a reduction.

show more ...