[Regalloc] Generate and store multiple regalloc hints.

MachineRegisterInfo used to allow just one regalloc hint per virtual
register. This patch extends this to a vector of regalloc hints, which is
filled in by common code with sorted copy hints. Such hints will make for
more ID copies that can be removed.

NB! This improvement is currently (and hopefully temporarily) *disabled* by
default, except for SystemZ. The only reason for this is the big impact this
has on tests, which has unfortunately proven unmanageable. It was a long
while since all the tests were updated and just waiting for review (which
didn't happen), but now targets have to enable this themselves
instead. Several targets could get a head-start by downloading the tests
updates from the Phabricator review. Thanks to those who helped, and sorry
you now have to do this step yourselves.

This should be an improvement generally for any target!

The target may still create its own hint, in which case this has highest
priority and is stored first in the vector. If it has target-type, it will
not be recomputed, as per the previous behaviour.

The temporary hook enableMultipleCopyHints() will be removed as soon as all
targets return true.

Review: Quentin Colombet, Ulrich Weigand.
https://reviews.llvm.org/D38128

llvm-svn: 319754

2 files changed, 98 insertions, 54 deletions

diff --git a/llvm/lib/CodeGen/CalcSpillWeights.cpp b/llvm/lib/CodeGen/CalcSpillWeights.cpp
index 6a6ec461cf7..f52a068a4cd 100644
--- a/llvm/lib/CodeGen/CalcSpillWeights.cpp
+++ b/llvm/lib/CodeGen/CalcSpillWeights.cpp
@@ -70,13 +70,24 @@ static unsigned copyHint(const MachineInstr *mi, unsigned reg,
     return sub == hsub ? hreg : 0;
 
   const TargetRegisterClass *rc = mri.getRegClass(reg);
+  if (!tri.enableMultipleCopyHints()) {
+    // Only allow physreg hints in rc.
+    if (sub == 0)
+      return rc->contains(hreg) ? hreg : 0;
 
-  // Only allow physreg hints in rc.
-  if (sub == 0)
-    return rc->contains(hreg) ? hreg : 0;
+    // reg:sub should match the physreg hreg.
+    return tri.getMatchingSuperReg(hreg, sub, rc);
+  }
+
+  unsigned CopiedPReg = (hsub ? tri.getSubReg(hreg, hsub) : hreg);
+  if (rc->contains(CopiedPReg))
+    return CopiedPReg;
+
+  // Check if reg:sub matches so that a super register could be hinted.
+  if (sub)
+    return tri.getMatchingSuperReg(CopiedPReg, sub, rc);
 
-  // reg:sub should match the physreg hreg.
-  return tri.getMatchingSuperReg(hreg, sub, rc);
+  return 0;
 }
 
 // Check if all values in LI are rematerializable
@@ -157,12 +168,7 @@ float VirtRegAuxInfo::weightCalcHelper(LiveInterval &li, SlotIndex *start,
   unsigned numInstr = 0; // Number of instructions using li
   SmallPtrSet<MachineInstr*, 8> visited;
 
-  // Find the best physreg hint and the best virtreg hint.
-  float bestPhys = 0, bestVirt = 0;
-  unsigned hintPhys = 0, hintVirt = 0;
-
-  // Don't recompute a target specific hint.
-  bool noHint = mri.getRegAllocationHint(li.reg).first != 0;
+  std::pair<unsigned, unsigned> TargetHint = mri.getRegAllocationHint(li.reg);
 
   // Don't recompute spill weight for an unspillable register.
   bool Spillable = li.isSpillable();
@@ -188,6 +194,36 @@ float VirtRegAuxInfo::weightCalcHelper(LiveInterval &li, SlotIndex *start,
     numInstr += 2;
   }
 
+  // CopyHint is a sortable hint derived from a COPY instruction.
+  struct CopyHint {
+    unsigned Reg;
+    float Weight;
+    bool IsPhys;
+    unsigned HintOrder;
+    CopyHint(unsigned R, float W, bool P, unsigned HR) :
+      Reg(R), Weight(W), IsPhys(P), HintOrder(HR) {}
+    bool operator<(const CopyHint &rhs) const {
+      // Always prefer any physreg hint.
+      if (IsPhys != rhs.IsPhys)
+        return (IsPhys && !rhs.IsPhys);
+      if (Weight != rhs.Weight)
+        return (Weight > rhs.Weight);
+
+      // This is just a temporary way to achive NFC for targets that don't
+      // enable multiple copy hints. HintOrder should be removed when all
+      // targets return true in enableMultipleCopyHints().
+      return (HintOrder < rhs.HintOrder);
+
+#if 0 // Should replace the HintOrder check, see above.
+      // (just for the purpose of maintaining the set)
+      return Reg < rhs.Reg;
+#endif
+    }
+  };
+  std::set<CopyHint> CopyHints;
+
+  // Temporary: see comment for HintOrder above.
+  unsigned CopyHintOrder = 0;
   for (MachineRegisterInfo::reg_instr_iterator
        I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end();
        I != E; ) {
@@ -227,7 +263,8 @@ float VirtRegAuxInfo::weightCalcHelper(LiveInterval &li, SlotIndex *start,
     }
 
     // Get allocation hints from copies.
-    if (noHint || !mi->isCopy())
+    if (!mi->isCopy() ||
+        (TargetHint.first != 0 && !tri.enableMultipleCopyHints()))
       continue;
     unsigned hint = copyHint(mi, li.reg, tri, mri);
     if (!hint)
@@ -237,28 +274,30 @@ float VirtRegAuxInfo::weightCalcHelper(LiveInterval &li, SlotIndex *start,
     //
     // FIXME: we probably shouldn't use floats at all.
     volatile float hweight = Hint[hint] += weight;
-    if (TargetRegisterInfo::isPhysicalRegister(hint)) {
-      if (hweight > bestPhys && mri.isAllocatable(hint)) {
-        bestPhys = hweight;
-        hintPhys = hint;
-      }
-    } else {
-      if (hweight > bestVirt) {
-        bestVirt = hweight;
-        hintVirt = hint;
-      }
-    }
+    if (TargetRegisterInfo::isVirtualRegister(hint) || mri.isAllocatable(hint))
+      CopyHints.insert(CopyHint(hint, hweight, tri.isPhysicalRegister(hint),
+                     (tri.enableMultipleCopyHints() ? hint : CopyHintOrder++)));
   }
 
   Hint.clear();
 
-  // Always prefer the physreg hint.
-  if (updateLI) {
-    if (unsigned hint = hintPhys ? hintPhys : hintVirt) {
-      mri.setRegAllocationHint(li.reg, 0, hint);
-      // Weakly boost the spill weight of hinted registers.
-      totalWeight *= 1.01F;
+  // Pass all the sorted copy hints to mri.
+  if (updateLI && CopyHints.size()) {
+    // Remove a generic hint if previously added by target.
+    if (TargetHint.first == 0 && TargetHint.second)
+      mri.clearSimpleHint(li.reg);
+
+    for (auto &Hint : CopyHints) {
+      if (TargetHint.first != 0 && Hint.Reg == TargetHint.second)
+        // Don't add again the target-type hint.
+        continue;
+      mri.addRegAllocationHint(li.reg, Hint.Reg);
+      if (!tri.enableMultipleCopyHints())
+        break;
     }
+
+    // Weakly boost the spill weight of hinted registers.
+    totalWeight *= 1.01F;
   }
 
   // If the live interval was already unspillable, leave it that way.
diff --git a/llvm/lib/CodeGen/TargetRegisterInfo.cpp b/llvm/lib/CodeGen/TargetRegisterInfo.cpp
index f4e5583cbe7..dfda313f233 100644
--- a/llvm/lib/CodeGen/TargetRegisterInfo.cpp
+++ b/llvm/lib/CodeGen/TargetRegisterInfo.cpp
@@ -373,31 +373,36 @@ TargetRegisterInfo::getRegAllocationHints(unsigned VirtReg,
                                           const VirtRegMap *VRM,
                                           const LiveRegMatrix *Matrix) const {
   const MachineRegisterInfo &MRI = MF.getRegInfo();
-  std::pair<unsigned, unsigned> Hint = MRI.getRegAllocationHint(VirtReg);
-
-  // Hints with HintType != 0 were set by target-dependent code.
-  // Such targets must provide their own implementation of
-  // TRI::getRegAllocationHints to interpret those hint types.
-  assert(Hint.first == 0 && "Target must implement TRI::getRegAllocationHints");
-
-  // Target-independent hints are either a physical or a virtual register.
-  unsigned Phys = Hint.second;
-  if (VRM && isVirtualRegister(Phys))
-    Phys = VRM->getPhys(Phys);
-
-  // Check that Phys is a valid hint in VirtReg's register class.
-  if (!isPhysicalRegister(Phys))
-    return false;
-  if (MRI.isReserved(Phys))
-    return false;
-  // Check that Phys is in the allocation order. We shouldn't heed hints
-  // from VirtReg's register class if they aren't in the allocation order. The
-  // target probably has a reason for removing the register.
-  if (!is_contained(Order, Phys))
-    return false;
-
-  // All clear, tell the register allocator to prefer this register.
-  Hints.push_back(Phys);
+  const std::pair<unsigned, SmallVector<unsigned, 4>> &Hints_MRI =
+    MRI.getRegAllocationHints(VirtReg);
+
+  // First hint may be a target hint.
+  bool Skip = (Hints_MRI.first != 0);
+  for (auto Reg : Hints_MRI.second) {
+    if (Skip) {
+      Skip = false;
+      continue;
+    }
+
+    // Target-independent hints are either a physical or a virtual register.
+    unsigned Phys = Reg;
+    if (VRM && isVirtualRegister(Phys))
+      Phys = VRM->getPhys(Phys);
+
+    // Check that Phys is a valid hint in VirtReg's register class.
+    if (!isPhysicalRegister(Phys))
+      continue;
+    if (MRI.isReserved(Phys))
+      continue;
+    // Check that Phys is in the allocation order. We shouldn't heed hints
+    // from VirtReg's register class if they aren't in the allocation order. The
+    // target probably has a reason for removing the register.
+    if (!is_contained(Order, Phys))
+      continue;
+
+    // All clear, tell the register allocator to prefer this register.
+    Hints.push_back(Phys);
+  }
   return false;
 }