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-06-17 00:07:59 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      499630 : INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
      20             :                 true)
      21             : 
      22      296150 : void ReachingDefAnalysis::enterBasicBlock(
      23             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
      24             : 
      25      296150 :   MachineBasicBlock *MBB = TraversedMBB.MBB;
      26      296150 :   unsigned MBBNumber = MBB->getNumber();
      27             :   assert(MBBNumber < MBBReachingDefs.size() &&
      28             :          "Unexpected basic block number.");
      29      592300 :   MBBReachingDefs[MBBNumber].resize(NumRegUnits);
      30             : 
      31             :   // Reset instruction counter in each basic block.
      32      296150 :   CurInstr = 0;
      33             : 
      34             :   // Set up LiveRegs to represent registers entering MBB.
      35             :   // Default values are 'nothing happened a long time ago'.
      36      296150 :   if (LiveRegs.empty())
      37      296150 :     LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
      38             : 
      39             :   // This is the entry block.
      40      296150 :   if (MBB->pred_empty()) {
      41      336563 :     for (const auto &LI : MBB->liveins()) {
      42      755134 :       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      618484 :         LiveRegs[*Unit] = -1;
      47      618484 :         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      447168 :   for (MachineBasicBlock *pred : MBB->predecessors()) {
      56             :     assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
      57             :            "Should have pre-allocated MBBInfos for all MBBs");
      58      264635 :     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      264635 :     if (Incoming.empty())
      62        5121 :       continue;
      63             : 
      64    72919280 :     for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
      65             :       // Use the most recent predecessor def for each register.
      66   108989649 :       LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
      67    36329883 :       if ((LiveRegs[Unit] != ReachingDefDefaultVal))
      68    11861254 :         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      296150 : void ReachingDefAnalysis::leaveBasicBlock(
      78             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
      79             :   assert(!LiveRegs.empty() && "Must enter basic block first.");
      80      296150 :   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      592300 :   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    41153905 :   for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
      91    40857755 :     OutLiveReg -= CurInstr;
      92             :   LiveRegs.clear();
      93      296150 : }
      94             : 
      95     2583707 : void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
      96             :   assert(!MI->isDebugInstr() && "Won't process debug instructions");
      97             : 
      98     2583707 :   unsigned MBBNumber = MI->getParent()->getNumber();
      99             :   assert(MBBNumber < MBBReachingDefs.size() &&
     100             :          "Unexpected basic block number.");
     101     2583707 :   const MCInstrDesc &MCID = MI->getDesc();
     102     1534423 :   for (unsigned i = 0,
     103     2583707 :                 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
     104     4118130 :        i != e; ++i) {
     105     1534423 :     MachineOperand &MO = MI->getOperand(i);
     106     1534423 :     if (!MO.isReg() || !MO.getReg())
     107       98162 :       continue;
     108     1436261 :     if (MO.isUse())
     109      133217 :       continue;
     110     4834012 :     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     4455848 :       LiveRegs[*Unit] = CurInstr;
     117     6683772 :       MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
     118             :     }
     119             :   }
     120     5167414 :   InstIds[MI] = CurInstr;
     121     2583707 :   ++CurInstr;
     122     2583707 : }
     123             : 
     124      296150 : void ReachingDefAnalysis::processBasicBlock(
     125             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
     126      296150 :   enterBasicBlock(TraversedMBB);
     127     3506158 :   for (MachineInstr &MI : *TraversedMBB.MBB) {
     128             :     if (!MI.isDebugInstr())
     129     2583707 :       processDefs(&MI);
     130             :   }
     131      296150 :   leaveBasicBlock(TraversedMBB);
     132      296150 : }
     133             : 
     134      113733 : bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
     135      113733 :   if (skipFunction(mf.getFunction()))
     136             :     return false;
     137      113617 :   MF = &mf;
     138      113617 :   TRI = MF->getSubtarget().getRegisterInfo();
     139             : 
     140             :   LiveRegs.clear();
     141      113617 :   NumRegUnits = TRI->getNumRegUnits();
     142             : 
     143      227234 :   MBBReachingDefs.resize(mf.getNumBlockIDs());
     144             : 
     145             :   LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
     146             : 
     147             :   // Initialize the MBBOutRegsInfos
     148      227234 :   MBBOutRegsInfos.resize(mf.getNumBlockIDs());
     149             : 
     150             :   // Traverse the basic blocks.
     151             :   LoopTraversal Traversal;
     152      113617 :   LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
     153      705917 :   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
     154      296150 :     processBasicBlock(TraversedMBB);
     155             :   }
     156             : 
     157             :   // Sorting all reaching defs found for a ceartin reg unit in a given BB.
     158      616441 :   for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
     159    34691170 :     for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
     160             :       llvm::sort(RegUnitDefs.begin(), RegUnitDefs.end());
     161             :   }
     162             : 
     163             :   return false;
     164             : }
     165             : 
     166      113752 : void ReachingDefAnalysis::releaseMemory() {
     167             :   // Clear the internal vectors.
     168      113752 :   MBBOutRegsInfos.clear();
     169             :   MBBReachingDefs.clear();
     170      113752 :   InstIds.clear();
     171      113752 : }
     172             : 
     173       11939 : int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
     174             :   assert(InstIds.count(MI) && "Unexpected machine instuction.");
     175       23878 :   int InstId = InstIds[MI];
     176       11939 :   int DefRes = ReachingDefDefaultVal;
     177       11939 :   unsigned MBBNumber = MI->getParent()->getNumber();
     178             :   assert(MBBNumber < MBBReachingDefs.size() &&
     179             :          "Unexpected basic block number.");
     180       11939 :   int LatestDef = ReachingDefDefaultVal;
     181       36041 :   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
     182      108985 :     for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
     183       45251 :       if (Def >= InstId)
     184             :         break;
     185       36248 :       DefRes = Def;
     186             :     }
     187       12163 :     LatestDef = std::max(LatestDef, DefRes);
     188             :   }
     189       11939 :   return LatestDef;
     190             : }
     191             : 
     192        5877 : int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
     193             :   assert(InstIds.count(MI) && "Unexpected machine instuction.");
     194       11754 :   return InstIds[MI] - getReachingDef(MI, PhysReg);
     195             : }

Generated by: LCOV version 1.13