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