[NFC][DebugInfo] Switch more call-sites to using iterator-insertion (#124283)

To finalise the "RemoveDIs" work removing debug intrinsics, we're
updating call sites that insert instructions to use i

[NFC][DebugInfo] Switch more call-sites to using iterator-insertion (#124283)

To finalise the "RemoveDIs" work removing debug intrinsics, we're
updating call sites that insert instructions to use iterators instead.
This set of changes are those where it's not immediately obvious that
just calling getIterator to fetch an iterator is correct, and one or two
places where more than one line needs to change.

Overall the same rule holds though: iterators generated for the start of
a block such as getFirstNonPHIIt need to be passed into insert/move
methods without being unwrapped/rewrapped, everything else can use
getIterator.

show more ...

[NFC][DebugInfo] Use iterators for instruction insertion in more places (#124291)

As part of the "RemoveDIs" work to eliminate debug intrinsics, we're
replacing methods that use Instruction*'s as p

[NFC][DebugInfo] Use iterators for instruction insertion in more places (#124291)

As part of the "RemoveDIs" work to eliminate debug intrinsics, we're
replacing methods that use Instruction*'s as positions with iterators.
This patch changes some more complex call-sites, those crossing file
boundaries and where I've had to perform some minor rewrites.

show more ...

[NFC][DebugInfo] Use iterator moveBefore at many call-sites (#123583)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and sim

[NFC][DebugInfo] Use iterator moveBefore at many call-sites (#123583)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and similar feed into
instruction insertion positions. Call-sites where that's necessary were
updated a year ago; but to ensure some type safety however, we'd like to
have all calls to moveBefore use iterators.

This patch adds a (guaranteed dereferenceable) iterator-taking
moveBefore, and changes a bunch of call-sites where it's obviously safe
to change to use it by just calling getIterator() on an instruction
pointer. A follow-up patch will contain less-obviously-safe changes.

We'll eventually deprecate and remove the instruction-pointer
insertBefore, but not before adding concise documentation of what
considerations are needed (very few).

show more ...

[LSR][NFC] Use range-based `for` (#113889)

[Scalar] Remove unused includes (NFC) (#114645)

Identified with misc-include-cleaner.

[llvm][LSR] Fix where invariant on ScaledReg & Scale is violated (#112576)

Comments attached to the `ScaledReg` field of `struct Formula` explains
that, `ScaledReg` must be non-null when `Scale` is

[llvm][LSR] Fix where invariant on ScaledReg & Scale is violated (#112576)

Comments attached to the `ScaledReg` field of `struct Formula` explains
that, `ScaledReg` must be non-null when `Scale` is non-zero.

This fixes up a code path where this invariant is violated. Also, add an
assert to ensure this invariant holds true.

Without this patch, compiler aborts with the attached test case.

Fixes #76504

show more ...

[DebugInfo][LSR] Fix assertion failure salvaging IV with offset > 64 bits wide (#110979)

Fixes #110494

Fix LLVM_ENABLE_ABI_BREAKING_CHECKS macro check: use #if instead of #ifdef (#110938)

This macros is always defined: either 0 or 1. The correct pattern is to
use #if.

Re-apply #110185 with more f

Fix LLVM_ENABLE_ABI_BREAKING_CHECKS macro check: use #if instead of #ifdef (#110938)

This macros is always defined: either 0 or 1. The correct pattern is to
use #if.

Re-apply #110185 with more fixes for debug build with the ABI breaking
checks disabled.

show more ...

Reland "[LSR] Do not create duplicated PHI nodes while preserving LCSSA form" (#107380)

Motivating example: https://godbolt.org/z/eb97zrxhx
Here we have 2 induction variables in the loop: one is cor

Reland "[LSR] Do not create duplicated PHI nodes while preserving LCSSA form" (#107380)

Motivating example: https://godbolt.org/z/eb97zrxhx
Here we have 2 induction variables in the loop: one is corresponding to
i variable (add rdx, 4), the other - to res (add rax, 2). The second
induction variable can be removed by rewriteLoopExitValues() method
(final value of res at loop exit is unroll_iter * -2); however, this
doesn't happen because we have duplicated LCSSA phi nodes at loop exit:
```
; Preheader:
for.body.preheader.new: ; preds = %for.body.preheader
%unroll_iter = and i64 %N, -4
br label %for.body

; Loop:
for.body: ; preds = %for.body, %for.body.preheader.new
%lsr.iv = phi i64 [ %lsr.iv.next, %for.body ], [ 0, %for.body.preheader.new ]
%i.07 = phi i64 [ 0, %for.body.preheader.new ], [ %inc.3, %for.body ]
%inc.3 = add nuw i64 %i.07, 4
%lsr.iv.next = add nsw i64 %lsr.iv, -2
%niter.ncmp.3.not = icmp eq i64 %unroll_iter, %inc.3
br i1 %niter.ncmp.3.not, label %for.end.loopexit.unr-lcssa.loopexit, label %for.body, !llvm.loop !7

; Exit blocks
for.end.loopexit.unr-lcssa.loopexit: ; preds = %for.body
%inc.3.lcssa = phi i64 [ %inc.3, %for.body ]
%lsr.iv.next.lcssa11 = phi i64 [ %lsr.iv.next, %for.body ]
%lsr.iv.next.lcssa = phi i64 [ %lsr.iv.next, %for.body ]
br label %for.end.loopexit.unr-lcssa
```
rewriteLoopExitValues requires %lsr.iv.next value to have only 2 uses:
one in LCSSA phi node, the other - in induction phi node. Here we have 3
uses of this value because of duplicated lcssa nodes, so the transform
doesn't apply and leads to an extra add operation inside the loop. The
proposed solution is to accumulate inserted instructions that will
require LCSSA form update into SetVector and then call
formLCSSAForInstructions for this SetVector once, so the same
instructions don't process twice.

Reland fixes the issue with preserve-lcssa.ll test: it fails in the situation
when x86_64-unknown-linux-gnu target is unavailable in opt. The changes are
moved into separate duplicated-phis.ll test with explicit x86 target requirement
to fix bots which are not building this target.

show more ...

Revert "[LSR] Do not create duplicated PHI nodes while preserving LCSSA form" (#107666)

Reverts llvm/llvm-project#107380

Change is causing the test preserve-lcssa.ll to fail on at least 2 build

Revert "[LSR] Do not create duplicated PHI nodes while preserving LCSSA form" (#107666)

Reverts llvm/llvm-project#107380

Change is causing the test preserve-lcssa.ll to fail on at least 2 build
bots:
- https://lab.llvm.org/buildbot/#/builders/190/builds/5231
- https://lab.llvm.org/buildbot/#/builders/161/builds/1855

show more ...

[LSR] Do not create duplicated PHI nodes while preserving LCSSA form (#107380)

Motivating example: https://godbolt.org/z/eb97zrxhx
Here we have 2 induction variables in the loop: one is correspondi

[LSR] Do not create duplicated PHI nodes while preserving LCSSA form (#107380)

Motivating example: https://godbolt.org/z/eb97zrxhx
Here we have 2 induction variables in the loop: one is corresponding to
i variable (add rdx, 4), the other - to res (add rax, 2). The second
induction variable can be removed by rewriteLoopExitValues() method
(final value of res at loop exit is unroll_iter * -2); however, this
doesn't happen because we have duplicated LCSSA phi nodes at loop exit:
```
; Preheader:
for.body.preheader.new: ; preds = %for.body.preheader
%unroll_iter = and i64 %N, -4
br label %for.body

; Loop:
for.body: ; preds = %for.body, %for.body.preheader.new
%lsr.iv = phi i64 [ %lsr.iv.next, %for.body ], [ 0, %for.body.preheader.new ]
%i.07 = phi i64 [ 0, %for.body.preheader.new ], [ %inc.3, %for.body ]
%inc.3 = add nuw i64 %i.07, 4
%lsr.iv.next = add nsw i64 %lsr.iv, -2
%niter.ncmp.3.not = icmp eq i64 %unroll_iter, %inc.3
br i1 %niter.ncmp.3.not, label %for.end.loopexit.unr-lcssa.loopexit, label %for.body, !llvm.loop !7

; Exit blocks
for.end.loopexit.unr-lcssa.loopexit: ; preds = %for.body
%inc.3.lcssa = phi i64 [ %inc.3, %for.body ]
%lsr.iv.next.lcssa11 = phi i64 [ %lsr.iv.next, %for.body ]
%lsr.iv.next.lcssa = phi i64 [ %lsr.iv.next, %for.body ]
br label %for.end.loopexit.unr-lcssa
```
rewriteLoopExitValues requires %lsr.iv.next value to have only 2 uses:
one in LCSSA phi node, the other - in induction phi node. Here we have 3
uses of this value because of duplicated lcssa nodes, so the transform
doesn't apply and leads to an extra add operation inside the loop. The
proposed solution is to accumulate inserted instructions that will
require LCSSA form update into SetVector and then call
formLCSSAForInstructions for this SetVector once, so the same
instructions don't process twice.

show more ...

[LSR] Use computeConstantDifference()

This API is faster than getMinusSCEV() and a SCEVConstant cast.

[LSR] Split the -lsr-term-fold transformation into it's own pass (#104234)

This transformation doesn't actually use any of the internal state of
LSR and recomputes all information from SCEV. Split

[LSR] Split the -lsr-term-fold transformation into it's own pass (#104234)

This transformation doesn't actually use any of the internal state of
LSR and recomputes all information from SCEV. Splitting it out makes
it easier to test.

Note that long term I would like to write a version of this transform
which *is* integrated with LSR's solver, but if that happens, we'll
just delete the extra pass.

Integration wise, I switched from using TTI to using a pass configuration
variable. This seems slightly more idiomatic, and means we don't run
the extra logic on any target other than RISCV.

show more ...

[LSR] Fix matching vscale immediates (#100080)

Somewhat confusingly a `SCEVMulExpr` is a `SCEVNAryExpr`, so can have
> 2 operands. Previously, the vscale immediate matching did not check
the numbe

[LSR] Fix matching vscale immediates (#100080)

Somewhat confusingly a `SCEVMulExpr` is a `SCEVNAryExpr`, so can have
> 2 operands. Previously, the vscale immediate matching did not check
the number of operands of the `SCEVMulExpr`, so would ignore any
operands after the first two.

This led to incorrect codegen (and results) for ArmSME in IREE
(https://github.com/iree-org/iree), which sometimes addresses things
that are a `vscale * vscale` multiple away. The test added with this
change shows an example reduced from IREE. The second write should
be offset from the first `16 * vscale * vscale` (* 4 bytes), however,
previously LSR dropped the second vscale and instead offset the write by
`#4, mul vl`, which is an offset of `16 * vscale` (* 4 bytes).

show more ...

[DebugInfo][LoopStrengthReduce] Fix missing debug location updates (#97519)

Fix #97510 .

Note that, for the new phi instruction `NewPH`, which replaces the old
phi `PH` and the cast `ShadowUse`,

[DebugInfo][LoopStrengthReduce] Fix missing debug location updates (#97519)

Fix #97510 .

Note that, for the new phi instruction `NewPH`, which replaces the old
phi `PH` and the cast `ShadowUse`, I choose to propagate the debug
location of `PH` to it, because the cast is eliminated according to the
optimization semantics.

show more ...

[Transforms] Use range-based for loops (NFC) (#98725)

[LSR] Recognize vscale-relative immediates (#88124)

Extends LoopStrengthReduce to recognize immediates multiplied by vscale, and query the current target for whether they are legal offsets for memor

[LSR] Recognize vscale-relative immediates (#88124)

Extends LoopStrengthReduce to recognize immediates multiplied by vscale, and query the current target for whether they are legal offsets for memory operations or adds.

show more ...

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it does

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it doesn't exist...

`getModule()->getDataLayout()` is also a common (the most common?)
reason why code has to include the Module.h header.

show more ...

[LSR][AArch64] Optimize chain generation based on legal addressing modes (#94453)

LSR will generate chains of related instructions with a known increment
between them. With SVE, in the case of the

[LSR][AArch64] Optimize chain generation based on legal addressing modes (#94453)

LSR will generate chains of related instructions with a known increment
between them. With SVE, in the case of the test case, this can include
increments like 'vscale * 16 + 8'. The idea of this patch is if we have
a '+8' increment already calculated in the chain, we can generate a
(legal) '+ vscale*16' addressing mode from it, allowing us to use the
'[x16, #1, mul vl]' addressing mode instructions.

In order to do this we keep track of the known 'bases' when generating
chains in GenerateIVChain, checking for each if the accumulated
increment expression from the base neatly folds into a legal addressing
mode. If they do not we fall back to the existing LeftOverExpr, whether
it is legal or not.

This is mostly orthogonal to #88124, dealing with the generation of
chains as opposed to rest of LSR. The existing vscale addressing mode
work has greatly helped compared to the last time I looked at this,
allowing us to check that the addressing modes are indeed legal.

show more ...

[LSR] Provide TTI hook to enable dropping solutions deemed to be unprofitable (#89924)

<https://reviews.llvm.org/D126043> introduced a flag to drop solutions
if deemed unprofitable. As noted there,

[LSR] Provide TTI hook to enable dropping solutions deemed to be unprofitable (#89924)

<https://reviews.llvm.org/D126043> introduced a flag to drop solutions
if deemed unprofitable. As noted there, introducing a TTI hook enables
backends to individually opt into this behaviour.

This will be used by #89927.

show more ...

[LSR] Tweak debug output to always print initial cost

[TTI] Support scalable offsets in getScalingFactorCost (#88113)

Part of the work to support vscale-relative immediates in LSR.

[RemoveDIs][NFC] Rename DPValue -> DbgVariableRecord (#85216)

This is the major rename patch that prior patches have built towards.
The DPValue class is being renamed to DbgVariableRecord, which re

[RemoveDIs][NFC] Rename DPValue -> DbgVariableRecord (#85216)

This is the major rename patch that prior patches have built towards.
The DPValue class is being renamed to DbgVariableRecord, which reflects
the updated terminology for the "final" implementation of the RemoveDI
feature. This is a pure string substitution + clang-format patch. The
only manual component of this patch was determining where to perform
these string substitutions: `DPValue` and `DPV` are almost exclusively
used for DbgRecords, *except* for:

- llvm/lib/target, where 'DP' is used to mean double-precision, and so
appears as part of .td files and in variable names. NB: There is a
single existing use of `DPValue` here that refers to debug info, which
I've manually updated.
- llvm/tools/gold, where 'LDPV' is used as a prefix for symbol
visibility enums.

Outside of these places, I've applied several basic string
substitutions, with the intent that they only affect DbgRecord-related
identifiers; I've checked them as I went through to verify this, with
reasonable confidence that there are no unintended changes that slipped
through the cracks. The substitutions applied are all case-sensitive,
and are applied in the order shown:

```
DPValue -> DbgVariableRecord
DPVal -> DbgVarRec
DPV -> DVR
```

Following the previous rename patches, it should be the case that there
are no instances of any of these strings that are meant to refer to the
general case of DbgRecords, or anything other than the DPValue class.
The idea behind this patch is therefore that pure string substitution is
correct in all cases as long as these assumptions hold.

show more ...

[RemoveDIs][NFC] Move DPValue::filter -> filterDbgVars (#85208)

This patch changes DPValue::filter to be a non-member method
filterDbgVars. There are two reasons for this: firstly, the name of
DPV

[RemoveDIs][NFC] Move DPValue::filter -> filterDbgVars (#85208)

This patch changes DPValue::filter to be a non-member method
filterDbgVars. There are two reasons for this: firstly, the name of
DPValue is about to change to DbgVariableRecord, which will result in
every `for` loop that uses DPValue::filter to require a line break. This
is a small thing, but it makes the rename patch more difficult to
review, and is just generally more awkward for what is a fairly common
loop. Secondly, the intent is to later break up the DPValue class into
subclasses, at which point it would be better to have a non-member
function that allows template arguments for the cases we want to filter
with greater specificity.

show more ...

[LSR] Clear SCEVExpander before deleting phi nodes

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