Don't skip splitSeparateComponents in eliminateDeadDefs

[wmi]

Summary

This patch is to fix a bug reported here: http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160411/347420.html

Because HoistSpillHelper::hoistAllSpills is called in postOptimization, we don't want LiveRangeEdit::eliminateDeadDefs to generate unassigned new vregs. That is why I set NoSplit flag to early return from LiveRangeEdit::eliminateDeadDefs. However, skipping splitSeparateComponents will make verify-machineinstrs unhappy, so I remove the early return, and use HoistSpillHelper::LRE_DidCloneVirtReg to assign physreg/stackslot for those new vregs. I know those new vregs should have the same physreg/stackslot as the old vreg which new vregs are splitted from.

Some code reorganization to make class HoistSpillHelper private inheriting from LiveRangeEdit::Delegate possible. This is to be consistent with class RAGreedy and class RegisterCoalescer.

Thanks,
Wei.

[uabelho]

The problem I saw on my out-of-tree target seems to be fixed with this patch and so far I haven't seen any new problems.

I'll run some more tests during the day.

[uabelho]

I haven't seen any new problems on my out-of-tree target with this patch.

[wmi]

Mikael, thank you for trying this patch.

Wei.

llvm/trunk/include/llvm/CodeGen/LiveRangeEdit.h

public:
   void eraseVirtReg(unsigned Reg);
 
   /// eliminateDeadDefs - Try to delete machine instructions that are now dead
   /// (allDefsAreDead returns true). This may cause live intervals to be trimmed
   /// and further dead efs to be eliminated.
   /// RegsBeingSpilled lists registers currently being spilled by the register
   /// allocator.  These registers should not be split into new intervals
   /// as currently those new intervals are not guaranteed to spill.
-  /// NoSplit indicates this func is used after the iterations of selectOrSplit
-  /// where registers should not be split into new intervals.
   void eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
-                         ArrayRef<unsigned> RegsBeingSpilled = None,
-                         bool NoSplit = false);
+                         ArrayRef<unsigned> RegsBeingSpilled = None);
 
   /// calculateRegClassAndHint - Recompute register class and hint for each new
   /// register.
   void calculateRegClassAndHint(MachineFunction&,
                                 const MachineLoopInfo&,
                                 const MachineBlockFrequencyInfo&);
 };
 
 }
 
 #endif

