llvm/lib/CodeGen/CalcSpillWeights.cpp

   1 //===- CalcSpillWeights.cpp -----------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/CodeGen/CalcSpillWeights.h"
  10 #include "llvm/ADT/SmallPtrSet.h"
  11 #include "llvm/CodeGen/LiveInterval.h"
  12 #include "llvm/CodeGen/LiveIntervals.h"
  13 #include "llvm/CodeGen/MachineFunction.h"
  14 #include "llvm/CodeGen/MachineInstr.h"
  15 #include "llvm/CodeGen/MachineLoopInfo.h"
  16 #include "llvm/CodeGen/MachineOperand.h"
  17 #include "llvm/CodeGen/MachineRegisterInfo.h"
  18 #include "llvm/CodeGen/StackMaps.h"
  19 #include "llvm/CodeGen/TargetInstrInfo.h"
  20 #include "llvm/CodeGen/TargetRegisterInfo.h"
  21 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  22 #include "llvm/CodeGen/VirtRegMap.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/MathExtras.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include <cassert>
  27 #include <tuple>
  28
  29 using namespace llvm;
  30
  31 #define DEBUG_TYPE "calcspillweights"
  32
  33 void VirtRegAuxInfo::calculateSpillWeightsAndHints() {
  34   LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
  35                     << "********** Function: " << MF.getName() << '\n');
  36
  37   MachineRegisterInfo &MRI = MF.getRegInfo();
  38   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
  39     Register Reg = Register::index2VirtReg(I);
  40     if (MRI.reg_nodbg_empty(Reg))
  41       continue;
  42     calculateSpillWeightAndHint(LIS.getInterval(Reg));
  43   }
  44 }
  45
  46 // Return the preferred allocation register for reg, given a COPY instruction.
  47 Register VirtRegAuxInfo::copyHint(const MachineInstr *MI, unsigned Reg,
  48                                   const TargetRegisterInfo &TRI,
  49                                   const MachineRegisterInfo &MRI) {
  50   unsigned Sub, HSub;
  51   Register HReg;
  52   if (MI->getOperand(0).getReg() == Reg) {
  53     Sub = MI->getOperand(0).getSubReg();
  54     HReg = MI->getOperand(1).getReg();
  55     HSub = MI->getOperand(1).getSubReg();
  56   } else {
  57     Sub = MI->getOperand(1).getSubReg();
  58     HReg = MI->getOperand(0).getReg();
  59     HSub = MI->getOperand(0).getSubReg();
  60   }
  61
  62   if (!HReg)
  63     return 0;
  64
  65   if (HReg.isVirtual())
  66     return Sub == HSub ? HReg : Register();
  67
  68   const TargetRegisterClass *RC = MRI.getRegClass(Reg);
  69   MCRegister CopiedPReg = HSub ? TRI.getSubReg(HReg, HSub) : HReg.asMCReg();
  70   if (RC->contains(CopiedPReg))
  71     return CopiedPReg;
  72
  73   // Check if reg:sub matches so that a super register could be hinted.
  74   if (Sub)
  75     return TRI.getMatchingSuperReg(CopiedPReg, Sub, RC);
  76
  77   return 0;
  78 }
  79
  80 // Check if all values in LI are rematerializable
  81 bool VirtRegAuxInfo::isRematerializable(const LiveInterval &LI,
  82                                         const LiveIntervals &LIS,
  83                                         const VirtRegMap &VRM,
  84                                         const TargetInstrInfo &TII) {
  85   Register Reg = LI.reg();
  86   Register Original = VRM.getOriginal(Reg);
  87   for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
  88        I != E; ++I) {
  89     const VNInfo *VNI = *I;
  90     if (VNI->isUnused())
  91       continue;
  92     if (VNI->isPHIDef())
  93       return false;
  94
  95     MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
  96     assert(MI && "Dead valno in interval");
  97
  98     // Trace copies introduced by live range splitting.  The inline
  99     // spiller can rematerialize through these copies, so the spill
 100     // weight must reflect this.
 101     while (TII.isFullCopyInstr(*MI)) {
 102       // The copy destination must match the interval register.
 103       if (MI->getOperand(0).getReg() != Reg)
 104         return false;
 105
 106       // Get the source register.
 107       Reg = MI->getOperand(1).getReg();
 108
 109       // If the original (pre-splitting) registers match this
 110       // copy came from a split.
 111       if (!Reg.isVirtual() || VRM.getOriginal(Reg) != Original)
 112         return false;
 113
 114       // Follow the copy live-in value.
 115       const LiveInterval &SrcLI = LIS.getInterval(Reg);
 116       LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
 117       VNI = SrcQ.valueIn();
 118       assert(VNI && "Copy from non-existing value");
 119       if (VNI->isPHIDef())
 120         return false;
 121       MI = LIS.getInstructionFromIndex(VNI->def);
 122       assert(MI && "Dead valno in interval");
 123     }
 124
 125     if (!TII.isTriviallyReMaterializable(*MI))
 126       return false;
 127   }
 128   return true;
 129 }
 130
 131 bool VirtRegAuxInfo::isLiveAtStatepointVarArg(LiveInterval &LI) {
 132   return any_of(VRM.getRegInfo().reg_operands(LI.reg()),
 133                 [](MachineOperand &MO) {
 134     MachineInstr *MI = MO.getParent();
 135     if (MI->getOpcode() != TargetOpcode::STATEPOINT)
 136       return false;
 137     return StatepointOpers(MI).getVarIdx() <= MO.getOperandNo();
 138   });
 139 }
 140
 141 void VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &LI) {
 142   float Weight = weightCalcHelper(LI);
 143   // Check if unspillable.
 144   if (Weight < 0)
 145     return;
 146   LI.setWeight(Weight);
 147 }
 148
 149 static bool canMemFoldInlineAsm(LiveInterval &LI,
 150                                 const MachineRegisterInfo &MRI) {
 151   for (const MachineOperand &MO : MRI.reg_operands(LI.reg())) {
 152     const MachineInstr *MI = MO.getParent();
 153     if (MI->isInlineAsm() && MI->mayFoldInlineAsmRegOp(MI->getOperandNo(&MO)))
 154       return true;
 155   }
 156
 157   return false;
 158 }
 159
 160 float VirtRegAuxInfo::weightCalcHelper(LiveInterval &LI, SlotIndex *Start,
 161                                        SlotIndex *End) {
 162   MachineRegisterInfo &MRI = MF.getRegInfo();
 163   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
 164   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
 165   MachineBasicBlock *MBB = nullptr;
 166   float TotalWeight = 0;
 167   unsigned NumInstr = 0; // Number of instructions using LI
 168   SmallPtrSet<MachineInstr *, 8> Visited;
 169
 170   std::pair<unsigned, Register> TargetHint = MRI.getRegAllocationHint(LI.reg());
 171
 172   if (LI.isSpillable()) {
 173     Register Reg = LI.reg();
 174     Register Original = VRM.getOriginal(Reg);
 175     const LiveInterval &OrigInt = LIS.getInterval(Original);
 176     // li comes from a split of OrigInt. If OrigInt was marked
 177     // as not spillable, make sure the new interval is marked
 178     // as not spillable as well.
 179     if (!OrigInt.isSpillable())
 180       LI.markNotSpillable();
 181   }
 182
 183   // Don't recompute spill weight for an unspillable register.
 184   bool IsSpillable = LI.isSpillable();
 185
 186   bool IsLocalSplitArtifact = Start && End;
 187
 188   // Do not update future local split artifacts.
 189   bool ShouldUpdateLI = !IsLocalSplitArtifact;
 190
 191   if (IsLocalSplitArtifact) {
 192     MachineBasicBlock *LocalMBB = LIS.getMBBFromIndex(*End);
 193     assert(LocalMBB == LIS.getMBBFromIndex(*Start) &&
 194            "start and end are expected to be in the same basic block");
 195
 196     // Local split artifact will have 2 additional copy instructions and they
 197     // will be in the same BB.
 198     // localLI = COPY other
 199     // ...
 200     // other   = COPY localLI
 201     TotalWeight +=
 202         LiveIntervals::getSpillWeight(true, false, &MBFI, LocalMBB, PSI);
 203     TotalWeight +=
 204         LiveIntervals::getSpillWeight(false, true, &MBFI, LocalMBB, PSI);
 205
 206     NumInstr += 2;
 207   }
 208
 209   // CopyHint is a sortable hint derived from a COPY instruction.
 210   struct CopyHint {
 211     Register Reg;
 212     float Weight;
 213     CopyHint(Register R, float W) : Reg(R), Weight(W) {}
 214     bool operator<(const CopyHint &Rhs) const {
 215       // Always prefer any physreg hint.
 216       if (Reg.isPhysical() != Rhs.Reg.isPhysical())
 217         return Reg.isPhysical();
 218       if (Weight != Rhs.Weight)
 219         return (Weight > Rhs.Weight);
 220       return Reg.id() < Rhs.Reg.id(); // Tie-breaker.
 221     }
 222   };
 223
 224   bool IsExiting = false;
 225   SmallDenseMap<Register, float, 8> Hint;
 226   for (MachineRegisterInfo::reg_instr_nodbg_iterator
 227            I = MRI.reg_instr_nodbg_begin(LI.reg()),
 228            E = MRI.reg_instr_nodbg_end();
 229        I != E;) {
 230     MachineInstr *MI = &*(I++);
 231
 232     // For local split artifacts, we are interested only in instructions between
 233     // the expected start and end of the range.
 234     SlotIndex SI = LIS.getInstructionIndex(*MI);
 235     if (IsLocalSplitArtifact && ((SI < *Start) || (SI > *End)))
 236       continue;
 237
 238     NumInstr++;
 239     bool identityCopy = false;
 240     auto DestSrc = TII.isCopyInstr(*MI);
 241     if (DestSrc) {
 242       const MachineOperand *DestRegOp = DestSrc->Destination;
 243       const MachineOperand *SrcRegOp = DestSrc->Source;
 244       identityCopy = DestRegOp->getReg() == SrcRegOp->getReg() &&
 245                      DestRegOp->getSubReg() == SrcRegOp->getSubReg();
 246     }
 247
 248     if (identityCopy || MI->isImplicitDef())
 249       continue;
 250     if (!Visited.insert(MI).second)
 251       continue;
 252
 253     // For terminators that produce values, ask the backend if the register is
 254     // not spillable.
 255     if (TII.isUnspillableTerminator(MI) &&
 256         MI->definesRegister(LI.reg(), /*TRI=*/nullptr)) {
 257       LI.markNotSpillable();
 258       return -1.0f;
 259     }
 260
 261     // Force Weight onto the stack so that x86 doesn't add hidden precision.
 262     stack_float_t Weight = 1.0f;
 263     if (IsSpillable) {
 264       // Get loop info for mi.
 265       if (MI->getParent() != MBB) {
 266         MBB = MI->getParent();
 267         const MachineLoop *Loop = Loops.getLoopFor(MBB);
 268         IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;
 269       }
 270
 271       // Calculate instr weight.
 272       bool Reads, Writes;
 273       std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());
 274       Weight = LiveIntervals::getSpillWeight(Writes, Reads, &MBFI, *MI, PSI);
 275
 276       // Give extra weight to what looks like a loop induction variable update.
 277       if (Writes && IsExiting && LIS.isLiveOutOfMBB(LI, MBB))
 278         Weight *= 3;
 279
 280       TotalWeight += Weight;
 281     }
 282
 283     // Get allocation hints from copies.
 284     if (!TII.isCopyInstr(*MI))
 285       continue;
 286     Register HintReg = copyHint(MI, LI.reg(), TRI, MRI);
 287     if (HintReg && (HintReg.isVirtual() || MRI.isAllocatable(HintReg)))
 288       Hint[HintReg] += Weight;
 289   }
 290
 291   // Pass all the sorted copy hints to mri.
 292   if (ShouldUpdateLI && Hint.size()) {
 293     // Remove a generic hint if previously added by target.
 294     if (TargetHint.first == 0 && TargetHint.second)
 295       MRI.clearSimpleHint(LI.reg());
 296
 297     // Don't add the target-type hint again.
 298     Register SkipReg = TargetHint.first != 0 ? TargetHint.second : Register();
 299     SmallVector<CopyHint, 8> RegHints;
 300     for (const auto &[Reg, Weight] : Hint) {
 301       if (Reg != SkipReg)
 302         RegHints.emplace_back(Reg, Weight);
 303     }
 304     sort(RegHints);
 305     for (const auto &[Reg, Weight] : RegHints)
 306       MRI.addRegAllocationHint(LI.reg(), Reg);
 307
 308     // Weakly boost the spill weight of hinted registers.
 309     TotalWeight *= 1.01F;
 310   }
 311
 312   // If the live interval was already unspillable, leave it that way.
 313   if (!IsSpillable)
 314     return -1.0;
 315
 316   // Mark li as unspillable if all live ranges are tiny and the interval
 317   // is not live at any reg mask.  If the interval is live at a reg mask
 318   // spilling may be required. If li is live as use in statepoint instruction
 319   // spilling may be required due to if we mark interval with use in statepoint
 320   // as not spillable we are risky to end up with no register to allocate.
 321   // At the same time STATEPOINT instruction is perfectly fine to have this
 322   // operand on stack, so spilling such interval and folding its load from stack
 323   // into instruction itself makes perfect sense.
 324   if (ShouldUpdateLI && LI.isZeroLength(LIS.getSlotIndexes()) &&
 325       !LI.isLiveAtIndexes(LIS.getRegMaskSlots()) &&
 326       !isLiveAtStatepointVarArg(LI) && !canMemFoldInlineAsm(LI, MRI)) {
 327     LI.markNotSpillable();
 328     return -1.0;
 329   }
 330
 331   // If all of the definitions of the interval are re-materializable,
 332   // it is a preferred candidate for spilling.
 333   // FIXME: this gets much more complicated once we support non-trivial
 334   // re-materialization.
 335   if (isRematerializable(LI, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
 336     TotalWeight *= 0.5F;
 337
 338   if (IsLocalSplitArtifact)
 339     return normalize(TotalWeight, Start->distance(*End), NumInstr);
 340   return normalize(TotalWeight, LI.getSize(), NumInstr);
 341 }