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 ReachingDefAnalysis()76 ReachingDefAnalysis() : MachineFunctionPass(ID) { 77 initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry()); 78 } 79 void releaseMemory() override; 80 getAnalysisUsage(AnalysisUsage & AU)81 void getAnalysisUsage(AnalysisUsage &AU) const override { 82 AU.setPreservesAll(); 83 MachineFunctionPass::getAnalysisUsage(AU); 84 } 85 86 bool runOnMachineFunction(MachineFunction &MF) override; 87 getRequiredProperties()88 MachineFunctionProperties getRequiredProperties() const override { 89 return MachineFunctionProperties().set( 90 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 119