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