[Analysis] allow caller to choose signed/unsigned when computing constant range

We should not lose analysis precision if an 'add' has both no-wrap
flags (nsw and nuw) compared to just one or the oth

[Analysis] allow caller to choose signed/unsigned when computing constant range

We should not lose analysis precision if an 'add' has both no-wrap
flags (nsw and nuw) compared to just one or the other.

This patch is modeled on a similar construct that was added with
D59386.

I don't think it is possible to expose a problem with an unsigned
compare because of the way this was coded (nuw is handled first).

InstCombine has an assert that fires with the example from:
https://github.com/llvm/llvm-project/issues/52884
...because it was expecting InstSimplify to handle this kind of
pattern with an smax.

Fixes #52884

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

show more ...

[AA] Correctly maintain the sign of PartiaAlias offset

Preserve the invariant that offset reported in the case of a
`PartialAlias` between `Loc1` and `Loc2`, is such that
`Loc1 + Offset = Loc2`, whe

[AA] Correctly maintain the sign of PartiaAlias offset

Preserve the invariant that offset reported in the case of a
`PartialAlias` between `Loc1` and `Loc2`, is such that
`Loc1 + Offset = Loc2`, where `Loc1` and `Loc2` are the first and
the second argument, respectively, in alias queries.

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

show more ...

[BasicAA] Use index size instead of pointer size

When accumulating the GEP offset in BasicAA, we should use the
pointer index size rather than the pointer size.

Differential Revision: https://revie

[BasicAA] Use index size instead of pointer size

When accumulating the GEP offset in BasicAA, we should use the
pointer index size rather than the pointer size.

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

show more ...

[BasicAA] Check known access sizes earlier (NFC)

All heuristics for variable accesses require both access sizes to
be known, so check this once at the start, rather than for each
particular heuristi

[BasicAA] Check known access sizes earlier (NFC)

All heuristics for variable accesses require both access sizes to
be known, so check this once at the start, rather than for each
particular heuristic.

show more ...

[BasicAA] Use early returns (NFC)

Reduce nesting in aliasGEP() a bit by returning early.

[BasicAA] Use saturating multiply on range if nsw

If we know that the var * scale multiplication is nsw, we can use
a saturating multiplication on the range (as a good approximation
of an nsw multip

[BasicAA] Use saturating multiply on range if nsw

If we know that the var * scale multiplication is nsw, we can use
a saturating multiplication on the range (as a good approximation
of an nsw multiply). This recovers some cases where the fix from
D112611 is unnecessarily strict. (This can be further strengthened
by using a saturating add, but we currently don't track all the
necessary information for that.)

This exposes an issue in our NSW tracking for multiplies. The code
was assuming that (X +nsw Y) *nsw Z results in
(X *nsw Z) +nsw (Y *nsw Z) -- however, it is possible that the
distributed multiplications overflow, even if the non-distributed
one does not. We should discard the nsw flag if the the offset is
non-zero. If we just have (X *nsw Y) *nsw Z then concluding
X *nsw (Y *nsw Z) is fine.

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

show more ...

[BasicAA] Extract linear expression multiplication (NFC)

Extract a common method for multiplying a linear expression by a
factor.

[BasicAA] Don't treat non-inbounds GEP as nsw

The scale multiplication is only guaranteed to be nsw if the GEP
is inbounds (or the multiplication is trivial). Previously we were
only considering exp

[BasicAA] Don't treat non-inbounds GEP as nsw

The scale multiplication is only guaranteed to be nsw if the GEP
is inbounds (or the multiplication is trivial). Previously we were
only considering explicit muls in GEP indices.

show more ...

[BasicAA] Remove misleading overflow check

GEP decomposition currently checks whether the multiplication of
the linear expression offset and GEP scale overflows. However, if
everything else works co

[BasicAA] Remove misleading overflow check

GEP decomposition currently checks whether the multiplication of
the linear expression offset and GEP scale overflows. However, if
everything else works correctly, this overflow check is both
unnecessary and dangerously misleading. While it will avoid an
overflow in Scale * Offset in particular, other parts of the
calculation (including those on dynamic values) may still overflow.
The code working on the decomposed GEPs is responsible for ensuring
that it remains correct in the presence of overflow. D112611 fixes
the last issue of that kind that I'm aware of (in fact, the overflow
check was originally introduced to work around precisely that issue).

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

