LiveRegMatrix.cpp revision 239310
11573Srgrimes//===-- LiveRegMatrix.cpp - Track register interference -------------------===// 21573Srgrimes// 31573Srgrimes// The LLVM Compiler Infrastructure 41573Srgrimes// 51573Srgrimes// This file is distributed under the University of Illinois Open Source 61573Srgrimes// License. See LICENSE.TXT for details. 71573Srgrimes// 81573Srgrimes//===----------------------------------------------------------------------===// 91573Srgrimes// 101573Srgrimes// This file defines the LiveRegMatrix analysis pass. 111573Srgrimes// 121573Srgrimes//===----------------------------------------------------------------------===// 131573Srgrimes 141573Srgrimes#define DEBUG_TYPE "regalloc" 151573Srgrimes#include "LiveRegMatrix.h" 161573Srgrimes#include "VirtRegMap.h" 171573Srgrimes#include "llvm/ADT/Statistic.h" 181573Srgrimes#include "llvm/CodeGen/MachineRegisterInfo.h" 191573Srgrimes#include "llvm/CodeGen/LiveIntervalAnalysis.h" 201573Srgrimes#include "llvm/Target/TargetMachine.h" 211573Srgrimes#include "llvm/Target/TargetRegisterInfo.h" 221573Srgrimes#include "llvm/Support/Debug.h" 231573Srgrimes#include "llvm/Support/raw_ostream.h" 241573Srgrimes 251573Srgrimesusing namespace llvm; 261573Srgrimes 271573SrgrimesSTATISTIC(NumAssigned , "Number of registers assigned"); 281573SrgrimesSTATISTIC(NumUnassigned , "Number of registers unassigned"); 291573Srgrimes 301573Srgrimeschar LiveRegMatrix::ID = 0; 311573SrgrimesINITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", 321573Srgrimes "Live Register Matrix", false, false) 331573SrgrimesINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 341573SrgrimesINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 351573SrgrimesINITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", 361573Srgrimes "Live Register Matrix", false, false) 371573Srgrimes 381573SrgrimesLiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID), 391573Srgrimes UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {} 4092986Sobrien 4192986Sobrienvoid LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { 421573Srgrimes AU.setPreservesAll(); 4371579Sdeischen AU.addRequiredTransitive<LiveIntervals>(); 441573Srgrimes AU.addRequiredTransitive<VirtRegMap>(); 451573Srgrimes MachineFunctionPass::getAnalysisUsage(AU); 4611185Speter} 4771579Sdeischen 481573Srgrimesbool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { 4911185Speter TRI = MF.getTarget().getRegisterInfo(); 5011185Speter MRI = &MF.getRegInfo(); 511573Srgrimes LIS = &getAnalysis<LiveIntervals>(); 521573Srgrimes VRM = &getAnalysis<VirtRegMap>(); 531573Srgrimes 541573Srgrimes unsigned NumRegUnits = TRI->getNumRegUnits(); 5592889Sobrien if (NumRegUnits != Matrix.size()) 5692889Sobrien Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); 571573Srgrimes Matrix.init(LIUAlloc, NumRegUnits); 581573Srgrimes 5911064Sbde // Make sure no stale queries get reused. 601573Srgrimes invalidateVirtRegs(); 611573Srgrimes return false; 6256698Sjasone} 631573Srgrimes 641573Srgrimesvoid LiveRegMatrix::releaseMemory() { 651573Srgrimes for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { 661573Srgrimes Matrix[i].clear(); 671573Srgrimes Queries[i].clear(); 681573Srgrimes } 691573Srgrimes} 701573Srgrimes 711573Srgrimesvoid LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { 721573Srgrimes DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 731573Srgrimes << " to " << PrintReg(PhysReg, TRI) << ':'); 741573Srgrimes assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 751573Srgrimes 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 85void 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 98bool 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() && (!PhysReg || !RegMaskUsable.test(PhysReg)); 114} 115 116bool 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 126LiveIntervalUnion::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 133LiveRegMatrix::InterferenceKind 134LiveRegMatrix::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