[llvm] LLVM_FALLTHROUGH => [[fallthrough]]. NFC

With C++17 there is no Clang pedantic warning or MSVC C5051.

Fix compiler error: init-statements in if/switch.

Reviewed By: pifon2a

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

Fix a stack overflow in ScalarEvolution.

Unfortunately, this overflow is extremely hard to reproduce reliably (in fact, I was unable to do so). The issue is that:

- getOperandsToCreate sometimes sk

Fix a stack overflow in ScalarEvolution.

Unfortunately, this overflow is extremely hard to reproduce reliably (in fact, I was unable to do so). The issue is that:

- getOperandsToCreate sometimes skips creating an SCEV for the LHS
- then, createSCEV is called for the BinaryOp
- ... which calls getNoWrapFlagsFromUB
- ... which under certain circumstances calls isSCEVExprNeverPoison
- ... which under certain circumstances requires the SCEVs of all operands

For certain deep dependency trees, this causes a stack overflow.

Reviewed By: bkramer, fhahn

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

show more ...

[SCEV] Use context to strengthen flags of BinOps

Sometimes SCEV cannot infer nuw/nsw from something as simple as
```
len in [0, MAX_INT]
...
iv = phi(0, iv.next)
guard(iv <s len)
guard(iv <u

[SCEV] Use context to strengthen flags of BinOps

Sometimes SCEV cannot infer nuw/nsw from something as simple as
```
len in [0, MAX_INT]
...
iv = phi(0, iv.next)
guard(iv <s len)
guard(iv <u len)
iv.next = iv + 1
```
just because flag strenthening only relies on definition and does not use local facts.
This patch adds support for the simplest case: inference of flags of `add(x, constant)`
if we can contextually prove that `x <= max_int - constant`.

In case if it has negative CT impact, we can add an option to switch it off. I woudln't
expect that though.

Differential Revision: https://reviews.llvm.org/D129643
Reviewed By: apilipenko

show more ...

[SCEV] Avoid repeated proveNoSignedWrapViaInduction calls.

At the moment, proveNoSignedWrapViaInduction may be called for the
same AddRec a large number of times via getSignExtendExpr. This can hav

[SCEV] Avoid repeated proveNoSignedWrapViaInduction calls.

At the moment, proveNoSignedWrapViaInduction may be called for the
same AddRec a large number of times via getSignExtendExpr. This can have
a severe compile-time impact for very loop-heavy code.

If proveNoSignedWrapViaInduction failed to prove NSW the first time,
it is unlikely to succeed on subsequent tries and the cost doesn't seem
to be justified.

This is the signed version of 8daa338297d533d / D130648.

This can drastically improve compile-time in some excessive cases and
also has a slightly positive compile-time impact on CTMark:

NewPM-O3: -0.06%
NewPM-ReleaseThinLTO: -0.04%
NewPM-ReleaseLTO-g: -0.04%

https://llvm-compile-time-tracker.com/compare.php?from=8daa338297d533db4d1ae8d3770613eb25c29688&to=aed126a196e7a5a9803543d9b4d6bdb233d0009c&stat=instructions

Reviewed By: nikic

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

show more ...

[SCEV] Avoid repeated proveNoUnsignedWrapViaInduction calls.

At the moment, proveNoUnsignedWrapViaInduction may be called for the
same AddRec a large number of times via getZeroExtendExpr. This can

[SCEV] Avoid repeated proveNoUnsignedWrapViaInduction calls.

At the moment, proveNoUnsignedWrapViaInduction may be called for the
same AddRec a large number of times via getZeroExtendExpr. This can have
a severe compile-time impact for very loop-heavy code. One one
particular workload, LSR takes ~51s without this patch, almost
exlusively in proveNoUnsignedWrapViaInduction. With this patch, the time
in LSR drops to ~0.4s.

If proveNoUnsignedWrapViaInduction failed to prove NUW the first time,
it is unlikely to succeed on subsequent tries and the cost doesn't seem
to be justified.

Besides drastically improving compile-time in some excessive cases, this
also has a slightly positive compile-time impact on CTMark:

NewPM-O3: -0.07%
NewPM-ReleaseThinLTO: -0.08%
NewPM-ReleaseLTO-g: -0.06

https://llvm-compile-time-tracker.com/compare.php?from=b435da027d7774c24cdb8c88d09f6b771e07fb14&to=f2729e33e8284b502f6c35a43345272252f35d12&stat=instructions

Reviewed By: nikic

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

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