[DebugInfo][InstrRef] Track values fused into stack spills

During register allocation, some instructions can have stack spills fused
into them. It means that when vregs are allocated on the stack we

[DebugInfo][InstrRef] Track values fused into stack spills

During register allocation, some instructions can have stack spills fused
into them. It means that when vregs are allocated on the stack we can
convert:

SETCCr %0
DBG_VALUE %0

to

SETCCm %stack.0
DBG_VALUE %stack.0

Unfortunately instruction referencing finds this harder: a store to the
stack doesn't have a specific operand number, therefore we don't substitute
the old operand for a new operand, and the location is dropped. This patch
implements a solution: just recognise the memory operand attached to an
instruction with a Special Number (TM), and record a substitution between
the old value and the new one.

This patch adds substitution code to InlineSpiller to record such fused
spills, and tracking in InstrRefBasedLDV to recognise such values, and
produce the value numbers for them. Everything to do with the movement of
stack-defined values is already handled in InstrRefBasedLDV.

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

show more ...

[DebugInfo][NFC] Avoid a use-after-free

This patch swaps two lines -- the CurSucc reference can be invalidated
by the call to DFS.push_back, therefore that should happen last. The
usual hat-tip to a

[DebugInfo][NFC] Avoid a use-after-free

This patch swaps two lines -- the CurSucc reference can be invalidated
by the call to DFS.push_back, therefore that should happen last. The
usual hat-tip to asan for catching this.

This patch also swaps an ealier call to ToAdd.insert and DFS.push_back,
where a stable iterator (from successors()) is being used. This isn't
strictly necessary, but is good for consistency and avoiding readers
asking themselves why the two code portions have a different order.

show more ...

[DebugInfo][Instr] Track subregisters across stack spills/restores

Sometimes we generate code that writes to a subregister, then spills /
restores a super-register to the stack, for example:

$e

[DebugInfo][Instr] Track subregisters across stack spills/restores

Sometimes we generate code that writes to a subregister, then spills /
restores a super-register to the stack, for example:

$eax = MOV32ri 0
MOV64mr $rsp, 1, $noreg, 16, $noreg, $rax
$rcx = MOV64rm $rsp, 1, $noreg, 8, $noreg

This patch takes a different approach: it adds another index to
MLocTracker that identifies a size/offset within a stack slot. A location
on the stack is then a pari of {FrameIndex, SlotNum}. Spilling and
restoring now involves pairing up the src/dest register numbers, and the
dest/src stack position to be transferred to/from. Location coverage
improves as a result, compile-time performance decreases, alas.

One limitation is that if a PHI occurs inside a stack slot:

DBG_PHI %stack.0, 1

We don't know how large the resulting value is, and so might have
difficulty picking which value to use. DBG_PHI might need to be augmented
in the future with such a size.

Unit tests added ensure that spills and restores correctly transfer to
positions in the Location => Value map, and that different register classes
written to the stack will correctly clobber all other positions in the
stack slot.

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

show more ...

[DebugInfo][InstrRef] Add unit tests for transfer-function building

This patch adds some unit tests for the machine-location transfer-function
building parts of InstrRefBasedLDV: i.e., test that if

[DebugInfo][InstrRef] Add unit tests for transfer-function building

This patch adds some unit tests for the machine-location transfer-function
building parts of InstrRefBasedLDV: i.e., test that if we feed some MIR
into the transfer-function building code, does it create the correct
transfer function.

There are a number of minor defects that get corrected in the process:
* The unit test was selecting the x86 (i.e. 32 bit) backend rather than
x86_64's 64 bit backend,
* COPY instructions weren't actually having their subregister values
correctly represented in the transfer function. Subregisters were being
defined by the COPY, rather than taking the value in the source register.
* SP aliases were at risk of being clobbered, if an SP subregister was
clobbered.

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

show more ...

[DebugInfo][InstrRef] Track a single variable at a time

Here's another performance patch for InstrRefBasedLDV: rather than
processing all variable values in a scope at a time, instead, process one
v

