1 //===- llvm/CodeGen/GlobalISel/CSEInfo.h ------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 /// Provides analysis for continuously CSEing during GISel passes.
11 //===----------------------------------------------------------------------===//
12 #ifndef LLVM_CODEGEN_GLOBALISEL_CSEINFO_H
13 #define LLVM_CODEGEN_GLOBALISEL_CSEINFO_H
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/GlobalISel/Utils.h"
20 #include "llvm/CodeGen/MachineBasicBlock.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Support/Allocator.h"
28 /// A class that wraps MachineInstrs and derives from FoldingSetNode in order to
29 /// be uniqued in a CSEMap. The tradeoff here is extra memory allocations for
30 /// UniqueMachineInstr vs making MachineInstr bigger.
31 class UniqueMachineInstr : public FoldingSetNode {
32 friend class GISelCSEInfo;
33 const MachineInstr *MI;
34 explicit UniqueMachineInstr(const MachineInstr *MI) : MI(MI) {}
37 void Profile(FoldingSetNodeID &ID);
40 // A CSE config for fully optimized builds.
41 class CSEConfigFull : public CSEConfigBase {
43 virtual ~CSEConfigFull() = default;
44 virtual bool shouldCSEOpc(unsigned Opc) override;
47 // Commonly used for O0 config.
48 class CSEConfigConstantOnly : public CSEConfigBase {
50 virtual ~CSEConfigConstantOnly() = default;
51 virtual bool shouldCSEOpc(unsigned Opc) override;
54 // Returns the standard expected CSEConfig for the given optimization level.
55 // We have this logic here so targets can make use of it from their derived
56 // TargetPassConfig, but can't put this logic into TargetPassConfig directly
57 // because the CodeGen library can't depend on GlobalISel.
58 std::unique_ptr<CSEConfigBase>
59 getStandardCSEConfigForOpt(CodeGenOpt::Level Level);
61 /// The CSE Analysis object.
62 /// This installs itself as a delegate to the MachineFunction to track
63 /// new instructions as well as deletions. It however will not be able to
64 /// track instruction mutations. In such cases, recordNewInstruction should be
65 /// called (for eg inside MachineIRBuilder::recordInsertion).
66 /// Also because of how just the instruction can be inserted without adding any
67 /// operands to the instruction, instructions are uniqued and inserted lazily.
68 /// CSEInfo should assert when trying to enter an incomplete instruction into
69 /// the CSEMap. There is Opcode level granularity on which instructions can be
70 /// CSE'd and for now, only Generic instructions are CSEable.
71 class GISelCSEInfo : public GISelChangeObserver {
72 // Make it accessible only to CSEMIRBuilder.
73 friend class CSEMIRBuilder;
75 BumpPtrAllocator UniqueInstrAllocator;
76 FoldingSet<UniqueMachineInstr> CSEMap;
77 MachineRegisterInfo *MRI = nullptr;
78 MachineFunction *MF = nullptr;
79 std::unique_ptr<CSEConfigBase> CSEOpt;
80 /// Keep a cache of UniqueInstrs for each MachineInstr. In GISel,
81 /// often instructions are mutated (while their ID has completely changed).
82 /// Whenever mutation happens, invalidate the UniqueMachineInstr for the
84 DenseMap<const MachineInstr *, UniqueMachineInstr *> InstrMapping;
86 /// Store instructions that are not fully formed in TemporaryInsts.
87 /// Also because CSE insertion happens lazily, we can remove insts from this
88 /// list and avoid inserting and then removing from the CSEMap.
89 GISelWorkList<8> TemporaryInsts;
91 // Only used in asserts.
92 DenseMap<unsigned, unsigned> OpcodeHitTable;
94 bool isUniqueMachineInstValid(const UniqueMachineInstr &UMI) const;
96 void invalidateUniqueMachineInstr(UniqueMachineInstr *UMI);
98 UniqueMachineInstr *getNodeIfExists(FoldingSetNodeID &ID,
99 MachineBasicBlock *MBB, void *&InsertPos);
101 /// Allocate and construct a new UniqueMachineInstr for MI and return.
102 UniqueMachineInstr *getUniqueInstrForMI(const MachineInstr *MI);
104 void insertNode(UniqueMachineInstr *UMI, void *InsertPos = nullptr);
106 /// Get the MachineInstr(Unique) if it exists already in the CSEMap and the
107 /// same MachineBasicBlock.
108 MachineInstr *getMachineInstrIfExists(FoldingSetNodeID &ID,
109 MachineBasicBlock *MBB,
112 /// Use this method to allocate a new UniqueMachineInstr for MI and insert it
113 /// into the CSEMap. MI should return true for shouldCSE(MI->getOpcode())
114 void insertInstr(MachineInstr *MI, void *InsertPos = nullptr);
117 GISelCSEInfo() = default;
119 virtual ~GISelCSEInfo();
121 void setMF(MachineFunction &MF);
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
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);
132 /// Use this callback to inform CSE about a newly fully created instruction.
133 void handleRecordedInst(MachineInstr *MI);
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
138 void handleRecordedInsts();
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);
144 void releaseMemory();
146 void setCSEConfig(std::unique_ptr<CSEConfigBase> Opt) {
147 CSEOpt = std::move(Opt);
150 bool shouldCSE(unsigned Opc) const;
152 void analyze(MachineFunction &MF);
154 void countOpcodeHit(unsigned Opc);
159 void erasingInstr(MachineInstr &MI) override;
160 void createdInstr(MachineInstr &MI) override;
161 void changingInstr(MachineInstr &MI) override;
162 void changedInstr(MachineInstr &MI) override;
165 class TargetRegisterClass;
168 // Simple builder class to easily profile properties about MIs.
169 class GISelInstProfileBuilder {
170 FoldingSetNodeID &ID;
171 const MachineRegisterInfo &MRI;
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;
181 const GISelInstProfileBuilder &
182 addNodeIDRegType(const TargetRegisterClass *RC) const;
183 const GISelInstProfileBuilder &addNodeIDRegType(const RegisterBank *RB) const;
185 const GISelInstProfileBuilder &addNodeIDRegNum(Register Reg) const;
187 const GISelInstProfileBuilder &addNodeIDImmediate(int64_t Imm) const;
188 const GISelInstProfileBuilder &
189 addNodeIDMBB(const MachineBasicBlock *MBB) const;
191 const GISelInstProfileBuilder &
192 addNodeIDMachineOperand(const MachineOperand &MO) const;
194 const GISelInstProfileBuilder &addNodeIDFlag(unsigned Flag) const;
195 const GISelInstProfileBuilder &addNodeID(const MachineInstr *MI) const;
198 /// Simple wrapper that does the following.
199 /// 1) Lazily evaluate the MachineFunction to compute CSEable instructions.
200 /// 2) Allows configuration of which instructions are CSEd through CSEConfig
201 /// object. Provides a method called get which takes a CSEConfig object.
202 class GISelCSEAnalysisWrapper {
204 MachineFunction *MF = nullptr;
205 bool AlreadyComputed = false;
208 /// Takes a CSEConfigBase object that defines what opcodes get CSEd.
209 /// If CSEConfig is already set, and the CSE Analysis has been preserved,
210 /// it will not use the new CSEOpt(use Recompute to force using the new
212 GISelCSEInfo &get(std::unique_ptr<CSEConfigBase> CSEOpt,
213 bool ReCompute = false);
214 void setMF(MachineFunction &MFunc) { MF = &MFunc; }
215 void setComputed(bool Computed) { AlreadyComputed = Computed; }
216 void releaseMemory() { Info.releaseMemory(); }
219 /// The actual analysis pass wrapper.
220 class GISelCSEAnalysisWrapperPass : public MachineFunctionPass {
221 GISelCSEAnalysisWrapper Wrapper;
225 GISelCSEAnalysisWrapperPass();
227 void getAnalysisUsage(AnalysisUsage &AU) const override;
229 const GISelCSEAnalysisWrapper &getCSEWrapper() const { return Wrapper; }
230 GISelCSEAnalysisWrapper &getCSEWrapper() { return Wrapper; }
232 bool runOnMachineFunction(MachineFunction &MF) override;
234 void releaseMemory() override {
235 Wrapper.releaseMemory();
236 Wrapper.setComputed(false);