Pre-commit tests exercising different types of source/sink in
depend_diff_types.ll, in preparation to weaken the HasSameSize check in
LoopAccessAnalysis.
Co-authored-by: Igor Kirillov <igor.kirillov@arm.com>
Relax the NUW requirements for isKnownPredicateViaNoOverflow, if the
second operand (Y) is an ADD. The code only simplifies the condition if
C1 < C2, so if the second ADD is NUW, it doesn't matter whether the
first operand also has the NUW flag, as it cannot wrap if C1 < C2.
https://alive2.llvm.org/ce/z/b3dM7N
PR: https://github.com/llvm/llvm-project/pull/149795
The original test @backward_dep_known_distance_less_than_btc was
incorrectly named, as all loads are completely before the first store.
Add a variant where this is not the case: @backward_dep_known_distance_less_than_btc
This reverts commit d43a80936d437d217d5a6dbbaa5fb131c27e7085.
With the correctness issue blocking the recommit finally fixed
(5d01697ec6cb), again unconditionally check if accesses are completely
before or after each other.
Strip ShouldRetyWithRuntimeCheck from the
DepedenceDistanceStrideAndSizeInfo struct, and free isDependent from the
responsibility of setting the condition for when runtime-checks are
needed, transferring this responsibility to
getDependenceDistanceStrideAndSize.
We can have multiple DepType::Unknown dependences that, by themselves,
do not trigger the retrying with runtime memory checks, and therefore
block vectorization. But once a single
FoundNonConstantDistanceDependence is found, the analysis seems to
switch to the "LAA: Retrying with memory checks" path and allows all
these dependences to be handled via runtime checks. There is hence no
rationale for predicating FoundNonConstantDependenceDistance on
DepType::Unknown, and removing this predication is one of the
side-effects of this patch.
Evaluating AR at the symbolic max BTC may wrap and create an expression
that is less than the start of the AddRec due to wrapping (for example
consider MaxBTC = -2).
If that's the case, set ScEnd to -(EltSize + 1). ScEnd will get
incremented by EltSize before returning, so this effectively sets ScEnd
to unsigned max. Note that LAA separately checks that accesses cannot
not wrap (52ded672492,
https://github.com/llvm/llvm-project/pull/127543), so unsigned max
represents an upper bound.
When there is a computable backedge-taken count, we are guaranteed to
execute the number of iterations, and if any pointer would wrap it would
be UB (or the access will never be executed, so cannot alias). It
includes new tests from the previous discussion that show a case we wrap
with a BTC, but it is UB due to the pointer after the object wrapping
(in `evaluate-at-backedge-taken-count-wrapping.ll`)
When we have only a maximum backedge taken count, we instead try to use
dereferenceability information to determine if the pointer access must be in
bounds for the maximum backedge taken count.
PR: https://github.com/llvm/llvm-project/pull/128061
Make sure tests cover loops accessing the last valid and the first
invalid memory location. Note that the test
`@all_exits_dominate_latch_countable_exits_at_most_1000_iterations_kno`
has been modified to execute at most 1000 iterations; it previously
executed 1001 iterations.
This depth limits a linear search (rather than the usual potentially
exponential one) and is not particularly important for compile-time in
practice.
The change in #137297 is going to increase the length of GEP chains, so
I'd like to increase this limit a bit to reduce the chance of
regressions (https://github.com/dtcxzyw/llvm-opt-benchmark/pull/2419
showed a 13% increase in SearchLimitReached). There is no particular
significance to the new value of 10.
Compile-time is neutral.
Currently if there's any memory access that AccessAnalysis couldn't
analyze then all of the runtime pointer check results are discarded.
This patch makes this able to be controlled with the AllowPartial
option, which makes it so we generate the runtime check information
for those pointers that we could analyze, as transformations may still
be able to make use of the partial information.
Of the transformations that use LoopAccessAnalysis, only
LoopVersioningLICM changes behaviour as a result of this change. This is
because the others either:
* Check canVectorizeMemory, which will return false when we have partial
pointer information as analyzeLoop() will return false.
* Examine the dependencies returned by getDepChecker(), which will be
empty as we exit analyzeLoop if we have partial pointer information
before calling areDepsSafe(), which is what fills in the dependency
information.
UpdateTestChecks has a make_analyzer_generalizer to replace pointer
addressess from the debug output of LAA with a pattern, which is an
acceptable solution when there is one RUN line. However, when there are
multiple RUN lines with a common pattern, UTC fails to recognize common
output due to mismatched pointer addresses. Instead of hacking UTC scrub
the output before comparing the outputs from the different RUN lines,
fix the issue once and for all by making LAA not output unstable pointer
addresses in the first place.
The removal of the now-dead make_analyzer_generalizer is left as a
non-trivial exercise for a follow-up.
We bail out from MaxVF calculation if the strides are not the same.
Instead, we are dependent on runtime checks, though not yet implemented.
We could instead use the MaxStride to conservatively use an upper bound.
This handles cases like the following:
```c
#define LEN 256 * 256
float a[LEN];
void gather() {
for (int i = 0; i < LEN - 1024 - 255; i++) {
#pragma clang loop interleave(disable)
#pragma clang loop unroll(disable)
for (int j = 0; j < 256; j++)
a[i + j + 1024] += a[j * 4 + i];
}
}
```
---------
Co-authored-by: Florian Hahn <flo@fhahn.com>
LoopAccessAnalysis has code for handling function calls where the
function is marked with the 'convergent' attribute, but the test
coverage is insufficient. Fix this by adding a test showing the case of
no-runtime-checks adapted from LoopDistribute, and clean up the existing
test with runtime-checks. Also regenerate the test file with
UpdateTestChecks.
The patch splits the store-load forwarding distance analysis from other
dependency analysis in LAA. Currently it supports only power-of-2
distances, required to support non-power-of-2 distances in future.
Part of #100755
In some cases, it is possible for the same underlying object to be
accessed via pointers to different address spaces. This could lead to
pointers from different address spaces ending up in the same dependency
set, which isn't allowed (and triggers an assertion).
Update the mapping from underlying object -> last access to also include
the accessing address space.
Fixes https://github.com/llvm/llvm-project/issues/124759.
PR: https://github.com/llvm/llvm-project/pull/129087
Currently we only check if the pointers involved in runtime checks do
not wrap if we need to perform dependency checks. If that's not the
case, we generate runtime checks, even if the pointers may wrap (see
test/Analysis/LoopAccessAnalysis/runtime-checks-may-wrap.ll).
If the pointer wraps, then we swap start and end of the runtime check,
leading to incorrect checks.
An Alive2 proof of what the runtime checks are checking conceptually (on
i4 to have it complete in reasonable time) showing the incorrect result
should be https://alive2.llvm.org/ce/z/KsHzn8
Depends on https://github.com/llvm/llvm-project/pull/127410 to avoid
more regressions.
PR: https://github.com/llvm/llvm-project/pull/127543
Update isNoWrap to make the IR Ptr argument optional. This allows using
isNoWrap when dealing with things like pointer-selects, where a select
is translated to multiple pointer SCEV expressions, but there is no IR
value that can be used. We don't try to retrieve pointer values for the
pointer SCEVs and using info from the IR would not be safe. For example,
we cannot use inbounds, because the pointer may never be accessed.
PR: https://github.com/llvm/llvm-project/pull/127410
The stripGetElementPtr function is mysteriously named, and calls into
another mysterious getGEPInductionOperand which does something
complicated with GEP indices. The real purpose of the badly-named
stripGetElementPtr function is to get a loop-variant GEP index, if there
is one. The getGEPInductionOperand is totally redundant, as stripping
off zeros from the end of GEP indices has no effect on computing the
loop-variant GEP index, as constant zeros are always loop-invariant.
Moreover, the GEP induction operand is simply the first non-zero index
from the end, which stripGetElementPtr returns when it finds that any of
the GEP indices are loop-variant: this is a completely unrelated value
to the GEP index that is loop-variant. The implicit assumption here is
that there is only ever one loop-variant index, and it is the first
non-zero one from the end.
The logic is unnecessarily complicated for what stripGetElementPtr wants
to achieve, and the header comments are confusing as well. Strip
getGEPInductionOperand, rework and rename stripGetElementPtr.
Inline hasComputableBounds into createCheckForAccess. This removes a
level of indirection and allows for passing the AddRec directly to
isNoWrap, removing the need to retrieve the AddRec for the pointer
again.
The early continue for invariant SCEVs now also applies to forked
pointers (i.e. when there's more than one entry in TranslatedPtrs) when
ShouldCheckWrap is true, as those trivially won't wrap.
The change is NFC otherwise. replaceSymbolicStrideSCEV is now called
earlier.
Reorganize the code in isNoWrap to perform the no-wrap checks without
relying on getPtrStride directly. getPtrStride now uses isNoWrap.
The new structure allows deriving no-wrap in more cases in LAA, because
there are some cases where getPtrStride bails out early because it
cannot return a constant stride, but we can still prove no-wrap for the
pointer.
An example are AddRecs with non-ConstantInt strides with inbound GEPs,
in the improved test cases.
This enables vectorization with runtime checks in a few more cases.
PR: https://github.com/llvm/llvm-project/pull/126971
Uses the fixed register width if scalable vectorization is not enabled
(via TargetTransformInfo::enableScalableVectorization) and improves
results if there are scalable vector registers, but they shouldn't be
used.
LoopAccessAnalysis is missing coverage of the special-case of invariant
stores with unit stride. It was previously determined that
stride-versioning for stores is not profitable, but test coverage is
missing. Fix this.
getPtrStride returns 0 when the PtrScev is loop-invariant, and this is
not an erroneous value: it returns std::nullopt to communicate that it
was not able to find a valid pointer stride. In analyzeLoop, we call
getPtrStride with a value_or(0) conflating the zero return value with
std::nullopt. Fix this, handling loop-invariant loads correctly.
When inverting source and sink on a negative induction step, the types
of the source and sink should also be swapped. This fixes a bug in the
code that follows, that computes properties based on these types. With
234cc40 ([LAA] Limit no-overlap check to at least one loop-invariant
accesses.), that code is guarded by a loop-invariant condition: however,
the commit did not add any new tests exercising the guarded code, and
hence the bugfix in this patch requires additional tests to exercise
that guarded codepath.
A SCEVWrapPredicate A implies B, if
* they have the same flag,
* both steps are positive and
* B's start and step are ULE/SLE (for NSUW/NSSW) than A's.
See https://alive2.llvm.org/ce/z/n2T4ss (first pair with known constants
as strides, second pair with variable strides).
Note that this is limited to steps of the same size, due to NSUW having
slightly different semantics than regular NUW. We should be able to
remove this restriction for NSSW (which matches NSW) in the future.
PR: https://github.com/llvm/llvm-project/pull/118184
In 4de3184f07fd8c548125d315dd306d4afa7c9698 we exposed BasicAA's
cross-iteration mode for use in LAA, so we can handle selects with equal
conditions correctly (where the select condition is not actually equal
across iterations).
However, if we replace the selects with equivalent phis, the issue still
exists. In the phi case, we effectively still have an assumption that
the condition(s) that control which phi arg is used will be the same
across iterations. Fix this by disabling this phi handling in
cross-iteration mode.
(I'm not entirely sure whether this is also needed when BasicAA enables
cross-iteration mode during internal phi recursion, but I wouldn't be
surprised if that's the case.)
