xref: /llvm-project/llvm/lib/CodeGen/GlobalISel/CSEInfo.cpp (revision 72918fd11dd805b578bbc9c4f36bea3bc96f37b5) 
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;
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 
31 void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
32   GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
33 }
34 /// -----------------------------------------
35 
36 /// --------- CSEConfigFull ---------- ///
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 
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>
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 -------------//
101 void GISelCSEInfo::setMF(MachineFunction &MF) {
102   this->MF = &MF;
103   this->MRI = &MF.getRegInfo();
104 }
105 
106 GISelCSEInfo::~GISelCSEInfo() = default;
107 
108 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 
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 
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 
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 
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 
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 
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 
182 void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
183 #ifndef NDEBUG
184   ++OpcodeHitTable[Opc];
185 #endif
186   // Else do nothing.
187 }
188 
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 
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 
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 
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 
237 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
238   assert(CSEOpt.get() && "CSEConfig not set");
239   return CSEOpt->shouldCSEOpc(Opc);
240 }
241 
242 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
243 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
244 void GISelCSEInfo::changingInstr(MachineInstr &MI) {
245   // For now, perform erase, followed by insert.
246   erasingInstr(MI);
247   createdInstr(MI);
248 }
249 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
250 
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 
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
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 
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 
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 &
332 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 &
342 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
343   ID.AddInteger(Opc);
344   return *this;
345 }
346 
347 const GISelInstProfileBuilder &
348 GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const {
349   uint64_t Val = Ty.getUniqueRAWLLTData();
350   ID.AddInteger(Val);
351   return *this;
352 }
353 
354 const GISelInstProfileBuilder &
355 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
356   ID.AddPointer(RC);
357   return *this;
358 }
359 
360 const GISelInstProfileBuilder &
361 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
362   ID.AddPointer(RB);
363   return *this;
364 }
365 
366 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 &
381 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
382   ID.AddInteger(Imm);
383   return *this;
384 }
385 
386 const GISelInstProfileBuilder &
387 GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const {
388   ID.AddInteger(Reg);
389   return *this;
390 }
391 
392 const GISelInstProfileBuilder &
393 GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const {
394   addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
395   return *this;
396 }
397 
398 const GISelInstProfileBuilder &
399 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
400   ID.AddPointer(MBB);
401   return *this;
402 }
403 
404 const GISelInstProfileBuilder &
405 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
406   if (Flag)
407     ID.AddInteger(Flag);
408   return *this;
409 }
410 
411 const GISelInstProfileBuilder &
412 GISelInstProfileBuilder::addNodeIDReg(Register Reg) const {
413   addNodeIDRegType(MRI.getVRegAttrs(Reg));
414   return *this;
415 }
416 
417 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 &
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 }
452 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
453   AU.setPreservesAll();
454   MachineFunctionPass::getAnalysisUsage(AU);
455 }
456 
457 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
458   releaseMemory();
459   Wrapper.setMF(MF);
460   return false;
461 }
462