[DebugInfo][InstrRef] Track a single variable at a time

Here's another performance patch for InstrRefBasedLDV: rather than
processing all variable values in a scope at a time, instead, process one
variable at a time. The benefits are twofold:
* It's easier to reason about one variable at a time in your mind,
* It improves performance, apparently from increased locality.

The downside is that the value-propagation code gets indented one level
further, plus there's some churn in the unit tests.

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

show more ...

[DebugInfo][InstrRef] Avoid un-necessary densemap copies and comparisons

This is purely a performance patch: InstrRefBasedLDV used to use three
DenseMaps to store variable values, two for long term

[DebugInfo][InstrRef] Avoid un-necessary densemap copies and comparisons

This is purely a performance patch: InstrRefBasedLDV used to use three
DenseMaps to store variable values, two for long term storage and one as a
working set. This patch eliminates the working set, and updates the long
term storage in place, thus avoiding two DenseMap comparisons and two
DenseMap assignments, which can be expensive.

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

show more ...

Fix signed/unsigned comparison after b5426ced71280

gcc11 warns that this counter causes a signed/unsigned comaprison when it's
later compared with a SmallVector::difference_type. gcc appears to be
c

Fix signed/unsigned comparison after b5426ced71280

gcc11 warns that this counter causes a signed/unsigned comaprison when it's
later compared with a SmallVector::difference_type. gcc appears to be
correct, clang does not warn one way or the other.

show more ...

[DebugInfo][InstrRef] Place variable-values PHI using LLVM utilities

This patch is very similar to D110173 / a3936a6c19c, but for variable
values rather than machine values. This is for the second i

[DebugInfo][InstrRef] Place variable-values PHI using LLVM utilities

This patch is very similar to D110173 / a3936a6c19c, but for variable
values rather than machine values. This is for the second instr-ref
problem, calculating the correct variable value on entry to each block.
The previous lattice based implementation was broken; we now use LLVMs
existing PHI placement utilities to work out where values need to merge,
then eliminate un-necessary ones through value propagation.

Most of the deletions here happen in vlocJoin: it was trying to pick a
location for PHIs to happen in, badly, leading to an infinite loop in the
MIR test added, where it would repeatedly switch between register
locations. The new approach is simpler: either PHIs can be eliminated, or
they can't, and the location of the value is a different problem.

Various bits and pieces move to the header so that they can be tested in
the unit tests. The DbgValue class grows a "VPHI" kind to represent
variable value PHIS that haven't been eliminated yet.

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

show more ...

[DebugInfo][InstrRef] Only calculate IDF for reg units

In D110173 we start using the existing LLVM IDF calculator to place PHIs as
we reconstruct an SSA form of machine-code program. Sadly that's sl

[DebugInfo][InstrRef] Only calculate IDF for reg units

In D110173 we start using the existing LLVM IDF calculator to place PHIs as
we reconstruct an SSA form of machine-code program. Sadly that's slower
than the old (but broken) way, this patch attempts to recover some of that
performance.

The key observation: every time we def a register, we also have to def it's
register units. If we def'd $rax, in the current implementation we
independently calculate PHI locations for {al, ah, ax, eax, hax, rax}, and
they will all have the same PHI positions. Instead of doing that, we can
calculate the PHI positions for {al, ah} and place PHIs for any aliasing
registers in the same positions. Any def of a super-register has to def
the unit, and vice versa, so this is sound. It cuts down the SSA placement
we need to do significantly.

This doesn't work for stack slots, or registers we only ever read, so place
PHIs normally for those. LiveDebugValues choses to ignore writes to SP at
calls, and now have to ignore writes to SP register units too.

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

show more ...

Follow up a3936a6c19c to work around an old compiler bug

Old versions of gcc want template specialisations to happen within the
namespace where the template lives; this is still present in gcc 5.1,

Follow up a3936a6c19c to work around an old compiler bug

Old versions of gcc want template specialisations to happen within the
namespace where the template lives; this is still present in gcc 5.1, which
we officially support, so it has to be worked around.

