| Age | Commit message (Collapse) | Author |
|---|
|
SCCP currently stores instructions whose lattice value has changed in a
worklist, and then updates their users in the main loop. This may result
in instructions unnecessarily being visited multiple times (as an
instruction will often use multiple other instructions). Additionally,
we'd often redundantly visit instructions that were already visited when
the containing block first became executable.
Instead, change the worklist to directly store the instructions that
need to be revisited. Additionally, do not add instructions to the
worklist that will already be covered by the main basic block walk.
This change is conceptually NFC, but is expected to produce minor
differences in practice, because the visitation order interacts with the
range widening limit.
|
|
Currently predicates are allocated on the heap and tracked with an
intrusive list. Use a bump pointer allocator instead, which is more
efficient. The list is no longer needed, as we don't have to track
predicates for freeing.
The bump pointer allocator is provided as a parameter for PredicateInfo
to allow reusing the same allocator for all functions during IPSCCP.
|
|
Do the cheap intrinsic check before the hash lookup for the
PredicateInfo.
|
|
So it can be reused between IPSCCP and SCCP.
Make the implementation a bit more efficient by only lookup the
PredicateInfo once.
|
|
Following the work in PR #107279, this patch applies the annotative
DebugLocs, which indicate that a particular instruction is intentionally
missing a location for a given reason, to existing sites in the compiler
where their conditions apply. This is NFC in ordinary LLVM builds (each
function `DebugLoc::getFoo()` is inlined as `DebugLoc()`), but marks the
instruction in coverage-tracking builds so that it will be ignored by
Debugify, allowing only real errors to be reported. From a developer
standpoint, it also communicates the intentionality and reason for a
missing DebugLoc.
Some notes for reviewers:
- The difference between `I->dropLocation()` and
`I->setDebugLoc(DebugLoc::getDropped())` is that the former _may_ decide
to keep some debug info alive, while the latter will always be empty; in
this patch, I always used the latter (even if the former could
technically be correct), because the former could result in some
(barely) different output, and I'd prefer to keep this patch purely NFC.
- I've generally documented the uses of `DebugLoc::getUnknown()`, with
the exception of the vectorizers - in summary, they are a huge cause of
dropped source locations, and I don't have the time or the domain
knowledge currently to solve that, so I've plastered it all over them as
a form of "fixme".
|
|
CVP version:
https://github.com/llvm/llvm-project/commit/2d5820cd72255e04aaef2da3c21d62396fdd7fb9
Compile-time impact:
https://llvm-compile-time-tracker.com/compare.php?from=3ec0c5c7fef03985b43432c6b914c289d8a5435e&to=92b4df90695dd37defdabf8a30f0b0322b648a00&stat=instructions:u
|
|
|
|
This patch makes getMRVFunctionsTracked return a reference.
runIPSCCP, the sole user of getMRVFunctionsTracked, just needs a
read-access to the map.
The missing "&" is most likely an oversight as two "sibling" functions
getTrackedRetVals and getTrackedGlobals return maps by const
reference.
|
|
try_emplace can default-construct values, so we do not need to do so
on our own. Plus, try_emplace(Key) is much shorter than
insert(std::make_pair(Key, Value()).
|
|
|
|
If the GEP is nusw/inbounds and has all-non-negative offsets infer nuw
as well.
This doesn't have measurable compile-time impact.
Proof: https://alive2.llvm.org/ce/z/ihztLy
|
|
Teach SCCP to compute a constant range for calls to llvm.vscale
intrinsics.
|
|
|
|
During inter-procedural SCCP, also infer attributes on arguments, not
just return values. This allows other non-interprocedural passes to make
use of the information later.
|
|
This patch removes the `LoadInst` when it loaded from Constant
GlobalVariable. This allows `canRemoveInstruction` function to be
removed.
|
|
Don't just leave the result as unknown. I think this currently
works out thanks to undef resolution, but the correct thing to
do is set it to overdefined explicitly.
|
|
We can infer the range/nonnull attributes in non-interprocedural SCCP as
well. The results may be better after the function has been simplified.
|
|
IPSCCP can currently return worse results than SCCP for arguments that
are tracked interprocedurally, because information from attributes is
not used for them.
Fix this by intersecting in the attribute information when propagating
lattice values from calls.
|
|
Also consider allocas non-null (subject to the usual caveats),
and consider nonnull/dereferenceable metadata on calls.
|
|
Add NotConstant(Null) roots for nonnull arguments and then propagate
them through nuw/inbounds GEPs.
Having this functionality in SCCP is useful because it allows reliably
eliminating null comparisons, independently of how deeply nested they
are in selects/phis. This handles cases that would hit a cutoff in
ValueTracking otherwise.
The implementation is something of a MVP, there are a number of obvious
extensions (e.g. allocas are also non-null).
|
|
This is a confusingly named helper than means "is not unknown,
undef or constant". Prefer the more obvious ValueLattice API
instead. Most of these checks are for values which are forced to
overdefined by undef resolution, in which case only actual
overdefined values are relevant.
|
|
the visit order depended on hashing because we iterated over a
SmallPtrSet
|
|
|
|
|
|
Fixes #98875
|
|
Add preliminary support for vectors of integers by using the
`ValueLatticeElement::asConstantRange()` helper instead of a custom
implementation, and relxing various integer type checks.
This enables just the part that works automatically, e.g. icmps with a
constant vector operand aren't supported yet.
The change in ssa.copy handling is because asConstantRange() returns an
unknown LV for empty range, while SCCP's getConstantRange() returned a
full range. I've made the change to preserve the existing behavior.
|
|
The only bitcasts the existing code might be able to handle are
bitcasts between iN and <1 x iN>. Don't bother.
|
|
When performing some range operation (e.g. and) on a constant range that
includes undef, we currently just ignore the undef value, which is
obviously incorrect. Instead, we can do one of two things:
* Say that the result range also includes undef.
* Treat undef as a full range.
This patch goes with the second approach -- I'd expect it to be a bit
better overall, e.g. it allows preserving the fact that a zext of a
range with undef isn't a full range.
Fixes https://github.com/llvm/llvm-project/issues/93096.
|
|
Similiar to the `InstCombine` changes, just furthering the support of
the `uitofp nneg` support.
Closes #86154
|
|
Following #85592, add support for nsw/nuw flags of trunc in SCCP.
|
|
Support the new range attribute to infer ConstantRanges in IPSCCP.
|
|
Leverage more refined ranges results when handling overflowing
binary operators.
|
|
I'd reverted this in 6c7805d5d1 after a bad stage. Original commit
messsage follows:
[NFC][RemoveDIs] Bulk update utilities to insert with iterators
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.
I've also switched DemotePHIToStack to take an optional iterator: it needs
to take an iterator, and having a no-insert-location behaviour appears to
be important. The constructors for ICmpInst and FCmpInst have been updated
too. They're the only instructions that take block _references_ rather than
pointers for certain calls, and a future patch is going to make use of
default-null block insertion locations.
All of this should be NFC.
|
|
This reverts commit 3fda50d3915b2163a54a37b602be7783a89dd808.
Apparently I've missed a hunk while staging this; will back out for now.
Picked up here: https://lab.llvm.org/buildbot/#/builders/139/builds/60429/steps/6/logs/stdio
|
|
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.
I've also switched DemotePHIToStack to take an optional iterator: it needs
to take an iterator, and having a no-insert-location behaviour appears to
be important. The constructors for ICmpInst and FCmpInst have been updated
too. They're the only instructions that take block _references_ rather than
pointers for certain calls, and a future patch is going to make use of
default-null block insertion locations.
All of this should be NFC.
|
|
This patch eliminates unreachable default cases using range information.
Fixes #76085.
|
|
This patch propagates exact flags for `ashr->lshr` and `sdiv->udiv` in
SCCP.
This missed optimization is discovered with the help of
https://github.com/AliveToolkit/alive2/pull/962.
|
|
This patch infers `nneg` flags for existing zext instructions in SCCP.
Similar patch: https://github.com/llvm/llvm-project/pull/72052
|
|
Builds on #67982 which recently introduced the nneg flag on a zext
instruction.
|
|
Introduce isDesirableCastOp() which determines whether IR builder
and constant folding should produce constant expressions for a
given cast type. This mirrors what we do for binary operators.
Mark zext/sext as undesirable, which prevents most creations of such
constant expressions. This is still somewhat incomplete and there
are a few more places that can create zext/sext expressions.
This is part of the work for
https://discourse.llvm.org/t/rfc-remove-most-constant-expressions/63179.
The reason for the odd result in the constantexpr-fneg.c test is
that initially the "a[]" global is created with an [0 x i32] type,
at which point the icmp expression cannot be folded. Later it is
replaced with an [1 x i32] global and the icmp gets folded away.
But at that point we no longer fold the zext.
|
|
isLegalToHoistInto() currently return true for callbr instructions.
That means that a callbr with one successor will be considered a
proper loop preheader, which may result in instructions that use
the callbr return value being hoisted past it.
Fix this by adding callbr to isExceptionTerminator (with a rename
to isSpecialTerminator), which also fixes similar assumptions in
other places.
Fixes https://github.com/llvm/llvm-project/issues/64215.
Differential Revision: https://reviews.llvm.org/D158609
|
|
Scalable vector GEPs are not constants and trying to create one for
these GEPs causes an assertion failure.
Reviewed By: nikic, paulwalker-arm
Differential Revision: https://reviews.llvm.org/D157590
|
|
If a value is already the last element of the worklist, then I think that we don't have to add it again, it is not needed to process it repeatedly.
For some long Triton-generated LLVM IR, this can cause a ~100x speedup.
Differential Revision: https://reviews.llvm.org/D153561
|
|
The ConstantRange specifies the range of the scalar elements in the
vector. When converting into a Constant, we need to create a vector
splat with the correct type. For that purpose, pass in the expected
type for the constant.
Fixes https://github.com/llvm/llvm-project/issues/63380.
|
|
Breaks all sanitizers bootstrap bots:
https://lab.llvm.org/buildbot/#/waterfall?tags=sanitizer
This reverts commit cf79773a9006a7e22f3919268b7db381ddcb3abc.
|
|
In replaceSignedInst, if a signed instruction can be repalced with
unsigned instruction, we created a new instruction and removed the old
instruction's value state. If the following instructions has this new
instruction as a use operand, transformations like replaceSignedInst and
refineInstruction would be blocked. The reason is there is no value
state for the new instrution.
This patch set the new instruction's value state with the removed
instruction's value state. I believe it is correct bacause when we
repalce a signed instruction with unsigned instruction, the value state
is not changed.
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D152337
|
|
For constant range supported intrinsics, we got consantrange from args
no matter if they are unknown or undef. And the constant range computed
from unknown or undef value state is full range.
I think compute with full constant range is harmful since although we
can do mergeIn after these args value state are changed, the merge
operation of two constant ranges is union.
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D152499
|
|
Using AvgLoopIters on any loop is too imprecise making the cost model
favor users inside loop nests regardless of the actual tripcount.
Differential Revision: https://reviews.llvm.org/D150375
|
|
Reapply with extra check for struct types, which caused buildbot
failures last time.
-----
The freeze instruction has not been handled by SCCPInstVisitor.
This patch adds SCCPInstVisitor::visitFreezeInst(FreezeInst &I)
method to handle freeze instructions.
Differential Revision: https://reviews.llvm.org/D151659
|
|
The SCCPSolver is using a structure (AnalysisResultsForFn) where it keeps
pointers to various analyses needed by the IPSCCP pass. These analyses are
requested all at the same time, which can become problematic in some cases.
For example one could be retrieved via getCachedAnalysis() prior to the
actual execution of the analysis. In more detail:
The IPSCCP pass uses a DomTreeUpdater to preserve the PostDominatorTree
in case the PostDominatorTreeAnalysis had run before IPSCCP. Starting with
commit 1b1232047e83b the IPSCCP pass may use BlockFrequencyAnalysis for
some functions in the module. As a result, the PostDominatorTreeAnalysis
may not run until the BlockFrequencyAnalysis has run, since the latter
analysis depends on the former. Currently, we setup the DomTreeUpdater
using getCachedAnalysis to retrieve a PostDominatorTree. This happens
before BlockFrequencyAnalysis has run, therefore the cached analysis can
become invalid by the time we use it.
Differential Revision: https://reviews.llvm.org/D151666
|
