RegAllocGreedy: Avoid overflowing priority bitfields

[arsenm]

Summary

The class priority is expected to be at most 5 bits before it starts
clobbering bits used for other fields. Also clamp the instruction
distance in case we have millions of instructions.

AMDGPU was accidentally overflowing into the global priority bit in
some cases. I think in principal we would have wanted this, but in the
cases I've looked at, it had the counter intuitive effect and
de-prioritized the large register tuple.

Avoid using weird bit hack PPC uses for global priority. The
AllocationPriority field is really 5 bits, and PPC was relying on
overflowing this to 6-bits to forcibly set the global priority
bit. Split this out as a separate flag to avoid having magic behavior
for values above 31.

[barannikov88]

llvm/include/llvm/Target/Target.td

291

Nit: '0' -> 'false'

[foad]

llvm/lib/CodeGen/RegAllocGreedy.cpp

352–353

These two get swapped by RegClassPriorityTrumpsGlobalness.

llvm/lib/Target/PowerPC/PPCRegisterInfoMMA.td

80–81

Shouldn't this be 36 - 32 = 4 to preserve current behaviour?

llvm/utils/TableGen/CodeGenRegisters.cpp

806–807

The < 0 check seems redundant.

[arsenm]

Address comments

[foad]

LGTM with the comment fixed, but it would be nice to get an ack from the PPC maintainers (or maybe @hfinkel).

llvm/lib/CodeGen/RegAllocGreedy.cpp

352–353

You've got the if/else cases the wrong way round.

[arsenm]

Fix comment

[arsenm]

63d1d37d35e513632e9d4fcc1910ed4e9e3525d0

llvm/include/llvm/CodeGen/TargetRegisterInfo.h

public:
   using sc_iterator = const TargetRegisterClass* const *;
 
   // Instance variables filled by tablegen, do not use!
   const MCRegisterClass *MC;
   const uint32_t *SubClassMask;
   const uint16_t *SuperRegIndices;
   const LaneBitmask LaneMask;
   /// Classes with a higher priority value are assigned first by register
-  /// allocators using a greedy heuristic. The value is in the range [0,63].
-  /// Values >= 32 should be used with care since they may overlap with other
-  /// fields in the allocator's priority heuristics.
+  /// allocators using a greedy heuristic. The value is in the range [0,31].
   const uint8_t AllocationPriority;
+
+  // Change allocation priority heuristic used by greedy.
+  const bool GlobalPriority;
+
   /// Configurable target specific flags.
   const uint8_t TSFlags;
   /// Whether the class supports two (or more) disjunct subregister indices.
   const bool HasDisjunctSubRegs;
   /// Whether a combination of subregisters can cover every register in the
   /// class. See also the CoveredBySubRegs description in Target.td.
   const bool CoveredBySubRegs;
   const sc_iterator SuperClasses;

llvm/include/llvm/Target/Target.td

class RegisterClass<string namespace, list<ValueType> regTypes, int alignment,
   //
   // 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 higher priority values are assigned first. This is
   // useful as it is sometimes beneficial to assign registers to highly
-  // constrained classes first. The value has to be in the range [0,63].
-  // Values >= 32 should be used with care since they may overlap with other
-  // fields in the allocator's priority heuristics.
+  // constrained classes first. The value has to be in the range [0,31].
   int AllocationPriority = 0;
 
+  // Force register class to use greedy's global heuristic for all
+  // registers in this class. This should more aggressively try to
+  // avoid spilling in pathological cases.
+  bit GlobalPriority = false;
+
   // Generate register pressure set for this register class and any class
   // synthesized from it. Set to 0 to inhibit unneeded pressure sets.
   bit GeneratePressureSet = true;
 
   // Weight override for register pressure calculation. This is the value
   // TargetRegisterClass::getRegClassWeight() will return. The weight is in
   // units of pressure for this register class. If unset tablegen will
   // calculate a weight based on a number of register units in this register

llvm/lib/CodeGen/RegAllocGreedy.cpp

if (Stage == RS_Split) {
     // the reverse order that they came in.
     // TODO: Make this a member variable and probably do something about hints.
     static unsigned MemOp = 0;
     Prio = MemOp++;
   } else {
     // Giant live ranges fall back to the global assignment heuristic, which
     // prevents excessive spilling in pathological cases.
     const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
-    bool ForceGlobal = !ReverseLocalAssignment &&
+    bool ForceGlobal = RC.GlobalPriority ||
+                       (!ReverseLocalAssignment &&
                         (Size / SlotIndex::InstrDist) >
-                           (2 * RegClassInfo.getNumAllocatableRegs(&RC));
+                            (2 * RegClassInfo.getNumAllocatableRegs(&RC)));
     unsigned GlobalBit = 0;
 
     if (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 (!ReverseLocalAssignment)
         Prio = LI.beginIndex().getApproxInstrDistance(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().getApproxInstrDistance(LI.endIndex());
       }
     } 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 = Size;
       GlobalBit = 1;
     }
