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