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