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//===----------------------------------------------------------------------===//
11#include "llvm/CodeGen/GlobalISel/CSEInfo.h"
12#include "llvm/CodeGen/MachineRegisterInfo.h"
13#include "llvm/InitializePasses.h"
14#include "llvm/Support/Error.h"
15
16#define DEBUG_TYPE "cseinfo"
17
18using namespace llvm;
19char llvm::GISelCSEAnalysisWrapperPass::ID = 0;
20GISelCSEAnalysisWrapperPass::GISelCSEAnalysisWrapperPass()
21 : MachineFunctionPass(ID) {
22 initializeGISelCSEAnalysisWrapperPassPass(*PassRegistry::getPassRegistry());
23}
24INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
25 "Analysis containing CSE Info", false, true)
26INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
27 "Analysis containing CSE Info", false, true)
28
29/// -------- UniqueMachineInstr -------------//
30
31void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
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
73bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
74 return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_FCONSTANT ||
75 Opc == TargetOpcode::G_IMPLICIT_DEF;
76}
77
78std::unique_ptr<CSEConfigBase>
79llvm::getStandardCSEConfigForOpt(CodeGenOptLevel Level) {
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 -------------//
91void GISelCSEInfo::setMF(MachineFunction &MF) {
92 this->MF = &MF;
93 this->MRI = &MF.getRegInfo();
94}
95
96GISelCSEInfo::~GISelCSEInfo() = default;
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(N: 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,
115 MachineBasicBlock *MBB,
116 void *&InsertPos) {
117 auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
118 if (Node) {
119 if (!isUniqueMachineInstValid(UMI: *Node)) {
120 invalidateUniqueMachineInstr(UMI: 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) {
131 handleRecordedInsts();
132 assert(UMI);
133 UniqueMachineInstr *MaybeNewNode = UMI;
134 if (InsertPos)
135 CSEMap.InsertNode(N: UMI, InsertPos);
136 else
137 MaybeNewNode = CSEMap.GetOrInsertNode(N: 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(I: MI);
157 auto *Node = getUniqueInstrForMI(MI);
158 insertNode(UMI: Node, InsertPos);
159}
160
161MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
162 MachineBasicBlock *MBB,
163 void *&InsertPos) {
164 handleRecordedInsts();
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
172void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
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
182void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {
183 if (shouldCSE(Opc: MI->getOpcode())) {
184 TemporaryInsts.insert(I: MI);
185 LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
186 }
187}
188
189void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {
190 assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
191 auto *UMI = InstrMapping.lookup(Val: MI);
192 LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
193 if (UMI) {
194 // Invalidate this MI.
195 invalidateUniqueMachineInstr(UMI);
196 InstrMapping.erase(Val: 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, InsertPos: nullptr);
204 } else {
205 /// This is a new instruction. Allocate a new UniqueMachineInstr and
206 /// Insert.
207 insertInstr(MI);
208 }
209}
210
211void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {
212 if (auto *UMI = InstrMapping.lookup(Val: MI)) {
213 invalidateUniqueMachineInstr(UMI);
214 InstrMapping.erase(Val: MI);
215 }
216 TemporaryInsts.remove(I: MI);
217}
218
219void GISelCSEInfo::handleRecordedInsts() {
220 if (HandlingRecordedInstrs)
221 return;
222 HandlingRecordedInstrs = true;
223 while (!TemporaryInsts.empty()) {
224 auto *MI = TemporaryInsts.pop_back_val();
225 handleRecordedInst(MI);
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
235void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(MI: &MI); }
236void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(MI: &MI); }
237void GISelCSEInfo::changingInstr(MachineInstr &MI) {
238 // For now, perform erase, followed by insert.
239 erasingInstr(MI);
240 createdInstr(MI);
241}
242void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
243
244void GISelCSEInfo::analyze(MachineFunction &MF) {
245 setMF(MF);
246 for (auto &MBB : MF) {
247 for (MachineInstr &MI : MBB) {
248 if (!shouldCSE(Opc: MI.getOpcode()))
249 continue;
250 LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
251 insertInstr(MI: &MI);
252 }
253 }
254}
255
256void GISelCSEInfo::releaseMemory() {
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) {
272 raw_string_ostream OS(S);
273 OS << *MI;
274 return OS.str().c_str();
275}
276#endif
277
278Error GISelCSEInfo::verify() {
279#ifndef NDEBUG
280 std::string S1, S2;
281 handleRecordedInsts();
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
315void GISelCSEInfo::print() {
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 --- //
324const GISelInstProfileBuilder &
325GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {
326 addNodeIDMBB(MBB: MI->getParent());
327 addNodeIDOpcode(Opc: MI->getOpcode());
328 for (const auto &Op : MI->operands())
329 addNodeIDMachineOperand(MO: Op);
330 addNodeIDFlag(Flag: MI->getFlags());
331 return *this;
332}
333
334const GISelInstProfileBuilder &
335GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
336 ID.AddInteger(I: Opc);
337 return *this;
338}
339
340const GISelInstProfileBuilder &
341GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const {
342 uint64_t Val = Ty.getUniqueRAWLLTData();
343 ID.AddInteger(I: Val);
344 return *this;
345}
346
347const GISelInstProfileBuilder &
348GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
349 ID.AddPointer(Ptr: RC);
350 return *this;
351}
352
353const GISelInstProfileBuilder &
354GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
355 ID.AddPointer(Ptr: RB);
356 return *this;
357}
358
359const GISelInstProfileBuilder &
360GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
361 ID.AddInteger(I: Imm);
362 return *this;
363}
364
365const GISelInstProfileBuilder &
366GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const {
367 ID.AddInteger(I: Reg);
368 return *this;
369}
370
371const GISelInstProfileBuilder &
372GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const {
373 addNodeIDMachineOperand(MO: MachineOperand::CreateReg(Reg, isDef: false));
374 return *this;
375}
376
377const GISelInstProfileBuilder &
378GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
379 ID.AddPointer(Ptr: MBB);
380 return *this;
381}
382
383const GISelInstProfileBuilder &
384GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
385 if (Flag)
386 ID.AddInteger(I: Flag);
387 return *this;
388}
389
390const GISelInstProfileBuilder &
391GISelInstProfileBuilder::addNodeIDReg(Register Reg) const {
392 LLT Ty = MRI.getType(Reg);
393 if (Ty.isValid())
394 addNodeIDRegType(Ty);
395
396 if (const RegClassOrRegBank &RCOrRB = MRI.getRegClassOrRegBank(Reg)) {
397 if (const auto *RB = dyn_cast_if_present<const RegisterBank *>(Val: RCOrRB))
398 addNodeIDRegType(RB);
399 else if (const auto *RC =
400 dyn_cast_if_present<const TargetRegisterClass *>(Val: RCOrRB))
401 addNodeIDRegType(RC);
402 }
403 return *this;
404}
405
406const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
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(I: MO.getImm());
418 else if (MO.isCImm())
419 ID.AddPointer(Ptr: MO.getCImm());
420 else if (MO.isFPImm())
421 ID.AddPointer(Ptr: MO.getFPImm());
422 else if (MO.isPredicate())
423 ID.AddInteger(I: MO.getPredicate());
424 else
425 llvm_unreachable("Unhandled operand type");
426 // Handle other types
427 return *this;
428}
429
430GISelCSEInfo &
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&: *MF);
437 AlreadyComputed = true;
438 }
439 return Info;
440}
441void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
442 AU.setPreservesAll();
443 MachineFunctionPass::getAnalysisUsage(AU);
444}
445
446bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
447 releaseMemory();
448 Wrapper.setMF(MF);
449 return false;
450}
451