show more ...

[DebugInfo][InstrRef] Use PHI placement utilities for machine locations

InstrRefBasedLDV used to try and determine which values are in which
registers using a lattice approach; however this is hard

[DebugInfo][InstrRef] Use PHI placement utilities for machine locations

InstrRefBasedLDV used to try and determine which values are in which
registers using a lattice approach; however this is hard to understand, and
broken in various ways. This patch replaces that approach with a standard
SSA approach using existing LLVM utilities. PHIs are placed at dominance
frontiers; value propagation then eliminates un-necessary PHIs.

This patch also adds a bunch of unit tests that should cover many of the
weirder forms of control flow.

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

show more ...

Scatter NDEBUG to fix after 838b4a533e6

These "dump" methods call into MachineOperand::dump, which doesn't exist
with NDEBUG, thus we croak. Disable LiveDebugValues dump methods when
NDEBUG is turne

Scatter NDEBUG to fix after 838b4a533e6

These "dump" methods call into MachineOperand::dump, which doesn't exist
with NDEBUG, thus we croak. Disable LiveDebugValues dump methods when
NDEBUG is turned on to avoid this.

show more ...

[DebugInfo][NFC] Move LiveDebugValues class to header

This patch shifts the InstrRefBasedLDV class declaration to a header.
Partially because it's already massive, but mostly so that I can start
wri

[DebugInfo][NFC] Move LiveDebugValues class to header

This patch shifts the InstrRefBasedLDV class declaration to a header.
Partially because it's already massive, but mostly so that I can start
writing some unit tests for it. This patch also adds the boilerplate for
said unit tests.

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

show more ...

[MachineInstr] Move MIParser's DBG_VALUE RegState::Debug invariant into MachineInstr::addOperand

Based on the reasoning of D53903, register operands of DBG_VALUE are
invariably treated as RegState::

[MachineInstr] Move MIParser's DBG_VALUE RegState::Debug invariant into MachineInstr::addOperand

Based on the reasoning of D53903, register operands of DBG_VALUE are
invariably treated as RegState::Debug operands. This change enforces
this invariant as part of MachineInstr::addOperand so that all passes
emit this flag consistently.

RegState::Debug is inconsistently set on DBG_VALUE registers throughout
LLVM. This runs the risk of a filtering iterator like
MachineRegisterInfo::reg_nodbg_iterator to process these operands
erroneously when not parsed from MIR sources.

This issue was observed in the development of the llvm-mos fork which
adds a backend that relies on physical register operands much more than
existing targets. Physical RegUnit 0 has the same numeric encoding as
$noreg (indicating an undef for DBG_VALUE). Allowing debug operands into
the machine scheduler correlates $noreg with RegUnit 0 (i.e. a collision
of register numbers with different zero semantics). Eventually, this
causes an assert where DBG_VALUE instructions are prohibited from
participating in live register ranges.

Reviewed By: MatzeB, StephenTozer

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

show more ...

[DebugInfo][InstrRef] Track all of DBG_PHIs operands

An important part of the instruction referencing solution is that we
identify all the registers that values move between before we then compute
a

[DebugInfo][InstrRef] Track all of DBG_PHIs operands

An important part of the instruction referencing solution is that we
identify all the registers that values move between before we then compute
an SSA-like function from the machine code, and from the variable
intrinsics. DBG_PHIs weren't causing all the subregisters of their operands
to be tracked; this patch forces that to happen.

The practical implications were that not enough space is allocated for
storing values when analysing the function -- asan will crash on the
attached test case with an unpatched compiler. Non-asan llc's will produce
a DBG_VALUE $noreg, where it should be $dil.

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

show more ...

[DebugInfo][InstrRef] Correctly ignore DBG_VALUE_LIST in InstrRef mode

This patch makes InstrRefBasedLDV "safe" to work with DBG_VALUE_LISTs. It
doesn't actually interpret them, but it recognises th

[DebugInfo][InstrRef] Correctly ignore DBG_VALUE_LIST in InstrRef mode

