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

llvm/trunk/lib/CodeGen/LiveIntervalAnalysis.cpp

 }
 
 
 /// computeVirtRegInterval - Compute the live interval of a virtual register,
 /// based on defs and uses.
 void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
   assert(LRCalc && "LRCalc not initialized.");
   assert(LI.empty() && "Should only compute empty intervals.");
+  bool ShouldTrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(LI.reg);
   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
-  LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg));
-  computeDeadValues(LI, nullptr);
+  LRCalc->calculate(LI, ShouldTrackSubRegLiveness);
+  bool SeparatedComponents = computeDeadValues(LI, nullptr);
+  if (SeparatedComponents) {
+    assert(ShouldTrackSubRegLiveness
+           && "Separated components should only occur for unused subreg defs");
+    SmallVector<LiveInterval*, 8> SplitLIs;
+    splitSeparateComponents(LI, SplitLIs);
+  }
 }
 
 void LiveIntervals::computeVirtRegs() {
   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
     if (MRI->reg_nodbg_empty(Reg))
       continue;
     createAndComputeVirtRegInterval(Reg);
bool LiveIntervals::shrinkToUses(LiveInterval *li,
   // Handle dead values.
   bool CanSeparate = computeDeadValues(*li, dead);
   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
   return CanSeparate;
 }
 
 bool LiveIntervals::computeDeadValues(LiveInterval &LI,
                                       SmallVectorImpl<MachineInstr*> *dead) {
-  bool PHIRemoved = false;
+  bool MayHaveSplitComponents = 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);
       DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
-      PHIRemoved = true;
+      MayHaveSplitComponents = 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)
+        MayHaveSplitComponents = true;
+
       if (dead && MI->allDefsAreDead()) {
         DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
         dead->push_back(MI);
       }
     }
   }
-  return PHIRemoved;
+  return MayHaveSplitComponents;
 }
 
 void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg)
 {
   DEBUG(dbgs() << "Shrink: " << SR << '\n');
   assert(TargetRegisterInfo::isVirtualRegister(Reg)
          && "Can only shrink virtual registers");
   // Find all the values used, including PHI kills.

llvm/trunk/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