[AA] Teach BasicAA to recognize basic GEP range information.

The information can be implicit (from `ValueTracking`) or explicit.

This implements the backend part of the following RFC
https://groups

[AA] Teach BasicAA to recognize basic GEP range information.

The information can be implicit (from `ValueTracking`) or explicit.

This implements the backend part of the following RFC
https://groups.google.com/g/llvm-dev/c/T9o51zB1JY.

We still need to settle on how to best represent the information in the
IR, but this is a separate discussion.

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

show more ...

[BasicAA] Move DecomposedGEP out of header (NFC)

It's sufficient to have a forward declaration in the header, we
can move the definition of the struct (and VariableGEPIndex)
in the source file.

[BasicAA] Pass whole DecomposedGEP to subtraction API (NFC)

Rather than separately handling subtraction of offset and variable
indices, make this one operation. Also rewrite the implementation
to us

[BasicAA] Pass whole DecomposedGEP to subtraction API (NFC)

Rather than separately handling subtraction of offset and variable
indices, make this one operation. Also rewrite the implementation
to use range-based for loops.

show more ...

[BasicAA] Pass DecomposedGEP to constantOffsetHeuristic() (NFC)

Rather than separately passing VarIndices and BaseOffset, pass
the whole DecomposedGEP.

[BasicAA] Don't check whether GEP is sized (NFC)

GEPs are required to have sized source element type, so we can
just assert that here.

[AA] Move earliest escape tracking from DSE to AA

This is a followup to D109844 (and alternative to D109907), which
integrates the new "earliest escape" tracking into AliasAnalysis.
This is done by

[AA] Move earliest escape tracking from DSE to AA

This is a followup to D109844 (and alternative to D109907), which
integrates the new "earliest escape" tracking into AliasAnalysis.
This is done by replacing the pre-existing context-free capture
cache in AAQueryInfo with a replaceable (virtual) object with two
implementations: The SimpleCaptureInfo implements the previous
behavior (check whether object is captured at all), while
EarliestEscapeInfo implements the new behavior from DSE.

This combines the "earliest escape" analysis with the full power of
BasicAA: It subsumes the call handling from D109907, considers a
wider range of escape sources, and works with AA recursion. The
compile-time cost is slightly higher than with D109907.

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

show more ...

[BasicAA] Don't consider Argument as escape source (NFCI)

The case of an Argument and an identified function local is already
handled earlier, because we don't care about captures in that case.
As s

[BasicAA] Don't consider Argument as escape source (NFCI)

The case of an Argument and an identified function local is already
handled earlier, because we don't care about captures in that case.
As such, we don't need to additionally consider the combination of
an Argument with a non-escaping identified function local.

This ensures that isEscapeSource() only returns true for
instructions, which is necessary for D110368.

show more ...

[BasicAA] Fix typo ScaleForGDC -> ScaleForGCD.

[BasicAA] Use separate scale variable for GCD.

Use separate variable for adjusted scale used for GCD computations. This
fixes an issue where we incorrectly determined that all indices are
non-negati

[BasicAA] Use separate scale variable for GCD.

Use separate variable for adjusted scale used for GCD computations. This
fixes an issue where we incorrectly determined that all indices are
non-negative and returned noalias because of that.

Follow up to 91fa3565da16.

show more ...

[BasicAA] Be more careful with modulo ops on VariableGEPIndex.

(V * Scale) % X may not produce the same result for any possible value
of V, e.g. if the multiplication overflows. This means we curren

[BasicAA] Be more careful with modulo ops on VariableGEPIndex.

(V * Scale) % X may not produce the same result for any possible value
of V, e.g. if the multiplication overflows. This means we currently
incorrectly determine NoAlias in some cases.

This patch updates LinearExpression to track whether the expression
has NSW and uses that to adjust the scale used for alias checks.

Reviewed By: nikic

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

show more ...

[BasicAA] Handle PHIs without incoming values gracefully

Fix a bug introduced by f6f6f6375d1a4bced8a6e79a78726ab32b8dd879.
Now for empty PHIs, instead of crashing on assert(hasVal()) in
Optional's i

[BasicAA] Handle PHIs without incoming values gracefully

