Revert 1c021c64c "[SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown"

> While we indeed can't treat them as no-ops, i believe we can/should
> do better tha

Revert 1c021c64c "[SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown"

> While we indeed can't treat them as no-ops, i believe we can/should
> do better than just modelling them as `unknown`. `inttoptr` story
> is complicated, but for `ptrtoint`, it seems straight-forward
> to model it just as a zext-or-trunc of unknown.
>
> This may be important now that we track towards
> making inttoptr/ptrtoint casts not no-op,
> and towards preventing folding them into loads/etc
> (see D88979/D88789/D88788)
>
> Reviewed By: mkazantsev
>
> Differential Revision: https://reviews.llvm.org/D88806

It caused the following assert during Chromium builds:

llvm/lib/IR/Constants.cpp:1868:
static llvm::Constant *llvm::ConstantExpr::getTrunc(llvm::Constant *, llvm::Type *, bool):
Assertion `C->getType()->isIntOrIntVectorTy() && "Trunc operand must be integer"' failed.

See code review for a link to a reproducer.

This reverts commit 1c021c64caef83cccb719c9bf0a2554faa6563af.

show more ...

[NFC] Remove redundant isFullSet checks

Full set case is handled inside intersection, no need to
litter the code with duplicating them outside.

[SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown

While we indeed can't treat them as no-ops, i believe we can/should
do better than just modelling them a

[SCEV] Model ptrtoint(SCEVUnknown) cast not as unknown, but as zext/trunc/self of SCEVUnknown

While we indeed can't treat them as no-ops, i believe we can/should
do better than just modelling them as `unknown`. `inttoptr` story
is complicated, but for `ptrtoint`, it seems straight-forward
to model it just as a zext-or-trunc of unknown.

This may be important now that we track towards
making inttoptr/ptrtoint casts not no-op,
and towards preventing folding them into loads/etc
(see D88979/D88789/D88788)

Reviewed By: mkazantsev

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

show more ...

[SCEV] Handle ULE in applyLoopGuards.

Handle ULE predicate in similar fashion to ULT predicate in
applyLoopGuards.

[SCEV] Do not apply info from loop guards in AddRecs.

We cannot guarantee that the replacement expression is loop-invariant in
all AddRecs in the source expression. Use a rewriter that skips
AddRecE

[SCEV] Do not apply info from loop guards in AddRecs.

We cannot guarantee that the replacement expression is loop-invariant in
all AddRecs in the source expression. Use a rewriter that skips
AddRecExpr for now.

Fixes PR47776.

show more ...

[Analysis] ScalarEvolution::getUMinFromMismatchedTypes - assert we've found the max type. NFCI.

Found by clang static analyzer.

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][NFC] Introduce isKnownPredicateAt method

We can query known predicates in different points, respecting
their dominating conditions.

[SCEV] Verify that all mapped SCEV AddRecs refer to valid loops.

This check helps to guard against cases where expressions referring to
invalidated/deleted loops are not properly invalidated.

The a

[SCEV] Verify that all mapped SCEV AddRecs refer to valid loops.

This check helps to guard against cases where expressions referring to
invalidated/deleted loops are not properly invalidated.

The additional check is motivated by the reproducer shared for 8fdac7cb7abb
and I think in general make sense as a sanity check.

Reviewed By: reames

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

show more ...

[SCEV][NFC] Introduce isBasicBlockEntryGuardedByCond

Currently, we have `isLoopEntryGuardedByCond` method in SCEV, which
checks that some fact is true if we enter the loop. In fact, this is just a
p

[SCEV][NFC] Introduce isBasicBlockEntryGuardedByCond

Currently, we have `isLoopEntryGuardedByCond` method in SCEV, which
checks that some fact is true if we enter the loop. In fact, this is just a
particular case of more general concept `isBasicBlockEntryGuardedByCond`
applied to given loop's header. In fact, the logic if this code is largely
independent on the given loop and only cares code above it.

This patch makes this generalization. Now we can query it for any block,
and `isBasicBlockEntryGuardedByCond` is just a particular case.

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

show more ...

[SCEV] Also use info from assumes in applyLoopGuards.

Similar to collecting information from branches guarding a loop, we can
also collect information from assumes dominating the loop header.

Fixes

[SCEV] Also use info from assumes in applyLoopGuards.

Similar to collecting information from branches guarding a loop, we can
also collect information from assumes dominating the loop header.

Fixes PR47247.

Reviewed By: jdoerfert

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

show more ...

[SCEV] Add support for `x != 0` to CollectCondition.

Add support for NE predicates with 0 constants. Those can be translated
to UMaxExpr(x, 1).

[SCEV] Add support for `x == constant` to CollectCondition.

Add support for EQ predicates with constant operand. In that case, using
the constant instead of an unknown expression should always be
be

[SCEV] Add support for `x == constant` to CollectCondition.

Add support for EQ predicates with constant operand. In that case, using
the constant instead of an unknown expression should always be
beneficial.

show more ...

[SCEV] Swap operands if LHS is not unknown.

Currently we only use information from guards for unknown expressions.
Swap LHS/RHS and predicate, if LHS is not unknown.

[SCEV] Extract code to collect conditions to lambda (NFC).

This makes re-using the common functionality easier in follow-up
patches.

[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] Handle `less` predicates for FoundPred = NE

Currently these predicates are ignored, yet their handling is
pretty simple. I could not find a single test where it would
actually change somethin

[SCEV] Handle `less` predicates for FoundPred = NE

Currently these predicates are ignored, yet their handling is
pretty simple. I could not find a single test where it would
actually change something, but it's only because isImpliedCondOperands
is not smart enough to prove it further on. Yet the situation when
we come there with `less` predicate is pretty common.

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

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

Revert D71539 "Recommit "[SCEV] Look through single value PHIs.""

This reverts commit 11dccf8d3aa5d55210f8b886fb21926c7a8353ca.

A bootstrapped clang crashes (due to ArrayRef::front called on an emp

Revert D71539 "Recommit "[SCEV] Look through single value PHIs.""

This reverts commit 11dccf8d3aa5d55210f8b886fb21926c7a8353ca.

A bootstrapped clang crashes (due to ArrayRef::front called on an empty
ArrayRef) when compiling some files. Very strangely, this only reproduces with
modules.

```
13 0x0000564d3349e968 llvm::ArrayRef<llvm::BasicBlock*>::front() const /proc/self/cwd/llvm/include/llvm/ADT/ArrayRef.h:160:7
14 0x0000564d3349e896 llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getHeader() const /proc/self/cwd/llvm/include/llvm/Analysis/LoopInfo.h:104:50
15 0x0000564d3349fd9d llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatch() const /proc/self/cwd/llvm/include/llvm/Analysis/LoopInfoImpl.h:210:11
16 0x0000564d33593c8a llvm::ScalarEvolution::computeBackedgeTakenCount(llvm::Loop const*, bool) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:6933:15
17 0x0000564d33592ebc llvm::ScalarEvolution::getBackedgeTakenInfo(llvm::Loop const*) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:0:30
18 0x0000564d33593a54 llvm::ScalarEvolution::getBackedgeTakenCount(llvm::Loop const*, llvm::ScalarEvolution::ExitCountKind) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:6487:36
19 0x0000564d32be2402 llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount(llvm::Loop const*) /proc/self/cwd/llvm/include/llvm/Analysis/ScalarEvolution.h:768:5
20 0x0000564d33590807 llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:5495:19
21 0x0000564d320abab7 llvm::ScalarEvolution::getSignedRange(llvm::SCEV const*) /proc/self/cwd/llvm/include/llvm/Analysis/ScalarEvolution.h:840:12
22 0x0000564d335a03aa llvm::ScalarEvolution::isKnownPredicateViaConstantRanges(llvm::CmpInst::Predicate, llvm::SCEV const*, llvm::SCEV const*) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:9239:60
23 0x0000564d33586a80 llvm::ScalarEvolution::isKnownViaNonRecursiveReasoning(llvm::CmpInst::Predicate, llvm::SCEV const*, llvm::SCEV const*) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:10284:60
```

show more ...

[NFC][SCEV] Cleanup lowering of @llvm.uadd.sat, (-1 - V) is just ~V

[SCEV] Recognize @llvm.uadd.sat as `%y + umin(%x, (-1 - %y))`

----------------------------------------
define i32 @src(i32 %x, i32 %y) {
%0:
%r = uadd_sat i32 %x, %y
ret i32 %r
}
=>
define i32 @

[SCEV] Recognize @llvm.uadd.sat as `%y + umin(%x, (-1 - %y))`

----------------------------------------
define i32 @src(i32 %x, i32 %y) {
%0:
%r = uadd_sat i32 %x, %y
ret i32 %r
}
=>
define i32 @tgt(i32 %x, i32 %y) {
%0:
%t0 = sub nsw nuw i32 4294967295, %y
%t1 = umin i32 %x, %t0
%r = add nuw i32 %t1, %y
ret i32 %r
}
Transformation seems to be correct!

The alternative, naive, lowering could be the following,
although i don't think it's better,
thought it will likely be needed for sadd/ssub/*shl:

----------------------------------------
define i32 @src(i32 %x, i32 %y) {
%0:
%r = uadd_sat i32 %x, %y
ret i32 %r
}
=>
define i32 @tgt(i32 %x, i32 %y) {
%0:
%t0 = zext i32 %x to i33
%t1 = zext i32 %y to i33
%t2 = add nuw i33 %t0, %t1
%t3 = zext i32 4294967295 to i33
%t4 = umin i33 %t2, %t3
%r = trunc i33 %t4 to i32
ret i32 %r
}
Transformation seems to be correct!

show more ...

[SCEV] Recognize @llvm.usub.sat as `%x - (umin %x, %y)`

----------------------------------------
define i32 @src(i32 %x, i32 %y) {
%0:
%r = usub_sat i32 %x, %y
ret i32 %r
}
=>
define i32 @tgt(i3

[SCEV] Recognize @llvm.usub.sat as `%x - (umin %x, %y)`

----------------------------------------
define i32 @src(i32 %x, i32 %y) {
%0:
%r = usub_sat i32 %x, %y
ret i32 %r
}
=>
define i32 @tgt(i32 %x, i32 %y) {
%0:
%t0 = umin i32 %x, %y
%r = sub nuw i32 %x, %t0
ret i32 %r
}
Transformation seems to be correct!

show more ...