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 return true;
69 }
70 return false;
71 }
72
shouldCSEOpc(unsigned Opc)73 bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
74 return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_FCONSTANT ||
75 Opc == TargetOpcode::G_IMPLICIT_DEF;
76 }
77
78 std::unique_ptr<CSEConfigBase>
getStandardCSEConfigForOpt(CodeGenOpt::Level Level)79 llvm::getStandardCSEConfigForOpt(CodeGenOpt::Level Level) {
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 -------------//
setMF(MachineFunction & MF)91 void GISelCSEInfo::setMF(MachineFunction &MF) {
92 this->MF = &MF;
93 this->MRI = &MF.getRegInfo();
94 }
95
96 GISelCSEInfo::~GISelCSEInfo() = default;
97
isUniqueMachineInstValid(const UniqueMachineInstr & UMI) const98 bool 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
invalidateUniqueMachineInstr(UniqueMachineInstr * UMI)107 void 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
getNodeIfExists(FoldingSetNodeID & ID,MachineBasicBlock * MBB,void * & InsertPos)114 UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
115 MachineBasicBlock *MBB,
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
insertNode(UniqueMachineInstr * UMI,void * InsertPos)130 void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
131 handleRecordedInsts();
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
getUniqueInstrForMI(const MachineInstr * MI)147 UniqueMachineInstr *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
insertInstr(MachineInstr * MI,void * InsertPos)153 void 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
getMachineInstrIfExists(FoldingSetNodeID & ID,MachineBasicBlock * MBB,void * & InsertPos)161 MachineInstr *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
countOpcodeHit(unsigned Opc)172 void 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
recordNewInstruction(MachineInstr * MI)182 void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {
183 if (shouldCSE(MI->getOpcode())) {
184 TemporaryInsts.insert(MI);
185 LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
186 }
187 }
188
handleRecordedInst(MachineInstr * MI)189 void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {
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
handleRemoveInst(MachineInstr * MI)211 void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {
212 if (auto *UMI = InstrMapping.lookup(MI)) {
213 invalidateUniqueMachineInstr(UMI);
214 InstrMapping.erase(MI);
215 }
216 TemporaryInsts.remove(MI);
217 }
218
handleRecordedInsts()219 void GISelCSEInfo::handleRecordedInsts() {
220 while (!TemporaryInsts.empty()) {
221 auto *MI = TemporaryInsts.pop_back_val();
222 handleRecordedInst(MI);
223 }
224 }
225
shouldCSE(unsigned Opc) const226 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
227 assert(CSEOpt.get() && "CSEConfig not set");
228 return CSEOpt->shouldCSEOpc(Opc);
229 }
230
erasingInstr(MachineInstr & MI)231 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
createdInstr(MachineInstr & MI)232 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
changingInstr(MachineInstr & MI)233 void GISelCSEInfo::changingInstr(MachineInstr &MI) {
234 // For now, perform erase, followed by insert.
235 erasingInstr(MI);
236 createdInstr(MI);
237 }
changedInstr(MachineInstr & MI)238 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
239
analyze(MachineFunction & MF)240 void GISelCSEInfo::analyze(MachineFunction &MF) {
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
releaseMemory()254 void GISelCSEInfo::releaseMemory() {
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
stringify(const MachineInstr * MI,std::string & S)269 static 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
verify()276 Error GISelCSEInfo::verify() {
277 #ifndef NDEBUG
278 std::string S1, S2;
279 handleRecordedInsts();
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
print()313 void GISelCSEInfo::print() {
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 --- //
322 const GISelInstProfileBuilder &
addNodeID(const MachineInstr * MI) const323 GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {
324 addNodeIDMBB(MI->getParent());
325 addNodeIDOpcode(MI->getOpcode());
326 for (const auto &Op : MI->operands())
327 addNodeIDMachineOperand(Op);
328 addNodeIDFlag(MI->getFlags());
329 return *this;
330 }
331
332 const GISelInstProfileBuilder &
addNodeIDOpcode(unsigned Opc) const333 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
334 ID.AddInteger(Opc);
335 return *this;
336 }
337
338 const GISelInstProfileBuilder &
addNodeIDRegType(const LLT Ty) const339 GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const {
340 uint64_t Val = Ty.getUniqueRAWLLTData();
341 ID.AddInteger(Val);
342 return *this;
343 }
344
345 const GISelInstProfileBuilder &
addNodeIDRegType(const TargetRegisterClass * RC) const346 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
347 ID.AddPointer(RC);
348 return *this;
349 }
350
351 const GISelInstProfileBuilder &
addNodeIDRegType(const RegisterBank * RB) const352 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
353 ID.AddPointer(RB);
354 return *this;
355 }
356
357 const GISelInstProfileBuilder &
addNodeIDImmediate(int64_t Imm) const358 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
359 ID.AddInteger(Imm);
360 return *this;
361 }
362
363 const GISelInstProfileBuilder &
addNodeIDRegNum(Register Reg) const364 GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const {
365 ID.AddInteger(Reg);
366 return *this;
367 }
368
369 const GISelInstProfileBuilder &
addNodeIDRegType(const Register Reg) const370 GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const {
371 addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
372 return *this;
373 }
374
375 const GISelInstProfileBuilder &
addNodeIDMBB(const MachineBasicBlock * MBB) const376 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
377 ID.AddPointer(MBB);
378 return *this;
379 }
380
381 const GISelInstProfileBuilder &
addNodeIDFlag(unsigned Flag) const382 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
383 if (Flag)
384 ID.AddInteger(Flag);
385 return *this;
386 }
387
388 const GISelInstProfileBuilder &
addNodeIDReg(Register Reg) const389 GISelInstProfileBuilder::addNodeIDReg(Register Reg) const {
390 LLT Ty = MRI.getType(Reg);
391 if (Ty.isValid())
392 addNodeIDRegType(Ty);
393
394 if (const RegClassOrRegBank &RCOrRB = MRI.getRegClassOrRegBank(Reg)) {
395 if (const auto *RB = RCOrRB.dyn_cast<const RegisterBank *>())
396 addNodeIDRegType(RB);
397 else if (const auto *RC = RCOrRB.dyn_cast<const TargetRegisterClass *>())
398 addNodeIDRegType(RC);
399 }
400 return *this;
401 }
402
addNodeIDMachineOperand(const MachineOperand & MO) const403 const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
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
427 GISelCSEInfo &
get(std::unique_ptr<CSEConfigBase> CSEOpt,bool Recompute)428 GISelCSEAnalysisWrapper::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 }
getAnalysisUsage(AnalysisUsage & AU) const438 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
439 AU.setPreservesAll();
440 MachineFunctionPass::getAnalysisUsage(AU);
441 }
442
runOnMachineFunction(MachineFunction & MF)443 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
444 releaseMemory();
445 Wrapper.setMF(MF);
446 return false;
447 }
448