| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
|
|
|
|
|
|
`ScalarEvolution::howFarToZero` (#131522)
https://github.com/llvm/llvm-project/pull/94525 assumes that the loop
will be infinite when the stride is zero. However, it doesn't hold when
the start value of addrec is also zero.
Closes https://github.com/llvm/llvm-project/issues/131465.
|
|
isBasicBlockEntryGuardedByCond inadvertedenly drops samesign information
when calling ICmpInst::getNonStrictPredicate. Fix this.
|
|
The commit f5d24e6c is buggy, and following miscompiles have been
reported: #126409 and
https://github.com/llvm/llvm-project/pull/124270#issuecomment-2647222903
Revert it while we investigate.
|
|
The code already guards against values coming from a previous iteration
using properlyDominates(). However, addrecs are considered to properly
dominate the loop they are defined in.
Handle this special case separately, by checking for expressions that
have computable loop evolution (this should cover cases like a zext of
an addrec as well).
I considered changing the definition of properlyDominates() instead, but
decided against it. The current definition is useful in other context,
e.g. when deciding whether an expression is safe to expand in a given
block.
Fixes https://github.com/llvm/llvm-project/issues/126012.
|
|
Use CmpPredicate::getMatching in isImpliedCondBalancedTypes to pass
samesign information to isImpliedViaOperations, and teach it to call
CmpPredicate::getPreferredSignedPredicate, effectively making it
optimize with samesign information.
|
|
Follow up on 60dc450 (SCEV: migrate to CmpPredicate (NFC)) to migrate
the missed ScalarEvolution::LoopInvariantPredicate to CmpPredicate.
|
|
This is a followup to #117152. That patch introduced a check for
UB/poison on BEValue. However, the SCEV we're actually going to use is
Shifted. In some cases, it's possible for Shifted to contain UB, while
BEValue doesn't.
In the test case the values are:
BEValue: (-1 * (zext i8 (-83 + ((-83 /u {1,+,1}<%loop>) *
{-1,+,-1}<%loop>)) to i32))<nuw><nsw>
Shifted: (-173 + (-1 * (zext i8 ((-83 /u {0,+,1}<%loop>) *
{0,+,-1}<%loop>) to i32))<nuw><nsw>)<nuw><nsw>
Fixes https://github.com/llvm/llvm-project/issues/123550.
|
|
Follow up to https://github.com/llvm/llvm-project/issues/123569
|
|
(#123662)
Attempting to collect loop guards for loops without a predecessor can
lead to non-terminating recursion trying to construct a SCEV.
Fixes https://github.com/llvm/llvm-project/issues/122913.
|
|
In preparation to teach implied-cond functions about samesign, migrate
integer-compare predicates that flow through to the functions from
CmpInst::Predicate to CmpPredicate.
|
|
|
|
collecting loop guards. (#120749)
When `collectFromBlock` is called without a predecessor (in particular
for loops that don't have a unique predecessor outside the loop) we
never start climbing the predecessor chain, and thus don't mark the
starting block as visited.
Fixes https://github.com/llvm/llvm-project/issues/120615.
|
|
When adding a new predicate to a union predicate, some of the existing
predicates may be implied by the new predicate. Remove any existing
predicates that are already implied by the new predicate.
Depends on https://github.com/llvm/llvm-project/pull/118184 to show the
main benefit.
PR: https://github.com/llvm/llvm-project/pull/118185
|
|
When assumptions are present `Terms.size()` does not actually count the
number of conditions collected from dominating branches; introduce a
separate counter.
Fixes https://github.com/llvm/llvm-project/issues/120237
|
|
Fixes a crash when trying to extend the pointer start value to a narrow
integer type after b6c29fdffd65.
|
|
This patch adds initial matchers for unary and binary SCEV expressions
and specializes it for SExt, ZExt and binary add expressions.
Also adds matchers for SCEVConstant and SCEVUnknown.
This patch only converts a few instances to use the new matchers to make
sure everything builds as expected for now.
The goal of the matchers is to hopefully make it slightly easier to
write code matching SCEV patterns.
Depends on https://github.com/llvm/llvm-project/pull/119389
PR: https://github.com/llvm/llvm-project/pull/119390
|
|
A SCEVWrapPredicate A implies B, if
* they have the same flag,
* both steps are positive and
* B's start and step are ULE/SLE (for NSUW/NSSW) than A's.
See https://alive2.llvm.org/ce/z/n2T4ss (first pair with known constants
as strides, second pair with variable strides).
Note that this is limited to steps of the same size, due to NSUW having
slightly different semantics than regular NUW. We should be able to
remove this restriction for NSSW (which matches NSW) in the future.
PR: https://github.com/llvm/llvm-project/pull/118184
|
|
Add initial pattern matching for SCEV constants. Follow-up patches will
add additional matchers for various SCEV expressions.
This patch only converts a few instances to use the new matchers to make
sure everything builds as expected for now.
PR: https://github.com/llvm/llvm-project/pull/119389
|
|
identical (#115945)
Helps SCEV analyze some special phi nodes, allowing the computation of
loop trip count in cases like the following:
https://godbolt.org/z/xGs1d81TW
|
|
See the following case:
```
; bin/opt -passes="print<scalar-evolution>" test.ll --disable-output
define i32 @widget() {
b:
br label %b1
b1: ; preds = %b5, %b
%phi = phi i32 [ 0, %b ], [ %udiv6, %b5 ]
%phi2 = phi i32 [ 1, %b ], [ %add, %b5 ]
%icmp = icmp eq i32 %phi, 0
br i1 %icmp, label %b3, label %b8
b3: ; preds = %b1
%udiv = udiv i32 10, %phi2
%urem = urem i32 %udiv, 10
%icmp4 = icmp eq i32 %urem, 0
br i1 %icmp4, label %b7, label %b5
b5: ; preds = %b3
%udiv6 = udiv i32 %phi2, 0
%add = add i32 %phi2, 1
br label %b1
b7: ; preds = %b3
ret i32 5
b8: ; preds = %b1
ret i32 7
}
```
```
%phi2 = phi i32 [ 1, %b ], [ %add, %b5 ] --> {1,+,1}<nuw><nsw><%b1>
%udiv6 = udiv i32 %phi2, 0 --> ({1,+,1}<nuw><nsw><%b1> /u 0)
%phi = phi i32 [ 0, %b ], [ %udiv6, %b5 ] --> ({0,+,1}<nuw><nsw><%b1> /u 0)
```
`ScalarEvolution::createAddRecFromPHI` gives a wrong SCEV result for
`%phi`:
https://github.com/llvm/llvm-project/blob/d7d6fb1804415b0f3e7f1cc9290bfb3d711cb707/llvm/lib/Analysis/ScalarEvolution.cpp#L5926-L5950
It converts `phi(0, ({1,+,1}<nuw><nsw><%b1> /u 0))` into `phi(0 / 0,
({1,+,1}<nuw><nsw><%b1> /u 0))`. Then it simplifies the expr into
`{0,+,1}<nuw><nsw><%b1> /u 0`.
As we did in
https://github.com/llvm/llvm-project/commit/acd700a24b6f767413db3d525e06d03e4245aa40,
this patch disallows udiv simplification if we cannot prove that the
denominator is a well-defined non-zero value.
Fixes https://github.com/llvm/llvm-project/issues/117133.
|
|
Counterexample: 219 is a multiple of 73. But `sext i8 219 to i16 =
65499` is not.
Fixes https://github.com/llvm/llvm-project/issues/116483.
|
|
De-duplicate the functions getSignedPredicate and getUnsignedPredicate,
nearly identical versions of which were present in CmpInst and ICmpInst,
creating less confusion.
|
|
Address post-commit comments for
https://github.com/llvm/llvm-project/pull/113915.
|
|
incoming values (#113915)
This patch aims to strengthen collection of loop guards by processing
PHI nodes with multiple incoming values as follows: collect guards for
all incoming values/blocks and try to merge them into a single one for
the PHI node.
The goal is to determine tighter bounds on the trip counts of scalar
tail loops after vectorization, helping to avoid unnecessary transforms.
In particular we'd like to avoid vectorizing scalar tails of
hand-vectorized loops, for example in
[Transforms/PhaseOrdering/X86/pr38280.ll](https://github.com/llvm/llvm-project/blob/231e03ba7e82896847dbc27d457dbb208f04699c/llvm/test/Transforms/PhaseOrdering/X86/pr38280.ll),
discovered via https://github.com/llvm/llvm-project/pull/108190
Compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=a55248789ed3f653740e0723d016203b9d585f26&to=500e4c46e79f60b93b11a752698c520e345948e3&stat=instructions:u
PR: https://github.com/llvm/llvm-project/pull/113915
|
|
See the following case:
```
@GlobIntONE = global i32 0, align 4
define ptr @src() {
entry:
br label %for.body.peel.begin
for.body.peel.begin: ; preds = %entry
br label %for.body.peel
for.body.peel: ; preds = %for.body.peel.begin
br i1 true, label %cleanup.peel, label %cleanup.loopexit.peel
cleanup.loopexit.peel: ; preds = %for.body.peel
br label %cleanup.peel
cleanup.peel: ; preds = %cleanup.loopexit.peel, %for.body.peel
%retval.2.peel = phi ptr [ undef, %for.body.peel ], [ @GlobIntONE, %cleanup.loopexit.peel ]
br i1 true, label %for.body.peel.next, label %cleanup7
for.body.peel.next: ; preds = %cleanup.peel
br label %for.body.peel.next1
for.body.peel.next1: ; preds = %for.body.peel.next
br label %entry.peel.newph
entry.peel.newph: ; preds = %for.body.peel.next1
br label %for.body
for.body: ; preds = %cleanup, %entry.peel.newph
%retval.0 = phi ptr [ %retval.2.peel, %entry.peel.newph ], [ %retval.2, %cleanup ]
br i1 false, label %cleanup, label %cleanup.loopexit
cleanup.loopexit: ; preds = %for.body
br label %cleanup
cleanup: ; preds = %cleanup.loopexit, %for.body
%retval.2 = phi ptr [ %retval.0, %for.body ], [ @GlobIntONE, %cleanup.loopexit ]
br i1 false, label %for.body, label %cleanup7.loopexit
cleanup7.loopexit: ; preds = %cleanup
%retval.2.lcssa.ph = phi ptr [ %retval.2, %cleanup ]
br label %cleanup7
cleanup7: ; preds = %cleanup7.loopexit, %cleanup.peel
%retval.2.lcssa = phi ptr [ %retval.2.peel, %cleanup.peel ], [ %retval.2.lcssa.ph, %cleanup7.loopexit ]
ret ptr %retval.2.lcssa
}
define ptr @tgt() {
entry:
br label %for.body.peel.begin
for.body.peel.begin: ; preds = %entry
br label %for.body.peel
for.body.peel: ; preds = %for.body.peel.begin
br i1 true, label %cleanup.peel, label %cleanup.loopexit.peel
cleanup.loopexit.peel: ; preds = %for.body.peel
br label %cleanup.peel
cleanup.peel: ; preds = %cleanup.loopexit.peel, %for.body.peel
%retval.2.peel = phi ptr [ undef, %for.body.peel ], [ @GlobIntONE, %cleanup.loopexit.peel ]
br i1 true, label %for.body.peel.next, label %cleanup7
for.body.peel.next: ; preds = %cleanup.peel
br label %for.body.peel.next1
for.body.peel.next1: ; preds = %for.body.peel.next
br label %entry.peel.newph
entry.peel.newph: ; preds = %for.body.peel.next1
br label %for.body
for.body: ; preds = %cleanup, %entry.peel.newph
br i1 false, label %cleanup, label %cleanup.loopexit
cleanup.loopexit: ; preds = %for.body
br label %cleanup
cleanup: ; preds = %cleanup.loopexit, %for.body
br i1 false, label %for.body, label %cleanup7.loopexit
cleanup7.loopexit: ; preds = %cleanup
%retval.2.lcssa.ph = phi ptr [ %retval.2.peel, %cleanup ]
br label %cleanup7
cleanup7: ; preds = %cleanup7.loopexit, %cleanup.peel
%retval.2.lcssa = phi ptr [ %retval.2.peel, %cleanup.peel ], [ %retval.2.lcssa.ph, %cleanup7.loopexit ]
ret ptr %retval.2.lcssa
}
```
1. `simplifyInstruction(%retval.2.peel)` returns `@GlobIntONE`. Thus,
`ScalarEvolution::createNodeForPHI` returns SCEV expr `@GlobIntONE` for
`%retval.2.peel`.
2. `SimplifyIndvar::replaceIVUserWithLoopInvariant` tries to replace the
use of `%retval.2.peel` in `%retval.2.lcssa.ph` with `@GlobIntONE`.
3. `simplifyLoopAfterUnroll -> simplifyLoopIVs -> SCEVExpander::expand`
reuses `%retval.2.peel = phi ptr [ undef, %for.body.peel ], [
@GlobIntONE, %cleanup.loopexit.peel ]` to generate code for
`@GlobIntONE`. It is incorrect.
This patch disallows simplifying `phi(undef, X)` to `X` by setting
`CanUseUndef` to false.
Closes https://github.com/llvm/llvm-project/issues/114879.
|
|
|
|
(#80309)
This fixes all the places that hit the new assertion added in
https://github.com/llvm/llvm-project/pull/106524 in tests. That is,
cases where the value passed to the APInt constructor is not an N-bit
signed/unsigned integer, where N is the bit width and signedness is
determined by the isSigned flag.
The fixes either set the correct value for isSigned, set the
implicitTrunc flag, or perform more calculations inside APInt.
Note that the assertion is currently still disabled by default, so this
patch is mostly NFC.
|
|
Add `Intrinsic::getDeclarationIfExists` to lookup an existing
declaration of an intrinsic in a `Module`.
|
|
Retain SCEVSequentialMinMaxExpr if an operand may trigger UB, e.g. if
there is an UDiv operand that may divide by 0 or poison
PR: https://github.com/llvm/llvm-project/pull/110824
|
|
There are a number of places where we call getSmallConstantMaxTripCount
without passing a vector of predicates:
getSmallBestKnownTC
isIndvarOverflowCheckKnownFalse
computeMaxVF
isMoreProfitable
I've changed all of these to now pass in a predicate vector so that
we get the benefit of making better vectorisation choices when we
know the max trip count for loops that require SCEV predicate checks.
I've tried to add tests that cover all the cases affected by these
changes.
|
|
|
|
Store predicates in ExitLimit and ExitNotTaken in a SmallVector instead
of a SmallPtrSet. This guarantees the predicates can be iterated on in a
predictable manner. This ensures the predicates can be printed and
generated in a predictable order.
This shifts de-duplication of predicates to construction time for
ExitLimit. ExitNotTaken just takes predicates from ExitLimit, so they
should also be free of duplicates.
This was exposed by 2f7ccaf4a8565628a4c7d2b5a49bb45478940be6
(https://github.com/llvm/llvm-project/pull/108777).
Should fix https://lab.llvm.org/buildbot/#/builders/110/builds/1494.
|
|
This can help in cases where pointer alignment info is missing, e.g.
https://github.com/llvm/llvm-project/pull/108210
The predicate is formed for the complex expression that's passed to
SolveLinEquationWithOverflow and the checks could probably be pushed
closer to the root nodes, which in some cases may be cheaper to check.
PR: https://github.com/llvm/llvm-project/pull/108777
|
|
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.
|
|
(#109417)"
This reverts commit 3f37c517fbc40531571f8b9f951a8610b4789cd6.
Lo and behold, I missed a unit test
|
|
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.
|
|
(#106562)
Currently if a loop contains loads that we can prove at compile time
are dereferenceable when certain conditions are satisfied the function
isDereferenceableAndAlignedInLoop will still return false because
getSmallConstantMaxTripCount will return 0 when SCEV predicates
are required. This patch changes getSmallConstantMaxTripCount to take
an optional Predicates pointer argument so that we can permit
functions such as isDereferenceableAndAlignedInLoop to consider more
cases.
|
|
It is almost always simpler to use {} instead of std::nullopt to
initialize an empty ArrayRef. This patch changes all occurrences I could
find in LLVM itself. In future the ArrayRef(std::nullopt_t) constructor
could be deprecated or removed.
|
|
If there are no predicates, the predicated counts should not be
different to the non-predicated ones.
|
|
There are a few places in ScalarEvolution.cpp where we copy predicates
from one list to another and they have a similar pattern:
for (const auto *P : ENT.Predicates)
Predicates->push_back(P);
We can avoid the loop by writing them like this:
Predicates->append(ENT.Predicates.begin(), ENT.Predicates.end());
which may end up being more efficient since we only have to try
reserving more space once.
|
|
The SCEV expression `((-C + (C smax %x)) /u %x)` can be folded
to zero for any positive constant C.
Proof: https://alive2.llvm.org/ce/z/_dLm8C.
|
|
Due to a reviewer request on PR #88385 I have created this patch
to add a getPredicatedExitCount function, which is similar to
getExitCount except that it uses the predicated backedge taken
information. With PR #88385 we will start to care about more
loops with multiple exits, and want the ability to query exit
counts for a particular exiting block. Such loops may require
predicates in order to be vectorised.
New tests added here:
Analysis/ScalarEvolution/predicated-exit-count.ll
|
|
Use SmallVectorImpl instead of SmallVector for function arguments
to give the caller greater flexibility in choice of initial size.
|
|
objects (#104778)
Whilst dealing with review comments on
https://github.com/llvm/llvm-project/pull/96752
I discovered that SCEV does not know about the dereferenceable attribute
on function arguments so I have updated getRangeRef to make use of it
by calling getPointerDereferenceableBytes.
|
|
Use computeConstantDifference() instead of casting getMinusSCEV() to
SCEVConstant. This can be much faster in some cases, because
computeConstantDifference() computes the result without creating new
SCEV expressions.
This improves LTO/ThinLTO compile-time for lencod by more than 10%.
I've verified that computeConstantDifference() does not produce worse
results than the previous code for anything in llvm-test-suite. This
required raising the iteration cutoff to 6. I ended up increasing it to
8 just to be on the safe side (for code outside llvm-test-suite), and
because this doesn't materially affect compile-time anyway (we'll almost
always bail out earlier).
|
|
|
|
Inside computeConstantDifference(), handle the case where both sides are
of the form `C * %x`, in which case we can strip off the common
multiplication (as long as we remember to multiply by it for the
following difference calculation).
There is an obvious alternative implementation here, which would be to
directly decompose multiplies inside the "Multiplicity" accumulation.
This does work, but I've found this to be both significantly slower
(because everything has to work on APInt) and more complex in
implementation (e.g. because we now need to match back the new More/Less
with an arbitrary factor) without providing more power in practice. As
such, I went for the simpler variant here.
This is the last step to make computeConstantDifference() sufficiently
powerful to replace existing uses of
`cast<SCEVConstant>(getMinusSCEV())` with it.
|