Fix a bug introduced by f6f6f6375d1a4bced8a6e79a78726ab32b8dd879.
Now for empty PHIs, instead of crashing on assert(hasVal()) in
Optional's internals, we'll return NoAlias, as we did before that patch.

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

show more ...

BasicAA: Recognize inttoptr as isEscapeSource

Pointers escape when converted to integers, so a pointer produced by
converting an integer to a pointer must not be a local non-escaping
object.

Review

BasicAA: Recognize inttoptr as isEscapeSource

Pointers escape when converted to integers, so a pointer produced by
converting an integer to a pointer must not be a local non-escaping
object.

Reviewed By: nikic, nlopes, aqjune

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

show more ...

[AA] Updates for D95543.

Addressing latter comments in D95543:
- `AliasResult::Result` renamed to `AliasResult::Kind`
- Offset printing added for `PartialAlias` case in `-aa-eval`
- Removed VisitedP

[AA] Updates for D95543.

Addressing latter comments in D95543:
- `AliasResult::Result` renamed to `AliasResult::Kind`
- Offset printing added for `PartialAlias` case in `-aa-eval`
- Removed VisitedPhiBBs check from BasicAA'

Reviewed By: nikic

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

show more ...

[AA][NFC] Convert AliasResult to class containing offset for PartialAlias case.

Add an ability to store `Offset` between partially aliased location. Use this
storage within returned `ResultAlias` in

[AA][NFC] Convert AliasResult to class containing offset for PartialAlias case.

Add an ability to store `Offset` between partially aliased location. Use this
storage within returned `ResultAlias` instead of caching it in `AAQueryInfo`.

Reviewed By: asbirlea

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

show more ...

[NFC][AA] Prepare to convert AliasResult to class with PartialAlias offset.

Main reason is preparation to transform AliasResult to class that contains
offset for PartialAlias case.

Reviewed By: asb

[NFC][AA] Prepare to convert AliasResult to class with PartialAlias offset.

Main reason is preparation to transform AliasResult to class that contains
offset for PartialAlias case.

Reviewed By: asbirlea

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

show more ...

[BasicAA] Don't store AATags in cache key (NFC)

The AAMDNodes part of the MemoryLocation is not used by the BasicAA
cache, so don't store it. This reduces the size of each cache entry
from 112 bytes

[BasicAA] Don't store AATags in cache key (NFC)

The AAMDNodes part of the MemoryLocation is not used by the BasicAA
cache, so don't store it. This reduces the size of each cache entry
from 112 bytes to 48 bytes.

show more ...

[BasicAA] Don't pass through AA metadata (NFCI)

BasicAA itself doesn't make use of AA metadata, but passes it
through to recursive queries and makes it part of the cache key.
Aliasing decisions that

[BasicAA] Don't pass through AA metadata (NFCI)

BasicAA itself doesn't make use of AA metadata, but passes it
through to recursive queries and makes it part of the cache key.
Aliasing decisions that are based on AA metadata (i.e. TBAA and
ScopedAA) are based *only* on AA metadata, so checking them with
different pointer values or sizes is not useful, the result will
always be the same.

While this change is a mild compile-time improvement by itself,
the actual goal here is to reduce the size of AA cache keys in
a followup change.

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

show more ...

[BasicAA] Make sure types match in constant offset heuristic

This can only happen if offset types that are larger than the
pointer size are involved. The previous implementation did not
assert in th

[BasicAA] Make sure types match in constant offset heuristic

This can only happen if offset types that are larger than the
pointer size are involved. The previous implementation did not
assert in this case because it initialized the APInts to the
width of one of the variables -- though I strongly suspect it
did not compute correct results in this case.

Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=32621
reported by fhahn.

show more ...

[BasicAA] Handle gep with unknown sizes earlier (NFCI)

If the sizes of both memory locations are unknown, we can only
perform a check on the underlying objects. There's no point in
going through GEP

[BasicAA] Handle gep with unknown sizes earlier (NFCI)

If the sizes of both memory locations are unknown, we can only
perform a check on the underlying objects. There's no point in
going through GEP decomposition in this case.

show more ...

[BasicAA] Refactor linear expression decomposition

The current linear expression decomposition handles zext/sext by
decomposing the casted operand, and then checking NUW/NSW flags
to determine wheth

[BasicAA] Refactor linear expression decomposition

