Intel SPMD Program Compiler  1.11.0
sym.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2010-2013, Intel Corporation
3  All rights reserved.
4 
5  Redistribution and use in source and binary forms, with or without
6  modification, are permitted provided that the following conditions are
7  met:
8 
9  * Redistributions of source code must retain the above copyright
10  notice, this list of conditions and the following disclaimer.
11 
12  * Redistributions in binary form must reproduce the above copyright
13  notice, this list of conditions and the following disclaimer in the
14  documentation and/or other materials provided with the distribution.
15 
16  * Neither the name of Intel Corporation nor the names of its
17  contributors may be used to endorse or promote products derived from
18  this software without specific prior written permission.
19 
20 
21  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
22  IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
23  TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
24  PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
25  OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33 
34 /** @file sym.h
35 
36  @brief header file with declarations for symbol and symbol table
37  classes.
38 */
39 
40 #ifndef ISPC_SYM_H
41 #define ISPC_SYM_H
42 
43 #include "decl.h"
44 #include "ispc.h"
45 #include <map>
46 
47 class StructType;
48 class ConstExpr;
49 
50 /**
51  @brief Representation of a program symbol.
52 
53  The Symbol class represents a symbol in an ispc program. Symbols can
54  include variables, functions, and named types. Note that all of the
55  members are publically accessible; other code throughout the system
56  accesses and modifies the members directly.
57 
58  @todo Should we break function symbols into a separate FunctionSymbol
59  class and then not have these members that are not applicable for
60  function symbols (and vice versa, for non-function symbols)?
61  */
62 
63 class Symbol {
64  public:
65  /** The Symbol constructor takes the name of the symbol, its
66  position in a source file, and its type (if known). */
67  Symbol(const std::string &name, SourcePos pos, const Type *t = NULL, StorageClass sc = SC_NONE);
68 
69  SourcePos pos; /*!< Source file position where the symbol was defined */
70  std::string name; /*!< Symbol's name */
71  llvm::Value *storagePtr; /*!< For symbols with storage associated with
72  them (i.e. variables but not functions),
73  this member stores a pointer to its
74  location in memory.) */
75  llvm::Function *function; /*!< For symbols that represent functions,
76  this stores the LLVM Function value for
77  the symbol once it has been created. */
78  llvm::Function *exportedFunction;
79  /*!< For symbols that represent functions with
80  'export' qualifiers, this points to the LLVM
81  Function for the application-callable version
82  of the function. */
83  const Type *type; /*!< The type of the symbol; if not set by the
84  constructor, this is set after the
85  declaration around the symbol has been parsed. */
86  ConstExpr *constValue; /*!< For symbols with const-qualified types, this may store
87  the symbol's compile-time constant value. This value may
88  validly be NULL for a const-qualified type, however; for
89  example, the ConstExpr class can't currently represent
90  struct types. For cases like these, ConstExpr is NULL,
91  though for all const symbols, the value pointed to by the
92  storagePtr member will be its constant value. (This
93  messiness is due to needing an ispc ConstExpr for the early
94  constant folding optimizations). */
95  StorageClass storageClass; /*!< Records the storage class (if any) provided with the
96  symbol's declaration. */
97  int varyingCFDepth; /*!< This member records the number of levels of nested 'varying'
98  control flow within which the symbol was declared. Having
99  this value available makes it possible to avoid performing
100  masked stores when modifying the symbol's value when the
101  store is done at the same 'varying' control flow depth as
102  the one where the symbol was originally declared. */
104  /*!< For symbols that are parameters to functions or are
105  variables declared inside functions, this gives the
106  function they're in. */
107 };
108 
109 /** @brief Symbol table that holds all known symbols during parsing and compilation.
110 
111  A single instance of a SymbolTable is stored in the Module class
112  (Module::symbolTable); it is created in the Module::Module()
113  constructor. It is then accessed via the global variable Module *\ref m
114  throughout the ispc implementation.
115  */
116 
117 class SymbolTable {
118  public:
119  SymbolTable();
120  ~SymbolTable();
121 
122  /** The parser calls this method when it enters a new scope in the
123  program; this allows us to track variables that shadows others in
124  outer scopes with same name as well as to efficiently discard all
125  of the variables declared in a particular scope when we exit that
126  scope. */
127  void PushScope();
128 
129  /** For each scope started by a call to SymbolTable::PushScope(), there
130  must be a matching call to SymbolTable::PopScope() at the end of
131  that scope. */
132  void PopScope();
133 
134  /** Adds the given variable symbol to the symbol table.
135  @param symbol The symbol to be added
136 
137  @return true if successful; false if the provided symbol clashes
138  with a symbol defined at the same scope. (Symbols may shaodow
139  symbols in outer scopes; a warning is issued in this case, but this
140  method still returns true.) */
141  bool AddVariable(Symbol *symbol);
142 
143  /** Looks for a variable with the given name in the symbol table. This
144  method searches outward from the innermost scope to the outermost,
145  returning the first match found.
146 
147  @param name The name of the variable to be searched for.
148  @return A pointer to the Symbol, if a match is found. NULL if no
149  Symbol with the given name is in the symbol table. */
150  Symbol *LookupVariable(const char *name);
151 
152  /** Adds the given function symbol to the symbol table.
153  @param symbol The function symbol to be added.
154 
155  @return true if the symbol has been added. False if another
156  function symbol with the same name and function signature is
157  already present in the symbol table. */
158  bool AddFunction(Symbol *symbol);
159 
160  /** Looks for the function or functions with the given name in the
161  symbol name. If a function has been overloaded and multiple
162  definitions are present for a given function name, all of them will
163  be returned in the provided vector and it's up the the caller to
164  resolve which one (if any) to use. Returns true if any matches
165  were found. */
166  bool LookupFunction(const char *name, std::vector<Symbol *> *matches = NULL);
167 
168  /** Looks for a function with the given name and type
169  in the symbol table.
170 
171  @return pointer to matching Symbol; NULL if none is found. */
172  Symbol *LookupFunction(const char *name, const FunctionType *type);
173 
174  /** Returns all of the functions in the symbol table that match the given
175  predicate.
176 
177  @param pred A unary predicate that returns true or false, given a Symbol
178  pointer, based on whether the symbol should be included in the returned
179  set of matches. It can either be a function, with signature
180  <tt>bool pred(const Symbol *s)</tt>, or a unary predicate object with
181  an <tt>bool operator()(const Symbol *)</tt> method.
182 
183  @param matches Pointer to a vector in which to return the matching
184  symbols.
185  */
186  template <typename Predicate> void GetMatchingFunctions(Predicate pred, std::vector<Symbol *> *matches) const;
187 
188  /** Returns all of the variable symbols in the symbol table that match
189  the given predicate. The predicate is defined as in the
190  GetMatchingFunctions() method.
191  */
192  template <typename Predicate> void GetMatchingVariables(Predicate pred, std::vector<Symbol *> *matches) const;
193 
194  /** Adds the named type to the symbol table. This is used for both
195  struct definitions (where <tt>struct Foo</tt> causes type \c Foo to
196  be added to the symbol table) as well as for <tt>typedef</tt>s.
197  For structs with forward declarations ("struct Foo;") and are thus
198  UndefinedStructTypes, this method replaces these with an actual
199  struct definition if one is provided.
200 
201  @param name Name of the type to be added
202  @param type Type that \c name represents
203  @param pos Position in source file where the type was named
204  @return true if the named type was successfully added. False if a type
205  with the same name has already been defined.
206 
207  */
208  bool AddType(const char *name, const Type *type, SourcePos pos);
209 
210  /** Looks for a type of the given name in the symbol table.
211 
212  @return Pointer to the Type, if found; otherwise NULL is returned.
213  */
214  const Type *LookupType(const char *name) const;
215 
216  /** Look for a type given a pointer.
217 
218  @return True if found, False otherwise.
219  */
220  bool ContainsType(const Type *type) const;
221 
222  /** This method returns zero or more strings with the names of symbols
223  in the symbol table that nearly (but not exactly) match the given
224  name. This is useful for issuing informative error methods when
225  misspelled identifiers are found a programs.
226 
227  @param name String to compare variable and function symbol names against.
228  @return vector of zero or more strings that approximately match \c name.
229  */
230  std::vector<std::string> ClosestVariableOrFunctionMatch(const char *name) const;
231  /** This method returns zero or more strings with the names of types
232  in the symbol table that nearly (but not exactly) match the given
233  name. */
234  std::vector<std::string> ClosestTypeMatch(const char *name) const;
235 
236  std::vector<std::string> ClosestEnumTypeMatch(const char *name) const;
237 
238  /** Prints out the entire contents of the symbol table to standard error.
239  (Debugging method). */
240  void Print();
241 
242  /** Returns a random symbol from the symbol table. (It is not
243  guaranteed that it is equally likely to return all symbols). */
244  Symbol *RandomSymbol();
245 
246  /** Returns a random type from the symbol table. */
247  const Type *RandomType();
248 
249  private:
250  std::vector<std::string> closestTypeMatch(const char *str, bool structsVsEnums) const;
251 
252  /** This member variable holds one SymbolMap for each of the current
253  active scopes as the program is being parsed. New maps are added
254  and removed from the end of the main vector, so searches for
255  symbols start looking at the end of \c variables and work
256  backwards.
257  */
258  typedef std::map<std::string, Symbol *> SymbolMapType;
259  std::vector<SymbolMapType *> variables;
260 
261  std::vector<SymbolMapType *> freeSymbolMaps;
262 
263  /** Function declarations are *not* scoped. (C99, for example, allows
264  an implementation to maintain function declarations in a single
265  namespace.) A STL \c vector is used to store the function symbols
266  for a given name since, due to function overloading, a name can
267  have multiple function symbols associated with it. */
268  typedef std::map<std::string, std::vector<Symbol *>> FunctionMapType;
270 
271  /** Type definitions can't currently be scoped.
272  */
273  typedef std::map<std::string, const Type *> TypeMapType;
275 };
276 
277 template <typename Predicate>
278 void SymbolTable::GetMatchingFunctions(Predicate pred, std::vector<Symbol *> *matches) const {
279  // Iterate through all function symbols and apply the given predicate.
280  // If it returns true, add the Symbol * to the provided vector.
281  FunctionMapType::const_iterator iter;
282  for (iter = functions.begin(); iter != functions.end(); ++iter) {
283  const std::vector<Symbol *> &syms = iter->second;
284  for (unsigned int j = 0; j < syms.size(); ++j) {
285  if (pred(syms[j]))
286  matches->push_back(syms[j]);
287  }
288  }
289 }
290 
291 template <typename Predicate>
292 void SymbolTable::GetMatchingVariables(Predicate pred, std::vector<Symbol *> *matches) const {
293  for (unsigned int i = 0; i < variables.size(); ++i) {
294  SymbolMapType &sm = *(variables[i]);
295  SymbolMapType::const_iterator iter;
296  for (iter = sm.begin(); iter != sm.end(); ++iter) {
297  if (pred(iter->second))
298  matches->push_back(iter->second);
299  }
300  }
301 }
302 
303 #endif // ISPC_SYM_H
llvm::Value * storagePtr
Definition: sym.h:71
Definition: func.h:44
void Print()
Definition: sym.cpp:272
std::map< std::string, const Type * > TypeMapType
Definition: sym.h:273
bool AddFunction(Symbol *symbol)
Definition: sym.cpp:126
void PushScope()
Definition: sym.cpp:67
const Type * LookupType(const char *name) const
Definition: sym.cpp:180
bool ContainsType(const Type *type) const
Definition: sym.cpp:188
bool AddVariable(Symbol *symbol)
Definition: sym.cpp:85
Expression representing a compile-time constant value.
Definition: expr.h:362
Symbol table that holds all known symbols during parsing and compilation.
Definition: sym.h:117
FunctionMapType functions
Definition: sym.h:269
std::vector< std::string > ClosestEnumTypeMatch(const char *name) const
Definition: sym.cpp:238
std::string name
Definition: sym.h:70
Symbol * LookupVariable(const char *name)
Definition: sym.cpp:112
~SymbolTable()
Definition: sym.cpp:61
ConstExpr * constValue
Definition: sym.h:86
TypeMapType types
Definition: sym.h:274
std::vector< SymbolMapType * > freeSymbolMaps
Definition: sym.h:261
std::vector< std::string > closestTypeMatch(const char *str, bool structsVsEnums) const
Definition: sym.cpp:242
Symbol(const std::string &name, SourcePos pos, const Type *t=NULL, StorageClass sc=SC_NONE)
Definition: sym.cpp:46
void GetMatchingVariables(Predicate pred, std::vector< Symbol *> *matches) const
Definition: sym.h:292
bool AddType(const char *name, const Type *type, SourcePos pos)
Definition: sym.cpp:165
bool LookupFunction(const char *name, std::vector< Symbol *> *matches=NULL)
Definition: sym.cpp:139
std::map< std::string, std::vector< Symbol * > > FunctionMapType
Definition: sym.h:268
std::vector< SymbolMapType * > variables
Definition: sym.h:259
Representation of a structure holding a number of members.
Definition: type.h:670
const Type * RandomType()
Definition: sym.cpp:328
SourcePos pos
Definition: sym.h:69
StorageClass storageClass
Definition: sym.h:95
Representation of a range of positions in a source file.
Definition: ispc.h:129
Declarations related to type declarations; the parser basically creates instances of these classes...
StorageClass
Definition: ispc.h:120
std::vector< std::string > ClosestTypeMatch(const char *name) const
Definition: sym.cpp:236
SymbolTable()
Definition: sym.cpp:59
Definition: ispc.h:120
std::map< std::string, Symbol * > SymbolMapType
Definition: sym.h:258
Type representing a function (return type + argument types)
Definition: type.h:858
Representation of a program symbol.
Definition: sym.h:63
int varyingCFDepth
Definition: sym.h:97
Interface class that defines the type abstraction.
Definition: type.h:95
void GetMatchingFunctions(Predicate pred, std::vector< Symbol *> *matches) const
Definition: sym.h:278
const Function * parentFunction
Definition: sym.h:103
void PopScope()
Definition: sym.cpp:79
Symbol * RandomSymbol()
Definition: sym.cpp:315
const Type * type
Definition: sym.h:83
Main ispc.header file. Defines Target, Globals and Opt classes.
llvm::Function * exportedFunction
Definition: sym.h:78
std::vector< std::string > ClosestVariableOrFunctionMatch(const char *name) const
Definition: sym.cpp:199