[BasicAA] Make sure context instruction is symmetric

D71264 started using a context instruction in a computeKnownBits()
call. However, if aliasing between two GEPs is checked, then the
choice of con

[BasicAA] Make sure context instruction is symmetric

D71264 started using a context instruction in a computeKnownBits()
call. However, if aliasing between two GEPs is checked, then the
choice of context instruction will be different for alias(GEP1, GEP2)
and alias(GEP2, GEP1), which is not supposed to happen.

Resolve this by remembering which GEP a certain VarIndex belongs to,
and use that as the context instruction. This makes the choice of
context instruction predictable and symmetric.

It should be noted that this choice of context instruction is
non-optimal (just like the previous choice): The AA query result is
only valid at points that are reachable from *both* instructions.
Using either one of them is conservatively correct, but a larger
context may also be valid to use.

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

show more ...

Revert "[BasicAA] Handle two unknown sizes for GEPs"

Temporarily revert commit 8b1c4e310c2f9686cad925ad81d8e2be10a1ef3c.

After 8b1c4e310c2f the compile-time for `MultiSource/Benchmarks/MiBench/cons

Revert "[BasicAA] Handle two unknown sizes for GEPs"

Temporarily revert commit 8b1c4e310c2f9686cad925ad81d8e2be10a1ef3c.

After 8b1c4e310c2f the compile-time for `MultiSource/Benchmarks/MiBench/consumer-lame`
dramatically increases with -O3 & LTO, causing issues for builders with
that configuration.

I filed PR48553 with a smallish reproducer that shows a 10-100x compile
time increase.

show more ...

[BasicAA] Handle known non-zero variable index

BasicAA currently handles cases like Scale*V0 + (-Scale)*V1 where
V0 != V1, but does not handle the simpler case of Scale*V with
V != 0. Add it based o

[BasicAA] Handle known non-zero variable index

BasicAA currently handles cases like Scale*V0 + (-Scale)*V1 where
V0 != V1, but does not handle the simpler case of Scale*V with
V != 0. Add it based on an isKnownNonZero() call.

I'm not passing a context instruction for now, because the existing
approach of always using GEP1 for context could result in symmetry
issues.

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

show more ...

[BasicAA] Make non-equal index handling simpler to extend (NFC)

[BasicAA] Handle two unknown sizes for GEPs

If we have two unknown sizes and one GEP operand and one non-GEP
operand, then we currently simply return MayAlias. The comment says
we can't do anything

[BasicAA] Handle two unknown sizes for GEPs

If we have two unknown sizes and one GEP operand and one non-GEP
operand, then we currently simply return MayAlias. The comment says
we can't do anything useful ... but we can! We can still check that
the underlying objects are different (and do so for the GEP-GEP case).

To reduce the compile-time impact, this a) checks this early, before
doing the relatively expensive GEP decomposition that will not be
used and b) doesn't do the check if the other operand is a phi or
select. In that case, the phi/select will already recurse, so this
would just do two slightly different recursive walks that arrive at
the same roots.

Compile-time is still a bit of a mixed bag: https://llvm-compile-time-tracker.com/compare.php?from=624af932a808b363a888139beca49f57313d9a3b&to=845356e14adbe651a553ed11318ddb5e79a24bcd&stat=instructions
On average this is a small improvement, but sqlite with ThinLTO has
a 0.5% regression (lencod has a 1% improvement).

The BasicAA test case checks this by using two memsets with unknown
size. However, the more interesting case where this is useful is
the LoopVectorize test case, as analysis of accesses in loops tends
to always us unknown sizes.

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

show more ...

[BasicAA] Migrate "same base pointer" logic to decomposed GEPs

BasicAA has some special bit of logic for "same base pointer" GEPs
that performs a structural comparison: It only looks at two GEPs
wit

[BasicAA] Migrate "same base pointer" logic to decomposed GEPs

BasicAA has some special bit of logic for "same base pointer" GEPs
that performs a structural comparison: It only looks at two GEPs
with the same base (as opposed to two GEP chains with a MustAlias
base) and compares their indexes in a limited way. I generalized
part of this code in D91027, and this patch merges the remainder
into the normal decomposed GEP logic.

What this code ultimately wants to do is to determine that
gep %base, %idx1 and gep %base, %idx2 don't alias if %idx1 != %idx2,
and the access size fits within the stride.

We can express this in terms of a decomposed GEP expression with
two indexes scale*%idx1 + -scale*%idx2 where %idx1 != %idx2, and
some appropriate checks for sizes and offsets.

This makes the reasoning slightly more powerful, and more
importantly brings all the GEP logic under a common umbrella.

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

show more ...

[BasicAA] Fix a bug with relational reasoning across iterations

Due to the recursion through phis basicaa does, the code needs to be extremely careful not to reason about equality between values whi

[BasicAA] Fix a bug with relational reasoning across iterations

Due to the recursion through phis basicaa does, the code needs to be extremely careful not to reason about equality between values which might represent distinct iterations. I'm generally skeptical of the correctness of the whole scheme, but this particular patch fixes one particular instance which is demonstrateable incorrect.

Interestingly, this appears to be the second attempted fix for the same issue. The former fix is incomplete and doesn't address the actual issue.

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

show more ...

[BasicAA] Generalize recursive phi alias analysis

For recursive phis, we skip the recursive operands and check that
the remaining operands are NoAlias with an unknown size. Currently,
this is limite

[BasicAA] Generalize recursive phi alias analysis

For recursive phis, we skip the recursive operands and check that
the remaining operands are NoAlias with an unknown size. Currently,
this is limited to inbounds GEPs with positive offsets, to
guarantee that the recursion only ever increases the pointer.

Make this more general by only requiring that the underlying object
of the phi operand is the phi itself, i.e. it it based on itself in
some way. To compensate, we need to use a beforeOrAfterPointer()
location size, as we no longer have the guarantee that the pointer
is strictly increasing.

This allows us to handle some additional cases like negative geps,
geps with dynamic offsets or geps that aren't inbounds.

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

show more ...

[BasicAA] Remove unnecessary known size requirement

The size requirement on V2 was present because it was not clear
whether an unknown size would allow an access before the start of
V2, which could

[BasicAA] Remove unnecessary known size requirement

The size requirement on V2 was present because it was not clear
whether an unknown size would allow an access before the start of
V2, which could then overlap. This is clarified since D91649: In
this part of BasicAA, all accesses can occur only after the base
pointer, even if they have unknown size.

This makes the positive and negative offset cases symmetric.

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

show more ...

Revert "[BasicAA] Fix BatchAA results for phi-phi assumptions"

This reverts commit 8166ed1a7a26ee8ea8db9005cc8ee5d156adad9b,
as it caused some compilations to hang/loop indefinitely, see
https://rev

Revert "[BasicAA] Fix BatchAA results for phi-phi assumptions"

This reverts commit 8166ed1a7a26ee8ea8db9005cc8ee5d156adad9b,
as it caused some compilations to hang/loop indefinitely, see
https://reviews.llvm.org/D91936 for details.

show more ...

[BasicAA] Fix BatchAA results for phi-phi assumptions

Add a flag that disables caching when computing aliasing results
potentially based on a phi-phi NoAlias assumption. We'll still
insert cache ent

[BasicAA] Fix BatchAA results for phi-phi assumptions

Add a flag that disables caching when computing aliasing results
potentially based on a phi-phi NoAlias assumption. We'll still
insert cache entries temporarily to catch infinite recursion,
but will drop them afterwards, so they won't persist in BatchAA.

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

show more ...

[AA] Split up LocationSize::unknown()

Currently, we have some confusion in the codebase regarding the
meaning of LocationSize::unknown(): Some parts (including most of
BasicAA) assume that LocationS

[AA] Split up LocationSize::unknown()

Currently, we have some confusion in the codebase regarding the
meaning of LocationSize::unknown(): Some parts (including most of
BasicAA) assume that LocationSize::unknown() only allows accesses
after the base pointer. Some parts (various callers of AA) assume
that LocationSize::unknown() allows accesses both before and after
the base pointer (but within the underlying object).

This patch splits up LocationSize::unknown() into
LocationSize::afterPointer() and LocationSize::beforeOrAfterPointer()
to make this completely unambiguous. I tried my best to determine
which one is appropriate for all the existing uses.

The test changes in cs-cs.ll in particular illustrate a previously
clearly incorrect AA result: We were effectively assuming that
argmemonly functions were only allowed to access their arguments
after the passed pointer, but not before it. I'm pretty sure that
this was not intentional, and it's certainly not specified by
LangRef that way.

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

show more ...

[BasicAA] Avoid unnecessary cache update (NFC)

If the final recursive query returns MayAlias as well, there is
no need to update the cache (which already stores MayAlias).

[BasicAA] Remove unnecessary sextOrSelf (NFC)

We are doing a sextOrTrunc directly afterwards, so this seems
useless. There is a multiplication in between, but truncating
before or after the multipli

[BasicAA] Remove unnecessary sextOrSelf (NFC)

We are doing a sextOrTrunc directly afterwards, so this seems
useless. There is a multiplication in between, but truncating
before or after the multiplication should not make a difference.

show more ...

[BasicAA] Return DecomposedGEP (NFC)

Instead of requiring the caller to initialize the DecomposedGEP
structure and then passing it in by reference, make
DecomposeGEPExpression() responsible for init

[BasicAA] Return DecomposedGEP (NFC)

Instead of requiring the caller to initialize the DecomposedGEP
structure and then passing it in by reference, make
DecomposeGEPExpression() responsible for initializing and returning
the structure.

show more ...

[BasicAA] Remove some intermediate variables (NFC)

Use DecompGEP1.Offset instead of GEP1BaseOffset, etc. I found the
asymmetry of modifying DecompGEP1.VarIndices, but not modifying
DecompGEP1.Offset

[BasicAA] Remove some intermediate variables (NFC)

Use DecompGEP1.Offset instead of GEP1BaseOffset, etc. I found the
asymmetry of modifying DecompGEP1.VarIndices, but not modifying
DecompGEP1.Offset odd here.

show more ...

[BasicAA] Remove stale FIXME (NFC)

If aliasGEP returns MayAlias, the code does fall through to
aliasPHI etc, so this FIXME is no longer applicable.

[MemLoc] Use hasValue() method more (NFC)

Followup to 7de7c40898a8f815d661781c92757f93fa4c6e5b. I previously
removed a number of == comparisons to LocationSize::unknown(), but
missed these != compar

[MemLoc] Use hasValue() method more (NFC)

Followup to 7de7c40898a8f815d661781c92757f93fa4c6e5b. I previously
removed a number of == comparisons to LocationSize::unknown(), but
missed these != comparisons.

show more ...

[MemLoc] Use hasValue() method (NFC)

Instead of comparing to LocationSize::unknown(), prefer calling
the hasValue() method instead, which is less reliant on
implementation details.

[MemLoc] Require LocationSize argument (NFC)

When constructing a MemoryLocation by hand, require that a
LocationSize is explicitly specified. D91649 will split up
LocationSize::unknown() into two di

[MemLoc] Require LocationSize argument (NFC)

When constructing a MemoryLocation by hand, require that a
LocationSize is explicitly specified. D91649 will split up
LocationSize::unknown() into two different states, and callers
should make an explicit choice regarding the kind of MemoryLocation
they want to have.

show more ...

[BasicAA] Deoptimize intrinsics don't modify memory

Similarly to assumes and guards deoptimize intrinsics are
marked as writing to ensure proper control dependencies
but they never modify any partic

[BasicAA] Deoptimize intrinsics don't modify memory

Similarly to assumes and guards deoptimize intrinsics are
marked as writing to ensure proper control dependencies
but they never modify any particular memory location.

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

show more ...

[BasicAA] Generalize base offset modulus handling

The GEP aliasing implementation currently has two pieces of code
that solve two different subsets of the same basic problem: If you
have GEPs with o

[BasicAA] Generalize base offset modulus handling

The GEP aliasing implementation currently has two pieces of code
that solve two different subsets of the same basic problem: If you
have GEPs with offsets 4*x + 0 and 4*y + 1 (assuming access size 1),
then they do not alias regardless of whether x and y are the same.

One implementation is in aliasSameBasePointerGEPs(), which looks at
this in a limited structural way. It requires both GEP base pointers
to be exactly the same, then (optionally) a number of equal indexes,
then an unknown index, then a non-equal index into a struct. This
set of limitations works, but it's overly restrictive and hides the
core property we're trying to exploit.

The second implementation is part of aliasGEP() itself and tries to
find a common modulus in the scales, so it can then check that the
constant offset doesn't overlap under modular arithmetic. The second
implementation has the right idea of what the general problem is,
but effectively only considers power of two factors in the scales
(while aliasSameBasePointerGEPs also works with non-pow2 struct sizes.)

What this patch does is to adjust the aliasGEP() implementation to
instead find the largest common factor in all the scales (i.e. the GCD)
and use that as the modulus.

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

show more ...

[BasicAA] Make alias GEP positive offset handling symmetric

aliasGEP() currently implements some special handling for the case
where all variable offsets are positive, in which case the constant
off

[BasicAA] Make alias GEP positive offset handling symmetric

aliasGEP() currently implements some special handling for the case
where all variable offsets are positive, in which case the constant
offset can be taken as the minimal offset. However, it does not
perform the same handling for the all-negative case. This means that
the alias-analysis result between two GEPs is asymmetric:
If GEP1 - GEP2 is all-positive, then GEP2 - GEP1 is all-negative,
and the first will result in NoAlias, while the second will result
in MayAlias.

Apart from producing sub-optimal results for one order, this also
violates our caching assumption. In particular, if BatchAA is used,
the cached result depends on the order of the GEPs in the first query.
This results in an inconsistency in BatchAA and AA results, which
is how I noticed this issue in the first place.

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

show more ...

[BasicAA] Remove unnecessary size limitation

We're dropping a common offset from both GEPs here. It's not
necessary for the access sizes to be the same as well.

[BasicAA] Remove checks for GEP decomposition limit reached

The GEP aliasing code currently checks for the GEP decomposition
limit being reached (i.e., we did not reach the "final" underlying
object

[BasicAA] Remove checks for GEP decomposition limit reached

The GEP aliasing code currently checks for the GEP decomposition
limit being reached (i.e., we did not reach the "final" underlying
object). As far as I can see, these checks are not necessary. It is
perfectly fine to work with a GEP whose base can still be further
decomposed.

Looking back through the commit history, these checks were originally
introduced in 1a444489e9d90915cfdda0720489893896ef1503. However, I
believe that the problem this was intended to address was later
properly fixed with 1726fc698ccb85fe4bb23c200a50f28b57fc53cb, and
the checks are no longer necessary since then (and were not the
right fix in the first place).

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

show more ...