xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/GlobalISel/CSEInfo.cpp (revision c1d255d3ffdbe447de3ab875bf4e7d7accc5bfc5)
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;
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 
30 void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
31   GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
32 }
33 /// -----------------------------------------
34 
35 /// --------- CSEConfigFull ---------- ///
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 
68 bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
69   return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_IMPLICIT_DEF;
70 }
71 
72 std::unique_ptr<CSEConfigBase>
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 -------------//
85 void GISelCSEInfo::setMF(MachineFunction &MF) {
86   this->MF = &MF;
87   this->MRI = &MF.getRegInfo();
88 }
89 
90 GISelCSEInfo::~GISelCSEInfo() {}
91 
92 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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
213 void GISelCSEInfo::handleRecordedInsts() {
214   while (!TemporaryInsts.empty()) {
215     auto *MI = TemporaryInsts.pop_back_val();
216     handleRecordedInst(MI);
217   }
218 }
219 
220 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
221   assert(CSEOpt.get() && "CSEConfig not set");
222   return CSEOpt->shouldCSEOpc(Opc);
223 }
224 
225 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
226 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
227 void GISelCSEInfo::changingInstr(MachineInstr &MI) {
228   // For now, perform erase, followed by insert.
229   erasingInstr(MI);
230   createdInstr(MI);
231 }
232 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
233 
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 
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 
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 
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 &
305 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 &
315 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
316   ID.AddInteger(Opc);
317   return *this;
318 }
319 
320 const GISelInstProfileBuilder &
321 GISelInstProfileBuilder::addNodeIDRegType(const LLT Ty) const {
322   uint64_t Val = Ty.getUniqueRAWLLTData();
323   ID.AddInteger(Val);
324   return *this;
325 }
326 
327 const GISelInstProfileBuilder &
328 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
329   ID.AddPointer(RC);
330   return *this;
331 }
332 
333 const GISelInstProfileBuilder &
334 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
335   ID.AddPointer(RB);
336   return *this;
337 }
338 
339 const GISelInstProfileBuilder &
340 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
341   ID.AddInteger(Imm);
342   return *this;
343 }
344 
345 const GISelInstProfileBuilder &
346 GISelInstProfileBuilder::addNodeIDRegNum(Register Reg) const {
347   ID.AddInteger(Reg);
348   return *this;
349 }
350 
351 const GISelInstProfileBuilder &
352 GISelInstProfileBuilder::addNodeIDRegType(const Register Reg) const {
353   addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
354   return *this;
355 }
356 
357 const GISelInstProfileBuilder &
358 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
359   ID.AddPointer(MBB);
360   return *this;
361 }
362 
363 const GISelInstProfileBuilder &
364 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
365   if (Flag)
366     ID.AddInteger(Flag);
367   return *this;
368 }
369 
370 const GISelInstProfileBuilder &
371 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 
385 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 &
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 }
420 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
421   AU.setPreservesAll();
422   MachineFunctionPass::getAnalysisUsage(AU);
423 }
424 
425 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
426   releaseMemory();
427   Wrapper.setMF(MF);
428   return false;
429 }
430