[LSR] Create SCEVExpander earlier, use member isSafeToExpand() (NFC)

This is a followup to D129630, which switches LSR to the member
isSafeToExpand() variant, and removes the freestanding function.

[LSR] Create SCEVExpander earlier, use member isSafeToExpand() (NFC)

This is a followup to D129630, which switches LSR to the member
isSafeToExpand() variant, and removes the freestanding function.

This is done by creating the SCEVExpander early (already during the
analysis phase). Because the SCEVExpander is now available for the
whole lifetime of LSRInstance, I've also made it into a member
variable, rather than passing it around in even more places.

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

show more ...

[SCEVExpander] Allow udiv with isKnownNonZero(RHS) + add vscale case

Motivation here is to unblock LSRs ability to use ICmpZero uses - the major effect of which is to enable count down IVs. The test

[SCEVExpander] Allow udiv with isKnownNonZero(RHS) + add vscale case

Motivation here is to unblock LSRs ability to use ICmpZero uses - the major effect of which is to enable count down IVs. The test changes reflect this goal, but the potential impact is much broader since this isn't a change in LSR at all.

SCEVExpander needs(*) to prove that expanding the expression is safe anywhere the SCEV expression is valid. In general, we can't expand any node which might fault (or exhibit UB) unless we can either a) prove it won't fault, or b) guard the faulting case. We'd been allowing non-zero constants here; this change extends it to non-zero values.

vscale is never zero. This is already implemented in ValueTracking, and this change just adds the same logic in SCEV's range computation (which in turn drives isKnownNonZero). We should common up some logic here, but let's do that in separate changes.

(*) As an aside, "needs" is such an interesting word here. First, we don't actually need to guard this at all; we could choose to emit a select for the RHS of ever udiv and remove this code entirely. Secondly, the property being checked here is way too strong. What the client actually needs is to expand the SCEV at some particular point in some particular loop. In the examples, the original urem dominates that loop and yet we completely ignore that information when analyzing legality. I don't plan to actively pursue either direction, just noting it for future reference.

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

show more ...

[LoopPredication] Use isSafeToExpandAt() member function (NFC)

As a followup to D129630, this switches a usage of the freestanding
function in LoopPredication to use the member variant instead. This

[LoopPredication] Use isSafeToExpandAt() member function (NFC)

As a followup to D129630, this switches a usage of the freestanding
function in LoopPredication to use the member variant instead. This
was the last use of the freestanding function, so drop it entirely.

show more ...

[SCEVExpander] Make CanonicalMode handing in isSafeToExpand() more robust (PR50506)

isSafeToExpand() for addrecs depends on whether the SCEVExpander
will be used in CanonicalMode. At least one calle

[SCEVExpander] Make CanonicalMode handing in isSafeToExpand() more robust (PR50506)

isSafeToExpand() for addrecs depends on whether the SCEVExpander
will be used in CanonicalMode. At least one caller currently gets
this wrong, resulting in PR50506.

Fix this by a) making the CanonicalMode argument on the freestanding
functions required and b) adding member functions on SCEVExpander
that automatically take the SCEVExpander mode into account. We can
use the latter variant nearly everywhere, and thus make sure that
there is no chance of CanonicalMode mismatch.

Fixes https://github.com/llvm/llvm-project/issues/50506.

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

show more ...

[SCEVExpander] Avoid ConstantExpr::get() (NFCI)

Use ConstantFoldBinaryOpOperands() instead. This will be important
when not all binops have constant expression variants.

[IRBuilder] Migrate all binops to folding API

Migrate all binops to use FoldXYZ rather than CreateXYZ APIs,
which are compatible with InstSimplifyFolder and fallible constant
folding.

Rather than c

[IRBuilder] Migrate all binops to folding API

Migrate all binops to use FoldXYZ rather than CreateXYZ APIs,
which are compatible with InstSimplifyFolder and fallible constant
folding.

Rather than continuing to add one method for every single operator,
add a generic FoldBinOp (plus variants for nowrap, exact and fmf
operators), which we would need anyway for CreateBinaryOp.

This change is not NFC because IRBuilder with InstSimplifyFolder
may perform more folding. However, this patch changes SCEVExpander
to not use the folder in InsertBinOp to minimize practical impact
and keep this change as close to NFC as possible.

show more ...

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with
the cleanup of InstructionSimplify in one commit.

This is the alternative to the less invasive clang-format only patch: D126783

Reviewed By: spatel, rengolin

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

show more ...

[NFC] Remove commented cerr debugging loggings

There are some unused cerr debugging loggings in the codes. It is weird
to remain such commented debug helpers in the product.

[SCEVExpander] Expand umin_seq using freeze

