Revert "Recommit "[SCEV] Look through single value PHIs." (take 3)"

This reverts commit 20d798bd47ec5191de1b2a8a031da06a04e612e1.

This commit caused crashes in some cases, see github issue #58152.

Revert "Recommit "[SCEV] Look through single value PHIs." (take 3)"

This reverts commit 20d798bd47ec5191de1b2a8a031da06a04e612e1.

This commit caused crashes in some cases, see github issue #58152.
This is fixed on main, but backporting it requires multiple
nontrivial cherrypicks.

Updating llvm/test/Transforms/LoopVectorize/create-induction-resume.ll
with update_test_checks.py, so this isn't an exact automatic revert,
as that test case was added after the reverted commit.

This fixes #58152 for the release branch.

show more ...

[SCEV][NFC][CT] Cheaper handling of guards in isBasicBlockEntryGuardedByCond

Handle guards uniformly with assumes, rather than iterating through all
block instructions in attempt to find them.

Diff

[SCEV][NFC][CT] Cheaper handling of guards in isBasicBlockEntryGuardedByCond

Handle guards uniformly with assumes, rather than iterating through all
block instructions in attempt to find them.

Differential Revision: https://reviews.llvm.org/D129874
Reviewed By: nikic

show more ...

[SCEV][NFC][CT] Do not waste time proving contextual facts for unreached loops and blocks

In fact, in unreached code we can say that every fact is true. So do not waste time trying to
do something s

[SCEV][NFC][CT] Do not waste time proving contextual facts for unreached loops and blocks

In fact, in unreached code we can say that every fact is true. So do not waste time trying to
do something smarter.

Formally it's not an NFC because it may change query results in unreached code, but they
won't have any impact on execution.

Hypothetical CT boost expected but not measured in practice.

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

show more ...

[Analysis] Qualify auto variables in for loops (NFC)

[NFC][SCEV] Rename variable to correspond its current meaning

[SCEV] List all binops in getOperandsToCreate()

Explicitly list all binops rather than having a default case. There
were two bugs here:
1. U->getOpcode() was used instead of BO->Opcode, which means

[SCEV] List all binops in getOperandsToCreate()

Explicitly list all binops rather than having a default case. There
were two bugs here:
1. U->getOpcode() was used instead of BO->Opcode, which means we
used the logic for the wrong opcode in some cases.
2. SCEV construction does not support LShr. We should return
unknown for it rather than recursing into the operands.

show more ...

[SCEV] Avoid creating unnecessary SCEVs for SelectInsts.

After 675080a4533b, we always create SCEVs for all operands of a
SelectInst. This can cause notable compile-time regressions compared to
the

[SCEV] Avoid creating unnecessary SCEVs for SelectInsts.

After 675080a4533b, we always create SCEVs for all operands of a
SelectInst. This can cause notable compile-time regressions compared to
the recursive algorithm, which only evaluates the operands if the select
is in a form we can create a usable expression.

This approach adds additional logic to getOperandsToCreate to only
queue operands for selects if we will later be able to construct a
usable SCEV.

Unfortunately this introduces a bit of coupling between actual SCEV
construction for selects and getOperandsToCreate, but I am not sure if
there are better alternatives to address the regression mentioned for
675080a4533b.

This doesn't have any notable compile-time impact on CTMark.

Reviewed By: nikic

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

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

[llvm] Use value instead of getValue (NFC)

[SCEV][NFC] Make getStrengthenedNoWrapFlagsFromBinOp return optional

[ConstExpr] Don't create div/rem expressions

This removes creation of udiv/sdiv/urem/srem constant expressions,
in preparation for their removal. I've added a
ConstantExpr::isDesirableBinOp() predic

[ConstExpr] Don't create div/rem expressions

This removes creation of udiv/sdiv/urem/srem constant expressions,
in preparation for their removal. I've added a
ConstantExpr::isDesirableBinOp() predicate to determine whether
an expression should be created for a certain operator.

With this patch, div/rem expressions can still be created through
explicit IR/bitcode, forbidding them entirely will be the next step.

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

show more ...

[SCEV] Fix isImpliedViaMerge() with values from previous iteration (PR56242)

When trying to prove an implied condition on a phi by proving it
for all incoming values, we need to be careful about val

