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 #include "llvm/InitializePasses.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 ReachingDefAnalysis() : MachineFunctionPass(ID) { 77 initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry()); 78 } 79 void releaseMemory() override; 80 81 void getAnalysisUsage(AnalysisUsage &AU) const override { 82 AU.setPreservesAll(); 83 MachineFunctionPass::getAnalysisUsage(AU); 84 } 85 86 bool runOnMachineFunction(MachineFunction &MF) override; 87 88 MachineFunctionProperties getRequiredProperties() const override { 89 return MachineFunctionProperties().set( 90 MachineFunctionProperties::Property::NoVRegs).set( 91 MachineFunctionProperties::Property::TracksLiveness); 92 } 93 94 /// Provides the instruction id of the closest reaching def instruction of 95 /// PhysReg that reaches MI, relative to the begining of MI's basic block. 96 int getReachingDef(MachineInstr *MI, int PhysReg); 97 98 /// Provides the instruction of the closest reaching def instruction of 99 /// PhysReg that reaches MI, relative to the begining of MI's basic block. 100 MachineInstr *getReachingMIDef(MachineInstr *MI, int PhysReg); 101 102 /// Provides the MI, from the given block, corresponding to the Id or a 103 /// nullptr if the id does not refer to the block. 104 MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId); 105 106 /// Return whether A and B use the same def of PhysReg. 107 bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, int PhysReg); 108 109 /// Return whether the reaching def for MI also is live out of its parent 110 /// block. 111 bool isReachingDefLiveOut(MachineInstr *MI, int PhysReg); 112 113 /// Return the local MI that produces the live out value for PhysReg, or 114 /// nullptr for a non-live out or non-local def. 115 MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB, 116 int PhysReg); 117 118 /// Return whether the given register is used after MI, whether it's a local 119 /// use or a live out. 120 bool isRegUsedAfter(MachineInstr *MI, int PhysReg); 121 122 /// Provides the first instruction before MI that uses PhysReg 123 MachineInstr *getInstWithUseBefore(MachineInstr *MI, int PhysReg); 124 125 /// Provides all instructions before MI that uses PhysReg 126 void getAllInstWithUseBefore(MachineInstr *MI, int PhysReg, 127 SmallVectorImpl<MachineInstr*> &Uses); 128 129 /// Provides the clearance - the number of instructions since the closest 130 /// reaching def instuction of PhysReg that reaches MI. 131 int getClearance(MachineInstr *MI, MCPhysReg PhysReg); 132 133 /// Provides the uses, in the same block as MI, of register that MI defines. 134 /// This does not consider live-outs. 135 void getReachingLocalUses(MachineInstr *MI, int PhysReg, 136 SmallVectorImpl<MachineInstr*> &Uses); 137 138 /// Provide the number of uses, in the same block as MI, of the register that 139 /// MI defines. 140 unsigned getNumUses(MachineInstr *MI, int PhysReg); 141 142 private: 143 /// Set up LiveRegs by merging predecessor live-out values. 144 void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); 145 146 /// Update live-out values. 147 void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); 148 149 /// Process he given basic block. 150 void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); 151 152 /// Update def-ages for registers defined by MI. 153 /// Also break dependencies on partial defs and undef uses. 154 void processDefs(MachineInstr *); 155 }; 156 157 } // namespace llvm 158 159 #endif // LLVM_CODEGEN_REACHINGDEFSANALYSIS_H 160