%x umin_seq %y is currently expanded to %x == 0 ? 0 : umin(%x, %y).
This patch changes the expansion to umin(%x, freeze %y) instead
(https://alive2.llvm.o

[SCEVExpander] Expand umin_seq using freeze

%x umin_seq %y is currently expanded to %x == 0 ? 0 : umin(%x, %y).
This patch changes the expansion to umin(%x, freeze %y) instead
(https://alive2.llvm.org/ce/z/wujUhp).

The motivation for this change are the test cases affected by
D124910, where the freeze expansion ultimately produces better
optimization results. This is largely because
`(%x umin_seq %y) == %x` is a common expansion pattern, which
reliably optimizes in freeze representation, but only sometimes
with the zero comparison (in particular, if %x == 0 can fold to
something else, we generally won't be able to cover reasonable
code from this.)

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

show more ...

[SCEVExpander] Deduplicate min/max expansion code (NFC)

[SCEVExpander] Remove handling for mixed int/pointer min/max (NFCI)

Mixed int/pointer min/max are no longer possible.

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120741

show more ...

[SCEVExpander] Use early returns in FindValueInExprValueMap() (NFC)

[SCEV] Return ArrayRef from getSCEVValues() (NFC)

Return a read-only view on this set. For the one internal use,
directly access ExprValueMap.

[SCEV] Don't try to reuse expressions with offset

SCEVs ExprValueMap currently tracks not only which IR Values
correspond to a given SCEV expression, but additionally stores that
it may be expanded

[SCEV] Don't try to reuse expressions with offset

SCEVs ExprValueMap currently tracks not only which IR Values
correspond to a given SCEV expression, but additionally stores that
it may be expanded in the form X+Offset. In theory, this allows
reusing existing IR Values in more cases.

In practice, this doesn't seem to be particularly useful (the test
changes are rather underwhelming) and adds a good bit of complexity.
Per https://github.com/llvm/llvm-project/issues/53905, we have an
invalidation issue with these offseted expressions.

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

show more ...

[SCEVExpander][OpaquePtr] Check GEP source type when finding identical GEP

Fixes an opaque pointers miscompile.

Reviewed By: #opaque-pointers, nikic

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

[SCEVExpander][OpaquePtr] Check GEP source type when finding identical GEP

Fixes an opaque pointers miscompile.

Reviewed By: #opaque-pointers, nikic

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

show more ...

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

[Transforms] Use default member initialization in SCEVFindUnsafe (NFC)

[SCEVExpander] Always use i8 GEP for reused value offset

We could keep the non-i8 GEP code for non-opaque pointers, but
there's two reasons I'm dropping it: First, this actually appears
to be dead c

[SCEVExpander] Always use i8 GEP for reused value offset

We could keep the non-i8 GEP code for non-opaque pointers, but
there's two reasons I'm dropping it: First, this actually appears
to be dead code, at least it isn't hit in any of our tests. I
expect that this is because we usually expand trip counts, and
those are never pointers (anymore). Second, the non-i8 GEP was
actually incorrect in multiple ways, because it used SCEV type
sizes, which don't match DL type sizes (for pointers) and certainly
don't match type alloc sizes (which is what GEPs actually use).
As such, I'm simplifying the code to always use the i8 GEP code
path if it does get hit.

show more ...

[SCEVExpander] Remove pointer element type access in assertion

Assert directly on i8 rather than the element type of i8*.

[NFC] Remove uses of PointerType::getElementType()

Instead use either Type::getPointerElementType() or
Type::getNonOpaquePointerElementType().

This is part of D117885, in preparation for deprecatin

[NFC] Remove uses of PointerType::getElementType()

Instead use either Type::getPointerElementType() or
Type::getNonOpaquePointerElementType().

This is part of D117885, in preparation for deprecating the API.

show more ...

[SCEVExpander] Use IntToPtr for temporary instruction.

Use PtrToInt instead Add when creating temporary instructions. The add
might get folded away with more sophisticated folding.

[SCEV] Sequential/in-order `UMin` expression

As discussed in https://github.com/llvm/llvm-project/issues/53020 / https://reviews.llvm.org/D116692,
SCEV is forbidden from reasoning about 'backedge ta

[SCEV] Sequential/in-order `UMin` expression

As discussed in https://github.com/llvm/llvm-project/issues/53020 / https://reviews.llvm.org/D116692,
SCEV is forbidden from reasoning about 'backedge taken count'
if the branch condition is a poison-safe logical operation,
which is conservatively correct, but is severely limiting.

Instead, we should have a way to express those
poison blocking properties in SCEV expressions.

The proposed semantics is:
```
Sequential/in-order min/max SCEV expressions are non-commutative variants
of commutative min/max SCEV expressions. If none of their operands
are poison, then they are functionally equivalent, otherwise,
if the operand that represents the saturation point* of given expression,
comes before the first poison operand, then the whole expression is not poison,
but is said saturation point.
```
* saturation point - the maximal/minimal possible integer value for the given type

The lowering is straight-forward:
```
compare each operand to the saturation point,
perform sequential in-order logical-or (poison-safe!) ordered reduction
over those checks, and if reduction returned true then return
saturation point else return the naive min/max reduction over the operands
```
https://alive2.llvm.org/ce/z/Q7jxvH (2 ops)
https://alive2.llvm.org/ce/z/QCRrhk (3 ops)
Note that we don't need to check the last operand: https://alive2.llvm.org/ce/z/abvHQS
Note that this is not commutative: https://alive2.llvm.org/ce/z/FK9e97

That allows us to handle the patterns in question.

Reviewed By: nikic, reames

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

show more ...

[SCEVExpander] Only create trunc when needed.

9345ab3a4550 updated generateOverflowCheck to skip creating checks that
always evaluate to false. This in turn means that we only need to
create TruncTr

[SCEVExpander] Only create trunc when needed.

9345ab3a4550 updated generateOverflowCheck to skip creating checks that
always evaluate to false. This in turn means that we only need to
create TruncTripCount if it is actually used.

Sink the TruncTripCount creating into ComputeEndCheck, so it is only
created when there's an actual check.

show more ...