[RegAllocGreedy] Take last chance recoloring into account in evicting.

[rudkx]

Summary

Last chance recoloring inserts into FixedRegisters those virtual
registers it is attempting to assign a physical register to.

We must consider these when we consider candidates for eviction so that
we do not end up evicting something while we are attempting to recolor
to assign it.

This is hitting in an out-of-tree target and no longer reproduces on
trunk. That does not appear to be a result of it having been fixed, but
rather, it appears that optimization changes and/or other changes to
register allocation mask the problem.

I haven't found a way to come up with a reasonable test case for this
(i.e. one that I can actually commit to open source, is reasonable
in size, and actually reproduces the issue).

rdar://problem/45708741

[qcolombet]

Hi Mark,

I am not sure that's the right fix, because by design, last chance recoloring was allowed to evict things that got scavenged.
To elaborate a bit on that, it is supposed to be fine to split the value (by spilling or copy insertion) but it is not fine to have it appears twice in the "moving part" (the fixedRegisters set).

If you evict something, the idea was the evicted register would still be here but with a smaller live-range, e.g.,

reg1(Rx) =
...
= reg1(Rx)

During last chance recoloring, if we were to scavenge reg1 and then evict it, we would end up with something like:

reg1(unassigned) =
Tmp(unassigned) = live-rangeSplittingOp reg1(unassigned)
...
regNew(unassigned) = live-rangeSplittingOp Tmp(unassigned)
= regNew(unassigned)

Which is fine.
When reverting the last coloring changes if it fails, reg1 can get back to its old assignment (Rx here) with no problem.

IIRC there was a bug with the order in which we assign them back, but I thought it was fixed.

What is the problem you're seeing?

Cheers,
-Quentin

[qcolombet]

Hi Mark,

Actually, re-reading through the code (it's been a while since I touched it), you're right, the intent was to freeze those regs when we scavenge them but do whatever we want to the others.
Bottom line, the fix looks good to me.

Nitpick below.

Cheers,
-Quentin

llvm/lib/CodeGen/RegAllocGreedy.cpp

2626

IIRC ::insert returns a boolean that says whether or not it has been inserted.
Thus, we can avoid the call to count and assert on the result of ::insert.

[rudkx]

llvm/lib/CodeGen/RegAllocGreedy.cpp

2626

Yes, I realize, but that would require assigning the result of ::insert, asserting on it, and then doing something like (void) inserted; to avoid a warning, so this seemed cleaner and simpler to me.

Having said that, if you feel strongly about doing that rather than calling ::count I'm more than happy to fix it up.

[qcolombet]

llvm/lib/CodeGen/RegAllocGreedy.cpp

2626

I don't feel strongly either way.
The only reason I brought it up is because ::count is not free. But given that's in anyway in any critical path plus that's just assert, up to you :).

[uabelho]

Hi!

Nice to see this fix get in because we've seen the need for such a change for our out-of-tree target as well.

However, we've added a FixedRegisters argument to tryAssign and trySplit too.
It was a while since we did that change locally but would it make sense to push that into trunk too?

[uabelho]

In D58200#1397672, @uabelho wrote:

Hi!

Nice to see this fix get in because we've seen the need for such a change for our out-of-tree target as well.

However, we've added a FixedRegisters argument to tryAssign and trySplit too.
It was a while since we did that change locally but would it make sense to push that into trunk too?

I created a patch for that:
https://reviews.llvm.org/D58376

llvm/lib/CodeGen/RegAllocGreedy.cpp

   void calcGapWeights(unsigned, SmallVectorImpl<float>&);
   unsigned canReassign(LiveInterval &VirtReg, unsigned PrevReg);
   bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
-  bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&);
+  bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&,
+                            const SmallVirtRegSet& = SmallVirtRegSet());
   bool canEvictInterferenceInRange(LiveInterval &VirtReg, unsigned PhysReg,
                                    SlotIndex Start, SlotIndex End,
                                    EvictionCost &MaxCost);

   unsigned tryAssign(LiveInterval&, AllocationOrder&,
                      SmallVectorImpl<unsigned>&);
   unsigned tryEvict(LiveInterval&, AllocationOrder&,
-                    SmallVectorImpl<unsigned>&, unsigned = ~0u);
+                    SmallVectorImpl<unsigned>&, unsigned = ~0u,
+                    const SmallVirtRegSet& = SmallVirtRegSet());
   unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
                           SmallVectorImpl<unsigned>&);
   unsigned isSplitBenefitWorthCost(LiveInterval &VirtReg);

 ///                when returning true.
 /// @returns True when interference can be evicted cheaper than MaxCost.
 bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
-                                    bool IsHint, EvictionCost &MaxCost) {
+                                    bool IsHint, EvictionCost &MaxCost,
+                                    const SmallVirtRegSet &FixedRegisters) {
   // It is only possible to evict virtual register interference.
   if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
     return false;

       LiveInterval *Intf = Q.interferingVRegs()[i - 1];
       assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) &&
              "Only expecting virtual register interference from query");
+
+      // Do not allow eviction of a virtual register if we are in the middle
+      // of last-chance recoloring and this virtual register is one that we
+      // have scavenged a physical register for.
+      if (FixedRegisters.count(Intf->reg))
+        return false;
+
       // Never evict spill products. They cannot split or spill.
       if (getStage(*Intf) == RS_Done)
         return false;

 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
                             AllocationOrder &Order,
                             SmallVectorImpl<unsigned> &NewVRegs,
-                            unsigned CostPerUseLimit) {
+                            unsigned CostPerUseLimit,
+                            const SmallVirtRegSet &FixedRegisters) {
   NamedRegionTimer T("evict", "Evict", TimerGroupName, TimerGroupDescription,
                      TimePassesIsEnabled);
 

       continue;
     }
 
-    if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
+    if (!canEvictInterference(VirtReg, PhysReg, false, BestCost,
+                              FixedRegisters))
       continue;
 
     // Best so far.

   DenseMap<unsigned, unsigned> VirtRegToPhysReg;
   // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
   // this recoloring "session".
+  assert(!FixedRegisters.count(VirtReg.reg));
   FixedRegisters.insert(VirtReg.reg);
   SmallVector<unsigned, 4> CurrentNewVRegs;
 

   // get a second chance until they have been split.
   if (Stage != RS_Split)
     if (unsigned PhysReg =
-            tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit)) {
+            tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,
+                     FixedRegisters)) {
       unsigned Hint = MRI->getSimpleHint(VirtReg.reg);
       // If VirtReg has a hint and that hint is broken record this
       // virtual register as a recoloring candidate for broken hint.