[SCEV] Cache operands used in BEInfo (NFC)

When memoized values for a SCEV expressions are dropped, we also
drop all BECounts that make use of the SCEV expression. This is done
by iterating over all

[SCEV] Cache operands used in BEInfo (NFC)

When memoized values for a SCEV expressions are dropped, we also
drop all BECounts that make use of the SCEV expression. This is done
by iterating over all the ExitNotTaken counts and (recursively)
checking whether they use the SCEV expression. If there are many
exits, this will take a lot of time.

This patch improves the situation by pre-computing a set of all
used operands, so that we can determine whether a certain BEInfo
needs to be invalidated using a simple set lookup. Will still need
to loop over all BEInfos though.

This makes for a mild improvement on non-degenerate cases:
https://llvm-compile-time-tracker.com/compare.php?from=b661a55a253f4a1cf5a0fbcb86e5ba7b9fb1387b&to=be1393f450e594c53f0ad7e62339a6bc831b16f6&stat=instructions

For the degenerate case from https://bugs.llvm.org/show_bug.cgi?id=50384,
for n=128 I'm seeing run time drop from 1.6s to 1.1s.

Differential Revision: https://reviews.llvm.org/D102796

show more ...

[SCEV] Cleanup doesIVOverflowOnX checks [NFC]

Stylistic changes only.
1) Don't pass a parameter just to do an early exit.
2) Use a name which matches actual behavior.

[SCEV] Remove unused parameter from computeBECount [NFC]

All callers pass "false" for the Equality parameter. Kill the dead code, and update the function block comment.

[ScalarEvolution] Remove unused ExitLimit::hasOperand() method (NFC)

We only use BackedgeTakenInfo::hasOperand().

[SCEV] Apply guards to max with non-unitary steps.

We already apply loop-guards when computing the maximum with unitary
steps. This extends the code to also do so when dealing with non-unitary
steps

[SCEV] Apply guards to max with non-unitary steps.

We already apply loop-guards when computing the maximum with unitary
steps. This extends the code to also do so when dealing with non-unitary
steps.

This allows us to infer a tighter maximum in some cases.

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D102267

show more ...

[SCEV] Handle and/or in applyLoopGuards()

applyLoopGuards() already combines conditions from multiple nested
guards. However, it cannot use multiple conditions on the same guard,
combined using and/

[SCEV] Handle and/or in applyLoopGuards()

applyLoopGuards() already combines conditions from multiple nested
guards. However, it cannot use multiple conditions on the same guard,
combined using and/or. Add support for this by recursing into either
`and` or `or`, depending on the direction of the branch.

Differential Revision: https://reviews.llvm.org/D101692

show more ...

[SCEV] By more careful when traversing phis in isImpliedViaMerge.

I think currently isImpliedViaMerge can incorrectly return true for phis
in a loop/cycle, if the found condition involves the previo

[SCEV] By more careful when traversing phis in isImpliedViaMerge.

I think currently isImpliedViaMerge can incorrectly return true for phis
in a loop/cycle, if the found condition involves the previous value of

Consider the case in exit_cond_depends_on_inner_loop.

At some point, we call (modulo simplifications)
isImpliedViaMerge(<=, %x.lcssa, -1, %call, -1).

The existing code tries to prove IncV <= -1 for all incoming values
InvV using the found condition (%call <= -1). At the moment this succeeds,
but only because it does not compare the same runtime value. The found
condition checks the value of the last iteration, but the incoming value
is from the *previous* iteration.

Hence we incorrectly determine that the *previous* value was <= -1,
which may not be true.

I think we need to be more careful when looking at the incoming values
here. In particular, we need to rule out that a found condition refers to
any value that may refer to one of the previous iterations. I'm not sure
there's a reliable way to do so (that also works of irreducible control
flow).

So for now this patch adds an additional requirement that the incoming
value must properly dominate the phi block. This should ensure the
values do not change in a cycle. I am not entirely sure if will catch
all cases and I appreciate a through second look in that regard.

Alternatively we could also unconditionally bail out in this case,
instead of checking the incoming values

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D101829

show more ...

[SCEV] Simplify backedge count clearing (NFC)

