lib/CodeGen/LiveRegMatrix.cpp

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