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 
14 #define DEBUG_TYPE "cseinfo"
15 
16 using namespace llvm;
17 char llvm::GISelCSEAnalysisWrapperPass::ID = 0;
18 INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
19                       "Analysis containing CSE Info", false, true)
20 INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass, DEBUG_TYPE,
21                     "Analysis containing CSE Info", false, true)
22 
23 /// -------- UniqueMachineInstr -------------//
24 
25 void UniqueMachineInstr::Profile(FoldingSetNodeID &ID) {
26   GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
27 }
28 /// -----------------------------------------
29 
30 /// --------- CSEConfig ---------- ///
31 bool CSEConfig::shouldCSEOpc(unsigned Opc) {
32   switch (Opc) {
33   default:
34     break;
35   case TargetOpcode::G_ADD:
36   case TargetOpcode::G_AND:
37   case TargetOpcode::G_ASHR:
38   case TargetOpcode::G_LSHR:
39   case TargetOpcode::G_MUL:
40   case TargetOpcode::G_OR:
41   case TargetOpcode::G_SHL:
42   case TargetOpcode::G_SUB:
43   case TargetOpcode::G_XOR:
44   case TargetOpcode::G_UDIV:
45   case TargetOpcode::G_SDIV:
46   case TargetOpcode::G_UREM:
47   case TargetOpcode::G_SREM:
48   case TargetOpcode::G_CONSTANT:
49   case TargetOpcode::G_FCONSTANT:
50   case TargetOpcode::G_ZEXT:
51   case TargetOpcode::G_SEXT:
52   case TargetOpcode::G_ANYEXT:
53   case TargetOpcode::G_UNMERGE_VALUES:
54   case TargetOpcode::G_TRUNC:
55     return true;
56   }
57   return false;
58 }
59 
60 bool CSEConfigConstantOnly::shouldCSEOpc(unsigned Opc) {
61   return Opc == TargetOpcode::G_CONSTANT;
62 }
63 /// -----------------------------------------
64 
65 /// -------- GISelCSEInfo -------------//
66 void GISelCSEInfo::setMF(MachineFunction &MF) {
67   this->MF = &MF;
68   this->MRI = &MF.getRegInfo();
69 }
70 
71 GISelCSEInfo::~GISelCSEInfo() {}
72 
73 bool GISelCSEInfo::isUniqueMachineInstValid(
74     const UniqueMachineInstr &UMI) const {
75   // Should we check here and assert that the instruction has been fully
76   // constructed?
77   // FIXME: Any other checks required to be done here? Remove this method if
78   // none.
79   return true;
80 }
81 
82 void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
83   bool Removed = CSEMap.RemoveNode(UMI);
84   (void)Removed;
85   assert(Removed && "Invalidation called on invalid UMI");
86   // FIXME: Should UMI be deallocated/destroyed?
87 }
88 
89 UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
90                                                   MachineBasicBlock *MBB,
91                                                   void *&InsertPos) {
92   auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
93   if (Node) {
94     if (!isUniqueMachineInstValid(*Node)) {
95       invalidateUniqueMachineInstr(Node);
96       return nullptr;
97     }
98 
99     if (Node->MI->getParent() != MBB)
100       return nullptr;
101   }
102   return Node;
103 }
104 
105 void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
106   handleRecordedInsts();
107   assert(UMI);
108   UniqueMachineInstr *MaybeNewNode = UMI;
109   if (InsertPos)
110     CSEMap.InsertNode(UMI, InsertPos);
111   else
112     MaybeNewNode = CSEMap.GetOrInsertNode(UMI);
113   if (MaybeNewNode != UMI) {
114     // A similar node exists in the folding set. Let's ignore this one.
115     return;
116   }
117   assert(InstrMapping.count(UMI->MI) == 0 &&
118          "This instruction should not be in the map");
119   InstrMapping[UMI->MI] = MaybeNewNode;
120 }
121 
122 UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
123   assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
124   auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
125   return Node;
126 }
127 
128 void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {
129   assert(MI);
130   // If it exists in temporary insts, remove it.
131   TemporaryInsts.remove(MI);
132   auto *Node = getUniqueInstrForMI(MI);
133   insertNode(Node, InsertPos);
134 }
135 
136 MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
137                                                     MachineBasicBlock *MBB,
138                                                     void *&InsertPos) {
139   handleRecordedInsts();
140   if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {
141     LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;);
142     return const_cast<MachineInstr *>(Inst->MI);
143   }
144   return nullptr;
145 }
146 
147 void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
148 #ifndef NDEBUG
149   if (OpcodeHitTable.count(Opc))
150     OpcodeHitTable[Opc] += 1;
151   else
152     OpcodeHitTable[Opc] = 1;
153 #endif
154   // Else do nothing.
155 }
156 
157 void GISelCSEInfo::recordNewInstruction(MachineInstr *MI) {
158   if (shouldCSE(MI->getOpcode())) {
159     TemporaryInsts.insert(MI);
160     LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
161   }
162 }
163 
164 void GISelCSEInfo::handleRecordedInst(MachineInstr *MI) {
165   assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
166   auto *UMI = InstrMapping.lookup(MI);
167   LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
168   if (UMI) {
169     // Invalidate this MI.
170     invalidateUniqueMachineInstr(UMI);
171     InstrMapping.erase(MI);
172   }
173   /// Now insert the new instruction.
174   if (UMI) {
175     /// We'll reuse the same UniqueMachineInstr to avoid the new
176     /// allocation.
177     *UMI = UniqueMachineInstr(MI);
178     insertNode(UMI, nullptr);
179   } else {
180     /// This is a new instruction. Allocate a new UniqueMachineInstr and
181     /// Insert.
182     insertInstr(MI);
183   }
184 }
185 
186 void GISelCSEInfo::handleRemoveInst(MachineInstr *MI) {
187   if (auto *UMI = InstrMapping.lookup(MI)) {
188     invalidateUniqueMachineInstr(UMI);
189     InstrMapping.erase(MI);
190   }
191   TemporaryInsts.remove(MI);
192 }
193 
194 void GISelCSEInfo::handleRecordedInsts() {
195   while (!TemporaryInsts.empty()) {
196     auto *MI = TemporaryInsts.pop_back_val();
197     handleRecordedInst(MI);
198   }
199 }
200 
201 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
202   // Only GISel opcodes are CSEable
203   if (!isPreISelGenericOpcode(Opc))
204     return false;
205   assert(CSEOpt.get() && "CSEConfig not set");
206   return CSEOpt->shouldCSEOpc(Opc);
207 }
208 
209 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
210 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
211 void GISelCSEInfo::changingInstr(MachineInstr &MI) {
212   // For now, perform erase, followed by insert.
213   erasingInstr(MI);
214   createdInstr(MI);
215 }
216 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
217 
218 void GISelCSEInfo::analyze(MachineFunction &MF) {
219   setMF(MF);
220   for (auto &MBB : MF) {
221     if (MBB.empty())
222       continue;
223     for (MachineInstr &MI : MBB) {
224       if (!shouldCSE(MI.getOpcode()))
225         continue;
226       LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
227       insertInstr(&MI);
228     }
229   }
230 }
231 
232 void GISelCSEInfo::releaseMemory() {
233   print();
234   CSEMap.clear();
235   InstrMapping.clear();
236   UniqueInstrAllocator.Reset();
237   TemporaryInsts.clear();
238   CSEOpt.reset();
239   MRI = nullptr;
240   MF = nullptr;
241 #ifndef NDEBUG
242   OpcodeHitTable.clear();
243 #endif
244 }
245 
246 void GISelCSEInfo::print() {
247   LLVM_DEBUG(for (auto &It
248                   : OpcodeHitTable) {
249     dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
250            << "\n";
251   };);
252 }
253 /// -----------------------------------------
254 // ---- Profiling methods for FoldingSetNode --- //
255 const GISelInstProfileBuilder &
256 GISelInstProfileBuilder::addNodeID(const MachineInstr *MI) const {
257   addNodeIDMBB(MI->getParent());
258   addNodeIDOpcode(MI->getOpcode());
259   for (auto &Op : MI->operands())
260     addNodeIDMachineOperand(Op);
261   addNodeIDFlag(MI->getFlags());
262   return *this;
263 }
264 
265 const GISelInstProfileBuilder &
266 GISelInstProfileBuilder::addNodeIDOpcode(unsigned Opc) const {
267   ID.AddInteger(Opc);
268   return *this;
269 }
270 
271 const GISelInstProfileBuilder &
272 GISelInstProfileBuilder::addNodeIDRegType(const LLT &Ty) const {
273   uint64_t Val = Ty.getUniqueRAWLLTData();
274   ID.AddInteger(Val);
275   return *this;
276 }
277 
278 const GISelInstProfileBuilder &
279 GISelInstProfileBuilder::addNodeIDRegType(const TargetRegisterClass *RC) const {
280   ID.AddPointer(RC);
281   return *this;
282 }
283 
284 const GISelInstProfileBuilder &
285 GISelInstProfileBuilder::addNodeIDRegType(const RegisterBank *RB) const {
286   ID.AddPointer(RB);
287   return *this;
288 }
289 
290 const GISelInstProfileBuilder &
291 GISelInstProfileBuilder::addNodeIDImmediate(int64_t Imm) const {
292   ID.AddInteger(Imm);
293   return *this;
294 }
295 
296 const GISelInstProfileBuilder &
297 GISelInstProfileBuilder::addNodeIDRegNum(unsigned Reg) const {
298   ID.AddInteger(Reg);
299   return *this;
300 }
301 
302 const GISelInstProfileBuilder &
303 GISelInstProfileBuilder::addNodeIDRegType(const unsigned Reg) const {
304   addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
305   return *this;
306 }
307 
308 const GISelInstProfileBuilder &
309 GISelInstProfileBuilder::addNodeIDMBB(const MachineBasicBlock *MBB) const {
310   ID.AddPointer(MBB);
311   return *this;
312 }
313 
314 const GISelInstProfileBuilder &
315 GISelInstProfileBuilder::addNodeIDFlag(unsigned Flag) const {
316   if (Flag)
317     ID.AddInteger(Flag);
318   return *this;
319 }
320 
321 const GISelInstProfileBuilder &GISelInstProfileBuilder::addNodeIDMachineOperand(
322     const MachineOperand &MO) const {
323   if (MO.isReg()) {
324     unsigned Reg = MO.getReg();
325     if (!MO.isDef())
326       addNodeIDRegNum(Reg);
327     LLT Ty = MRI.getType(Reg);
328     if (Ty.isValid())
329       addNodeIDRegType(Ty);
330     auto *RB = MRI.getRegBankOrNull(Reg);
331     if (RB)
332       addNodeIDRegType(RB);
333     auto *RC = MRI.getRegClassOrNull(Reg);
334     if (RC)
335       addNodeIDRegType(RC);
336     assert(!MO.isImplicit() && "Unhandled case");
337   } else if (MO.isImm())
338     ID.AddInteger(MO.getImm());
339   else if (MO.isCImm())
340     ID.AddPointer(MO.getCImm());
341   else if (MO.isFPImm())
342     ID.AddPointer(MO.getFPImm());
343   else if (MO.isPredicate())
344     ID.AddInteger(MO.getPredicate());
345   else
346     llvm_unreachable("Unhandled operand type");
347   // Handle other types
348   return *this;
349 }
350 
351 GISelCSEInfo &GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfig> CSEOpt,
352                                            bool Recompute) {
353   if (!AlreadyComputed || Recompute) {
354     Info.setCSEConfig(std::move(CSEOpt));
355     Info.analyze(*MF);
356     AlreadyComputed = true;
357   }
358   return Info;
359 }
360 void GISelCSEAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
361   AU.setPreservesAll();
362   MachineFunctionPass::getAnalysisUsage(AU);
363 }
364 
365 bool GISelCSEAnalysisWrapperPass::runOnMachineFunction(MachineFunction &MF) {
366   releaseMemory();
367   Wrapper.setMF(MF);
368   return false;
369 }
370