show more ...

[BasicAA] Handle known bits as ranges

BasicAA currently tries to determine that the offset is positive by
checking whether all variable indices are positive based on known
bits, multiplied by a posi

[BasicAA] Handle known bits as ranges

BasicAA currently tries to determine that the offset is positive by
checking whether all variable indices are positive based on known
bits, multiplied by a positive scale. However, this is incorrect
if the scale multiplication might overflow. In the modified test
case the original value is positive, but may be negative after a
left shift.

Fix this by converting known bits into a constant range and reusing
the range-based logic, which handles overflow correctly.

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

show more ...

[BasicAA] Make range check more precise

Make the range check more precise by calculating the range of
potentially accessed bytes for both accesses and checking whether
their intersection is empty. I

[BasicAA] Make range check more precise

Make the range check more precise by calculating the range of
potentially accessed bytes for both accesses and checking whether
their intersection is empty. In that case there can be no overlap
between the accesses and the result is NoAlias.

This is more powerful than the previous approach, because it can
deal with sign-wrapped ranges. In the test case the original range
is [-1, INT_MAX] but becomes [0, INT_MIN] after applying the offset.
This is a wrapping range, so getSignedMin/getSignedMax will treat
it as a full range. However, the range excludes the elements
[INT_MIN+1, -1], which is enough to prove NoAlias with an access
at offset -1.

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

show more ...

[BasicAA] Use ranges for more than one index

D109746 made BasicAA use range information to determine the
minimum/maximum GEP offset. However, it was limited to the case of
a single variable index. T

[BasicAA] Use ranges for more than one index

D109746 made BasicAA use range information to determine the
minimum/maximum GEP offset. However, it was limited to the case of
a single variable index. This patch extends support to multiple
indices by adding all the ranges together.

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

show more ...

[BasicAA] Model implicit trunc of GEP indices

GEP indices larger than the GEP index size are implicitly truncated
to the index size. BasicAA currently doesn't model this, resulting
in incorrect alia

[BasicAA] Model implicit trunc of GEP indices

GEP indices larger than the GEP index size are implicitly truncated
to the index size. BasicAA currently doesn't model this, resulting
in incorrect alias analysis results.

Fix this by explicitly modelling truncation in CastedValue in the
same way we do zext and sext. Additionally we need to disable a
number of optimizations for truncated values, in particular
"non-zero" and "non-equal" may no longer hold after truncation.
I believe the constant offset heuristic is also not necessarily
correct for truncated values, but wasn't able to come up with a
test for that one.

A possible followup here would be to use the new mechanism to
model explicit trunc as well (which should be much more common,
as it is the canonical form). This is straightforward, but omitted
here to separate the correctness fix from the analysis improvement.

(Side note: While I say "index size" above, BasicAA currently uses
the pointer size instead. Something for another day...)

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

show more ...

[ConstantRange] Add fast signed multiply

The multiply() implementation is very slow -- it performs six
multiplications in double the bitwidth, which means that it will
typically work on allocated AP

[ConstantRange] Add fast signed multiply

The multiply() implementation is very slow -- it performs six
multiplications in double the bitwidth, which means that it will
typically work on allocated APInts and bypass fast-path
implementations. Add an additional implementation that doesn't
try to produce anything better than a full range if overflow is
possible. At least for the BasicAA use-case, we really don't care
about more precise modeling of overflow behavior. The current
use of multiply() is fine while the implementation is limited to
a single index, but extending it to the multiple-index case makes
the compile-time impact untenable.

show more ...

[BasicAA] Rename ExtendedValue to CastedValue (NFC)

As suggested on D110977, rename ExtendedValue to CastedValue,
because it will contain more than just extensions in the future.

[BasicAA] Improve scalable vector handling

Currently, DecomposeGEP() bails out on the whole decomposition if
it encounters a scalable GEP type anywhere. However, it is fine to
still analyze other GE

[BasicAA] Improve scalable vector handling

