[RegAllocGreedy]: Allow recoloring of done register if it's non-tied

[uabelho]

Summary

If we have a non-allocated register, we allow us to try recoloring of an
already allocated and "Done" register, even if they are of the same
register class, if the non-allocated register has at least one tied def
and the allocated one has none.

It should be easier to recolor the non-tied register than the tied one, so
it might be an improvement even if they use the same regclasses.

[uabelho]

I found this problem on my out-of-tree target and the only reproducer I
have for it there is quite big and ugly so I've failed to make a nice
testcase out of it for an in-tree target.

I've run the benchmarks with

lnt runtest nt

on my x86 linux machine and computed checksums on the object files
and there is no difference with/without the patch.

[qcolombet]

Looks sensible to me.

[uabelho]

Rebased to top of tree.

llvm/trunk/lib/CodeGen/RegAllocGreedy.cpp

unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
   // Then isolate blocks.
   return tryBlockSplit(VirtReg, Order, NewVRegs);
 }
 
 //===----------------------------------------------------------------------===//
 //                          Last Chance Recoloring
 //===----------------------------------------------------------------------===//
 
+/// Return true if \p reg has any tied def operand.
+static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg) {
+  for (const MachineOperand &MO : MRI->def_operands(reg))
+    if (MO.isTied())
+      return true;
+
+  return false;
+}
+
 /// mayRecolorAllInterferences - Check if the virtual registers that
 /// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be
 /// recolored to free \p PhysReg.
 /// When true is returned, \p RecoloringCandidates has been augmented with all
 /// the live intervals that need to be recolored in order to free \p PhysReg
 /// for \p VirtReg.
 /// \p FixedRegisters contains all the virtual registers that cannot be
 /// recolored.
if (Q.collectInterferingVRegs(LastChanceRecoloringMaxInterference) >=
       DEBUG(dbgs() << "Early abort: too many interferences.\n");
       CutOffInfo |= CO_Interf;
       return false;
     }
     for (unsigned i = Q.interferingVRegs().size(); i; --i) {
       LiveInterval *Intf = Q.interferingVRegs()[i - 1];
       // If Intf is done and sit on the same register class as VirtReg,
       // it would not be recolorable as it is in the same state as VirtReg.
-      if ((getStage(*Intf) == RS_Done &&
-           MRI->getRegClass(Intf->reg) == CurRC) ||
+      // However, if VirtReg has tied defs and Intf doesn't, then
+      // there is still a point in examining if it can be recolorable.
+      if (((getStage(*Intf) == RS_Done &&
+            MRI->getRegClass(Intf->reg) == CurRC) &&
+           !(hasTiedDef(MRI, VirtReg.reg) && !hasTiedDef(MRI, Intf->reg))) ||
           FixedRegisters.count(Intf->reg)) {
         DEBUG(dbgs() << "Early abort: the interference is not recolorable.\n");
         return false;
       }
       RecoloringCandidates.insert(Intf);
     }
   }
   return true;