[LAA] Require AddRecs to be in the innermost loop for diff-checks.

The simpler diff-checks require pointers with add-recs from the same
innermost loop, but this property wasn't check completely. Add

[LAA] Require AddRecs to be in the innermost loop for diff-checks.

The simpler diff-checks require pointers with add-recs from the same
innermost loop, but this property wasn't check completely. Add the
missing check to ensure both addrecs are in the innermost loop.

Fixes #57315.

(cherry picked from commit 9405af1c850139f6ddd6d35ff395756fe2aef31f)

show more ...

Use llvm::less_first and llvm::less_second (NFC)

[Analysis] Remove a redundant return statement (NFC)

Identified with readability-redundant-control-flow.

[LoopAccessAnalysis] Simplify D119047

No need to add checks for every type per pointer that we couldn't create
a check for the first time around, just the types that weren't
successful.

Reviewed By

[LoopAccessAnalysis] Simplify D119047

No need to add checks for every type per pointer that we couldn't create
a check for the first time around, just the types that weren't
successful.

Reviewed By: fhahn

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

show more ...

[LAA] Fix latent missing check bug when mixing scalable and non-scalabe strides

Noticed via inspection; to my knowledge, impossible to hit today. In theory, we could have a fixed stride check be an

[LAA] Fix latent missing check bug when mixing scalable and non-scalabe strides

Noticed via inspection; to my knowledge, impossible to hit today. In theory, we could have a fixed stride check be analyzed, then a scalable one. With the old code, the scalable one would be silently dropped, and the runtime guard would go ahead with only the fixed one. This would be a miscompile.

show more ...

[LAA] Fix the build with older versions of Clang

llvm/lib/Analysis/LoopAccessAnalysis.cpp:916:12: error: no viable conversion from returned value of type 'SmallVector<[...], 2>' to function return t

[LAA] Fix the build with older versions of Clang

llvm/lib/Analysis/LoopAccessAnalysis.cpp:916:12: error: no viable conversion from returned value of type 'SmallVector<[...], 2>' to function return type 'SmallVector<[...], (default)
CalculateSmallVectorDefaultInlinedElements<T>::value aka 3>'
return Scevs;
^~~~~

show more ...

[LAA] Add recursive IR walker for forked pointers

This builds on the previous forked pointers patch, which only accepted
a single select as the pointer to check. A recursive function to walk
through

[LAA] Add recursive IR walker for forked pointers

This builds on the previous forked pointers patch, which only accepted
a single select as the pointer to check. A recursive function to walk
through IR has been added, which searches for either a loop-invariant
or addrec SCEV.

This will only handle a single fork at present, so selects of selects
or a GEP with a select for both the base and offset will be rejected.

There is also a recursion limit with a cli option to change it.

Reviewed By: fhahn, david-arm

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

show more ...

[Analysis] Qualify auto variables in for loops (NFC)

Recommit "[LAA] Initial support for runtime checks with pointer selects."

This reverts commit 7aa8a678826dea86ff3e6c7df9d2a8a6ef868f5d.

This version includes fixes to address issues uncovered after

Recommit "[LAA] Initial support for runtime checks with pointer selects."

This reverts commit 7aa8a678826dea86ff3e6c7df9d2a8a6ef868f5d.

This version includes fixes to address issues uncovered after
the commit landed and discussed at D11448.

Those include:

* Limit select-traversal to selects inside the loop.
* Freeze pointers resulting from looking through selects to avoid
branch-on-poison.

show more ...

Revert "[LAA] Initial support for runtime checks with pointer selects."

This reverts commit 5890b30105999a137e72e42f3760bebfd77001ca as per discussion
on the review thread: https://reviews.llvm.org/

Revert "[LAA] Initial support for runtime checks with pointer selects."

This reverts commit 5890b30105999a137e72e42f3760bebfd77001ca as per discussion
on the review thread: https://reviews.llvm.org/D114487#3547560.

show more ...

[LAA,LV] Add initial support for pointer-diff memory checks.

This patch adds initial support for a pointer diff based runtime check
scheme for vectorization. This scheme requires fewer computations

[LAA,LV] Add initial support for pointer-diff memory checks.

This patch adds initial support for a pointer diff based runtime check
scheme for vectorization. This scheme requires fewer computations and
checks than the existing full overlap checking, if it is applicable.

The main idea is to only check if source and sink of a dependency are
far enough apart so the accesses won't overlap in the vector loop. To do
so, it is sufficient to compute the difference and compare it to the
`VF * UF * AccessSize`. It is sufficient to check
`(Sink - Src) <u VF * UF * AccessSize` to rule out a backwards
dependence in the vector loop with the given VF and UF. If Src >=u Sink,
there is not dependence preventing vectorization, hence the overflow
should not matter and using the ULT should be sufficient.

Note that the initial version is restricted in multiple ways:

1. Pointers must only either be read or written, by a single
instruction (this allows re-constructing source/sink for
dependences with the available information)
2. Source and sink pointers must be add-recs, with matching steps
3. The step must be a constant.
3. abs(step) == AccessSize.

Most of those restrictions can be relaxed in the future.

