[SCEV] Store predicates for EL/ENT in SmallVector.

Store predicates in ExitLimit and ExitNotTaken in a SmallVector instead
of a SmallPtrSet. This guarantees the predicates can be iterated on in a
pr

[SCEV] Store predicates for EL/ENT in SmallVector.

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.

show more ...

[SCEV] Add predicate in SolveLinEq to ensure B is a multiple of A. (#108777)

This can help in cases where pointer alignment info is missing, e.g.
https://github.com/llvm/llvm-project/pull/108210

[SCEV] Add predicate in SolveLinEq to ensure B is a multiple of A. (#108777)

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

show more ...

[NFC] Reapply 3f37c517f, SmallDenseMap speedups

This time with 100% more building unit tests. Original commit message follows.

[NFC] Switch a number of DenseMaps to SmallDenseMaps for speedup (#109

[NFC] Reapply 3f37c517f, SmallDenseMap speedups

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.

show more ...

Revert "[NFC] Switch a number of DenseMaps to SmallDenseMaps for speedup (#109417)"

This reverts commit 3f37c517fbc40531571f8b9f951a8610b4789cd6.

Lo and behold, I missed a unit test

[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 spurio

[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.

show more ...

[Analysis] Teach isDereferenceableAndAlignedInLoop about SCEV predicates (#106562)

Currently if a loop contains loads that we can prove at compile time
are dereferenceable when certain conditions a

[Analysis] Teach isDereferenceableAndAlignedInLoop about SCEV predicates (#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.

show more ...

[LLVM] Use {} instead of std::nullopt to initialize empty ArrayRef (#109133)

It is almost always simpler to use {} instead of std::nullopt to
initialize an empty ArrayRef. This patch changes all oc

[LLVM] Use {} instead of std::nullopt to initialize empty ArrayRef (#109133)

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.

show more ...

[SCEV] Replace redundant !Preds.empty() check with assert. (NFCI)

If there are no predicates, the predicated counts should not be
different to the non-predicated ones.

[Analysis][NFC] Clean-up in ScalarEvolution when copying predicates (#108851)

There are a few places in ScalarEvolution.cpp where we copy predicates
from one list to another and they have a similar

[Analysis][NFC] Clean-up in ScalarEvolution when copying predicates (#108851)

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.

show more ...

[SCEV] BECount to zero if `((-C + (C smax %x)) /u %x), C > 0` holds

The SCEV expression `((-C + (C smax %x)) /u %x)` can be folded
to zero for any positive constant C.

Proof: https://alive2.llvm.or

[SCEV] BECount to zero if `((-C + (C smax %x)) /u %x), C > 0` holds

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.

show more ...

[Analysis] Add getPredicatedExitCount to ScalarEvolution (#105649)

Due to a reviewer request on PR #88385 I have created this patch
to add a getPredicatedExitCount function, which is similar to
ge

[Analysis] Add getPredicatedExitCount to ScalarEvolution (#105649)

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

show more ...

[Analysis][NFC] Use SmallVectorImpl consistently in ScalarEvolution (#105663)

Use SmallVectorImpl instead of SmallVector for function arguments
to give the caller greater flexibility in choice of i

[Analysis][NFC] Use SmallVectorImpl consistently in ScalarEvolution (#105663)

Use SmallVectorImpl instead of SmallVector for function arguments
to give the caller greater flexibility in choice of initial size.

show more ...

[Analysis] Teach ScalarEvolution::getRangeRef about more dereferenceable objects (#104778)

Whilst dealing with review comments on

https://github.com/llvm/llvm-project/pull/96752

I discovered t

[Analysis] Teach ScalarEvolution::getRangeRef about more dereferenceable 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.

show more ...

[LAA] Use computeConstantDifference() (#103725)

Use computeConstantDifference() instead of casting getMinusSCEV() to
SCEVConstant. This can be much faster in some cases, because
computeConstantDif

[LAA] Use computeConstantDifference() (#103725)

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).

show more ...

[Analysis] Use range-based for loops (NFC) (#103540)

[SCEV] Look through multiply in computeConstantDifference() (#103051)

Inside computeConstantDifference(), handle the case where both sides are
of the form `C * %x`, in which case we can strip off t

[SCEV] Look through multiply in computeConstantDifference() (#103051)

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.

show more ...

[SCEV] Fix -Wrange-loop-construct (NFC)

/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:12009:21:
error: loop variable '[S, Mul]' creates a copy from type 'const value_type' (aka 'const llvm::d

[SCEV] Fix -Wrange-loop-construct (NFC)

/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:12009:21:
error: loop variable '[S, Mul]' creates a copy from type 'const value_type' (aka 'const llvm::detail::DenseMapPair<const llvm::SCEV *, int>') [-Werror,-Wrange-loop-construct]
for (const auto [S, Mul] : Multiplicity) {
^
/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:12009:10:
note: use reference type 'const value_type &' (aka 'const llvm::detail::DenseMapPair<const llvm::SCEV *, int> &') to prevent copying
for (const auto [S, Mul] : Multiplicity) {
^~~~~~~~~~~~~~~~~~~~~
&

show more ...

[SCEV] Handle more add/addrec mixes in computeConstantDifference() (#101999)

computeConstantDifference() can currently look through addrecs with
identical steps, and then through adds with identica

[SCEV] Handle more add/addrec mixes in computeConstantDifference() (#101999)

computeConstantDifference() can currently look through addrecs with
identical steps, and then through adds with identical operands (apart
from constants).

However, it fails to handle minor variations, such as two nested add
recs, or an outer add with an inner addrec (rather than the other way
around).

This patch supports these cases by adding a loop over the
simplifications, limited to a small number of iterations. The motivation
is the same as in #101339, to make
computeConstantDifference() powerful enough to replace existing uses of
`dyn_cast<SCEVConstant>(getMinusSCEV())` with it. Though as the IR test
diff shows, other callers may also benefit.

show more ...

[SCEV] Consolidate code for proving wrap flags of controlling finite IVs (#101404)

The canAssumeNoSelfWrap routine in howManyLessThans was doing two subtly
inter-related things. First, it was provi

[SCEV] Consolidate code for proving wrap flags of controlling finite IVs (#101404)

The canAssumeNoSelfWrap routine in howManyLessThans was doing two subtly
inter-related things. First, it was proving no-self-wrap. This exactly
duplicates the existing logic in the caller. Second, it was establishing
the precondition for the nw->nsw/nuw inference. Specifically, we need to
know that *this* exit must be taken for the inference to be sound.
Otherwise, another (possible abnormal) exit could be taken in the
iteration where this IV would become poison.

This change moves all of that logic into the caller, and caches the
resulting nuw/nsw flags in the AddRec. This centralizes the logic in one
place, and makes it clear that it all depends on controlling the sole
exit.

We do loose a couple cases with SCEV predication. Specifically, if SCEV
predication was able to convert e.g. zext(addrec) into an addrec(zext)
using predication, but didn't record the nuw fact on the new addrec,
then the consuming code can no longer fix this up. I don't think this
case particularly matters.

---------

Co-authored-by: Nikita Popov <github@npopov.com>

show more ...

[SCEV] Fix incorrect extension in computeConstantDifference()

The Mul factor was zero-extended here, resulting in incorrect
results for integers larger than 64-bit.

As we currently only multiply by

[SCEV] Fix incorrect extension in computeConstantDifference()

The Mul factor was zero-extended here, resulting in incorrect
results for integers larger than 64-bit.

As we currently only multiply by 1 or -1, just split this into
two cases -- there's no need for a full multiplication here.

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

show more ...

[Analysis] Use llvm::set_is_subset (NFC) (#102766)

[llvm] Construct SmallVector with ArrayRef (NFC) (#102712)

Without this patch, the constructor arguments come from
SmallVectorImpl, not ArrayRef. This patch switches them to ArrayRef
so that we c

[llvm] Construct SmallVector with ArrayRef (NFC) (#102712)

Without this patch, the constructor arguments come from
SmallVectorImpl, not ArrayRef. This patch switches them to ArrayRef
so that we can construct SmallVector with a single argument.

Note that LLVM Programmer’s Manual prefers ArrayRef to SmallVectorImpl
for flexibility.

show more ...

[SCEV] Fix warning (NFC)

Produces -Wrange-loop-construct on some buildbots.

[SCEV] Handle more adds in computeConstantDifference() (#101339)

Currently it only deals with the case where we're subtracting adds with
at most one non-constant operand. This patch extends it to c

[SCEV] Handle more adds in computeConstantDifference() (#101339)

Currently it only deals with the case where we're subtracting adds with
at most one non-constant operand. This patch extends it to cancel out
common operands for the subtraction of arbitrary add expressions.

The background here is that I want to replace a getMinusSCEV() call in
LAA with computeConstantDifference():

https://github.com/llvm/llvm-project/blob/93fecc2577ece0329f3bbe2719bbc5b4b9b30010/llvm/lib/Analysis/LoopAccessAnalysis.cpp#L1602-L1603

This particular call is very expensive in some cases (e.g. lencod with
LTO) and computeConstantDifference() could achieve this much more
cheaply, because it does not need to construct new SCEV expressions.

However, the current computeConstantDifference() implementation is too
weak for this and misses many basic cases. This is a step towards making
it more powerful while still keeping it pretty fast.

show more ...

[SCEV] Unify and optimize constant folding (NFC) (#101473)

Add a common constantFoldAndGroupOps() helper that takes care of
constant folding and grouping transforms that are common to all nary
ops

[SCEV] Unify and optimize constant folding (NFC) (#101473)

Add a common constantFoldAndGroupOps() helper that takes care of
constant folding and grouping transforms that are common to all nary
ops. This moves the constant folding prior to grouping, which is more
efficient, and excludes any constant from the sort.

The constant folding has hooks for folding, identity constants and
absorber constants.

This gives a compile-time improvement for SCEV-heavy workloads like
lencod.

show more ...