[MachineVerifier] Confirm that both ends of a tied def/use are live together

[reames]

Summary

If we have a tied def, the tied use should also be live in the same live interval. The exception is that the use may be undef, in which case the def is dead, but we don't appear to enforce that tightly. For the moment, check only the non-undef case.

The need to not check physical registers here bothers me. I added this because without it, test/CodeGen/X86/segmented-stacks-dynamic.ll fails. However, I can't claim to understand why it's necessary.

From reading the existing code, I believe this is the intended invariant. I am not overly familiar with this code (or at least I wasn't until recently), so I would appreciate a careful review.

[reames]

Realized I'd only run the X86 tests. Went and ran all targets, and hit some failures on AMDGPU and SystemZ.

Failed Tests (8):

LLVM :: CodeGen/AMDGPU/GlobalISel/insertelement.ll
LLVM :: CodeGen/AMDGPU/indirect-addressing-si.ll
LLVM :: CodeGen/AMDGPU/insert_vector_dynelt.ll
LLVM :: CodeGen/AMDGPU/llvm.amdgcn.image.dim.ll
LLVM :: CodeGen/AMDGPU/r600.global_atomics.ll
LLVM :: CodeGen/SystemZ/asm-18.ll
LLVM :: CodeGen/SystemZ/fold-memory-op-impl.ll
LLVM :: CodeGen/SystemZ/int-cmp-44.ll

I think I'm going to need some input from someone knowledgeable of these backends. As an example, the SystemZ/int-cmp-44.ll failure looks like this:

• • Bad machine code: tied def w/o use in same live range ***
• function: f19
• basic block: %bb.0 entry (0x560f21608b18) [0B;112B)
• instruction: 48B %0:gr64bit = RISBG $noreg(tied-def 0), %2:gr64bit, 0, 190, 0, implicit-def dead $cc
• liverange: [48r,160r:0) 0@48r
• v. register: %0
• ValNo: 0 (def 48r)

That looks like an invalid use of tied defs to me, but is there something I'm missing here?

[arsenm]

Testcase? I also think this won't handle subregister indexes correctly. How does the x86 test fail?

llvm/lib/CodeGen/MachineVerifier.cpp

2732

I'm surprised this isn't checking readsReg instead of isDef

[skatkov]

In D97054#2574688, @reames wrote:

Realized I'd only run the X86 tests. Went and ran all targets, and hit some failures on AMDGPU and SystemZ.

Failed Tests (8):

LLVM :: CodeGen/AMDGPU/GlobalISel/insertelement.ll
LLVM :: CodeGen/AMDGPU/indirect-addressing-si.ll
LLVM :: CodeGen/AMDGPU/insert_vector_dynelt.ll
LLVM :: CodeGen/AMDGPU/llvm.amdgcn.image.dim.ll
LLVM :: CodeGen/AMDGPU/r600.global_atomics.ll
LLVM :: CodeGen/SystemZ/asm-18.ll
LLVM :: CodeGen/SystemZ/fold-memory-op-impl.ll
LLVM :: CodeGen/SystemZ/int-cmp-44.ll

I took a look into another failure CodeGen/AMDGPU/r600.global_atomics.ll
After Register Coalescing added verification check complains about subrange.

********** MACHINEINSTRS **********
# Machine code for function atomic_add_i32_offset: NoPHIs, TracksLiveness, TiedOpsRewritten

0B	bb.0.entry:
16B	  undef %4.sub0:r600_reg128 = MOV 1, 0, 0, 0, $alu_const, 0, 0, 0, 2058, 1, $pred_sel_off, 0, 0
32B	  %1:r600_treg32_x = ADD_INT 0, 0, 1, 0, 0, 0, $alu_const, 0, 0, 0, 2057, $alu_literal_x, 0, 0, 0, -1, 1, $pred_sel_off, 16, 0
80B	  dead %4:r600_reg128 = RAT_ATOMIC_ADD_NORET %4:r600_reg128(tied-def 0), %1:r600_treg32_x
96B	  RETURN

# End machine code for function atomic_add_i32_offset.

*** Bad machine code: tied def w/o use in same live range ***
- function:    atomic_add_i32_offset
- basic block: %bb.0 entry (0x1bcdbd8) [0B;112B)
- instruction: 80B	dead %4:r600_reg128 = RAT_ATOMIC_ADD_NORET %4:r600_reg128(tied-def 0), %1:r600_treg32_x
- liverange:   [80r,80d:1)  0@x 1@80r
- v. register: %4
- lanemask:    000000000000000E
- ValNo:       1 (def 80r)

Here,
16B undef %4.sub0:r600_reg128 = MOV 1, 0, 0, 0, $alu_const, 0, 0, 0, 2058, 1, $pred_sel_off, 0, 0
only subrange is defined.

[mtrofin]

llvm/lib/CodeGen/MachineVerifier.cpp

2749

Nit: you can just use Reg.isVirtual().

[reames]

In D97054#2574843, @arsenm wrote:

Testcase?

Not sure how to honestly. The whole idea is that an invalid live range should be impossible to construct, but that we want to catch it in verification if the register allocator does so.

I also think this won't handle subregister indexes correctly. How does the x86 test fail?

Can you expand on this a bit? I'm not sure what you mean by handling subregisters. What are the expectations for tied subregisters?

[arsenm]

In D97054#2579436, @reames wrote:

In D97054#2574843, @arsenm wrote:

Testcase?

Not sure how to honestly. The whole idea is that an invalid live range should be impossible to construct, but that we want to catch it in verification if the register allocator does so.

We have unit tests in unittests/MI/LiveIntervalTest

I also think this won't handle subregister indexes correctly. How does the x86 test fail?

Can you expand on this a bit? I'm not sure what you mean by handling subregisters. What are the expectations for tied subregisters?

I believe the tied operands should have the same subregister index (although I'm not sure this is enforced). The same rules should apply, just on the subrange

[reames]

Second attempt. Finally wrapped my head around the weird failures - they turned out to mostly be sub-register liveness cases. I'm definitely not clear on what the expected invariants are there, and intend to punt that part to someone who does in the future.

[reames]

In D97054#2580395, @arsenm wrote:

In D97054#2579436, @reames wrote:

In D97054#2574843, @arsenm wrote:

Testcase?

Not sure how to honestly. The whole idea is that an invalid live range should be impossible to construct, but that we want to catch it in verification if the register allocator does so.

We have unit tests in unittests/MI/LiveIntervalTest

I might be missing the obvious, but I don't see anything here to guide me on how to construct an intentionally malformed live interval and check for a verifier failure.

[arsenm]

In D97054#2601519, @reames wrote:

In D97054#2580395, @arsenm wrote:

In D97054#2579436, @reames wrote:

In D97054#2574843, @arsenm wrote:

Testcase?

Not sure how to honestly. The whole idea is that an invalid live range should be impossible to construct, but that we want to catch it in verification if the register allocator does so.

We have unit tests in unittests/MI/LiveIntervalTest

I might be missing the obvious, but I don't see anything here to guide me on how to construct an intentionally malformed live interval and check for a verifier failure.

Well there's not really much to guide creating properly constructed intervals either...

Theoretically you could just do something like LIS->getInterval(Reg).removeSegment(Start, WrongEnd)

llvm/lib/CodeGen/MachineVerifier.cpp

2749

Maybe should have a FIXME to handle physical registers too

2754

I don't see why being implicit would be a special case for this. Implicit operands still need to follow all of the liveness rules

2757

I think checking isUndef is usually wrong, since undef on a subregister def still reads the register. This should probably be .readsReg()

[arsenm]

Implicit operands aren't special. I also think the subreg handling is off

[reames]

Abandoning change. I still think this is valuable, but I think it's also clear I don't have the necessary background knowledge to drive this. If anyone else wants to pick this up, feel free.

llvm/lib/CodeGen/MachineVerifier.cpp

for (unsigned Idx = 0; Idx < MI->getNumDefs(); Idx++) {
       }
     }
 
     // TODO: verify we have properly encoded deopt arguments
   } break;
   }
 }
 
