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