This seems to be a leftover from when the BackedgeTakenInfo
stored multiple exit counts with manual memory management. At
some point this was switchted

[SCEV] Simplify backedge count clearing (NFC)

This seems to be a leftover from when the BackedgeTakenInfo
stored multiple exit counts with manual memory management. At
some point this was switchted to a simple vector, and there should
be no need to micro-manage the clearing anymore. We can simply
drop the loop from the map and the the destructor do its job.

show more ...

[SCEV] Avoid range intersection idiom in getRangeForUnkownRecurrence [NFC]

Addresses a review comment from D101181

[SCEV] Compute ranges for ashr recurrences

Straight forward extension to the recently added infrastructure which was pioneered with shl. This was originally posted as part of D99687, but split off f

[SCEV] Compute ranges for ashr recurrences

Straight forward extension to the recently added infrastructure which was pioneered with shl. This was originally posted as part of D99687, but split off for ease of review.

(I also decided to exclude the unknown start sign case explicitly for simplicity of understanding.)

Differential Revision: https://reviews.llvm.org/D101181

show more ...

[SCEV] Handle uge/ugt predicates in applyLoopGuards()

These can be handled the same way as ule/ult, just using umax
instead of umin. This is useful in cases where the umax prevents
the upper bound f

[SCEV] Handle uge/ugt predicates in applyLoopGuards()

These can be handled the same way as ule/ult, just using umax
instead of umin. This is useful in cases where the umax prevents
the upper bound from overflowing.

Differential Revision: https://reviews.llvm.org/D101196

show more ...

[SCEV] Fix applyLoopGuards() chaining for ne predicates

ICMP_NE predicates directly overwrote the rewritten result,
instead of chaining it with previous rewrites, as was done for
ICMP_ULT and ICMP_U

[SCEV] Fix applyLoopGuards() chaining for ne predicates

ICMP_NE predicates directly overwrote the rewritten result,
instead of chaining it with previous rewrites, as was done for
ICMP_ULT and ICMP_ULE. This means that some guards were effectively
discarded, depending on their order.

show more ...

[SCEV] Compute ranges for lshr recurrences

Straight forward extension to the recently added infrastructure which was pioneered with shl.

Differential Revision: https://reviews.llvm.org/D99687

[SCEV] Fix -Wunused-variable warning (NFC)

GCC warning:
```
/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp: In member function ‘const llvm::SCEV* llvm::ScalarEvolution::getLosslessPtrToIntExpr(

[SCEV] Fix -Wunused-variable warning (NFC)

GCC warning:
```
/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp: In member function ‘const llvm::SCEV* llvm::ScalarEvolution::getLosslessPtrToIntExpr(const llvm::SCEV*, unsigned int)::SCEVPtrToIntSinkingRewriter::visitUnknown(const llvm::SCEVUnknown*)’:
/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:1152:13: warning: unused variable ‘ExprPtrTy’ [-Wunused-variable]
1152 | Type *ExprPtrTy = Expr->getType();
| ^~~~~~~~~
```

show more ...

Rearrange code to reduce diff for D99687 [nfc]

Adding the switches to reduce diffs. I'm about to split that into an lshr part and an ashr part, doing the NFC part first makes it easier to maintain

Rearrange code to reduce diff for D99687 [nfc]

Adding the switches to reduce diffs. I'm about to split that into an lshr part and an ashr part, doing the NFC part first makes it easier to maintain both diffs.

show more ...

[NFC][SCEV] Split getLosslessPtrToIntExpr out of getPtrToIntExpr()

[NFC][SCEV] Assert that we don't try to create SCEVPtrToIntExpr of a non-integral pointer

ptr<->int casts are only valid for integral pointes,
defensively assert that we don't try to break that here.

Revert "[SCEV] Model `ashr exact x, C` as `(abs(x) EXACT/u (1<<C)) * signum(x)`"

As being discussed in https://reviews.llvm.org/D100721,
this modelling is lossy, we can't reconstruct `ash`/`ashr exa

Revert "[SCEV] Model `ashr exact x, C` as `(abs(x) EXACT/u (1<<C)) * signum(x)`"

As being discussed in https://reviews.llvm.org/D100721,
this modelling is lossy, we can't reconstruct `ash`/`ashr exact`
from it, which means that whenever we actually expand the IR,
we've just pessimized the code..

