[MemDepAnalysis] Don't reuse NonLocalPointerDeps cache if memory location size differs (#116936)

As seen in #111585, we can end up using a previous cache entry where the
size was too large and was

[MemDepAnalysis] Don't reuse NonLocalPointerDeps cache if memory location size differs (#116936)

As seen in #111585, we can end up using a previous cache entry where the
size was too large and was UB.

Compile time impact:
https://llvm-compile-time-tracker.com/compare.php?from=6a863f7e2679a60f2f38ae6a920d0b6e1a2c1690&to=faccf4e1f47fcd5360a438de2a56d02b770ad498&stat=instructions:u.

Fixes #111585.

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

[NFC] Reapply 3f37c517f, SmallDenseMap speedups

This time with 100% more building unit tests. Original commit message follows.

[NFC] Switch a number of DenseMaps to SmallDenseMaps for speedup (#109

[NFC] Reapply 3f37c517f, SmallDenseMap speedups

This time with 100% more building unit tests. Original commit message follows.

[NFC] Switch a number of DenseMaps to SmallDenseMaps for speedup (#109417)

If we use SmallDenseMaps instead of DenseMaps at these locations,
we get a substantial speedup because there's less spurious malloc
traffic. Discovered by instrumenting DenseMap with some accounting
code, then selecting sites where we'll get the most bang for our buck.

show more ...

Revert "[NFC] Switch a number of DenseMaps to SmallDenseMaps for speedup (#109417)"

This reverts commit 3f37c517fbc40531571f8b9f951a8610b4789cd6.

Lo and behold, I missed a unit test

[NFC] Switch a number of DenseMaps to SmallDenseMaps for speedup (#109417)

If we use SmallDenseMaps instead of DenseMaps at these locations,
we get a substantial speedup because there's less spurio

[NFC] Switch a number of DenseMaps to SmallDenseMaps for speedup (#109417)

If we use SmallDenseMaps instead of DenseMaps at these locations,
we get a substantial speedup because there's less spurious malloc
traffic. Discovered by instrumenting DenseMap with some accounting
code, then selecting sites where we'll get the most bang for our buck.

show more ...

[LLVM] Don't peek through bitcast on pointers and gep with zero indices. NFC. (#102889)

Since we are using opaque pointers now, we don't need to peek through
bitcast on pointers and gep with zero i

[LLVM] Don't peek through bitcast on pointers and gep with zero indices. NFC. (#102889)

Since we are using opaque pointers now, we don't need to peek through
bitcast on pointers and gep with zero indices.

show more ...

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it does

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it doesn't exist...

`getModule()->getDataLayout()` is also a common (the most common?)
reason why code has to include the Module.h header.

show more ...

[Analysis] Use range-based for loops (NFC)

[Analysis] Add Scalable field in MemoryLocation.h (#69716)

This is the first of a series of patch to improve Alias Analysis on
Scalable quantities.
Keep Scalable information from TypeSize whic

[Analysis] Add Scalable field in MemoryLocation.h (#69716)

This is the first of a series of patch to improve Alias Analysis on
Scalable quantities.
Keep Scalable information from TypeSize which
will be used in Alias Analysis.

show more ...

[MemDep] Use EarliestEscapeInfo (#69727)

Use BatchAA with EarliestEscapeInfo instead of callCapturesBefore() in
MemDepAnalysis. The advantage of this is that it will also take
not-captured-before

[MemDep] Use EarliestEscapeInfo (#69727)

Use BatchAA with EarliestEscapeInfo instead of callCapturesBefore() in
MemDepAnalysis. The advantage of this is that it will also take
not-captured-before information into account for non-calls (see
test_store_before_capture for a representative example), and that this
is a cached analysis. The disadvantage is that EII is slightly less
precise than full CapturedBefore analysis.

In practice the impact is positive, with gvn.NumGVNLoad going from 22022
to 22808 on test-suite.

The impact to compile-time is also positive, mainly in the ThinLTO
configuration.

show more ...

[GVN] Drop Clobber dependency if store may overwrite only the same value (#68322)

In some cases clobbering store can be safely skipped if it can only must
or no alias with memory location and it wr

[GVN] Drop Clobber dependency if store may overwrite only the same value (#68322)

In some cases clobbering store can be safely skipped if it can only must
or no alias with memory location and it writes the same value. This
patch supports simple case when the value from memory location was
loaded in the same basic block before the store and there are no
modifications between them.

show more ...

Revert "[GVN] Support address translation through select instructions"

This reverts commit b5bf6f6392a3408be1b7b7e036eb69358c5a2c29.

[GVN] Support address translation through select instructions

Process cases when phi incoming in predecessor block has select
instruction, and this select address is unavailable, but there
are addre

[GVN] Support address translation through select instructions

Process cases when phi incoming in predecessor block has select
instruction, and this select address is unavailable, but there
are addresses translated from both sides of select instruction.

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

show more ...

[NFC] PHITransAddr refactoring - return translated value directly or nullptr on
failure (instead of bool flag)

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

[NFC] Fix function naming conventions in PHITransAddr methods

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

[GVN] Refactor handling of pointer-select in GVN pass

This patch extends Def memory dependency with support of select
instructions to consistently handle pointer-select conversion.

Differential Rev

[GVN] Refactor handling of pointer-select in GVN pass

This patch extends Def memory dependency with support of select
instructions to consistently handle pointer-select conversion.

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

show more ...

Revert "[GVN] Refactor handling of pointer-select in GVN pass"

This reverts commit fc7cdaa373308ce3d72218b4d80101ae19850a6c.

[GVN] Refactor handling of pointer-select in GVN pass

This patch introduces new type of memory dependency - Select to
consistently handle it like Def/Clobber dependency.

Differential Revision: http

[GVN] Refactor handling of pointer-select in GVN pass

This patch introduces new type of memory dependency - Select to
consistently handle it like Def/Clobber dependency.

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

show more ...

[MemDep] Reduce block limit

The non-local MemDep analysis has a limit on the number of blocks
it will scan trying to find dependencies. The current limit of 1000
is very high, especially when we con

[MemDep] Reduce block limit

The non-local MemDep analysis has a limit on the number of blocks
it will scan trying to find dependencies. The current limit of 1000
is very high, especially when we consider that each block scan can
also visit up to 100 instructions. In degenerate cases (where we
actually scan that many blocks) MemDep/GVN dominate overall
compile-time, for little benefit.

This patch reduces the limit to 200, which is probably still too
large, but at least mitigates some of the more catastrophic cases.
(For comparison, MSSA clobber walks consider up to 100
MemoryDefs/MemoryPhis, rather than 200 blocks * 100 instructions,
but these limits aren't directly comparable.)

I know that we were kind of hoping that this issue would resolve
itself in time, either by a switch to NewGVN or use of MSSA in GVN.
But I think we should still address this in the meantime.
Additionally, a switch to an MSSA-based implementation will
effectively be doing this as well, in a roundabout way (by dint of
MSSA having lower cutoffs than MDA).

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

show more ...

[BasicAA] Remove support for PhiValues analysis

BasicAA currently has an optional dependency on the PhiValues
analysis. However, at least with our current pipeline setup, we
never actually make use

[BasicAA] Remove support for PhiValues analysis

BasicAA currently has an optional dependency on the PhiValues
analysis. However, at least with our current pipeline setup, we
never actually make use of it. It's possible that this used to work
with the legacy pass manager, but I'm not sure of that either.

Given that this analysis has not actually been in use for a long
time, and nobody noticed or complained, I think we should drop
support for it and focus on one code path. It is worth noting that
analysis quality for the non-PhiValues case has significantly
improved in the meantime.

If we really wanted to make use of PhiValues, the right way would
probably be to pass it in via AAQI in places we want to use it,
rather than using an optional pass manager dependency (which are
an unpredictable PITA and should really only ever be used for
analyses that are only preserved and not used).

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

show more ...

[AliasAnalysis] Introduce getModRefInfoMask() as a generalization of pointsToConstantMemory().

The pointsToConstantMemory() method returns true only if the memory pointed to
by the memory location i

[AliasAnalysis] Introduce getModRefInfoMask() as a generalization of pointsToConstantMemory().

The pointsToConstantMemory() method returns true only if the memory pointed to
by the memory location is globally invariant. However, the LLVM memory model
also has the semantic notion of *locally-invariant*: memory that is known to be
invariant for the life of the SSA value representing that pointer. The most
common example of this is a pointer argument that is marked readonly noalias,
which the Rust compiler frequently emits.

It'd be desirable for LLVM to treat locally-invariant memory the same way as
globally-invariant memory when it's safe to do so. This patch implements that,
by introducing the concept of a *ModRefInfo mask*. A ModRefInfo mask is a bound
on the Mod/Ref behavior of an instruction that writes to a memory location,
based on the knowledge that the memory is globally-constant memory (in which
case the mask is NoModRef) or locally-constant memory (in which case the mask
is Ref). ModRefInfo values for an instruction can be combined with the
ModRefInfo mask by simply using the & operator. Where appropriate, this patch
has modified uses of pointsToConstantMemory() to instead examine the mask.

The most notable optimization change I noticed with this patch is that now
redundant loads from readonly noalias pointers can be eliminated across calls,
even when the pointer is captured. Internally, before this patch,
AliasAnalysis was assigning Ref to reads from constant memory; now AA can
assign NoModRef, which is a tighter bound.

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

show more ...

[llvm] LLVM_FALLTHROUGH => [[fallthrough]]. NFC

With C++17 there is no Clang pedantic warning or MSVC C5051.

[AA] Do not track Must in ModRefInfo

getModRefInfo() queries currently track whether the result is a
MustAlias on a best-effort basis. The only user of this functionality
is the optimized memory acc

[AA] Do not track Must in ModRefInfo

getModRefInfo() queries currently track whether the result is a
MustAlias on a best-effort basis. The only user of this functionality
is the optimized memory access type in MemorySSA -- which in turn
has no users. Given that this functionality has not found a user
since it was introduced five years ago (in D38862), I think we
should drop it again.

The context is that I'm working to separate FunctionModRefBehavior
to track mod/ref for different location kinds (like argmem or
inaccessiblemem) separately, and the fact that ModRefInfo also has
an unrelated Must flag makes this quite awkward, especially as this
means that NoModRef is not a zero value. If we want to retain the
functionality, I would probably split getModRefInfo() results into
a part that just contains the ModRef information, and a separate
part containing a (best-effort) AliasResult.

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

show more ...

[MemoryBuiltins] Add getFreedOperand() function (NFCI)

We currently assume in a number of places that free-like functions
free their first argument. This is true for all hardcoded free-like
function

[MemoryBuiltins] Add getFreedOperand() function (NFCI)

We currently assume in a number of places that free-like functions
free their first argument. This is true for all hardcoded free-like
functions, but with the new attribute-based design, the freed
argument is supposed to be indicated by the allocptr attribute.

To make sure we handle this correctly once allockind(free) is
respected, add a getFreedOperand() helper which returns the freed
argument, rather than just indicating whether the call frees *some*
argument.

This migrates most but not all users of isFreeCall() to the new
API. The remaining users are a bit more tricky.

show more ...

[NFC] Remove commented cerr debugging loggings

There are some unused cerr debugging loggings in the codes. It is weird
to remain such commented debug helpers in the product.