LiveIntervalAnalysis: Add function to reassign vregs of dead subregister defs

[MatzeB]

Summary

Normally dead definitions have an own vreg when coming out of SSA form.
However we do not have a static single assignment property at the
subregister level, so we cannot easily detect dead subregister
definitions without doing subregister liveness analysis. We also cannot
mark them with a dead flag unless all lanes (even the ones not
affected by the subregister definition) are dead.

The new LiveIntervalAnalysis::renameDeadSubRegDefs() detects dead
subregister definitions based on liveness information and assigns them
to new vreg.

This is intended as a prepass to subregister aware scheduling and avoids
the formation of multiple connected components in liveintervals if dead
subregister defs are moved. It may also have some positive effects on
the allocation by removing unnecessary constraints.

[arsenm]

lib/CodeGen/LiveIntervalAnalysis.cpp

1489

grammar, s/an/their/

[atrick]

LGTM except for the inline comments.

lib/CodeGen/LiveIntervalAnalysis.cpp

1481

This function needs comments reflecting some of what is explained in the commit message. It should be clear that this is an optimization not required for correctness.

1498

This shadows 'Reg' above. It should probably be an assert.

1528

setIsUndef confused me at first. You must be assuming here that this is a subregister def and that subreg defs are always marked undef. Please comment. Also let me know where that invariant is explained and enforced.

[MatzeB]

This is superseded by http://reviews.llvm.org/D16126 as it turned out the dead subregister defs are just a special case of a general situation where subregisters defs+uses do not influence each other and can be split into separate equivalence classes.

include/llvm/CodeGen/LiveIntervalAnalysis.h

public:
     /// Remove value number and related live segments of @p LI and its subranges
     /// that start at position @p Pos.
     void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos);
 
     /// Split separate components in LiveInterval \p LI into separate intervals.
     void splitSeparateComponents(LiveInterval &LI,
                                  SmallVectorImpl<LiveInterval*> &SplitLIs);
 
+    /// Assure dead subregister definitions have their own vreg assigned.
+    void renameDeadSubRegDefs();
+
   private:
     /// Compute live intervals for all virtual registers.
     void computeVirtRegs();
 
     /// Compute RegMaskSlots and RegMaskBits.
     void computeRegMasks();
 
     /// Walk the values in @p LI and check for dead values:

lib/CodeGen/LiveIntervalAnalysis.cpp

void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
   const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
   for (unsigned I = 1; I < NumComp; ++I) {
     unsigned NewVReg = MRI->createVirtualRegister(RegClass);
     LiveInterval &NewLI = createEmptyInterval(NewVReg);
     SplitLIs.push_back(&NewLI);
   }
   ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
 }
+
+/// Remove the definition at \p Def from LiveRange \p LR. If there is an
+/// adjacent previous segment merge with that. If there is no Def at the
+/// specified position do nothing.
+static void removeDefFrom(LiveRange &LR, SlotIndex Def) {
+  LiveRange::iterator I = LR.find(Def);
+  if (I->start != Def)
+    return;
+
+  // Merge with previous segment if possible.
+  if (I != LR.begin()) {
+    LiveRange::iterator Prev = std::prev(I);
+    if (SlotIndex::isSameInstr(Prev->end, I->start))
+      Prev->end = I->end;
+  }
+  I->valno->markUnused();
+  LR.removeSegment(I);
+}
+
+void LiveIntervals::renameDeadSubRegDefs() {
+  for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
+    unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
+    LiveInterval *LI = VirtRegIntervals[Reg];
+    if (LI == nullptr || !LI->hasSubRanges())
+      continue;
+
+    // Only look for vregs with multiple definition to find candidates of dead
+    // subregister defs that do not write into an own register.
+    if (LI->valnos.size() < 2)
+      continue;
+
+    for (const VNInfo *VNI : LI->valnos) {
+      if (VNI->isUnused())
+        continue;
+
+      SlotIndex Def = VNI->def;
+      unsigned Reg = LI->reg;
+      // Do we only have dead (subregister) defs at VNI->def?
+      bool OnlyDeadDefs = true;
+      for (const LiveInterval::SubRange &SR : LI->subranges()) {
+        LiveRange::const_iterator SI = SR.find(Def);
+        if (SI != SR.end() && SI->start == Def &&
+            !SlotIndex::isSameInstr(SI->start, SI->end)) {
+          OnlyDeadDefs = false;
+          break;
+        }
+      }
+      if (!OnlyDeadDefs)
+        continue;
+
+      MachineInstr *MI = getInstructionFromIndex(Def);
+      if (MI == nullptr)
+        continue;
+      const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
+      unsigned NewVReg = MRI->createVirtualRegister(RegClass);
+      LiveInterval &NewLI = createEmptyInterval(NewVReg);
+      NewLI.createDeadDef(Def, getVNInfoAllocator());
+      LaneBitmask LaneMask = 0;
+      for (MachineOperand &MO : MI->operands()) {
+        if (!MO.isReg() || !MO.isDef() || MO.getReg() != Reg)
+          continue;
+        unsigned SubRegIndex = MO.getSubReg();
+        assert(SubRegIndex != 0 && !MO.isUndef() &&
+               "Should find proper subreg def");
+        LaneMask |= TRI->getSubRegIndexLaneMask(SubRegIndex);
+        MO.setReg(NewVReg);
+        MO.setIsUndef();
+        MO.setIsDead();
+      }
+      assert(LaneMask != 0);
+
+      NewLI.createSubRangeFrom(getVNInfoAllocator(), LaneMask, NewLI);
+
+      // Remove Def from LI.
+      for (LiveInterval::SubRange &SR : LI->subranges())
+        removeDefFrom(SR, Def);
+      LI->removeEmptySubRanges();
+      removeDefFrom(*LI, Def);
+    }
+  }
+}