Precompute some information about register costs.

Remember the minimum cost of the registers in an allocation order and
the number of registers at the end of the allocation order that have the
same cost per use.

This information can be used to limit the search space for
RAGreedy::tryEvict() when looking for a cheaper register.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172280 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/CodeGen/RegisterClassInfo.h b/include/llvm/CodeGen/RegisterClassInfo.h
index 12bd1c61d25fc24f2906ed6b20b280ca63fac3e6..3ad22e65c8c7deadfd5283c27a86ddaa541ee86c 100644 (file)
--- a/include/llvm/CodeGen/RegisterClassInfo.h
+++ b/include/llvm/CodeGen/RegisterClassInfo.h
@@ -29,9 +29,14 @@ class RegisterClassInfo {
     unsigned Tag;
     unsigned NumRegs;
     bool ProperSubClass;
+    uint8_t MinCost;
+    uint16_t LastCostChange;
     OwningArrayPtr<MCPhysReg> Order;
 
-    RCInfo() : Tag(0), NumRegs(0), ProperSubClass(false) {}
+    RCInfo()
+      : Tag(0), NumRegs(0), ProperSubClass(false), MinCost(0),
+        LastCostChange(0) {}
+
     operator ArrayRef<MCPhysReg>() const {
       return makeArrayRef(Order.get(), NumRegs);
     }
@@ -106,6 +111,21 @@ public:
       return CalleeSaved[N-1];
     return 0;
   }
+
+  /// Get the minimum register cost in RC's allocation order.
+  /// This is the smallest value returned by TRI->getCostPerUse(Reg) for all
+  /// the registers in getOrder(RC).
+  unsigned getMinCost(const TargetRegisterClass *RC) {
+    return get(RC).MinCost;
+  }
+
+  /// Get the position of the last cost change in getOrder(RC).
+  ///
+  /// All registers in getOrder(RC).slice(getLastCostChange(RC)) will have the
+  /// same cost according to TRI->getCostPerUse().
+  unsigned getLastCostChange(const TargetRegisterClass *RC) {
+    return get(RC).LastCostChange;
+  }
 };
 } // end namespace llvm
 

diff --git a/lib/CodeGen/RegisterClassInfo.cpp b/lib/CodeGen/RegisterClassInfo.cpp
index 078a0df9151a4541b1c30aa8f6abba61e06ace41..87382d8f7c42ec35a5b9e41fbc2c76e06365f778 100644 (file)
--- a/lib/CodeGen/RegisterClassInfo.cpp
+++ b/lib/CodeGen/RegisterClassInfo.cpp
@@ -83,6 +83,9 @@ void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
 
   unsigned N = 0;
   SmallVector<MCPhysReg, 16> CSRAlias;
+  unsigned MinCost = 0xff;
+  unsigned LastCost = ~0u;
+  unsigned LastCostChange = 0;
 
   // FIXME: Once targets reserve registers instead of removing them from the
   // allocation order, we can simply use begin/end here.
@@ -92,17 +95,31 @@ void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
     // Remove reserved registers from the allocation order.
     if (Reserved.test(PhysReg))
       continue;
+    unsigned Cost = TRI->getCostPerUse(PhysReg);
+    MinCost = std::min(MinCost, Cost);
+
     if (CSRNum[PhysReg])
       // PhysReg aliases a CSR, save it for later.
       CSRAlias.push_back(PhysReg);
-    else
+    else {
+      if (Cost != LastCost)
+        LastCostChange = N;
       RCI.Order[N++] = PhysReg;
+      LastCost = Cost;
+    }
   }
   RCI.NumRegs = N + CSRAlias.size();
   assert (RCI.NumRegs <= NumRegs && "Allocation order larger than regclass");
 
   // CSR aliases go after the volatile registers, preserve the target's order.
-  std::copy(CSRAlias.begin(), CSRAlias.end(), &RCI.Order[N]);
+  for (unsigned i = 0, e = CSRAlias.size(); i != e; ++i) {
+    unsigned PhysReg = CSRAlias[i];
+    unsigned Cost = TRI->getCostPerUse(PhysReg);
+    if (Cost != LastCost)
+      LastCostChange = N;
+    RCI.Order[N++] = PhysReg;
+    LastCost = Cost;
+  }
 
   // Register allocator stress test.  Clip register class to N registers.
   if (StressRA && RCI.NumRegs > StressRA)
@@ -113,6 +130,9 @@ void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
     if (Super != RC && getNumAllocatableRegs(Super) > RCI.NumRegs)
       RCI.ProperSubClass = true;
 
+  RCI.MinCost = uint8_t(MinCost);
+  RCI.LastCostChange = LastCostChange;
+
   DEBUG({
     dbgs() << "AllocationOrder(" << RC->getName() << ") = [";
     for (unsigned I = 0; I != RCI.NumRegs; ++I)