+
+    // Priority bit layout:
+    // 31 RS_Assign priority
+    // 30 Preference priority
+    // if (RegClassPriorityTrumpsGlobalness)
+    //   29-25 AllocPriority
+    //   24 GlobalBit
+    // else
+    //   29 Global bit
+    //   28-24 AllocPriority
+    // 0-23 Size/Instr distance
+
+    // Clamp the size to fit with the priority masking scheme
+    Prio = std::min(Prio, (unsigned)maxUIntN(24));
+    assert(isUInt<5>(RC.AllocationPriority) && "allocation priority overflow");
+
     if (RegClassPriorityTrumpsGlobalness)
       Prio |= RC.AllocationPriority << 25 | GlobalBit << 24;
     else
       Prio |= GlobalBit << 29 | RC.AllocationPriority << 24;
 
     // Mark a higher bit to prioritize global and local above RS_Split.
     Prio |= (1u << 31);
 

llvm/lib/Target/PowerPC/PPCRegisterInfoMMA.td

let SubRegIndices = [sub_pair0, sub_pair1] in {
   def ACC3 : ACC<3, "acc3", [VSRp6, VSRp7]>, DwarfRegNum<[-1, -1]>;
   def ACC4 : ACC<4, "acc4", [VSRp8, VSRp9]>, DwarfRegNum<[-1, -1]>;
   def ACC5 : ACC<5, "acc5", [VSRp10, VSRp11]>, DwarfRegNum<[-1, -1]>;
   def ACC6 : ACC<6, "acc6", [VSRp12, VSRp13]>, DwarfRegNum<[-1, -1]>;
   def ACC7 : ACC<7, "acc7", [VSRp14, VSRp15]>, DwarfRegNum<[-1, -1]>;
 }
 def ACCRC : RegisterClass<"PPC", [v512i1], 128, (add ACC0, ACC1, ACC2, ACC3,
                                                       ACC4, ACC5, ACC6, ACC7)> {
-  // The AllocationPriority is in the range [0, 63]. Assigned the ACC registers
+  // The AllocationPriority is in the range [0, 31]. Assigned the ACC registers
   // the highest possible priority in this range to force the register allocator
   // to assign these registers first. This is done because the ACC registers
   // must represent 4 advacent vector registers. For example ACC1 must be
-  // VS4 - VS7. The value here must be at least 32 as we want to allocate
-  // these registers even before we allocate global ranges.
-  let AllocationPriority = 63;
+  // VS4 - VS7.
+  let AllocationPriority = 31;
+
+  // We want to allocate these registers even before we allocate
+  // global ranges.
+  let GlobalPriority = true;
   let Size = 512;
 }
 
 let SubRegIndices = [sub_pair0, sub_pair1] in {
   def UACC0 : UACC<0, "acc0", [VSRp0, VSRp1]>, DwarfRegNum<[-1, -1]>;
   def UACC1 : UACC<1, "acc1", [VSRp2, VSRp3]>, DwarfRegNum<[-1, -1]>;
   def UACC2 : UACC<2, "acc2", [VSRp4, VSRp5]>, DwarfRegNum<[-1, -1]>;
   def UACC3 : UACC<3, "acc3", [VSRp6, VSRp7]>, DwarfRegNum<[-1, -1]>;
   def UACC4 : UACC<4, "acc4", [VSRp8, VSRp9]>, DwarfRegNum<[-1, -1]>;
   def UACC5 : UACC<5, "acc5", [VSRp10, VSRp11]>, DwarfRegNum<[-1, -1]>;
   def UACC6 : UACC<6, "acc6", [VSRp12, VSRp13]>, DwarfRegNum<[-1, -1]>;
   def UACC7 : UACC<7, "acc7", [VSRp14, VSRp15]>, DwarfRegNum<[-1, -1]>;
 }
 def UACCRC : RegisterClass<"PPC", [v512i1], 128,
                            (add UACC0, UACC1, UACC2, UACC3,
                                 UACC4, UACC5, UACC6, UACC7)> {
   // The AllocationPriority for the UACC registers is still high and must be at
   // least 32 as we want to allocate these registers before we allocate other
   // global ranges. The value must be less than the AllocationPriority of the
   // ACC registers.
-  let AllocationPriority = 36;
+  let AllocationPriority = 4;
+  let GlobalPriority = true;
   let Size = 512;
 }
 
 // FIXME: This allocation order may increase stack frame size when allocating
 // non-volatile registers.
 //
 // Placing Altivec registers first and allocate the rest as underlying VSX
 // ones, to reduce interference with accumulator registers (lower 32 VSRs).

