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 static bool foreachUnit(const TargetRegisterInfo *TRI, 75 LiveInterval &VRegInterval, unsigned PhysReg, 76 Callable Func) { 77 if (VRegInterval.hasSubRanges()) { 78 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 79 unsigned Unit = (*Units).first; 80 LaneBitmask Mask = (*Units).second; 81 for (LiveInterval::SubRange &S : VRegInterval.subranges()) { 82 if (!(S.LaneMask & Mask).none()) { 83 if (Func(Unit, S)) 84 return true; 85 break; 86 } 87 } 88 } 89 } else { 90 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 91 if (Func(*Units, VRegInterval)) 92 return true; 93 } 94 } 95 return false; 96 } 97 98 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { 99 DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 100 << " to " << PrintReg(PhysReg, TRI) << ':'); 101 assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 102 VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 103 104 foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 105 const LiveRange &Range) { 106 DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << ' ' << Range); 107 Matrix[Unit].unify(VirtReg, Range); 108 return false; 109 }); 110 111 ++NumAssigned; 112 DEBUG(dbgs() << '\n'); 113 } 114 115 void LiveRegMatrix::unassign(LiveInterval &VirtReg) { 116 unsigned PhysReg = VRM->getPhys(VirtReg.reg); 117 DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 118 << " from " << PrintReg(PhysReg, TRI) << ':'); 119 VRM->clearVirt(VirtReg.reg); 120 121 foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 122 const LiveRange &Range) { 123 DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI)); 124 Matrix[Unit].extract(VirtReg, Range); 125 return false; 126 }); 127 128 ++NumUnassigned; 129 DEBUG(dbgs() << '\n'); 130 } 131 132 bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const { 133 for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) { 134 if (!Matrix[*Unit].empty()) 135 return true; 136 } 137 return false; 138 } 139 140 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, 141 unsigned PhysReg) { 142 // Check if the cached information is valid. 143 // The same BitVector can be reused for all PhysRegs. 144 // We could cache multiple VirtRegs if it becomes necessary. 145 if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) { 146 RegMaskVirtReg = VirtReg.reg; 147 RegMaskTag = UserTag; 148 RegMaskUsable.clear(); 149 LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 150 } 151 152 // The BitVector is indexed by PhysReg, not register unit. 153 // Regmask interference is more fine grained than regunits. 154 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 155 return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg)); 156 } 157 158 bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, 159 unsigned PhysReg) { 160 if (VirtReg.empty()) 161 return false; 162 CoalescerPair CP(VirtReg.reg, PhysReg, *TRI); 163 164 bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 165 const LiveRange &Range) { 166 const LiveRange &UnitRange = LIS->getRegUnit(Unit); 167 return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes()); 168 }); 169 return Result; 170 } 171 172 LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg, 173 unsigned RegUnit) { 174 LiveIntervalUnion::Query &Q = Queries[RegUnit]; 175 Q.init(UserTag, &VirtReg, &Matrix[RegUnit]); 176 return Q; 177 } 178 179 LiveRegMatrix::InterferenceKind 180 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { 181 if (VirtReg.empty()) 182 return IK_Free; 183 184 // Regmask interference is the fastest check. 185 if (checkRegMaskInterference(VirtReg, PhysReg)) 186 return IK_RegMask; 187 188 // Check for fixed interference. 189 if (checkRegUnitInterference(VirtReg, PhysReg)) 190 return IK_RegUnit; 191 192 // Check the matrix for virtual register interference. 193 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 194 if (query(VirtReg, *Units).checkInterference()) 195 return IK_VirtReg; 196 197 return IK_Free; 198 } 199