LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveRegMatrix.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 103 103 100.0 %
Date: 2018-10-20 13:21:21 Functions: 18 18 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       31780 : INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
      40             :                       "Live Register Matrix", false, false)
      41       31780 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
      42       31780 : INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
      43       95340 : INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
      44             :                     "Live Register Matrix", false, false)
      45             : 
      46       19532 : LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
      47             : 
      48       19532 : void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
      49             :   AU.setPreservesAll();
      50             :   AU.addRequiredTransitive<LiveIntervals>();
      51             :   AU.addRequiredTransitive<VirtRegMap>();
      52       19532 :   MachineFunctionPass::getAnalysisUsage(AU);
      53       19532 : }
      54             : 
      55      193992 : bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
      56      193992 :   TRI = MF.getSubtarget().getRegisterInfo();
      57      193992 :   LIS = &getAnalysis<LiveIntervals>();
      58      193992 :   VRM = &getAnalysis<VirtRegMap>();
      59             : 
      60      193992 :   unsigned NumRegUnits = TRI->getNumRegUnits();
      61      193992 :   if (NumRegUnits != Matrix.size())
      62     3762307 :     Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
      63      193992 :   Matrix.init(LIUAlloc, NumRegUnits);
      64             : 
      65             :   // Make sure no stale queries get reused.
      66             :   invalidateVirtRegs();
      67      193992 :   return false;
      68             : }
      69             : 
      70      194006 : void LiveRegMatrix::releaseMemory() {
      71    38851723 :   for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
      72    38657717 :     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      194006 : }
      78             : 
      79             : template <typename Callable>
      80    12125609 : static bool foreachUnit(const TargetRegisterInfo *TRI,
      81             :                         LiveInterval &VRegInterval, unsigned PhysReg,
      82             :                         Callable Func) {
      83    12125609 :   if (VRegInterval.hasSubRanges()) {
      84     6219490 :     for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      85             :       unsigned Unit = (*Units).first;
      86             :       LaneBitmask Mask = (*Units).second;
      87     7946414 :       for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
      88    15844010 :         if ((S.LaneMask & Mask).any()) {
      89     3823910 :           if (Func(Unit, S))
      90             :             return true;
      91             :           break;
      92             :         }
      93             :       }
      94             :     }
      95             :   } else {
      96    33147371 :     for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
      97    28491850 :       if (Func(*Units, VRegInterval))
      98             :         return true;
      99             :     }
     100             :   }
     101             :   return false;
     102             : }
     103     4916807 : 
     104             : void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
     105             :   LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg, TRI) << " to "
     106     4916807 :                     << printReg(PhysReg, TRI) << ':');
     107     1405514 :   assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
     108             :   VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
     109             : 
     110     1193376 :   foreachUnit(
     111     2378210 :       TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
     112      753503 :         LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
     113             :         Matrix[Unit].unify(VirtReg, Range);
     114             :         return false;
     115             :       });
     116             : 
     117             :   ++NumAssigned;
     118             :   LLVM_DEBUG(dbgs() << '\n');
     119    10917991 : }
     120    10450808 : 
     121             : void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
     122             :   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     5674436 : 
     127             :   foreachUnit(TRI, VirtReg, PhysReg,
     128             :               [&](unsigned Unit, const LiveRange &Range) {
     129     5674436 :                 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
     130     4470198 :                 Matrix[Unit].extract(VirtReg, Range);
     131             :                 return false;
     132             :               });
     133     6244511 : 
     134    12456986 :   ++NumUnassigned;
     135     2863151 :   LLVM_DEBUG(dbgs() << '\n');
     136             : }
     137             : 
     138             : bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
     139             :   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
     140             :     if (!Matrix[*Unit].empty())
     141             :       return true;
     142    16748420 :   }
     143    15496412 :   return false;
     144             : }
     145             : 
     146             : bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
     147             :                                              unsigned PhysReg) {
     148             :   // Check if the cached information is valid.
     149       63177 :   // The same BitVector can be reused for all PhysRegs.
     150             :   // We could cache multiple VirtRegs if it becomes necessary.
     151             :   if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
     152       63177 :     RegMaskVirtReg = VirtReg.reg;
     153        4404 :     RegMaskTag = UserTag;
     154             :     RegMaskUsable.clear();
     155             :     LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
     156        6377 :   }
     157       12746 : 
     158        2758 :   // 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             :   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
     162             : }
     163             : 
     164             : bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
     165      297308 :                                              unsigned PhysReg) {
     166      172596 :   if (VirtReg.empty())
     167             :     return false;
     168             :   CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
     169             : 
     170             :   bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
     171             :                                                        const LiveRange &Range) {
     172     1471189 :     const LiveRange &UnitRange = LIS->getRegUnit(Unit);
     173             :     return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
     174             :   });
     175     1471189 :   return Result;
     176      339374 : }
     177             : 
     178             : LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
     179      502150 :                                                unsigned RegUnit) {
     180      996068 :   LiveIntervalUnion::Query &Q = Queries[RegUnit];
     181      204498 :   Q.init(UserTag, LR, Matrix[RegUnit]);
     182             :   return Q;
     183             : }
     184             : 
     185             : LiveRegMatrix::InterferenceKind
     186             : LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
     187             :   if (VirtReg.empty())
     188     5183652 :     return IK_Free;
     189     2372034 : 
     190             :   // Regmask interference is the fastest check.
     191             :   if (checkRegMaskInterference(VirtReg, PhysReg))
     192             :     return IK_RegMask;
     193             : 
     194             :   // Check for fixed interference.
     195             :   if (checkRegUnitInterference(VirtReg, PhysReg))
     196     1471189 :     return IK_RegUnit;
     197             : 
     198             :   // Check the matrix for virtual register interference.
     199             :   bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
     200     1471189 :                                   [&](unsigned Unit, const LiveRange &LR) {
     201             :     return query(LR, Unit).checkInterference();
     202     1471189 :   });
     203             :   if (Interference)
     204             :     return IK_VirtReg;
     205     5153064 : 
     206             :   return IK_Free;
     207             : }
     208             : 
     209             : bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
     210             :                                       unsigned PhysReg) {
     211     1471189 :   // Construct artificial live range containing only one segment [Start, End).
     212             :   VNInfo valno(0, Start);
     213       63177 :   LiveRange::Segment Seg(Start, End, &valno);
     214       63177 :   LiveRange LR;
     215             :   LR.addSegment(Seg);
     216             : 
     217             :   // Check for interference with that segment
     218             :   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
     219       63177 :     if (query(LR, *Units).checkInterference())
     220             :       return true;
     221             :   }
     222      350708 :   return false;
     223             : }

Generated by: LCOV version 1.13