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 set contains machine basic blocks which are necessary
140   // for correct MIR but will not be emitted.
141   DenseSet<MachineBasicBlock *> MBBsToSkip;
142   // The table contains global aliases of local registers for each machine
143   // function. The aliases are used to substitute local registers during
144   // code emission.
145   RegisterAliasMapTy RegisterAliasTable;
146   // The counter holds the maximum ID we have in the module.
147   unsigned MaxID;
148   // The array contains lists of MIs for each module section.
149   InstrList MS[NUM_MODULE_SECTIONS];
150   // The table maps MBB number to SPIR-V unique ID register.
151   DenseMap<int, Register> BBNumToRegMap;
152 
153   Register getFuncReg(const Function *F) {
154     assert(F && "Function is null");
155     auto FuncPtrRegPair = FuncMap.find(F);
156     assert(FuncPtrRegPair != FuncMap.end() && "Cannot find function ID");
157     return FuncPtrRegPair->second;
158   }
159   Register getExtInstSetReg(unsigned SetNum) { return ExtInstSetMap[SetNum]; }
160   InstrList &getMSInstrs(unsigned MSType) { return MS[MSType]; }
161   void setSkipEmission(MachineInstr *MI) { InstrsToDelete.insert(MI); }
162   bool getSkipEmission(const MachineInstr *MI) {
163     return InstrsToDelete.contains(MI);
164   }
165   void setRegisterAlias(const MachineFunction *MF, Register Reg,
166                         Register AliasReg) {
167     RegisterAliasTable[MF][Reg] = AliasReg;
168   }
169   Register getRegisterAlias(const MachineFunction *MF, Register Reg) {
170     auto RI = RegisterAliasTable[MF].find(Reg);
171     if (RI == RegisterAliasTable[MF].end()) {
172       return Register(0);
173     }
174     return RegisterAliasTable[MF][Reg];
175   }
176   bool hasRegisterAlias(const MachineFunction *MF, Register Reg) {
177     return RegisterAliasTable.find(MF) != RegisterAliasTable.end() &&
178            RegisterAliasTable[MF].find(Reg) != RegisterAliasTable[MF].end();
179   }
180   unsigned getNextID() { return MaxID++; }
181   bool hasMBBRegister(const MachineBasicBlock &MBB) {
182     return BBNumToRegMap.find(MBB.getNumber()) != BBNumToRegMap.end();
183   }
184   // Convert MBB's number to corresponding ID register.
185   Register getOrCreateMBBRegister(const MachineBasicBlock &MBB) {
186     auto f = BBNumToRegMap.find(MBB.getNumber());
187     if (f != BBNumToRegMap.end())
188       return f->second;
189     Register NewReg = Register::index2VirtReg(getNextID());
190     BBNumToRegMap[MBB.getNumber()] = NewReg;
191     return NewReg;
192   }
193 };
194 } // namespace SPIRV
195 
196 struct SPIRVModuleAnalysis : public ModulePass {
197   static char ID;
198 
199 public:
200   SPIRVModuleAnalysis() : ModulePass(ID) {}
201 
202   bool runOnModule(Module &M) override;
203   void getAnalysisUsage(AnalysisUsage &AU) const override;
204   static struct SPIRV::ModuleAnalysisInfo MAI;
205 
206 private:
207   void setBaseInfo(const Module &M);
208   void collectGlobalEntities(
209       const std::vector<SPIRV::DTSortableEntry *> &DepsGraph,
210       SPIRV::ModuleSectionType MSType,
211       std::function<bool(const SPIRV::DTSortableEntry *)> Pred,
212       bool UsePreOrder);
213   void processDefInstrs(const Module &M);
214   void collectFuncNames(MachineInstr &MI, const Function *F);
215   void processOtherInstrs(const Module &M);
216   void numberRegistersGlobally(const Module &M);
217 
218   const SPIRVSubtarget *ST;
219   SPIRVGlobalRegistry *GR;
220   const SPIRVInstrInfo *TII;
221   MachineModuleInfo *MMI;
222 };
223 } // namespace llvm
224 #endif // LLVM_LIB_TARGET_SPIRV_SPIRVMODULEANALYSIS_H
225