Intel SPMD Program Compiler  1.9.1
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 "ispc.h"
44 #include "decl.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,
68  StorageClass sc = SC_NONE);
69 
70  SourcePos pos; /*!< Source file position where the symbol was defined */
71  std::string name; /*!< Symbol's name */
72  llvm::Value *storagePtr; /*!< For symbols with storage associated with
73  them (i.e. variables but not functions),
74  this member stores a pointer to its
75  location in memory.) */
76  llvm::Function *function; /*!< For symbols that represent functions,
77  this stores the LLVM Function value for
78  the symbol once it has been created. */
79  llvm::Function *exportedFunction;
80  /*!< For symbols that represent functions with
81  'export' qualifiers, this points to the LLVM
82  Function for the application-callable version
83  of the function. */
84  const Type *type; /*!< The type of the symbol; if not set by the
85  constructor, this is set after the
86  declaration around the symbol has been parsed. */
87  ConstExpr *constValue; /*!< For symbols with const-qualified types, this may store
88  the symbol's compile-time constant value. This value may
89  validly be NULL for a const-qualified type, however; for
90  example, the ConstExpr class can't currently represent
91  struct types. For cases like these, ConstExpr is NULL,
92  though for all const symbols, the value pointed to by the
93  storagePtr member will be its constant value. (This
94  messiness is due to needing an ispc ConstExpr for the early
95  constant folding optimizations). */
96  StorageClass storageClass;/*!< Records the storage class (if any) provided with the
97  symbol's declaration. */
98  int varyingCFDepth; /*!< This member records the number of levels of nested 'varying'
99  control flow within which the symbol was declared. Having
100  this value available makes it possible to avoid performing
101  masked stores when modifying the symbol's value when the
102  store is done at the same 'varying' control flow depth as
103  the one where the symbol was originally declared. */
105  /*!< For symbols that are parameters to functions or are
106  variables declared inside functions, this gives the
107  function they're in. */
108 };
109 
110 
111 /** @brief Symbol table that holds all known symbols during parsing and compilation.
112 
113  A single instance of a SymbolTable is stored in the Module class
114  (Module::symbolTable); it is created in the Module::Module()
115  constructor. It is then accessed via the global variable Module *\ref m
116  throughout the ispc implementation.
117  */
118 
119 class SymbolTable {
120 public:
121  SymbolTable();
122  ~SymbolTable();
123 
124  /** The parser calls this method when it enters a new scope in the
125  program; this allows us to track variables that shadows others in
126  outer scopes with same name as well as to efficiently discard all
127  of the variables declared in a particular scope when we exit that
128  scope. */
129  void PushScope();
130 
131  /** For each scope started by a call to SymbolTable::PushScope(), there
132  must be a matching call to SymbolTable::PopScope() at the end of
133  that scope. */
134  void PopScope();
135 
136  /** Adds the given variable symbol to the symbol table.
137  @param symbol The symbol to be added
138 
139  @return true if successful; false if the provided symbol clashes
140  with a symbol defined at the same scope. (Symbols may shaodow
141  symbols in outer scopes; a warning is issued in this case, but this
142  method still returns true.) */
143  bool AddVariable(Symbol *symbol);
144 
145  /** Looks for a variable with the given name in the symbol table. This
146  method searches outward from the innermost scope to the outermost,
147  returning the first match found.
148 
149  @param name The name of the variable to be searched for.
150  @return A pointer to the Symbol, if a match is found. NULL if no
151  Symbol with the given name is in the symbol table. */
152  Symbol *LookupVariable(const char *name);
153 
154  /** Adds the given function symbol to the symbol table.
155  @param symbol The function symbol to be added.
156 
157  @return true if the symbol has been added. False if another
158  function symbol with the same name and function signature is
159  already present in the symbol table. */
160  bool AddFunction(Symbol *symbol);
161 
162  /** Looks for the function or functions with the given name in the
163  symbol name. If a function has been overloaded and multiple
164  definitions are present for a given function name, all of them will
165  be returned in the provided vector and it's up the the caller to
166  resolve which one (if any) to use. Returns true if any matches
167  were found. */
168  bool LookupFunction(const char *name,
169  std::vector<Symbol *> *matches = NULL);
170 
171  /** Looks for a function with the given name and type
172  in the symbol table.
173 
174  @return pointer to matching Symbol; NULL if none is found. */
175  Symbol *LookupFunction(const char *name, const FunctionType *type);
176 
177  /** Returns all of the functions in the symbol table that match the given
178  predicate.
179 
180  @param pred A unary predicate that returns true or false, given a Symbol
181  pointer, based on whether the symbol should be included in the returned
182  set of matches. It can either be a function, with signature
183  <tt>bool pred(const Symbol *s)</tt>, or a unary predicate object with
184  an <tt>bool operator()(const Symbol *)</tt> method.
185 
186  @param matches Pointer to a vector in which to return the matching
187  symbols.
188  */
189  template <typename Predicate>
190  void GetMatchingFunctions(Predicate pred,
191  std::vector<Symbol *> *matches) const;
192 
193  /** Returns all of the variable symbols in the symbol table that match
194  the given predicate. The predicate is defined as in the
195  GetMatchingFunctions() method.
196  */
197  template <typename Predicate>
198  void GetMatchingVariables(Predicate pred,
199  std::vector<Symbol *> *matches) const;
200 
201  /** Adds the named type to the symbol table. This is used for both
202  struct definitions (where <tt>struct Foo</tt> causes type \c Foo to
203  be added to the symbol table) as well as for <tt>typedef</tt>s.
204  For structs with forward declarations ("struct Foo;") and are thus
205  UndefinedStructTypes, this method replaces these with an actual
206  struct definition if one is provided.
207 
208  @param name Name of the type to be added
209  @param type Type that \c name represents
210  @param pos Position in source file where the type was named
211  @return true if the named type was successfully added. False if a type
212  with the same name has already been defined.
213 
214  */
215  bool AddType(const char *name, const Type *type, SourcePos pos);
216 
217  /** Looks for a type of the given name in the symbol table.
218 
219  @return Pointer to the Type, if found; otherwise NULL is returned.
220  */
221  const Type *LookupType(const char *name) const;
222 
223  /** Look for a type given a pointer.
224 
225  @return True if found, False otherwise.
226  */
227  bool ContainsType(const Type * type) const;
228 
229  /** This method returns zero or more strings with the names of symbols
230  in the symbol table that nearly (but not exactly) match the given
231  name. This is useful for issuing informative error methods when
232  misspelled identifiers are found a programs.
233 
234  @param name String to compare variable and function symbol names against.
235  @return vector of zero or more strings that approximately match \c name.
236  */
237  std::vector<std::string> ClosestVariableOrFunctionMatch(const char *name) const;
238  /** This method returns zero or more strings with the names of types
239  in the symbol table that nearly (but not exactly) match the given
240  name. */
241  std::vector<std::string> ClosestTypeMatch(const char *name) const;
242 
243  std::vector<std::string> ClosestEnumTypeMatch(const char *name) const;
244 
245  /** Prints out the entire contents of the symbol table to standard error.
246  (Debugging method). */
247  void Print();
248 
249  /** Returns a random symbol from the symbol table. (It is not
250  guaranteed that it is equally likely to return all symbols). */
251  Symbol *RandomSymbol();
252 
253  /** Returns a random type from the symbol table. */
254  const Type *RandomType();
255 
256 private:
257  std::vector<std::string> closestTypeMatch(const char *str,
258  bool structsVsEnums) const;
259 
260  /** This member variable holds one SymbolMap for each of the current
261  active scopes as the program is being parsed. New maps are added
262  and removed from the end of the main vector, so searches for
263  symbols start looking at the end of \c variables and work
264  backwards.
265  */
266  typedef std::map<std::string, Symbol *> SymbolMapType;
267  std::vector<SymbolMapType *> variables;
268 
269  std::vector<SymbolMapType *> freeSymbolMaps;
270 
271  /** Function declarations are *not* scoped. (C99, for example, allows
272  an implementation to maintain function declarations in a single
273  namespace.) A STL \c vector is used to store the function symbols
274  for a given name since, due to function overloading, a name can
275  have multiple function symbols associated with it. */
276  typedef std::map<std::string, std::vector<Symbol *> > FunctionMapType;
277  FunctionMapType functions;
278 
279  /** Type definitions can't currently be scoped.
280  */
281  typedef std::map<std::string, const Type *> TypeMapType;
282  TypeMapType types;
283 };
284 
285 
286 template <typename Predicate> void
288  std::vector<Symbol *> *matches) const {
289  // Iterate through all function symbols and apply the given predicate.
290  // If it returns true, add the Symbol * to the provided vector.
291  FunctionMapType::const_iterator iter;
292  for (iter = functions.begin(); iter != functions.end(); ++iter) {
293  const std::vector<Symbol *> &syms = iter->second;
294  for (unsigned int j = 0; j < syms.size(); ++j) {
295  if (pred(syms[j]))
296  matches->push_back(syms[j]);
297  }
298  }
299 }
300 
301 
302 template <typename Predicate> void
304  std::vector<Symbol *> *matches) const {
305  for (unsigned int i = 0; i < variables.size(); ++i) {
306  SymbolMapType &sm = *(variables[i]);
307  SymbolMapType::const_iterator iter;
308  for (iter = sm.begin(); iter != sm.end(); ++iter) {
309  if (pred(iter->second))
310  matches->push_back(iter->second);
311  }
312  }
313 }
314 
315 #endif // ISPC_SYM_H
llvm::Value * storagePtr
Definition: sym.h:72
std::vector< std::string > closestTypeMatch(const char *str, bool structsVsEnums) const
Definition: sym.cpp:281
Definition: func.h:44
bool ContainsType(const Type *type) const
Definition: sym.cpp:218
void Print()
Definition: sym.cpp:313
std::map< std::string, const Type * > TypeMapType
Definition: sym.h:281
bool AddFunction(Symbol *symbol)
Definition: sym.cpp:147
void PushScope()
Definition: sym.cpp:75
bool AddVariable(Symbol *symbol)
Definition: sym.cpp:98
Expression representing a compile-time constant value.
Definition: expr.h:390
Symbol table that holds all known symbols during parsing and compilation.
Definition: sym.h:119
FunctionMapType functions
Definition: sym.h:277
std::vector< std::string > ClosestEnumTypeMatch(const char *name) const
Definition: sym.cpp:275
std::string name
Definition: sym.h:71
Symbol * LookupVariable(const char *name)
Definition: sym.cpp:131
std::vector< std::string > ClosestTypeMatch(const char *name) const
Definition: sym.cpp:269
~SymbolTable()
Definition: sym.cpp:67
ConstExpr * constValue
Definition: sym.h:87
TypeMapType types
Definition: sym.h:282
std::vector< SymbolMapType * > freeSymbolMaps
Definition: sym.h:269
void GetMatchingFunctions(Predicate pred, std::vector< Symbol * > *matches) const
Definition: sym.h:287
Symbol(const std::string &name, SourcePos pos, const Type *t=NULL, StorageClass sc=SC_NONE)
Definition: sym.cpp:46
const Type * LookupType(const char *name) const
Definition: sym.cpp:209
bool LookupFunction(const char *name, std::vector< Symbol * > *matches=NULL)
Definition: sym.cpp:162
bool AddType(const char *name, const Type *type, SourcePos pos)
Definition: sym.cpp:192
void GetMatchingVariables(Predicate pred, std::vector< Symbol * > *matches) const
Definition: sym.h:303
std::map< std::string, std::vector< Symbol * > > FunctionMapType
Definition: sym.h:276
std::vector< SymbolMapType * > variables
Definition: sym.h:267
Representation of a structure holding a number of members.
Definition: type.h:690
const Type * RandomType()
Definition: sym.cpp:376
SourcePos pos
Definition: sym.h:70
StorageClass storageClass
Definition: sym.h:96
Representation of a range of positions in a source file.
Definition: ispc.h:134
Declarations related to type declarations; the parser basically creates instances of these classes...
StorageClass
Definition: ispc.h:118
SymbolTable()
Definition: sym.cpp:62
Definition: ispc.h:119
std::map< std::string, Symbol * > SymbolMapType
Definition: sym.h:266
Type representing a function (return type + argument types)
Definition: type.h:883
Representation of a program symbol.
Definition: sym.h:63
int varyingCFDepth
Definition: sym.h:98
Interface class that defines the type abstraction.
Definition: type.h:101
const Function * parentFunction
Definition: sym.h:104
void PopScope()
Definition: sym.cpp:90
Symbol * RandomSymbol()
Definition: sym.cpp:361
std::vector< std::string > ClosestVariableOrFunctionMatch(const char *name) const
Definition: sym.cpp:230
const Type * type
Definition: sym.h:84
Main ispc.header file. Defines Target, Globals and Opt classes.
llvm::Function * exportedFunction
Definition: sym.h:79