RegAllocGreedy: Allow target to specify register class ordering.

[MatzeB]

Summary

Specify an allocation order with a register class. This is used by register
allocators with a greedy heuristic. This is usefull as it is sometimes
beneficial to color more constrained classes first.

[atrick]

Ok. The comment is misleading though. It makes it sounds as though getClassPriority can be used to prioritize "big" live ranges. I think it instead allows register class order to take precedence over live range size.

Also, this really puts the burden on the target to assign priorities that make sense in the context of the regalloc algorithm. I think it's ok to have that back door, but it seems like there should be a use-at-your-own risk disclaimer, no? I would indicate that the default implementation should be used unless the hook is really needed to improve allocation.

[qcolombet]

Agreed with Andy.

Also, I believe it would make sense to have that tablegen driven (like the allocation order), we possibly a hook to override.

Q.

[MatzeB]

New version which sets priority with tablegen.

[atrick]

LGTM.

llvm/trunk/include/llvm/Target/Target.td

class RegisterClass<string namespace, list<ValueType> regTypes, int alignment,
   // to use in a given machine function. The code will be inserted in a
   // function like this:
   //
   //   static inline unsigned f(const MachineFunction &MF) { ... }
   //
   // The function should return 0 to select the default order defined by
   // MemberList, 1 to select the first AltOrders entry and so on.
   code AltOrderSelect = [{}];
+
+  // Specify allocation priority for register allocators using a greedy
+  // heuristic. Classes with high priority are assigned first. It is sometimes
+  // beneficial to assign registers to highly constrained classes first.
+  // The priority has to be in the range [0,63].
+  int AllocationPriority = 0;
 }
 
 // The memberList in a RegisterClass is a dag of set operations. TableGen
 // evaluates these set operations and expand them into register lists. These
 // are the most common operation, see test/TableGen/SetTheory.td for more
 // examples of what is possible:
 //
 // (add R0, R1, R2) - Set Union. Each argument can be an individual register, a

llvm/trunk/include/llvm/Target/TargetRegisterInfo.h

public:
   typedef const TargetRegisterClass* const * sc_iterator;
 
   // Instance variables filled by tablegen, do not use!
   const MCRegisterClass *MC;
   const vt_iterator VTs;
   const uint32_t *SubClassMask;
   const uint16_t *SuperRegIndices;
   const unsigned LaneMask;
+  /// Classes with high priority should be assigned first by register allocators
+  /// with a greedy heuristic. The priority is a value in the range [0,63].
+  const uint8_t AllocationPriority;
   /// Whether the class supports two (or more) disjunct subregister indices.
   const bool HasDisjunctSubRegs;
   const sc_iterator SuperClasses;
   ArrayRef<MCPhysReg> (*OrderFunc)(const MachineFunction&);
 
   /// getID() - Return the register class ID number.
   ///
   unsigned getID() const { return MC->getID(); }

llvm/trunk/lib/CodeGen/RegAllocGreedy.cpp

