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/VirtRegMap.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/raw_ostream.h"
  21 #include "llvm/Target/TargetRegisterInfo.h"
  22 #include "llvm/Target/TargetSubtargetInfo.h"
  23
  24 using namespace llvm;
  25
  26 #define DEBUG_TYPE "regalloc"
  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.getSubtarget().getRegisterInfo();
  51   LIS = &getAnalysis<LiveIntervals>();
  52   VRM = &getAnalysis<VirtRegMap>();
  53
  54   unsigned NumRegUnits = TRI->getNumRegUnits();
  55   if (NumRegUnits != Matrix.size())
  56     Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
  57   Matrix.init(LIUAlloc, NumRegUnits);
  58
  59   // Make sure no stale queries get reused.
  60   invalidateVirtRegs();
  61   return false;
  62 }
  63
  64 void LiveRegMatrix::releaseMemory() {
  65   for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
  66     Matrix[i].clear();
  67     // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
  68     // have anything important to clear and LiveRegMatrix's runOnFunction()
  69     // does a std::unique_ptr::reset anyways.
  70   }
  71 }
  72
  73 template<typename Callable>
  74 bool foreachUnit(const TargetRegisterInfo *TRI, LiveInterval &VRegInterval,
  75                  unsigned PhysReg, Callable Func) {
  76   if (VRegInterval.hasSubRanges()) {
  77     for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
  78       unsigned Unit = (*Units).first;
  79       LaneBitmask Mask = (*Units).second;
  80       for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
  81         if (S.LaneMask & Mask) {
  82           if (Func(Unit, S))
  83             return true;
  84           break;
  85         }
  86       }
  87     }
  88   } else {
  89     for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
  90       if (Func(*Units, VRegInterval))
  91         return true;
  92     }
  93   }
  94   return false;
  95 }
  96
  97 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
  98   DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
  99                << " to " << PrintReg(PhysReg, TRI) << ':');
 100   assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
 101   VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
 102
 103   foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
 104                                          const LiveRange &Range) {
 105     DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << ' ' << Range);
 106     Matrix[Unit].unify(VirtReg, Range);
 107     return false;
 108   });
 109
 110   ++NumAssigned;
 111   DEBUG(dbgs() << '\n');
 112 }
 113
 114 void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
 115   unsigned PhysReg = VRM->getPhys(VirtReg.reg);
 116   DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
 117                << " from " << PrintReg(PhysReg, TRI) << ':');
 118   VRM->clearVirt(VirtReg.reg);
 119
 120   foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
 121                                          const LiveRange &Range) {
 122     DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI));
 123     Matrix[Unit].extract(VirtReg, Range);
 124     return false;
 125   });
 126
 127   ++NumUnassigned;
 128   DEBUG(dbgs() << '\n');
 129 }
 130
 131 bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
 132   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
 133     if (!Matrix[*Unit].empty())
 134       return true;
 135   }
 136   return false;
 137 }
 138
 139 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
 140                                              unsigned PhysReg) {
 141   // Check if the cached information is valid.
 142   // The same BitVector can be reused for all PhysRegs.
 143   // We could cache multiple VirtRegs if it becomes necessary.
 144   if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
 145     RegMaskVirtReg = VirtReg.reg;
 146     RegMaskTag = UserTag;
 147     RegMaskUsable.clear();
 148     LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
 149   }
 150
 151   // The BitVector is indexed by PhysReg, not register unit.
 152   // Regmask interference is more fine grained than regunits.
 153   // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
 154   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
 155 }
 156
 157 bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
 158                                              unsigned PhysReg) {
 159   if (VirtReg.empty())
 160     return false;
 161   CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
 162
 163   bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
 164                                                        const LiveRange &Range) {
 165     const LiveRange &UnitRange = LIS->getRegUnit(Unit);
 166     return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
 167   });
 168   return Result;
 169 }
 170
 171 LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg,
 172                                                unsigned RegUnit) {
 173   LiveIntervalUnion::Query &Q = Queries[RegUnit];
 174   Q.init(UserTag, &VirtReg, &Matrix[RegUnit]);
 175   return Q;
 176 }
 177
 178 LiveRegMatrix::InterferenceKind
 179 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
 180   if (VirtReg.empty())
 181     return IK_Free;
 182
 183   // Regmask interference is the fastest check.
 184   if (checkRegMaskInterference(VirtReg, PhysReg))
 185     return IK_RegMask;
 186
 187   // Check for fixed interference.
 188   if (checkRegUnitInterference(VirtReg, PhysReg))
 189     return IK_RegUnit;
 190
 191   // Check the matrix for virtual register interference.
 192   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
 193     if (query(VirtReg, *Units).checkInterference())
 194       return IK_VirtReg;
 195
 196   return IK_Free;
 197 }