This patch makes InstrRefBasedLDV "safe" to work with DBG_VALUE_LISTs. It
doesn't actually interpret them, but it recognises that they specify
variable locations and avoids propagating false locations, which is better
than the current state. Observe the attached tes

* We avoid propagating DBG_VALUE_LISTs into successor blocks, as they're
not "currently" supported,
* We don't propagate other variable locations across DBG_VALUE_LISTs,
because we know that the variable location is terminated by the
DBG_VALUE_LIST.

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

show more ...

[DebugInfo][InstrRef] Remove a faulty assertion

This patch removes an assertion, and adds a regression test showing why the
assertion is broken.

For context, LocIdx is a key/index number for machin

[DebugInfo][InstrRef] Remove a faulty assertion

This patch removes an assertion, and adds a regression test showing why the
assertion is broken.

For context, LocIdx is a key/index number for machine locations, so that we
can describe locations as a single integer and ignore whether they're on
the stack, in registers or otherwise. Back when InstrRefBasedLDV was added,
I happened to bake in a "special" zero number for various reasons, which
Vedant identified as undesirable in this review comment:
https://reviews.llvm.org/D83047#inline-765495 . I subsequently removed that
special zero number, but it looks like I didn't delete this assertion at
the time, which assumes that a zero LocIdx is invalid.

The attached test shows that this assertion is reachable on valid code --
on x86 $rsp always gets the LocIdx number zero, and if you transfer a
variable value into it, InstrRefBasedLDV crashes on that assertion. The
code might be a bit wild to be storing variables to $rsp like that, however
we shouldn't crash on it.

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

show more ...

[DebugInfo][InstrRef] Honour too-much-debug-info cutouts

This reapplies 54a61c94f93, its follow up in 547b712500e, which were
reverted 95fe61e63954. Original commit message:

VarLoc based LiveDebugV

[DebugInfo][InstrRef] Honour too-much-debug-info cutouts

This reapplies 54a61c94f93, its follow up in 547b712500e, which were
reverted 95fe61e63954. Original commit message:

VarLoc based LiveDebugValues will abandon variable location propagation if
there are too many blocks and variable assignments in the function. If it
didn't, and we had (say) 1000 blocks and 1000 variables in scope, we'd end
up with 1 million DBG_VALUEs just at the start of blocks.

Instruction-referencing LiveDebugValues should honour this limitation too
(because the same limitation applies to it). Hoist the relevant command
line options into LiveDebugValues.cpp and pass it down into the
implementation classes as an argument to ExtendRanges. I've duplicated all
the run-lines in live-debug-values-cutoffs.mir to have an
instruction-referencing flavour.

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

show more ...

Revert 54a61c94f93 and its follow up in 547b712500e

These were part of D107823, however asan has found something excitingly
wrong happening:

https://lab.llvm.org/buildbot/#/builders/5/builds/10543

Revert 54a61c94f93 and its follow up in 547b712500e

These were part of D107823, however asan has found something excitingly
wrong happening:

https://lab.llvm.org/buildbot/#/builders/5/builds/10543/steps/13/logs/stdio

show more ...

Suppress signedness-comparison warning

This is a follow-up to 54a61c94f93.

[DebugInfo][InstrRef] Honour too-much-debug-info cutouts

VarLoc based LiveDebugValues will abandon variable location propagation if
there are too many blocks and variable assignments in the function

[DebugInfo][InstrRef] Honour too-much-debug-info cutouts

VarLoc based LiveDebugValues will abandon variable location propagation if
there are too many blocks and variable assignments in the function. If it
didn't, and we had (say) 1000 blocks and 1000 variables in scope, we'd end
up with 1 million DBG_VALUEs just at the start of blocks.

Instruction-referencing LiveDebugValues should honour this limitation too
(because the same limitation applies to it). Hoist the relevant command
line options into LiveDebugValues.cpp and pass it down into the
implementation classes as an argument to ExtendRanges. I've duplicated all
the run-lines in live-debug-values-cutoffs.mir to have an
instruction-referencing flavour.

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

