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