llvm/utils/TableGen/CodeGenRegisters.h

public:
     unsigned EnumValue;
     StringRef Namespace;
     SmallVector<ValueTypeByHwMode, 4> VTs;
     RegSizeInfoByHwMode RSI;
     int CopyCost;
     bool Allocatable;
     StringRef AltOrderSelect;
     uint8_t AllocationPriority;
+    bool GlobalPriority;
     uint8_t TSFlags;
     /// Contains the combination of the lane masks of all subregisters.
     LaneBitmask LaneMask;
     /// True if there are at least 2 subregisters which do not interfere.
     bool HasDisjunctSubRegs;
     bool CoveredBySubRegs;
     /// A register class is artificial if all its members are artificial.
     bool Artificial;

llvm/utils/TableGen/CodeGenRegisters.cpp

if (!RSI.hasDefault()) {
     RI.SpillAlignment = R->getValueAsInt("Alignment");
     RSI.insertRegSizeForMode(DefaultMode, RI);
   }
 
   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]");
+  if (!isUInt<5>(AllocationPriority))
+    PrintFatalError(R->getLoc(), "AllocationPriority out of range [0,31]");
   this->AllocationPriority = AllocationPriority;
 
+  GlobalPriority = R->getValueAsBit("GlobalPriority");
+
   BitsInit *TSF = R->getValueAsBitsInit("TSFlags");
   for (unsigned I = 0, E = TSF->getNumBits(); I != E; ++I) {
     BitInit *Bit = cast<BitInit>(TSF->getBit(I));
     TSFlags |= uint8_t(Bit->getValue()) << I;
   }
 }
 
 // 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), TheDef(nullptr), Name(std::string(Name)),
       TopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1), RSI(Props.RSI),
-      CopyCost(0), Allocatable(true), AllocationPriority(0), TSFlags(0) {
+      CopyCost(0), Allocatable(true), AllocationPriority(0),
+      GlobalPriority(false), TSFlags(0) {
   Artificial = true;
   GeneratePressureSet = false;
   for (const auto R : Members) {
     TopoSigs.set(R->getTopoSig());
     Artificial &= R->Artificial;
   }
 }
 
void CodeGenRegisterClass::inheritProperties(CodeGenRegBank &RegBank) {
   VTs = Super.VTs;
   CopyCost = Super.CopyCost;
   // Check for allocatable superclasses.
   Allocatable = any_of(SuperClasses, [&](const CodeGenRegisterClass *S) {
     return S->Allocatable;
   });
   AltOrderSelect = Super.AltOrderSelect;
   AllocationPriority = Super.AllocationPriority;
+  GlobalPriority = Super.GlobalPriority;
   TSFlags = Super.TSFlags;
   GeneratePressureSet |= Super.GeneratePressureSet;
 
   // Copy all allocation orders, filter out foreign registers from the larger
   // super-class.
   Orders.resize(Super.Orders.size());
   for (unsigned i = 0, ie = Super.Orders.size(); i != ie; ++i)
     for (unsigned j = 0, je = Super.Orders[i].size(); j != je; ++j)

llvm/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    "
          << RC.getName() << "SubClassMask,\n    SuperRegIdxSeqs + "
          << SuperRegIdxSeqs.get(SuperRegIdxLists[RC.EnumValue]) << ",\n    ";
       printMask(OS, RC.LaneMask);
       OS << ",\n    " << (unsigned)RC.AllocationPriority << ",\n    "
+         << (RC.GlobalPriority ? "true" : "false") << ",\n    "
          << format("0x%02x", RC.TSFlags) << ", /* TSFlags */\n    "
-         << (RC.HasDisjunctSubRegs?"true":"false")
+         << (RC.HasDisjunctSubRegs ? "true" : "false")
          << ", /* HasDisjunctSubRegs */\n    "
-         << (RC.CoveredBySubRegs?"true":"false")
+         << (RC.CoveredBySubRegs ? "true" : "false")
          << ", /* CoveredBySubRegs */\n    ";
       if (RC.getSuperClasses().empty())
         OS << "NullRegClasses,\n    ";
       else
         OS << RC.getName() << "Superclasses,\n    ";
       if (RC.AltOrderSelect.empty())
         OS << "nullptr\n";
       else