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