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-07-13 00:08:38 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       26316 : INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
      40             :                       "Live Register Matrix", false, false)
      41       26316 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
      42       26316 : INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
      43      157896 : INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
      44             :                     "Live Register Matrix", false, false)
      45             : 
      46       55908 : LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
      47             : 
      48       18636 : void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
      49             :   AU.setPreservesAll();
      50             :   AU.addRequiredTransitive<LiveIntervals>();
      51             :   AU.addRequiredTransitive<VirtRegMap>();
      52       18636 :   MachineFunctionPass::getAnalysisUsage(AU);
      53       18636 : }
      54             : 
      55      181815 : bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
      56      181815 :   TRI = MF.getSubtarget().getRegisterInfo();
      57      181815 :   LIS = &getAnalysis<LiveIntervals>();
      58      181815 :   VRM = &getAnalysis<VirtRegMap>();
      59             : 
      60      181815 :   unsigned NumRegUnits = TRI->getNumRegUnits();
      61      181815 :   if (NumRegUnits != Matrix.size())
      62     3571810 :     Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
      63      181815 :   Matrix.init(LIUAlloc, NumRegUnits);
      64             : 
      65             :   // Make sure no stale queries get reused.
      66             :   invalidateVirtRegs();
      67      181815 :   return false;
      68             : }
      69             : 
      70      181831 : void LiveRegMatrix::releaseMemory() {
      71    36390225 :   for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
      72    36208394 :     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      181831 : }
      78             : 
      79             : template <typename Callable>
      80    11760690 : static bool foreachUnit(const TargetRegisterInfo *TRI,
      81             :                         LiveInterval &VRegInterval, unsigned PhysReg,
      82             :                         Callable Func) {
      83    11760690 :   if (VRegInterval.hasSubRanges()) {
      84     6161027 :     for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      85             :       unsigned Unit = (*Units).first;
      86             :       LaneBitmask Mask = (*Units).second;
      87     7921265 :       for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
      88     7896581 :         if ((S.LaneMask & Mask).any()) {
      89     3797301 :           if (Func(Unit, S))
      90             :             return true;
      91             :           break;
      92             :         }
      93             :       }
      94             :     }
      95             :   } else {
      96    32203707 :     for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      97    27919789 :       if (Func(*Units, VRegInterval))
      98             :         return true;
      99             :     }
     100             :   }
     101             :   return false;
     102             : }
     103             : 
     104     1399361 : 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     1399361 :   VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
     109             : 
     110     1399361 :   foreachUnit(
     111             :       TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
     112             :         LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
     113     5002230 :         Matrix[Unit].unify(VirtReg, Range);
     114             :         return false;
     115             :       });
     116             : 
     117             :   ++NumAssigned;
     118             :   LLVM_DEBUG(dbgs() << '\n');
     119     1399361 : }
     120             : 
     121       63123 : void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
     122       63123 :   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       63123 :   foreachUnit(TRI, VirtReg, PhysReg,
     128             :               [&](unsigned Unit, const LiveRange &Range) {
     129             :                 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
     130      351758 :                 Matrix[Unit].extract(VirtReg, Range);
     131             :                 return false;
     132             :               });
     133             : 
     134             :   ++NumUnassigned;
     135             :   LLVM_DEBUG(dbgs() << '\n');
     136       63123 : }
     137             : 
     138       52335 : bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
     139      156182 :   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
     140      161936 :     if (!Matrix[*Unit].empty())
     141             :       return true;
     142             :   }
     143       22879 :   return false;
     144             : }
     145             : 
     146     7340757 : 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     7340757 :   if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
     152     1507087 :     RegMaskVirtReg = VirtReg.reg;
     153     1507087 :     RegMaskTag = UserTag;
     154             :     RegMaskUsable.clear();
     155     1507087 :     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     9702832 :   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
     162             : }
     163             : 
     164     5529001 : bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
     165             :                                              unsigned PhysReg) {
     166     5529001 :   if (VirtReg.empty())
     167             :     return false;
     168     5529001 :   CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
     169             : 
     170     5529001 :   bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
     171    10485677 :                                                        const LiveRange &Range) {
     172    10485677 :     const LiveRange &UnitRange = LIS->getRegUnit(Unit);
     173    10485677 :     return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
     174     5529001 :   });
     175     5529001 :   return Result;
     176             : }
     177             : 
     178     7348781 : LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
     179             :                                                unsigned RegUnit) {
     180     7348781 :   LiveIntervalUnion::Query &Q = Queries[RegUnit];
     181    14697562 :   Q.init(UserTag, LR, Matrix[RegUnit]);
     182     7348781 :   return Q;
     183             : }
     184             : 
     185             : LiveRegMatrix::InterferenceKind
     186     7192440 : LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
     187     7192440 :   if (VirtReg.empty())
     188             :     return IK_Free;
     189             : 
     190             :   // Regmask interference is the fastest check.
     191     7185382 :   if (checkRegMaskInterference(VirtReg, PhysReg))
     192             :     return IK_RegMask;
     193             : 
     194             :   // Check for fixed interference.
     195     5529001 :   if (checkRegUnitInterference(VirtReg, PhysReg))
     196             :     return IK_RegUnit;
     197             : 
     198             :   // Check the matrix for virtual register interference.
     199     4769205 :   bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
     200     5835393 :                                   [&](unsigned Unit, const LiveRange &LR) {
     201     5835393 :     return query(LR, Unit).checkInterference();
     202    10604598 :   });
     203     4769205 :   if (Interference)
     204             :     return IK_VirtReg;
     205             : 
     206     1349607 :   return IK_Free;
     207             : }
     208             : 
     209       12372 : 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       24744 :   LiveRange LR;
     215       12372 :   LR.addSegment(Seg);
     216             : 
     217             :   // Check for interference with that segment
     218       34648 :   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
     219       33380 :     if (query(LR, *Units).checkInterference())
     220             :       return true;
     221             :   }
     222        5586 :   return false;
     223             : }

Generated by: LCOV version 1.13