1 //===- LiveRegMatrix.cpp - Track register interference --------------------===// 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 // This file defines the LiveRegMatrix analysis pass. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/CodeGen/LiveRegMatrix.h" 14 #include "RegisterCoalescer.h" 15 #include "llvm/ADT/Statistic.h" 16 #include "llvm/CodeGen/LiveInterval.h" 17 #include "llvm/CodeGen/LiveIntervalUnion.h" 18 #include "llvm/CodeGen/LiveIntervals.h" 19 #include "llvm/CodeGen/MachineFunction.h" 20 #include "llvm/CodeGen/TargetRegisterInfo.h" 21 #include "llvm/CodeGen/TargetSubtargetInfo.h" 22 #include "llvm/CodeGen/VirtRegMap.h" 23 #include "llvm/InitializePasses.h" 24 #include "llvm/MC/LaneBitmask.h" 25 #include "llvm/MC/MCRegisterInfo.h" 26 #include "llvm/Pass.h" 27 #include "llvm/Support/Debug.h" 28 #include "llvm/Support/raw_ostream.h" 29 #include <cassert> 30 31 using namespace llvm; 32 33 #define DEBUG_TYPE "regalloc" 34 35 STATISTIC(NumAssigned , "Number of registers assigned"); 36 STATISTIC(NumUnassigned , "Number of registers unassigned"); 37 38 char LiveRegMatrixWrapperLegacy::ID = 0; 39 INITIALIZE_PASS_BEGIN(LiveRegMatrixWrapperLegacy, "liveregmatrix", 40 "Live Register Matrix", false, false) 41 INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass) 42 INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy) 43 INITIALIZE_PASS_END(LiveRegMatrixWrapperLegacy, "liveregmatrix", 44 "Live Register Matrix", false, true) 45 46 void LiveRegMatrixWrapperLegacy::getAnalysisUsage(AnalysisUsage &AU) const { 47 AU.setPreservesAll(); 48 AU.addRequiredTransitive<LiveIntervalsWrapperPass>(); 49 AU.addRequiredTransitive<VirtRegMapWrapperLegacy>(); 50 MachineFunctionPass::getAnalysisUsage(AU); 51 } 52 53 bool LiveRegMatrixWrapperLegacy::runOnMachineFunction(MachineFunction &MF) { 54 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS(); 55 auto &VRM = getAnalysis<VirtRegMapWrapperLegacy>().getVRM(); 56 LRM.init(MF, LIS, VRM); 57 return false; 58 } 59 60 void LiveRegMatrix::init(MachineFunction &MF, LiveIntervals &pLIS, 61 VirtRegMap &pVRM) { 62 TRI = MF.getSubtarget().getRegisterInfo(); 63 LIS = &pLIS; 64 VRM = &pVRM; 65 66 unsigned NumRegUnits = TRI->getNumRegUnits(); 67 if (NumRegUnits != Matrix.size()) 68 Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); 69 Matrix.init(*LIUAlloc, NumRegUnits); 70 71 // Make sure no stale queries get reused. 72 invalidateVirtRegs(); 73 } 74 75 void LiveRegMatrixWrapperLegacy::releaseMemory() { LRM.releaseMemory(); } 76 77 void LiveRegMatrix::releaseMemory() { 78 for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { 79 Matrix[i].clear(); 80 // No need to clear Queries here, since LiveIntervalUnion::Query doesn't 81 // have anything important to clear and LiveRegMatrix's runOnFunction() 82 // does a std::unique_ptr::reset anyways. 83 } 84 } 85 86 template <typename Callable> 87 static bool foreachUnit(const TargetRegisterInfo *TRI, 88 const LiveInterval &VRegInterval, MCRegister PhysReg, 89 Callable Func) { 90 if (VRegInterval.hasSubRanges()) { 91 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 92 unsigned Unit = (*Units).first; 93 LaneBitmask Mask = (*Units).second; 94 for (const LiveInterval::SubRange &S : VRegInterval.subranges()) { 95 if ((S.LaneMask & Mask).any()) { 96 if (Func(Unit, S)) 97 return true; 98 break; 99 } 100 } 101 } 102 } else { 103 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { 104 if (Func(Unit, VRegInterval)) 105 return true; 106 } 107 } 108 return false; 109 } 110 111 void LiveRegMatrix::assign(const LiveInterval &VirtReg, MCRegister PhysReg) { 112 LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg(), TRI) << " to " 113 << printReg(PhysReg, TRI) << ':'); 114 assert(!VRM->hasPhys(VirtReg.reg()) && "Duplicate VirtReg assignment"); 115 VRM->assignVirt2Phys(VirtReg.reg(), PhysReg); 116 117 foreachUnit( 118 TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) { 119 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range); 120 Matrix[Unit].unify(VirtReg, Range); 121 return false; 122 }); 123 124 ++NumAssigned; 125 LLVM_DEBUG(dbgs() << '\n'); 126 } 127 128 void LiveRegMatrix::unassign(const LiveInterval &VirtReg) { 129 Register PhysReg = VRM->getPhys(VirtReg.reg()); 130 LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg(), TRI) 131 << " from " << printReg(PhysReg, TRI) << ':'); 132 VRM->clearVirt(VirtReg.reg()); 133 134 foreachUnit(TRI, VirtReg, PhysReg, 135 [&](unsigned Unit, const LiveRange &Range) { 136 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI)); 137 Matrix[Unit].extract(VirtReg, Range); 138 return false; 139 }); 140 141 ++NumUnassigned; 142 LLVM_DEBUG(dbgs() << '\n'); 143 } 144 145 bool LiveRegMatrix::isPhysRegUsed(MCRegister PhysReg) const { 146 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { 147 if (!Matrix[Unit].empty()) 148 return true; 149 } 150 return false; 151 } 152 153 bool LiveRegMatrix::checkRegMaskInterference(const LiveInterval &VirtReg, 154 MCRegister PhysReg) { 155 // Check if the cached information is valid. 156 // The same BitVector can be reused for all PhysRegs. 157 // We could cache multiple VirtRegs if it becomes necessary. 158 if (RegMaskVirtReg != VirtReg.reg() || RegMaskTag != UserTag) { 159 RegMaskVirtReg = VirtReg.reg(); 160 RegMaskTag = UserTag; 161 RegMaskUsable.clear(); 162 LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 163 } 164 165 // The BitVector is indexed by PhysReg, not register unit. 166 // Regmask interference is more fine grained than regunits. 167 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 168 return !RegMaskUsable.empty() && 169 (!PhysReg || !RegMaskUsable.test(PhysReg.id())); 170 } 171 172 bool LiveRegMatrix::checkRegUnitInterference(const LiveInterval &VirtReg, 173 MCRegister PhysReg) { 174 if (VirtReg.empty()) 175 return false; 176 CoalescerPair CP(VirtReg.reg(), PhysReg, *TRI); 177 178 bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 179 const LiveRange &Range) { 180 const LiveRange &UnitRange = LIS->getRegUnit(Unit); 181 return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes()); 182 }); 183 return Result; 184 } 185 186 LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR, 187 MCRegUnit RegUnit) { 188 LiveIntervalUnion::Query &Q = Queries[RegUnit]; 189 Q.init(UserTag, LR, Matrix[RegUnit]); 190 return Q; 191 } 192 193 LiveRegMatrix::InterferenceKind 194 LiveRegMatrix::checkInterference(const LiveInterval &VirtReg, 195 MCRegister PhysReg) { 196 if (VirtReg.empty()) 197 return IK_Free; 198 199 // Regmask interference is the fastest check. 200 if (checkRegMaskInterference(VirtReg, PhysReg)) 201 return IK_RegMask; 202 203 // Check for fixed interference. 204 if (checkRegUnitInterference(VirtReg, PhysReg)) 205 return IK_RegUnit; 206 207 // Check the matrix for virtual register interference. 208 bool Interference = foreachUnit(TRI, VirtReg, PhysReg, 209 [&](MCRegUnit Unit, const LiveRange &LR) { 210 return query(LR, Unit).checkInterference(); 211 }); 212 if (Interference) 213 return IK_VirtReg; 214 215 return IK_Free; 216 } 217 218 bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End, 219 MCRegister PhysReg) { 220 // Construct artificial live range containing only one segment [Start, End). 221 VNInfo valno(0, Start); 222 LiveRange::Segment Seg(Start, End, &valno); 223 LiveRange LR; 224 LR.addSegment(Seg); 225 226 // Check for interference with that segment 227 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { 228 // LR is stack-allocated. LiveRegMatrix caches queries by a key that 229 // includes the address of the live range. If (for the same reg unit) this 230 // checkInterference overload is called twice, without any other query() 231 // calls in between (on heap-allocated LiveRanges) - which would invalidate 232 // the cached query - the LR address seen the second time may well be the 233 // same as that seen the first time, while the Start/End/valno may not - yet 234 // the same cached result would be fetched. To avoid that, we don't cache 235 // this query. 236 // 237 // FIXME: the usability of the Query API needs to be improved to avoid 238 // subtle bugs due to query identity. Avoiding caching, for example, would 239 // greatly simplify things. 240 LiveIntervalUnion::Query Q; 241 Q.reset(UserTag, LR, Matrix[Unit]); 242 if (Q.checkInterference()) 243 return true; 244 } 245 return false; 246 } 247 248 LaneBitmask LiveRegMatrix::checkInterferenceLanes(SlotIndex Start, 249 SlotIndex End, 250 MCRegister PhysReg) { 251 // Construct artificial live range containing only one segment [Start, End). 252 VNInfo valno(0, Start); 253 LiveRange::Segment Seg(Start, End, &valno); 254 LiveRange LR; 255 LR.addSegment(Seg); 256 257 LaneBitmask InterferingLanes; 258 259 // Check for interference with that segment 260 for (MCRegUnitMaskIterator MCRU(PhysReg, TRI); MCRU.isValid(); ++MCRU) { 261 auto [Unit, Lanes] = *MCRU; 262 // LR is stack-allocated. LiveRegMatrix caches queries by a key that 263 // includes the address of the live range. If (for the same reg unit) this 264 // checkInterference overload is called twice, without any other query() 265 // calls in between (on heap-allocated LiveRanges) - which would invalidate 266 // the cached query - the LR address seen the second time may well be the 267 // same as that seen the first time, while the Start/End/valno may not - yet 268 // the same cached result would be fetched. To avoid that, we don't cache 269 // this query. 270 // 271 // FIXME: the usability of the Query API needs to be improved to avoid 272 // subtle bugs due to query identity. Avoiding caching, for example, would 273 // greatly simplify things. 274 LiveIntervalUnion::Query Q; 275 Q.reset(UserTag, LR, Matrix[Unit]); 276 if (Q.checkInterference()) 277 InterferingLanes |= Lanes; 278 } 279 280 return InterferingLanes; 281 } 282 283 Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const { 284 const LiveInterval *VRegInterval = nullptr; 285 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { 286 if ((VRegInterval = Matrix[Unit].getOneVReg())) 287 return VRegInterval->reg(); 288 } 289 290 return MCRegister::NoRegister; 291 } 292 293 AnalysisKey LiveRegMatrixAnalysis::Key; 294 295 LiveRegMatrix LiveRegMatrixAnalysis::run(MachineFunction &MF, 296 MachineFunctionAnalysisManager &MFAM) { 297 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(MF); 298 auto &VRM = MFAM.getResult<VirtRegMapAnalysis>(MF); 299 LiveRegMatrix LRM; 300 LRM.init(MF, LIS, VRM); 301 return LRM; 302 } 303