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) {}
22INITIALIZE_PASS(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
23 "Analysis containing CSE Info", false, true)
24
25/// -------- UniqueMachineInstr -------------//
26
27void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
28 GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
29}
30/// -----------------------------------------
31
32/// --------- CSEConfigFull ---------- ///
33bool CSEConfigFull::shouldCSEOpc(unsigned Opc) {
34 switch (Opc) {
35 default:
36 break;
37 case TargetOpcode::G_ADD:
38 case TargetOpcode::G_AND:
39 case TargetOpcode::G_ASHR:
40 case TargetOpcode::G_LSHR:
41 case TargetOpcode::G_MUL:
42 case TargetOpcode::G_OR:
43 case TargetOpcode::G_SHL:
44 case TargetOpcode::G_SUB:
45 case TargetOpcode::G_XOR:
46 case TargetOpcode::G_UDIV:
47 case TargetOpcode::G_SDIV:
48 case TargetOpcode::G_UREM:
49 case TargetOpcode::G_SREM:
50 case TargetOpcode::G_CONSTANT:
51 case TargetOpcode::G_FCONSTANT:
52 case TargetOpcode::G_IMPLICIT_DEF:
53 case TargetOpcode::G_ZEXT:
54 case TargetOpcode::G_SEXT:
55 case TargetOpcode::G_ANYEXT:
56 case TargetOpcode::G_UNMERGE_VALUES:
57 case TargetOpcode::G_TRUNC:
58 case TargetOpcode::G_PTR_ADD:
59 case TargetOpcode::G_EXTRACT:
60 case TargetOpcode::G_SELECT:
61 case TargetOpcode::G_BUILD_VECTOR:
62 case TargetOpcode::G_BUILD_VECTOR_TRUNC:
63 case TargetOpcode::G_SEXT_INREG:
64 case TargetOpcode::G_FADD:
65 case TargetOpcode::G_FSUB:
66 case TargetOpcode::G_FMUL:
67 case TargetOpcode::G_FDIV:
68 case TargetOpcode::G_FABS:
69 // TODO: support G_FNEG.
70 case TargetOpcode::G_FMAXNUM:
71 case TargetOpcode::G_FMINNUM:
72 case TargetOpcode::G_FMAXNUM_IEEE:
73 case TargetOpcode::G_FMINNUM_IEEE:
74 return true;
75 }
76 return false;
77}
78
79bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
80 return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_FCONSTANT ||
81 Opc == TargetOpcode::G_IMPLICIT_DEF;
82}
83
84std::unique_ptr<CSEConfigBase>
85llvm::getStandardCSEConfigForOpt(CodeGenOptLevel Level) {
86 std::unique_ptr<CSEConfigBase> Config;
87 if (Level == CodeGenOptLevel::None)
88 Config = std::make_unique<CSEConfigConstantOnly>();
89 else
90 Config = std::make_unique<CSEConfigFull>();
91 return Config;
92}
93
94/// -----------------------------------------
95
96/// -------- GISelCSEInfo -------------//
97void GISelCSEInfo::setMF(MachineFunction &MF) {
98 this->MF = &MF;
99 this->MRI = &MF.getRegInfo();
100}
101
102GISelCSEInfo::~GISelCSEInfo() = default;
103
104bool GISelCSEInfo::isUniqueMachineInstValid(
105 const UniqueMachineInstr &UMI) const {
106 // Should we check here and assert that the instruction has been fully
107 // constructed?
108 // FIXME: Any other checks required to be done here? Remove this method if
109 // none.
110 return true;
111}
112
113void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
114 bool Removed = CSEMap.erase(N: UMI);
115 (void)Removed;
116 assert(Removed && "Invalidation called on invalid UMI");
117 // FIXME: Should UMI be deallocated/destroyed?
118}
119
120UniqueMachineInstr *
121GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID, MachineBasicBlock *MBB,
122 FoldingSetInsertToken &Token) {
123 auto *Node = CSEMap.lookup(ID, Token);
124 if (Node) {
125 if (!isUniqueMachineInstValid(UMI: *Node)) {
126 invalidateUniqueMachineInstr(UMI: Node);
127 return nullptr;
128 }
129
130 if (Node->MI->getParent() != MBB)
131 return nullptr;
132 }
133 return Node;
134}
135
136void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI,
137 FoldingSetInsertToken Token) {
138 handleRecordedInsts();
139 assert(UMI);
140 UniqueMachineInstr *MaybeNewNode = UMI;
141 if (Token)
142 CSEMap.insert(N: UMI, Token);
143 else
144 MaybeNewNode = CSEMap.getOrInsert(N: UMI);
145 if (MaybeNewNode != UMI) {
146 // A similar node exists in the folding set. Let's ignore this one.
147 return;
148 }
149 assert(InstrMapping.count(UMI->MI) == 0 &&
150 "This instruction should not be in the map");
151 InstrMapping[UMI->MI] = MaybeNewNode;
152}
153
154UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
155 assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
156 auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
157 return Node;
158}
159
160void GISelCSEInfo::insertInstr(MachineInstr *MI, FoldingSetInsertToken Token) {
161 assert(MI);
162 // If it exists in temporary insts, remove it.
163 TemporaryInsts.remove(I: MI);
164 auto *Node = getUniqueInstrForMI(MI);
165 insertNode(UMI: Node, Token);
166}
167
168MachineInstr *
169GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
170 MachineBasicBlock *MBB,
171 FoldingSetInsertToken &Token) {
172 handleRecordedInsts();
173 if (auto *Inst = getNodeIfExists(ID, MBB, Token)) {
174 LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI);
175 return const_cast<MachineInstr *>(Inst->MI);
176 }
177 return nullptr;
178}
179
180void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
181#ifndef NDEBUG
182 ++OpcodeHitTable[Opc];
183#endif
184 // Else do nothing.
185}
186
187void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {
188 if (shouldCSE(Opc: MI->getOpcode())) {
189 TemporaryInsts.insert(I: MI);
190 LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
191 }
192}
193
194void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {
195 assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
196 auto *UMI = InstrMapping.lookup(Val: MI);
197 LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
198 if (UMI) {
199 // Invalidate this MI.
200 invalidateUniqueMachineInstr(UMI);
201 InstrMapping.erase(Val: MI);
202 }
203 /// Now insert the new instruction.
204 if (UMI) {
205 /// We'll reuse the same UniqueMachineInstr to avoid the new
206 /// allocation.
207 *UMI = UniqueMachineInstr(MI);
208 insertNode(UMI);
209 } else {
210 /// This is a new instruction. Allocate a new UniqueMachineInstr and
211 /// Insert.
212 insertInstr(MI);
213 }
214}
215
216void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {
217 if (auto *UMI = InstrMapping.lookup(Val: MI)) {
218 invalidateUniqueMachineInstr(UMI);
219 InstrMapping.erase(Val: MI);
220 }
221 TemporaryInsts.remove(I: MI);
222}
223
224void GISelCSEInfo::handleRecordedInsts() {
225 if (HandlingRecordedInstrs)
226 return;
227 HandlingRecordedInstrs = true;
228 while (!TemporaryInsts.empty()) {
229 auto *MI = TemporaryInsts.pop_back_val();
230 handleRecordedInst(MI);
231 }
232 HandlingRecordedInstrs = false;
233}
234
235bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
236 assert(CSEOpt.get() && "CSEConfig not set");
237 return CSEOpt->shouldCSEOpc(Opc);
238}
239
240void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(MI: &MI); }
241void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(MI: &MI); }
242void GISelCSEInfo::changingInstr(MachineInstr &MI) {
243 // For now, perform erase, followed by insert.
244 erasingInstr(MI);
245 createdInstr(MI);
246}
247void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
248
249void GISelCSEInfo::analyze(MachineFunction &MF) {
250 setMF(MF);
251 for (auto &MBB : MF) {
252 for (MachineInstr &MI : MBB) {
253 if (!shouldCSE(Opc: MI.getOpcode()))
254 continue;
255 LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
256 insertInstr(MI: &MI);
257 }
258 }
259}
260
261void GISelCSEInfo::releaseMemory() {
262 print();
263 CSEMap.clear();
264 InstrMapping.clear();
265 UniqueInstrAllocator.Reset();
266 TemporaryInsts.clear();
267 CSEOpt.reset();
268 MRI = nullptr;
269 MF = nullptr;
270#ifndef NDEBUG
271 OpcodeHitTable.clear();
272#endif
273}
274
275#ifndef NDEBUG
276static const char *stringify(const MachineInstr *MI, std::string &S) {
277 raw_string_ostream OS(S);
278 OS << *MI;
279 return OS.str().c_str();
280}
281#endif
282
283Error GISelCSEInfo::verify() {
284#ifndef NDEBUG
285 std::string S1, S2;
286 handleRecordedInsts();
287 // For each instruction in map from MI -> UMI,
288 // Profile(MI) and make sure UMI is found for that profile.
289 for (auto &It : InstrMapping) {
290 FoldingSetNodeID TmpID;
291 GISelInstProfileBuilder(TmpID, *MRI).addNodeID(It.first);
292 FoldingSetInsertToken Token;
293 UniqueMachineInstr *FoundNode = CSEMap.lookup(TmpID, Token);
294 if (FoundNode != It.second)
295 return createStringError(std::errc::not_supported,
296 "CSEMap mismatch, InstrMapping has MIs without "
297 "corresponding Nodes in CSEMap:\n%s",
298 stringify(It.second->MI, S1));
299 }
300
301 // For every node in the CSEMap, make sure that the InstrMapping
302 // points to it.
303 for (const UniqueMachineInstr &UMI : CSEMap) {
304 if (!InstrMapping.count(UMI.MI))
305 return createStringError(std::errc::not_supported,
306 "Node in CSE without InstrMapping:\n%s",
307 stringify(UMI.MI, S1));
308
309 if (InstrMapping[UMI.MI] != &UMI)
310 return createStringError(std::make_error_code(std::errc::not_supported),
311 "Mismatch in CSE mapping:\n%s\n%s",
312 stringify(InstrMapping[UMI.MI]->MI, S1),
313 stringify(UMI.MI, S2));
314 }
315#endif
316 return Error::success();
317}
318
319void GISelCSEInfo::print() {
320 LLVM_DEBUG({
321 for (auto &It : OpcodeHitTable)
322 dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
323 << "\n";
324 });
325}
326/// -----------------------------------------
327// ---- Profiling methods for FoldingSetNode --- //
328const GISelInstProfileBuilder &
329GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {
330 addNodeIDMBB(MBB: MI->getParent());
331 addNodeIDOpcode(Opc: MI->getOpcode());
332 for (const auto &Op : MI->operands())
333 addNodeIDMachineOperand(MO: Op);
334 addNodeIDFlag(Flag: MI->getFlags());
335 return *this;
336}
337
338const GISelInstProfileBuilder &
339GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
340 ID.AddInteger(I: Opc);
341 return *this;
342}
343
344const GISelInstProfileBuilder &
345GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const {
346 uint64_t Val = Ty.getUniqueRAWLLTData();
347 ID.AddInteger(I: Val);
348 return *this;
349}
350
351const GISelInstProfileBuilder &
352GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
353 ID.AddPointer(Ptr: RC);
354 return *this;
355}
356
357const GISelInstProfileBuilder &
358GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
359 ID.AddPointer(Ptr: RB);
360 return *this;
361}
362
363const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDRegType(
364 MachineRegisterInfo::VRegAttrs Attrs) const {
365 addNodeIDRegType(Ty: Attrs.Ty);
366
367 const RegClassOrRegBank &RCOrRB = Attrs.RCOrRB;
368 if (RCOrRB) {
369 if (const auto *RB = dyn_cast_if_present<const RegisterBank *>(Val: RCOrRB))
370 addNodeIDRegType(RB);
371 else
372 addNodeIDRegType(RC: cast<const TargetRegisterClass *>(Val: RCOrRB));
373 }
374 return *this;
375}
376
377const GISelInstProfileBuilder &
378GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
379 ID.AddInteger(I: Imm);
380 return *this;
381}
382
383const GISelInstProfileBuilder &
384GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const {
385 ID.AddInteger(I: Reg.id());
386 return *this;
387}
388
389const GISelInstProfileBuilder &
390GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const {
391 addNodeIDMachineOperand(MO: MachineOperand::CreateReg(Reg, isDef: false));
392 return *this;
393}
394
395const GISelInstProfileBuilder &
396GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
397 ID.AddPointer(Ptr: MBB);
398 return *this;
399}
400
401const GISelInstProfileBuilder &
402GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
403 if (Flag)
404 ID.AddInteger(I: Flag);
405 return *this;
406}
407
408const GISelInstProfileBuilder &
409GISelInstProfileBuilder::addNodeIDReg(Register Reg) const {
410 addNodeIDRegType(Attrs: MRI.getVRegAttrs(Reg));
411 return *this;
412}
413
414const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
415 const MachineOperand &MO) const {
416 if (MO.isReg()) {
417 Register Reg = MO.getReg();
418 if (!MO.isDef())
419 addNodeIDRegNum(Reg);
420
421 // Profile the register properties.
422 addNodeIDReg(Reg);
423 assert(!MO.isImplicit() && "Unhandled case");
424 } else if (MO.isImm())
425 ID.AddInteger(I: MO.getImm());
426 else if (MO.isCImm())
427 ID.AddPointer(Ptr: MO.getCImm());
428 else if (MO.isFPImm())
429 ID.AddPointer(Ptr: MO.getFPImm());
430 else if (MO.isPredicate())
431 ID.AddInteger(I: MO.getPredicate());
432 else
433 llvm_unreachable("Unhandled operand type");
434 // Handle other types
435 return *this;
436}
437
438GISelCSEInfo &
439GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt) {
440 if (!AlreadyComputed) {
441 Info.releaseMemory();
442 Info.setCSEConfig(std::move(CSEOpt));
443 Info.analyze(MF&: *MF);
444 AlreadyComputed = true;
445 }
446 return Info;
447}
448
449AnalysisKey GISelCSEAnalysis::Key;
450
451GISelCSEAnalysis::Result
452GISelCSEAnalysis::run(MachineFunction &MF,
453 MachineFunctionAnalysisManager &MFAM) {
454 std::unique_ptr<GISelCSEInfo> Info = std::make_unique<GISelCSEInfo>();
455 Info->setCSEConfig(getStandardCSEConfigForOpt(Level: TM->getOptLevel()));
456 Info->analyze(MF);
457 return Info;
458}
459
460void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
461 AU.setPreservesAll();
462 MachineFunctionPass::getAnalysisUsage(AU);
463}
464
465bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
466 releaseMemory();
467 Wrapper.setMF(MF);
468 return false;
469}
470