LLVM  13.0.0git
CSEInfo.h
Go to the documentation of this file.
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"
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.
30  friend class GISelCSEInfo;
31  const MachineInstr *MI;
32  explicit UniqueMachineInstr(const MachineInstr *MI) : MI(MI) {}
33 
34 public:
36 };
37 
38 // A CSE config for fully optimized builds.
39 class CSEConfigFull : public CSEConfigBase {
40 public:
41  virtual ~CSEConfigFull() = default;
42  virtual bool shouldCSEOpc(unsigned Opc) override;
43 };
44 
45 // Commonly used for O0 config.
47 public:
48  virtual ~CSEConfigConstantOnly() = default;
49  virtual 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>
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.
70  // Make it accessible only to CSEMIRBuilder.
71  friend class CSEMIRBuilder;
72 
73  BumpPtrAllocator UniqueInstrAllocator;
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
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,
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 public:
115  GISelCSEInfo() = default;
116 
117  virtual ~GISelCSEInfo();
118 
119  void setMF(MachineFunction &MF);
120 
121  Error verify();
122 
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
125  /// MachineInstr,
126  // (right after BuildMI without adding any operands) - and in such cases,
127  // defer the hashing of the instruction to a later stage.
129 
130  /// Use this callback to inform CSE about a newly fully created instruction.
132 
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
135  /// any operands.
136  void handleRecordedInsts();
137 
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.
141 
142  void releaseMemory();
143 
144  void setCSEConfig(std::unique_ptr<CSEConfigBase> Opt) {
145  CSEOpt = std::move(Opt);
146  }
147 
148  bool shouldCSE(unsigned Opc) const;
149 
150  void analyze(MachineFunction &MF);
151 
152  void countOpcodeHit(unsigned Opc);
153 
154  void print();
155 
156  // Observer API
157  void erasingInstr(MachineInstr &MI) override;
158  void createdInstr(MachineInstr &MI) override;
159  void changingInstr(MachineInstr &MI) override;
160  void changedInstr(MachineInstr &MI) override;
161 };
162 
163 class TargetRegisterClass;
164 class RegisterBank;
165 
166 // Simple builder class to easily profile properties about MIs.
168  FoldingSetNodeID &ID;
169  const MachineRegisterInfo &MRI;
170 
171 public:
173  : ID(ID), MRI(MRI) {}
174  // Profiling methods.
175  const GISelInstProfileBuilder &addNodeIDOpcode(unsigned Opc) const;
176  const GISelInstProfileBuilder &addNodeIDRegType(const LLT Ty) const;
178 
180  addNodeIDRegType(const TargetRegisterClass *RC) const;
181  const GISelInstProfileBuilder &addNodeIDRegType(const RegisterBank *RB) const;
182 
184 
186 
187  const GISelInstProfileBuilder &addNodeIDImmediate(int64_t Imm) const;
189  addNodeIDMBB(const MachineBasicBlock *MBB) const;
190 
192  addNodeIDMachineOperand(const MachineOperand &MO) const;
193 
194  const GISelInstProfileBuilder &addNodeIDFlag(unsigned Flag) const;
195  const GISelInstProfileBuilder &addNodeID(const MachineInstr *MI) const;
196 };
197 
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.
203  GISelCSEInfo Info;
204  MachineFunction *MF = nullptr;
205  bool AlreadyComputed = false;
206 
207 public:
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
211  /// CSEOpt).
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(); }
217 };
218 
219 /// The actual analysis pass wrapper.
221  GISelCSEAnalysisWrapper Wrapper;
222 
223 public:
224  static char ID;
226 
227  void getAnalysisUsage(AnalysisUsage &AU) const override;
228 
229  const GISelCSEAnalysisWrapper &getCSEWrapper() const { return Wrapper; }
231 
232  bool runOnMachineFunction(MachineFunction &MF) override;
233 
234  void releaseMemory() override {
235  Wrapper.releaseMemory();
236  Wrapper.setComputed(false);
237  }
238 };
239 
240 } // namespace llvm
241 
242 #endif
llvm::GISelCSEAnalysisWrapperPass::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: CSEInfo.h:234
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
llvm::GISelCSEInfo::handleRecordedInst
void handleRecordedInst(MachineInstr *MI)
Use this callback to inform CSE about a newly fully created instruction.
Definition: CSEInfo.cpp:183
llvm
Definition: AllocatorList.h:23
llvm::GISelCSEInfo::~GISelCSEInfo
virtual ~GISelCSEInfo()
Definition: CSEInfo.cpp:90
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::GISelCSEAnalysisWrapperPass
The actual analysis pass wrapper.
Definition: CSEInfo.h:220
llvm::GISelCSEInfo::handleRemoveInst
void handleRemoveInst(MachineInstr *MI)
Remove this inst from the CSE map.
Definition: CSEInfo.cpp:205
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
CSEConfigBase.h
Wrapper
amdgpu aa AMDGPU Address space based Alias Analysis Wrapper
Definition: AMDGPUAliasAnalysis.cpp:30
llvm::GISelCSEInfo
The CSE Analysis object.
Definition: CSEInfo.h:69
llvm::GISelInstProfileBuilder::addNodeIDMBB
const GISelInstProfileBuilder & addNodeIDMBB(const MachineBasicBlock *MBB) const
Definition: CSEInfo.cpp:357
Allocator.h
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::GISelInstProfileBuilder::addNodeIDMachineOperand
const GISelInstProfileBuilder & addNodeIDMachineOperand(const MachineOperand &MO) const
Definition: CSEInfo.cpp:384
llvm::GISelCSEAnalysisWrapperPass::getCSEWrapper
const GISelCSEAnalysisWrapper & getCSEWrapper() const
Definition: CSEInfo.h:229
llvm::GISelCSEAnalysisWrapper::releaseMemory
void releaseMemory()
Definition: CSEInfo.h:216
llvm::GISelCSEAnalysisWrapper::setMF
void setMF(MachineFunction &MFunc)
Definition: CSEInfo.h:214
llvm::GISelInstProfileBuilder::addNodeID
const GISelInstProfileBuilder & addNodeID(const MachineInstr *MI) const
Definition: CSEInfo.cpp:304
llvm::GISelCSEInfo::changedInstr
void changedInstr(MachineInstr &MI) override
This instruction was mutated in some way.
Definition: CSEInfo.cpp:232
llvm::GISelInstProfileBuilder::addNodeIDRegType
const GISelInstProfileBuilder & addNodeIDRegType(const LLT Ty) const
Definition: CSEInfo.cpp:320
llvm::GISelCSEInfo::shouldCSE
bool shouldCSE(unsigned Opc) const
Definition: CSEInfo.cpp:220
llvm::CSEConfigConstantOnly::~CSEConfigConstantOnly
virtual ~CSEConfigConstantOnly()=default
llvm::GISelCSEAnalysisWrapper::get
GISelCSEInfo & get(std::unique_ptr< CSEConfigBase > CSEOpt, bool ReCompute=false)
Takes a CSEConfigBase object that defines what opcodes get CSEd.
Definition: CSEInfo.cpp:409
llvm::UniqueMachineInstr
A class that wraps MachineInstrs and derives from FoldingSetNode in order to be uniqued in a CSEMap.
Definition: CSEInfo.h:29
llvm::CSEConfigFull::~CSEConfigFull
virtual ~CSEConfigFull()=default
llvm::GISelInstProfileBuilder::addNodeIDOpcode
const GISelInstProfileBuilder & addNodeIDOpcode(unsigned Opc) const
Definition: CSEInfo.cpp:314
llvm::GISelInstProfileBuilder::addNodeIDReg
const GISelInstProfileBuilder & addNodeIDReg(Register Reg) const
Definition: CSEInfo.cpp:370
llvm::CSEConfigConstantOnly
Definition: CSEInfo.h:46
llvm::RegisterBank
This class implements the register bank concept.
Definition: RegisterBank.h:28
llvm::GISelCSEAnalysisWrapperPass::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: CSEInfo.cpp:424
llvm::GISelCSEInfo::recordNewInstruction
void recordNewInstruction(MachineInstr *MI)
Records a newly created inst in a list and lazily insert it to the CSEMap.
Definition: CSEInfo.cpp:176
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::GISelCSEInfo::erasingInstr
void erasingInstr(MachineInstr &MI) override
An instruction is about to be erased.
Definition: CSEInfo.cpp:225
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::GISelCSEInfo::analyze
void analyze(MachineFunction &MF)
Definition: CSEInfo.cpp:234
llvm::MCID::Flag
Flag
These should be considered private to the implementation of the MCInstrDesc class.
Definition: MCInstrDesc.h:147
llvm::GISelInstProfileBuilder::addNodeIDRegNum
const GISelInstProfileBuilder & addNodeIDRegNum(Register Reg) const
Definition: CSEInfo.cpp:345
llvm::GISelInstProfileBuilder::addNodeIDImmediate
const GISelInstProfileBuilder & addNodeIDImmediate(int64_t Imm) const
Definition: CSEInfo.cpp:339
llvm::GISelInstProfileBuilder::GISelInstProfileBuilder
GISelInstProfileBuilder(FoldingSetNodeID &ID, const MachineRegisterInfo &MRI)
Definition: CSEInfo.h:172
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:26
llvm::CSEConfigBase
Definition: CSEConfigBase.h:17
llvm::GISelCSEInfo::createdInstr
void createdInstr(MachineInstr &MI) override
An instruction has been created and inserted into the function.
Definition: CSEInfo.cpp:226
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::CSEConfigFull::shouldCSEOpc
virtual bool shouldCSEOpc(unsigned Opc) override
------— CSEConfigFull -------— ///
Definition: CSEInfo.cpp:36
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::GISelCSEAnalysisWrapperPass::GISelCSEAnalysisWrapperPass
GISelCSEAnalysisWrapperPass()
Definition: CSEInfo.cpp:19
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
MachineFunctionPass.h
llvm::CSEMIRBuilder
Defines a builder that does CSE of MachineInstructions using GISelCSEInfo.
Definition: CSEMIRBuilder.h:32
llvm::MachineFunction
Definition: MachineFunction.h:227
llvm::GISelCSEAnalysisWrapperPass::getCSEWrapper
GISelCSEAnalysisWrapper & getCSEWrapper()
Definition: CSEInfo.h:230
llvm::FoldingSet
FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...
Definition: FoldingSet.h:493
llvm::GISelCSEInfo::setCSEConfig
void setCSEConfig(std::unique_ptr< CSEConfigBase > Opt)
Definition: CSEInfo.h:144
llvm::FoldingSetBase::Node
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:133
llvm::getStandardCSEConfigForOpt
std::unique_ptr< CSEConfigBase > getStandardCSEConfigForOpt(CodeGenOpt::Level Level)
Definition: CSEInfo.cpp:73
llvm::GISelCSEInfo::countOpcodeHit
void countOpcodeHit(unsigned Opc)
Definition: CSEInfo.cpp:166
llvm::GISelCSEAnalysisWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: CSEInfo.cpp:419
llvm::GISelCSEAnalysisWrapper::setComputed
void setComputed(bool Computed)
Definition: CSEInfo.h:215
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:313
llvm::PICLevel::Level
Level
Definition: CodeGen.h:33
llvm::CodeGenOpt::Level
Level
Definition: CodeGen.h:52
llvm::GISelCSEInfo::handleRecordedInsts
void handleRecordedInsts()
Use this callback to insert all the recorded instructions.
Definition: CSEInfo.cpp:213
llvm::GISelChangeObserver
Abstract class that contains various methods for clients to notify about changes.
Definition: GISelChangeObserver.h:29
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
GISelWorkList.h
FoldingSet.h
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::GISelInstProfileBuilder::addNodeIDFlag
const GISelInstProfileBuilder & addNodeIDFlag(unsigned Flag) const
Definition: CSEInfo.cpp:363
llvm::GISelInstProfileBuilder
Definition: CSEInfo.h:167
llvm::Error
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
llvm::GISelCSEInfo::releaseMemory
void releaseMemory()
Definition: CSEInfo.cpp:248
llvm::CSEConfigConstantOnly::shouldCSEOpc
virtual bool shouldCSEOpc(unsigned Opc) override
Definition: CSEInfo.cpp:68
llvm::GISelCSEInfo::verify
Error verify()
Definition: CSEInfo.cpp:262
llvm::GISelCSEAnalysisWrapper
Simple wrapper that does the following.
Definition: CSEInfo.h:202
llvm::GISelCSEInfo::setMF
void setMF(MachineFunction &MF)
-----— GISelCSEInfo ----------—//
Definition: CSEInfo.cpp:85
llvm::CSEConfigFull
Definition: CSEInfo.h:39
CodeGen.h
llvm::GISelCSEInfo::GISelCSEInfo
GISelCSEInfo()=default
llvm::UniqueMachineInstr::Profile
void Profile(FoldingSetNodeID &ID)
-----— UniqueMachineInstr ----------—//
Definition: CSEInfo.cpp:30
llvm::GISelWorkList< 8 >
llvm::GISelCSEInfo::print
void print()
Definition: CSEInfo.cpp:294
llvm::GISelCSEAnalysisWrapperPass::ID
static char ID
Definition: CSEInfo.h:224
GISelChangeObserver.h
llvm::GISelCSEInfo::changingInstr
void changingInstr(MachineInstr &MI) override
This instruction is about to be mutated in some way.
Definition: CSEInfo.cpp:227
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::LLT
Definition: LowLevelTypeImpl.h:40