llvm/trunk/lib/CodeGen/InlineSpiller.cpp

 STATISTIC(NumFolded,          "Number of folded stack accesses");
 STATISTIC(NumFoldedLoads,     "Number of folded loads");
 STATISTIC(NumRemats,          "Number of rematerialized defs for spilling");
 
 static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden,
                                      cl::desc("Disable inline spill hoisting"));
 
 namespace {
-class HoistSpillHelper {
+class HoistSpillHelper : private LiveRangeEdit::Delegate {
+  MachineFunction &MF;
   LiveIntervals &LIS;
   LiveStacks &LSS;
   AliasAnalysis *AA;
   MachineDominatorTree &MDT;
   MachineLoopInfo &Loops;
   VirtRegMap &VRM;
   MachineFrameInfo &MFI;
   MachineRegisterInfo &MRI;
class HoistSpillHelper : private LiveRangeEdit::Delegate {
   void runHoistSpills(unsigned OrigReg, VNInfo &OrigVNI,
                       SmallPtrSet<MachineInstr *, 16> &Spills,
                       SmallVectorImpl<MachineInstr *> &SpillsToRm,
                       DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns);
 
 public:
   HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
                    VirtRegMap &vrm)
-      : LIS(pass.getAnalysis<LiveIntervals>()),
+      : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
         LSS(pass.getAnalysis<LiveStacks>()),
         AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
         MDT(pass.getAnalysis<MachineDominatorTree>()),
         Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
         MFI(*mf.getFrameInfo()), MRI(mf.getRegInfo()),
         TII(*mf.getSubtarget().getInstrInfo()),
         TRI(*mf.getSubtarget().getRegisterInfo()),
         MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()) {}
 
   void addToMergeableSpills(MachineInstr *Spill, int StackSlot,
                             unsigned Original);
   bool rmFromMergeableSpills(MachineInstr *Spill, int StackSlot);
-  void hoistAllSpills(LiveRangeEdit &Edit);
+  void hoistAllSpills();
+  void LRE_DidCloneVirtReg(unsigned, unsigned) override;
 };
 
 class InlineSpiller : public Spiller {
   MachineFunction &MF;
   LiveIntervals &LIS;
   LiveStacks &LSS;
   AliasAnalysis *AA;
   MachineDominatorTree &MDT;
void InlineSpiller::spill(LiveRangeEdit &edit) {
   if (!RegsToSpill.empty())
     spillAll();
 
   Edit->calculateRegClassAndHint(MF, Loops, MBFI);
 }
 
 /// Optimizations after all the reg selections and spills are done.
 ///
-void InlineSpiller::postOptimization() {
-  SmallVector<unsigned, 4> NewVRegs;
-  LiveRangeEdit LRE(nullptr, NewVRegs, MF, LIS, &VRM, nullptr);
-  HSpiller.hoistAllSpills(LRE);
-  assert(NewVRegs.size() == 0 &&
-         "No new vregs should be generated in hoistAllSpills");
-}
+void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }
 
 /// When a spill is inserted, add the spill to MergeableSpills map.
 ///
 void HoistSpillHelper::addToMergeableSpills(MachineInstr *Spill, int StackSlot,
                                             unsigned Original) {
   StackSlotToReg[StackSlot] = Original;
   SlotIndex Idx = LIS.getInstructionIndex(*Spill);
   VNInfo *OrigVNI = LIS.getInterval(Original).getVNInfoAt(Idx.getRegSlot());

 /// is located, mark the dominated spills to be deleted along the way and
 /// collect the BB nodes on the path from non-dominated spills to the define
 /// instruction into a WorkSet. The nodes in WorkSet are the candidate places
 /// where we consider to hoist the spills. We iterate the WorkSet in bottom-up
 /// order, and for each node, we will decide whether to hoist spills inside
 /// its subtree to that node. In this way, we can get benefit locally even if
 /// hoisting all the equal spills to one cold place is impossible.
 ///
-void HoistSpillHelper::hoistAllSpills(LiveRangeEdit &Edit) {
+void HoistSpillHelper::hoistAllSpills() {
+  SmallVector<unsigned, 4> NewVRegs;
+  LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);
+
   // Save the mapping between stackslot and its original reg.
   DenseMap<int, unsigned> SlotToOrigReg;
   for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
     int Slot = VRM.getStackSlot(Reg);
     if (Slot != VirtRegMap::NO_STACK_SLOT)
       SlotToOrigReg[Slot] = VRM.getOriginal(Reg);
     unsigned Original = VRM.getPreSplitReg(Reg);
for (auto &Ent : MergeableSpills) {
     for (auto const RMEnt : SpillsToRm) {
       RMEnt->setDesc(TII.get(TargetOpcode::KILL));
       for (unsigned i = RMEnt->getNumOperands(); i; --i) {
         MachineOperand &MO = RMEnt->getOperand(i - 1);
         if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())
           RMEnt->RemoveOperand(i - 1);
       }
     }
-    Edit.eliminateDeadDefs(SpillsToRm, None, true);
-  }
+    Edit.eliminateDeadDefs(SpillsToRm, None);
+  }
+
+/// For VirtReg clone, the \p New register should have the same physreg or
+/// stackslot as the \p old register.
+void HoistSpillHelper::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
+  if (VRM.hasPhys(Old))
+    VRM.assignVirt2Phys(New, VRM.getPhys(Old));
+  else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)
+    VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
+  else
+    llvm_unreachable("VReg should be assigned either physreg or stackslot");
 }

llvm/trunk/lib/CodeGen/LiveRangeEdit.cpp

for (unsigned i = 0, e = RegsToErase.size(); i != e; ++i) {
     if (LIS.hasInterval(Reg) && MRI.reg_nodbg_empty(Reg)) {
       ToShrink.remove(&LIS.getInterval(Reg));
       eraseVirtReg(Reg);
     }
   }
 }
 
 void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
-                                      ArrayRef<unsigned> RegsBeingSpilled,
-                                      bool NoSplit) {
+                                      ArrayRef<unsigned> RegsBeingSpilled) {
   ToShrinkSet ToShrink;
 
   for (;;) {
     // Erase all dead defs.
     while (!Dead.empty())
       eliminateDeadDef(Dead.pop_back_val(), ToShrink);
 
     if (ToShrink.empty())
       break;
 
     // Shrink just one live interval. Then delete new dead defs.
     LiveInterval *LI = ToShrink.back();
     ToShrink.pop_back();
     if (foldAsLoad(LI, Dead))
       continue;
     unsigned VReg = LI->reg;
     if (TheDelegate)
       TheDelegate->LRE_WillShrinkVirtReg(VReg);
     if (!LIS.shrinkToUses(LI, &Dead))
       continue;
 
-    if (NoSplit)
-      continue;
-
     // Don't create new intervals for a register being spilled.
     // The new intervals would have to be spilled anyway so its not worth it.
     // Also they currently aren't spilled so creating them and not spilling
     // them results in incorrect code.
     bool BeingSpilled = false;
     for (unsigned i = 0, e = RegsBeingSpilled.size(); i != e; ++i) {
       if (VReg == RegsBeingSpilled[i]) {
         BeingSpilled = true;

llvm/trunk/test/CodeGen/X86/interval-update-remat.ll

-; RUN: llc -verify-regalloc < %s
+; RUN: llc -verify-regalloc -verify-machineinstrs < %s
 ; PR27275: When enabling remat for vreg defined by PHIs, make sure the update
 ; of the live range removes dead phi. Otherwise, we may end up with PHIs with
 ; incorrect operands and that will trigger assertions or verifier failures
 ; in later passes.
 
 target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
 target triple = "i386-unknown-linux-gnu"