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