This patch replaces SmallSet<T *, N> with SmallPtrSet<T *, N>. Note
that SmallSet.h "redirects" SmallSet to SmallPtrSet for pointer
element types:
template <typename PointeeType, unsigned N>
class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N>
{};
We only have 140 instances that rely on this "redirection", with the
vast majority of them under llvm/. Since relying on the redirection
doesn't improve readability, this patch replaces SmallSet with
SmallPtrSet for pointer element types.
If we have a known `p == p2` equality, we cannot replace `p2` with `p`
unless they are known to have the same provenance. GVN handles this when
propagating equalities from conditions, but not for assumes, as these go
through a different code path for uses in the same block.
Call canReplacePointersInUseIfEqual() before performing the replacement.
This is subject to the usual approximations (e.g. that we always allow
replacement with a dereferenceable constant and null).
This restriction does not appear to have any impact in practice.
Look through `not` when propagating equalities in GVN. Usually these
will be canonicalized away, but they may be retained due to multi-use or
involvement in logical expressions.
Fixes https://github.com/llvm/llvm-project/issues/143529.
There is a larger problem here in that we should not be performing
arbitrary pointer replacements for assumes. This is handled for
branches, but assume goes through a different code path.
Fixes https://github.com/llvm/llvm-project/issues/151785.
With the advent of intrinsic-less debug-info, we no longer need to
scatter calls to getPrevNonDebugInstruction around the codebase. Remove
most of them -- there are one or two that have the "SkipPseudoOp" flag
turned on, however they don't seem to be in positions where skipping
anything would be reasonable.
Seeing how we can't generate any debug intrinsics any more: delete a
variety of codepaths where they're handled. For the most part these are
plain deletions, in others I've tweaked comments to remain coherent, or
added a type to (what was) type-generic-lambdas.
This isn't all the DbgInfoIntrinsic call sites but it's most of the
simple scenarios.
Co-authored-by: Nikita Popov <github@npopov.com>
While migrating towards MemorySSA, account for the memory state modeled
by MemorySSA by hashing it, when computing the symbolic expressions for
the memory operations. Likewise, when phi-translating while walking the
CFG for PRE possibilities, see if the value number of an operand may be
refined with one of the value from the incoming edges of the MemoryPhi
associated to the current phi.
Co-authored-by: Momchil Velikov <momchil.velikov@arm.com>
This patch adds to GVN's `propagateEquality()` to reason about equality
constraints through `trunc nuw iN to i1`.
Given:
%tr = trunc nuw iN %v to i1
We can deduce that if `%tr == true`, then `%v == 1`, and if `%tr ==
false`, then `%v == 0`. This is valid because `nuw` guarantees that
truncation didn't lose unsigned bits, so `%v` must have been either 0 or
1.
The patch adds logic to propagate this information via the GVN worklist.
This enables further simplification opportunities downstream, such as
folding redundant stores or conditionals that depend on `%v`.
Includes a test case in `GVN/trunc-nuw-equality.ll`.
Resolves#142744
This patch deletes the instructions immediately in core GVN processing by using the appropriate
iterators. Thus, it avoids collecting the instructions in a vector and then
doing the erasure.
DenseSet, SmallPtrSet, SmallSet, SetVector, and StringSet recently
gained C++23-style insert_range. This patch replaces:
Dest.insert(Src.begin(), Src.end());
with:
Dest.insert_range(Src);
This patch does not touch custom begin like succ_begin for now.
As per LLVM coding standards
"Variable names should be nouns (as they represent state).
The name should be camel case, and start with an upper
case letter (e.g. Leader or Boats)."
When storing a scalable vector and loading a fixed-size vector, where
the
scalable vector is known to be larger based on vscale_range, perform
store-to-load forwarding through temporary @llvm.vector.extract calls.
InstCombine then folds the insert/extract pair away.
The usecase is shown in https://godbolt.org/z/KT3sMrMbd, which shows
that clang generates IR that matches this pattern when the
"arm_sve_vector_bits" attribute is used:
```c
typedef svfloat32_t svfloat32_fixed_t
__attribute__((arm_sve_vector_bits(512)));
struct svfloat32_wrapped_t {
svfloat32_fixed_t v;
};
static inline svfloat32_wrapped_t
add(svfloat32_wrapped_t a, svfloat32_wrapped_t b) {
return {svadd_f32_x(svptrue_b32(), a.v, b.v)};
}
svfloat32_wrapped_t
foo(svfloat32_wrapped_t a, svfloat32_wrapped_t b) {
// The IR pattern this patch matches is generated for this return:
return add(a, b);
}
```
As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and similar feed into
instruction insertion positions. Call-sites where that's necessary were
updated a year ago; but to ensure some type safety however, we'd like to
have all calls to getFirstNonPHI use the iterator-returning version.
This patch changes a bunch of call-sites calling getFirstNonPHI to use
getFirstNonPHIIt, which returns an iterator. All these call sites are
where it's obviously safe to fetch the iterator then dereference it. A
follow-up patch will contain less-obviously-safe changes.
We'll eventually deprecate and remove the instruction-pointer
getFirstNonPHI, but not before adding concise documentation of what
considerations are needed (very few).
---------
Co-authored-by: Stephen Tozer <Melamoto@gmail.com>
As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and similar feed into
instruction insertion positions. Call-sites where that's necessary were
updated a year ago; but to ensure some type safety however, we'd like to
have all calls to moveBefore use iterators.
This patch adds a (guaranteed dereferenceable) iterator-taking
moveBefore, and changes a bunch of call-sites where it's obviously safe
to change to use it by just calling getIterator() on an instruction
pointer. A follow-up patch will contain less-obviously-safe changes.
We'll eventually deprecate and remove the instruction-pointer
insertBefore, but not before adding concise documentation of what
considerations are needed (very few).
Original commit: eb63cd62a4a1907dbd58f12660efd8244e7d81e9
Previously reverted due to non-negligible compile-time impact in
stage1-ReleaseLTO-g scenario. The issue has been addressed by
always reusing previously computed MemorySSA results, and request
new ones only when `isMemorySSAEnabled` is set.
Co-authored-by: Momchil Velikov <momchil.velikov@arm.com>
When replacing a load from a selected pointer with a select of the known
stored values, we currently assign no DebugLoc to the select; this patch
propagates the load's DebugLoc to the new select, since it is a direct
replacement.
Steal impliesEquivalanceIf{True,False} (sic) from GVN, and extend it for
floating-point constant vectors, and accounting for denormal values.
Since InstCombine also performs GVN-like replacements, introduce
CmpInst::isEquivalence, and remove the corresponding code in GVN, with
the intent of using it in more places.
The code in GVN also has a bad FIXME saying that the optimization may be
valid in the nsz case, but this is not the case.
Alive2 proof: https://alive2.llvm.org/ce/z/vEaK8M
This patch intersects attributes of two calls to avoid introducing UB.
It also skips incompatible call pairs in GVN/NewGVN. However, I cannot
provide negative tests for these changes.
Fixes https://github.com/llvm/llvm-project/issues/113997.
This replaces some of the most frequent offenders of using a DenseMap that
cause a malloc, where the typical element-count is small enough to fit in
an initial stack allocation.
Most of these are fairly obvious, one to highlight is the collectOffset
method of GEP instructions: if there's a GEP, of course it's going to have
at least one offset, but every time we've called collectOffset we end up
calling malloc as well for the DenseMap in the MapVector.
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.
Hide the details of the one-off linked list used to implement the leader
lists by
wrapping them in iterators, and then use that to reimplement a number of
traversals
using standard algorithms and range-based for-loops.
No functional change intended.
This patch does the following:
Adds the following functions:
- replaceDominatedUsesWithIf() that takes a callback.
- canReplacePointersIfEqual(...) returns true if the underlying object
is the same, and for null and const dereferencable pointer replacements.
- canReplacePointersIfEqualInUse(...) returns true for the above as well
as if the use is in icmp/ptrtoint or phi/selects feeding into them.
Updates GVN using the functions above so that the pointer replacements
are only made using the above API.
https://reviews.llvm.org/D143129
As part of the RemoveDIs project we need LLVM to insert instructions using
iterators wherever possible, so that the iterators can carry a bit of
debug-info. This commit implements some of that by updating the contents of
llvm/lib/Transforms/Utils to always use iterator-versions of instruction
constructors.
There are two general flavours of update:
* Almost all call-sites just call getIterator on an instruction
* Several make use of an existing iterator (scenarios where the code is
actually significant for debug-info)
The underlying logic is that any call to getFirstInsertionPt or similar
APIs that identify the start of a block need to have that iterator passed
directly to the insertion function, without being converted to a bare
Instruction pointer along the way.
Noteworthy changes:
* FindInsertedValue now takes an optional iterator rather than an
instruction pointer, as we need to always insert with iterators,
* I've added a few iterator-taking versions of some value-tracking and
DomTree methods -- they just unwrap the iterator. These are purely
convenience methods to avoid extra syntax in some passes.
* A few calls to getNextNode become std::next instead (to keep in the
theme of using iterators for positions),
* SeparateConstOffsetFromGEP has it's insertion-position field changed.
Noteworthy because it's not a purely localised spelling change.
All this should be NFC.
replaceValuesPerBlockEntry() only handled simple and coerced load
values, however the load may also be referenced by a select value.
Additionally, I suspect that the previous code might have been incorrect
if a load had an offset, as it always constructed the AvailableValue
from scratch.
Fixes https://github.com/llvm/llvm-project/issues/69301.
GVN behavior depends on LoopInfo in multiple ways, most notably
as a dependency for loop load PRE. As this is not a preserved-only
analysis, using a cached analysis is inappropriate.
In the actual optimization pipeline LoopInfo is always available
at the point GVN runs, but this will ensure it stays this way
even if the pipeline changes.
After a pass calls addRequired<X>() it is strange to call
getAnalysisIfAvailable<X>() because analysis X should always be
available. Use getAnalysis<X>() instead.
When performing store to load forwarding, replacing users of the
load may turn an indirect call into one with a known callee, in
which case it might become willreturn, invalidating cached ICF
information. Avoid this by removing users.
This is a bit more aggressive than strictly necessary (e.g. this
shouldn't be necessary when doing load-load CSE), but better safe
than sorry.
Fixes https://github.com/llvm/llvm-project/issues/48805.
Duplicate phi nodes were being directly removed, without
invalidating MDA. This could result in a new phi node being
allocated at the same address, incorrectly reusing a cache entry.
Fix this by optionally allowing EliminateDuplicatePHINodes() to
collect phi nodes to remove into a vector, which allows GVN to
handle removal itself.
Fixes https://github.com/llvm/llvm-project/issues/64598.
Differential Revision: https://reviews.llvm.org/D158849
findDominatingValue has a search limit, and when it is reached, optimization is
not applied. This patch fixes the issue that this limit also takes into account
debug intrinsics, so the result of optimization can depend from the presence of
debug info.
Continuing the patch series to get rid of debug intrinsics [0], instruction
insertion needs to be done with iterators rather than instruction pointers,
so that we can communicate information in the iterator class. This patch
adds an iterator-taking insertBefore method and converts various call sites
to take iterators. These are all sites where such debug-info needs to be
preserved so that a stage2 clang can be built identically; it's likely that
many more will need to be changed in the future.
At this stage, this is just changing the spelling of a few operations,
which will eventually become signifiant once the debug-info bearing
iterator is used.
[0] https://discourse.llvm.org/t/rfc-instruction-api-changes-needed-to-eliminate-debug-intrinsics-from-ir/68939
Differential Revision: https://reviews.llvm.org/D152537
