LCOV - code coverage report
Current view: top level - lib/CodeGen - ReachingDefAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 76 76 100.0 %
Date: 2018-10-20 13:21:21 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      277470 : INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
      20             :                 true)
      21             : 
      22      437466 : void ReachingDefAnalysis::enterBasicBlock(
      23             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
      24             : 
      25      437466 :   MachineBasicBlock *MBB = TraversedMBB.MBB;
      26      437466 :   unsigned MBBNumber = MBB->getNumber();
      27             :   assert(MBBNumber < MBBReachingDefs.size() &&
      28             :          "Unexpected basic block number.");
      29      874932 :   MBBReachingDefs[MBBNumber].resize(NumRegUnits);
      30             : 
      31             :   // Reset instruction counter in each basic block.
      32      437466 :   CurInstr = 0;
      33             : 
      34             :   // Set up LiveRegs to represent registers entering MBB.
      35             :   // Default values are 'nothing happened a long time ago'.
      36      437466 :   if (LiveRegs.empty())
      37      437466 :     LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
      38             : 
      39             :   // This is the entry block.
      40      437466 :   if (MBB->pred_empty()) {
      41      371700 :     for (const auto &LI : MBB->liveins()) {
      42      683416 :       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      873160 :         LiveRegs[*Unit] = -1;
      47      873160 :         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      756675 :   for (MachineBasicBlock *pred : MBB->predecessors()) {
      56             :     assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
      57             :            "Should have pre-allocated MBBInfos for all MBBs");
      58      444073 :     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      444073 :     if (Incoming.empty())
      62             :       continue;
      63             : 
      64    70588377 :     for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
      65             :       // Use the most recent predecessor def for each register.
      66   140301606 :       LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
      67    70150803 :       if ((LiveRegs[Unit] != ReachingDefDefaultVal))
      68    27472910 :         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      437466 : void ReachingDefAnalysis::leaveBasicBlock(
      78             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
      79             :   assert(!LiveRegs.empty() && "Must enter basic block first.");
      80      437466 :   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      874932 :   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    69619291 :   for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
      91    69181825 :     OutLiveReg -= CurInstr;
      92             :   LiveRegs.clear();
      93      437466 : }
      94             : 
      95     2979549 : void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
      96             :   assert(!MI->isDebugInstr() && "Won't process debug instructions");
      97             : 
      98     2979549 :   unsigned MBBNumber = MI->getParent()->getNumber();
      99             :   assert(MBBNumber < MBBReachingDefs.size() &&
     100             :          "Unexpected basic block number.");
     101     2979549 :   const MCInstrDesc &MCID = MI->getDesc();
     102     1647201 :   for (unsigned i = 0,
     103     2979550 :                 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
     104     4626751 :        i != e; ++i) {
     105     1647201 :     MachineOperand &MO = MI->getOperand(i);
     106     1647201 :     if (!MO.isReg() || !MO.getReg())
     107             :       continue;
     108     1547368 :     if (MO.isUse())
     109             :       continue;
     110     5545475 :     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     2744193 :       LiveRegs[*Unit] = CurInstr;
     117     8232579 :       MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
     118             :     }
     119             :   }
     120     2979550 :   InstIds[MI] = CurInstr;
     121     2979550 :   ++CurInstr;
     122     2979550 : }
     123             : 
     124      437466 : void ReachingDefAnalysis::processBasicBlock(
     125             :     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
     126      437466 :   enterBasicBlock(TraversedMBB);
     127     3560951 :   for (MachineInstr &MI : *TraversedMBB.MBB) {
     128             :     if (!MI.isDebugInstr())
     129     2979550 :       processDefs(&MI);
     130             :   }
     131      437466 :   leaveBasicBlock(TraversedMBB);
     132      437466 : }
     133             : 
     134      125006 : bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
     135      125006 :   if (skipFunction(mf.getFunction()))
     136             :     return false;
     137      124864 :   MF = &mf;
     138      124864 :   TRI = MF->getSubtarget().getRegisterInfo();
     139             : 
     140             :   LiveRegs.clear();
     141      124864 :   NumRegUnits = TRI->getNumRegUnits();
     142             : 
     143      249728 :   MBBReachingDefs.resize(mf.getNumBlockIDs());
     144             : 
     145             :   LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
     146             : 
     147             :   // Initialize the MBBOutRegsInfos
     148      249728 :   MBBOutRegsInfos.resize(mf.getNumBlockIDs());
     149             : 
     150             :   // Traverse the basic blocks.
     151             :   LoopTraversal Traversal;
     152      124864 :   LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
     153      562330 :   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
     154      437466 :     processBasicBlock(TraversedMBB);
     155             :   }
     156             : 
     157             :   // Sorting all reaching defs found for a ceartin reg unit in a given BB.
     158      492195 :   for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
     159    58002734 :     for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
     160             :       llvm::sort(RegUnitDefs);
     161             :   }
     162             : 
     163             :   return false;
     164             : }
     165             : 
     166      125019 : void ReachingDefAnalysis::releaseMemory() {
     167             :   // Clear the internal vectors.
     168      125019 :   MBBOutRegsInfos.clear();
     169             :   MBBReachingDefs.clear();
     170      125019 :   InstIds.clear();
     171      125019 : }
     172             : 
     173       14320 : int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
     174             :   assert(InstIds.count(MI) && "Unexpected machine instuction.");
     175       14320 :   int InstId = InstIds[MI];
     176       14320 :   int DefRes = ReachingDefDefaultVal;
     177       14320 :   unsigned MBBNumber = MI->getParent()->getNumber();
     178             :   assert(MBBNumber < MBBReachingDefs.size() &&
     179             :          "Unexpected basic block number.");
     180       14320 :   int LatestDef = ReachingDefDefaultVal;
     181       28864 :   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
     182       71717 :     for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
     183       53552 :       if (Def >= InstId)
     184             :         break;
     185       42629 :       DefRes = Def;
     186             :     }
     187       14544 :     LatestDef = std::max(LatestDef, DefRes);
     188             :   }
     189       14320 :   return LatestDef;
     190             : }
     191             : 
     192        7024 : int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
     193             :   assert(InstIds.count(MI) && "Unexpected machine instuction.");
     194        7024 :   return InstIds[MI] - getReachingDef(MI, PhysReg);
     195             : }

Generated by: LCOV version 1.13