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
);
123 /// Records a newly created inst in a list and lazily insert it to the CSEMap.
124 /// Sometimes, this method might be called with a partially constructed
126 // (right after BuildMI without adding any operands) - and in such cases,
127 // defer the hashing of the instruction to a later stage.
128 void recordNewInstruction(MachineInstr
*MI
);
130 /// Use this callback to inform CSE about a newly fully created instruction.
131 void handleRecordedInst(MachineInstr
*MI
);
133 /// Use this callback to insert all the recorded instructions. At this point,
134 /// all of these insts need to be fully constructed and should not be missing
136 void handleRecordedInsts();
138 /// Remove this inst from the CSE map. If this inst has not been inserted yet,
139 /// it will be removed from the Tempinsts list if it exists.
140 void handleRemoveInst(MachineInstr
*MI
);
142 void releaseMemory();
144 void setCSEConfig(std::unique_ptr
<CSEConfigBase
> Opt
) {
145 CSEOpt
= std::move(Opt
);
148 bool shouldCSE(unsigned Opc
) const;
150 void analyze(MachineFunction
&MF
);
152 void countOpcodeHit(unsigned Opc
);
157 void erasingInstr(MachineInstr
&MI
) override
;
158 void createdInstr(MachineInstr
&MI
) override
;
159 void changingInstr(MachineInstr
&MI
) override
;
160 void changedInstr(MachineInstr
&MI
) override
;
163 class TargetRegisterClass
;
166 // Simple builder class to easily profile properties about MIs.
167 class GISelInstProfileBuilder
{
168 FoldingSetNodeID
&ID
;
169 const MachineRegisterInfo
&MRI
;
172 GISelInstProfileBuilder(FoldingSetNodeID
&ID
, const MachineRegisterInfo
&MRI
)
173 : ID(ID
), MRI(MRI
) {}
174 // Profiling methods.
175 const GISelInstProfileBuilder
&addNodeIDOpcode(unsigned Opc
) const;
176 const GISelInstProfileBuilder
&addNodeIDRegType(const LLT
&Ty
) const;
177 const GISelInstProfileBuilder
&addNodeIDRegType(const unsigned) const;
179 const GISelInstProfileBuilder
&
180 addNodeIDRegType(const TargetRegisterClass
*RC
) const;
181 const GISelInstProfileBuilder
&addNodeIDRegType(const RegisterBank
*RB
) const;
183 const GISelInstProfileBuilder
&addNodeIDRegNum(unsigned Reg
) const;
185 const GISelInstProfileBuilder
&addNodeIDImmediate(int64_t Imm
) const;
186 const GISelInstProfileBuilder
&
187 addNodeIDMBB(const MachineBasicBlock
*MBB
) const;
189 const GISelInstProfileBuilder
&
190 addNodeIDMachineOperand(const MachineOperand
&MO
) const;
192 const GISelInstProfileBuilder
&addNodeIDFlag(unsigned Flag
) const;
193 const GISelInstProfileBuilder
&addNodeID(const MachineInstr
*MI
) const;
196 /// Simple wrapper that does the following.
197 /// 1) Lazily evaluate the MachineFunction to compute CSEable instructions.
198 /// 2) Allows configuration of which instructions are CSEd through CSEConfig
199 /// object. Provides a method called get which takes a CSEConfig object.
200 class GISelCSEAnalysisWrapper
{
202 MachineFunction
*MF
= nullptr;
203 bool AlreadyComputed
= false;
206 /// Takes a CSEConfigBase object that defines what opcodes get CSEd.
207 /// If CSEConfig is already set, and the CSE Analysis has been preserved,
208 /// it will not use the new CSEOpt(use Recompute to force using the new
210 GISelCSEInfo
&get(std::unique_ptr
<CSEConfigBase
> CSEOpt
,
211 bool ReCompute
= false);
212 void setMF(MachineFunction
&MFunc
) { MF
= &MFunc
; }
213 void setComputed(bool Computed
) { AlreadyComputed
= Computed
; }
214 void releaseMemory() { Info
.releaseMemory(); }
217 /// The actual analysis pass wrapper.
218 class GISelCSEAnalysisWrapperPass
: public MachineFunctionPass
{
219 GISelCSEAnalysisWrapper Wrapper
;
223 GISelCSEAnalysisWrapperPass() : MachineFunctionPass(ID
) {
224 initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry());
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);