[Analysis] Remove unused includes (NFC) (#114936)

Identified with misc-include-cleaner.

[Analysis] Exclude llvm.allow.{runtime,ubsan}.check() from AliasSetTracker (#86065)

RFC:
https://discourse.llvm.org/t/rfc-add-llvm-experimental-hot-intrinsic-or-llvm-hot/77641

[AST] Don't merge memory locations in AliasSetTracker (#65731)

This changes the AliasSetTracker to track memory locations instead of
pointers in its alias sets. The motivation for this is outlined

[AST] Don't merge memory locations in AliasSetTracker (#65731)

This changes the AliasSetTracker to track memory locations instead of
pointers in its alias sets. The motivation for this is outlined in an RFC
posted on LLVM discourse:
https://discourse.llvm.org/t/rfc-dont-merge-memory-locations-in-aliassettracker/73336

In the data structures of the AST implementation, I made the choice to
replace the linked list of `PointerRec` entries (that had to go anyway)
with a simple flat vector of `MemoryLocation` objects, but for the
`AliasSet` objects referenced from a lookup table, I retained the
mechanism of a linked list, reference counting, forwarding, etc. The
data structures could be revised in a follow-up change.

show more ...

[AST] Switch to MemoryLocation in add method (NFC)

Pass MemoryLocation as one argument, instead of passing all its
parts separately.

[AST] Fix size merging for MustAlias sets (#73820)

AST checks aliasing with MustAlias sets by only checking the
representative pointer (getSomePointer). This is only correct if the
Size and AATags

[AST] Fix size merging for MustAlias sets (#73820)

AST checks aliasing with MustAlias sets by only checking the
representative pointer (getSomePointer). This is only correct if the
Size and AATags information of that pointer also includes the
Size/AATags of all other pointers in the set.

When we add a new pointer to the AliasSet, we do perform this update
(see the code in AliasSet::addPointer). However, if a pointer already in
the MustAlias set is used with a new size, we currently do not update
the representative pointer, resulting in miscompilations. Fix this by
adding the missing update.

This is a targeted fix using the current representation. There are a
couple of alternatives:
* For MustAlias sets, don't store per-pointer Size/AATags at all. This
would make it clear that there is only one set of common Size/AATags for
all pointers.
* Check against all pointers in the set even for MustAlias. This is what
https://github.com/llvm/llvm-project/pull/65731 proposes to do as part
of a larger change to AST representation.

Fixes https://github.com/llvm/llvm-project/issues/64897.

show more ...

[llvm] Add missing StringExtras.h includes

In preparation for removing the `#include "llvm/ADT/StringExtras.h"`
from the header to source file of `llvm/Support/Error.h`, first add in
all the missing

[llvm] Add missing StringExtras.h includes

In preparation for removing the `#include "llvm/ADT/StringExtras.h"`
from the header to source file of `llvm/Support/Error.h`, first add in
all the missing includes that were previously included transitively
through this header.

show more ...

Revert "[AST] Use ModRefInfo to represent access kind (NFC)"

This reverts commit 2c78a9e65ccfe36d213a409592bebdd3ed8ba771.

Fails to compile on mlir-s390x-linux buildbot using GCC 9.4 with:

llv

Revert "[AST] Use ModRefInfo to represent access kind (NFC)"

This reverts commit 2c78a9e65ccfe36d213a409592bebdd3ed8ba771.

Fails to compile on mlir-s390x-linux buildbot using GCC 9.4 with:

llvm/lib/Analysis/AliasSetTracker.cpp: In member function 'void llvm::AliasSet::mergeSetIn(llvm::AliasSet&, llvm::AliasSetTracker&, llvm::BatchAAResults&)':
llvm/lib/Analysis/AliasSetTracker.cpp:50:19: error: invalid operands of types 'unsigned char:2' and 'unsigned char:2' to binary 'operator|'

show more ...

[AST] Use ModRefInfo to represent access kind (NFC)

AST was using a custom enum with exactly the same semantics. Use
the standard one instead.

[LICM] Allow load-only scalar promotion in the presence of aliasing loads

During scalar promotion, if there are additional potentially-aliasing
loads outside the promoted set, we can still perform a

[LICM] Allow load-only scalar promotion in the presence of aliasing loads

During scalar promotion, if there are additional potentially-aliasing
loads outside the promoted set, we can still perform a load-only
promotion. As the stores are retained, any potentially-aliasing
loads will still read the correct value.

This increases the number of load promotions in llvm-test-suite by
a factor of two:

| Old | New
licm.NumPromotionCandidates | 4448 | 6038
licm.NumLoadPromoted | 479 | 1069
licm.NumLoadStorePromoted | 1459 | 1459

Unfortunately, this does have some impact on compile-time:
http://llvm-compile-time-tracker.com/compare.php?from=57f7f0d6cf0706a88e1ecb74f3d3e8891cceabfa&to=72b811738148aab399966a0435f13b695da1c1c8&stat=instructions
In part this is because we now have less early bailouts from
promotion, but also due to second order effects (e.g. for one case
I looked at we spend more time in SLP now).

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

show more ...

[AST] Make AliasSetTracker work on BatchAA

D138014 restricted AST to work on immutable IR. This means it is
also safe to use a single BatchAA instance for the entire AST
lifetime, instead of only ba

[AST] Make AliasSetTracker work on BatchAA

D138014 restricted AST to work on immutable IR. This means it is
also safe to use a single BatchAA instance for the entire AST
lifetime, instead of only batching parts of individual queries.

The primary motivation for this is not compile-time, but rather
having a central place to control cross-iteration AA, which will
be used by D137958.

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

show more ...

[AST] Don't use WeakVH for unknown insts (NFCI)

After D138014 we do not support using AST with IR that is being
mutated. As such, we also no longer need to track unknown
instructions using WeakVH. R

[AST] Don't use WeakVH for unknown insts (NFCI)

After D138014 we do not support using AST with IR that is being
mutated. As such, we also no longer need to track unknown
instructions using WeakVH. Replace with AssertingVH to make sure
that they are not invalidated.

show more ...

[AST] Restrict AliasSetTracker to immutable IR

This restricts usage of AliasSetTracker to IR that does not change.
We used to use it during LICM where the underlying IR could change,
but remaining u

[AST] Restrict AliasSetTracker to immutable IR

This restricts usage of AliasSetTracker to IR that does not change.
We used to use it during LICM where the underlying IR could change,
but remaining uses all use AST as part of a separate analysis phase.

This is split out from D137955, which makes use of the new guarantee
to switch to BatchAA.

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

show more ...

[AST] Remove legacy AliasSetPrinter pass

A NewPM version of this pass exists, drop the legacy version of
this testing-only pass.

[AA] Rename getModRefBehavior() to getMemoryEffects() (NFC)

Follow up on D135962, renaming the method name to match the new
type name.

[AST] Pass BatchAA to mergeSetIn() (NFCI)

[AST] Use BatchAA in aliasesPointer() (NFC)

[AA] Tracking per-location ModRef info in FunctionModRefBehavior (NFCI)

Currently, FunctionModRefBehavior tracks whether the function reads
or writes memory (ModRefInfo) and which locations it can a

[AA] Tracking per-location ModRef info in FunctionModRefBehavior (NFCI)

Currently, FunctionModRefBehavior tracks whether the function reads
or writes memory (ModRefInfo) and which locations it can access
(argmem, inaccessiblemem and other). This patch changes it to track
ModRef information per-location instead.

To give two examples of why this is useful:

* D117095 highlights a weakness of ModRef modelling in the presence
of operand bundles. For a memcpy call with deopt operand bundle,
we want to say that it can read any memory, but only write argument
memory. This would allow them to be treated like any other calls.
However, we currently can't express this and have to say that it
can read or write any memory.
* D127383 would ideally be modelled as a separate threadid location,
where threadid Refs outside pre-split coroutines can be ignored
(like other accesses to constant memory). The current representation
does not allow modelling this precisely.

The patch as implemented is intended to be NFC, but there are some
obvious opportunities for improvements and simplification. To fully
capitalize on this we would also want to change the way we represent
memory attributes on functions, but that's a larger change, and I
think it makes sense to separate out the FunctionModRefBehavior
refactoring.

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

show more ...

[AST] Use BatchAA in aliasesUnknownInst() (NFCI)

[AA] Make ModRefInfo a bitmask enum (NFC)

Mark ModRefInfo as a bitmask enum, which allows using normal
& and | operators on it. This supersedes various functions like
unionModRef() and intersectModR

[AA] Make ModRefInfo a bitmask enum (NFC)

Mark ModRefInfo as a bitmask enum, which allows using normal
& and | operators on it. This supersedes various functions like
unionModRef() and intersectModRef(). I think this makes the code
cleaner than going through helper functions...

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

show more ...

[Analysis] Qualify auto variables in for loops (NFC)

[AST] Don't assert instruction reads/writes memory (PR51333)

This function is well-defined for an instruction that doesn't access
memory (and thus trivially doesn't alias anything in the AST), so
dr

[AST] Don't assert instruction reads/writes memory (PR51333)

This function is well-defined for an instruction that doesn't access
memory (and thus trivially doesn't alias anything in the AST), so
drop the assert. We can end up with a readnone call here if we
originally created a MemoryDef for an indirect call, which was
later replaced with a direct readnone call.

Fixes https://github.com/llvm/llvm-project/issues/51333.

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

show more ...

[Analysis] Remove getUniqueInstruction (NFC)

The last use was removed on Apr 7, 2022 in commit
5cefe7d9f531fe6eac4cd22978861752498b2265.

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Diff

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120659

show more ...

[NFC][AA] Prepare to convert AliasResult to class with PartialAlias offset.

Main reason is preparation to transform AliasResult to class that contains
offset for PartialAlias case.

Reviewed By: asb

[NFC][AA] Prepare to convert AliasResult to class with PartialAlias offset.

Main reason is preparation to transform AliasResult to class that contains
offset for PartialAlias case.

Reviewed By: asbirlea

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

show more ...

Reapply [LICM] Make promotion faster

Relative to the previous implementation, this always uses
aliasesUnknownInst() instead of aliasesPointer() to correctly
handle atomics. The added test case was p

Reapply [LICM] Make promotion faster

Relative to the previous implementation, this always uses
aliasesUnknownInst() instead of aliasesPointer() to correctly
handle atomics. The added test case was previously miscompiled.

-----

Even when MemorySSA-based LICM is used, an AST is still populated
for scalar promotion. As the AST has quadratic complexity, a lot
of time is spent in this step despite the existing access count
limit. This patch optimizes the identification of promotable stores.

The idea here is pretty simple: We're only interested in must-alias
mod sets of loop invariant pointers. As such, only populate the AST
with loop-invariant loads and stores (anything else is definitely
not promotable) and then discard any sets which alias with any of
the remaining, definitely non-promotable accesses.

If we promoted something, check whether this has made some other
accesses loop invariant and thus possible promotion candidates.

This is much faster in practice, because we need to perform AA
queries for O(NumPromotable^2 + NumPromotable*NumNonPromotable)
instead of O(NumTotal^2), and NumPromotable tends to be small.
Additionally, promotable accesses have loop invariant pointers,
for which AA is cheaper.

This has a signicant positive compile-time impact. We save ~1.8%
geomean on CTMark at O3, with 6% on lencod in particular and 25%
on individual files.

Conceptually, this change is NFC, but may not be so in practice,
because the AST is only an approximation, and can produce
different results depending on the order in which accesses are
added. However, there is at least no impact on the number of promotions
(licm.NumPromoted) in test-suite O3 configuration with this change.

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

show more ...