1// Copyright (c) 2015-2016 The Khronos Group Inc.
2//
3// Permission is hereby granted, free of charge, to any person obtaining a
4// copy of this software and/or associated documentation files (the
5// "Materials"), to deal in the Materials without restriction, including
6// without limitation the rights to use, copy, modify, merge, publish,
7// distribute, sublicense, and/or sell copies of the Materials, and to
8// permit persons to whom the Materials are furnished to do so, subject to
9// the following conditions:
10//
11// The above copyright notice and this permission notice shall be included
12// in all copies or substantial portions of the Materials.
13//
14// MODIFICATIONS TO THIS FILE MAY MEAN IT NO LONGER ACCURATELY REFLECTS
15// KHRONOS STANDARDS. THE UNMODIFIED, NORMATIVE VERSIONS OF KHRONOS
16// SPECIFICATIONS AND HEADER INFORMATION ARE LOCATED AT
17//    https://www.khronos.org/registry/
18//
19// THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
22// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
23// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
24// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
25// MATERIALS OR THE USE OR OTHER DEALINGS IN THE MATERIALS.
26
27#ifndef LIBSPIRV_VAL_VALIDATIONSTATE_H_
28#define LIBSPIRV_VAL_VALIDATIONSTATE_H_
29
30#include <list>
31#include <map>
32#include <string>
33#include <unordered_map>
34#include <unordered_set>
35#include <vector>
36
37#include "assembly_grammar.h"
38#include "diagnostic.h"
39#include "spirv-tools/libspirv.h"
40#include "spirv/1.1/spirv.h"
41#include "spirv_definition.h"
42
43namespace libspirv {
44
45// Universal Limit of ResultID + 1
46static const uint32_t kInvalidId = 0x400000;
47
48// Info about a result ID.
49typedef struct spv_id_info_t {
50  /// Id value.
51  uint32_t id;
52  /// Type id, or 0 if no type.
53  uint32_t type_id;
54  /// Opcode of the instruction defining the id.
55  SpvOp opcode;
56  /// Binary words of the instruction defining the id.
57  std::vector<uint32_t> words;
58} spv_id_info_t;
59
60/// This enum represents the sections of a SPIRV module. See section 2.4
61/// of the SPIRV spec for additional details of the order. The enumerant values
62/// are in the same order as the vector returned by GetModuleOrder
63enum ModuleLayoutSection {
64  kLayoutCapabilities,          /// < Section 2.4 #1
65  kLayoutExtensions,            /// < Section 2.4 #2
66  kLayoutExtInstImport,         /// < Section 2.4 #3
67  kLayoutMemoryModel,           /// < Section 2.4 #4
68  kLayoutEntryPoint,            /// < Section 2.4 #5
69  kLayoutExecutionMode,         /// < Section 2.4 #6
70  kLayoutDebug1,                /// < Section 2.4 #7 > 1
71  kLayoutDebug2,                /// < Section 2.4 #7 > 2
72  kLayoutAnnotations,           /// < Section 2.4 #8
73  kLayoutTypes,                 /// < Section 2.4 #9
74  kLayoutFunctionDeclarations,  /// < Section 2.4 #10
75  kLayoutFunctionDefinitions    /// < Section 2.4 #11
76};
77
78class Function;
79
80/// This class manages the state of the SPIR-V validation as it is being parsed.
81class ValidationState_t {
82 public:
83  ValidationState_t(spv_diagnostic* diagnostic,
84                    const spv_const_context context);
85
86  /// Forward declares the id in the module
87  spv_result_t ForwardDeclareId(uint32_t id);
88
89  /// Removes a forward declared ID if it has been defined
90  spv_result_t RemoveIfForwardDeclared(uint32_t id);
91
92  /// Assigns a name to an ID
93  void AssignNameToId(uint32_t id, std::string name);
94
95  /// Returns a string representation of the ID in the format <id>[Name] where
96  /// the <id> is the numeric valid of the id and the Name is a name assigned by
97  /// the OpName instruction
98  std::string getIdName(uint32_t id) const;
99
100  /// Like getIdName but does not display the id if the \p id has a name
101  std::string getIdOrName(uint32_t id) const;
102
103  /// Returns the number of ID which have been forward referenced but not
104  /// defined
105  size_t unresolved_forward_id_count() const;
106
107  /// Returns a list of unresolved forward ids.
108  std::vector<uint32_t> UnresolvedForwardIds() const;
109
110  /// Returns true if the id has been defined
111  bool IsDefinedId(uint32_t id) const;
112
113  /// Increments the instruction count. Used for diagnostic
114  int increment_instruction_count();
115
116  /// Returns the current layout section which is being processed
117  ModuleLayoutSection current_layout_section() const;
118
119  /// Increments the module_layout_order_section_
120  void ProgressToNextLayoutSectionOrder();
121
122  /// Determines if the op instruction is part of the current section
123  bool IsOpcodeInCurrentLayoutSection(SpvOp op);
124
125  libspirv::DiagnosticStream diag(spv_result_t error_code) const;
126
127  /// Returns the function states
128  std::list<Function>& functions();
129
130  /// Returns the function states
131  Function& current_function();
132
133  /// Returns true if the called after a function instruction but before the
134  /// function end instruction
135  bool in_function_body() const;
136
137  /// Returns true if called after a label instruction but before a branch
138  /// instruction
139  bool in_block() const;
140
141  /// Keeps track of ID definitions and uses.
142  class UseDefTracker {
143   public:
144    void AddDef(const spv_id_info_t& def) { defs_[def.id] = def; }
145
146    void AddUse(uint32_t id) { uses_.insert(id); }
147
148    /// Finds id's def, if it exists.  If found, returns <true, def>. Otherwise,
149    /// returns <false, something>.
150    std::pair<bool, spv_id_info_t> FindDef(uint32_t id) const {
151      if (defs_.count(id) == 0) {
152        return std::make_pair(false, spv_id_info_t{});
153      } else {
154        /// We are in a const function, so we cannot use defs.operator[]().
155        /// Luckily we know the key exists, so defs_.at() won't throw an
156        /// exception.
157        return std::make_pair(true, defs_.at(id));
158      }
159    }
160
161    /// Returns uses of IDs lacking defs.
162    std::unordered_set<uint32_t> FindUsesWithoutDefs() const {
163      auto diff = uses_;
164      for (const auto d : defs_) diff.erase(d.first);
165      return diff;
166    }
167
168   private:
169    std::unordered_set<uint32_t> uses_;
170    std::unordered_map<uint32_t, spv_id_info_t> defs_;
171  };
172
173  UseDefTracker& usedefs() { return usedefs_; }
174  const UseDefTracker& usedefs() const { return usedefs_; }
175
176  /// Returns a list of entry point function ids
177  std::vector<uint32_t>& entry_points() { return entry_points_; }
178  const std::vector<uint32_t>& entry_points() const { return entry_points_; }
179
180  /// Registers the capability and its dependent capabilities
181  void RegisterCapability(SpvCapability cap);
182
183  /// Registers the function in the module. Subsequent instructions will be
184  /// called against this function
185  spv_result_t RegisterFunction(uint32_t id, uint32_t ret_type_id,
186                                SpvFunctionControlMask function_control,
187                                uint32_t function_type_id);
188
189  /// Register a function end instruction
190  spv_result_t RegisterFunctionEnd();
191
192  /// Returns true if the capability is enabled in the module.
193  bool has_capability(SpvCapability cap) const;
194
195  /// Returns true if any of the capabilities are enabled.  Always true for
196  /// capabilities==0.
197  bool HasAnyOf(spv_capability_mask_t capabilities) const;
198
199  /// Sets the addressing model of this module (logical/physical).
200  void set_addressing_model(SpvAddressingModel am);
201
202  /// Returns the addressing model of this module, or Logical if uninitialized.
203  SpvAddressingModel addressing_model() const;
204
205  /// Sets the memory model of this module.
206  void set_memory_model(SpvMemoryModel mm);
207
208  /// Returns the memory model of this module, or Simple if uninitialized.
209  SpvMemoryModel memory_model() const;
210
211  AssemblyGrammar& grammar() { return grammar_; }
212
213 private:
214  spv_diagnostic* diagnostic_;
215  /// Tracks the number of instructions evaluated by the validator
216  int instruction_counter_;
217
218  /// IDs which have been forward declared but have not been defined
219  std::unordered_set<uint32_t> unresolved_forward_ids_;
220
221  /// A map of operand IDs and their names defined by the OpName instruction
222  std::map<uint32_t, std::string> operand_names_;
223
224  /// The section of the code being processed
225  ModuleLayoutSection current_layout_section_;
226
227  /// A list of functions in the module
228  std::list<Function> module_functions_;
229
230  /// Mask of the capabilities available in the module
231  spv_capability_mask_t
232      module_capabilities_;  /// Module's declared capabilities.
233
234  /// Definitions and uses of all the IDs in the module.
235  UseDefTracker usedefs_;
236
237  /// IDs that are entry points, ie, arguments to OpEntryPoint.
238  std::vector<uint32_t> entry_points_;
239
240  AssemblyGrammar grammar_;
241
242  SpvAddressingModel addressing_model_;
243  SpvMemoryModel memory_model_;
244
245  /// NOTE: See correspoding getter functions
246  bool in_function_;
247};
248
249}  /// namespace libspirv
250
251#endif  /// LIBSPIRV_VAL_VALIDATIONSTATE_H_
252