[SCEV] Make SCEVUnionPredicate externally immutable [NFC]

This is the last major stepping stone before being able to allocate the node via the folding set allocator. That will in turn allow more ge

[SCEV] Make SCEVUnionPredicate externally immutable [NFC]

This is the last major stepping stone before being able to allocate the node via the folding set allocator. That will in turn allow more general SCEV predicate expression trees.

show more ...

[ScalarEvolution] Infer loop max trip count from array accesses

Data references in a loop should not access elements over the
statically allocated size. So we can infer a loop max trip count
from th

[ScalarEvolution] Infer loop max trip count from array accesses

Data references in a loop should not access elements over the
statically allocated size. So we can infer a loop max trip count
from this undefined behavior.

Reviewed By: reames, mkazantsev, nikic

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

show more ...

[unittest] Exercise SCEV's udiv and udiv ceiling routines

The ceiling variant was recently added (due to the work towards D105216), and we're spending a lot of time trying to find optimizations for

[unittest] Exercise SCEV's udiv and udiv ceiling routines

The ceiling variant was recently added (due to the work towards D105216), and we're spending a lot of time trying to find optimizations for the expression. This patch brute forces the space of i8 unsigned divides and checks that we get a correct (well consistent with APInt) result for both udiv and udiv ceiling.

