Intel SPMD Program Compiler  1.3.0
sym.h
Go to the documentation of this file.
00001 /*
00002   Copyright (c) 2010-2012, Intel Corporation
00004
00005   Redistribution and use in source and binary forms, with or without
00006   modification, are permitted provided that the following conditions are
00007   met:
00008
00009     * Redistributions of source code must retain the above copyright
00010       notice, this list of conditions and the following disclaimer.
00011
00012     * Redistributions in binary form must reproduce the above copyright
00013       notice, this list of conditions and the following disclaimer in the
00014       documentation and/or other materials provided with the distribution.
00015
00016     * Neither the name of Intel Corporation nor the names of its
00017       contributors may be used to endorse or promote products derived from
00018       this software without specific prior written permission.
00019
00020
00021    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
00022    IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
00023    TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
00024    PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
00025    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00026    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00027    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00028    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00029    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00030    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00031    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00032 */
00033
00034 /** @file sym.h
00035
00036     @brief header file with declarations for symbol and symbol table
00037     classes.
00038 */
00039
00040 #ifndef ISPC_SYM_H
00041 #define ISPC_SYM_H
00042
00043 #include "ispc.h"
00044 #include "decl.h"
00045 #include <map>
00046
00047 class StructType;
00048 class ConstExpr;
00049
00050 /**
00051    @brief Representation of a program symbol.
00052
00053    The Symbol class represents a symbol in an ispc program.  Symbols can
00054    include variables, functions, and named types.  Note that all of the
00055    members are publically accessible; other code throughout the system
00056    accesses and modifies the members directly.
00057
00058    @todo Should we break function symbols into a separate FunctionSymbol
00059    class and then not have these members that are not applicable for
00060    function symbols (and vice versa, for non-function symbols)?
00061  */
00062
00063 class Symbol {
00064 public:
00065     /** The Symbol constructor takes the name of the symbol, its
00066         position in a source file, and its type (if known). */
00067     Symbol(const std::string &name, SourcePos pos, const Type *t = NULL,
00068            StorageClass sc = SC_NONE);
00069
00070     SourcePos pos;            /*!< Source file position where the symbol was defined */
00071     std::string name;         /*!< Symbol's name */
00072     llvm::Value *storagePtr;  /*!< For symbols with storage associated with
00073                                    them (i.e. variables but not functions),
00074                                    this member stores a pointer to its
00075                                    location in memory.) */
00076     llvm::Function *function; /*!< For symbols that represent functions,
00077                                    this stores the LLVM Function value for
00078                                    the symbol once it has been created. */
00079     llvm::Function *exportedFunction;
00080                               /*!< For symbols that represent functions with
00081                                    'export' qualifiers, this points to the LLVM
00082                                    Function for the application-callable version
00083                                    of the function. */
00084     const Type *type;         /*!< The type of the symbol; if not set by the
00085                                    constructor, this is set after the
00086                                    declaration around the symbol has been parsed.  */
00087     ConstExpr *constValue;    /*!< For symbols with const-qualified types, this may store
00088                                    the symbol's compile-time constant value.  This value may
00089                                    validly be NULL for a const-qualified type, however; for
00090                                    example, the ConstExpr class can't currently represent
00091                                    struct types.  For cases like these, ConstExpr is NULL,
00092                                    though for all const symbols, the value pointed to by the
00093                                    storagePtr member will be its constant value.  (This
00094                                    messiness is due to needing an ispc ConstExpr for the early
00095                                    constant folding optimizations). */
00096     StorageClass storageClass;/*!< Records the storage class (if any) provided with the
00097                                    symbol's declaration. */
00098     int varyingCFDepth;       /*!< This member records the number of levels of nested 'varying'
00099                                    control flow within which the symbol was declared.  Having
00100                                    this value available makes it possible to avoid performing
00101                                    masked stores when modifying the symbol's value when the
00102                                    store is done at the same 'varying' control flow depth as
00103                                    the one where the symbol was originally declared. */
00104     const Function *parentFunction;
00105                               /*!< For symbols that are parameters to functions or are
00106                                    variables declared inside functions, this gives the
00107                                    function they're in. */
00108 };
00109
00110
00111 /** @brief Symbol table that holds all known symbols during parsing and compilation.
00112
00113     A single instance of a SymbolTable is stored in the Module class
00114     (Module::symbolTable); it is created in the Module::Module()
00115     constructor.  It is then accessed via the global variable Module *\ref m
00116     throughout the ispc implementation.
00117  */
00118
00119 class SymbolTable {
00120 public:
00121     SymbolTable();
00122     ~SymbolTable();
00123
00124     /** The parser calls this method when it enters a new scope in the
00125         program; this allows us to track variables that shadows others in
00126         outer scopes with same name as well as to efficiently discard all
00127         of the variables declared in a particular scope when we exit that
00128         scope. */
00129     void PushScope();
00130
00131     /** For each scope started by a call to SymbolTable::PushScope(), there
00132         must be a matching call to SymbolTable::PopScope() at the end of
00133         that scope. */
00134     void PopScope();
00135
00136     /** Adds the given variable symbol to the symbol table.
00137         @param symbol The symbol to be added
00138
00139         @return true if successful; false if the provided symbol clashes
00140         with a symbol defined at the same scope.  (Symbols may shaodow
00141         symbols in outer scopes; a warning is issued in this case, but this
00142         method still returns true.) */
00144
00145     /** Looks for a variable with the given name in the symbol table.  This
00146         method searches outward from the innermost scope to the outermost,
00147         returning the first match found.
00148
00149         @param  name The name of the variable to be searched for.
00150         @return A pointer to the Symbol, if a match is found.  NULL if no
00151         Symbol with the given name is in the symbol table. */
00152     Symbol *LookupVariable(const char *name);
00153
00154     /** Adds the given function symbol to the symbol table.
00155         @param symbol The function symbol to be added.
00156
00157         @return true if the symbol has been added.  False if another
00158         function symbol with the same name and function signature is
00159         already present in the symbol table. */
00161
00162     /** Looks for the function or functions with the given name in the
00163         symbol name.  If a function has been overloaded and multiple
00164         definitions are present for a given function name, all of them will
00165         be returned in the provided vector and it's up the the caller to
00166         resolve which one (if any) to use.  Returns true if any matches
00167         were found. */
00168     bool LookupFunction(const char *name,
00169                         std::vector<Symbol *> *matches = NULL);
00170
00171     /** Looks for a function with the given name and type
00172         in the symbol table.
00173
00174         @return pointer to matching Symbol; NULL if none is found. */
00175     Symbol *LookupFunction(const char *name, const FunctionType *type);
00176
00177     /** Returns all of the functions in the symbol table that match the given
00178         predicate.
00179
00180         @param pred A unary predicate that returns true or false, given a Symbol
00181         pointer, based on whether the symbol should be included in the returned
00182         set of matches.  It can either be a function, with signature
00183         <tt>bool pred(const Symbol *s)</tt>, or a unary predicate object with
00184         an <tt>bool operator()(const Symbol *)</tt> method.
00185
00186         @param matches Pointer to a vector in which to return the matching
00187         symbols.
00188      */
00189     template <typename Predicate>
00190         void GetMatchingFunctions(Predicate pred,
00191                                   std::vector<Symbol *> *matches) const;
00192
00193     /** Returns all of the variable symbols in the symbol table that match
00194         the given predicate.  The predicate is defined as in the
00195         GetMatchingFunctions() method.
00196      */
00197     template <typename Predicate>
00198         void GetMatchingVariables(Predicate pred,
00199                                   std::vector<Symbol *> *matches) const;
00200
00201     /** Adds the named type to the symbol table.  This is used for both
00202         struct definitions (where <tt>struct Foo</tt> causes type \c Foo to
00203         be added to the symbol table) as well as for <tt>typedef</tt>s.
00204         For structs with forward declarations ("struct Foo;") and are thus
00205         UndefinedStructTypes, this method replaces these with an actual
00206         struct definition if one is provided.
00207
00208         @param name Name of the type to be added
00209         @param type Type that \c name represents
00210         @param pos Position in source file where the type was named
00211         @return true if the named type was successfully added.  False if a type
00212         with the same name has already been defined.
00213
00214     */
00215     bool AddType(const char *name, const Type *type, SourcePos pos);
00216
00217     /** Looks for a type of the given name in the symbol table.
00218
00219         @return Pointer to the Type, if found; otherwise NULL is returned.
00220     */
00221     const Type *LookupType(const char *name) const;
00222
00223     /** This method returns zero or more strings with the names of symbols
00224         in the symbol table that nearly (but not exactly) match the given
00225         name.  This is useful for issuing informative error methods when
00226         misspelled identifiers are found a programs.
00227
00228         @param name String to compare variable and function symbol names against.
00229         @return vector of zero or more strings that approximately match \c name.
00230     */
00231     std::vector<std::string> ClosestVariableOrFunctionMatch(const char *name) const;
00232     /** This method returns zero or more strings with the names of types
00233         in the symbol table that nearly (but not exactly) match the given
00234         name. */
00235     std::vector<std::string> ClosestTypeMatch(const char *name) const;
00236
00237     std::vector<std::string> ClosestEnumTypeMatch(const char *name) const;
00238
00239     /** Prints out the entire contents of the symbol table to standard error.
00240         (Debugging method). */
00241     void Print();
00242
00243     /** Returns a random symbol from the symbol table. (It is not
00244         guaranteed that it is equally likely to return all symbols). */
00245     Symbol *RandomSymbol();
00246
00247     /** Returns a random type from the symbol table. */
00248     const Type *RandomType();
00249
00250 private:
00251     std::vector<std::string> closestTypeMatch(const char *str,
00252                                               bool structsVsEnums) const;
00253
00254     /** This member variable holds one SymbolMap for each of the current
00255         active scopes as the program is being parsed.  New maps are added
00256         and removed from the end of the main vector, so searches for
00257         symbols start looking at the end of \c variables and work
00258         backwards.
00259      */
00260     typedef std::map<std::string, Symbol *> SymbolMapType;
00261     std::vector<SymbolMapType *> variables;
00262
00263     std::vector<SymbolMapType *> freeSymbolMaps;
00264
00265     /** Function declarations are *not* scoped.  (C99, for example, allows
00266         an implementation to maintain function declarations in a single
00267         namespace.)  A STL \c vector is used to store the function symbols
00268         for a given name since, due to function overloading, a name can
00269         have multiple function symbols associated with it. */
00270     typedef std::map<std::string, std::vector<Symbol *> > FunctionMapType;
00271     FunctionMapType functions;
00272
00273     /** Type definitions can't currently be scoped.
00274      */
00275     typedef std::map<std::string, const Type *> TypeMapType;
00276     TypeMapType types;
00277 };
00278
00279
00280 template <typename Predicate> void
00281 SymbolTable::GetMatchingFunctions(Predicate pred,
00282                                   std::vector<Symbol *> *matches) const {
00283     // Iterate through all function symbols and apply the given predicate.
00284     // If it returns true, add the Symbol * to the provided vector.
00285     FunctionMapType::const_iterator iter;
00286     for (iter = functions.begin(); iter != functions.end(); ++iter) {
00287         const std::vector<Symbol *> &syms = iter->second;
00288         for (unsigned int j = 0; j < syms.size(); ++j) {
00289             if (pred(syms[j]))
00290                 matches->push_back(syms[j]);
00291         }
00292     }
00293 }
00294
00295
00296 template <typename Predicate> void
00297 SymbolTable::GetMatchingVariables(Predicate pred,
00298                                   std::vector<Symbol *> *matches) const {
00299     for (unsigned int i = 0; i < variables.size(); ++i) {
00300         SymbolMapType &sm = *(variables[i]);
00301         SymbolMapType::const_iterator iter;
00302         for (iter = sm.begin(); iter != sm.end(); ++iter) {
00303             if (pred(iter->second))
00304                 matches->push_back(iter->second);
00305         }
00306     }
00307 }
00308
00309 #endif // ISPC_SYM_H