[SCEV] `createNodeForSelectOrPHIInstWithICmpInstCond()`: generalize eq handling

The current logic was: https://alive2.llvm.org/ce/z/j8muXk
but in reality the offset to the Y in the 'true' hand
does

[SCEV] `createNodeForSelectOrPHIInstWithICmpInstCond()`: generalize eq handling

The current logic was: https://alive2.llvm.org/ce/z/j8muXk
but in reality the offset to the Y in the 'true' hand
does not need to exist: https://alive2.llvm.org/ce/z/MNQ7DZ
https://alive2.llvm.org/ce/z/S2pMQD

To catch that, instead of computing the Y's in both
hands and checking their equality, compute Y and C,
and check that C is 0 or 1.

show more ...

[NFC][SCEV] `createNodeForSelectOrPHIInstWithICmpInstCond()`: dedup eq/ne pred handling

[PSE] Allow duplicate predicates in debug output

This lets us avoid redundant implication work in the constructor of SCEVUnionPredicate which simplifies an upcoming change. If we're actually buildi

[PSE] Allow duplicate predicates in debug output

This lets us avoid redundant implication work in the constructor of SCEVUnionPredicate which simplifies an upcoming change. If we're actually building a predicate via PSE, that goes through addPredicate which does include the implication check.

show more ...

[PSE] Remove assumption that top level predicate is union from public interface [NFC*]

Note that this doesn't actually cause the top level predicate to become a non-union just yet.

The * above come

[PSE] Remove assumption that top level predicate is union from public interface [NFC*]

Note that this doesn't actually cause the top level predicate to become a non-union just yet.

The * above comes from a case in the LoopVectorizer where a predicate which is later proven no longer blocks vectorization due to a change from checking if predicates exists to whether the predicate is possibly false.

show more ...

[SCEVPredicateRewriter] Remove assumption top level predicate is a union [NFC]

[NFC][SCEV] `createNodeForSelectOrPHIViaUMinSeq()`: use sub instead of add

For booleans, xor/add/sub are interchangeable:
https://alive2.llvm.org/ce/z/ziav3d

But for larger bitwidths, we'll need su

[NFC][SCEV] `createNodeForSelectOrPHIViaUMinSeq()`: use sub instead of add

For booleans, xor/add/sub are interchangeable:
https://alive2.llvm.org/ce/z/ziav3d

But for larger bitwidths, we'll need sub, so change it now.

show more ...

[SCEV] Constify some uses of SCEVUnionPredicate* [NFC]

This exploits the immutability introduced in d334fec.

[NFC][SCEV] `createNodeForSelectOrPHIViaUMinSeq()`: refactor `i1 cond ? i1 x : i1 y` handling

While that effectively concludes i1 select handling,
that boolean restriction can be lifted later.

[NFC][SCEV] `createNodeForSelectOrPHIViaUMinSeq()`: refactor `i1 cond ? i1 C : i1 y` pattern

https://alive2.llvm.org/ce/z/uRvVtN

[NFC][SCEV] `createNodeForSelectOrPHIViaUMinSeq()`: refactor `i1 cond ? i1 x : i1 C` pattern

https://alive2.llvm.org/ce/z/2Q7Du_

[SCEV] Recognize `cond ? i1 0 : i1 y` as `umin_seq ~cond, x`

By definition, `umin_seq` has the exact same
poison stopping properties the original `select` had:
https://alive2.llvm.org/ce/z/N6XwV-

[SCEV] Recognize `cond ? i1 x : i1 1` as `~umin_seq cond, ~x`

By definition, `umin_seq` has the exact same
poison stopping properties the original `select` had:
https://alive2.llvm.org/ce/z/aqe9GK

[SCEV] Recognize logical `or` as `not umin_seq (not, not)`

By definition, `umin_seq` has the exact same
poison stopping properties the original `select` had:
https://alive2.llvm.org/ce/z/MUfbTL

[SCEV] Recognize logical `and` as `umin_seq`

By definition, `umin_seq` has the exact same
poison stopping properties the original `select` had:
https://alive2.llvm.org/ce/z/59KuZZ

