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