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