[SCEV] Check correct value for UB (#124302)

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

[SCEV] Check correct value for UB (#124302)

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.

show more ...

[IR] Replace of PointerType::getUnqual(Type) with opaque version (NFC) (#123909)

Follow up to https://github.com/llvm/llvm-project/issues/123569

[SCEV] Do not attempt to collect loop guards for loops without predecessor. (#123662)

Attempting to collect loop guards for loops without a predecessor can
lead to non-terminating recursion trying

[SCEV] Do not attempt to collect loop guards for loops without predecessor. (#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.

show more ...

SCEV: migrate to CmpPredicate (NFC) (#122907)

In preparation to teach implied-cond functions about samesign, migrate
integer-compare predicates that flow through to the functions from
CmpInst::Pre

SCEV: migrate to CmpPredicate (NFC) (#122907)

In preparation to teach implied-cond functions about samesign, migrate
integer-compare predicates that flow through to the functions from
CmpInst::Predicate to CmpPredicate.

show more ...

[LLVM] Fix various cl::desc typos and whitespace issues (NFC) (#121955)

[SCEV] Make sure starting block is marked as visited when recursively collecting loop guards. (#120749)

When `collectFromBlock` is called without a predecessor (in particular
for loops that don't h

[SCEV] Make sure starting block is marked as visited when recursively 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.

show more ...

[SCEV] Remove existing predicates implied by newly added ones. (#118185)

When adding a new predicate to a union predicate, some of the existing
predicates may be implied by the new predicate. Remov

[SCEV] Remove existing predicates implied by newly added ones. (#118185)

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

show more ...

[SCEV] Fix exit condition for recursive loop guard collection (#120442)

When assumptions are present `Terms.size()` does not actually count the
number of conditions collected from dominating branch

[SCEV] Fix exit condition for recursive loop guard collection (#120442)

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

show more ...

[SCEV] Bail out on mixed int/pointer in SCEVWrapPredicate::implies.

Fixes a crash when trying to extend the pointer start value to a narrow
integer type after b6c29fdffd65.

[SCEV] Add initial matchers for SCEV expressions. (NFC) (#119390)

This patch adds initial matchers for unary and binary SCEV expressions
and specializes it for SExt, ZExt and binary add expression

[SCEV] Add initial matchers for SCEV expressions. (NFC) (#119390)

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

show more ...

[SCEV] Use Step and Start to check if SCEVWrapPredicate is implied. (#118184)

A SCEVWrapPredicate A implies B, if
* they have the same flag,
* both steps are positive and
* B's start and step

[SCEV] Use Step and Start to check if SCEVWrapPredicate is implied. (#118184)

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

show more ...

[SCEV] Add initial pattern matching for SCEV constants. (NFC) (#119389)

Add initial pattern matching for SCEV constants. Follow-up patches will
add additional matchers for various SCEV expressions.

[SCEV] Add initial pattern matching for SCEV constants. (NFC) (#119389)

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

show more ...

[SCEV] Simplify SCEVExpr for PHI to SCEV for operand if operands are identical (#115945)

Helps SCEV analyze some special phi nodes, allowing the computation of
loop trip count in cases like the fol

[SCEV] Simplify SCEVExpr for PHI to SCEV for operand if operands are 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

show more ...

[SCEV] Do not allow refinement in the rewriting of BEValue (#117152)

See the following case:
```
; bin/opt -passes="print<scalar-evolution>" test.ll --disable-output
define i32 @widget() {
b:

[SCEV] Do not allow refinement in the rewriting of BEValue (#117152)

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.

show more ...

[SCEV] Fix sext handling for `getConstantMultiple` (#117093)

Counterexample: 219 is a multiple of 73. But `sext i8 219 to i16 =
65499` is not.
Fixes https://github.com/llvm/llvm-project/issues/116

[SCEV] Fix sext handling for `getConstantMultiple` (#117093)

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.

show more ...

IR: de-duplicate two CmpInst routines (NFC) (#116866)

De-duplicate the functions getSignedPredicate and getUnsignedPredicate,
nearly identical versions of which were present in CmpInst and ICmpInst

IR: de-duplicate two CmpInst routines (NFC) (#116866)

De-duplicate the functions getSignedPredicate and getUnsignedPredicate,
nearly identical versions of which were present in CmpInst and ICmpInst,
creating less confusion.

show more ...

[SCEV] Address post-commit comments for #113915.

Address post-commit comments for
https://github.com/llvm/llvm-project/pull/113915.

[SCEV] Collect and merge loop guards through PHI nodes with multiple incoming values (#113915)

This patch aims to strengthen collection of loop guards by processing
PHI nodes with multiple incoming

[SCEV] Collect and merge loop guards through PHI nodes with multiple 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

show more ...

[SCEV] Disallow simplifying phi(undef, X) to X (#115109)

See the following case:
```
@GlobIntONE = global i32 0, align 4

define ptr @src() {
entry:
br label %for.body.peel.begin

for.body

[SCEV] Disallow simplifying phi(undef, X) to X (#115109)

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.

show more ...

[SCEV] Avoid repeated hash lookups (NFC) (#112656)

[APInt] Fix APInt constructions where value does not fit bitwidth (NFCI) (#80309)

This fixes all the places that hit the new assertion added in
https://github.com/llvm/llvm-project/pull/106524 in t

[APInt] Fix APInt constructions where value does not fit bitwidth (NFCI) (#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.

show more ...

[LLVM] Add `Intrinsic::getDeclarationIfExists` (#112428)

Add `Intrinsic::getDeclarationIfExists` to lookup an existing
declaration of an intrinsic in a `Module`.

[SCEV] Retain SCEVSequentialMinMaxExpr if an operand may trigger UB. (#110824)

Retain SCEVSequentialMinMaxExpr if an operand may trigger UB, e.g. if
there is an UDiv operand that may divide by 0 or

[SCEV] Retain SCEVSequentialMinMaxExpr if an operand may trigger UB. (#110824)

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

show more ...

[LoopVectorize] Use predicated version of getSmallConstantMaxTripCount (#109928)

There are a number of places where we call getSmallConstantMaxTripCount
without passing a vector of predicates:

g

[LoopVectorize] Use predicated version of getSmallConstantMaxTripCount (#109928)

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.

show more ...

[Analysis] Simplify code with DenseMap::operator[] (NFC) (#111331)