llvm dev - Nov 2015 - LiveVariables clears the MO::IsDead bit from non-RA, physical regs, but never restores it. Bug?

I am observing poor instruction scheduling in my out-of-tree target.  The
problem is an over-constrained scheduling DAG.  In particular, the DAG includes
spurious output dependencies on physical, non-register-allocatable registers. 
MISched already includes code to avoid this problem.  However that code relies
on information clobbered by the earlier pass LiveVariables.

I wonder whether this is a bug in the LiveVariables pass and would appreciate
feedback.  Let me expand with a small example,

Suppose my target declares machine instruction type FOO that implicitly writes a
condition-code register named 'F_OVERFLOW'.  F_OVERFLOW is a physical
register and is not register-allocatable.  Consider this sequence of
instructions:

A:   %vreg4<def> = FOO %vreg1<kill>, 
%F_OVERFLOW<imp-def,dead>
B:   %vreg5<def> = FOO %vreg2<kill>, 
%F_OVERFLOW<imp-def,dead>
C:   %vreg6<def> = FOO %vreg3<kill>,  %F_OVERFLOW<imp-def>
...

When constructing a MISched DAG, I expect to see output dependencies (A -> C)
and (B -> C).  I assert that output dependency (A -> B) is spurious
because F_OVERFLOW is dead at B.  Indeed, ScheduleDAGInstrs::addPhysRegDeps
already includes a test for this case  (if MO.isDead()), confirming that the
developer intended to omit output dependencies on dead registers.
 
However, the LiveVariables pass clears the isDead flag from all operands that
reference F_OVERFLOW and does not reset those flags.  Without this information
MISched builds the pessimistic graph including the spurious output dependency (A
-> B).  I don't believe this is the intended behavior, and I'll cite
two comments to support that hypothesis:

(1) In method LiveVariables::runOnInstr, the comment "// Clear kill and
dead markers.  LV will recompute them" suggests that the kill, dead flags
will be valid after this pass completes.
(2) At the top of LiveVariables.h, "If a physical register is not register
allocatable, it is not tracked.  This is useful for things like the stack
pointer and condition codes."  This suggests that the pass cannot restore
the MachineOperand::IsKill and MachineOperand::IsDead bits for physical
non-register-allocatable registers.


I would appreciate any feedback.  If we decide this is buggy, I'll work on a
fix.


I have tested this on 3.6.1.  I have not yet tested on the 3.7 series as it may
take some effort to port my out-of-tree target.  However, I looked at the old
and new versions and I don't *think* any relevant code has changed.

Thanks,
Nick Johnson
D. E. Shaw Research

Following up, I've submitted a patch to phabricator for review:
http://reviews.llvm.org/D14875

Thanks,
Nick Johnson
D. E. Shaw Research
>-----Original Message-----
>From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
>Johnson, Nicholas Paul via llvm-dev
>Sent: Tuesday, November 17, 2015 5:58 PM
>To: llvm-dev at lists.llvm.org
>Subject: [llvm-dev] LiveVariables clears the MO::IsDead bit from non-RA,
>physical regs, but never restores it. Bug?
>
>I am observing poor instruction scheduling in my out-of-tree target.  The
>problem is an over-constrained scheduling DAG.  In particular, the DAG
>includes spurious output dependencies on physical, non-register-allocatable
>registers.  MISched already includes code to avoid this problem.  However
>that code relies on information clobbered by the earlier pass LiveVariables.
>
>I wonder whether this is a bug in the LiveVariables pass and would
>appreciate feedback.  Let me expand with a small example,
>
>Suppose my target declares machine instruction type FOO that implicitly
>writes a condition-code register named 'F_OVERFLOW'.  F_OVERFLOW is
a
>physical register and is not register-allocatable.  Consider this sequence
of
>instructions:
>
>A:   %vreg4<def> = FOO %vreg1<kill>, 
%F_OVERFLOW<imp-def,dead>
>B:   %vreg5<def> = FOO %vreg2<kill>, 
%F_OVERFLOW<imp-def,dead>
>C:   %vreg6<def> = FOO %vreg3<kill>,  %F_OVERFLOW<imp-def>
>...
>
>When constructing a MISched DAG, I expect to see output dependencies (A -
>> C) and (B -> C).  I assert that output dependency (A -> B) is
spurious because
>F_OVERFLOW is dead at B.  Indeed, ScheduleDAGInstrs::addPhysRegDeps
>already includes a test for this case  (if MO.isDead()), confirming that the
>developer intended to omit output dependencies on dead registers.
>
>However, the LiveVariables pass clears the isDead flag from all operands
that
>reference F_OVERFLOW and does not reset those flags.  Without this
>information MISched builds the pessimistic graph including the spurious
>output dependency (A -> B).  I don't believe this is the intended
behavior,
>and I'll cite two comments to support that hypothesis:
>
>(1) In method LiveVariables::runOnInstr, the comment "// Clear kill and
dead
>markers.  LV will recompute them" suggests that the kill, dead flags
will be
>valid after this pass completes.
>(2) At the top of LiveVariables.h, "If a physical register is not
register
>allocatable, it is not tracked.  This is useful for things like the stack
pointer
>and condition codes."  This suggests that the pass cannot restore the
>MachineOperand::IsKill and MachineOperand::IsDead bits for physical non-
>register-allocatable registers.
>
>
>I would appreciate any feedback.  If we decide this is buggy, I'll work
on a fix.
>
>
>I have tested this on 3.6.1.  I have not yet tested on the 3.7 series as it
may
>take some effort to port my out-of-tree target.  However, I looked at the
old
>and new versions and I don't *think* any relevant code has changed.
>
>Thanks,
>Nick Johnson
>D. E. Shaw Research
>
>
>
>
>_______________________________________________
>LLVM Developers mailing list
>llvm-dev at lists.llvm.org
>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