show more ...

[X86] Return src/dest register from stack spill/restore recogniser

LLVM provides target hooks to recognise stack spill and restore
instructions, such as isLoadFromStackSlot, and it also provides pos

[X86] Return src/dest register from stack spill/restore recogniser

LLVM provides target hooks to recognise stack spill and restore
instructions, such as isLoadFromStackSlot, and it also provides post frame
elimination versions such as isLoadFromStackSlotPostFE. These are supposed
to return the store-source and load-destination registers; unfortunately on
X86, the PostFE recognisers just return "1", apparently to signify "yes
it's a spill/load". This patch alters the hooks to correctly return the
store-source and load-destination registers:

This is really useful for debug-info as we it helps follow variable values
as they move on/off the stack. There should be no codegen changes: the only
other users of these PostFE target hooks are MachineInstr::getRestoreSize
and MachineInstr::getSpillSize, which don't attempt to interpret the
returned register location.

While we're here, delete the (InstrRef) LiveDebugValues heuristic that
tries to find the spill source register by looking for a killed reg -- we
should be able to rely on the target hooks for that. This involves
temporarily turning off a n InstrRef LivedDebugValues test on aarch64
(patch to re-enable it is in D104521).

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

show more ...

[Debug-info][InstrRef] Avoid an unnecessary map ordering

We keep a record of substitutions between debug value numbers post-isel,
however we never actually look them up until the end of compilation.

[Debug-info][InstrRef] Avoid an unnecessary map ordering

We keep a record of substitutions between debug value numbers post-isel,
however we never actually look them up until the end of compilation. As a
result, there's nothing gained by the collection being a std::map. This
patch downgrades it to being a vector, that's then sorted at the end of
compilation in LiveDebugValues.

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

show more ...

[DebugInfo][InstrRef][2/4] Use subreg substitutions in LiveDebugValues

Added in 47c3fe2a22cf, we sometimes need to describe a variable value
substitution with a subregister qualifier, to say that "t

[DebugInfo][InstrRef][2/4] Use subreg substitutions in LiveDebugValues

Added in 47c3fe2a22cf, we sometimes need to describe a variable value
substitution with a subregister qualifier, to say that "the value is the
lower 32 bits of this 64 bit register def" for example. That then needs
support during LiveDebugValues to interpret the subregister qualifiers,
which is what this patch adds.

Whenever we encounter a DBG_INSTR_REF and find its value by using a
substitution, collect any subregister qualifiers seen. Then, accumulate the
effects of the qualifiers to work out what offset and what size should be
extracted from the defined register. Finally, for the target ValueIDNum,
extract whatever subregister is in the correct position

Currently, describing a subregister field of a larger value that has been
spilt to the stack, is unimplemented.

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

show more ...

[DebugInfo][InstrRef][1/4] Support transformations that widen values

Very late in compilation, backends like X86 will perform optimisations like
this:

$cx = MOV16rm $rax, ...
->
$rcx =

[DebugInfo][InstrRef][1/4] Support transformations that widen values

Very late in compilation, backends like X86 will perform optimisations like
this:

$cx = MOV16rm $rax, ...
->
$rcx = MOV64rm $rax, ...

Widening the load from 16 bits to 64 bits. SEeing how the lower 16 bits
remain the same, this doesn't affect execution. However, any debug
instruction reference to the defined operand now refers to a 64 bit value,
nto a 16 bit one, which might be unexpected. Elsewhere in codegen, there's
often this pattern:

CALL64pcrel32 @foo, implicit-def $rax
%0:gr64 = COPY $rax
%1:gr32 = COPY %0.sub_32bit

Where we want to refer to the definition of $eax by the call, but don't
want to refer the copies (they don't define values in the way
LiveDebugValues sees it). To solve this, add a subregister field to the
existing "substitutions" facility, so that we can describe a field within
a larger value definition. I would imagine that this would be used most
often when a value is widened, and we need to refer to the original,
narrower definition.

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

show more ...