Line data    Source code

       1             : //==--- llvm/CodeGen/ReachingDefAnalysis.h - 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             : /// \file Reaching Defs Analysis pass.
      11             : ///
      12             : /// This pass tracks for each instruction what is the “closest” reaching def of
      13             : /// a given register. It is used by BreakFalseDeps (for clearance calculation)
      14             : /// and ExecutionDomainFix (for arbitrating conflicting domains).
      15             : ///
      16             : /// Note that this is different from the usual definition notion of liveness.
      17             : /// The CPU doesn't care whether or not we consider a register killed.
      18             : ///
      19             : //
      20             : //===----------------------------------------------------------------------===//
      21             : 
      22             : #ifndef LLVM_CODEGEN_REACHINGDEFSANALYSIS_H
      23             : #define LLVM_CODEGEN_REACHINGDEFSANALYSIS_H
      24             : 
      25             : #include "llvm/ADT/DenseMap.h"
      26             : #include "llvm/ADT/SmallVector.h"
      27             : #include "llvm/CodeGen/LoopTraversal.h"
      28             : #include "llvm/CodeGen/MachineFunctionPass.h"
      29             : 
      30             : namespace llvm {
      31             : 
      32             : class MachineBasicBlock;
      33             : class MachineInstr;
      34             : 
      35             : /// This class provides the reaching def analysis.
      36             : class ReachingDefAnalysis : public MachineFunctionPass {
      37             : private:
      38             :   MachineFunction *MF;
      39             :   const TargetRegisterInfo *TRI;
      40             :   unsigned NumRegUnits;
      41             :   /// Instruction that defined each register, relative to the beginning of the
      42             :   /// current basic block.  When a LiveRegsDefInfo is used to represent a
      43             :   /// live-out register, this value is relative to the end of the basic block,
      44             :   /// so it will be a negative number.
      45             :   using LiveRegsDefInfo = std::vector<int>;
      46             :   LiveRegsDefInfo LiveRegs;
      47             : 
      48             :   /// Keeps clearance information for all registers. Note that this
      49             :   /// is different from the usual definition notion of liveness. The CPU
      50             :   /// doesn't care whether or not we consider a register killed.
      51             :   using OutRegsInfoMap = SmallVector<LiveRegsDefInfo, 4>;
      52             :   OutRegsInfoMap MBBOutRegsInfos;
      53             : 
      54             :   /// Current instruction number.
      55             :   /// The first instruction in each basic block is 0.
      56             :   int CurInstr;
      57             : 
      58             :   /// Maps instructions to their instruction Ids, relative to the begining of
      59             :   /// their basic blocks.
      60             :   DenseMap<MachineInstr *, int> InstIds;
      61             : 
      62             :   /// All reaching defs of a given RegUnit for a given MBB.
      63             :   using MBBRegUnitDefs = SmallVector<int, 1>;
      64             :   /// All reaching defs of all reg units for a given MBB
      65             :   using MBBDefsInfo = std::vector<MBBRegUnitDefs>;
      66             :   /// All reaching defs of all reg units for a all MBBs
      67             :   using MBBReachingDefsInfo = SmallVector<MBBDefsInfo, 4>;
      68             :   MBBReachingDefsInfo MBBReachingDefs;
      69             : 
      70             :   /// Default values are 'nothing happened a long time ago'.
      71             :   const int ReachingDefDefaultVal = -(1 << 20);
      72             : 
      73             : public:
      74             :   static char ID; // Pass identification, replacement for typeid
      75             : 
      76       10905 :   ReachingDefAnalysis() : MachineFunctionPass(ID) {
      77       10905 :     initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry());
      78       10905 :   }
      79             :   void releaseMemory() override;
      80             : 
      81       10905 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      82             :     AU.setPreservesAll();
      83       10905 :     MachineFunctionPass::getAnalysisUsage(AU);
      84       10905 :   }
      85             : 
      86             :   bool runOnMachineFunction(MachineFunction &MF) override;
      87             : 
      88       10908 :   MachineFunctionProperties getRequiredProperties() const override {
      89       10908 :     return MachineFunctionProperties().set(
      90       10908 :         MachineFunctionProperties::Property::NoVRegs);
      91             :   }
      92             : 
      93             :   /// Provides the instruction id of the closest reaching def instruction of
      94             :   /// PhysReg that reaches MI, relative to the begining of MI's basic block.
      95             :   int getReachingDef(MachineInstr *MI, int PhysReg);
      96             : 
      97             :   /// Provides the clearance - the number of instructions since the closest
      98             :   /// reaching def instuction of PhysReg that reaches MI.
      99             :   int getClearance(MachineInstr *MI, MCPhysReg PhysReg);
     100             : 
     101             : private:
     102             :   /// Set up LiveRegs by merging predecessor live-out values.
     103             :   void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
     104             : 
     105             :   /// Update live-out values.
     106             :   void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
     107             : 
     108             :   /// Process he given basic block.
     109             :   void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
     110             : 
     111             :   /// Update def-ages for registers defined by MI.
     112             :   /// Also break dependencies on partial defs and undef uses.
     113             :   void processDefs(MachineInstr *);
     114             : };
     115             : 
     116             : } // namespace llvm
     117             : 
     118             : #endif // LLVM_CODEGEN_REACHINGDEFSANALYSIS_H