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