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     return true;
65   }
66   return false;
67 }
68 
69 bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
70   return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_IMPLICIT_DEF;
71 }
72 
73 std::unique_ptr<CSEConfigBase>
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 -------------//
86 void GISelCSEInfo::setMF(MachineFunction &MF) {
87   this->MF = &MF;
88   this->MRI = &MF.getRegInfo();
89 }
90 
91 GISelCSEInfo::~GISelCSEInfo() {}
92 
93 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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
214 void GISelCSEInfo::handleRecordedInsts() {
215   while (!TemporaryInsts.empty()) {
216     auto *MI = TemporaryInsts.pop_back_val();
217     handleRecordedInst(MI);
218   }
219 }
220 
221 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
222   assert(CSEOpt.get() && "CSEConfig not set");
223   return CSEOpt->shouldCSEOpc(Opc);
224 }
225 
226 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
227 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
228 void GISelCSEInfo::changingInstr(MachineInstr &MI) {
229   // For now, perform erase, followed by insert.
230   erasingInstr(MI);
231   createdInstr(MI);
232 }
233 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
234 
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 
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
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 
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 
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 &
318 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 &
328 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
329   ID.AddInteger(Opc);
330   return *this;
331 }
332 
333 const GISelInstProfileBuilder &
334 GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const {
335   uint64_t Val = Ty.getUniqueRAWLLTData();
336   ID.AddInteger(Val);
337   return *this;
338 }
339 
340 const GISelInstProfileBuilder &
341 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
342   ID.AddPointer(RC);
343   return *this;
344 }
345 
346 const GISelInstProfileBuilder &
347 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
348   ID.AddPointer(RB);
349   return *this;
350 }
351 
352 const GISelInstProfileBuilder &
353 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
354   ID.AddInteger(Imm);
355   return *this;
356 }
357 
358 const GISelInstProfileBuilder &
359 GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const {
360   ID.AddInteger(Reg);
361   return *this;
362 }
363 
364 const GISelInstProfileBuilder &
365 GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const {
366   addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
367   return *this;
368 }
369 
370 const GISelInstProfileBuilder &
371 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
372   ID.AddPointer(MBB);
373   return *this;
374 }
375 
376 const GISelInstProfileBuilder &
377 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
378   if (Flag)
379     ID.AddInteger(Flag);
380   return *this;
381 }
382 
383 const GISelInstProfileBuilder &
384 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 
398 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 &
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 }
433 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
434   AU.setPreservesAll();
435   MachineFunctionPass::getAnalysisUsage(AU);
436 }
437 
438 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
439   releaseMemory();
440   Wrapper.setMF(MF);
441   return false;
442 }
443