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