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