[BasicAA] Unify struct/other offset (NFC)

The distinction between StructOffset and OtherOffset has been
originally introduced by 82069c44ca39df9d506e16bfb0ca2481866dd0bb,
which applied different rea

[BasicAA] Unify struct/other offset (NFC)

The distinction between StructOffset and OtherOffset has been
originally introduced by 82069c44ca39df9d506e16bfb0ca2481866dd0bb,
which applied different reasoning to both offset kinds. However,
this distinction was not actually correct, and has been fixed by
c84e77aeaefccb8d0c4c508b8017dcad80607f53. Since then, we only ever
consider the sum StructOffset + OtherOffset, so we may as well
store it in that form directly.

show more ...

[BasicAA] Use smul_ov helper (NFCI)

Instead of performing the multiplication in double the bit width
and using active bits to determine overflow, use the existing
smul_ov() APInt method to detect ov

[BasicAA] Use smul_ov helper (NFCI)

Instead of performing the multiplication in double the bit width
and using active bits to determine overflow, use the existing
smul_ov() APInt method to detect overflow.

The smul_ov() implementation is not particularly efficient, but
it's still better than doing this a wide, usually 128-bit, type.

show more ...

[BasicAA] Avoid duplicate cache lookup (NFCI)

Rather than performing the cache lookup with both possible orders
for the locations, use the same canonicalization as the other
AliasCache lookups in Ba

[BasicAA] Avoid duplicate cache lookup (NFCI)

Rather than performing the cache lookup with both possible orders
for the locations, use the same canonicalization as the other
AliasCache lookups in BasicAA.

show more ...

[BasicAA] Fix caching in the presence of phi cycles

Any time we insert a block into VisitedPhiBBs, previously cached
values may no longer be valid for the recursive alias queries. As
such, perform t

[BasicAA] Fix caching in the presence of phi cycles

Any time we insert a block into VisitedPhiBBs, previously cached
values may no longer be valid for the recursive alias queries. As
such, perform them using an empty AAQueryInfo.

Note that if we recurse to the same phi, the block will already
be inserted, so we reuse the old AAQueryInfo, and thus still
protect against infinite recursion.

This problem can appear with with an without BatchAA, but is more
likely to occur with BatchAA, as more values are cached.

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

show more ...

[BasicAA] Only add visited phi blocks temporarily

Visited phi blocks only need to be added for the duration of the
recursive alias queries, they should not leak into following code.

Once again, whi

[BasicAA] Only add visited phi blocks temporarily

Visited phi blocks only need to be added for the duration of the
recursive alias queries, they should not leak into following code.

Once again, while this also improves analysis precision, this is
mainly intended to clarify the applicability scope of VisitedPhiBBs.

show more ...

[BasicAA] Don't track visited blocks for phi-phi alias query

We only need the VisitedPhiBBs to disambiguate comparisons of
values from two different loop iterations. If we're comparing
two phis from

[BasicAA] Don't track visited blocks for phi-phi alias query

We only need the VisitedPhiBBs to disambiguate comparisons of
values from two different loop iterations. If we're comparing
two phis from the same basic block in lock-step, the compared
values will always be on the same iteration.

While this also increases precision, this is mainly intended
to clarify the scope of VisitedPhiBBs.

show more ...

[BasicAA] Accept AATags by const reference (NFC)

Rather than swapping the value, the sizes, the AA tags and the
underlying objects multiple times, invoke the helper methods
with swapped arguments.

[AA] Add helper to update result (NFC)

This pattern was repeated a few times, and for some reason always
using insert or try_emplace, even though we know in advance that
we're looking for an existin

[AA] Add helper to update result (NFC)

This pattern was repeated a few times, and for some reason always
using insert or try_emplace, even though we know in advance that
we're looking for an existing entry and not trying to create a
new one.

show more ...

[BasicAA] Avoid alias query if result cannot be used (NFCI)

Rather then querying first and then checking additional conditions,
check the conditions first. They are much cheaper than the alias
query.

[BasicAA] Fix stale comment (NFC)

DataLayout is always around...

[NFC][CaptureTracking] Move static function isNonEscapingLocalObject to llvm namespace

