[BasicAA] Do not decompose past casts with different index width (#119365)

BasicAA currently tries to support addrspacecasts that change the index
width by performing the decomposition in the maxim

[BasicAA] Do not decompose past casts with different index width (#119365)

BasicAA currently tries to support addrspacecasts that change the index
width by performing the decomposition in the maximum of all index widths
and then trying to fix this up with in-place sign extends to get correct
overflow behavior if the actual index width is smaller.

However, even in the case where we don't mix different index widths and
just have an index width that is smaller than the maximum, the behavior
is incorrect (see test), because we only perform the index width
adjustment during decomposition and not any of the later logic -- and we
don't do anything at all for variable offsets. I'm sure that the case
where we actually mix different index widths is even more broken than
that.

Fix this by not allowing decomposition through index width changes. If
the pointers have different index widths, fall back to a base object
comparison, ignoring the offsets.

show more ...

[AA] Export the isBaseOfObject() API (NFC)

This is also useful outside BasicAA.

[BasicAA] Treat returns_twice functions as clobbering unescaped objects (#117902)

Effectively this models all the accesses that occur between the first
and second return as happening at the point o

[BasicAA] Treat returns_twice functions as clobbering unescaped objects (#117902)

Effectively this models all the accesses that occur between the first
and second return as happening at the point of the call.

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

show more ...

[BasicAA][LAA] Don't use same-block phis in cross iteration mode (#116802)

In 4de3184f07fd8c548125d315dd306d4afa7c9698 we exposed BasicAA's
cross-iteration mode for use in LAA, so we can handle sel

[BasicAA][LAA] Don't use same-block phis in cross iteration mode (#116802)

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.)

show more ...

[AA] Rename CaptureInfo -> CaptureAnalysis (NFC) (#116842)

I'd like to use the name CaptureInfo to represent the new attribute
proposed at
https://discourse.llvm.org/t/rfc-improvements-to-capture-

[AA] Rename CaptureInfo -> CaptureAnalysis (NFC) (#116842)

I'd like to use the name CaptureInfo to represent the new attribute
proposed at
https://discourse.llvm.org/t/rfc-improvements-to-capture-tracking/81420,
but it's already taken by AA, and I can't think of great alternatives
(CaptureEffects would be something of a stretch).

As such, I'd like to rename CaptureInfo -> CaptureAnalysis in AA, which
also seems like the more accurate terminology.

show more ...

[Analysis] Simplify code with DenseMap::operator[] (NFC) (#111331)

BasicAA: update comments in a routine (NFC) (#110492)

The comments in isObjectSmallerThan are outdated, as it is only ever
called with the underlying object as the first argument. Update the
comme

BasicAA: update comments in a routine (NFC) (#110492)

The comments in isObjectSmallerThan are outdated, as it is only ever
called with the underlying object as the first argument. Update the
comments to reflect this.

show more ...

[BasicAA] Track nuw through decomposed expressions (#106512)

When we decompose the GEP offset expression, and the arithmetic is not
performed using nuw operations, we cannot retain the nuw flag on

[BasicAA] Track nuw through decomposed expressions (#106512)

When we decompose the GEP offset expression, and the arithmetic is not
performed using nuw operations, we cannot retain the nuw flag on the
decomposed GEP.

For example, if we have `gep nuw p, (a-1)`, this is not at all the same
as `gep nuw (gep nuw p, a), -1`.

Fix this by tracking NUW through linear expression decomposition,
similarly to what we already do for the NSW flag.

This fixes the miscompilation reported in
https://github.com/llvm/llvm-project/pull/105496#issuecomment-2315322220.

show more ...

[BasicAA] Use nuw attribute of GEPs (#98608)

Use the nuw attribute of GEPs to prove that pointers do not alias, in
cases matching the following:

+ + +
|

[BasicAA] Use nuw attribute of GEPs (#98608)

Use the nuw attribute of GEPs to prove that pointers do not alias, in
cases matching the following:

+ + +
| BaseOffset | +<nuw> Indices |
---------------->|-------------------->|
|-->V2Size | |-------> V1Size
LHS RHS

If the difference between pointers is Offset +<nuw> Indices then we know
that the addition does not wrap the pointer index type (add nuw) and the
constant Offset is a lower bound on the distance between the pointers. We
can then prove NoAlias via Offset u>= V2Size.

show more ...

BasicAA: Fix assert when indexing address spaces with different sizes (#103713)

Fixes #103500

[BasicAA] Remove unused variables (NFC)

Split out from #98608.

[BasicAA] Make use of nusw+nuw -> nneg implication (#102141)

If the GEP is both nuw and inbounds/nusw, the offset is non-negative.
Pass this information to CastedValue and make use of it when deter

[BasicAA] Make use of nusw+nuw -> nneg implication (#102141)

If the GEP is both nuw and inbounds/nusw, the offset is non-negative.
Pass this information to CastedValue and make use of it when determining
the value range.

Proof for nusw+nuw->nneg: https://alive2.llvm.org/ce/z/a_CKAw
Proof for the test case: https://alive2.llvm.org/ce/z/yJ3ymP

show more ...

[BasicAA] Check nusw instead of inbounds

For the offset scaling, this is sufficient to guarantee nsw. The
other checks for inbounds in this file do need proper inbounds.

[BasicAA] Fix handling of indirect assumption based results (#100130)

If a result is potentially based on a not yet proven assumption,
BasicAA will remember it inside AssumptionBasedResults and rem

[BasicAA] Fix handling of indirect assumption based results (#100130)

If a result is potentially based on a not yet proven assumption,
BasicAA will remember it inside AssumptionBasedResults and remove
the cache entry if an assumption higher up is later disproved.
However, we currently miss the case where another cache entry ends
up depending on such an AssumptionBased result.

Fix this by introducing an additional AssumptionBased state for
cache entries. If such a result is used, we'll still increment
AAQI.NumAssumptionUses, which means that the using entry will
also become AssumptionBased and be cleared if the assumption is
disproved.

At the end of the root query, convert remaining AssumptionBased
results into definitive results.

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

show more ...

[IR] Add getDataLayout() helpers to Function and GlobalValue (#96919)

Similar to https://github.com/llvm/llvm-project/pull/96902, this adds
`getDataLayout()` helpers to Function and GlobalValue, re

[IR] Add getDataLayout() helpers to Function and GlobalValue (#96919)

Similar to https://github.com/llvm/llvm-project/pull/96902, this adds
`getDataLayout()` helpers to Function and GlobalValue, replacing the
current `getParent()->getDataLayout()` pattern.

show more ...

[BasicAA] Consider 'nneg' flag when comparing CastedValues (#94129)

Any of the `zext` bits in a `zext nneg` can be converted to `sext` but
when checking if casts are compatible `BasicAA` fails to t

[BasicAA] Consider 'nneg' flag when comparing CastedValues (#94129)

Any of the `zext` bits in a `zext nneg` can be converted to `sext` but
when checking if casts are compatible `BasicAA` fails to take into
account `nneg`. This change adds tracking of `nneg` to the `CastedValue`
struct and ensures that `sext` and `zext` bits are treated as
interchangeable when either `CastedValue` has a `nneg`. When
distributing casted values in `GetLinearExpression` we conservatively
discard the `nneg` from the `CastedValue`, except in the case of `shl
nsw`, where we know the sign has not changed to negative.

show more ...

[SimplifyQuery] Avoid PatternMatch.h include (NFC)

Move the one method that uses it out of line. This is primarily to
reduce the number of files to rebuild when changing PatternMatch.h.

[ValueTracking] Restore isKnownNonZero parameter order. (#88873)

Prior to #85863, the required parameters of llvm::isKnownNonZero were
Value and DataLayout. After, they are Value, Depth, and Simpli

[ValueTracking] Restore isKnownNonZero parameter order. (#88873)

Prior to #85863, the required parameters of llvm::isKnownNonZero were
Value and DataLayout. After, they are Value, Depth, and SimplifyQuery,
where SimplifyQuery is implicitly constructible from DataLayout. The
change to move Depth before SimplifyQuery needed callers to be updated
unnecessarily, and as commented in #85863, we actually want Depth to be
after SimplifyQuery anyway so that it can be defaulted and the caller
does not need to specify it.

show more ...

[ValueTracking] Convert `isKnownNonZero` to use SimplifyQuery (#85863)

This patch converts `isKnownNonZero` to use SimplifyQuery. Then we can
use the context information from `DomCondCache`.

Fix

[ValueTracking] Convert `isKnownNonZero` to use SimplifyQuery (#85863)

This patch converts `isKnownNonZero` to use SimplifyQuery. Then we can
use the context information from `DomCondCache`.

Fixes https://github.com/llvm/llvm-project/issues/85823.
Alive2: https://alive2.llvm.org/ce/z/QUvHVj

show more ...

[BasicAA] Treat different VScale intrinsics as the same value. (#81152)

The IR may contain multiple llvm.vscale intrinsics that have not been CSEd.
This patch ensures that multiple vscales can be t

[BasicAA] Treat different VScale intrinsics as the same value. (#81152)

The IR may contain multiple llvm.vscale intrinsics that have not been CSEd.
This patch ensures that multiple vscales can be treated the same, either in the
decomposition of geps and when we subtract one decomposition from another.

show more ...

[BasicAA] Check for Overflow using vscale_range (#81144)

This extends #80818 when IsNSW is lost (possibly due to looking through
multiple GEPs), to check the vscale_range for an access that will no

[BasicAA] Check for Overflow using vscale_range (#81144)

This extends #80818 when IsNSW is lost (possibly due to looking through
multiple GEPs), to check the vscale_range for an access that will not
overflow even with the maximum range.

show more ...

[BasicAA] Fix Scale check in vscale aliasing. (#81174)

This is a fix for #80818, as pointed out in #81144 it should be checking
the abs of Scale. The added test changes from NoAlias to MayAlias.

[BasicAA] Scalable offset with scalable typesize. (#80818)

This patch adds a simple alias analysis check for accesses that are scalable
with a offset between them that is also trivially scalable (t

[BasicAA] Scalable offset with scalable typesize. (#80818)

This patch adds a simple alias analysis check for accesses that are scalable
with a offset between them that is also trivially scalable (there are no other
constant/variable offsets). We essentially divide each side by vscale and are
left needing to check that the offset >= typesize.

show more ...

[BasicAA] Handle scalable type sizes with constant offsets (#80445)

This is a separate, but related issue to #69152 that was attempting to improve
AA with scalable dependency distances. This patch

[BasicAA] Handle scalable type sizes with constant offsets (#80445)

This is a separate, but related issue to #69152 that was attempting to improve
AA with scalable dependency distances. This patch attempts to improve when
there are scalable accesses with a constant offset between them. We happen to
get a report of such a thing recently, where so long as the vscale_range is
known, the maximum size of the access can be assessed and better aliasing
results can be returned.

The Upper range of the vscale_range, along with known part of the typesize are
used to prove that Off >= CR.upper * LSize. It does not try to produce
PartialAlias results at the moment from the lower vscale_range. It also enables
the added benefit of allowing better alias analysis when the RHS of the two
values is scalable, but the LHS is normal and can be treated like any other
aliasing query.

show more ...

[AA][JumpThreading] Don't use DomTree for AA in JumpThreading (#79294)

JumpThreading may perform AA queries while the dominator tree is not up
to date, which may result in miscompilations.

Fix t

[AA][JumpThreading] Don't use DomTree for AA in JumpThreading (#79294)

JumpThreading may perform AA queries while the dominator tree is not up
to date, which may result in miscompilations.

Fix this by adding a new AAQI option to disable the use of the dominator
tree in BasicAA.

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

show more ...