void RAGreedy::enqueue(PQueue &CurQueue, LiveInterval *LI) {
   if (ExtraRegInfo[Reg].Stage == RS_Split) {
     // Unsplit ranges that couldn't be allocated immediately are deferred until
     // everything else has been allocated.
     Prio = Size;
   } else {
     // Giant live ranges fall back to the global assignment heuristic, which
     // prevents excessive spilling in pathological cases.
     bool ReverseLocal = TRI->reverseLocalAssignment();
+    const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
     bool ForceGlobal = !ReverseLocal &&
-      (Size / SlotIndex::InstrDist) > (2 * MRI->getRegClass(Reg)->getNumRegs());
+      (Size / SlotIndex::InstrDist) > (2 * RC.getNumRegs());
 
     if (ExtraRegInfo[Reg].Stage == RS_Assign && !ForceGlobal && !LI->empty() &&
         LIS->intervalIsInOneMBB(*LI)) {
       // Allocate original local ranges in linear instruction order. Since they
       // are singly defined, this produces optimal coloring in the absence of
       // global interference and other constraints.
       if (!ReverseLocal)
         Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex());
       else {
         // Allocating bottom up may allow many short LRGs to be assigned first
         // to one of the cheap registers. This could be much faster for very
         // large blocks on targets with many physical registers.
         Prio = Indexes->getZeroIndex().getInstrDistance(LI->endIndex());
       }
-    }
-    else {
+      Prio |= RC.AllocationPriority << 24;
+    } else {
       // Allocate global and split ranges in long->short order. Long ranges that
       // don't fit should be spilled (or split) ASAP so they don't create
       // interference.  Mark a bit to prioritize global above local ranges.
       Prio = (1u << 29) + Size;
     }
     // Mark a higher bit to prioritize global and local above RS_Split.
     Prio |= (1u << 31);
 

llvm/trunk/utils/TableGen/CodeGenRegisters.h

public:
     unsigned EnumValue;
     std::string Namespace;
     SmallVector<MVT::SimpleValueType, 4> VTs;
     unsigned SpillSize;
     unsigned SpillAlignment;
     int CopyCost;
     bool Allocatable;
     std::string AltOrderSelect;
+    uint8_t AllocationPriority;
     /// Contains the combination of the lane masks of all subregisters.
     unsigned LaneMask;
     /// True if there are at least 2 subregisters which do not interfere.
     bool HasDisjunctSubRegs;
 
     // Return the Record that defined this class, or NULL if the class was
     // created by TableGen.
     Record *getDef() const { return TheDef; }

llvm/trunk/utils/TableGen/CodeGenRegisters.cpp

CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R)
   unsigned Size = R->getValueAsInt("Size");
 
   Namespace = R->getValueAsString("Namespace");
   SpillSize = Size ? Size : MVT(VTs[0]).getSizeInBits();
   SpillAlignment = R->getValueAsInt("Alignment");
   CopyCost = R->getValueAsInt("CopyCost");
   Allocatable = R->getValueAsBit("isAllocatable");
   AltOrderSelect = R->getValueAsString("AltOrderSelect");
+  int AllocationPriority = R->getValueAsInt("AllocationPriority");
+  if (AllocationPriority < 0 || AllocationPriority > 63)
+    PrintFatalError(R->getLoc(), "AllocationPriority out of range [0,63]");
+  this->AllocationPriority = AllocationPriority;
 }
 
 // Create an inferred register class that was missing from the .td files.
 // Most properties will be inherited from the closest super-class after the
 // class structure has been computed.
 CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank,
                                            StringRef Name, Key Props)
   : Members(*Props.Members),

llvm/trunk/utils/TableGen/RegisterInfoEmitter.cpp

if (!RegisterClasses.empty()) {
     for (const auto &RC : RegisterClasses) {
       OS << "  extern const TargetRegisterClass " << RC.getName()
          << "RegClass = {\n    " << '&' << Target.getName()
          << "MCRegisterClasses[" << RC.getName() << "RegClassID],\n    "
          << "VTLists + " << VTSeqs.get(RC.VTs) << ",\n    " << RC.getName()
          << "SubClassMask,\n    SuperRegIdxSeqs + "
          << SuperRegIdxSeqs.get(SuperRegIdxLists[RC.EnumValue]) << ",\n    "
          << format("0x%08x,\n    ", RC.LaneMask)
+         << (unsigned)RC.AllocationPriority << ",\n    "
          << (RC.HasDisjunctSubRegs?"true":"false")
          << ", /* HasDisjunctSubRegs */\n    ";
       if (RC.getSuperClasses().empty())
         OS << "NullRegClasses,\n    ";
       else
         OS << RC.getName() << "Superclasses,\n    ";
       if (RC.AltOrderSelect.empty())
         OS << "nullptr\n";