LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveRegMatrix.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 78 78 100.0 %
Date: 2018-06-17 00:07:59 Functions: 20 20 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/LiveIntervalUnion.h"
      19             : #include "llvm/CodeGen/LiveIntervals.h"
      20             : #include "llvm/CodeGen/MachineFunction.h"
      21             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      22             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      23             : #include "llvm/CodeGen/VirtRegMap.h"
      24             : #include "llvm/MC/LaneBitmask.h"
      25             : #include "llvm/MC/MCRegisterInfo.h"
      26             : #include "llvm/Pass.h"
      27             : #include "llvm/Support/Debug.h"
      28             : #include "llvm/Support/raw_ostream.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       26770 : INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
      40             :                       "Live Register Matrix", false, false)
      41       26770 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
      42       26770 : INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
      43      160620 : INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
      44             :                     "Live Register Matrix", false, false)
      45             : 
      46       55542 : LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
      47             : 
      48       18514 : void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
      49             :   AU.setPreservesAll();
      50             :   AU.addRequiredTransitive<LiveIntervals>();
      51             :   AU.addRequiredTransitive<VirtRegMap>();
      52       18514 :   MachineFunctionPass::getAnalysisUsage(AU);
      53       18514 : }
      54             : 
      55      179253 : bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
      56      179253 :   TRI = MF.getSubtarget().getRegisterInfo();
      57      179253 :   LIS = &getAnalysis<LiveIntervals>();
      58      179253 :   VRM = &getAnalysis<VirtRegMap>();
      59             : 
      60      179253 :   unsigned NumRegUnits = TRI->getNumRegUnits();
      61      179253 :   if (NumRegUnits != Matrix.size())
      62     5823467 :     Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
      63      179253 :   Matrix.init(LIUAlloc, NumRegUnits);
      64             : 
      65             :   // Make sure no stale queries get reused.
      66             :   invalidateVirtRegs();
      67      179253 :   return false;
      68             : }
      69             : 
      70      179275 : void LiveRegMatrix::releaseMemory() {
      71    58614292 :   for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
      72    58435017 :     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      179275 : }
      78             : 
      79             : template <typename Callable>
      80    11721436 : static bool foreachUnit(const TargetRegisterInfo *TRI,
      81             :                         LiveInterval &VRegInterval, unsigned PhysReg,
      82             :                         Callable Func) {
      83    11721436 :   if (VRegInterval.hasSubRanges()) {
      84     5978763 :     for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      85             :       unsigned Unit = (*Units).first;
      86             :       LaneBitmask Mask = (*Units).second;
      87     7521463 :       for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
      88     7497711 :         if ((S.LaneMask & Mask).any()) {
      89     3673176 :           if (Func(Unit, S))
      90             :             return true;
      91             :           break;
      92             :         }
      93             :       }
      94             :     }
      95             :   } else {
      96    30703353 :     for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      97    25172847 :       if (Func(*Units, VRegInterval))
      98             :         return true;
      99             :     }
     100             :   }
     101             :   return false;
     102             : }
     103             : 
     104     1393777 : void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
     105             :   LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg, TRI) << " to "
     106             :                     << printReg(PhysReg, TRI) << ':');
     107             :   assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
     108     1393777 :   VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
     109             : 
     110     1393777 :   foreachUnit(
     111             :       TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
     112             :         LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
     113     4523272 :         Matrix[Unit].unify(VirtReg, Range);
     114             :         return false;
     115             :       });
     116             : 
     117             :   ++NumAssigned;
     118             :   LLVM_DEBUG(dbgs() << '\n');
     119     1393777 : }
     120             : 
     121       63145 : void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
     122       63145 :   unsigned PhysReg = VRM->getPhys(VirtReg.reg);
     123             :   LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg, TRI) << " from "
     124             :                     << printReg(PhysReg, TRI) << ':');
     125             :   VRM->clearVirt(VirtReg.reg);
     126             : 
     127       63145 :   foreachUnit(TRI, VirtReg, PhysReg,
     128             :               [&](unsigned Unit, const LiveRange &Range) {
     129             :                 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
     130      306496 :                 Matrix[Unit].extract(VirtReg, Range);
     131             :                 return false;
     132             :               });
     133             : 
     134             :   ++NumUnassigned;
     135             :   LLVM_DEBUG(dbgs() << '\n');
     136       63145 : }
     137             : 
     138       52077 : bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
     139      143365 :   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
     140      137304 :     if (!Matrix[*Unit].empty())
     141             :       return true;
     142             :   }
     143       22636 :   return false;
     144             : }
     145             : 
     146     7323538 : 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     7323538 :   if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
     152     1501311 :     RegMaskVirtReg = VirtReg.reg;
     153     1501311 :     RegMaskTag = UserTag;
     154             :     RegMaskUsable.clear();
     155     1501311 :     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     9685811 :   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
     162             : }
     163             : 
     164     5511945 : bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
     165             :                                              unsigned PhysReg) {
     166     5511945 :   if (VirtReg.empty())
     167             :     return false;
     168     5511945 :   CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
     169             : 
     170     5511945 :   bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
     171     9393159 :                                                        const LiveRange &Range) {
     172     9393159 :     const LiveRange &UnitRange = LIS->getRegUnit(Unit);
     173     9393159 :     return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
     174     5511945 :   });
     175     5511945 :   return Result;
     176             : }
     177             : 
     178     6910610 : LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
     179             :                                                unsigned RegUnit) {
     180     6910610 :   LiveIntervalUnion::Query &Q = Queries[RegUnit];
     181    13821220 :   Q.init(UserTag, LR, Matrix[RegUnit]);
     182     6910610 :   return Q;
     183             : }
     184             : 
     185             : LiveRegMatrix::InterferenceKind
     186     7175399 : LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
     187     7175399 :   if (VirtReg.empty())
     188             :     return IK_Free;
     189             : 
     190             :   // Regmask interference is the fastest check.
     191     7168141 :   if (checkRegMaskInterference(VirtReg, PhysReg))
     192             :     return IK_RegMask;
     193             : 
     194             :   // Check for fixed interference.
     195     5511945 :   if (checkRegUnitInterference(VirtReg, PhysReg))
     196             :     return IK_RegUnit;
     197             : 
     198             :   // Check the matrix for virtual register interference.
     199     4752569 :   bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
     200     5575667 :                                   [&](unsigned Unit, const LiveRange &LR) {
     201     5575667 :     return query(LR, Unit).checkInterference();
     202    10328236 :   });
     203     4752569 :   if (Interference)
     204             :     return IK_VirtReg;
     205             : 
     206     1343727 :   return IK_Free;
     207             : }
     208             : 
     209       12371 : bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
     210             :                                       unsigned PhysReg) {
     211             :   // Construct artificial live range containing only one segment [Start, End).
     212             :   VNInfo valno(0, Start);
     213             :   LiveRange::Segment Seg(Start, End, &valno);
     214       24742 :   LiveRange LR;
     215       12371 :   LR.addSegment(Seg);
     216             : 
     217             :   // Check for interference with that segment
     218       34523 :   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
     219       33108 :     if (query(LR, *Units).checkInterference())
     220             :       return true;
     221             :   }
     222        5598 :   return false;
     223             : }

Generated by: LCOV version 1.13