LiveIntervalAnalysis: Avoid multiple connected liveness components

[MatzeB]

Summary

We may have subregister defs which are unused but not discovered and
cleaned up prior to liveness analysis. This creates multiple connected
components in the resultsing live range which are forbidden in the
MachineVerifier because they would unnecesarily constrain the register
allocation. Rewrite those dead definitions to define a newly created
virtual register.

[qcolombet]

Hi Matthias,

Nice catch!

Right now, this is on the users of shrinkUses to fix the multi component splitting.
The rationale, I think :), is that we want the users to be aware of the any virtual registers that would be created. This is not the case in that patch.

The bottom line is I believe shrinkToUses should return true in those situations and we should fix the users of shrinkToUses, if need to.
Indeed, I, for instance, guess that the register coalescer would already do the right thing if we return true, since it creates new virtual registers, and wouldn’t have to fix it.

What do you think?

Cheers,
-Quentin

[MatzeB]

In D13035#250321, @qcolombet wrote:

Hi Matthias,

Nice catch!

Right now, this is on the users of shrinkUses to fix the multi component splitting.
The rationale, I think :), is that we want the users to be aware of the any virtual registers that would be created. This is not the case in that patch.

The bottom line is I believe shrinkToUses should return true in those situations and we should fix the users of shrinkToUses, if need to.
Indeed, I, for instance, guess that the register coalescer would already do the right thing if we return true, since it creates new virtual registers, and wouldn’t have to fix it.

What do you think?

computeDeadValues() is also used during the initial Liveness computation in which the return value is not checked (because we cannot have deadPhi values at that place). Seeing on the other hand that the creation of the new VReg is trivial and in this case faster because we know exactly that we will only have a single dead definition I decided to do the LiveInterval creation inline.

I also checked all places where shrinkToUses() is called to ensure they can deal with the fact that additional LiveIntervals may have been created.

[qcolombet]

I guess if it is needed we could have an additional optional parameter (like SmallVectorImpl<unsigned> *) to return the virtual registers created.
Seems like it is not needed for now.

The thing that I do not like is that it seems to me that the handling of multi component is not homogeneous between the non-subregister and the subregister case.

computeDeadValues() is also used during the initial Liveness computation in which the return value is not checked (because we cannot have deadPhi values at that place).

How hard would it be to account for the returned value?

Thanks,
-Quentin

[MatzeB]

New version which uses the existing mechanisms to split the live interval into multiple components.

[qcolombet]

LGTM.

Cheers,
-Quentin

include/llvm/CodeGen/LiveIntervalAnalysis.h

LiveInterval::Segment addSegmentToEndOfBlock(unsigned reg,
                                                  MachineInstr* startInst);
 
     /// After removing some uses of a register, shrink its live range to just
     /// the remaining uses. This method does not compute reaching defs for new
     /// uses, and it doesn't remove dead defs.
     /// Dead PHIDef values are marked as unused. New dead machine instructions
     /// are added to the dead vector. Returns true if the interval may have been
     /// separated into multiple connected components.
+    /// May create new VRegs/LiveIntervals with a single dead def to break apart
+    /// separated dead subregister defs.
     bool shrinkToUses(LiveInterval *li,
                       SmallVectorImpl<MachineInstr*> *dead = nullptr);
 
     /// Specialized version of
     /// shrinkToUses(LiveInterval *li, SmallVectorImpl<MachineInstr*> *dead)
     /// that works on a subregister live range and only looks at uses matching
     /// the lane mask of the subregister range.
     /// This may leave the subrange empty which needs to be cleaned up with
private:
 
     /// Walk the values in @p LI and check for dead values:
     /// - Dead PHIDef values are marked as unused.
     /// - Dead operands are marked as such.
     /// - Completely dead machine instructions are added to the @p dead vector
     ///   if it is not nullptr.
     /// Returns true if any PHI value numbers have been removed which may
     /// have separated the interval into multiple connected components.
+    /// May create new VRegs/LiveIntervals with a single dead def to break apart
+    /// separated dead subregister defs.
     bool computeDeadValues(LiveInterval &LI,
                            SmallVectorImpl<MachineInstr*> *dead);
 
     static LiveInterval* createInterval(unsigned Reg);
 
     void printInstrs(raw_ostream &O) const;
     void dumpInstrs() const;
 

