1 //===-- LiveRegMatrix.cpp - Track register interference -------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the LiveRegMatrix analysis pass. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/LiveRegMatrix.h" 15 #include "RegisterCoalescer.h" 16 #include "llvm/ADT/Statistic.h" 17 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 18 #include "llvm/CodeGen/MachineRegisterInfo.h" 19 #include "llvm/CodeGen/VirtRegMap.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/Support/Format.h" 22 #include "llvm/Support/raw_ostream.h" 23 #include "llvm/Target/TargetRegisterInfo.h" 24 25 using namespace llvm; 26 27 #define DEBUG_TYPE "regalloc" 28 29 STATISTIC(NumAssigned , "Number of registers assigned"); 30 STATISTIC(NumUnassigned , "Number of registers unassigned"); 31 32 char LiveRegMatrix::ID = 0; 33 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", 34 "Live Register Matrix", false, false) 35 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 36 INITIALIZE_PASS_DEPENDENCY(VirtRegMap) 37 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", 38 "Live Register Matrix", false, false) 39 40 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID), 41 UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {} 42 43 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { 44 AU.setPreservesAll(); 45 AU.addRequiredTransitive<LiveIntervals>(); 46 AU.addRequiredTransitive<VirtRegMap>(); 47 MachineFunctionPass::getAnalysisUsage(AU); 48 } 49 50 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { 51 TRI = MF.getSubtarget().getRegisterInfo(); 52 MRI = &MF.getRegInfo(); 53 LIS = &getAnalysis<LiveIntervals>(); 54 VRM = &getAnalysis<VirtRegMap>(); 55 56 unsigned NumRegUnits = TRI->getNumRegUnits(); 57 if (NumRegUnits != Matrix.size()) 58 Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); 59 Matrix.init(LIUAlloc, NumRegUnits); 60 61 // Make sure no stale queries get reused. 62 invalidateVirtRegs(); 63 return false; 64 } 65 66 void LiveRegMatrix::releaseMemory() { 67 for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { 68 Matrix[i].clear(); 69 // No need to clear Queries here, since LiveIntervalUnion::Query doesn't 70 // have anything important to clear and LiveRegMatrix's runOnFunction() 71 // does a std::unique_ptr::reset anyways. 72 } 73 } 74 75 template<typename Callable> 76 bool foreachUnit(const TargetRegisterInfo *TRI, LiveInterval &VRegInterval, 77 unsigned PhysReg, Callable Func) { 78 if (VRegInterval.hasSubRanges()) { 79 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 80 unsigned Unit = (*Units).first; 81 unsigned Mask = (*Units).second; 82 for (LiveInterval::SubRange &S : VRegInterval.subranges()) { 83 if (S.LaneMask & Mask) { 84 if (Func(Unit, S)) 85 return true; 86 break; 87 } 88 } 89 } 90 } else { 91 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 92 if (Func(*Units, VRegInterval)) 93 return true; 94 } 95 } 96 return false; 97 } 98 99 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { 100 DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 101 << " to " << PrintReg(PhysReg, TRI) << ':'); 102 assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 103 VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 104 MRI->setPhysRegUsed(PhysReg); 105 106 foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 107 const LiveRange &Range) { 108 DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << ' ' << Range); 109 Matrix[Unit].unify(VirtReg, Range); 110 return false; 111 }); 112 113 ++NumAssigned; 114 DEBUG(dbgs() << '\n'); 115 } 116 117 void LiveRegMatrix::unassign(LiveInterval &VirtReg) { 118 unsigned PhysReg = VRM->getPhys(VirtReg.reg); 119 DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 120 << " from " << PrintReg(PhysReg, TRI) << ':'); 121 VRM->clearVirt(VirtReg.reg); 122 123 foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 124 const LiveRange &Range) { 125 DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI)); 126 Matrix[Unit].extract(VirtReg, Range); 127 return false; 128 }); 129 130 ++NumUnassigned; 131 DEBUG(dbgs() << '\n'); 132 } 133 134 bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const { 135 for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) { 136 if (!Matrix[*Unit].empty()) 137 return true; 138 } 139 return false; 140 } 141 142 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, 143 unsigned PhysReg) { 144 // Check if the cached information is valid. 145 // The same BitVector can be reused for all PhysRegs. 146 // We could cache multiple VirtRegs if it becomes necessary. 147 if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) { 148 RegMaskVirtReg = VirtReg.reg; 149 RegMaskTag = UserTag; 150 RegMaskUsable.clear(); 151 LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 152 } 153 154 // The BitVector is indexed by PhysReg, not register unit. 155 // Regmask interference is more fine grained than regunits. 156 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 157 return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg)); 158 } 159 160 bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, 161 unsigned PhysReg) { 162 if (VirtReg.empty()) 163 return false; 164 CoalescerPair CP(VirtReg.reg, PhysReg, *TRI); 165 166 bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 167 const LiveRange &Range) { 168 const LiveRange &UnitRange = LIS->getRegUnit(Unit); 169 return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes()); 170 }); 171 return Result; 172 } 173 174 LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg, 175 unsigned RegUnit) { 176 LiveIntervalUnion::Query &Q = Queries[RegUnit]; 177 Q.init(UserTag, &VirtReg, &Matrix[RegUnit]); 178 return Q; 179 } 180 181 LiveRegMatrix::InterferenceKind 182 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { 183 if (VirtReg.empty()) 184 return IK_Free; 185 186 // Regmask interference is the fastest check. 187 if (checkRegMaskInterference(VirtReg, PhysReg)) 188 return IK_RegMask; 189 190 // Check for fixed interference. 191 if (checkRegUnitInterference(VirtReg, PhysReg)) 192 return IK_RegUnit; 193 194 // Check the matrix for virtual register interference. 195 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 196 if (query(VirtReg, *Units).checkInterference()) 197 return IK_VirtReg; 198 199 return IK_Free; 200 } 201