[SCEV] Fix isImpliedViaMerge() with values from previous iteration (PR56242)

When trying to prove an implied condition on a phi by proving it
for all incoming values, we need to be careful about values coming
from a backedge, as these may refer to a previous loop iteration.
A variant of this issue was fixed in D101829, but the dominance
condition used there isn't quite right: It checks that the value
dominates the incoming block, which doesn't exclude backedges
(values defined in a loop will usually dominate the loop latch,
which is the incoming block of the backedge).

Instead, we should be checking for domination of the phi block.
Any values defined inside the loop will not dominate the loop
header phi.

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

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

show more ...

[SCEV] recognize llvm.annotation intrinsic

Reviewed By: nikic

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

[SCEV] Remove unnecessary pointer handling in BuildConstantFromSCEV (NFCI)

Nowadays, we do not allow pointers in multiplies, and adds can only
have a single pointer, which is also guaranteed to be l

[SCEV] Remove unnecessary pointer handling in BuildConstantFromSCEV (NFCI)

Nowadays, we do not allow pointers in multiplies, and adds can only
have a single pointer, which is also guaranteed to be last by
complexity sorting. As such, we can somewhat simplify the treatment
of pointer types.

show more ...

[ConstantFold] Support loads in ConstantFoldInstOperands()

This allows all constant folding to happen through a single
function, without requiring special handling for loads at each
call-site.

This

[ConstantFold] Support loads in ConstantFoldInstOperands()

This allows all constant folding to happen through a single
function, without requiring special handling for loads at each
call-site.

This may not be NFC because some callers currently don't do that
special handling.

show more ...

[ConstantFold] Supports compares in ConstantFoldInstOperands()

Support compares in ConstantFoldInstOperands(), instead of
forcing the use of ConstantFoldCompareInstOperands(). Also handle
insertvalu

[ConstantFold] Supports compares in ConstantFoldInstOperands()

Support compares in ConstantFoldInstOperands(), instead of
forcing the use of ConstantFoldCompareInstOperands(). Also handle
insertvalue (extractvalue was already handled).

This removes a footgun, where many uses of ConstantFoldInstOperands()
need a separate check for compares beforehand. It's particularly
insidious if called on a constant expression, because it doesn't
fail in that case, but will just not do DL-dependent folding.

show more ...

[SCEV] Don't create udiv constant expression (NFC)

Work on APInts to make it clear that this will not create a
constant expression.

This code path is not reached if the RHS is zero.

[SCEV] Construct SCEV iteratively.

This patch updates SCEV construction to work iteratively instead of recursively
in most cases. It resolves stack overflow issues when trying to construct SCEVs
for

[SCEV] Construct SCEV iteratively.

This patch updates SCEV construction to work iteratively instead of recursively
in most cases. It resolves stack overflow issues when trying to construct SCEVs
for certain inputs, e.g. PR45201.

The basic approach is to to use a worklist to queue operands of V which
need to be created before V. To do so, the current patch adds a
getOperandsToCreate function which collects the operands SCEV
construction depends on for a given value. This is a slight duplication
with createSCEV.

At the moment, SCEVs for phis are still created recursively.

Fixes #32078, #42594, #44546, #49293, #49599, #55333, #55511

Reviewed By: nikic

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

show more ...

[SCEV] Assert that GEP source element type is sized (NFC)

This is checked by the IR verifier, so replace the condition with
an assert.

[SCEV] Use SCEVUnknown(poison) instead of SCEVUnknown(undef).

Use poison instead of undef for SCEVUnkown of unreachable values.
This should be in line with the movement to replace undef with poison

[SCEV] Use SCEVUnknown(poison) instead of SCEVUnknown(undef).

Use poison instead of undef for SCEVUnkown of unreachable values.
This should be in line with the movement to replace undef with poison
when possible.

Suggested in D114650.

Reviewed By: nikic

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

show more ...

[llvm] Don't use Optional::hasValue (NFC)

This patch replaces Optional::hasValue with the implicit cast to bool
in conditionals only.

Revert "Don't use Optional::hasValue (NFC)"

This reverts commit aa8feeefd3ac6c78ee8f67bf033976fc7d68bc6d.

Don't use Optional::hasValue (NFC)

[llvm] Don't use Optional::getValue (NFC)

Don't use Optional::hasValue (NFC)