(This is basically what I've been doing locally in a hand rolled C++ program, and I realized there no good reason not to check it in as a unit test which directly exercises the logic on constants.)

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

show more ...

[ScalarEvolution] Strictly enforce pointer/int type rules.

Rules:

1. SCEVUnknown is a pointer if and only if the LLVM IR value is a
pointer.
2. SCEVPtrToInt is never a pointer.
3. If any other S

[ScalarEvolution] Strictly enforce pointer/int type rules.

Rules:

1. SCEVUnknown is a pointer if and only if the LLVM IR value is a
pointer.
2. SCEVPtrToInt is never a pointer.
3. If any other SCEV expression has no pointer operands, the result is
an integer.
4. If a SCEVAddExpr has exactly one pointer operand, the result is a
pointer.
5. If a SCEVAddRecExpr's first operand is a pointer, and it has no other
pointer operands, the result is a pointer.
6. If every operand of a SCEVMinMaxExpr is a pointer, the result is a
pointer.
7. Otherwise, the SCEV expression is invalid.

I'm not sure how useful rule 6 is in practice. If we exclude it, we can
guarantee that ScalarEvolution::getPointerBase always returns a
SCEVUnknown, which might be a helpful property. Anyway, I'll leave that
for a followup.

This is basically mop-up at this point; all the changes with significant
functional effects have landed. Some of the remaining changes could be
split off, but I don't see much point.

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

show more ...

[SCEV] Keep common NUW flags when inlining Add operands.

Currently, NoWrapFlags are dropped if we inline operands of SCEVAddExpr
operands. As a consequence, we always drop flags when building
expres

[SCEV] Keep common NUW flags when inlining Add operands.

Currently, NoWrapFlags are dropped if we inline operands of SCEVAddExpr
operands. As a consequence, we always drop flags when building
expressions like `getAddExpr(A, getAddExpr(B, C, NUW), NUW)`.

We should be able to retain NUW flags common among all inlined
SCEVAddExpr and the original flags.

Reviewed By: nikic, mkazantsev

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

show more ...

[SCEV] Improve handling of not expressions in isImpliedCond()

SCEV currently tries to prove implications of x pred y by also
trying to imply ~y pred ~x. This is expensive in terms of
compile-time (i

[SCEV] Improve handling of not expressions in isImpliedCond()

SCEV currently tries to prove implications of x pred y by also
trying to imply ~y pred ~x. This is expensive in terms of
compile-time (in fact, the majority of isImpliedCond compile-time
is spent here) and generally not fruitful. The issue is that this
also swaps the operands and thus breaks canonical ordering. If
originally we were trying to prove an implication like
X > C1 -> Y > C2, then we'll now try to prove X > C1 -> C3 > ~Y,
which will not work.

The only real case where we can get some use out of this transform
is if the original conditions were in the form X > C1 -> Y < C2, were
then swapped to X > C1 -> C2 > Y and are then swapped again here to
X > C1 -> ~Y > C3.

As such, handle this at a higher level, where we are doing the
swapping in the first place. There's four different ways that we
can line up a predicate and a swapped predicate, so we use some
heuristics to pick some profitable way.

Because we now try this transform at a higher level
(isImpliedCondOperands rather than isImpliedCondOperandsHelper),
we can also prove additional facts. Of the added tests, one was
proven previously while the other wasn't.

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

show more ...

[SCEV] Match 'zext (trunc A to iB) to iY' as URem.

URem operations with constant power-of-2 second operands are modeled as
such. This patch on its own has very little impact (e.g. no changes in
Code

[SCEV] Match 'zext (trunc A to iB) to iY' as URem.

URem operations with constant power-of-2 second operands are modeled as
such. This patch on its own has very little impact (e.g. no changes in
CodeGen for MultiSource/SPEC2000/SPEC2006 on X86 -O3 -flto), but I'll
soon post follow-up patches that make use of it to more accurately
determine the trip multiple.

Reviewed By: mkazantsev

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

show more ...

Re-enable "[SCEV] Prove implications of different type via truncation"

When we need to prove implication of expressions of different type width,
the default strategy is to widen everything to wider

Re-enable "[SCEV] Prove implications of different type via truncation"

When we need to prove implication of expressions of different type width,
the default strategy is to widen everything to wider type and prove in this
type. This does not interact well with AddRecs with negative steps and
unsigned predicates: such AddRec will likely not have a `nuw` flag, and its
`zext` to wider type will not be an AddRec. In contraty, `trunc` of an AddRec
in some cases can easily be proved to be an `AddRec` too.

This patch introduces an alternative way to handling implications of different
type widths. If we can prove that wider type values actually fit in the narrow type,
we truncate them and prove the implication in narrow type.

The return was due to revert of underlying patch that this one depends on.

Unit test temporarily disabled because the required logic in SCEV is switched
off due to compile time reasons.

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

show more ...

Revert "[SCEV] Prove implications of different type via truncation"

This reverts commit 80852a4f2fb154c6094bb9d9e3457757d5a60ad1.

Test is now broken because underlying required patch was also rever

Revert "[SCEV] Prove implications of different type via truncation"

This reverts commit 80852a4f2fb154c6094bb9d9e3457757d5a60ad1.

Test is now broken because underlying required patch was also reverted SUDDENLY.

show more ...

[SCEV] Prove implications of different type via truncation

When we need to prove implication of expressions of different type width,
the default strategy is to widen everything to wider type and pro

[SCEV] Prove implications of different type via truncation

When we need to prove implication of expressions of different type width,
the default strategy is to widen everything to wider type and prove in this
type. This does not interact well with AddRecs with negative steps and
unsigned predicates: such AddRec will likely not have a `nuw` flag, and its
`zext` to wider type will not be an AddRec. In contraty, `trunc` of an AddRec
in some cases can easily be proved to be an `AddRec` too.

This patch introduces an alternative way to handling implications of different
type widths. If we can prove that wider type values actually fit in the narrow type,
we truncate them and prove the implication in narrow type.

Differential Revision: https://reviews.llvm.org/D89548
Reviewed By: fhahn

show more ...

Return "[SCEV] Prove implicaitons via AddRec start"

The initial version of the patch was reverted because it missed the check that
the predicate being proved is actually guarded by this check on 1st

Return "[SCEV] Prove implicaitons via AddRec start"

The initial version of the patch was reverted because it missed the check that
the predicate being proved is actually guarded by this check on 1st iteration.
If it was not executed on 1st iteration (but possibly executes after that), then
it is incorrect to use reasoning about IV start to prove it.

Added the test where the miscompile was seen. Unfortunately, my attempts
to reduce it with bugpoint did not succeed; it can further be reduced when
we understand how to do it without losing the initial bug's notion.

Returning assuming the miscompiles are now gone.

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

show more ...

Revert "[SCEV] Prove implicaitons via AddRec start"

This reverts commit 69acdfe075fa8eb18781f88f4d0cd1ea40fa6e48.

Need to investigate reported miscompiles.

[SCEV] Limited support for unsigned preds in isImpliedViaOperations

The logic there only considers `SLT/SGT` predicates. We can use the same logic
for proving `ULT/UGT` predicates if all involved va

[SCEV] Limited support for unsigned preds in isImpliedViaOperations

The logic there only considers `SLT/SGT` predicates. We can use the same logic
for proving `ULT/UGT` predicates if all involved values are non-negative.

Adding full-scale support for unsigned might be challenging because of code amount,
so we can consider this in the future.

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

show more ...

[SCEV] Prove implicaitons via AddRec start

If we know that some predicate is true for AddRec and an invariant
(w.r.t. this AddRec's loop), this fact is, in particular, true on the first
iteration. W

[SCEV] Prove implicaitons via AddRec start

If we know that some predicate is true for AddRec and an invariant
(w.r.t. this AddRec's loop), this fact is, in particular, true on the first
iteration. We can try to prove the facts we need using the start value.

The motivating example is proving things like
```
isImpliedCondOperands(>=, X, 0, {X,+,-1}, 0}
```

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

show more ...

[SCEV] Use loop guard info when computing the max BE taken count in howFarToZero.

For some expressions, we can use information from loop guards when
we are looking for a maximum. This patch applies

[SCEV] Use loop guard info when computing the max BE taken count in howFarToZero.

For some expressions, we can use information from loop guards when
we are looking for a maximum. This patch applies information from
loop guards to the expression used to compute the maximum backedge
taken count in howFarToZero. It currently replaces an unknown
expression X with UMin(X, Y), if the loop is guarded by
X ult Y.

This patch is minimal in what conditions it applies, and there
are a few TODOs to generalize.

This partly addresses PR40961. We will also need an update to
LV to address it completely.

Reviewed By: reames

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

show more ...

[SCEV] Support unsigned predicates in isKnownPredicateViaNoOverflow

SCEV should be able to prove facts like `x <u x+1<nuw>`.

Differential Revision: https://reviews.llvm.org/D88015
Reviewed By: lebe

[SCEV] Support unsigned predicates in isKnownPredicateViaNoOverflow

SCEV should be able to prove facts like `x <u x+1<nuw>`.

Differential Revision: https://reviews.llvm.org/D88015
Reviewed By: lebedev.ri

show more ...

[SCEV] Generalize SCEVParameterRewriter to accept SCEV expression as target.

This patch extends SCEVParameterRewriter to support rewriting unknown
epxressions to arbitrary SCEV expressions. It will

[SCEV] Generalize SCEVParameterRewriter to accept SCEV expression as target.

This patch extends SCEVParameterRewriter to support rewriting unknown
epxressions to arbitrary SCEV expressions. It will be used by further
patches.

Reviewed By: reames

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

show more ...

[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).

SCEVExpander modifies the underlying function so it is more suitable in
Transforms/Utils, rather than Analysis. This allows using o

[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).

SCEVExpander modifies the underlying function so it is more suitable in
Transforms/Utils, rather than Analysis. This allows using other
transform utils in SCEVExpander.

This patch was originally committed as b8a3c34eee06, but broke the
modules build, as LoopAccessAnalysis was using the Expander.

The code-gen part of LAA was moved to lib/Transforms recently, so this
patch can be landed again.

Reviewers: sanjoy.google, efriedma, reames

Reviewed By: sanjoy.google

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

show more ...

[SVEV] Recognise hardware-loop intrinsic loop.decrement.reg

Teach SCEV about the @loop.decrement.reg intrinsic, which has exactly the same
semantics as a sub expression. This allows us to query hard

[SVEV] Recognise hardware-loop intrinsic loop.decrement.reg

Teach SCEV about the @loop.decrement.reg intrinsic, which has exactly the same
semantics as a sub expression. This allows us to query hardware-loops, which
contain this @loop.decrement.reg intrinsic, so that we can calculate iteration
counts, exit values, etc. of hardwareloops.

This "int_loop_decrement_reg" intrinsic is defined as "IntrNoDuplicate". Thus,
while hardware-loops and tripcounts now become analysable by SCEV, this
prevents the usual loop transformations from applying transformations on
hardware-loops, which is what we want at this point, for which I have added
test cases for loopunrolling and IndVarSimplify and LFTR.

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

show more ...

Revert "[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC)."

This reverts commit 51ef53f3bd23559203fe9af82ff2facbfedc1db3, as it
breaks some bots.

[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).

SCEVExpander modifies the underlying function so it is more suitable in
Transforms/Utils, rather than Analysis. This allows using o

[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).

SCEVExpander modifies the underlying function so it is more suitable in
Transforms/Utils, rather than Analysis. This allows using other
transform utils in SCEVExpander.

Reviewers: sanjoy.google, efriedma, reames

Reviewed By: sanjoy.google

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

show more ...

[SCEV] Disable canonical expansion for non-affine addrecs.

Reviewed By: apilipenko

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

Patch by Evgeniy Brevnov ([email protected])

llvm-svn: 37

[SCEV] Disable canonical expansion for non-affine addrecs.

Reviewed By: apilipenko

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

Patch by Evgeniy Brevnov ([email protected])

llvm-svn: 372789

show more ...

[SCEV] Return zero from computeConstantDifference(X, X)

Without this patch computeConstantDifference returns None for cases like
these:

computeConstantDifference(%x, %x)
computeConstantDifferen

[SCEV] Return zero from computeConstantDifference(X, X)

Without this patch computeConstantDifference returns None for cases like
these:

computeConstantDifference(%x, %x)
computeConstantDifference({%x,+,16}, {%x,+,16})

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

llvm-svn: 368193

show more ...

[SCEV] Fix for PR42397. SCEVExpander wrongly adds nsw to shl instruction.

Change-Id: I76c9f628c092ae3e6e78ebdaf55cec726e25d692
llvm-svn: 365363

Add ScalarEvolutionsTest::SCEVExpandInsertCanonicalIV tests

Test insertion of canonical IV in canonical expansion mode.

llvm-svn: 362432