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