LLVM 19.0.0git
CSEInfo.cpp
Go to the documentation of this file.
1//===- CSEInfo.cpp ------------------------------===//
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//
9//
10//===----------------------------------------------------------------------===//
14#include "llvm/Support/Error.h"
15
16#define DEBUG_TYPE "cseinfo"
17
18using namespace llvm;
23}
25 "Analysis containing CSE Info", false, true)
27 "Analysis containing CSE Info", false, true)
28
29/// -------- UniqueMachineInstr -------------//
30
32 GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
33}
34/// -----------------------------------------
35
36/// --------- CSEConfigFull ---------- ///
37bool CSEConfigFull::shouldCSEOpc(unsigned Opc) {
38 switch (Opc) {
39 default:
40 break;
41 case TargetOpcode::G_ADD:
42 case TargetOpcode::G_AND:
43 case TargetOpcode::G_ASHR:
44 case TargetOpcode::G_LSHR:
45 case TargetOpcode::G_MUL:
46 case TargetOpcode::G_OR:
47 case TargetOpcode::G_SHL:
48 case TargetOpcode::G_SUB:
49 case TargetOpcode::G_XOR:
50 case TargetOpcode::G_UDIV:
51 case TargetOpcode::G_SDIV:
52 case TargetOpcode::G_UREM:
53 case TargetOpcode::G_SREM:
54 case TargetOpcode::G_CONSTANT:
55 case TargetOpcode::G_FCONSTANT:
56 case TargetOpcode::G_IMPLICIT_DEF:
57 case TargetOpcode::G_ZEXT:
58 case TargetOpcode::G_SEXT:
59 case TargetOpcode::G_ANYEXT:
60 case TargetOpcode::G_UNMERGE_VALUES:
61 case TargetOpcode::G_TRUNC:
62 case TargetOpcode::G_PTR_ADD:
63 case TargetOpcode::G_EXTRACT:
64 case TargetOpcode::G_SELECT:
65 case TargetOpcode::G_BUILD_VECTOR:
66 case TargetOpcode::G_BUILD_VECTOR_TRUNC:
67 case TargetOpcode::G_SEXT_INREG:
68 return true;
69 }
70 return false;
71}
72
74 return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_FCONSTANT ||
75 Opc == TargetOpcode::G_IMPLICIT_DEF;
76}
77
78std::unique_ptr<CSEConfigBase>
80 std::unique_ptr<CSEConfigBase> Config;
81 if (Level == CodeGenOptLevel::None)
82 Config = std::make_unique<CSEConfigConstantOnly>();
83 else
84 Config = std::make_unique<CSEConfigFull>();
85 return Config;
86}
87
88/// -----------------------------------------
89
90/// -------- GISelCSEInfo -------------//
92 this->MF = &MF;
93 this->MRI = &MF.getRegInfo();
94}
95
97
98bool GISelCSEInfo::isUniqueMachineInstValid(
99 const UniqueMachineInstr &UMI) const {
100 // Should we check here and assert that the instruction has been fully
101 // constructed?
102 // FIXME: Any other checks required to be done here? Remove this method if
103 // none.
104 return true;
105}
106
107void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
108 bool Removed = CSEMap.RemoveNode(UMI);
109 (void)Removed;
110 assert(Removed && "Invalidation called on invalid UMI");
111 // FIXME: Should UMI be deallocated/destroyed?
112}
113
114UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
116 void *&InsertPos) {
117 auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
118 if (Node) {
119 if (!isUniqueMachineInstValid(*Node)) {
120 invalidateUniqueMachineInstr(Node);
121 return nullptr;
122 }
123
124 if (Node->MI->getParent() != MBB)
125 return nullptr;
126 }
127 return Node;
128}
129
130void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
132 assert(UMI);
133 UniqueMachineInstr *MaybeNewNode = UMI;
134 if (InsertPos)
135 CSEMap.InsertNode(UMI, InsertPos);
136 else
137 MaybeNewNode = CSEMap.GetOrInsertNode(UMI);
138 if (MaybeNewNode != UMI) {
139 // A similar node exists in the folding set. Let's ignore this one.
140 return;
141 }
142 assert(InstrMapping.count(UMI->MI) == 0 &&
143 "This instruction should not be in the map");
144 InstrMapping[UMI->MI] = MaybeNewNode;
145}
146
147UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
148 assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
149 auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
150 return Node;
151}
152
153void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {
154 assert(MI);
155 // If it exists in temporary insts, remove it.
156 TemporaryInsts.remove(MI);
157 auto *Node = getUniqueInstrForMI(MI);
158 insertNode(Node, InsertPos);
159}
160
161MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
163 void *&InsertPos) {
165 if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {
166 LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;);
167 return const_cast<MachineInstr *>(Inst->MI);
168 }
169 return nullptr;
170}
171
173#ifndef NDEBUG
174 if (OpcodeHitTable.count(Opc))
175 OpcodeHitTable[Opc] += 1;
176 else
177 OpcodeHitTable[Opc] = 1;
178#endif
179 // Else do nothing.
180}
181
183 if (shouldCSE(MI->getOpcode())) {
184 TemporaryInsts.insert(MI);
185 LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
186 }
187}
188
190 assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
191 auto *UMI = InstrMapping.lookup(MI);
192 LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
193 if (UMI) {
194 // Invalidate this MI.
195 invalidateUniqueMachineInstr(UMI);
196 InstrMapping.erase(MI);
197 }
198 /// Now insert the new instruction.
199 if (UMI) {
200 /// We'll reuse the same UniqueMachineInstr to avoid the new
201 /// allocation.
202 *UMI = UniqueMachineInstr(MI);
203 insertNode(UMI, nullptr);
204 } else {
205 /// This is a new instruction. Allocate a new UniqueMachineInstr and
206 /// Insert.
207 insertInstr(MI);
208 }
209}
210
212 if (auto *UMI = InstrMapping.lookup(MI)) {
213 invalidateUniqueMachineInstr(UMI);
214 InstrMapping.erase(MI);
215 }
216 TemporaryInsts.remove(MI);
217}
218
220 if (HandlingRecordedInstrs)
221 return;
222 HandlingRecordedInstrs = true;
223 while (!TemporaryInsts.empty()) {
224 auto *MI = TemporaryInsts.pop_back_val();
226 }
227 HandlingRecordedInstrs = false;
228}
229
230bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
231 assert(CSEOpt.get() && "CSEConfig not set");
232 return CSEOpt->shouldCSEOpc(Opc);
233}
234
238 // For now, perform erase, followed by insert.
241}
243
245 setMF(MF);
246 for (auto &MBB : MF) {
247 for (MachineInstr &MI : MBB) {
248 if (!shouldCSE(MI.getOpcode()))
249 continue;
250 LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
251 insertInstr(&MI);
252 }
253 }
254}
255
257 print();
258 CSEMap.clear();
259 InstrMapping.clear();
260 UniqueInstrAllocator.Reset();
261 TemporaryInsts.clear();
262 CSEOpt.reset();
263 MRI = nullptr;
264 MF = nullptr;
265#ifndef NDEBUG
266 OpcodeHitTable.clear();
267#endif
268}
269
270#ifndef NDEBUG
271static const char *stringify(const MachineInstr *MI, std::string &S) {
273 OS << *MI;
274 return OS.str().c_str();
275}
276#endif
277
279#ifndef NDEBUG
280 std::string S1, S2;
282 // For each instruction in map from MI -> UMI,
283 // Profile(MI) and make sure UMI is found for that profile.
284 for (auto &It : InstrMapping) {
285 FoldingSetNodeID TmpID;
286 GISelInstProfileBuilder(TmpID, *MRI).addNodeID(It.first);
287 void *InsertPos;
288 UniqueMachineInstr *FoundNode =
289 CSEMap.FindNodeOrInsertPos(TmpID, InsertPos);
290 if (FoundNode != It.second)
291 return createStringError(std::errc::not_supported,
292 "CSEMap mismatch, InstrMapping has MIs without "
293 "corresponding Nodes in CSEMap:\n%s",
294 stringify(It.second->MI, S1));
295 }
296
297 // For every node in the CSEMap, make sure that the InstrMapping
298 // points to it.
299 for (const UniqueMachineInstr &UMI : CSEMap) {
300 if (!InstrMapping.count(UMI.MI))
301 return createStringError(std::errc::not_supported,
302 "Node in CSE without InstrMapping:\n%s",
303 stringify(UMI.MI, S1));
304
305 if (InstrMapping[UMI.MI] != &UMI)
306 return createStringError(std::make_error_code(std::errc::not_supported),
307 "Mismatch in CSE mapping:\n%s\n%s",
308 stringify(InstrMapping[UMI.MI]->MI, S1),
309 stringify(UMI.MI, S2));
310 }
311#endif
312 return Error::success();
313}
314
316 LLVM_DEBUG(for (auto &It
317 : OpcodeHitTable) {
318 dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
319 << "\n";
320 };);
321}
322/// -----------------------------------------
323// ---- Profiling methods for FoldingSetNode --- //
326 addNodeIDMBB(MI->getParent());
327 addNodeIDOpcode(MI->getOpcode());
328 for (const auto &Op : MI->operands())
330 addNodeIDFlag(MI->getFlags());
331 return *this;
332}
333
336 ID.AddInteger(Opc);
337 return *this;
338}
339
342 uint64_t Val = Ty.getUniqueRAWLLTData();
343 ID.AddInteger(Val);
344 return *this;
345}
346
349 ID.AddPointer(RC);
350 return *this;
351}
352
355 ID.AddPointer(RB);
356 return *this;
357}
358
361 ID.AddInteger(Imm);
362 return *this;
363}
364
367 ID.AddInteger(Reg);
368 return *this;
369}
370
374 return *this;
375}
376
379 ID.AddPointer(MBB);
380 return *this;
381}
382
385 if (Flag)
386 ID.AddInteger(Flag);
387 return *this;
388}
389
392 LLT Ty = MRI.getType(Reg);
393 if (Ty.isValid())
395
396 if (const RegClassOrRegBank &RCOrRB = MRI.getRegClassOrRegBank(Reg)) {
397 if (const auto *RB = dyn_cast_if_present<const RegisterBank *>(RCOrRB))
399 else if (const auto *RC =
400 dyn_cast_if_present<const TargetRegisterClass *>(RCOrRB))
402 }
403 return *this;
404}
405
407 const MachineOperand &MO) const {
408 if (MO.isReg()) {
409 Register Reg = MO.getReg();
410 if (!MO.isDef())
411 addNodeIDRegNum(Reg);
412
413 // Profile the register properties.
414 addNodeIDReg(Reg);
415 assert(!MO.isImplicit() && "Unhandled case");
416 } else if (MO.isImm())
417 ID.AddInteger(MO.getImm());
418 else if (MO.isCImm())
419 ID.AddPointer(MO.getCImm());
420 else if (MO.isFPImm())
421 ID.AddPointer(MO.getFPImm());
422 else if (MO.isPredicate())
423 ID.AddInteger(MO.getPredicate());
424 else
425 llvm_unreachable("Unhandled operand type");
426 // Handle other types
427 return *this;
428}
429
431GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
432 bool Recompute) {
433 if (!AlreadyComputed || Recompute) {
434 Info.releaseMemory();
435 Info.setCSEConfig(std::move(CSEOpt));
436 Info.analyze(*MF);
437 AlreadyComputed = true;
438 }
439 return Info;
440}
442 AU.setPreservesAll();
444}
445
448 Wrapper.setMF(MF);
449 return false;
450}
MachineBasicBlock & MBB
static const LLT S1
basic Basic Alias true
block Block Frequency Analysis
static const char * stringify(const MachineInstr *MI, std::string &S)
Definition: CSEInfo.cpp:271
Provides analysis for continuously CSEing during GISel passes.
#define LLVM_DEBUG(X)
Definition: Debug.h:101
RelaxConfig Config
Definition: ELF_riscv.cpp:506
#define DEBUG_TYPE
IRTranslator LLVM IR MI
Load MIR Sample Profile
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
separate const offset from Split GEPs to a variadic base and a constant offset for better CSE
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
bool shouldCSEOpc(unsigned Opc) override
Definition: CSEInfo.cpp:73
bool shouldCSEOpc(unsigned Opc) override
------— CSEConfigFull -------— ///
Definition: CSEInfo.cpp:37
This class represents an Operation in the Expression.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
Lightweight error class with error context and mandatory checking.
Definition: Error.h:160
static ErrorSuccess success()
Create a success value.
Definition: Error.h:334
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:319
The actual analysis pass wrapper.
Definition: CSEInfo.h:222
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:236
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: CSEInfo.cpp:441
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: CSEInfo.cpp:446
void setMF(MachineFunction &MFunc)
Definition: CSEInfo.h:216
GISelCSEInfo & get(std::unique_ptr< CSEConfigBase > CSEOpt, bool ReCompute=false)
Takes a CSEConfigBase object that defines what opcodes get CSEd.
Definition: CSEInfo.cpp:431
The CSE Analysis object.
Definition: CSEInfo.h:69
bool shouldCSE(unsigned Opc) const
Definition: CSEInfo.cpp:230
void changingInstr(MachineInstr &MI) override
This instruction is about to be mutated in some way.
Definition: CSEInfo.cpp:237
void analyze(MachineFunction &MF)
Definition: CSEInfo.cpp:244
void changedInstr(MachineInstr &MI) override
This instruction was mutated in some way.
Definition: CSEInfo.cpp:242
void recordNewInstruction(MachineInstr *MI)
Records a newly created inst in a list and lazily insert it to the CSEMap.
Definition: CSEInfo.cpp:182
void setMF(MachineFunction &MF)
-----— GISelCSEInfo ----------—//
Definition: CSEInfo.cpp:91
virtual ~GISelCSEInfo()
void erasingInstr(MachineInstr &MI) override
An instruction is about to be erased.
Definition: CSEInfo.cpp:235
void countOpcodeHit(unsigned Opc)
Definition: CSEInfo.cpp:172
void setCSEConfig(std::unique_ptr< CSEConfigBase > Opt)
Definition: CSEInfo.h:146
void handleRecordedInsts()
Use this callback to insert all the recorded instructions.
Definition: CSEInfo.cpp:219
void handleRecordedInst(MachineInstr *MI)
Use this callback to inform CSE about a newly fully created instruction.
Definition: CSEInfo.cpp:189
void handleRemoveInst(MachineInstr *MI)
Remove this inst from the CSE map.
Definition: CSEInfo.cpp:211
void releaseMemory()
Definition: CSEInfo.cpp:256
void createdInstr(MachineInstr &MI) override
An instruction has been created and inserted into the function.
Definition: CSEInfo.cpp:236
const GISelInstProfileBuilder & addNodeIDOpcode(unsigned Opc) const
Definition: CSEInfo.cpp:335
const GISelInstProfileBuilder & addNodeIDRegNum(Register Reg) const
Definition: CSEInfo.cpp:366
const GISelInstProfileBuilder & addNodeIDFlag(unsigned Flag) const
Definition: CSEInfo.cpp:384
const GISelInstProfileBuilder & addNodeIDImmediate(int64_t Imm) const
Definition: CSEInfo.cpp:360
const GISelInstProfileBuilder & addNodeIDReg(Register Reg) const
Definition: CSEInfo.cpp:391
const GISelInstProfileBuilder & addNodeID(const MachineInstr *MI) const
Definition: CSEInfo.cpp:325
const GISelInstProfileBuilder & addNodeIDMBB(const MachineBasicBlock *MBB) const
Definition: CSEInfo.cpp:378
const GISelInstProfileBuilder & addNodeIDRegType(const LLT Ty) const
Definition: CSEInfo.cpp:341
const GISelInstProfileBuilder & addNodeIDMachineOperand(const MachineOperand &MO) const
Definition: CSEInfo.cpp:406
void insert(MachineInstr *I)
Add the specified instruction to the worklist if it isn't already in it.
Definition: GISelWorkList.h:74
MachineInstr * pop_back_val()
bool empty() const
Definition: GISelWorkList.h:38
void remove(const MachineInstr *I)
Remove I from the worklist if it exists.
Definition: GISelWorkList.h:83
constexpr bool isValid() const
Definition: LowLevelType.h:137
constexpr uint64_t getUniqueRAWLLTData() const
Definition: LowLevelType.h:420
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
Definition: MachineInstr.h:68
MachineOperand class - Representation of each machine instruction operand.
const ConstantInt * getCImm() const
bool isCImm() const
isCImm - Test if this is a MO_CImmediate operand.
int64_t getImm() const
bool isImplicit() const
bool isPredicate() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
Register getReg() const
getReg - Returns the register number.
const ConstantFP * getFPImm() const
unsigned getPredicate() const
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
bool isFPImm() const
isFPImm - Tests if this is a MO_FPImmediate operand.
const RegClassOrRegBank & getRegClassOrRegBank(Register Reg) const
Return the register bank or register class of Reg.
LLT getType(Register Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class implements the register bank concept.
Definition: RegisterBank.h:28
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
A class that wraps MachineInstrs and derives from FoldingSetNode in order to be uniqued in a CSEMap.
Definition: CSEInfo.h:29
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:660
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)
Create formatted StringError object.
Definition: Error.h:1244
std::unique_ptr< CSEConfigBase > getStandardCSEConfigForOpt(CodeGenOptLevel Level)
Definition: CSEInfo.cpp:79
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CodeGenOptLevel
Code generation optimization level.
Definition: CodeGen.h:54
void initializeGISelCSEAnalysisWrapperPassPass(PassRegistry &)