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 
23 namespace llvm {
24 class 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.
29 class UniqueMachineInstr : public FoldingSetNode {
30   friend class GISelCSEInfo;
31   const MachineInstr *MI;
UniqueMachineInstr(const MachineInstr * MI)32   explicit UniqueMachineInstr(const MachineInstr *MI) : MI(MI) {}
33 
34 public:
35   void Profile(FoldingSetNodeID &ID);
36 };
37 
38 // A CSE config for fully optimized builds.
39 class CSEConfigFull : public CSEConfigBase {
40 public:
41   virtual ~CSEConfigFull() = default;
42   bool shouldCSEOpc(unsigned Opc) override;
43 };
44 
45 // Commonly used for O0 config.
46 class CSEConfigConstantOnly : public CSEConfigBase {
47 public:
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.
56 std::unique_ptr<CSEConfigBase>
57 getStandardCSEConfigForOpt(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.
69 class 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 
116 public:
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 
setCSEConfig(std::unique_ptr<CSEConfigBase> Opt)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 
165 class TargetRegisterClass;
166 class RegisterBank;
167 
168 // Simple builder class to easily profile properties about MIs.
169 class GISelInstProfileBuilder {
170   FoldingSetNodeID &ID;
171   const MachineRegisterInfo &MRI;
172 
173 public:
GISelInstProfileBuilder(FoldingSetNodeID & ID,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;
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.
204 class GISelCSEAnalysisWrapper {
205   GISelCSEInfo Info;
206   MachineFunction *MF = nullptr;
207   bool AlreadyComputed = false;
208 
209 public:
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);
setMF(MachineFunction & MFunc)216   void setMF(MachineFunction &MFunc) { MF = &MFunc; }
setComputed(bool Computed)217   void setComputed(bool Computed) { AlreadyComputed = Computed; }
releaseMemory()218   void releaseMemory() { Info.releaseMemory(); }
219 };
220 
221 /// The actual analysis pass wrapper.
222 class GISelCSEAnalysisWrapperPass : public MachineFunctionPass {
223   GISelCSEAnalysisWrapper Wrapper;
224 
225 public:
226   static char ID;
227   GISelCSEAnalysisWrapperPass();
228 
229   void getAnalysisUsage(AnalysisUsage &AU) const override;
230 
getCSEWrapper()231   const GISelCSEAnalysisWrapper &getCSEWrapper() const { return Wrapper; }
getCSEWrapper()232   GISelCSEAnalysisWrapper &getCSEWrapper() { return Wrapper; }
233 
234   bool runOnMachineFunction(MachineFunction &MF) override;
235 
releaseMemory()236   void releaseMemory() override {
237     Wrapper.releaseMemory();
238     Wrapper.setComputed(false);
239   }
240 };
241 
242 } // namespace llvm
243 
244 #endif
245