1 //===- SPIRVModuleAnalysis.h - 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 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_LIB_TARGET_SPIRV_SPIRVMODULEANALYSIS_H
15 #define LLVM_LIB_TARGET_SPIRV_SPIRVMODULEANALYSIS_H
16 
17 #include "MCTargetDesc/SPIRVBaseInfo.h"
18 #include "SPIRVGlobalRegistry.h"
19 #include "SPIRVUtils.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/SmallSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/StringMap.h"
24 
25 namespace llvm {
26 class SPIRVSubtarget;
27 class MachineFunction;
28 class MachineModuleInfo;
29 
30 namespace SPIRV {
31 // The enum contains logical module sections for the instruction collection.
32 enum ModuleSectionType {
33   //  MB_Capabilities, MB_Extensions, MB_ExtInstImports, MB_MemoryModel,
34   MB_EntryPoints, // All OpEntryPoint instructions (if any).
35   //  MB_ExecutionModes, MB_DebugSourceAndStrings,
36   MB_DebugNames,           // All OpName and OpMemberName intrs.
37   MB_DebugModuleProcessed, // All OpModuleProcessed instructions.
38   MB_Annotations,          // OpDecorate, OpMemberDecorate etc.
39   MB_TypeConstVars,        // OpTypeXXX, OpConstantXXX, and global OpVariables.
40   MB_ExtFuncDecls,         // OpFunction etc. to declare for external funcs.
41   NUM_MODULE_SECTIONS      // Total number of sections requiring basic blocks.
42 };
43 
44 struct Requirements {
45   const bool IsSatisfiable;
46   const std::optional<Capability::Capability> Cap;
47   const ExtensionList Exts;
48   const unsigned MinVer; // 0 if no min version is required.
49   const unsigned MaxVer; // 0 if no max version is required.
50 
51   Requirements(bool IsSatisfiable = false,
52                std::optional<Capability::Capability> Cap = {},
53                ExtensionList Exts = {}, unsigned MinVer = 0,
54                unsigned MaxVer = 0)
55       : IsSatisfiable(IsSatisfiable), Cap(Cap), Exts(Exts), MinVer(MinVer),
56         MaxVer(MaxVer) {}
57   Requirements(Capability::Capability Cap) : Requirements(true, {Cap}) {}
58 };
59 
60 struct RequirementHandler {
61 private:
62   CapabilityList MinimalCaps;
63   SmallSet<Capability::Capability, 8> AllCaps;
64   SmallSet<Extension::Extension, 4> AllExtensions;
65   unsigned MinVersion; // 0 if no min version is defined.
66   unsigned MaxVersion; // 0 if no max version is defined.
67   DenseSet<unsigned> AvailableCaps;
68   // Remove a list of capabilities from dedupedCaps and add them to AllCaps,
69   // recursing through their implicitly declared capabilities too.
70   void pruneCapabilities(const CapabilityList &ToPrune);
71 
72 public:
73   RequirementHandler() : MinVersion(0), MaxVersion(0) {}
74   void clear() {
75     MinimalCaps.clear();
76     AllCaps.clear();
77     AvailableCaps.clear();
78     AllExtensions.clear();
79     MinVersion = 0;
80     MaxVersion = 0;
81   }
82   unsigned getMinVersion() const { return MinVersion; }
83   unsigned getMaxVersion() const { return MaxVersion; }
84   const CapabilityList &getMinimalCapabilities() const { return MinimalCaps; }
85   const SmallSet<Extension::Extension, 4> &getExtensions() const {
86     return AllExtensions;
87   }
88   // Add a list of capabilities, ensuring AllCaps captures all the implicitly
89   // declared capabilities, and MinimalCaps has the minimal set of required
90   // capabilities (so all implicitly declared ones are removed).
91   void addCapabilities(const CapabilityList &ToAdd);
92   void addCapability(Capability::Capability ToAdd) { addCapabilities({ToAdd}); }
93   void addExtensions(const ExtensionList &ToAdd) {
94     AllExtensions.insert(ToAdd.begin(), ToAdd.end());
95   }
96   void addExtension(Extension::Extension ToAdd) { AllExtensions.insert(ToAdd); }
97   // Add the given requirements to the lists. If constraints conflict, or these
98   // requirements cannot be satisfied, then abort the compilation.
99   void addRequirements(const Requirements &Req);
100   // Get requirement and add it to the list.
101   void getAndAddRequirements(SPIRV::OperandCategory::OperandCategory Category,
102                              uint32_t i, const SPIRVSubtarget &ST);
103   // Check if all the requirements can be satisfied for the given subtarget, and
104   // if not abort compilation.
105   void checkSatisfiable(const SPIRVSubtarget &ST) const;
106   void initAvailableCapabilities(const SPIRVSubtarget &ST);
107   // Add the given capabilities to available and all their implicitly defined
108   // capabilities too.
109   void addAvailableCaps(const CapabilityList &ToAdd);
110   bool isCapabilityAvailable(Capability::Capability Cap) const {
111     return AvailableCaps.contains(Cap);
112   }
113 };
114 
115 using InstrList = SmallVector<MachineInstr *>;
116 // Maps a local register to the corresponding global alias.
117 using LocalToGlobalRegTable = std::map<Register, Register>;
118 using RegisterAliasMapTy =
119     std::map<const MachineFunction *, LocalToGlobalRegTable>;
120 
121 // The struct contains results of the module analysis and methods
122 // to access them.
123 struct ModuleAnalysisInfo {
124   RequirementHandler Reqs;
125   MemoryModel::MemoryModel Mem;
126   AddressingModel::AddressingModel Addr;
127   SourceLanguage::SourceLanguage SrcLang;
128   unsigned SrcLangVersion;
129   StringSet<> SrcExt;
130   // Maps ExtInstSet to corresponding ID register.
131   DenseMap<unsigned, Register> ExtInstSetMap;
132   // Contains the list of all global OpVariables in the module.
133   SmallVector<MachineInstr *, 4> GlobalVarList;
134   // Maps functions to corresponding function ID registers.
135   DenseMap<const Function *, Register> FuncMap;
136   // The set contains machine instructions which are necessary
137   // for correct MIR but will not be emitted in function bodies.
138   DenseSet<MachineInstr *> InstrsToDelete;
139   // The table contains global aliases of local registers for each machine
140   // function. The aliases are used to substitute local registers during
141   // code emission.
142   RegisterAliasMapTy RegisterAliasTable;
143   // The counter holds the maximum ID we have in the module.
144   unsigned MaxID;
145   // The array contains lists of MIs for each module section.
146   InstrList MS[NUM_MODULE_SECTIONS];
147   // The table maps MBB number to SPIR-V unique ID register.
148   DenseMap<int, Register> BBNumToRegMap;
149 
150   Register getFuncReg(const Function *F) {
151     assert(F && "Function is null");
152     auto FuncPtrRegPair = FuncMap.find(F);
153     assert(FuncPtrRegPair != FuncMap.end() && "Cannot find function ID");
154     return FuncPtrRegPair->second;
155   }
156   Register getExtInstSetReg(unsigned SetNum) { return ExtInstSetMap[SetNum]; }
157   InstrList &getMSInstrs(unsigned MSType) { return MS[MSType]; }
158   void setSkipEmission(MachineInstr *MI) { InstrsToDelete.insert(MI); }
159   bool getSkipEmission(const MachineInstr *MI) {
160     return InstrsToDelete.contains(MI);
161   }
162   void setRegisterAlias(const MachineFunction *MF, Register Reg,
163                         Register AliasReg) {
164     RegisterAliasTable[MF][Reg] = AliasReg;
165   }
166   Register getRegisterAlias(const MachineFunction *MF, Register Reg) {
167     auto RI = RegisterAliasTable[MF].find(Reg);
168     if (RI == RegisterAliasTable[MF].end()) {
169       return Register(0);
170     }
171     return RegisterAliasTable[MF][Reg];
172   }
173   bool hasRegisterAlias(const MachineFunction *MF, Register Reg) {
174     return RegisterAliasTable.find(MF) != RegisterAliasTable.end() &&
175            RegisterAliasTable[MF].find(Reg) != RegisterAliasTable[MF].end();
176   }
177   unsigned getNextID() { return MaxID++; }
178   bool hasMBBRegister(const MachineBasicBlock &MBB) {
179     return BBNumToRegMap.find(MBB.getNumber()) != BBNumToRegMap.end();
180   }
181   // Convert MBB's number to corresponding ID register.
182   Register getOrCreateMBBRegister(const MachineBasicBlock &MBB) {
183     auto f = BBNumToRegMap.find(MBB.getNumber());
184     if (f != BBNumToRegMap.end())
185       return f->second;
186     Register NewReg = Register::index2VirtReg(getNextID());
187     BBNumToRegMap[MBB.getNumber()] = NewReg;
188     return NewReg;
189   }
190 };
191 } // namespace SPIRV
192 
193 struct SPIRVModuleAnalysis : public ModulePass {
194   static char ID;
195 
196 public:
197   SPIRVModuleAnalysis() : ModulePass(ID) {}
198 
199   bool runOnModule(Module &M) override;
200   void getAnalysisUsage(AnalysisUsage &AU) const override;
201   static struct SPIRV::ModuleAnalysisInfo MAI;
202 
203 private:
204   void setBaseInfo(const Module &M);
205   void collectGlobalEntities(
206       const std::vector<SPIRV::DTSortableEntry *> &DepsGraph,
207       SPIRV::ModuleSectionType MSType,
208       std::function<bool(const SPIRV::DTSortableEntry *)> Pred,
209       bool UsePreOrder);
210   void processDefInstrs(const Module &M);
211   void collectFuncNames(MachineInstr &MI, const Function *F);
212   void processOtherInstrs(const Module &M);
213   void numberRegistersGlobally(const Module &M);
214 
215   const SPIRVSubtarget *ST;
216   SPIRVGlobalRegistry *GR;
217   const SPIRVInstrInfo *TII;
218   MachineModuleInfo *MMI;
219 };
220 } // namespace llvm
221 #endif // LLVM_LIB_TARGET_SPIRV_SPIRVMODULEANALYSIS_H
222