Home | History | Annotate | Download | only in CodeGen 
      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 "RegisterCoalescer.h"
     17 #include "VirtRegMap.h"
     18 #include "llvm/ADT/Statistic.h"
     19 #include "llvm/CodeGen/MachineRegisterInfo.h"
     20 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
     21 #include "llvm/Target/TargetMachine.h"
     22 #include "llvm/Target/TargetRegisterInfo.h"
     23 #include "llvm/Support/Debug.h"
     24 #include "llvm/Support/raw_ostream.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     Queries[i].clear();
     69   }
     70 }
     71 
     72 void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
     73   DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
     74                << " to " << PrintReg(PhysReg, TRI) << ':');
     75   assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
     76   VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
     77   MRI->setPhysRegUsed(PhysReg);
     78   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
     79     DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI));
     80     Matrix[*Units].unify(VirtReg);
     81   }
     82   ++NumAssigned;
     83   DEBUG(dbgs() << '\n');
     84 }
     85 
     86 void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
     87   unsigned PhysReg = VRM->getPhys(VirtReg.reg);
     88   DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
     89                << " from " << PrintReg(PhysReg, TRI) << ':');
     90   VRM->clearVirt(VirtReg.reg);
     91   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
     92     DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI));
     93     Matrix[*Units].extract(VirtReg);
     94   }
     95   ++NumUnassigned;
     96   DEBUG(dbgs() << '\n');
     97 }
     98 
     99 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
    100                                              unsigned PhysReg) {
    101   // Check if the cached information is valid.
    102   // The same BitVector can be reused for all PhysRegs.
    103   // We could cache multiple VirtRegs if it becomes necessary.
    104   if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
    105     RegMaskVirtReg = VirtReg.reg;
    106     RegMaskTag = UserTag;
    107     RegMaskUsable.clear();
    108     LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
    109   }
    110 
    111   // The BitVector is indexed by PhysReg, not register unit.
    112   // Regmask interference is more fine grained than regunits.
    113   // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
    114   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
    115 }
    116 
    117 bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
    118                                              unsigned PhysReg) {
    119   if (VirtReg.empty())
    120     return false;
    121   CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
    122   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
    123     if (VirtReg.overlaps(LIS->getRegUnit(*Units), CP, *LIS->getSlotIndexes()))
    124       return true;
    125   return false;
    126 }
    127 
    128 LiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg,
    129                                                unsigned RegUnit) {
    130   LiveIntervalUnion::Query &Q = Queries[RegUnit];
    131   Q.init(UserTag, &VirtReg, &Matrix[RegUnit]);
    132   return Q;
    133 }
    134 
    135 LiveRegMatrix::InterferenceKind
    136 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
    137   if (VirtReg.empty())
    138     return IK_Free;
    139 
    140   // Regmask interference is the fastest check.
    141   if (checkRegMaskInterference(VirtReg, PhysReg))
    142     return IK_RegMask;
    143 
    144   // Check for fixed interference.
    145   if (checkRegUnitInterference(VirtReg, PhysReg))
    146     return IK_RegUnit;
    147 
    148   // Check the matrix for virtual register interference.
    149   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
    150     if (query(VirtReg, *Units).checkInterference())
    151       return IK_VirtReg;
    152 
    153   return IK_Free;
    154 }
    155