LiveRegMatrix.cpp revision 276479
117680Spst//===-- LiveRegMatrix.cpp - Track register interference -------------------===// 239300Sfenner// 317680Spst// The LLVM Compiler Infrastructure 417680Spst// 517680Spst// This file is distributed under the University of Illinois Open Source 617680Spst// License. See LICENSE.TXT for details. 717680Spst// 817680Spst//===----------------------------------------------------------------------===// 917680Spst// 1017680Spst// This file defines the LiveRegMatrix analysis pass. 1117680Spst// 1217680Spst//===----------------------------------------------------------------------===// 1317680Spst 1417680Spst#include "llvm/CodeGen/LiveRegMatrix.h" 1517680Spst#include "RegisterCoalescer.h" 1617680Spst#include "llvm/ADT/Statistic.h" 1717680Spst#include "llvm/CodeGen/LiveIntervalAnalysis.h" 1817680Spst#include "llvm/CodeGen/MachineRegisterInfo.h" 1917680Spst#include "llvm/CodeGen/VirtRegMap.h" 2017680Spst#include "llvm/Support/Debug.h" 2117680Spst#include "llvm/Support/raw_ostream.h" 2256896Sfenner#include "llvm/Target/TargetMachine.h" 2356896Sfenner#include "llvm/Target/TargetRegisterInfo.h" 2417680Spst 2517680Spstusing namespace llvm; 2626183Sfenner 2756896Sfenner#define DEBUG_TYPE "regalloc" 2817680Spst 2917680SpstSTATISTIC(NumAssigned , "Number of registers assigned"); 3056896SfennerSTATISTIC(NumUnassigned , "Number of registers unassigned"); 3156896Sfenner 3256896Sfennerchar LiveRegMatrix::ID = 0; 3356896SfennerINITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", 3417680Spst "Live Register Matrix", false, false) 3517680SpstINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 3617680SpstINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 3717680SpstINITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", 3817680Spst "Live Register Matrix", false, false) 3917680Spst 4017680SpstLiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID), 4117680Spst UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {} 4217680Spst 4317680Spstvoid LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { 4417680Spst AU.setPreservesAll(); 4521262Swollman AU.addRequiredTransitive<LiveIntervals>(); 4617680Spst AU.addRequiredTransitive<VirtRegMap>(); 4717680Spst MachineFunctionPass::getAnalysisUsage(AU); 4839300Sfenner} 4939300Sfenner 5039300Sfennerbool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { 5117680Spst TRI = MF.getTarget().getRegisterInfo(); 5217680Spst MRI = &MF.getRegInfo(); 5317680Spst LIS = &getAnalysis<LiveIntervals>(); 5417680Spst VRM = &getAnalysis<VirtRegMap>(); 5517680Spst 5617680Spst unsigned NumRegUnits = TRI->getNumRegUnits(); 5717680Spst if (NumRegUnits != Matrix.size()) 5817680Spst Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); 5917680Spst Matrix.init(LIUAlloc, NumRegUnits); 6017680Spst 6117680Spst // Make sure no stale queries get reused. 6217680Spst invalidateVirtRegs(); 6317680Spst return false; 6417680Spst} 6517680Spst 6617680Spstvoid LiveRegMatrix::releaseMemory() { 6717680Spst for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { 6817680Spst Matrix[i].clear(); 6917680Spst // No need to clear Queries here, since LiveIntervalUnion::Query doesn't 7017680Spst // have anything important to clear and LiveRegMatrix's runOnFunction() 7117680Spst // does a std::unique_ptr::reset anyways. 7217680Spst } 7317680Spst} 7417680Spst 7517680Spstvoid LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { 7617680Spst DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 7717680Spst << " to " << PrintReg(PhysReg, TRI) << ':'); 7817680Spst assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 7917680Spst VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 8017680Spst MRI->setPhysRegUsed(PhysReg); 8117680Spst for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 8217680Spst DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); 8317680Spst Matrix[*Units].unify(VirtReg); 8417680Spst } 8517680Spst ++NumAssigned; 8617680Spst DEBUG(dbgs() << '\n'); 8717680Spst} 8817680Spst 8917680Spstvoid LiveRegMatrix::unassign(LiveInterval &VirtReg) { 9017680Spst unsigned PhysReg = VRM->getPhys(VirtReg.reg); 9117680Spst DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 9217680Spst << " from " << PrintReg(PhysReg, TRI) << ':'); 9317680Spst VRM->clearVirt(VirtReg.reg); 9417680Spst for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 9517680Spst DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); 9617680Spst Matrix[*Units].extract(VirtReg); 9717680Spst } 9817680Spst ++NumUnassigned; 9917680Spst DEBUG(dbgs() << '\n'); 10017680Spst} 10117680Spst 10217680Spstbool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, 10317680Spst unsigned PhysReg) { 10417680Spst // Check if the cached information is valid. 10517680Spst // The same BitVector can be reused for all PhysRegs. 10617680Spst // We could cache multiple VirtRegs if it becomes necessary. 10717680Spst if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) { 10817680Spst RegMaskVirtReg = VirtReg.reg; 10917680Spst RegMaskTag = UserTag; 11017680Spst RegMaskUsable.clear(); 11156896Sfenner LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 11256896Sfenner } 11317680Spst 11417680Spst // The BitVector is indexed by PhysReg, not register unit. 11517680Spst // Regmask interference is more fine grained than regunits. 11617680Spst // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 11717680Spst return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg)); 11817680Spst} 11917680Spst 12017680Spstbool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, 12117680Spst unsigned PhysReg) { 12217680Spst if (VirtReg.empty()) 12317680Spst return false; 12417680Spst CoalescerPair CP(VirtReg.reg, PhysReg, *TRI); 12517680Spst for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 12617680Spst const LiveRange &UnitRange = LIS->getRegUnit(*Units); 12717680Spst if (VirtReg.overlaps(UnitRange, CP, *LIS->getSlotIndexes())) 12817680Spst return true; 12917680Spst } 13017680Spst return false; 13117680Spst} 13217680Spst 13317680SpstLiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg, 13417680Spst unsigned RegUnit) { 13517680Spst LiveIntervalUnion::Query &Q = Queries[RegUnit]; 13617680Spst Q.init(UserTag, &VirtReg, &Matrix[RegUnit]); 13717680Spst return Q; 13817680Spst} 13917680Spst 14017680SpstLiveRegMatrix::InterferenceKind 14117680SpstLiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { 14217680Spst if (VirtReg.empty()) 14317680Spst return IK_Free; 14417680Spst 14517680Spst // Regmask interference is the fastest check. 14617680Spst if (checkRegMaskInterference(VirtReg, PhysReg)) 14717680Spst return IK_RegMask; 14817680Spst 14917680Spst // Check for fixed interference. 15017680Spst if (checkRegUnitInterference(VirtReg, PhysReg)) 15117680Spst return IK_RegUnit; 15217680Spst 15317680Spst // Check the matrix for virtual register interference. 15417680Spst for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 15517680Spst if (query(VirtReg, *Units).checkInterference()) 15617680Spst return IK_VirtReg; 15717680Spst 15817680Spst return IK_Free; 15939300Sfenner} 16017680Spst