Currently, DecomposeGEP() bails out on the whole decomposition if
it encounters a scalable GEP type anywhere. However, it is fine to
still analyze other GEPs that we look through before hitting the
scalable GEP. This does mean that the decomposed GEP base is no
longer required to be the same as the underlying object. However,
I don't believe this property is necessary for correctness anymore.

This allows us to compute slightly more precise aliasing results
for GEP chains containing scalable vectors, though my primary
interest here is simplifying the code.

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

show more ...

re-land "[AA] Teach BasicAA to recognize basic GEP range information."

Now that PR52104 is fixed.

[BasicAA] Use base of decomposed GEP in recursive queries (NFC)

DecompGEP.Base and UnderlyingV are currently always the same.
However, logically DecompGEP.Base is the right value to use here,
becaus

[BasicAA] Use base of decomposed GEP in recursive queries (NFC)

DecompGEP.Base and UnderlyingV are currently always the same.
However, logically DecompGEP.Base is the right value to use here,
because the decomposed offset is relative to that base.

show more ...

[BasicAA] Don't unnecessarily extend pointer size

BasicAA GEP decomposition currently performs all calculation on the
maximum pointer size, but at least 64-bit, with an option to double
the size. Th

[BasicAA] Don't unnecessarily extend pointer size

BasicAA GEP decomposition currently performs all calculation on the
maximum pointer size, but at least 64-bit, with an option to double
the size. The code comment claims that this improves analysis power
when working with uint64_t indices on 32-bit systems. However, I don't
see how this can be, at least while maintaining correctness:

When working on canonical code, the GEP indices will have GEP index
size. If the original code worked on uint64_t with a 32-bit size_t,
then there will be truncs inserted before use as a GEP index. Linear
expression decomposition does not look through truncs, so this will
be an opaque value as far as GEP decomposition is concerned. Working
on a wider pointer size does not help here (or have any effect at all).

When working on non-canonical code (before first InstCombine), the
GEP indices are implicitly truncated to GEP index size. The BasicAA
code currently just ignores this fact completely, and pretends that
this truncation doesn't happen. This is incorrect and will be
addressed by D110977.

I believe that for correctness reasons, it is important to work on
the actual GEP index size to properly model potential overflow.
BasicAA tries to patch over the fact that it uses the wrong size
(see adjustToPointerSize), but it only does that in limited cases
(only for constant values, and not all of them either). I'd like to
move this code towards always working on the correct size, and
dropping these artificial pointer size adjustments is the first step
towards that.

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

show more ...

Fix incomplete conflict resolution in ff41fc07b12bd7bf3c8cd238824b16b1066fe5a0

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

We have found a miscompile with this change, reverting while working on a
reproducer.

This reverts commit 455b60ccfbfdbb5d2b652

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

We have found a miscompile with this change, reverting while working on a
reproducer.

This reverts commit 455b60ccfbfdbb5d2b652666050544c31e6673b1.

show more ...

[BasicAA] Ignore CanBeFreed in minimal extent reasoning

When determining NoAlias based on object size and dereferenceability
information, we can ignore frees for the same reason we can ignore
possib

[BasicAA] Ignore CanBeFreed in minimal extent reasoning

When determining NoAlias based on object size and dereferenceability
information, we can ignore frees for the same reason we can ignore
possible null pointers (if null is not a valid pointer): Actually
accessing the null pointer / freed pointer would be immediate UB,
and AA results are only valid under the assumption of an access.

This addresses a minor regression from D110745.

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

show more ...

[Analysis, CodeGen] Migrate from arg_operands to args (NFC)

Note that arg_operands is considered a legacy name. See
llvm/include/llvm/IR/InstrTypes.h for details.

[BasicAA] Move more extension logic into ExtendedValue (NFC)

Add methods to appropriately extend KnownBits/ConstantRange there,
same as with APInt. Also clean up the known bits handling by
actually

[BasicAA] Move more extension logic into ExtendedValue (NFC)

Add methods to appropriately extend KnownBits/ConstantRange there,
same as with APInt. Also clean up the known bits handling by
actually doing that extension rather than checking ZExtBits. This
doesn't matter now, but becomes relevant once truncation is
involved.

show more ...

[BasicAA] Use ExtendedValue in VariableGEPIndex (NFC)

Use the ExtendedValue structure which is used for LinearExpression
in VariableGEPIndex as well.