lib/CodeGen/LiveIntervalAnalysis.cpp

bool LiveIntervals::shrinkToUses(LiveInterval *li,
   li->segments.swap(NewLR.segments);
 
   // Handle dead values.
   bool CanSeparate = computeDeadValues(*li, dead);
   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
   return CanSeparate;
 }
 
+static void removeDeadDef(LiveInterval &LI, LiveRange::iterator I) {
+  assert(SlotIndex::isSameInstr(I->start, I->end));
+
+  SlotIndex Def = I->start;
+  for (LiveInterval::SubRange &SR : LI.subranges()) {
+    LiveRange::iterator SRI = SR.FindSegmentContaining(Def);
+    if (SRI != SR.end()) {
+      assert(SlotIndex::isSameInstr(SRI->start, SRI->end));
+      SRI->valno->markUnused();
+      SR.removeSegment(SRI);
+    }
+  }
+  LI.removeEmptySubRanges();
+
+  I->valno->markUnused();
+  LI.removeSegment(I);
+}
+
 bool LiveIntervals::computeDeadValues(LiveInterval &LI,
                                       SmallVectorImpl<MachineInstr*> *dead) {
   bool PHIRemoved = false;
   for (auto VNI : LI.valnos) {
     if (VNI->isUnused())
       continue;
     SlotIndex Def = VNI->def;
     LiveRange::iterator I = LI.FindSegmentContaining(Def);
     assert(I != LI.end() && "Missing segment for VNI");
 
     // Is the register live before? Otherwise we may have to add a read-undef
     // flag for subregister defs.
-    if (MRI->shouldTrackSubRegLiveness(LI.reg)) {
+    bool DeadBeforeDef = false;
+    unsigned VReg = LI.reg;
+    if (MRI->shouldTrackSubRegLiveness(VReg)) {
       if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
         MachineInstr *MI = getInstructionFromIndex(Def);
-        MI->addRegisterDefReadUndef(LI.reg);
+        MI->addRegisterDefReadUndef(VReg);
+        DeadBeforeDef = true;
       }
     }
 
     if (I->end != Def.getDeadSlot())
       continue;
     if (VNI->isPHIDef()) {
       // This is a dead PHI. Remove it.
-      VNI->markUnused();
-      LI.removeSegment(I);
+      removeDeadDef(LI, I);
       DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
       PHIRemoved = true;
     } else {
       // This is a dead def. Make sure the instruction knows.
       MachineInstr *MI = getInstructionFromIndex(Def);
       assert(MI && "No instruction defining live value");
-      MI->addRegisterDead(LI.reg, TRI);
+      MI->addRegisterDead(VReg, TRI);
+
+      // If we have a dead def that is completely separate from the rest of
+      // the liverange then we rewrite it to use a different VReg to not violate
+      // the rule that the liveness of a virtual register forms a connected
+      // component. This should only happen if subregister liveness is tracked.
+      if (DeadBeforeDef) {
+        // Create a fresh vreg and rewrite MI.
+        const TargetRegisterClass *RegClass = MRI->getRegClass(VReg);
+        unsigned NewVReg = MRI->createVirtualRegister(RegClass);
+        LiveInterval &NewLI = createEmptyInterval(NewVReg);
+        NewLI.createDeadDef(Def, VNInfoAllocator);
+        for (MachineOperand &MO : MI->operands()) {
+          if (MO.isReg() && MO.getReg() == VReg)
+            MO.setReg(NewVReg);
+        }
+        // Remove the dead segments from the old register liveness info.
+        removeDeadDef(LI, I);
+      }
+
       if (dead && MI->allDefsAreDead()) {
         DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
         dead->push_back(MI);
       }
     }
   }
   return PHIRemoved;
 }

test/CodeGen/AMDGPU/partially-dead-super-register-immediate.ll

-; XFAIL: *
 ; RUN: llc -march=amdgcn -verify-machineinstrs -verify-coalescing < %s
 
 ; The original and requires materializing a 64-bit immediate for
 ; s_and_b64. This is split into 2 x v_and_i32, part of the immediate
 ; is folded through the reg_sequence into the v_and_i32 operand, and
 ; only half of the result is ever used.
 ;
 ; During live interval construction, the first sub register def is