[llvm] Replace `UndefValue` placeholders with `PoisonValue` in unit tests [NFC] (#116453)

This PR replaces all `UndefValue` act as placeholders with `PoisonValue`
in `llvm/unittests`.

[SCEV] Disallow simplifying phi(undef, X) to X (#115109)

See the following case:
```
@GlobIntONE = global i32 0, align 4

define ptr @src() {
entry:
br label %for.body.peel.begin

for.body

[SCEV] Disallow simplifying phi(undef, X) to X (#115109)

See the following case:
```
@GlobIntONE = global i32 0, align 4

define ptr @src() {
entry:
br label %for.body.peel.begin

for.body.peel.begin: ; preds = %entry
br label %for.body.peel

for.body.peel: ; preds = %for.body.peel.begin
br i1 true, label %cleanup.peel, label %cleanup.loopexit.peel

cleanup.loopexit.peel: ; preds = %for.body.peel
br label %cleanup.peel

cleanup.peel: ; preds = %cleanup.loopexit.peel, %for.body.peel
%retval.2.peel = phi ptr [ undef, %for.body.peel ], [ @GlobIntONE, %cleanup.loopexit.peel ]
br i1 true, label %for.body.peel.next, label %cleanup7

for.body.peel.next: ; preds = %cleanup.peel
br label %for.body.peel.next1

for.body.peel.next1: ; preds = %for.body.peel.next
br label %entry.peel.newph

entry.peel.newph: ; preds = %for.body.peel.next1
br label %for.body

for.body: ; preds = %cleanup, %entry.peel.newph
%retval.0 = phi ptr [ %retval.2.peel, %entry.peel.newph ], [ %retval.2, %cleanup ]
br i1 false, label %cleanup, label %cleanup.loopexit

cleanup.loopexit: ; preds = %for.body
br label %cleanup

cleanup: ; preds = %cleanup.loopexit, %for.body
%retval.2 = phi ptr [ %retval.0, %for.body ], [ @GlobIntONE, %cleanup.loopexit ]
br i1 false, label %for.body, label %cleanup7.loopexit

cleanup7.loopexit: ; preds = %cleanup
%retval.2.lcssa.ph = phi ptr [ %retval.2, %cleanup ]
br label %cleanup7

cleanup7: ; preds = %cleanup7.loopexit, %cleanup.peel
%retval.2.lcssa = phi ptr [ %retval.2.peel, %cleanup.peel ], [ %retval.2.lcssa.ph, %cleanup7.loopexit ]
ret ptr %retval.2.lcssa
}

define ptr @tgt() {
entry:
br label %for.body.peel.begin

for.body.peel.begin: ; preds = %entry
br label %for.body.peel

for.body.peel: ; preds = %for.body.peel.begin
br i1 true, label %cleanup.peel, label %cleanup.loopexit.peel

cleanup.loopexit.peel: ; preds = %for.body.peel
br label %cleanup.peel

cleanup.peel: ; preds = %cleanup.loopexit.peel, %for.body.peel
%retval.2.peel = phi ptr [ undef, %for.body.peel ], [ @GlobIntONE, %cleanup.loopexit.peel ]
br i1 true, label %for.body.peel.next, label %cleanup7

for.body.peel.next: ; preds = %cleanup.peel
br label %for.body.peel.next1

for.body.peel.next1: ; preds = %for.body.peel.next
br label %entry.peel.newph

entry.peel.newph: ; preds = %for.body.peel.next1
br label %for.body

for.body: ; preds = %cleanup, %entry.peel.newph
br i1 false, label %cleanup, label %cleanup.loopexit

cleanup.loopexit: ; preds = %for.body
br label %cleanup

cleanup: ; preds = %cleanup.loopexit, %for.body
br i1 false, label %for.body, label %cleanup7.loopexit

cleanup7.loopexit: ; preds = %cleanup
%retval.2.lcssa.ph = phi ptr [ %retval.2.peel, %cleanup ]
br label %cleanup7

cleanup7: ; preds = %cleanup7.loopexit, %cleanup.peel
%retval.2.lcssa = phi ptr [ %retval.2.peel, %cleanup.peel ], [ %retval.2.lcssa.ph, %cleanup7.loopexit ]
ret ptr %retval.2.lcssa
}
```
1. `simplifyInstruction(%retval.2.peel)` returns `@GlobIntONE`. Thus,
`ScalarEvolution::createNodeForPHI` returns SCEV expr `@GlobIntONE` for
`%retval.2.peel`.
2. `SimplifyIndvar::replaceIVUserWithLoopInvariant` tries to replace the
use of `%retval.2.peel` in `%retval.2.lcssa.ph` with `@GlobIntONE`.
3. `simplifyLoopAfterUnroll -> simplifyLoopIVs -> SCEVExpander::expand`
reuses `%retval.2.peel = phi ptr [ undef, %for.body.peel ], [
@GlobIntONE, %cleanup.loopexit.peel ]` to generate code for
`@GlobIntONE`. It is incorrect.

This patch disallows simplifying `phi(undef, X)` to `X` by setting
`CanUseUndef` to false.
Closes https://github.com/llvm/llvm-project/issues/114879.

show more ...

[UnitTests] Fix APInt signed flags (NFC)

This makes unit tests compatible with the assertion added in
https://github.com/llvm/llvm-project/pull/106524, by setting the
isSigned flag to the correct va

[UnitTests] Fix APInt signed flags (NFC)

This makes unit tests compatible with the assertion added in
https://github.com/llvm/llvm-project/pull/106524, by setting the
isSigned flag to the correct value or changing how the value is
constructed.

show more ...

[SCEV] Look through multiply in computeConstantDifference() (#103051)

Inside computeConstantDifference(), handle the case where both sides are
of the form `C * %x`, in which case we can strip off t

[SCEV] Look through multiply in computeConstantDifference() (#103051)

Inside computeConstantDifference(), handle the case where both sides are
of the form `C * %x`, in which case we can strip off the common
multiplication (as long as we remember to multiply by it for the
following difference calculation).

There is an obvious alternative implementation here, which would be to
directly decompose multiplies inside the "Multiplicity" accumulation.
This does work, but I've found this to be both significantly slower
(because everything has to work on APInt) and more complex in
implementation (e.g. because we now need to match back the new More/Less
with an arbitrary factor) without providing more power in practice. As
such, I went for the simpler variant here.

This is the last step to make computeConstantDifference() sufficiently
powerful to replace existing uses of
`cast<SCEVConstant>(getMinusSCEV())` with it.

show more ...

[SCEV] Handle more add/addrec mixes in computeConstantDifference() (#101999)

computeConstantDifference() can currently look through addrecs with
identical steps, and then through adds with identica

[SCEV] Handle more add/addrec mixes in computeConstantDifference() (#101999)

computeConstantDifference() can currently look through addrecs with
identical steps, and then through adds with identical operands (apart
from constants).

However, it fails to handle minor variations, such as two nested add
recs, or an outer add with an inner addrec (rather than the other way
around).

This patch supports these cases by adding a loop over the
simplifications, limited to a small number of iterations. The motivation
is the same as in #101339, to make
computeConstantDifference() powerful enough to replace existing uses of
`dyn_cast<SCEVConstant>(getMinusSCEV())` with it. Though as the IR test
diff shows, other callers may also benefit.

show more ...

[DebugInfo][RemoveDIs] Use iterator-insertion in unittests and fuzzer (#102015)

These are the final few places in LLVM that use instruction pointers to
insert instructions -- use iterators instead,

[DebugInfo][RemoveDIs] Use iterator-insertion in unittests and fuzzer (#102015)

These are the final few places in LLVM that use instruction pointers to
insert instructions -- use iterators instead, which is needed for
debug-info correctness in the future. Most of this is a gentle
scattering of getIterator calls or not deref-then-addrofing iterators.
libfuzzer does require a storage change to keep built instruction
positions in a container though. The unit-test changes are very
straightforwards.

This leaves us in a position where libfuzzer can't fuzz on either of
debug-info records, however I don't believe that fuzzing of debug-info
is in scope for the library.

show more ...

[SCEV] Add additional computeConstantDifference() tests (NFC)

And some tweaks to make this test easier to update. Use raw
string literals and print parse and verifier errors.

[SCEV] Use const SCEV * explicitly in more places.

Use const SCEV * explicitly in more places to prepare for
https://github.com/llvm/llvm-project/pull/91961. Split off as suggested.

[SCEV] Handle more adds in computeConstantDifference() (#101339)

Currently it only deals with the case where we're subtracting adds with
at most one non-constant operand. This patch extends it to c

[SCEV] Handle more adds in computeConstantDifference() (#101339)

Currently it only deals with the case where we're subtracting adds with
at most one non-constant operand. This patch extends it to cancel out
common operands for the subtraction of arbitrary add expressions.

The background here is that I want to replace a getMinusSCEV() call in
LAA with computeConstantDifference():

https://github.com/llvm/llvm-project/blob/93fecc2577ece0329f3bbe2719bbc5b4b9b30010/llvm/lib/Analysis/LoopAccessAnalysis.cpp#L1602-L1603

This particular call is very expensive in some cases (e.g. lencod with
LTO) and computeConstantDifference() could achieve this much more
cheaply, because it does not need to construct new SCEV expressions.

However, the current computeConstantDifference() implementation is too
weak for this and misses many basic cases. This is a step towards making
it more powerful while still keeping it pretty fast.

show more ...

Remove value cache in SCEV comparator. (#100721)

The cache triggers almost never, and seems unlikely to help with
performance. However, when it does, it is likely to cause the comparator
to become

Remove value cache in SCEV comparator. (#100721)

The cache triggers almost never, and seems unlikely to help with
performance. However, when it does, it is likely to cause the comparator
to become inconsistent due to a bad interaction of the depth limit and
cache hits. This leads to crashes in debug builds. See the new unit test
for a reproducer.

show more ...

[SCEV] forgetValue: support (with-overflow-inst op0, op1) (#98015)

The use-def walk in forgetValue() was skipping instructions with
non-SCEVable types. However, SCEV may look past with.overflow
in

[SCEV] forgetValue: support (with-overflow-inst op0, op1) (#98015)

The use-def walk in forgetValue() was skipping instructions with
non-SCEVable types. However, SCEV may look past with.overflow
intrinsics returning aggregates.

Fixes #97586.

show more ...

[NFC] Remove Type::getInt8PtrTy (#71029)

Replace this with PointerType::getUnqual().
Followup to the opaque pointer transition. Fixes an in-code TODO item.

[llvm] Replace uses of Type::getPointerTo (NFC)

opaque pointer clean-up effort (NFC)

[llvm][unittests] Remove unneeded header includes

[llvm] Drop some bitcasts and references related to typed pointers

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

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

This reverts commit 57e093162e27334730d8ed8f7b25b1b6f65ec8c8.

[SCEV] Preserve divisibility and min/max information in applyLoopGuards

applyLoopGuards doesn't always preserve information when there are multiple assumes.

This patch tries to deal with multiple a

[SCEV] Preserve divisibility and min/max information in applyLoopGuards

applyLoopGuards doesn't always preserve information when there are multiple assumes.

This patch tries to deal with multiple assumes regarding a SCEV's divisibility and min/max values, and rewrite it into a SCEV that still preserves all of the information.
For example, let the trip count of the loop be TC. Consider the 3 following assumes:

1. __builtin_assume(TC % 8 == 0);
2. __builtin_assume(TC > 0);
3. __builtin_assume(TC < 100);

Before this patch, depending on the assume processing order applyLoopGuards could create the following SCEV:
max(min((8 * (TC / 8)) , 99), 1)

Looking at this SCEV, it doesn't preserve the divisibility by 8 information.

After this patch, depending on the assume processing order applyLoopGuards could create the following SCEV:
max(min((8 * (TC / 8)) , 96), 8)

By aligning up 1 to 8, and aligning down 99 to 96, the new SCEV still preserves all of the original assumes.

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

show more ...

[SCEV][NFC] Introduce utility function to get power of 2

The new function has been added to SCEV that allows to raise the number 2
to the desired power.

Authored-by: Dmitry Bakunevich

Differential

[SCEV][NFC] Introduce utility function to get power of 2

The new function has been added to SCEV that allows to raise the number 2
to the desired power.

Authored-by: Dmitry Bakunevich

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

show more ...

Revert "[SCEV] Preserve divisibility and min/max information in applyLoopGuards"

This reverts commit 219ba2fb7b0ae89101f3c81a47fe4fc4aa80dea4.

[SCEV] Preserve divisibility and min/max information in applyLoopGuards

applyLoopGuards doesn't always preserve information when there are multiple assumes.

This patch tries to deal with multiple a

[SCEV] Preserve divisibility and min/max information in applyLoopGuards

applyLoopGuards doesn't always preserve information when there are multiple assumes.

This patch tries to deal with multiple assumes regarding a SCEV's divisibility and min/max values, and rewrite it into a SCEV that still preserves all of the information.
For example, let the trip count of the loop be TC. Consider the 3 following assumes:

1. __builtin_assume(TC % 8 == 0);
2. __builtin_assume(TC > 0);
3. __builtin_assume(TC < 100);

Before this patch, depending on the assume processing order applyLoopGuards could create the following SCEV:
max(min((8 * (TC / 8)) , 99), 1)

Looking at this SCEV, it doesn't preserve the divisibility by 8 information.

After this patch, depending on the assume processing order applyLoopGuards could create the following SCEV:
max(min((8 * (TC / 8)) , 96), 8)

By aligning up 1 to 8, and aligning down 99 to 96, the new SCEV still preserves all of the original assumes.

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

show more ...

[Analysis] llvm::Optional => std::optional

[SCEV] Convert Optional to std::optional

[llvm/unittests] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the am

[llvm/unittests] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

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

[ScalarEvolution] Infer loop max trip count from array accesses

Data references in a loop should not access elements over the
statically allocated size. So we can infer a loop max trip count
from th

[ScalarEvolution] Infer loop max trip count from array accesses

Data references in a loop should not access elements over the
statically allocated size. So we can infer a loop max trip count
from this undefined behavior.

Reviewed By: reames, mkazantsev, nikic

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

show more ...