ReachingDefAnalysis.h revision 360784 
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
30namespace llvm {
31
32class MachineBasicBlock;
33class MachineInstr;
34
35/// This class provides the reaching def analysis.
36class ReachingDefAnalysis : public MachineFunctionPass {
37private:
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
73public:
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
142private:
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