Function isNonEscapingLocalObject is a static one within BasicAliasAnalysis.cpp.
It wraps around PointerMayBeCa

[NFC][CaptureTracking] Move static function isNonEscapingLocalObject to llvm namespace

Function isNonEscapingLocalObject is a static one within BasicAliasAnalysis.cpp.
It wraps around PointerMayBeCaptured of CaptureTracking, checking whether a pointer
is to a function-local object, which never escapes from the function.

Although at the moment, isNonEscapingLocalObject is used only by BasicAliasAnalysis,
its functionality can be used by other pass(es), one of which I will put up for review
very soon. Instead of copying the contents of this static function, I move it to llvm
scope, and place it amongst other functions with similar functionality in CaptureTracking.

The rationale for the location are:
- Pointer escape and pointer being captured are actually two sides of the same coin
- isNonEscapingLocalObject is wrapping around another function in CaptureTracking

Reviewed By: jdoerfert (Johannes Doerfert)

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

show more ...

[LangRef] Adjust guarantee for llvm.memcpy to also allow equal arguments.

This adjusts the description of `llvm.memcpy` to also allow operands
to be equal. This is in line with what Clang currently

[LangRef] Adjust guarantee for llvm.memcpy to also allow equal arguments.

This adjusts the description of `llvm.memcpy` to also allow operands
to be equal. This is in line with what Clang currently expects.

This change is intended to be temporary and followed by re-introduce
a variant with the non-overlapping guarantee for cases where we can
actually ensure that property in the front-end.

See the links below for more details:
http://lists.llvm.org/pipermail/cfe-dev/2020-August/066614.html
and PR11763.

Reviewed By: nikic

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

show more ...

[BasicAA] Enable -basic-aa-recphi by default

This option was added a while back, to help improve AA around pointer
phi loops. It looks for phi(gep(phi, const), x) loops, checking if x can
then prove

[BasicAA] Enable -basic-aa-recphi by default

This option was added a while back, to help improve AA around pointer
phi loops. It looks for phi(gep(phi, const), x) loops, checking if x can
then prove more precise aliasing info.

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

show more ...

[NFC] Remove unused GetUnderlyingObject paramenter

Depends on D84617.

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

[NFC] GetUnderlyingObject -> getUnderlyingObject

I am going to touch them in the next patch anyway

[BasicAA] Fix -basicaa-recphi for geps with negative offsets

As shown in D82998, the basic-aa-recphi option can cause miscompiles for
gep's with negative constants. The option checks for recursive p

[BasicAA] Fix -basicaa-recphi for geps with negative offsets

As shown in D82998, the basic-aa-recphi option can cause miscompiles for
gep's with negative constants. The option checks for recursive phi, that
recurse through a contant gep. If it finds one, it performs aliasing
calculations using the other phi operands with an unknown size, to
specify that an unknown number of elements after the initial value are
potentially accessed. This works fine expect where the constant is
negative, as the size is still considered to be positive. So this patch
expands the check to make sure that the constant is also positive.

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

show more ...

Revert "[BasicAA] Enable -basic-aa-recphi by default"

This reverts commit af839a96187e3538d63ad57571e4bdf01e2b15c5.

Some issues appear to be being caused by this. Reverting whilst we
investigate.

[BasicAA] Enable -basic-aa-recphi by default

This option was added a while back, to help improve AA around pointer
phi loops. It looks for phi(gep(phi, const), x) loops, checking if x can
then prove

[BasicAA] Enable -basic-aa-recphi by default

This option was added a while back, to help improve AA around pointer
phi loops. It looks for phi(gep(phi, const), x) loops, checking if x can
then prove more precise aliasing info.

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

show more ...

BasicAAResult::constantOffsetHeuristic - pass APInt arg as const reference. NFCI.

Avoids unnecessary APInt copies and silences clang tidy warning.

[BasicAA] Fix recursive phi MustAlias calculations

With the option -basic-aa-recphi we can detect recursive phis that loop
through constant geps, which allows us to detect more no-alias case for
poi

[BasicAA] Fix recursive phi MustAlias calculations