[SCEV] `createNodeForSelectOrPHI()`: try constant-folding even if not an Instruction

We'd catch the tautological select pattern later anyways
due to constant folding, so that leaves PHI-like select,

[SCEV] `createNodeForSelectOrPHI()`: try constant-folding even if not an Instruction

We'd catch the tautological select pattern later anyways
due to constant folding, so that leaves PHI-like select,
but it does not appear to fire there.

show more ...

[NFC][SCEV] Prepare `createNodeForSelectOrPHI()` for gaining additional strategy

Currently `createNodeForSelectOrPHI()` takes an Instruction,
and only works on the Cond that is an ICmpInst,
but that

[NFC][SCEV] Prepare `createNodeForSelectOrPHI()` for gaining additional strategy

Currently `createNodeForSelectOrPHI()` takes an Instruction,
and only works on the Cond that is an ICmpInst,
but that can be relaxed somewhat.

For now, simply rename the existing function,
and add a thin wrapper ontop that still does
the same thing as it used to.

show more ...

[SCEV] Recognize binary `xor` as bit-wise `add`

https://alive2.llvm.org/ce/z/ULuZxB

We could transparently handle wider bitwidths,
by effectively casting iN to <N x i1> and performing the `add`
bit

[SCEV] Recognize binary `xor` as bit-wise `add`

https://alive2.llvm.org/ce/z/ULuZxB

We could transparently handle wider bitwidths,
by effectively casting iN to <N x i1> and performing the `add`
bit/element -wise, the expression will be rather large,
so let's not do that for now.

show more ...

[SCEV] Recognize binary `and` as bit-wise `umin`

https://alive2.llvm.org/ce/z/aKAr94

We could transparently handle wider bitwidths,
by effectively casting iN to <N x i1> and performing the `umin`
b

[SCEV] Recognize binary `and` as bit-wise `umin`

https://alive2.llvm.org/ce/z/aKAr94

We could transparently handle wider bitwidths,
by effectively casting iN to <N x i1> and performing the `umin`
bit/element -wise, the expression will be rather large,
so let's not do that for now.

show more ...

[SCEV] Recognize binary `or` as bit-wise `umax`

https://alive2.llvm.org/ce/z/SMEaoc

We could transparently handle wider bitwidths,
by effectively casting iN to <N x i1> and performing the `umax`
bi

[SCEV] Recognize binary `or` as bit-wise `umax`

https://alive2.llvm.org/ce/z/SMEaoc

We could transparently handle wider bitwidths,
by effectively casting iN to <N x i1> and performing the `umax`
bit/element -wise, the expression will be rather large,
so let's not do that for now.

show more ...

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

[SCEV] Remove a direct call to SCEVUnionPredicate::add [NFC]

[SCEV] Unwind SCEVUnionPredicate from getPredicatedBackedgeTakenCount [NFC]

For those curious, the whole reason for tracking the predicate set seperately as opposed to just immediately registering t

[SCEV] Unwind SCEVUnionPredicate from getPredicatedBackedgeTakenCount [NFC]

For those curious, the whole reason for tracking the predicate set seperately as opposed to just immediately registering the dependencies appears to be allowing the printing code to print a result without changing the PSE state. It's slightly questionable if this justifies the complexity, but since we can preserve it with local ugliness, I did so.

show more ...

[SCEV] Remove conversion to SCEVUnionPredicate in ExitNotTakenInfo [NFC]

This removes one of the places where we mutate an existing union predicate.

[SCEV] Add interface for constructing generic SCEVComparePredicate [NFC}

[SCEV] Generalize SCEVEqualsPredicate to any compare [NFC]

PredicatedScalarEvolution has a predicate type for representing A == B. This change generalizes it into something which can represent a A

[SCEV] Generalize SCEVEqualsPredicate to any compare [NFC]

PredicatedScalarEvolution has a predicate type for representing A == B. This change generalizes it into something which can represent a A <pred> B.

This generality is currently unused, but is motivated by a couple of recent cases which have come up. In particular, I'm currently playing around with using this to simplify the runtime checking code in LoopVectorizer. Regardless of the outcome of that prototyping, generalizing the compare node seemed useful.

show more ...