Now that #149310 has restricted lifetime intrinsics to only work on
allocas, we can also drop the explicit size argument. Instead, the size
is implied by the alloca.
This removes the ability to only mark a prefix of an alloca alive/dead.
We never used that capability, so we should remove the need to handle
that possibility everywhere (though many key places, including stack
coloring, did not actually respect this).
lifetime.start and lifetime.end are primarily intended for use on
allocas, to enable stack coloring and other liveness optimizations. This
is necessary because all (static) allocas are hoisted into the entry
block, so lifetime markers are the only way to convey the actual
lifetimes.
However, lifetime.start and lifetime.end are currently *allowed* to be
used on non-alloca pointers. We don't actually do this in practice, but
just the mere fact that this is possible breaks the core purpose of the
lifetime markers, which is stack coloring of allocas. Stack coloring can
only work correctly if all lifetime markers for an alloca are
analyzable.
* If a lifetime marker may operate on multiple allocas via a select/phi,
we don't know which lifetime actually starts/ends and handle it
incorrectly (https://github.com/llvm/llvm-project/issues/104776).
* Stack coloring operates on the assumption that all lifetime markers
are visible, and not, for example, hidden behind a function call or
escaped pointer. It's not possible to change this, as part of the
purpose of lifetime markers is that they work even in the presence of
escaped pointers, where simple use analysis is insufficient.
I don't think there is any way to have coherent semantics for lifetime
markers on allocas, while also permitting them on arbitrary pointer
values.
This PR restricts lifetimes to operate on allocas only. As a followup, I
will also drop the size argument, which is superfluous if we always
operate on an alloca. (This change also renders various code handling
lifetime markers on non-alloca dead. I plan to clean up that kind of
code after dropping the size argument as well.)
In practice, I've only found a few places that currently produce
lifetimes on non-allocas:
* CoroEarly replaces the promise alloca with the result of an intrinsic,
which will later be replaced back with an alloca. I think this is the
only place where there is some legitimate loss of functionality, but I
don't think this is particularly important (I don't think we'd expect
the promise in a coroutine to admit useful lifetime optimization.)
* SafeStack moves unsafe allocas onto a separate frame. We can safely
drop lifetimes here, as SafeStack performs its own stack coloring.
* Similar for AddressSanitizer, it also moves allocas into separate
memory.
* LSR sometimes replaces the lifetime argument with a GEP chain of the
alloca (where the offsets ultimately cancel out). This is just
unnecessary. (Fixed separately in
https://github.com/llvm/llvm-project/pull/149492.)
* InferAddrSpaces sometimes makes lifetimes operate on an addrspacecast
of an alloca. I don't think this is necessary.
I found this peculiar comment in EarlyCSE:
1c78d8d9d7/llvm/lib/Transforms/Scalar/EarlyCSE.cpp (L1620-L1624)
Looking back over history, this seems to be referring to the
aarch64.neon.stN intrinsics, which are indeed not marked writeonly
(though the ldN intrinsics are readonly).
Possibly I'm missing something special about these intrinsics, but I
think it is safe to mark them as writeonly.
Update the AA CaptureAnalysis providers to return CaptureComponents, so
we can distinguish between full provenance and read-only provenance
captures.
Use this to restrict "other" memory effects on call from ModRef to Ref.
Ideally we would also apply the same reasoning for escape sources, but
the current API cannot actually convey the necessary information (we can
only say NoAlias or MayAlias, not MayAlias but only via Ref).
This depth limits a linear search (rather than the usual potentially
exponential one) and is not particularly important for compile-time in
practice.
The change in #137297 is going to increase the length of GEP chains, so
I'd like to increase this limit a bit to reduce the chance of
regressions (https://github.com/dtcxzyw/llvm-opt-benchmark/pull/2419
showed a 13% increase in SearchLimitReached). There is no particular
significance to the new value of 10.
Compile-time is neutral.
Similar to 1b7ef6aac8a3cad245c0ed14fe21725e31261f73, add a check to only
set MinAbsVarIndex if abs(Scale*V0) and abs((-Scale)*V1) won't wrap. In
the absence of IsNSW, try to use the bitwidths of the original V and
Scale to rule out wrapping
This is a much smaller, technically orthogonal patch similar to #134505. It
states that a extractvalue(Argument) can be treated like an Argument for alias
analysis, where the extractelement acts like a phi / copy. No inttoptr here.
Currently, the handling for calls is split between AA and BasicAA in an
awkward way. BasicAA does argument alias analysis for non-escaping
objects (but without considering MemoryEffects), while AA handles the
generic case using MemoryEffects. However, fundamentally, both of these
are really trying to do the same thing.
The new merged logic first tries to remove the OtherMR component of the
memory effects, which includes accesses to escaped memory. If a
function-local object does not escape, OtherMR can be set to NoModRef.
Then we perform the argument scan in basically the same way as AA
previously did. However, we also need to look at the operand bundles. To
support that, I've adjusted getArgModRefInfo to accept operand bundle
arguments.
For the purposes of alias analysis, we should only consider provenance
captures, not address captures. To support this, change (or add)
CaptureTracking APIs to accept a Mask and StopFn argument. The Mask
determines which components we are interested in (for AA that would be
Provenance).
The StopFn determines when we can abort the walk early. Currently, we
want to do this as soon as any of the components in the Mask is
captured. The purpose of making this a separate predicate is that in the
future we will also want to distinguish between capturing full
provenance and read-only provenance. In that case, we can only stop
early once full provenance is captured. The earliest escape analysis
does not get a StopFn, because it must always inspect all captures.
CaptureTracking considers insertions into aggregates and vectors as
captures. As such, extractions from aggregates and vectors are escape
sources. A non-escaping identified local cannot alias with the result of
an extractvalue/extractelement.
Fixes https://github.com/llvm/llvm-project/issues/126670.
Relates to (but isn't dependent on) #120420.
This allows alias analysis o the intrinsic of the same quality as for
the libcall, which we want in order to move LoopIdiomRecognize over to
selecting the intrinsic.
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.
As defined in LangRef, branching on `undef` is undefined behavior.
This PR aims to remove undefined behavior from tests. As UB tests break
Alive2 and may be the root cause of breaking future optimizations.
Here's an Alive2 proof for one of the examples:
https://alive2.llvm.org/ce/z/TncxhP
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.
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.
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
When using stripPointerCasts() and getUnderlyingObject(), don't
strip through a bitcast from ptr to <1 x ptr>, which is not a
no-op pointer cast. Calling code is generally not prepared to
handle that situation, resulting in incorrect alias analysis
results for example.
Fixes https://github.com/llvm/llvm-project/issues/97600.
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.
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.
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.
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.
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.
This patch canonicalizes getelementptr instructions with constant
indices to use the `i8` source element type. This makes it easier for
optimizations to recognize that two GEPs are identical, because they
don't need to see past many different ways to express the same offset.
This is a first step towards
https://discourse.llvm.org/t/rfc-replacing-getelementptr-with-ptradd/68699.
This is limited to constant GEPs only for now, as they have a clear
canonical form, while we're not yet sure how exactly to deal with
variable indices.
The test llvm/test/Transforms/PhaseOrdering/switch_with_geps.ll gives
two representative examples of the kind of optimization improvement we
expect from this change. In the first test SimplifyCFG can now realize
that all switch branches are actually the same. In the second test it
can convert it into simple arithmetic. These are representative of
common optimization failures we see in Rust.
Fixes https://github.com/llvm/llvm-project/issues/69841.
BasicAA currently says that any Constant cannot alias an identified
local object. This is not correct if the local object escaped, as it's
possible to create a pointer to the escaped object using an inttoptr
constant expression base.
To compensate for this, make sure that inttoptr constant expressions are
treated as escape sources, just like inttoptr instructions. This ensures
that the optimization can still be applied if the local object is
non-escaping. This is sufficient to still optimize the original
motivating case from c53e2ecf0296a55d3c33c19fb70a3aa7f81f2732.
Fixes https://github.com/llvm/llvm-project/issues/76789.
This removes the MaskedValueIsZero check in decomposing geps in BasicAA, using
the isDisjoint flags instead. This relies on the disjoint flags being present
when AA is ran. The alternative would be to keep the old MaskedValueIsZero check
too if this causes issues.
The definition of the pointer of the memory location being queried is
always one such context. Even this conservative guess can be better than
no guess at all in some cases.
Fixes#64666
Co-authored-by: David Goldblatt <davidgoldblatt@meta.com>
The current code incorrectly assumed that the absolute variable index
needs to be at least 1, if the variable is != 0. This is incorrect, in
case multiplying with Scale wraps.
The code below already checks for wrapping properly, so just remove the
incorrect assignment.
Fixes https://github.com/llvm/llvm-project/issues/72831.
There are many tests that specify a target triple/CPU flags but no
DataLayout which can lead to IR being generated that has unusual
behaviour. This commit attempts to use the default DataLayout based
on the relevant flags if there is no explicit override on the command
line or in the IR file.
One thing that is not currently possible to differentiate from a missing
datalayout `target datalayout = ""` in the IR file since the current
APIs don't allow detecting this case. If it is considered useful to
support this case (instead of passing "-data-layout=" on the command
line), I can change IR parsers to track whether they have seen such a
directive and change the callback type.
Differential Revision: https://reviews.llvm.org/D141060
Basic way to recursively analyze `select` in `isKnownNonEqual`: `select
%c, %t, %f` is non-equal to `%x` if `%t` is non-equal to `%x` and `%f`
is non-equal to `%x`.
