Revert "[ValueTracking] Remove by-ref computeKnownBits() overloads (NFC)"

This reverts commit b5743d4798b250506965e07ebab806a3c2d767cc.

This causes some minor compile-time impact. Revert for now, b

Revert "[ValueTracking] Remove by-ref computeKnownBits() overloads (NFC)"

This reverts commit b5743d4798b250506965e07ebab806a3c2d767cc.

This causes some minor compile-time impact. Revert for now, better
to do the change more gradually.

show more ...

[ValueTracking] Remove by-ref computeKnownBits() overloads (NFC)

Remove the old overloads that accept KnownBits by reference, in
favor of those that return it by value.

[ValueTracking] Use SimplifyQuery in haveNoCommonBitsSet() (NFC)

Pass SimplifyQuery instead of unpacked list of arguments.

[SCEV] Make invalidation in SCEVCallbackVH more thorough (#68316)

When a SCEVCallbackVH is RAUWed, we currently do a def-use walk and
remove dependent instructions from the ValueExprMap. However, u

[SCEV] Make invalidation in SCEVCallbackVH more thorough (#68316)

When a SCEVCallbackVH is RAUWed, we currently do a def-use walk and
remove dependent instructions from the ValueExprMap. However, unlike
SCEVs usual invalidation, this does not forget memoized values.

The end result is that we might end up removing a SCEVUnknown from the
map, while that expression still has users. Due to that, we may later
fail to invalide those expressions. In particular, invalidation of loop
dispositions only does something if there is an expression for the
value, which would not be the case here.

Fix this by using the standard forgetValue() API, instead of rolling a
custom variant.

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

show more ...

Revert "[SCEV] Don't invalidate past dependency-breaking instructions"

Unforuntately, the assumption underlying this optimization is
incorrect for getSCEVAtScope(): A SCEVUnknown instruction with
op

Revert "[SCEV] Don't invalidate past dependency-breaking instructions"

Unforuntately, the assumption underlying this optimization is
incorrect for getSCEVAtScope(): A SCEVUnknown instruction with
operands that have constant loop exit values can evaluate to
a constant, thus creating a dependency from an "always unknown"
instruction.

Losing this optimization is quite unfortunate, but it doesn't
seem like there is any simple workaround for this.

Fixes #68260.

This reverts commit 3ddd1ffb721dd0ac3faa4a53c76b6904e862b7ab.

show more ...

[SCEV] Don't require positive BTC when non-zero is sufficient

The only thing we care about here is that we don't exit on the
first iteration. Whether the BTC is large enough to overflow the
signed i

[SCEV] Don't require positive BTC when non-zero is sufficient

The only thing we care about here is that we don't exit on the
first iteration. Whether the BTC is large enough to overflow the
signed integer space is not relevant.

show more ...

[SCEV] Remove unnecessary cast code (NFC)

The types should always match here. Possibly this is a leftover
from pre-opaque-pointers times.

[SCEV] Remove zext/sext from BuildConstantForSCEV

In preparation for removing these constant expressions.

[SCEV] Work on APInt instead of ConstantExpr (NFC)

Avoid an unnecessary use of ConstantExpr::getZExt() when
APInt::zext() is sufficient.

[Analysis] Use drop_begin (NFC)

[SCEV] Require that addrec operands dominate the loop

SCEVExpander currently has special handling for the case where the
start or the step of an addrec do not dominate the loop header,
which is not

[SCEV] Require that addrec operands dominate the loop

SCEVExpander currently has special handling for the case where the
start or the step of an addrec do not dominate the loop header,
which is not used by any lit test.

Initially I thought that this is entirely dead code, because
addrec operands are required to be loop invariant. However,
SCEV currently allows creating an addrec with operands that are
loop invariant but defined *after* the loop.

This doesn't seem like a useful case to allow, and we don't
appear to be using this outside a single easy to adjust unit test.

show more ...

[SCEV] Fix incorrect nsw inference for multiply of addrec (#66500)

SCEV currently preserves the nsw flag when performing an nsw multiply of
an nsw addrec. While this is legal for nuw, this is not g

[SCEV] Fix incorrect nsw inference for multiply of addrec (#66500)

SCEV currently preserves the nsw flag when performing an nsw multiply of
an nsw addrec. While this is legal for nuw, this is not generally the
case for nsw.

This is because nsw mul does not distribute over nsw add:
https://alive2.llvm.org/ce/z/mergCt

Instead, we need either both nuw and nsw to be set
(https://alive2.llvm.org/ce/z/7wpgGc) or explicitly prove that the
distributed multiplications are also nsw
(https://alive2.llvm.org/ce/z/wef9su).

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

show more ...

[SCEV] Fix potentially empty set for unsigned ranges

The following commit enabled the analysis of ranges for heap allocations:
22ca38da25e19a7c5fcfeb3f22159aba92ec381e

The range turns out to be emp

[SCEV] Fix potentially empty set for unsigned ranges

The following commit enabled the analysis of ranges for heap allocations:
22ca38da25e19a7c5fcfeb3f22159aba92ec381e

The range turns out to be empty in cases such as the one in test (which
is [1,1)), leading to an assertion failure. This patch fixes for the
same case.

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

Reviewed By: fhahn

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

show more ...

[SCEV] Compute SCEV for ashr(add(shl(x, n), c), m) instr triplet

%x = shl i64 %w, n
%y = add i64 %x, c
%z = ashr i64 %y, m

The above given instruction triplet is seen many times in the generated
LL

[SCEV] Compute SCEV for ashr(add(shl(x, n), c), m) instr triplet

%x = shl i64 %w, n
%y = add i64 %x, c
%z = ashr i64 %y, m

The above given instruction triplet is seen many times in the generated
LLVM IR, but SCEV model is not able to compute the SCEV value of AShr
instruction in this case.

This patch models the two cases of the above instruction pattern using
the following expression:

=> sext(add(mul(trunc(w), 2^(n-m)), c >> m))

1) when n = m the expression reduces to sext(add(trunc(w), c >> n))
as n-m=0, and multiplying with 2^0 gives the same result.

2) when n > m the expression works as given above.

It also adds several unittest to verify that SCEV is able to compute
the value.

$ opt sext-add-inreg.ll -passes="print<scalar-evolution>"

Comparing the snippets of the result of SCEV analysis:

* SCEV of ashr before change
----------------------------
%idxprom = ashr exact i64 %sext, 32
--> %idxprom U: [-2147483648,2147483648) S: [-2147483648,2147483648)
Exits: 8 LoopDispositions: { %for.body: Variant }

* SCEV of ashr after change
---------------------------
%idxprom = ashr exact i64 %sext, 32
--> {0,+,1}<nuw><nsw><%for.body> U: [0,9) S: [0,9)
Exits: 8 LoopDispositions: { %for.body: Computable }

LoopDisposition of the given SCEV was LoopVariant before, after adding
the new way to model the instruction, the LoopDisposition becomes
LoopComputable as it is able to compute the SCEV of the instruction.

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

show more ...

[SCEVExpander] Fix incorrect reuse of more poisonous instructions (PR63763)

SCEVExpander tries to reuse existing instruction with the same
SCEV expression. However, doing this replacement blindly is

[SCEVExpander] Fix incorrect reuse of more poisonous instructions (PR63763)

SCEVExpander tries to reuse existing instruction with the same
SCEV expression. However, doing this replacement blindly is not
safe, because the instruction might be more poisonous.

What we were already doing is to drop poison-generating flags on
the reused instruction. But this is not the only way that more
poison can be introduced. The poison-generating flag might not
be directly on the reused instruction, or the poison contribution
might come from something like 0 * %var, which folds to 0 but can
still introduce poison.

This patch fixes the issue in a principled way, by determining which
values can contribute poison to the SCEV expression, and then
checking whether any additional values can contribute poison to the
instruction being reused. Poison-generating flags are dropped if
doing that enables reuse.

This is a pretty big hammer and does cause some regressions in
tests, but less than I would have expected. I wasn't able to come
up with a less intrusive fix that still satisfies the correctness
requirements.

Fixes https://github.com/llvm/llvm-project/issues/63763.
Fixes https://github.com/llvm/llvm-project/issues/63926.
Fixes https://github.com/llvm/llvm-project/issues/64333.
Fixes https://github.com/llvm/llvm-project/issues/63727.

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

show more ...

[SCEV] Move SCEVPoisonCollector outside function (NFC)

To allow reusing it. Also switch it to store SCEVUnknown rather
than SCEV, as only these can produce poison.

[SCEV] Remove unnecessary bitcast (NFC)

[ScalarEvolution][NFC] Typo fix

Fix typo in ScalarEvolution public method.

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

[ADT] Support iterating size-based integer ranges.

It seems the ranges start with 0 in most cases.

Reviewed By: dblaikie, gchatelet

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

[NFC] Update stale comment after D154001

[ScalarEvolution] Analyze ranges for heap allocations

Followup to D153624. Allows for better exit count calculations for loops checking heap allocations against null.

Reviewed By: nikic

Differenti

[ScalarEvolution] Analyze ranges for heap allocations

Followup to D153624. Allows for better exit count calculations for loops checking heap allocations against null.

Reviewed By: nikic

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

show more ...

Revert "[ScalarEvolution] Infer loop max trip count from array accesses"

This reverts commit 57e093162e27334730d8ed8f7b25b1b6f65ec8c8.

[SCEV] Make use of non-null pointers for range calculation

We know that certain pointers (e.g. non-extern-weak globals or
allocas in default address space) are not null, in which case the
lowest add

[SCEV] Make use of non-null pointers for range calculation

We know that certain pointers (e.g. non-extern-weak globals or
allocas in default address space) are not null, in which case the
lowest address they can be allocated at is their alignment.

This allows us to calculate better exit counts for loops that have
an additional null check in the guarding condition
(see alloca_icmp_null_exit_count).

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

show more ...

[SCEV] Optimize FoldID

Improve compile time

https://llvm-compile-time-tracker.com/compare.php?from=773e5dfbc6bf4d4c5be568a039661e9baad80d15&to=7ba15f3a4b59181110e73dc397a9fe56165a2b73&stat=instruct

[SCEV] Optimize FoldID

Improve compile time

https://llvm-compile-time-tracker.com/compare.php?from=773e5dfbc6bf4d4c5be568a039661e9baad80d15&to=7ba15f3a4b59181110e73dc397a9fe56165a2b73&stat=instructions:u

Reviewed By: MaskRay

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

show more ...

[SCEV] Print block dispositions on mismatch (NFC)