+static bool tiedOpsRewritten(const MachineFunction *MF) {
+  auto Prop = MachineFunctionProperties::Property::TiedOpsRewritten;
+  return MF->getProperties().hasProperty(Prop);
+}
+
 void
 MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
   const MachineInstr *MI = MO->getParent();
   const MCInstrDesc &MCID = MI->getDesc();
   unsigned NumDefs = MCID.getNumDefs();
   if (MCID.getOpcode() == TargetOpcode::PATCHPOINT)
     NumDefs = (MONum == 0 && MO->isReg()) ? NumDefs : 0;
 
case MachineOperand::MO_Register: {
     // Verify two-address constraints after the twoaddressinstruction pass.
     // Both twoaddressinstruction pass and phi-node-elimination pass call
     // MRI->leaveSSA() to set MF as NoSSA, we should do the verification after
     // twoaddressinstruction pass not after phi-node-elimination pass. So we
     // shouldn't use the NoSSA as the condition, we should based on
     // TiedOpsRewritten property to verify two-address constraints, this
     // property will be set in twoaddressinstruction pass.
     unsigned DefIdx;
-    if (MF->getProperties().hasProperty(
-            MachineFunctionProperties::Property::TiedOpsRewritten) &&
+    if (tiedOpsRewritten(MF) &&
         MO->isUse() && MI->isRegTiedToDefOperand(MONum, &DefIdx) &&
         Reg != MI->getOperand(DefIdx).getReg())
       report("Two-address instruction operands must be identical", MO, MONum);
 
     // Check register classes.
     unsigned SubIdx = MO->getSubReg();
 
     if (Register::isPhysicalRegister(Reg)) {
if (!MI) {
     report_context(*VNI);
     return;
   }
 
   if (Reg != 0) {
     bool hasDef = false;
     bool isEarlyClobber = false;
     for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
       if (!MOI->isReg() || !MOI->isDef())
         continue;
       if (Register::isVirtualRegister(Reg)) {
         if (MOI->getReg() != Reg)
           continue;
       } else {
         if (!Register::isPhysicalRegister(MOI->getReg()) ||
             !TRI->hasRegUnit(MOI->getReg(), Reg))
           continue;
       }
       if (LaneMask.any() &&
           (TRI->getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask).none())
         continue;
       hasDef = true;
       if (MOI->isEarlyClobber())
         isEarlyClobber = true;
+
+      if (tiedOpsRewritten(MF) && MOI->isTied() && Reg.isVirtual()) {
+        unsigned DefOpNum = std::distance(MI->operands_begin(), &*MOI);
+        unsigned UseOpNum = MI->findTiedOperandIdx(DefOpNum);
+        const MachineOperand &UseOp = MI->getOperand(UseOpNum);
+        // Both ends of a tied def must be the same interval.  Exceptions:
+        // - use is undef, implicit or noreg (not a real read)
+        // - live interval has subranges (purely because this is complicated
+        //   and we haven't implemented the precise check yet)
+        if (!UseOp.isUndef() && !UseOp.isImplicit() && UseOp.getReg() != 0 &&
+            LaneMask.none() && !LR.liveAt(VNI->def.getBaseIndex())) {
+          report("tied def w/o use in same live range", MI);
+          report_context(LR, Reg, LaneMask);
+          report_context(*VNI);
+        }
+      }
     }
 
     if (!hasDef) {
       report("Defining instruction does not modify register", MI);
       report_context(LR, Reg, LaneMask);
       report_context(*VNI);
     }