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