See https://github.com/llvm/llvm-project/issues/53590.

Reviewed By: dmgreen

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

show more ...

[LAA] Initial support for runtime checks with pointer selects.

Scaffolding support for generating runtime checks for multiple SCEV expressions
per pointer. The initial version just adds support for

[LAA] Initial support for runtime checks with pointer selects.

Scaffolding support for generating runtime checks for multiple SCEV expressions
per pointer. The initial version just adds support for looking through
a single pointer select.

The more sophisticated logic for analyzing forks is in D108699

Reviewed By: huntergr

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

show more ...

[LoopVectorize] Support reductions that store intermediary result

Adds ability to vectorize loops containing a store to a loop-invariant
address as part of a reduction that isn't converted to SSA fo

[LoopVectorize] Support reductions that store intermediary result

Adds ability to vectorize loops containing a store to a loop-invariant
address as part of a reduction that isn't converted to SSA form due to
lack of aliasing info. Runtime checks are generated to ensure the store
does not alias any other accesses in the loop.

Ordered fadd reductions are not yet supported.

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

show more ...

[NFC][LAA] Match-up type sizes for possible extensions, based on actual bit-size rather than rounded-up byte size.

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

[Analysis] Apply clang-tidy fixes for readability-redundant-smartptr-get (NFC)

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Diff

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120659

show more ...

[LAA] Add remarks for unbounded array access

Adds new optimization remarks when loop vectorization fails due to
the compiler being unable to find bound of an array access inside
a loop

Differentia

[LAA] Add remarks for unbounded array access

Adds new optimization remarks when loop vectorization fails due to
the compiler being unable to find bound of an array access inside
a loop

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

show more ...

[LAA] Add missing newline in debug print

[PSE] Remove assumption that top level predicate is union from public interface [NFC*]

Note that this doesn't actually cause the top level predicate to become a non-union just yet.

The * above come

[PSE] Remove assumption that top level predicate is union from public interface [NFC*]

Note that this doesn't actually cause the top level predicate to become a non-union just yet.

The * above comes from a case in the LoopVectorizer where a predicate which is later proven no longer blocks vectorization due to a change from checking if predicates exists to whether the predicate is possibly false.

show more ...

[OpaquePtr][LoopAccessAnalysis] Support opaque pointers

Previously we relied on the pointee type to determine what type we need
to do runtime pointer access checks.

With opaque pointers, we can acc

[OpaquePtr][LoopAccessAnalysis] Support opaque pointers

Previously we relied on the pointee type to determine what type we need
to do runtime pointer access checks.

With opaque pointers, we can access a pointer with more than one type,
so now we keep track of all the types we're accessing a pointer's
memory with.

Also some other minor getPointerElementType() removals.

Reviewed By: #opaque-pointers, nikic

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

show more ...

[LAA] Add Memory dependence remarks.

Adds new optimization remarks when vectorization fails.

More specifically, new remarks are added for following 4 cases:

- Backward dependency
- Backward depend

[LAA] Add Memory dependence remarks.

Adds new optimization remarks when vectorization fails.

More specifically, new remarks are added for following 4 cases:

- Backward dependency
- Backward dependency that prevents Store-to-load forwarding
- Forward dependency that prevents Store-to-load forwarding
- Unknown dependency

It is important to note that only one of the sources
of failures (to vectorize) is reported by the remarks.
This source of failure may not be first in program order.

A regression test has been added to test the following cases:

a) Loop can be vectorized: No optimization remark is emitted
b) Loop can not be vectorized: In this case an optimization
remark will be emitted for one source of failure.

Reviewed By: sdesmalen, david-arm

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

show more ...

[Analysis] Use default member initialization (NFC)

Identified with modernize-use-default-member-init.

[LAA] Remove overeager assertion for aggregate types.

0a00d64 turned an early exit here into an assertion, but the assertion
can be triggered, as PR52920 shows.

The later code is agnostic to the ac

[LAA] Remove overeager assertion for aggregate types.

0a00d64 turned an early exit here into an assertion, but the assertion
can be triggered, as PR52920 shows.

The later code is agnostic to the accessed type, so just drop the
assert. The patch also adds tests for LAA directly and
loop-load-elimination to show the behavior is sane.

show more ...

[LAA] Use type sizes when determining dependence.

In the isDependence function the code does not try hard enough
to determine the dependence between types. If the types are
different it simply gives

[LAA] Use type sizes when determining dependence.

In the isDependence function the code does not try hard enough
to determine the dependence between types. If the types are
different it simply gives up, whereas in fact what we really
care about are the type sizes. I've changed the code to compare
sizes instead of types.

Reviewed By: fhahn, sdesmalen

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

show more ...

[LoopAccessAnalysis][SVE] Bail out for scalable vectors

The supplied test case, reduced from real world code, crashes with a
'Invalid size request on a scalable vector.' error.

Since it's similar i

[LoopAccessAnalysis][SVE] Bail out for scalable vectors

The supplied test case, reduced from real world code, crashes with a
'Invalid size request on a scalable vector.' error.

Since it's similar in spirit to an existing LAA test, rename the file to
generalize it to both.

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

show more ...