With the option -basic-aa-recphi we can detect recursive phis that loop
through constant geps, which allows us to detect more no-alias case for
pointer IV's. If the other phi operand and the other alias value are
MustAlias though, we cannot presume that every element in the loop is
also MustAlias. We need to instead be conservative and return MayAlias.

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

show more ...

[BasicAA] Rename deprecated -basicaa to -basic-aa

Follow-up to D82607
Revert an accidental change (empty.ll) of D82683

[NewPM][BasicAA] Rename basicaa -> basic-aa, add alias

Summary:
BasicAA under the new pass manager is called "basic-aa", which fits more
with the other AA names which almost always contain a dash.

[NewPM][BasicAA] Rename basicaa -> basic-aa, add alias

Summary:
BasicAA under the new pass manager is called "basic-aa", which fits more
with the other AA names which almost always contain a dash.

Keep an alias from basicaa -> basic-aa.

Will change all references of "basicaa" to "basic-aa", then remove the
alias.

Makes check-llvm failures under NPM go from 2307 to 1867.

Reviewers: asbirlea, ychen

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[ValueTracking, BasicAA] Don't simplify instructions

GetUnderlyingObject() (and by required symmetry
DecomposeGEPExpression()) will call SimplifyInstruction() on the
passed value if other checks fai

[ValueTracking, BasicAA] Don't simplify instructions

GetUnderlyingObject() (and by required symmetry
DecomposeGEPExpression()) will call SimplifyInstruction() on the
passed value if other checks fail. This simplification is very
expensive, but has little effect in practice. This patch removes
the SimplifyInstruction call(), and replaces it with a check for
single-argument phis (which can occur in canonical IR in LCSSA
form), which is the only useful simplification case I was able to
identify.

At O3 the geomean CTMark improvement is -1.7%. The largest
improvement is SPASS with ThinLTO at -6%.

In test-suite, I see only two tests with a hash difference and
no code size difference (PAQ8p, Ptrdist), which indicates that
the simplification only ends up being useful very rarely. (I would
have liked to figure out which simplification is responsible here,
but wasn't able to spot it looking at transformation logs.)

The AMDGPU test case that is update was using two selects with
undef condition, in which case GetUnderlyingObject will return
the first select operand as the underlying object. This will of
course not happen with non-undef conditions, so this was not
testing anything realistic. Additionally this illustrates potential
unsoundness: While GetUnderlyingObject will pick the first operand,
the select might be later replaced by the second operand, resulting
in inconsistent assumptions about the undef value.

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

show more ...

Revert "[BasicAA] Use known lower bounds for index values for size based check."

This potentially related to https://bugs.llvm.org/show_bug.cgi?id=46335
and causes a slight compile-time regression.

Revert "[BasicAA] Use known lower bounds for index values for size based check."

This potentially related to https://bugs.llvm.org/show_bug.cgi?id=46335
and causes a slight compile-time regression. Revert while investigating.

This reverts commit d99a1848c4f8ca164c0c0768e10eafc850b2a68a.

show more ...

[BasicAA] Use known lower bounds for index values for size based check.

Currently, BasicAA does not exploit information about value ranges of
indexes. For example, consider the 2 pointers %a = %base

[BasicAA] Use known lower bounds for index values for size based check.

Currently, BasicAA does not exploit information about value ranges of
indexes. For example, consider the 2 pointers %a = %base and
%b = %base + %stride below, assuming they are used to access 4 elements.

If we know that %stride >= 4, we know the accesses do not alias. If
%stride is a constant, BasicAA currently gets that. But if the >= 4
constraint is encoded using an assume, it misses the NoAlias.

This patch extends DecomposedGEP to include an additional MinOtherOffset
field, which tracks the constant offset similar to the existing
OtherOffset, which the difference that it also includes non-negative
lower bounds on the range of the index value. When checking if the
distance between 2 accesses exceeds the access size, we can use this
improved bound.

For now this is limited to using non-negative lower bounds for indices,
as this conveniently skips cases where we do not have a useful lower
bound (because it is not constrained). We potential miss out in cases
where the lower bound is constrained but negative, but that can be
exploited in the future.

Reviewers: sanjoy, hfinkel, reames, asbirlea

Reviewed By: asbirlea

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

show more ...