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

Johnson, Nicholas Paul via llvm-dev llvm-dev at lists.llvm.org
Tue Nov 17 14:57:59 PST 2015

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.

Nick Johnson
D. E. Shaw Research

More information about the llvm-dev mailing list