LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveRegMatrix.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 83 83 100.0 %
Date: 2017-09-14 15:23:50 Functions: 19 19 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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/LiveInterval.h"
      18             : #include "llvm/CodeGen/LiveIntervalAnalysis.h"
      19             : #include "llvm/CodeGen/LiveIntervalUnion.h"
      20             : #include "llvm/CodeGen/MachineFunction.h"
      21             : #include "llvm/CodeGen/VirtRegMap.h"
      22             : #include "llvm/MC/LaneBitmask.h"
      23             : #include "llvm/MC/MCRegisterInfo.h"
      24             : #include "llvm/Pass.h"
      25             : #include "llvm/Support/Debug.h"
      26             : #include "llvm/Support/raw_ostream.h"
      27             : #include "llvm/Target/TargetRegisterInfo.h"
      28             : #include "llvm/Target/TargetSubtargetInfo.h"
      29             : #include <cassert>
      30             : 
      31             : using namespace llvm;
      32             : 
      33             : #define DEBUG_TYPE "regalloc"
      34             : 
      35             : STATISTIC(NumAssigned   , "Number of registers assigned");
      36             : STATISTIC(NumUnassigned , "Number of registers unassigned");
      37             : 
      38             : char LiveRegMatrix::ID = 0;
      39       20212 : INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
      40             :                       "Live Register Matrix", false, false)
      41       20212 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
      42       20212 : INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
      43      161696 : INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
      44             :                     "Live Register Matrix", false, false)
      45             : 
      46       76745 : LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
      47             : 
      48       15349 : void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
      49       30698 :   AU.setPreservesAll();
      50       15349 :   AU.addRequiredTransitive<LiveIntervals>();
      51       15349 :   AU.addRequiredTransitive<VirtRegMap>();
      52       15349 :   MachineFunctionPass::getAnalysisUsage(AU);
      53       15349 : }
      54             : 
      55      134827 : bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
      56      134827 :   TRI = MF.getSubtarget().getRegisterInfo();
      57      134827 :   LIS = &getAnalysis<LiveIntervals>();
      58      134827 :   VRM = &getAnalysis<VirtRegMap>();
      59             : 
      60      134827 :   unsigned NumRegUnits = TRI->getNumRegUnits();
      61      134827 :   if (NumRegUnits != Matrix.size())
      62     4655668 :     Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
      63      134827 :   Matrix.init(LIUAlloc, NumRegUnits);
      64             : 
      65             :   // Make sure no stale queries get reused.
      66      134827 :   invalidateVirtRegs();
      67      134827 :   return false;
      68             : }
      69             : 
      70      134848 : void LiveRegMatrix::releaseMemory() {
      71    45296674 :   for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
      72   135485478 :     Matrix[i].clear();
      73             :     // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
      74             :     // have anything important to clear and LiveRegMatrix's runOnFunction()
      75             :     // does a std::unique_ptr::reset anyways.
      76             :   }
      77      134848 : }
      78             : 
      79             : template <typename Callable>
      80    10963922 : static bool foreachUnit(const TargetRegisterInfo *TRI,
      81             :                         LiveInterval &VRegInterval, unsigned PhysReg,
      82             :                         Callable Func) {
      83    10963922 :   if (VRegInterval.hasSubRanges()) {
      84     6414212 :     for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      85     3785807 :       unsigned Unit = (*Units).first;
      86     3785807 :       LaneBitmask Mask = (*Units).second;
      87    10847435 :       for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
      88    14084536 :         if ((S.LaneMask & Mask).any()) {
      89     3916235 :           if (Func(Unit, S))
      90     1063293 :             return true;
      91             :           break;
      92             :         }
      93             :       }
      94             :     }
      95             :   } else {
      96    25733069 :     for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      97    20893100 :       if (Func(*Units, VRegInterval))
      98             :         return true;
      99             :     }
     100             :   }
     101             :   return false;
     102             : }
     103             : 
     104     1221992 : void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
     105             :   DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
     106             :                << " to " << PrintReg(PhysReg, TRI) << ':');
     107             :   assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
     108     1221992 :   VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
     109             : 
     110     1221992 :   foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
     111             :                                          const LiveRange &Range) {
     112             :     DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << ' ' << Range);
     113     3239222 :     Matrix[Unit].unify(VirtReg, Range);
     114             :     return false;
     115             :   });
     116             : 
     117     1221992 :   ++NumAssigned;
     118             :   DEBUG(dbgs() << '\n');
     119     1221992 : }
     120             : 
     121       42931 : void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
     122       85862 :   unsigned PhysReg = VRM->getPhys(VirtReg.reg);
     123             :   DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
     124             :                << " from " << PrintReg(PhysReg, TRI) << ':');
     125       85862 :   VRM->clearVirt(VirtReg.reg);
     126             : 
     127       42931 :   foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
     128             :                                          const LiveRange &Range) {
     129             :     DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI));
     130      112886 :     Matrix[Unit].extract(VirtReg, Range);
     131             :     return false;
     132             :   });
     133             : 
     134       42931 :   ++NumUnassigned;
     135             :   DEBUG(dbgs() << '\n');
     136       42931 : }
     137             : 
     138       48779 : bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
     139      121324 :   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
     140      154791 :     if (!Matrix[*Unit].empty())
     141             :       return true;
     142             :   }
     143       20948 :   return false;
     144             : }
     145             : 
     146     6894603 : bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
     147             :                                              unsigned PhysReg) {
     148             :   // Check if the cached information is valid.
     149             :   // The same BitVector can be reused for all PhysRegs.
     150             :   // We could cache multiple VirtRegs if it becomes necessary.
     151     6894603 :   if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
     152     1322433 :     RegMaskVirtReg = VirtReg.reg;
     153     1322433 :     RegMaskTag = UserTag;
     154     1322433 :     RegMaskUsable.clear();
     155     1322433 :     LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
     156             :   }
     157             : 
     158             :   // The BitVector is indexed by PhysReg, not register unit.
     159             :   // Regmask interference is more fine grained than regunits.
     160             :   // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
     161     9117996 :   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
     162             : }
     163             : 
     164     5205181 : bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
     165             :                                              unsigned PhysReg) {
     166    10410362 :   if (VirtReg.empty())
     167             :     return false;
     168    10410362 :   CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
     169             : 
     170     5205181 :   bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
     171     7622891 :                                                        const LiveRange &Range) {
     172     7622891 :     const LiveRange &UnitRange = LIS->getRegUnit(Unit);
     173     7622891 :     return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
     174     5205181 :   });
     175     5205181 :   return Result;
     176             : }
     177             : 
     178     5965289 : LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
     179             :                                                unsigned RegUnit) {
     180    11930578 :   LiveIntervalUnion::Query &Q = Queries[RegUnit];
     181    17895867 :   Q.init(UserTag, LR, Matrix[RegUnit]);
     182     5965289 :   return Q;
     183             : }
     184             : 
     185             : LiveRegMatrix::InterferenceKind
     186     6758139 : LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
     187    13516278 :   if (VirtReg.empty())
     188             :     return IK_Free;
     189             : 
     190             :   // Regmask interference is the fastest check.
     191     6752094 :   if (checkRegMaskInterference(VirtReg, PhysReg))
     192             :     return IK_RegMask;
     193             : 
     194             :   // Check for fixed interference.
     195     5205181 :   if (checkRegUnitInterference(VirtReg, PhysReg))
     196             :     return IK_RegUnit;
     197             : 
     198             :   // Check the matrix for virtual register interference.
     199     4493818 :   bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
     200     4914052 :                                   [&](unsigned Unit, const LiveRange &LR) {
     201     4914052 :     return query(LR, Unit).checkInterference();
     202     9407870 :   });
     203     4493818 :   if (Interference)
     204             :     return IK_VirtReg;
     205             : 
     206     1192261 :   return IK_Free;
     207             : }

Generated by: LCOV version 1.13