1//===- llvm/CodeGen/GlobalISel/CSEInfo.h ------------------*- 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/// \file
9/// Provides analysis for continuously CSEing during GISel passes.
10///
11//===----------------------------------------------------------------------===//
12#ifndef LLVM_CODEGEN_GLOBALISEL_CSEINFO_H
13#define LLVM_CODEGEN_GLOBALISEL_CSEINFO_H
14
15#include "llvm/ADT/FoldingSet.h"
16#include "llvm/CodeGen/CSEConfigBase.h"
17#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
18#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
19#include "llvm/CodeGen/MachineFunctionPass.h"
20#include "llvm/Support/Allocator.h"
21#include "llvm/Support/CodeGen.h"
22
23namespace llvm {
24class MachineBasicBlock;
25
26/// A class that wraps MachineInstrs and derives from FoldingSetNode in order to
27/// be uniqued in a CSEMap. The tradeoff here is extra memory allocations for
28/// UniqueMachineInstr vs making MachineInstr bigger.
29class UniqueMachineInstr : public FoldingSetNode {
30 friend class GISelCSEInfo;
31 const MachineInstr *MI;
32 explicit UniqueMachineInstr(const MachineInstr *MI) : MI(MI) {}
33
34public:
35 void Profile(FoldingSetNodeID &ID);
36};
37
38// A CSE config for fully optimized builds.
39class CSEConfigFull : public CSEConfigBase {
40public:
41 virtual ~CSEConfigFull() = default;
42 bool shouldCSEOpc(unsigned Opc) override;
43};
44
45// Commonly used for O0 config.
46class CSEConfigConstantOnly : public CSEConfigBase {
47public:
48 virtual ~CSEConfigConstantOnly() = default;
49 bool shouldCSEOpc(unsigned Opc) override;
50};
51
52// Returns the standard expected CSEConfig for the given optimization level.
53// We have this logic here so targets can make use of it from their derived
54// TargetPassConfig, but can't put this logic into TargetPassConfig directly
55// because the CodeGen library can't depend on GlobalISel.
56std::unique_ptr<CSEConfigBase>
57getStandardCSEConfigForOpt(CodeGenOptLevel Level);
58
59/// The CSE Analysis object.
60/// This installs itself as a delegate to the MachineFunction to track
61/// new instructions as well as deletions. It however will not be able to
62/// track instruction mutations. In such cases, recordNewInstruction should be
63/// called (for eg inside MachineIRBuilder::recordInsertion).
64/// Also because of how just the instruction can be inserted without adding any
65/// operands to the instruction, instructions are uniqued and inserted lazily.
66/// CSEInfo should assert when trying to enter an incomplete instruction into
67/// the CSEMap. There is Opcode level granularity on which instructions can be
68/// CSE'd and for now, only Generic instructions are CSEable.
69class GISelCSEInfo : public GISelChangeObserver {
70 // Make it accessible only to CSEMIRBuilder.
71 friend class CSEMIRBuilder;
72
73 BumpPtrAllocator UniqueInstrAllocator;
74 FoldingSet<UniqueMachineInstr> CSEMap;
75 MachineRegisterInfo *MRI = nullptr;
76 MachineFunction *MF = nullptr;
77 std::unique_ptr<CSEConfigBase> CSEOpt;
78 /// Keep a cache of UniqueInstrs for each MachineInstr. In GISel,
79 /// often instructions are mutated (while their ID has completely changed).
80 /// Whenever mutation happens, invalidate the UniqueMachineInstr for the
81 /// MachineInstr
82 DenseMap<const MachineInstr *, UniqueMachineInstr *> InstrMapping;
83
84 /// Store instructions that are not fully formed in TemporaryInsts.
85 /// Also because CSE insertion happens lazily, we can remove insts from this
86 /// list and avoid inserting and then removing from the CSEMap.
87 GISelWorkList<8> TemporaryInsts;
88
89 // Only used in asserts.
90 DenseMap<unsigned, unsigned> OpcodeHitTable;
91
92 bool isUniqueMachineInstValid(const UniqueMachineInstr &UMI) const;
93
94 void invalidateUniqueMachineInstr(UniqueMachineInstr *UMI);
95
96 UniqueMachineInstr *getNodeIfExists(FoldingSetNodeID &ID,
97 MachineBasicBlock *MBB, void *&InsertPos);
98
99 /// Allocate and construct a new UniqueMachineInstr for MI and return.
100 UniqueMachineInstr *getUniqueInstrForMI(const MachineInstr *MI);
101
102 void insertNode(UniqueMachineInstr *UMI, void *InsertPos = nullptr);
103
104 /// Get the MachineInstr(Unique) if it exists already in the CSEMap and the
105 /// same MachineBasicBlock.
106 MachineInstr *getMachineInstrIfExists(FoldingSetNodeID &ID,
107 MachineBasicBlock *MBB,
108 void *&InsertPos);
109
110 /// Use this method to allocate a new UniqueMachineInstr for MI and insert it
111 /// into the CSEMap. MI should return true for shouldCSE(MI->getOpcode())
112 void insertInstr(MachineInstr *MI, void *InsertPos = nullptr);
113
114 bool HandlingRecordedInstrs = false;
115
116public:
117 GISelCSEInfo() = default;
118
119 virtual ~GISelCSEInfo();
120
121 void setMF(MachineFunction &MF);
122
123 Error verify();
124
125 /// Records a newly created inst in a list and lazily insert it to the CSEMap.
126 /// Sometimes, this method might be called with a partially constructed
127 /// MachineInstr,
128 // (right after BuildMI without adding any operands) - and in such cases,
129 // defer the hashing of the instruction to a later stage.
130 void recordNewInstruction(MachineInstr *MI);
131
132 /// Use this callback to inform CSE about a newly fully created instruction.
133 void handleRecordedInst(MachineInstr *MI);
134
135 /// Use this callback to insert all the recorded instructions. At this point,
136 /// all of these insts need to be fully constructed and should not be missing
137 /// any operands.
138 void handleRecordedInsts();
139
140 /// Remove this inst from the CSE map. If this inst has not been inserted yet,
141 /// it will be removed from the Tempinsts list if it exists.
142 void handleRemoveInst(MachineInstr *MI);
143
144 void releaseMemory();
145
146 void setCSEConfig(std::unique_ptr<CSEConfigBase> Opt) {
147 CSEOpt = std::move(Opt);
148 }
149
150 bool shouldCSE(unsigned Opc) const;
151
152 void analyze(MachineFunction &MF);
153
154 void countOpcodeHit(unsigned Opc);
155
156 void print();
157
158 // Observer API
159 void erasingInstr(MachineInstr &MI) override;
160 void createdInstr(MachineInstr &MI) override;
161 void changingInstr(MachineInstr &MI) override;
162 void changedInstr(MachineInstr &MI) override;
163};
164
165class TargetRegisterClass;
166class RegisterBank;
167
168// Simple builder class to easily profile properties about MIs.
169class GISelInstProfileBuilder {
170 FoldingSetNodeID &ID;
171 const MachineRegisterInfo &MRI;
172
173public:
174 GISelInstProfileBuilder(FoldingSetNodeID &ID, const MachineRegisterInfo &MRI)
175 : ID(ID), MRI(MRI) {}
176 // Profiling methods.
177 const GISelInstProfileBuilder &addNodeIDOpcode(unsigned Opc) const;
178 const GISelInstProfileBuilder &addNodeIDRegType(const LLT Ty) const;
179 const GISelInstProfileBuilder &addNodeIDRegType(const Register) const;
180
181 const GISelInstProfileBuilder &
182 addNodeIDRegType(const TargetRegisterClass *RC) const;
183 const GISelInstProfileBuilder &addNodeIDRegType(const RegisterBank *RB) const;
184
185 const GISelInstProfileBuilder &addNodeIDRegNum(Register Reg) const;
186
187 const GISelInstProfileBuilder &addNodeIDReg(Register Reg) const;
188
189 const GISelInstProfileBuilder &addNodeIDImmediate(int64_t Imm) const;
190 const GISelInstProfileBuilder &
191 addNodeIDMBB(const MachineBasicBlock *MBB) const;
192
193 const GISelInstProfileBuilder &
194 addNodeIDMachineOperand(const MachineOperand &MO) const;
195
196 const GISelInstProfileBuilder &addNodeIDFlag(unsigned Flag) const;
197 const GISelInstProfileBuilder &addNodeID(const MachineInstr *MI) const;
198};
199
200/// Simple wrapper that does the following.
201/// 1) Lazily evaluate the MachineFunction to compute CSEable instructions.
202/// 2) Allows configuration of which instructions are CSEd through CSEConfig
203/// object. Provides a method called get which takes a CSEConfig object.
204class GISelCSEAnalysisWrapper {
205 GISelCSEInfo Info;
206 MachineFunction *MF = nullptr;
207 bool AlreadyComputed = false;
208
209public:
210 /// Takes a CSEConfigBase object that defines what opcodes get CSEd.
211 /// If CSEConfig is already set, and the CSE Analysis has been preserved,
212 /// it will not use the new CSEOpt(use Recompute to force using the new
213 /// CSEOpt).
214 GISelCSEInfo &get(std::unique_ptr<CSEConfigBase> CSEOpt,
215 bool ReCompute = false);
216 void setMF(MachineFunction &MFunc) { MF = &MFunc; }
217 void setComputed(bool Computed) { AlreadyComputed = Computed; }
218 void releaseMemory() { Info.releaseMemory(); }
219};
220
221/// The actual analysis pass wrapper.
222class GISelCSEAnalysisWrapperPass : public MachineFunctionPass {
223 GISelCSEAnalysisWrapper Wrapper;
224
225public:
226 static char ID;
227 GISelCSEAnalysisWrapperPass();
228
229 void getAnalysisUsage(AnalysisUsage &AU) const override;
230
231 const GISelCSEAnalysisWrapper &getCSEWrapper() const { return Wrapper; }
232 GISelCSEAnalysisWrapper &getCSEWrapper() { return Wrapper; }
233
234 bool runOnMachineFunction(MachineFunction &MF) override;
235
236 void releaseMemory() override {
237 Wrapper.releaseMemory();
238 Wrapper.setComputed(false);
239 }
240};
241
242} // namespace llvm
243
244#endif
245