[NFC][RemoveDIs] Bulk update utilities to insert with iterators

As part of the RemoveDIs project we need LLVM to insert instructions using
iterators wherever possible, so that the iterators can carr

[NFC][RemoveDIs] Bulk update utilities to insert with iterators

As part of the RemoveDIs project we need LLVM to insert instructions using
iterators wherever possible, so that the iterators can carry a bit of
debug-info. This commit implements some of that by updating the contents of
llvm/lib/Transforms/Utils to always use iterator-versions of instruction
constructors.

There are two general flavours of update:
* Almost all call-sites just call getIterator on an instruction
* Several make use of an existing iterator (scenarios where the code is
actually significant for debug-info)
The underlying logic is that any call to getFirstInsertionPt or similar
APIs that identify the start of a block need to have that iterator passed
directly to the insertion function, without being converted to a bare
Instruction pointer along the way.

I've also switched DemotePHIToStack to take an optional iterator: it needs
to take an iterator, and having a no-insert-location behaviour appears to
be important. The constructors for ICmpInst and FCmpInst have been updated
too. They're the only instructions that take block _references_ rather than
pointers for certain calls, and a future patch is going to make use of
default-null block insertion locations.

All of this should be NFC.

show more ...

[LIR][SCEVExpander] Restore original flags when aborting transform (#82362)

SCEVExpanderCleaner will currently remove instructions created by
SCEVExpander, but not restore poison generating flags t

[LIR][SCEVExpander] Restore original flags when aborting transform (#82362)

SCEVExpanderCleaner will currently remove instructions created by
SCEVExpander, but not restore poison generating flags that it may have
dropped. As such, running LIR can currently spuriously drop flags
without performing any transforms.

Fix this by keeping track of original instruction flags in SCEVExpander.

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

show more ...

[IndVars] Recompute flags if needed in widenIVUse of IV increment. (#82352)

widenIVUse may hoist a wide induction increment and introduce new uses,
but does not recompute the wrap flags. In some ca

[IndVars] Recompute flags if needed in widenIVUse of IV increment. (#82352)

widenIVUse may hoist a wide induction increment and introduce new uses,
but does not recompute the wrap flags. In some cases this can make the
new uses of the wide IV inc more poisonous.

Update the code to recompute flags if needed when hoisting an IV. If
both the narrow and wide IV increment's flags match and we can re-use
the flags from the increments, there's no need to recompute the flags,
as the replacement won't make the new uses of the wide IV's increment
more poisonous.

Note that this also updates a stale comment which claimed that the widen
increment is only used if it dominates the new use.

The helper should also be used to guard the code added in da437330be,
which I am planning on doing separately once the helper lands.

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

show more ...

[SCEVExpander] Don't use recursive expansion for ptr IV inc

Similar to the non-ptr case, directly create the getelementptr
instruction. Going through expandAddToGEP() no longer makes sense
with opaq

[SCEVExpander] Don't use recursive expansion for ptr IV inc

Similar to the non-ptr case, directly create the getelementptr
instruction. Going through expandAddToGEP() no longer makes sense
with opaque pointers, where generating the necessary instruction
is trivial.

This avoids recursive expansion of (the SCEV of) StepV while the
IR is in an inconsistent state, in particular with an incomplete
IV phi node, which utilities may not be prepared to deal with.

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

show more ...

[SCEV] Move canReuseInstruction() helper into SCEV (NFC)

To allow reusing it in IndVars.

[SCEVExpander] Do not reuse disjoint or (#80281)

SCEV treats "or disjoint" the same as "add nsw nuw". However, when
expanding, we cannot generally replace an add SCEV node with an "or
disjoint" in

[SCEVExpander] Do not reuse disjoint or (#80281)

SCEV treats "or disjoint" the same as "add nsw nuw". However, when
expanding, we cannot generally replace an add SCEV node with an "or
disjoint" instruction. Just dropping the poison flag is insufficient in
this case, we would have to actually convert the or into an add.

This is a partial fix for #79861.

show more ...

[SCEVExp] Keep NUW/NSW if both original inc and isomporphic inc agree. (#79512)

We are replacing with a wider increment. If both OrigInc and
IsomorphicInc are NUW/NSW, then we can preserve them on

[SCEVExp] Keep NUW/NSW if both original inc and isomporphic inc agree. (#79512)

We are replacing with a wider increment. If both OrigInc and
IsomorphicInc are NUW/NSW, then we can preserve them on the wider
increment; the narrower IsomorphicInc would wrap before the wider
OrigInc, so the replacement won't make IsomorphicInc's uses more
poisonous.

PR: https://github.com/llvm/llvm-project/pull/79512

show more ...

[Transforms] Use llvm::pred_size and llvm::pred_successors (NFC)

[SCEVExp] Move logic to replace congruent IV increments to helper (NFC).

Move logic to replace congruent IV increments to helper function, to
reduce the indentation by using early returns. This is i

[SCEVExp] Move logic to replace congruent IV increments to helper (NFC).

Move logic to replace congruent IV increments to helper function, to
reduce the indentation by using early returns. This is in preparation
for a follow-up patch.

show more ...

[IRBuilder] Add CreatePtrAdd() method (NFC) (#77582)

This abstracts over the common pattern of creating a gep with i8 element
type.

[SCEVExpander] Attempt to reinfer flags dropped due to CSE (#72431)

LSR uses SCEVExpander to generate induction formulas. The expander
internally tries to reuse existing IR expressions. To do that,

[SCEVExpander] Attempt to reinfer flags dropped due to CSE (#72431)

LSR uses SCEVExpander to generate induction formulas. The expander
internally tries to reuse existing IR expressions. To do that, it needs
to strip any poison generating flags (nsw, nuw, exact, nneg, etc..)
which may not be valid for the newly added users.

This is conservatively correct, but has the effect that LSR will strip
nneg flags on zext instructions involved in trip counts in loop
preheaders. To avoid this, this patch adjusts the expanded to reinfer
the flags on the CSE candidate if legal for all possible users.

This should fix the regression reported in
https://github.com/llvm/llvm-project/issues/71200.

This should arguably be done inside canReuseInstruction instead, but
doing it outside is more conservative compile time wise. Both
canReuseInstruction and isGuaranteedNotToBePoison walk operand lists, so
right now we are performing work which is roughly O(N^2) in the size of
the operand graph. We should fix that before making the per operand step
more expensive. My tenative plan is to land this, and then rework the
code to sink the logic into more core interfaces.

show more ...

[IRBuilder] Add IsNonNeg param to CreateZExt() (NFC)

[SCEV] Teach SCEVExpander to use zext nneg when possible (#70815)

zext nneg was recently added to the IR in #67982. Teaching SCEVExpander
to emit nneg when possible is valuable since SCEV may have

[SCEV] Teach SCEVExpander to use zext nneg when possible (#70815)

zext nneg was recently added to the IR in #67982. Teaching SCEVExpander
to emit nneg when possible is valuable since SCEV may have proved
non-trivial facts about loop bounds which would otherwise be lost when
materializing the value.

show more ...

[SCEVExpander] Remove unused variable [NFC]

gcc warned about it:
../lib/Transforms/Utils/ScalarEvolutionExpander.cpp: In lambda function:
../lib/Transforms/Utils/ScalarEvolutionExpander.cpp:2104:2

[SCEVExpander] Remove unused variable [NFC]

gcc warned about it:
../lib/Transforms/Utils/ScalarEvolutionExpander.cpp: In lambda function:
../lib/Transforms/Utils/ScalarEvolutionExpander.cpp:2104:22: warning: unused variable 'ARPtrTy' [-Wunused-variable]
2104 | if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARTy)) {
| ^~~~~~~
Fix the warning by removing the variable and turn dyn_cast into isa.

show more ...

[SCEVExpander] Clarify absence of no-op casts (NFC)

Remove all the expandCodeFor() uses that specify an explicit type,
as well as InsertNoopCastOfTo() calls and most uses of
getEffectiveSCEVType().

[SCEVExpander] Clarify absence of no-op casts (NFC)

Remove all the expandCodeFor() uses that specify an explicit type,
as well as InsertNoopCastOfTo() calls and most uses of
getEffectiveSCEVType().

The only place where no-op casts can now be inserted are public
expandCodeFor() uses.

show more ...

[SCEV] Fix -Wunused-variable in ScalarEvolutionExpander.cpp (NFC)

llvm-project/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp:1077:15: error: unused variable 'Start' [-Werror,-Wunused-variabl

[SCEV] Fix -Wunused-variable in ScalarEvolutionExpander.cpp (NFC)

llvm-project/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp:1077:15: error: unused variable 'Start' [-Werror,-Wunused-variable]
const SCEV *Start = Normalized->getStart();
^
1 error generated.

show more ...

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

[SCEVExpander] Drop ExpandTy argument from expandIVInc() (NFC)

Check the type of the phi node instead (as the comment already
indicates).

[SCEVExpander] Drop Ty argument from expandAddToGEP() (NFC)

We can directly use the type of Offset here.

[SCEVExpander] Remove some unnecessary effective type handling (NFC)

A lot of SCEV expressions only work on integers -- in which case
the effective type will always be the same as the type.

There i

[SCEVExpander] Remove some unnecessary effective type handling (NFC)

A lot of SCEV expressions only work on integers -- in which case
the effective type will always be the same as the type.

There is a lot more cleanup to do here.

show more ...

[SCEVExpander] Remove unnecessary expandCodeForImpl() wrapper (NFC)

expandCodeFor() was directly calling expandCodeForImpl(). Drop the
Impl variant.

[NFC][RemoveDIs] Use iterators over inst-pointers when using IRBuilder

This patch adds a two-argument SetInsertPoint method to IRBuilder that
takes a block/iterator instead of an instruction, and up

[NFC][RemoveDIs] Use iterators over inst-pointers when using IRBuilder

This patch adds a two-argument SetInsertPoint method to IRBuilder that
takes a block/iterator instead of an instruction, and updates many call
sites to use it. The motivating reason for doing this is given here [0],
we'd like to pass around more information about the position of debug-info
in the iterator object. That necessitates passing iterators around most of
the time.

[0] https://discourse.llvm.org/t/rfc-instruction-api-changes-needed-to-eliminate-debug-intrinsics-from-ir/68939

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

show more ...

[NFC][RemoveDIs] Prefer iterator-insertion over instructions

Continuing the patch series to get rid of debug intrinsics [0], instruction
insertion needs to be done with iterators rather than instruc

[NFC][RemoveDIs] Prefer iterator-insertion over instructions

Continuing the patch series to get rid of debug intrinsics [0], instruction
insertion needs to be done with iterators rather than instruction pointers,
so that we can communicate information in the iterator class. This patch
adds an iterator-taking insertBefore method and converts various call sites
to take iterators. These are all sites where such debug-info needs to be
preserved so that a stage2 clang can be built identically; it's likely that
many more will need to be changed in the future.

At this stage, this is just changing the spelling of a few operations,
which will eventually become signifiant once the debug-info bearing
iterator is used.

[0] https://discourse.llvm.org/t/rfc-instruction-api-changes-needed-to-eliminate-debug-intrinsics-from-ir/68939

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

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

[SCEVExpander] Change getRelatedExistingExpansion() to return bool (NFC)

This method is only used to determine whether a related expansion
exists, the actual value is unused. Clarify that by renamin

[SCEVExpander] Change getRelatedExistingExpansion() to return bool (NFC)

This method is only used to determine whether a related expansion
exists, the actual value is unused. Clarify that by renaming
get -> has and returning bool.

show more ...