RFC: LiveIntervalCalc: Always split separate components

[foad]

Summary

With D129208 applied but without this patch,
CodeGen/AMDGPU/subreg-intervals.mir fails machine verification
immediately after running LiveIntervals:

# Machine code for function test0: NoPHIs

0B	bb.0:
16B	  S_NOP 0, implicit-def %0:sreg_64
32B	  S_NOP 0, implicit %0:sreg_64
48B	  S_NOP 0, implicit-def undef %0.sub0:sreg_64
64B	  S_NOP 0, implicit %0:sreg_64

# End machine code for function test0.

*** Bad machine code: Multiple connected components in live interval ***
- function:    test0
- interval:    %0 [16r,32r:0)[48r,64r:1) 0@16r 1@48r  L000000000000000C [16r,32r:0) 0@16r  L0000000000000003 [16r,32r:1)[48r,64r:0) 0@48r 1@16r  weight:0.000000e+00

[foad]

I need some help understanding the background here. Why does LiveIntervals::computeVirtRegs only call splitSeparateComponents if it detected dead defs in a live interval? Is this some artifact of the way MIR is typically constructed by instruction selection?

If you write MIR by hand you can easily construct cases where LiveIntervalCalc leaves multiple connected components that need to be split, e.g.:

S_NOP 0, implicit-def %0
S_NOP 0, implicit %0
S_NOP 0, implicit-def %0
S_NOP 0, implicit %0

Is this something that never normally occurs in MIR? MachineVerifier does not complain about it.

[foad]

Note to self: some of the background is in D21189 and D68666 and D67448.

[arsenm]

This is also one of the difficulties I ran into while trying to make llvm-reduce MIR support use LiveIntervals

[foad]

Alternatively I could just remove this case from test/CodeGen/AMDGPU/subreg-intervals.mir:

---
name: test0
registers:
  - { id: 0, class: sreg_64 }
body: |
  bb.0:
    S_NOP 0, implicit-def %0
    S_NOP 0, implicit %0

    S_NOP 0, implicit-def undef %0.sub0
    S_NOP 0, implicit %0
...

I have gone back to the original commit of D21189 and confirmed that this test case passes both before and after that commit, so it wasn't testing any new functionality. @kparzysz would you be happy with that?

[qcolombet]

I need some help understanding the background here. Why does LiveIntervals::computeVirtRegs only call splitSeparateComponents if it detected dead defs in a live interval? Is this some artifact of the way MIR is typically constructed by instruction selection?

I think, yes, it's just what a regular compilation flow is supposed to produce.

If you check the machine verifier, you'll see that the "separate component" property is checked, hence the different passes are not supposed to break that.

Having something more robust here sounds reasonable, I'm just worried about the compile time impact of this change. (I don't remember if splitting components is expensive.)

Is this something that never normally occurs in MIR? MachineVerifier does not complain about it.

That's strange, the verifier is supposed to catch this kind of things at https://github.com/llvm/llvm-project/blob/29dc47a9eeeb2e080170109e3e2fb3cd5aad58d2/llvm/lib/CodeGen/MachineVerifier.cpp#L3333

[foad]

Is this something that never normally occurs in MIR? MachineVerifier does not complain about it.

That's strange, the verifier is supposed to catch this kind of things at https://github.com/llvm/llvm-project/blob/29dc47a9eeeb2e080170109e3e2fb3cd5aad58d2/llvm/lib/CodeGen/MachineVerifier.cpp#L3333

Right, it does complain about the LiveIntervals, but I thought that indicated that the LiveIntervals were not computed correctly, not that the underlying MIR was malformed. If you don't have LiveIntervals, the verifier does not complain about the MIR.

[foad]

Alternatively I could just remove this case from test/CodeGen/AMDGPU/subreg-intervals.mir:

If the verification error indicates malformed MIR, not just malformed LiveIntervals, then I am even more convinced that this is the right solution. I have already incorporated it into D129208.

[qcolombet]

Right, it does complain about the LiveIntervals, but I thought that indicated that the LiveIntervals were not computed correctly, not that the underlying MIR was malformed.

Fair point. I guess we're back to your original question: can the compiler actually produce this kind of MIR that happens to be ill-formed for LiveIntervals computation?

I don't believe it can, but if fixing that makes our life easier (e.g., by unblocking some llvm-reduce workflow) without noticeable compile time impact, I think we should do it.

[arsenm]

The MIR is a standalone thing with rules on its own independent of the LiveIntervals. LiveIntervals is supposed to be a reflection of the MIR, it doesn't make sense to have restrictions on the MIR because of LiveIntervals. The implication there is some MIR which exists that's valid under -O0 but not with LiveIntervals suggests brokenness

[foad]

In D151227#4369508, @arsenm wrote:

The MIR is a standalone thing with rules on its own independent of the LiveIntervals. LiveIntervals is supposed to be a reflection of the MIR, it doesn't make sense to have restrictions on the MIR because of LiveIntervals. The implication there is some MIR which exists that's valid under -O0 but not with LiveIntervals suggests brokenness

A slightly different way of looking at the current situation: MIR *does* have rules forbidding multiple disconnected definitions, but MachineVerifier currently does not enforce them unless it has access to LiveIntervals.

In any case I removed the offending test as part of D129208, so I'm not planning to pursue this patch. Feel free to pick it up if you want.

llvm/lib/CodeGen/LiveIntervals.cpp

 }
 
 void LiveIntervals::computeVirtRegs() {
   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
     Register Reg = Register::index2VirtReg(i);
     if (MRI->reg_nodbg_empty(Reg))
       continue;
     LiveInterval &LI = createEmptyInterval(Reg);
-    bool NeedSplit = computeVirtRegInterval(LI);
-    if (NeedSplit) {
-      SmallVector<LiveInterval*, 8> SplitLIs;
-      splitSeparateComponents(LI, SplitLIs);
-    }
-  }
-}
+    computeVirtRegInterval(LI);
 
 void LiveIntervals::computeRegMasks() {
   RegMaskBlocks.resize(MF->getNumBlockIDs());
 
   // Find all instructions with regmask operands.
   for (const MachineBasicBlock &MBB : *MF) {
     std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
     RMB.first = RegMaskSlots.size();