contrib/llvm-project/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

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