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 LiveRegMatrix::ID = 0; 39 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", 40 "Live Register Matrix", false, false) 41 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 42 INITIALIZE_PASS_DEPENDENCY(VirtRegMap) 43 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", 44 "Live Register Matrix", false, false) 45 46 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {} 47 48 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { 49 AU.setPreservesAll(); 50 AU.addRequiredTransitive<LiveIntervals>(); 51 AU.addRequiredTransitive<VirtRegMap>(); 52 MachineFunctionPass::getAnalysisUsage(AU); 53 } 54 55 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { 56 TRI = MF.getSubtarget().getRegisterInfo(); 57 LIS = &getAnalysis<LiveIntervals>(); 58 VRM = &getAnalysis<VirtRegMap>(); 59 60 unsigned NumRegUnits = TRI->getNumRegUnits(); 61 if (NumRegUnits != Matrix.size()) 62 Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); 63 Matrix.init(LIUAlloc, NumRegUnits); 64 65 // Make sure no stale queries get reused. 66 invalidateVirtRegs(); 67 return false; 68 } 69 70 void LiveRegMatrix::releaseMemory() { 71 for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { 72 Matrix[i].clear(); 73 // No need to clear Queries here, since LiveIntervalUnion::Query doesn't 74 // have anything important to clear and LiveRegMatrix's runOnFunction() 75 // does a std::unique_ptr::reset anyways. 76 } 77 } 78 79 template <typename Callable> 80 static bool foreachUnit(const TargetRegisterInfo *TRI, 81 const LiveInterval &VRegInterval, MCRegister PhysReg, 82 Callable Func) { 83 if (VRegInterval.hasSubRanges()) { 84 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 85 unsigned Unit = (*Units).first; 86 LaneBitmask Mask = (*Units).second; 87 for (const LiveInterval::SubRange &S : VRegInterval.subranges()) { 88 if ((S.LaneMask & Mask).any()) { 89 if (Func(Unit, S)) 90 return true; 91 break; 92 } 93 } 94 } 95 } else { 96 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { 97 if (Func(Unit, VRegInterval)) 98 return true; 99 } 100 } 101 return false; 102 } 103 104 void LiveRegMatrix::assign(const LiveInterval &VirtReg, MCRegister PhysReg) { 105 LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg(), TRI) << " to " 106 << printReg(PhysReg, TRI) << ':'); 107 assert(!VRM->hasPhys(VirtReg.reg()) && "Duplicate VirtReg assignment"); 108 VRM->assignVirt2Phys(VirtReg.reg(), PhysReg); 109 110 foreachUnit( 111 TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) { 112 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range); 113 Matrix[Unit].unify(VirtReg, Range); 114 return false; 115 }); 116 117 ++NumAssigned; 118 LLVM_DEBUG(dbgs() << '\n'); 119 } 120 121 void LiveRegMatrix::unassign(const LiveInterval &VirtReg) { 122 Register PhysReg = VRM->getPhys(VirtReg.reg()); 123 LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg(), TRI) 124 << " from " << printReg(PhysReg, TRI) << ':'); 125 VRM->clearVirt(VirtReg.reg()); 126 127 foreachUnit(TRI, VirtReg, PhysReg, 128 [&](unsigned Unit, const LiveRange &Range) { 129 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI)); 130 Matrix[Unit].extract(VirtReg, Range); 131 return false; 132 }); 133 134 ++NumUnassigned; 135 LLVM_DEBUG(dbgs() << '\n'); 136 } 137 138 bool LiveRegMatrix::isPhysRegUsed(MCRegister PhysReg) const { 139 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { 140 if (!Matrix[Unit].empty()) 141 return true; 142 } 143 return false; 144 } 145 146 bool LiveRegMatrix::checkRegMaskInterference(const LiveInterval &VirtReg, 147 MCRegister PhysReg) { 148 // Check if the cached information is valid. 149 // The same BitVector can be reused for all PhysRegs. 150 // We could cache multiple VirtRegs if it becomes necessary. 151 if (RegMaskVirtReg != VirtReg.reg() || RegMaskTag != UserTag) { 152 RegMaskVirtReg = VirtReg.reg(); 153 RegMaskTag = UserTag; 154 RegMaskUsable.clear(); 155 LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 156 } 157 158 // The BitVector is indexed by PhysReg, not register unit. 159 // Regmask interference is more fine grained than regunits. 160 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 161 return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg)); 162 } 163 164 bool LiveRegMatrix::checkRegUnitInterference(const LiveInterval &VirtReg, 165 MCRegister PhysReg) { 166 if (VirtReg.empty()) 167 return false; 168 CoalescerPair CP(VirtReg.reg(), PhysReg, *TRI); 169 170 bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 171 const LiveRange &Range) { 172 const LiveRange &UnitRange = LIS->getRegUnit(Unit); 173 return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes()); 174 }); 175 return Result; 176 } 177 178 LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR, 179 MCRegister RegUnit) { 180 LiveIntervalUnion::Query &Q = Queries[RegUnit]; 181 Q.init(UserTag, LR, Matrix[RegUnit]); 182 return Q; 183 } 184 185 LiveRegMatrix::InterferenceKind 186 LiveRegMatrix::checkInterference(const LiveInterval &VirtReg, 187 MCRegister PhysReg) { 188 if (VirtReg.empty()) 189 return IK_Free; 190 191 // Regmask interference is the fastest check. 192 if (checkRegMaskInterference(VirtReg, PhysReg)) 193 return IK_RegMask; 194 195 // Check for fixed interference. 196 if (checkRegUnitInterference(VirtReg, PhysReg)) 197 return IK_RegUnit; 198 199 // Check the matrix for virtual register interference. 200 bool Interference = foreachUnit(TRI, VirtReg, PhysReg, 201 [&](MCRegister Unit, const LiveRange &LR) { 202 return query(LR, Unit).checkInterference(); 203 }); 204 if (Interference) 205 return IK_VirtReg; 206 207 return IK_Free; 208 } 209 210 bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End, 211 MCRegister PhysReg) { 212 // Construct artificial live range containing only one segment [Start, End). 213 VNInfo valno(0, Start); 214 LiveRange::Segment Seg(Start, End, &valno); 215 LiveRange LR; 216 LR.addSegment(Seg); 217 218 // Check for interference with that segment 219 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { 220 // LR is stack-allocated. LiveRegMatrix caches queries by a key that 221 // includes the address of the live range. If (for the same reg unit) this 222 // checkInterference overload is called twice, without any other query() 223 // calls in between (on heap-allocated LiveRanges) - which would invalidate 224 // the cached query - the LR address seen the second time may well be the 225 // same as that seen the first time, while the Start/End/valno may not - yet 226 // the same cached result would be fetched. To avoid that, we don't cache 227 // this query. 228 // 229 // FIXME: the usability of the Query API needs to be improved to avoid 230 // subtle bugs due to query identity. Avoiding caching, for example, would 231 // greatly simplify things. 232 LiveIntervalUnion::Query Q; 233 Q.reset(UserTag, LR, Matrix[Unit]); 234 if (Q.checkInterference()) 235 return true; 236 } 237 return false; 238 } 239 240 Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const { 241 const LiveInterval *VRegInterval = nullptr; 242 for (MCRegUnit Unit : TRI->regunits(PhysReg)) { 243 if ((VRegInterval = Matrix[Unit].getOneVReg())) 244 return VRegInterval->reg(); 245 } 246 247 return MCRegister::NoRegister; 248 } 249