> On Nov 20, 2015, at 8:49 AM, Johnson, Nicholas Paul via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 
> Following up, I've submitted a patch to phabricator for review:
http://reviews.llvm.org/D14875
Thanks Nick, I agree with your analysis and fix. LiveVariables ideally should
have no impact on the MachintInstrs. In the long run, it should be removed from
the pipeline entirely, but the 2-address pass still requires it.

Andy
> Thanks,
> Nick Johnson
> D. E. Shaw Research
> 
>> -----Original Message-----
>> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
>> Johnson, Nicholas Paul via llvm-dev
>> Sent: Tuesday, November 17, 2015 5:58 PM
>> To: llvm-dev at lists.llvm.org
>> Subject: [llvm-dev] LiveVariables clears the MO::IsDead bit from
non-RA,
>> physical regs, but never restores it. Bug?
>> 
>> I am observing poor instruction scheduling in my out-of-tree target. 
The
>> problem is an over-constrained scheduling DAG.  In particular, the DAG
>> includes spurious output dependencies on physical,
non-register-allocatable
>> registers.  MISched already includes code to avoid this problem. 
However
>> that code relies on information clobbered by the earlier pass
LiveVariables.
>> 
>> I wonder whether this is a bug in the LiveVariables pass and would
>> appreciate feedback.  Let me expand with a small example,
>> 
>> Suppose my target declares machine instruction type FOO that implicitly
>> writes a condition-code register named 'F_OVERFLOW'. 
F_OVERFLOW is a
>> physical register and is not register-allocatable.  Consider this
sequence of
>> instructions:
>> 
>> A:   %vreg4<def> = FOO %vreg1<kill>, 
%F_OVERFLOW<imp-def,dead>
>> B:   %vreg5<def> = FOO %vreg2<kill>, 
%F_OVERFLOW<imp-def,dead>
>> C:   %vreg6<def> = FOO %vreg3<kill>, 
%F_OVERFLOW<imp-def>
>> ...
>> 
>> When constructing a MISched DAG, I expect to see output dependencies (A
-
>>> C) and (B -> C).  I assert that output dependency (A -> B) is
spurious because
>> F_OVERFLOW is dead at B.  Indeed, ScheduleDAGInstrs::addPhysRegDeps
>> already includes a test for this case  (if MO.isDead()), confirming
that the
>> developer intended to omit output dependencies on dead registers.
>> 
>> However, the LiveVariables pass clears the isDead flag from all
operands that
>> reference F_OVERFLOW and does not reset those flags.  Without this
>> information MISched builds the pessimistic graph including the spurious
>> output dependency (A -> B).  I don't believe this is the
intended behavior,
>> and I'll cite two comments to support that hypothesis:
>> 
>> (1) In method LiveVariables::runOnInstr, the comment "// Clear
kill and dead
>> markers.  LV will recompute them" suggests that the kill, dead
flags will be
>> valid after this pass completes.
>> (2) At the top of LiveVariables.h, "If a physical register is not
register
>> allocatable, it is not tracked.  This is useful for things like the
stack pointer
>> and condition codes."  This suggests that the pass cannot restore
the
>> MachineOperand::IsKill and MachineOperand::IsDead bits for physical
non-
>> register-allocatable registers.
>> 
>> 
>> I would appreciate any feedback.  If we decide this is buggy, I'll
work on a fix.
>> 
>> 
>> I have tested this on 3.6.1.  I have not yet tested on the 3.7 series
as it may
>> take some effort to port my out-of-tree target.  However, I looked at
the old
>> and new versions and I don't *think* any relevant code has changed.
>> 
>> Thanks,
>> Nick Johnson
>> D. E. Shaw Research
>> 
>> 
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev