1239310Sdim//===-- LiveRegMatrix.cpp - Track register interference -------------------===// 2239310Sdim// 3239310Sdim// The LLVM Compiler Infrastructure 4239310Sdim// 5239310Sdim// This file is distributed under the University of Illinois Open Source 6239310Sdim// License. See LICENSE.TXT for details. 7239310Sdim// 8239310Sdim//===----------------------------------------------------------------------===// 9239310Sdim// 10239310Sdim// This file defines the LiveRegMatrix analysis pass. 11239310Sdim// 12239310Sdim//===----------------------------------------------------------------------===// 13239310Sdim 14249423Sdim#include "llvm/CodeGen/LiveRegMatrix.h" 15243830Sdim#include "RegisterCoalescer.h" 16239310Sdim#include "llvm/ADT/Statistic.h" 17249423Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 18249423Sdim#include "llvm/CodeGen/VirtRegMap.h" 19249423Sdim#include "llvm/Support/Debug.h" 20249423Sdim#include "llvm/Support/raw_ostream.h" 21239310Sdim#include "llvm/Target/TargetRegisterInfo.h" 22296417Sdim#include "llvm/Target/TargetSubtargetInfo.h" 23239310Sdim 24239310Sdimusing namespace llvm; 25239310Sdim 26276479Sdim#define DEBUG_TYPE "regalloc" 27276479Sdim 28239310SdimSTATISTIC(NumAssigned , "Number of registers assigned"); 29239310SdimSTATISTIC(NumUnassigned , "Number of registers unassigned"); 30239310Sdim 31239310Sdimchar LiveRegMatrix::ID = 0; 32239310SdimINITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", 33239310Sdim "Live Register Matrix", false, false) 34239310SdimINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 35239310SdimINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 36239310SdimINITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", 37239310Sdim "Live Register Matrix", false, false) 38239310Sdim 39239310SdimLiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID), 40239310Sdim UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {} 41239310Sdim 42239310Sdimvoid LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { 43239310Sdim AU.setPreservesAll(); 44239310Sdim AU.addRequiredTransitive<LiveIntervals>(); 45239310Sdim AU.addRequiredTransitive<VirtRegMap>(); 46239310Sdim MachineFunctionPass::getAnalysisUsage(AU); 47239310Sdim} 48239310Sdim 49239310Sdimbool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { 50280031Sdim TRI = MF.getSubtarget().getRegisterInfo(); 51239310Sdim LIS = &getAnalysis<LiveIntervals>(); 52239310Sdim VRM = &getAnalysis<VirtRegMap>(); 53239310Sdim 54239310Sdim unsigned NumRegUnits = TRI->getNumRegUnits(); 55239310Sdim if (NumRegUnits != Matrix.size()) 56239310Sdim Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); 57239310Sdim Matrix.init(LIUAlloc, NumRegUnits); 58239310Sdim 59239310Sdim // Make sure no stale queries get reused. 60239310Sdim invalidateVirtRegs(); 61239310Sdim return false; 62239310Sdim} 63239310Sdim 64239310Sdimvoid LiveRegMatrix::releaseMemory() { 65239310Sdim for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { 66239310Sdim Matrix[i].clear(); 67276479Sdim // No need to clear Queries here, since LiveIntervalUnion::Query doesn't 68276479Sdim // have anything important to clear and LiveRegMatrix's runOnFunction() 69276479Sdim // does a std::unique_ptr::reset anyways. 70239310Sdim } 71239310Sdim} 72239310Sdim 73280031Sdimtemplate<typename Callable> 74280031Sdimbool foreachUnit(const TargetRegisterInfo *TRI, LiveInterval &VRegInterval, 75280031Sdim unsigned PhysReg, Callable Func) { 76280031Sdim if (VRegInterval.hasSubRanges()) { 77280031Sdim for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 78280031Sdim unsigned Unit = (*Units).first; 79296417Sdim LaneBitmask Mask = (*Units).second; 80280031Sdim for (LiveInterval::SubRange &S : VRegInterval.subranges()) { 81280031Sdim if (S.LaneMask & Mask) { 82280031Sdim if (Func(Unit, S)) 83280031Sdim return true; 84280031Sdim break; 85280031Sdim } 86280031Sdim } 87280031Sdim } 88280031Sdim } else { 89280031Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 90280031Sdim if (Func(*Units, VRegInterval)) 91280031Sdim return true; 92280031Sdim } 93280031Sdim } 94280031Sdim return false; 95280031Sdim} 96280031Sdim 97239310Sdimvoid LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { 98239310Sdim DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 99239310Sdim << " to " << PrintReg(PhysReg, TRI) << ':'); 100239310Sdim assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 101239310Sdim VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 102280031Sdim 103280031Sdim foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 104280031Sdim const LiveRange &Range) { 105280031Sdim DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << ' ' << Range); 106280031Sdim Matrix[Unit].unify(VirtReg, Range); 107280031Sdim return false; 108280031Sdim }); 109280031Sdim 110239310Sdim ++NumAssigned; 111239310Sdim DEBUG(dbgs() << '\n'); 112239310Sdim} 113239310Sdim 114239310Sdimvoid LiveRegMatrix::unassign(LiveInterval &VirtReg) { 115239310Sdim unsigned PhysReg = VRM->getPhys(VirtReg.reg); 116239310Sdim DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 117239310Sdim << " from " << PrintReg(PhysReg, TRI) << ':'); 118239310Sdim VRM->clearVirt(VirtReg.reg); 119280031Sdim 120280031Sdim foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 121280031Sdim const LiveRange &Range) { 122280031Sdim DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI)); 123280031Sdim Matrix[Unit].extract(VirtReg, Range); 124280031Sdim return false; 125280031Sdim }); 126280031Sdim 127239310Sdim ++NumUnassigned; 128239310Sdim DEBUG(dbgs() << '\n'); 129239310Sdim} 130239310Sdim 131288943Sdimbool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const { 132288943Sdim for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) { 133288943Sdim if (!Matrix[*Unit].empty()) 134288943Sdim return true; 135288943Sdim } 136288943Sdim return false; 137288943Sdim} 138288943Sdim 139239310Sdimbool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, 140239310Sdim unsigned PhysReg) { 141239310Sdim // Check if the cached information is valid. 142239310Sdim // The same BitVector can be reused for all PhysRegs. 143239310Sdim // We could cache multiple VirtRegs if it becomes necessary. 144239310Sdim if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) { 145239310Sdim RegMaskVirtReg = VirtReg.reg; 146239310Sdim RegMaskTag = UserTag; 147239310Sdim RegMaskUsable.clear(); 148239310Sdim LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 149239310Sdim } 150239310Sdim 151239310Sdim // The BitVector is indexed by PhysReg, not register unit. 152239310Sdim // Regmask interference is more fine grained than regunits. 153239310Sdim // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 154239310Sdim return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg)); 155239310Sdim} 156239310Sdim 157239310Sdimbool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, 158239310Sdim unsigned PhysReg) { 159239310Sdim if (VirtReg.empty()) 160239310Sdim return false; 161243830Sdim CoalescerPair CP(VirtReg.reg, PhysReg, *TRI); 162280031Sdim 163280031Sdim bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit, 164280031Sdim const LiveRange &Range) { 165280031Sdim const LiveRange &UnitRange = LIS->getRegUnit(Unit); 166280031Sdim return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes()); 167280031Sdim }); 168280031Sdim return Result; 169239310Sdim} 170239310Sdim 171239310SdimLiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg, 172239310Sdim unsigned RegUnit) { 173239310Sdim LiveIntervalUnion::Query &Q = Queries[RegUnit]; 174239310Sdim Q.init(UserTag, &VirtReg, &Matrix[RegUnit]); 175239310Sdim return Q; 176239310Sdim} 177239310Sdim 178239310SdimLiveRegMatrix::InterferenceKind 179239310SdimLiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { 180239310Sdim if (VirtReg.empty()) 181239310Sdim return IK_Free; 182239310Sdim 183239310Sdim // Regmask interference is the fastest check. 184239310Sdim if (checkRegMaskInterference(VirtReg, PhysReg)) 185239310Sdim return IK_RegMask; 186239310Sdim 187239310Sdim // Check for fixed interference. 188239310Sdim if (checkRegUnitInterference(VirtReg, PhysReg)) 189239310Sdim return IK_RegUnit; 190239310Sdim 191239310Sdim // Check the matrix for virtual register interference. 192239310Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 193239310Sdim if (query(VirtReg, *Units).checkInterference()) 194239310Sdim return IK_VirtReg; 195239310Sdim 196239310Sdim return IK_Free; 197239310Sdim} 198