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 #define DEBUG_TYPE "regalloc" 15 #include "LiveRegMatrix.h" 16 #include "VirtRegMap.h" 17 #include "llvm/ADT/Statistic.h" 18 #include "llvm/CodeGen/MachineRegisterInfo.h" 19 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 20 #include "llvm/Target/TargetMachine.h" 21 #include "llvm/Target/TargetRegisterInfo.h" 22 #include "llvm/Support/Debug.h" 23 #include "llvm/Support/raw_ostream.h" 24 25 using namespace llvm; 26 27 STATISTIC(NumAssigned , "Number of registers assigned"); 28 STATISTIC(NumUnassigned , "Number of registers unassigned"); 29 30 char LiveRegMatrix::ID = 0; 31 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", 32 "Live Register Matrix", false, false) 33 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 34 INITIALIZE_PASS_DEPENDENCY(VirtRegMap) 35 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", 36 "Live Register Matrix", false, false) 37 38 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID), 39 UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {} 40 41 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { 42 AU.setPreservesAll(); 43 AU.addRequiredTransitive<LiveIntervals>(); 44 AU.addRequiredTransitive<VirtRegMap>(); 45 MachineFunctionPass::getAnalysisUsage(AU); 46 } 47 48 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { 49 TRI = MF.getTarget().getRegisterInfo(); 50 MRI = &MF.getRegInfo(); 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 Queries[i].clear(); 68 } 69 } 70 71 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { 72 DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 73 << " to " << PrintReg(PhysReg, TRI) << ':'); 74 assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 75 VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 76 MRI->setPhysRegUsed(PhysReg); 77 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 78 DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); 79 Matrix[*Units].unify(VirtReg); 80 } 81 ++NumAssigned; 82 DEBUG(dbgs() << '\n'); 83 } 84 85 void LiveRegMatrix::unassign(LiveInterval &VirtReg) { 86 unsigned PhysReg = VRM->getPhys(VirtReg.reg); 87 DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 88 << " from " << PrintReg(PhysReg, TRI) << ':'); 89 VRM->clearVirt(VirtReg.reg); 90 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 91 DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); 92 Matrix[*Units].extract(VirtReg); 93 } 94 ++NumUnassigned; 95 DEBUG(dbgs() << '\n'); 96 } 97 98 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, 99 unsigned PhysReg) { 100 // Check if the cached information is valid. 101 // The same BitVector can be reused for all PhysRegs. 102 // We could cache multiple VirtRegs if it becomes necessary. 103 if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) { 104 RegMaskVirtReg = VirtReg.reg; 105 RegMaskTag = UserTag; 106 RegMaskUsable.clear(); 107 LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 108 } 109 110 // The BitVector is indexed by PhysReg, not register unit. 111 // Regmask interference is more fine grained than regunits. 112 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 113 return !RegMaskUsable.empty() && !RegMaskUsable.test(PhysReg); 114 } 115 116 bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, 117 unsigned PhysReg) { 118 if (VirtReg.empty()) 119 return false; 120 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 121 if (VirtReg.overlaps(LIS->getRegUnit(*Units))) 122 return true; 123 return false; 124 } 125 126 LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg, 127 unsigned RegUnit) { 128 LiveIntervalUnion::Query &Q = Queries[RegUnit]; 129 Q.init(UserTag, &VirtReg, &Matrix[RegUnit]); 130 return Q; 131 } 132 133 LiveRegMatrix::InterferenceKind 134 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { 135 if (VirtReg.empty()) 136 return IK_Free; 137 138 // Regmask interference is the fastest check. 139 if (checkRegMaskInterference(VirtReg, PhysReg)) 140 return IK_RegMask; 141 142 // Check for fixed interference. 143 if (checkRegUnitInterference(VirtReg, PhysReg)) 144 return IK_RegUnit; 145 146 // Check the matrix for virtual register interference. 147 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 148 if (query(VirtReg, *Units).checkInterference()) 149 return IK_VirtReg; 150 151 return IK_Free; 152 } 153