LCOV - code coverage report
Current view: top level - lib/CodeGen - ReachingDefAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 79 79 100.0 %
Date: 2018-07-13 00:08:38 Functions: 10 10 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
       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             : #include "llvm/CodeGen/ReachingDefAnalysis.h"
      11             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      12             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      13             : 
      14             : using namespace llvm;
      15             : 
      16             : #define DEBUG_TYPE "reaching-deps-analysis"
      17             : 
      18             : char ReachingDefAnalysis::ID = 0;
      19      481458 : INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
      20             :                 true)
      21             : 
      22      299018 : void ReachingDefAnalysis::enterBasicBlock(
      23             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
      24             : 
      25      299018 :   MachineBasicBlock *MBB = TraversedMBB.MBB;
      26      299018 :   unsigned MBBNumber = MBB->getNumber();
      27             :   assert(MBBNumber < MBBReachingDefs.size() &&
      28             :          "Unexpected basic block number.");
      29      598036 :   MBBReachingDefs[MBBNumber].resize(NumRegUnits);
      30             : 
      31             :   // Reset instruction counter in each basic block.
      32      299018 :   CurInstr = 0;
      33             : 
      34             :   // Set up LiveRegs to represent registers entering MBB.
      35             :   // Default values are 'nothing happened a long time ago'.
      36      299018 :   if (LiveRegs.empty())
      37      299018 :     LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
      38             : 
      39             :   // This is the entry block.
      40      299018 :   if (MBB->pred_empty()) {
      41      342864 :     for (const auto &LI : MBB->liveins()) {
      42      842961 :       for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
      43             :         // Treat function live-ins as if they were defined just before the first
      44             :         // instruction.  Usually, function arguments are set up immediately
      45             :         // before the call.
      46      777658 :         LiveRegs[*Unit] = -1;
      47      777658 :         MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]);
      48             :       }
      49             :     }
      50             :     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
      51             :     return;
      52             :   }
      53             : 
      54             :   // Try to coalesce live-out registers from predecessors.
      55      448853 :   for (MachineBasicBlock *pred : MBB->predecessors()) {
      56             :     assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
      57             :            "Should have pre-allocated MBBInfos for all MBBs");
      58      265633 :     const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
      59             :     // Incoming is null if this is a backedge from a BB
      60             :     // we haven't processed yet
      61      265633 :     if (Incoming.empty())
      62        5132 :       continue;
      63             : 
      64    83276305 :     for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
      65             :       // Use the most recent predecessor def for each register.
      66   124523706 :       LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
      67    41507902 :       if ((LiveRegs[Unit] != ReachingDefDefaultVal))
      68    15766436 :         MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
      69             :     }
      70             :   }
      71             : 
      72             :   LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
      73             :                     << (!TraversedMBB.IsDone ? ": incomplete\n"
      74             :                                              : ": all preds known\n"));
      75             : }
      76             : 
      77      299018 : void ReachingDefAnalysis::leaveBasicBlock(
      78             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
      79             :   assert(!LiveRegs.empty() && "Must enter basic block first.");
      80      299018 :   unsigned MBBNumber = TraversedMBB.MBB->getNumber();
      81             :   assert(MBBNumber < MBBOutRegsInfos.size() &&
      82             :          "Unexpected basic block number.");
      83             :   // Save register clearances at end of MBB - used by enterBasicBlock().
      84      598036 :   MBBOutRegsInfos[MBBNumber] = LiveRegs;
      85             : 
      86             :   // While processing the basic block, we kept `Def` relative to the start
      87             :   // of the basic block for convenience. However, future use of this information
      88             :   // only cares about the clearance from the end of the block, so adjust
      89             :   // everything to be relative to the end of the basic block.
      90    47158084 :   for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
      91    46859066 :     OutLiveReg -= CurInstr;
      92             :   LiveRegs.clear();
      93      299018 : }
      94             : 
      95     2593842 : void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
      96             :   assert(!MI->isDebugInstr() && "Won't process debug instructions");
      97             : 
      98     2593842 :   unsigned MBBNumber = MI->getParent()->getNumber();
      99             :   assert(MBBNumber < MBBReachingDefs.size() &&
     100             :          "Unexpected basic block number.");
     101     2593842 :   const MCInstrDesc &MCID = MI->getDesc();
     102     1544985 :   for (unsigned i = 0,
     103     2593842 :                 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
     104     4138827 :        i != e; ++i) {
     105     1544985 :     MachineOperand &MO = MI->getOperand(i);
     106     1544985 :     if (!MO.isReg() || !MO.getReg())
     107       98911 :       continue;
     108     1446074 :     if (MO.isUse())
     109      136313 :       continue;
     110     5180104 :     for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
     111             :       // This instruction explicitly defines the current reg unit.
     112             :       LLVM_DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr
     113             :                         << '\t' << *MI);
     114             : 
     115             :       // How many instructions since this reg unit was last written?
     116     5121164 :       LiveRegs[*Unit] = CurInstr;
     117     7681746 :       MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
     118             :     }
     119             :   }
     120     5187684 :   InstIds[MI] = CurInstr;
     121     2593842 :   ++CurInstr;
     122     2593842 : }
     123             : 
     124      299018 : void ReachingDefAnalysis::processBasicBlock(
     125             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
     126      299018 :   enterBasicBlock(TraversedMBB);
     127     3537007 :   for (MachineInstr &MI : *TraversedMBB.MBB) {
     128             :     if (!MI.isDebugInstr())
     129     2593842 :       processDefs(&MI);
     130             :   }
     131      299018 :   leaveBasicBlock(TraversedMBB);
     132      299018 : }
     133             : 
     134      115914 : bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
     135      115914 :   if (skipFunction(mf.getFunction()))
     136             :     return false;
     137      115798 :   MF = &mf;
     138      115798 :   TRI = MF->getSubtarget().getRegisterInfo();
     139             : 
     140             :   LiveRegs.clear();
     141      115798 :   NumRegUnits = TRI->getNumRegUnits();
     142             : 
     143      231596 :   MBBReachingDefs.resize(mf.getNumBlockIDs());
     144             : 
     145             :   LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
     146             : 
     147             :   // Initialize the MBBOutRegsInfos
     148      231596 :   MBBOutRegsInfos.resize(mf.getNumBlockIDs());
     149             : 
     150             :   // Traverse the basic blocks.
     151             :   LoopTraversal Traversal;
     152      115798 :   LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
     153      713834 :   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
     154      299018 :     processBasicBlock(TraversedMBB);
     155             :   }
     156             : 
     157             :   // Sorting all reaching defs found for a ceartin reg unit in a given BB.
     158      624340 :   for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
     159    39803619 :     for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
     160             :       llvm::sort(RegUnitDefs.begin(), RegUnitDefs.end());
     161             :   }
     162             : 
     163             :   return false;
     164             : }
     165             : 
     166      115927 : void ReachingDefAnalysis::releaseMemory() {
     167             :   // Clear the internal vectors.
     168      115927 :   MBBOutRegsInfos.clear();
     169             :   MBBReachingDefs.clear();
     170      115926 :   InstIds.clear();
     171      115926 : }
     172             : 
     173       12200 : int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
     174             :   assert(InstIds.count(MI) && "Unexpected machine instuction.");
     175       24400 :   int InstId = InstIds[MI];
     176       12200 :   int DefRes = ReachingDefDefaultVal;
     177       12200 :   unsigned MBBNumber = MI->getParent()->getNumber();
     178             :   assert(MBBNumber < MBBReachingDefs.size() &&
     179             :          "Unexpected basic block number.");
     180       12200 :   int LatestDef = ReachingDefDefaultVal;
     181       36824 :   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
     182      110752 :     for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
     183       45909 :       if (Def >= InstId)
     184             :         break;
     185       36740 :       DefRes = Def;
     186             :     }
     187       12424 :     LatestDef = std::max(LatestDef, DefRes);
     188             :   }
     189       12200 :   return LatestDef;
     190             : }
     191             : 
     192        6098 : int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
     193             :   assert(InstIds.count(MI) && "Unexpected machine instuction.");
     194       12196 :   return InstIds[MI] - getReachingDef(MI, PhysReg);
     195             : }

Generated by: LCOV version 1.13