It would be good to model this pattern, after all it comes up every time
you want to compute a distance between two pointers, but not at this cost.

This reverts commit ec54867df5e7f20e12146e628af34f0384308bcb.

show more ...

Revert "[SCEV] Don't walk uses of phis without SCEV expression when forgetting"

This reverts commit faf9f11589ce892b31d271917cf840f8ca903221.

Issues with this patch have been reported in
https://re

Revert "[SCEV] Don't walk uses of phis without SCEV expression when forgetting"

This reverts commit faf9f11589ce892b31d271917cf840f8ca903221.

Issues with this patch have been reported in
https://reviews.llvm.org/D100264#2689917 and
https://bugs.llvm.org/show_bug.cgi?id=49967.

show more ...

[SCEV] Don't walk uses of phis without SCEV expression when forgetting

I've run into some cases where a large fraction of compile-time is
spent invalidating SCEV. One of the causes is forgetLoop(),

[SCEV] Don't walk uses of phis without SCEV expression when forgetting

I've run into some cases where a large fraction of compile-time is
spent invalidating SCEV. One of the causes is forgetLoop(), which
walks all values that are def-use reachable from the loop header
phis. When invalidating a topmost loop, that might be close to all
values in a function. Additionally, it's fairly common for there to
not actually be anything to invalidate, but we'll still be performing
this walk again and again.

My first thought was that we don't need to continue walking the uses
if the current value doesn't have a SCEV expression. However, this
isn't quite right, because SCEV construction can skip over values
(e.g. for a chain of adds, we might only create a SCEV expression
for the final value).

What this patch does instead is to only walk the (full) def-use chain
of loop phis that have a SCEV expression. If there's no expression
for a phi, then we also don't have any dependent expressions to
invalidate.

Differential Revision: https://reviews.llvm.org/D100264

show more ...

[NFC][ConstantRange] Add 'icmp' helper method

"Does the predicate hold between two ranges?"

Not very surprisingly, some places were already doing this check,
without explicitly naming the algorithm

[NFC][ConstantRange] Add 'icmp' helper method

"Does the predicate hold between two ranges?"

Not very surprisingly, some places were already doing this check,
without explicitly naming the algorithm, cleanup them all.

show more ...

Revert "[NFC][ConstantRange] Add 'icmp' helper method"

This reverts commit 17cf2c94230bc107e7294ef84fad3b47f4cd1b73.

[NFC][ConstantRange] Add 'icmp' helper method

"Does the predicate hold between two ranges?"

Not very surprisingly, some places were already doing this check,
without explicitly naming the algorithm

[NFC][ConstantRange] Add 'icmp' helper method

"Does the predicate hold between two ranges?"

Not very surprisingly, some places were already doing this check,
without explicitly naming the algorithm, cleanup them all.

show more ...

[SCEV] Fix false-positive recognition of simple recurrences. PR49856

A value from reachable block may come to a Phi node as its input from
unreachable block. This may confuse matchSimpleRecurrence

[SCEV] Fix false-positive recognition of simple recurrences. PR49856

A value from reachable block may come to a Phi node as its input from
unreachable block. This may confuse matchSimpleRecurrence which
has no access to DomTree and can falsely recognize something as a recurrency
because of this effect, as the attached test shows.

Patch `ae7b1e` deals with half of this problem, but it only accounts from
the case when an unreachable instruction comes to Phi as an input.

This patch provides a generalization by checking that no Phi block's
predecessor is unreachable (no matter what the input is).

Differential Revision: https://reviews.llvm.org/D99929
Reviewed By: reames

show more ...

[SCEV] Handle unreachable binop when matching shift recurrence

This fixes an issue introduced with my change d4648e, and reported in pr49768.

The root problem is that dominance collapses in unreach

[SCEV] Handle unreachable binop when matching shift recurrence

This fixes an issue introduced with my change d4648e, and reported in pr49768.

The root problem is that dominance collapses in unreachable code, and that LoopInfo explicitly only models reachable code. Since the recurrence matcher doesn't filter by reachability (and can't easily because not all consumers have domtree), we need to bailout before assuming that finding a recurrence implies we found a loop.

show more ...