LLVM 17.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 == CodeGenOpt::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 while (!TemporaryInsts.empty()) {
221 auto *MI = TemporaryInsts.pop_back_val();
223 }
224}
225
226bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
227 assert(CSEOpt.get() && "CSEConfig not set");
228 return CSEOpt->shouldCSEOpc(Opc);
229}
230
234 // For now, perform erase, followed by insert.
237}
239
241 setMF(MF);
242 for (auto &MBB : MF) {
243 if (MBB.empty())
244 continue;
245 for (MachineInstr &MI : MBB) {
246 if (!shouldCSE(MI.getOpcode()))
247 continue;
248 LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
249 insertInstr(&MI);
250 }
251 }
252}
253
255 print();
256 CSEMap.clear();
257 InstrMapping.clear();
258 UniqueInstrAllocator.Reset();
259 TemporaryInsts.clear();
260 CSEOpt.reset();
261 MRI = nullptr;
262 MF = nullptr;
263#ifndef NDEBUG
264 OpcodeHitTable.clear();
265#endif
266}
267
268#ifndef NDEBUG
269static const char *stringify(const MachineInstr *MI, std::string &S) {
270 raw_string_ostream OS(S);
271 OS << *MI;
272 return OS.str().c_str();
273}
274#endif
275
277#ifndef NDEBUG
278 std::string S1, S2;
280 // For each instruction in map from MI -> UMI,
281 // Profile(MI) and make sure UMI is found for that profile.
282 for (auto &It : InstrMapping) {
283 FoldingSetNodeID TmpID;
284 GISelInstProfileBuilder(TmpID, *MRI).addNodeID(It.first);
285 void *InsertPos;
286 UniqueMachineInstr *FoundNode =
287 CSEMap.FindNodeOrInsertPos(TmpID, InsertPos);
288 if (FoundNode != It.second)
289 return createStringError(std::errc::not_supported,
290 "CSEMap mismatch, InstrMapping has MIs without "
291 "corresponding Nodes in CSEMap:\n%s",
292 stringify(It.second->MI, S1));
293 }
294
295 // For every node in the CSEMap, make sure that the InstrMapping
296 // points to it.
297 for (const UniqueMachineInstr &UMI : CSEMap) {
298 if (!InstrMapping.count(UMI.MI))
299 return createStringError(std::errc::not_supported,
300 "Node in CSE without InstrMapping:\n%s",
301 stringify(UMI.MI, S1));
302
303 if (InstrMapping[UMI.MI] != &UMI)
304 return createStringError(std::make_error_code(std::errc::not_supported),
305 "Mismatch in CSE mapping:\n%s\n%s",
306 stringify(InstrMapping[UMI.MI]->MI, S1),
307 stringify(UMI.MI, S2));
308 }
309#endif
310 return Error::success();
311}
312
314 LLVM_DEBUG(for (auto &It
315 : OpcodeHitTable) {
316 dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
317 << "\n";
318 };);
319}
320/// -----------------------------------------
321// ---- Profiling methods for FoldingSetNode --- //
324 addNodeIDMBB(MI->getParent());
325 addNodeIDOpcode(MI->getOpcode());
326 for (const auto &Op : MI->operands())
328 addNodeIDFlag(MI->getFlags());
329 return *this;
330}
331
334 ID.AddInteger(Opc);
335 return *this;
336}
337
340 uint64_t Val = Ty.getUniqueRAWLLTData();
341 ID.AddInteger(Val);
342 return *this;
343}
344
347 ID.AddPointer(RC);
348 return *this;
349}
350
353 ID.AddPointer(RB);
354 return *this;
355}
356
359 ID.AddInteger(Imm);
360 return *this;
361}
362
365 ID.AddInteger(Reg);
366 return *this;
367}
368
372 return *this;
373}
374
377 ID.AddPointer(MBB);
378 return *this;
379}
380
383 if (Flag)
384 ID.AddInteger(Flag);
385 return *this;
386}
387
390 LLT Ty = MRI.getType(Reg);
391 if (Ty.isValid())
393
394 if (const RegClassOrRegBank &RCOrRB = MRI.getRegClassOrRegBank(Reg)) {
395 if (const auto *RB = RCOrRB.dyn_cast<const RegisterBank *>())
397 else if (const auto *RC = RCOrRB.dyn_cast<const TargetRegisterClass *>())
399 }
400 return *this;
401}
402
404 const MachineOperand &MO) const {
405 if (MO.isReg()) {
406 Register Reg = MO.getReg();
407 if (!MO.isDef())
408 addNodeIDRegNum(Reg);
409
410 // Profile the register properties.
411 addNodeIDReg(Reg);
412 assert(!MO.isImplicit() && "Unhandled case");
413 } else if (MO.isImm())
414 ID.AddInteger(MO.getImm());
415 else if (MO.isCImm())
416 ID.AddPointer(MO.getCImm());
417 else if (MO.isFPImm())
418 ID.AddPointer(MO.getFPImm());
419 else if (MO.isPredicate())
420 ID.AddInteger(MO.getPredicate());
421 else
422 llvm_unreachable("Unhandled operand type");
423 // Handle other types
424 return *this;
425}
426
428GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
429 bool Recompute) {
430 if (!AlreadyComputed || Recompute) {
431 Info.releaseMemory();
432 Info.setCSEConfig(std::move(CSEOpt));
433 Info.analyze(*MF);
434 AlreadyComputed = true;
435 }
436 return Info;
437}
439 AU.setPreservesAll();
441}
442
445 Wrapper.setMF(MF);
446 return false;
447}
MachineBasicBlock & MBB
basic Basic Alias true
block Block Frequency Analysis
static const char * stringify(const MachineInstr *MI, std::string &S)
Definition: CSEInfo.cpp:269
Provides analysis for continuously CSEing during GISel passes.
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#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())
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
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:145
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
static ErrorSuccess success()
Create a success value.
Definition: Error.h:330
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:318
The actual analysis pass wrapper.
Definition: CSEInfo.h:220
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
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: CSEInfo.cpp:438
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: CSEInfo.cpp:443
void setMF(MachineFunction &MFunc)
Definition: CSEInfo.h:214
GISelCSEInfo & get(std::unique_ptr< CSEConfigBase > CSEOpt, bool ReCompute=false)
Takes a CSEConfigBase object that defines what opcodes get CSEd.
Definition: CSEInfo.cpp:428
The CSE Analysis object.
Definition: CSEInfo.h:69
bool shouldCSE(unsigned Opc) const
Definition: CSEInfo.cpp:226
void changingInstr(MachineInstr &MI) override
This instruction is about to be mutated in some way.
Definition: CSEInfo.cpp:233
void analyze(MachineFunction &MF)
Definition: CSEInfo.cpp:240
void changedInstr(MachineInstr &MI) override
This instruction was mutated in some way.
Definition: CSEInfo.cpp:238
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:231
void countOpcodeHit(unsigned Opc)
Definition: CSEInfo.cpp:172
void setCSEConfig(std::unique_ptr< CSEConfigBase > Opt)
Definition: CSEInfo.h:144
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:254
void createdInstr(MachineInstr &MI) override
An instruction has been created and inserted into the function.
Definition: CSEInfo.cpp:232
const GISelInstProfileBuilder & addNodeIDOpcode(unsigned Opc) const
Definition: CSEInfo.cpp:333
const GISelInstProfileBuilder & addNodeIDRegNum(Register Reg) const
Definition: CSEInfo.cpp:364
const GISelInstProfileBuilder & addNodeIDFlag(unsigned Flag) const
Definition: CSEInfo.cpp:382
const GISelInstProfileBuilder & addNodeIDImmediate(int64_t Imm) const
Definition: CSEInfo.cpp:358
const GISelInstProfileBuilder & addNodeIDReg(Register Reg) const
Definition: CSEInfo.cpp:389
const GISelInstProfileBuilder & addNodeID(const MachineInstr *MI) const
Definition: CSEInfo.cpp:323
const GISelInstProfileBuilder & addNodeIDMBB(const MachineBasicBlock *MBB) const
Definition: CSEInfo.cpp:376
const GISelInstProfileBuilder & addNodeIDRegType(const LLT Ty) const
Definition: CSEInfo.cpp:339
const GISelInstProfileBuilder & addNodeIDMachineOperand(const MachineOperand &MO) const
Definition: CSEInfo.cpp:403
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
constexpr uint64_t getUniqueRAWLLTData() const
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...
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:118
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:642
std::string & str()
Returns the string's reference.
Definition: raw_ostream.h:660
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Level
Code generation optimization level.
Definition: CodeGen.h:57
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:1246
std::unique_ptr< CSEConfigBase > getStandardCSEConfigForOpt(CodeGenOpt::Level Level)
Definition: CSEInfo.cpp:79
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void initializeGISelCSEAnalysisWrapperPassPass(PassRegistry &)