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