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/MC/LaneBitmask.h" 24 #include "llvm/MC/MCRegisterInfo.h" 25 #include "llvm/Pass.h" 26 #include "llvm/Support/Debug.h" 27 #include "llvm/Support/raw_ostream.h" 28 #include <cassert> 29 30 using namespace llvm; 31 32 #define DEBUG_TYPE "regalloc" 33 34 STATISTIC(NumAssigned , "Number of registers assigned"); 35 STATISTIC(NumUnassigned , "Number of registers unassigned"); 36 37 char LiveRegMatrix::ID = 0; 38 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", 39 "Live Register Matrix", false, false) 40 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 41 INITIALIZE_PASS_DEPENDENCY(VirtRegMap) 42 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", 43 "Live Register Matrix", false, false) 44 45 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {} 46 47 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { 48 AU.setPreservesAll(); 49 AU.addRequiredTransitive<LiveIntervals>(); 50 AU.addRequiredTransitive<VirtRegMap>(); 51 MachineFunctionPass::getAnalysisUsage(AU); 52 } 53 54 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { 55 TRI = MF.getSubtarget().getRegisterInfo(); 56 LIS = &getAnalysis<LiveIntervals>(); 57 VRM = &getAnalysis<VirtRegMap>(); 58 59 unsigned NumRegUnits = TRI->getNumRegUnits(); 60 if (NumRegUnits != Matrix.size()) 61 Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); 62 Matrix.init(LIUAlloc, NumRegUnits); 63 64 // Make sure no stale queries get reused. 65 invalidateVirtRegs(); 66 return false; 67 } 68 69 void LiveRegMatrix::releaseMemory() { 70 for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { 71 Matrix[i].clear(); 72 // No need to clear Queries here, since LiveIntervalUnion::Query doesn't 73 // have anything important to clear and LiveRegMatrix's runOnFunction() 74 // does a std::unique_ptr::reset anyways. 75 } 76 } 77 78 template <typename Callable> 79 static bool foreachUnit(const TargetRegisterInfo *TRI, 80 LiveInterval &VRegInterval, unsigned PhysReg, 81 Callable Func) { 82 if (VRegInterval.hasSubRanges()) { 83 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 84 unsigned Unit = (*Units).first; 85 LaneBitmask Mask = (*Units).second; 86 for (LiveInterval::SubRange &S : VRegInterval.subranges()) { 87 if ((S.LaneMask & Mask).any()) { 88 if (Func(Unit, S)) 89 return true; 90 break; 91 } 92 } 93 } 94 } else { 95 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 96 if (Func(*Units, VRegInterval)) 97 return true; 98 } 99 } 100 return false; 101 } 102 103 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { 104 LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg, TRI) << " to " 105 << printReg(PhysReg, TRI) << ':'); 106 assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 107 VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 108 109 foreachUnit( 110 TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) { 111 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range); 112 Matrix[Unit].unify(VirtReg, Range); 113 return false; 114 }); 115 116 ++NumAssigned; 117 LLVM_DEBUG(dbgs() << '\n'); 118 } 119 120 void LiveRegMatrix::unassign(LiveInterval &VirtReg) { 121 unsigned PhysReg = VRM->getPhys(VirtReg.reg); 122 LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg, TRI) << " from " 123 << printReg(PhysReg, TRI) << ':'); 124 VRM->clearVirt(VirtReg.reg); 125 126 foreachUnit(TRI, VirtReg, PhysReg, 127 [&](unsigned Unit, const LiveRange &Range) { 128 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI)); 129 Matrix[Unit].extract(VirtReg, Range); 130 return false; 131 }); 132 133 ++NumUnassigned; 134 LLVM_DEBUG(dbgs() << '\n'); 135 } 136 137 bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const { 138 for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) { 139 if (!Matrix[*Unit].empty()) 140 return true; 141 } 142 return false; 143 } 144 145 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, 146 unsigned PhysReg) { 147 // Check if the cached information is valid. 148 // The same BitVector can be reused for all PhysRegs. 149 // We could cache multiple VirtRegs if it becomes necessary. 150 if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) { 151 RegMaskVirtReg = VirtReg.reg; 152 RegMaskTag = UserTag; 153 RegMaskUsable.clear(); 154 LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 155 } 156 157 // The BitVector is indexed by PhysReg, not register unit. 158 // Regmask interference is more fine grained than regunits. 159 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 160 return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg)); 161 } 162 163 bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, 164 unsigned PhysReg) { 165 if (VirtReg.empty()) 166 return false; 167 CoalescerPair CP(VirtReg.reg, PhysReg, *TRI); 168 169 bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 170 const LiveRange &Range) { 171 const LiveRange &UnitRange = LIS->getRegUnit(Unit); 172 return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes()); 173 }); 174 return Result; 175 } 176 177 LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR, 178 unsigned RegUnit) { 179 LiveIntervalUnion::Query &Q = Queries[RegUnit]; 180 Q.init(UserTag, LR, Matrix[RegUnit]); 181 return Q; 182 } 183 184 LiveRegMatrix::InterferenceKind 185 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { 186 if (VirtReg.empty()) 187 return IK_Free; 188 189 // Regmask interference is the fastest check. 190 if (checkRegMaskInterference(VirtReg, PhysReg)) 191 return IK_RegMask; 192 193 // Check for fixed interference. 194 if (checkRegUnitInterference(VirtReg, PhysReg)) 195 return IK_RegUnit; 196 197 // Check the matrix for virtual register interference. 198 bool Interference = foreachUnit(TRI, VirtReg, PhysReg, 199 [&](unsigned Unit, const LiveRange &LR) { 200 return query(LR, Unit).checkInterference(); 201 }); 202 if (Interference) 203 return IK_VirtReg; 204 205 return IK_Free; 206 } 207 208 bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End, 209 unsigned PhysReg) { 210 // Construct artificial live range containing only one segment [Start, End). 211 VNInfo valno(0, Start); 212 LiveRange::Segment Seg(Start, End, &valno); 213 LiveRange LR; 214 LR.addSegment(Seg); 215 216 // Check for interference with that segment 217 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 218 if (query(LR, *Units).checkInterference()) 219 return true; 220 } 221 return false; 222 } 223