1 //===- SPIRVModuleAnalysis.cpp - analysis of global instrs & regs - C++ -*-===//
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 // The analysis collects instructions that should be output at the module level
10 // and performs the global register numbering.
11 //
12 // The results of this analysis are used in AsmPrinter to rename registers
13 // globally and to output required instructions at the module level.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "SPIRVModuleAnalysis.h"
18 #include "SPIRV.h"
19 #include "SPIRVGlobalRegistry.h"
20 #include "SPIRVSubtarget.h"
21 #include "SPIRVTargetMachine.h"
22 #include "SPIRVUtils.h"
23 #include "TargetInfo/SPIRVTargetInfo.h"
24 #include "llvm/CodeGen/MachineModuleInfo.h"
25 #include "llvm/CodeGen/TargetPassConfig.h"
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "spirv-module-analysis"
30 
31 static cl::opt<bool>
32     SPVDumpDeps("spv-dump-deps",
33                 cl::desc("Dump MIR with SPIR-V dependencies info"),
34                 cl::Optional, cl::init(false));
35 
36 char llvm::SPIRVModuleAnalysis::ID = 0;
37 
38 namespace llvm {
39 void initializeSPIRVModuleAnalysisPass(PassRegistry &);
40 } // namespace llvm
41 
42 INITIALIZE_PASS(SPIRVModuleAnalysis, DEBUG_TYPE, "SPIRV module analysis", true,
43                 true)
44 
45 // Retrieve an unsigned from an MDNode with a list of them as operands.
46 static unsigned getMetadataUInt(MDNode *MdNode, unsigned OpIndex,
47                                 unsigned DefaultVal = 0) {
48   if (MdNode && OpIndex < MdNode->getNumOperands()) {
49     const auto &Op = MdNode->getOperand(OpIndex);
50     return mdconst::extract<ConstantInt>(Op)->getZExtValue();
51   }
52   return DefaultVal;
53 }
54 
55 void SPIRVModuleAnalysis::setBaseInfo(const Module &M) {
56   MAI.MaxID = 0;
57   for (int i = 0; i < SPIRV::NUM_MODULE_SECTIONS; i++)
58     MAI.MS[i].clear();
59   MAI.RegisterAliasTable.clear();
60   MAI.InstrsToDelete.clear();
61   MAI.FuncNameMap.clear();
62   MAI.GlobalVarList.clear();
63   MAI.ExtInstSetMap.clear();
64 
65   // TODO: determine memory model and source language from the configuratoin.
66   if (auto MemModel = M.getNamedMetadata("spirv.MemoryModel")) {
67     auto MemMD = MemModel->getOperand(0);
68     MAI.Addr = static_cast<SPIRV::AddressingModel>(getMetadataUInt(MemMD, 0));
69     MAI.Mem = static_cast<SPIRV::MemoryModel>(getMetadataUInt(MemMD, 1));
70   } else {
71     MAI.Mem = SPIRV::MemoryModel::OpenCL;
72     unsigned PtrSize = ST->getPointerSize();
73     MAI.Addr = PtrSize == 32   ? SPIRV::AddressingModel::Physical32
74                : PtrSize == 64 ? SPIRV::AddressingModel::Physical64
75                                : SPIRV::AddressingModel::Logical;
76   }
77   // Get the OpenCL version number from metadata.
78   // TODO: support other source languages.
79   if (auto VerNode = M.getNamedMetadata("opencl.ocl.version")) {
80     MAI.SrcLang = SPIRV::SourceLanguage::OpenCL_C;
81     // Construct version literal in accordance with SPIRV-LLVM-Translator.
82     // TODO: support multiple OCL version metadata.
83     assert(VerNode->getNumOperands() > 0 && "Invalid SPIR");
84     auto VersionMD = VerNode->getOperand(0);
85     unsigned MajorNum = getMetadataUInt(VersionMD, 0, 2);
86     unsigned MinorNum = getMetadataUInt(VersionMD, 1);
87     unsigned RevNum = getMetadataUInt(VersionMD, 2);
88     MAI.SrcLangVersion = (MajorNum * 100 + MinorNum) * 1000 + RevNum;
89   } else {
90     MAI.SrcLang = SPIRV::SourceLanguage::Unknown;
91     MAI.SrcLangVersion = 0;
92   }
93 
94   if (auto ExtNode = M.getNamedMetadata("opencl.used.extensions")) {
95     for (unsigned I = 0, E = ExtNode->getNumOperands(); I != E; ++I) {
96       MDNode *MD = ExtNode->getOperand(I);
97       if (!MD || MD->getNumOperands() == 0)
98         continue;
99       for (unsigned J = 0, N = MD->getNumOperands(); J != N; ++J)
100         MAI.SrcExt.insert(cast<MDString>(MD->getOperand(J))->getString());
101     }
102   }
103 
104   // TODO: check if it's required by default.
105   MAI.ExtInstSetMap[static_cast<unsigned>(SPIRV::InstructionSet::OpenCL_std)] =
106       Register::index2VirtReg(MAI.getNextID());
107 }
108 
109 // Collect MI which defines the register in the given machine function.
110 static void collectDefInstr(Register Reg, const MachineFunction *MF,
111                             SPIRV::ModuleAnalysisInfo *MAI,
112                             SPIRV::ModuleSectionType MSType,
113                             bool DoInsert = true) {
114   assert(MAI->hasRegisterAlias(MF, Reg) && "Cannot find register alias");
115   MachineInstr *MI = MF->getRegInfo().getUniqueVRegDef(Reg);
116   assert(MI && "There should be an instruction that defines the register");
117   MAI->setSkipEmission(MI);
118   if (DoInsert)
119     MAI->MS[MSType].push_back(MI);
120 }
121 
122 void SPIRVModuleAnalysis::collectGlobalEntities(
123     const std::vector<SPIRV::DTSortableEntry *> &DepsGraph,
124     SPIRV::ModuleSectionType MSType,
125     std::function<bool(const SPIRV::DTSortableEntry *)> Pred,
126     bool UsePreOrder = false) {
127   DenseSet<const SPIRV::DTSortableEntry *> Visited;
128   for (const auto *E : DepsGraph) {
129     std::function<void(const SPIRV::DTSortableEntry *)> RecHoistUtil;
130     // NOTE: here we prefer recursive approach over iterative because
131     // we don't expect depchains long enough to cause SO.
132     RecHoistUtil = [MSType, UsePreOrder, &Visited, &Pred,
133                     &RecHoistUtil](const SPIRV::DTSortableEntry *E) {
134       if (Visited.count(E) || !Pred(E))
135         return;
136       Visited.insert(E);
137 
138       // Traversing deps graph in post-order allows us to get rid of
139       // register aliases preprocessing.
140       // But pre-order is required for correct processing of function
141       // declaration and arguments processing.
142       if (!UsePreOrder)
143         for (auto *S : E->getDeps())
144           RecHoistUtil(S);
145 
146       Register GlobalReg = Register::index2VirtReg(MAI.getNextID());
147       bool IsFirst = true;
148       for (auto &U : *E) {
149         const MachineFunction *MF = U.first;
150         Register Reg = U.second;
151         MAI.setRegisterAlias(MF, Reg, GlobalReg);
152         if (!MF->getRegInfo().getUniqueVRegDef(Reg))
153           continue;
154         collectDefInstr(Reg, MF, &MAI, MSType, IsFirst);
155         IsFirst = false;
156         if (E->getIsGV())
157           MAI.GlobalVarList.push_back(MF->getRegInfo().getUniqueVRegDef(Reg));
158       }
159 
160       if (UsePreOrder)
161         for (auto *S : E->getDeps())
162           RecHoistUtil(S);
163     };
164     RecHoistUtil(E);
165   }
166 }
167 
168 // The function initializes global register alias table for types, consts,
169 // global vars and func decls and collects these instruction for output
170 // at module level. Also it collects explicit OpExtension/OpCapability
171 // instructions.
172 void SPIRVModuleAnalysis::processDefInstrs(const Module &M) {
173   std::vector<SPIRV::DTSortableEntry *> DepsGraph;
174 
175   GR->buildDepsGraph(DepsGraph, SPVDumpDeps ? MMI : nullptr);
176 
177   collectGlobalEntities(
178       DepsGraph, SPIRV::MB_TypeConstVars,
179       [](const SPIRV::DTSortableEntry *E) { return !E->getIsFunc(); });
180 
181   collectGlobalEntities(
182       DepsGraph, SPIRV::MB_ExtFuncDecls,
183       [](const SPIRV::DTSortableEntry *E) { return E->getIsFunc(); }, true);
184 }
185 
186 // True if there is an instruction in the MS list with all the same operands as
187 // the given instruction has (after the given starting index).
188 // TODO: maybe it needs to check Opcodes too.
189 static bool findSameInstrInMS(const MachineInstr &A,
190                               SPIRV::ModuleSectionType MSType,
191                               SPIRV::ModuleAnalysisInfo &MAI,
192                               unsigned StartOpIndex = 0) {
193   for (const auto *B : MAI.MS[MSType]) {
194     const unsigned NumAOps = A.getNumOperands();
195     if (NumAOps != B->getNumOperands() || A.getNumDefs() != B->getNumDefs())
196       continue;
197     bool AllOpsMatch = true;
198     for (unsigned i = StartOpIndex; i < NumAOps && AllOpsMatch; ++i) {
199       if (A.getOperand(i).isReg() && B->getOperand(i).isReg()) {
200         Register RegA = A.getOperand(i).getReg();
201         Register RegB = B->getOperand(i).getReg();
202         AllOpsMatch = MAI.getRegisterAlias(A.getMF(), RegA) ==
203                       MAI.getRegisterAlias(B->getMF(), RegB);
204       } else {
205         AllOpsMatch = A.getOperand(i).isIdenticalTo(B->getOperand(i));
206       }
207     }
208     if (AllOpsMatch)
209       return true;
210   }
211   return false;
212 }
213 
214 // Look for IDs declared with Import linkage, and map the imported name string
215 // to the register defining that variable (which will usually be the result of
216 // an OpFunction). This lets us call externally imported functions using
217 // the correct ID registers.
218 void SPIRVModuleAnalysis::collectFuncNames(MachineInstr &MI,
219                                            const Function &F) {
220   if (MI.getOpcode() == SPIRV::OpDecorate) {
221     // If it's got Import linkage.
222     auto Dec = MI.getOperand(1).getImm();
223     if (Dec == static_cast<unsigned>(SPIRV::Decoration::LinkageAttributes)) {
224       auto Lnk = MI.getOperand(MI.getNumOperands() - 1).getImm();
225       if (Lnk == static_cast<unsigned>(SPIRV::LinkageType::Import)) {
226         // Map imported function name to function ID register.
227         std::string Name = getStringImm(MI, 2);
228         Register Target = MI.getOperand(0).getReg();
229         // TODO: check defs from different MFs.
230         MAI.FuncNameMap[Name] = MAI.getRegisterAlias(MI.getMF(), Target);
231       }
232     }
233   } else if (MI.getOpcode() == SPIRV::OpFunction) {
234     // Record all internal OpFunction declarations.
235     Register Reg = MI.defs().begin()->getReg();
236     Register GlobalReg = MAI.getRegisterAlias(MI.getMF(), Reg);
237     assert(GlobalReg.isValid());
238     // TODO: check that it does not conflict with existing entries.
239     MAI.FuncNameMap[F.getGlobalIdentifier()] = GlobalReg;
240   }
241 }
242 
243 // Collect the given instruction in the specified MS. We assume global register
244 // numbering has already occurred by this point. We can directly compare reg
245 // arguments when detecting duplicates.
246 static void collectOtherInstr(MachineInstr &MI, SPIRV::ModuleAnalysisInfo &MAI,
247                               SPIRV::ModuleSectionType MSType,
248                               bool Append = true) {
249   MAI.setSkipEmission(&MI);
250   if (findSameInstrInMS(MI, MSType, MAI))
251     return; // Found a duplicate, so don't add it.
252   // No duplicates, so add it.
253   if (Append)
254     MAI.MS[MSType].push_back(&MI);
255   else
256     MAI.MS[MSType].insert(MAI.MS[MSType].begin(), &MI);
257 }
258 
259 // Some global instructions make reference to function-local ID regs, so cannot
260 // be correctly collected until these registers are globally numbered.
261 void SPIRVModuleAnalysis::processOtherInstrs(const Module &M) {
262   for (auto F = M.begin(), E = M.end(); F != E; ++F) {
263     if ((*F).isDeclaration())
264       continue;
265     MachineFunction *MF = MMI->getMachineFunction(*F);
266     assert(MF);
267     for (MachineBasicBlock &MBB : *MF)
268       for (MachineInstr &MI : MBB) {
269         if (MAI.getSkipEmission(&MI))
270           continue;
271         const unsigned OpCode = MI.getOpcode();
272         if (OpCode == SPIRV::OpName || OpCode == SPIRV::OpMemberName) {
273           collectOtherInstr(MI, MAI, SPIRV::MB_DebugNames);
274         } else if (OpCode == SPIRV::OpEntryPoint) {
275           collectOtherInstr(MI, MAI, SPIRV::MB_EntryPoints);
276         } else if (TII->isDecorationInstr(MI)) {
277           collectOtherInstr(MI, MAI, SPIRV::MB_Annotations);
278           collectFuncNames(MI, *F);
279         } else if (TII->isConstantInstr(MI)) {
280           // Now OpSpecConstant*s are not in DT,
281           // but they need to be collected anyway.
282           collectOtherInstr(MI, MAI, SPIRV::MB_TypeConstVars);
283         } else if (OpCode == SPIRV::OpFunction) {
284           collectFuncNames(MI, *F);
285         } else if (OpCode == SPIRV::OpTypeForwardPointer) {
286           collectOtherInstr(MI, MAI, SPIRV::MB_TypeConstVars, false);
287         }
288       }
289   }
290 }
291 
292 // Number registers in all functions globally from 0 onwards and store
293 // the result in global register alias table. Some registers are already
294 // numbered in collectGlobalEntities.
295 void SPIRVModuleAnalysis::numberRegistersGlobally(const Module &M) {
296   for (auto F = M.begin(), E = M.end(); F != E; ++F) {
297     if ((*F).isDeclaration())
298       continue;
299     MachineFunction *MF = MMI->getMachineFunction(*F);
300     assert(MF);
301     for (MachineBasicBlock &MBB : *MF) {
302       for (MachineInstr &MI : MBB) {
303         for (MachineOperand &Op : MI.operands()) {
304           if (!Op.isReg())
305             continue;
306           Register Reg = Op.getReg();
307           if (MAI.hasRegisterAlias(MF, Reg))
308             continue;
309           Register NewReg = Register::index2VirtReg(MAI.getNextID());
310           MAI.setRegisterAlias(MF, Reg, NewReg);
311         }
312         if (MI.getOpcode() != SPIRV::OpExtInst)
313           continue;
314         auto Set = MI.getOperand(2).getImm();
315         if (MAI.ExtInstSetMap.find(Set) == MAI.ExtInstSetMap.end())
316           MAI.ExtInstSetMap[Set] = Register::index2VirtReg(MAI.getNextID());
317       }
318     }
319   }
320 }
321 
322 // Find OpIEqual and OpBranchConditional instructions originating from
323 // OpSwitches, mark them skipped for emission. Also mark MBB skipped if it
324 // contains only these instructions.
325 static void processSwitches(const Module &M, SPIRV::ModuleAnalysisInfo &MAI,
326                             MachineModuleInfo *MMI) {
327   DenseSet<Register> SwitchRegs;
328   for (auto F = M.begin(), E = M.end(); F != E; ++F) {
329     MachineFunction *MF = MMI->getMachineFunction(*F);
330     if (!MF)
331       continue;
332     for (MachineBasicBlock &MBB : *MF)
333       for (MachineInstr &MI : MBB) {
334         if (MAI.getSkipEmission(&MI))
335           continue;
336         if (MI.getOpcode() == SPIRV::OpSwitch) {
337           assert(MI.getOperand(0).isReg());
338           SwitchRegs.insert(MI.getOperand(0).getReg());
339         }
340         if (MI.getOpcode() != SPIRV::OpIEqual || !MI.getOperand(2).isReg() ||
341             !SwitchRegs.contains(MI.getOperand(2).getReg()))
342           continue;
343         Register CmpReg = MI.getOperand(0).getReg();
344         MachineInstr *CBr = MI.getNextNode();
345         assert(CBr && CBr->getOpcode() == SPIRV::OpBranchConditional &&
346                CBr->getOperand(0).isReg() &&
347                CBr->getOperand(0).getReg() == CmpReg);
348         MAI.setSkipEmission(&MI);
349         MAI.setSkipEmission(CBr);
350         if (&MBB.front() == &MI && &MBB.back() == CBr)
351           MAI.MBBsToSkip.insert(&MBB);
352       }
353   }
354 }
355 
356 struct SPIRV::ModuleAnalysisInfo SPIRVModuleAnalysis::MAI;
357 
358 void SPIRVModuleAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
359   AU.addRequired<TargetPassConfig>();
360   AU.addRequired<MachineModuleInfoWrapperPass>();
361 }
362 
363 bool SPIRVModuleAnalysis::runOnModule(Module &M) {
364   SPIRVTargetMachine &TM =
365       getAnalysis<TargetPassConfig>().getTM<SPIRVTargetMachine>();
366   ST = TM.getSubtargetImpl();
367   GR = ST->getSPIRVGlobalRegistry();
368   TII = ST->getInstrInfo();
369 
370   MMI = &getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
371 
372   setBaseInfo(M);
373 
374   processSwitches(M, MAI, MMI);
375 
376   // Process type/const/global var/func decl instructions, number their
377   // destination registers from 0 to N, collect Extensions and Capabilities.
378   processDefInstrs(M);
379 
380   // Number rest of registers from N+1 onwards.
381   numberRegistersGlobally(M);
382 
383   // Collect OpName, OpEntryPoint, OpDecorate etc, process other instructions.
384   processOtherInstrs(M);
385 
386   return false;
387 }
388