lib/CodeGen/ReachingDefAnalysis.cpp

   1 //===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/CodeGen/ReachingDefAnalysis.h"
  10 #include "llvm/CodeGen/TargetRegisterInfo.h"
  11 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  12 #include "llvm/Support/Debug.h"
  13
  14 using namespace llvm;
  15
  16 #define DEBUG_TYPE "reaching-deps-analysis"
  17
  18 char ReachingDefAnalysis::ID = 0;
  19 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
  20                 true)
  21
  22 void ReachingDefAnalysis::enterBasicBlock(
  23     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
  24
  25   MachineBasicBlock *MBB = TraversedMBB.MBB;
  26   unsigned MBBNumber = MBB->getNumber();
  27   assert(MBBNumber < MBBReachingDefs.size() &&
  28          "Unexpected basic block number.");
  29   MBBReachingDefs[MBBNumber].resize(NumRegUnits);
  30
  31   // Reset instruction counter in each basic block.
  32   CurInstr = 0;
  33
  34   // Set up LiveRegs to represent registers entering MBB.
  35   // Default values are 'nothing happened a long time ago'.
  36   if (LiveRegs.empty())
  37     LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
  38
  39   // This is the entry block.
  40   if (MBB->pred_empty()) {
  41     for (const auto &LI : MBB->liveins()) {
  42       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         LiveRegs[*Unit] = -1;
  47         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   for (MachineBasicBlock *pred : MBB->predecessors()) {
  56     assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
  57            "Should have pre-allocated MBBInfos for all MBBs");
  58     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     if (Incoming.empty())
  62       continue;
  63
  64     for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
  65       // Use the most recent predecessor def for each register.
  66       LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
  67       if ((LiveRegs[Unit] != ReachingDefDefaultVal))
  68         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 void ReachingDefAnalysis::leaveBasicBlock(
  78     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
  79   assert(!LiveRegs.empty() && "Must enter basic block first.");
  80   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   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   for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
  91     OutLiveReg -= CurInstr;
  92   LiveRegs.clear();
  93 }
  94
  95 void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
  96   assert(!MI->isDebugInstr() && "Won't process debug instructions");
  97
  98   unsigned MBBNumber = MI->getParent()->getNumber();
  99   assert(MBBNumber < MBBReachingDefs.size() &&
 100          "Unexpected basic block number.");
 101   const MCInstrDesc &MCID = MI->getDesc();
 102   for (unsigned i = 0,
 103                 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
 104        i != e; ++i) {
 105     MachineOperand &MO = MI->getOperand(i);
 106     if (!MO.isReg() || !MO.getReg())
 107       continue;
 108     if (MO.isUse())
 109       continue;
 110     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       LiveRegs[*Unit] = CurInstr;
 117       MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
 118     }
 119   }
 120   InstIds[MI] = CurInstr;
 121   ++CurInstr;
 122 }
 123
 124 void ReachingDefAnalysis::processBasicBlock(
 125     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
 126   enterBasicBlock(TraversedMBB);
 127   for (MachineInstr &MI : *TraversedMBB.MBB) {
 128     if (!MI.isDebugInstr())
 129       processDefs(&MI);
 130   }
 131   leaveBasicBlock(TraversedMBB);
 132 }
 133
 134 bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
 135   if (skipFunction(mf.getFunction()))
 136     return false;
 137   MF = &mf;
 138   TRI = MF->getSubtarget().getRegisterInfo();
 139
 140   LiveRegs.clear();
 141   NumRegUnits = TRI->getNumRegUnits();
 142
 143   MBBReachingDefs.resize(mf.getNumBlockIDs());
 144
 145   LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
 146
 147   // Initialize the MBBOutRegsInfos
 148   MBBOutRegsInfos.resize(mf.getNumBlockIDs());
 149
 150   // Traverse the basic blocks.
 151   LoopTraversal Traversal;
 152   LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
 153   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
 154     processBasicBlock(TraversedMBB);
 155   }
 156
 157   // Sorting all reaching defs found for a ceartin reg unit in a given BB.
 158   for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
 159     for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
 160       llvm::sort(RegUnitDefs);
 161   }
 162
 163   return false;
 164 }
 165
 166 void ReachingDefAnalysis::releaseMemory() {
 167   // Clear the internal vectors.
 168   MBBOutRegsInfos.clear();
 169   MBBReachingDefs.clear();
 170   InstIds.clear();
 171 }
 172
 173 int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
 174   assert(InstIds.count(MI) && "Unexpected machine instuction.");
 175   int InstId = InstIds[MI];
 176   int DefRes = ReachingDefDefaultVal;
 177   unsigned MBBNumber = MI->getParent()->getNumber();
 178   assert(MBBNumber < MBBReachingDefs.size() &&
 179          "Unexpected basic block number.");
 180   int LatestDef = ReachingDefDefaultVal;
 181   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
 182     for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
 183       if (Def >= InstId)
 184         break;
 185       DefRes = Def;
 186     }
 187     LatestDef = std::max(LatestDef, DefRes);
 188   }
 189   return LatestDef;
 190 }
 191
 192 int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
 193   assert(InstIds.count(MI) && "Unexpected machine instuction.");
 194   return InstIds[MI] - getReachingDef(MI, PhysReg);
 195 }