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.
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".
While sinking instructions (that are loop invariant) from preheader to
the exit block, we are skipping instructions due to decrementing
instruction iterator twice.
Relevant parts of ScalarEvolution's API accept a CmpPredicate instead of
a CmpInst::Predicate after 60dc450 (SCEV: migrate to CmpPredicate
(NFC)). After auditing the callers of these APIs, it was found that
IndVarSimplify was dropping samesign information. Fix this.
This macros is always defined: either 0 or 1. The correct pattern is to
use #if.
Re-apply #110185 with more fixes for debug build with the ABI breaking
checks disabled.
The sort used the block name as a tie-breaker, which will not work for
unnamed blocks and can result in a strict weak ordering violation.
Fix this by checking that all exiting blocks dominate the latch first,
which means that we have a total dominance order. This makes the code
structure here align with what optimizeLoopExits() does.
Fixes https://github.com/llvm/llvm-project/issues/108618.
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.
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.
The integer case in genLoopLimit reduces down to a special case for narrowing the bitwidth of the limit, and then performing the same expansion we would for a pointer IV.
Differential Revision: https://reviews.llvm.org/D146638
Note that the comments being removed appear to be very out of sync with the actual code in question.
Differential Revision: https://reviews.llvm.org/D146468
This option is switched off by default, and it seems that it has never worked correctly.
What it basically does is: it remembers current BECount SCEV, and after all transforms
tries to validate some facts for it. However, between these two points this SCEV may
become invalid (e.g. because some SCEVUnknown it references may be deleted as dead
code). So basically it may work with broken pointers.
Besides, its implementation does strange things (e.g. forgetLoop) which are invasive and
may affect behavior in other parts of the system (specifically verification), concealing some
other problems. Another issue is that it may use SCEVCouldNotCompute object without
checking this.
The option is not used in any unit tests, and if switched on by default, the following tests
fail:
```
********************
Failed Tests (14):
LLVM :: Transforms/IndVarSimplify/2005-06-15-InstMoveCrash.ll
LLVM :: Transforms/IndVarSimplify/2007-06-06-DeleteDanglesPtr.ll
LLVM :: Transforms/IndVarSimplify/2008-10-03-CouldNotCompute.ll
LLVM :: Transforms/IndVarSimplify/2009-05-24-useafterfree.ll
LLVM :: Transforms/IndVarSimplify/2011-10-27-lftrnull.ll
LLVM :: Transforms/IndVarSimplify/ARM/code-size.ll
LLVM :: Transforms/IndVarSimplify/X86/deterministic-scev-verify.ll
LLVM :: Transforms/IndVarSimplify/X86/pr57187.ll
LLVM :: Transforms/IndVarSimplify/X86/verify-scev.ll
LLVM :: Transforms/IndVarSimplify/bbi-63564.ll
LLVM :: Transforms/IndVarSimplify/invalidate-modified-lcssa-phi.ll
LLVM :: Transforms/IndVarSimplify/loop-predication.ll
LLVM :: Transforms/IndVarSimplify/post-inc-range.ll
LLVM :: Transforms/IndVarSimplify/turn-to-invariant.ll
********************
Unexpectedly Passed Tests (1):
LLVM :: Transforms/IndVarSimplify/pr55689.ll
```
None of these looks like real problems found by verification, these are
bugs in the verifying code itself (such as use of deleted SCEVs and
SCEVCouldNotCompute's).
I think it all gives enough justification for its removal.
https://github.com/llvm/llvm-project/issues/61302
Differential Revision: https://reviews.llvm.org/D145894
Reviewed By: nikic
DFAJumpThreading
JumpThreading
LibCallsShrink
LoopVectorize
SLPVectorizer
DeadStoreElimination
AggressiveDCE
CorrelatedValuePropagation
IndVarSimplify
These are part of the optimization pipeline, of which the legacy version is deprecated and being removed.
The motivation is that 'createInvariantCond' unconditionally
builds icmp in the loop block, while it could always do it
in preheader. Build it in preheader instead.
Patch by Aleksandr Popov!
Differential Revision: https://reviews.llvm.org/D141994
Reviewed By: nikic
This patch does two things, both related to support of multi-exit loops with
many exits that have known symbolic max exit count. They can theoretically
go independently, but I don't know how to write a test showing separate
impact.
Part 1: `SkipLastIter` can be set to `true` not when a particular exit has exit
count same as the whole loop (and therefore it must exit on the last iteration),
but when the aggregate of first few exits has umin same as whole loop exit count.
It means that it's not known which of them will exit exactly, but one of them will.
Part 2: when `SkipLastIter` is set, and exit count is `umin(a, b, c)`, instead of
`umin(a, b, c) - 1` use `umin(a - 1, b - 1, c - 1)`. We don't care about overflows
here, but the further logic knows how to deal with umin by element, but the
`SCEVAddExpr` node will confuse it.
Differential Revision: https://reviews.llvm.org/D141361
Reviewed By: nikic
When exit by condition `C1` dominates exit by condition `C2`, and
max symbolic exit count for `C1` matches those for loop, we will
apply more optimistic logic to `C2` by setting `SkipLastIter` for it,
meaning that it will do 1 iteration less because the dominating branch
must exit on the last loop iteration.
But when we have a single exit by condition `C1 & C2`, we cannot
apply the same logic, because there is no dominating condition.
However, if we can prove that the symbolic max exit count of `C1 & C2`
matches those of `C1`, it means that for `C2` we can assume that it
doesn't matter on the last iteration (because the whole thing is `false`
because `C1` must be `false`). Therefore, in this situation, we can handle
`C2` as if it had `SkipLastIter`.
Differential Revision: https://reviews.llvm.org/D139934
Reviewed By: nikic
Similar to how `makeArrayRef` is deprecated in favor of deduction guides, do the
same for `makeMutableArrayRef`.
Once all of the places in-tree are using the deduction guides for
`MutableArrayRef`, we can mark `makeMutableArrayRef` as deprecated.
Differential Revision: https://reviews.llvm.org/D141814
This patch allows optimizeLoopExitWithUnknownExitCount to deal with
branches by conditions that are not immediately ICmp's, but aggregates
of ICmp's joined by arithmetic or logical AND/OR. Each ICmp is optimized
independently.
Differential Revision: https://reviews.llvm.org/D139832
Reviewed By: nikic
This patch updates propgatesPoison to take a Use as argument and
propagatesPoison now returns true if the passed in operand causes the
user to yield poison if the operand is poison
This allows propagating poison if the condition of a select is poison.
This helps improve results for programUndefinedIfUndefOrPoison.
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D111643
There was a crippled version of this transform for Inverted predicate, so the same
query was done twice. Advanced version of this transform wasn't implemented for
inverted condition. Thus, the code was hard to read. The only real purpose of the
Inverted param was to make a simple isKnownPredicateAt query.
Instead if this, use evaluatePredicateAt to solve the task for both inverted and
non-inverted predicate. This slightly changes the order of queries, but effectively
it should save some time by avoiding duplicating queries, and simplifies the code a lot.
I also could not find any evidence that we ever eliminate anything with Inverted = true,
but conservatively preserved the current behavior. Maybe we can remove it and save
some compile time.
Differential Revision: https://reviews.llvm.org/D139814
Reviewed By: nikic
Old logic: when loop symbolic max exit count matched *exact* block exit count,
assume that all subsequent blocks will do 1 iteration less.
New logic: when loop symbolic max exit count matched *symbolic max* block exit count,
assume that all subsequent blocks will do 1 iteration less.
The new logic is still legal and is more permissive in situations when exact
block exit count is not known.
Differential Revision: https://reviews.llvm.org/D139692
Reviewed By: nikic