The current linear expression decomposition handles zext/sext by
decomposing the casted operand, and then checking NUW/NSW flags
to determine whether the extension can be distributed. This has
some disadvantages:

First, it is not possible to perform a partial decomposition. If
we have zext((x + C1) +<nuw> C2) then we will fail to decompose
the expression entirely, even though it would be safe and
profitable to decompose it to zext(x + C1) +<nuw> zext(C2)

Second, we may end up performing unnecessary decompositions,
which will later be discarded because they lack nowrap flags
necessary for extensions.

Third, correctness of the code is not entirely obvious: At a high
level, we encounter zext(x -<nuw> C) in the form of a zext on the
linear expression x + (-C) with nuw flag set. Notably, this case
must be treated as zext(x) + -zext(C) rather than zext(x) + zext(-C).
The code handles this correctly by speculatively zexting constants
to the final bitwidth, and performing additional fixup if the
actual extension turns out to be an sext. This was not immediately
obvious to me.

This patch inverts the approach: An ExtendedValue represents a
zext(sext(V)), and linear expression decomposition will try to
decompose V further, either by absorbing another sext/zext into the
ExtendedValue, or by distributing zext(sext(x op C)) over a binary
operator with appropriate nsw/nuw flags. At each step we can
determine whether distribution is legal and abort with a partial
decomposition if not. We also know which extensions we need to
apply to constants, and don't need to speculate or fixup.

show more ...

[BasicAA] Correct handle implicit sext in decomposition

While explicit sext instructions were handled correctly, the
implicit sext that occurs if the offset is smaller than the
pointer size blindly

[BasicAA] Correct handle implicit sext in decomposition

While explicit sext instructions were handled correctly, the
implicit sext that occurs if the offset is smaller than the
pointer size blindly assumed that sext(X * Scale + Offset) is the
same as sext(X) * Scale + Offset, which is obviously not correct.

Fix this by extracting the code that handles linear expression
extension and reusing it for the implicit sext as well.

show more ...

[BasicAA] Clarify entry values of GetLinearExpression() (NFC)

A number of variables need to be correctly initialized on entry
to GetLinearExpression() for the implementation to behave reasonably.

T

[BasicAA] Clarify entry values of GetLinearExpression() (NFC)

A number of variables need to be correctly initialized on entry
to GetLinearExpression() for the implementation to behave reasonably.

The fact that SExtBits can currenlty be non-zero on entry is a bug,
as demonstrated by the added test: For implicit sexts by the GEP,
we do currently skip legality checks.

show more ...

[BasicAA] Bail out earlier for invalid shift amount

Currently, we'd produce an incorrect decomposition, because we
already recursively called GetLinearExpression(), so the Scale=1,
Offset=0 will not

[BasicAA] Bail out earlier for invalid shift amount

Currently, we'd produce an incorrect decomposition, because we
already recursively called GetLinearExpression(), so the Scale=1,
Offset=0 will not necessarily be relative to the shl itself.

Now, this doesn't actually matter for functional correctness,
because such a shift is poison anyway, so its okay to return
an incorrect decomposition. It's still unnecessarily confusing
though, and we can easily avoid this by checking the bitwidth
earlier.

show more ...

[BasicAA] Retain shl nowrap flags in GetLinearExpression()

Nowrap flags between mul and shl differ in that mul nsw allows
multiplication of 1 * INT_MIN, while shl nsw does not. This means
that it is

[BasicAA] Retain shl nowrap flags in GetLinearExpression()

Nowrap flags between mul and shl differ in that mul nsw allows
multiplication of 1 * INT_MIN, while shl nsw does not. This means
that it is always fine to transfer shl nowrap flags to muls, but
not necessarily the other way around. In this case the NUW/NSW
results refer to mul/add operations, so it's fine to retain the
flags from the shl.

show more ...

[IR] Lift attribute handling for assume bundles into CallBase

Rather than special-casing assume in BasicAA getModRefBehavior(),
do this one level higher, in the attribute handling of CallBase.

For

[IR] Lift attribute handling for assume bundles into CallBase

Rather than special-casing assume in BasicAA getModRefBehavior(),
do this one level higher, in the attribute handling of CallBase.

For assumes with operand bundles, the inaccessiblememonly attribute
applies regardless of operand bundles.

show more ...