Intel SPMD Program Compiler  1.9.1
sym.cpp
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.cpp
35  @brief file with definitions for symbol and symbol table classes.
36 */
37 
38 #include "sym.h"
39 #include "type.h"
40 #include "util.h"
41 #include <stdio.h>
42 
43 ///////////////////////////////////////////////////////////////////////////
44 // Symbol
45 
46 Symbol::Symbol(const std::string &n, SourcePos p, const Type *t,
47  StorageClass sc)
48  : pos(p), name(n) {
49  storagePtr = NULL;
50  function = exportedFunction = NULL;
51  type = t;
52  constValue = NULL;
53  storageClass = sc;
54  varyingCFDepth = 0;
55  parentFunction = NULL;
56 }
57 
58 
59 ///////////////////////////////////////////////////////////////////////////
60 // SymbolTable
61 
63  PushScope();
64 }
65 
66 
68  // Otherwise we have mismatched push/pop scopes
69  Assert(variables.size() == 1);
70  PopScope();
71 }
72 
73 
74 void
76  SymbolMapType *sm;
77  if (freeSymbolMaps.size() > 0) {
78  sm = freeSymbolMaps.back();
79  freeSymbolMaps.pop_back();
80  sm->erase(sm->begin(), sm->end());
81  }
82  else
83  sm = new SymbolMapType;
84 
85  variables.push_back(sm);
86 }
87 
88 
89 void
91  Assert(variables.size() > 1);
92  freeSymbolMaps.push_back(variables.back());
93  variables.pop_back();
94 }
95 
96 
97 bool
99  Assert(symbol != NULL);
100 
101  // Check to see if a symbol of the same name has already been declared.
102  for (int i = (int)variables.size() - 1; i >= 0; --i) {
103  SymbolMapType &sm = *(variables[i]);
104  if (sm.find(symbol->name) != sm.end()) {
105  if (i == (int)variables.size()-1) {
106  // If a symbol of the same name was declared in the
107  // same scope, it's an error.
108  Error(symbol->pos, "Ignoring redeclaration of symbol \"%s\".",
109  symbol->name.c_str());
110  return false;
111  }
112  else {
113  // Otherwise it's just shadowing something else, which
114  // is legal but dangerous..
115  Warning(symbol->pos,
116  "Symbol \"%s\" shadows symbol declared in outer scope.",
117  symbol->name.c_str());
118  (*variables.back())[symbol->name] = symbol;
119  return true;
120  }
121  }
122  }
123 
124  // No matches, so go ahead and add it...
125  (*variables.back())[symbol->name] = symbol;
126  return true;
127 }
128 
129 
130 Symbol *
131 SymbolTable::LookupVariable(const char *name) {
132  // Note that we iterate through the variables vectors backwards, since
133  // we want to search from the innermost scope to the outermost, so that
134  // we get the right symbol if we have multiple variables in different
135  // scopes that shadow each other.
136  for (int i = (int)variables.size() - 1; i >= 0; --i) {
137  SymbolMapType &sm = *(variables[i]);
138  SymbolMapType::iterator iter = sm.find(name);
139  if (iter != sm.end())
140  return iter->second;
141  }
142  return NULL;
143 }
144 
145 
146 bool
148  const FunctionType *ft = CastType<FunctionType>(symbol->type);
149  Assert(ft != NULL);
150  if (LookupFunction(symbol->name.c_str(), ft) != NULL)
151  // A function of the same name and type has already been added to
152  // the symbol table
153  return false;
154 
155  std::vector<Symbol *> &funOverloads = functions[symbol->name];
156  funOverloads.push_back(symbol);
157  return true;
158 }
159 
160 
161 bool
162 SymbolTable::LookupFunction(const char *name, std::vector<Symbol *> *matches) {
163  FunctionMapType::iterator iter = functions.find(name);
164  if (iter != functions.end()) {
165  if (matches == NULL)
166  return true;
167  else {
168  const std::vector<Symbol *> &funcs = iter->second;
169  for (int j = 0; j < (int)funcs.size(); ++j)
170  matches->push_back(funcs[j]);
171  }
172  }
173  return matches ? (matches->size() > 0) : false;
174 }
175 
176 
177 Symbol *
178 SymbolTable::LookupFunction(const char *name, const FunctionType *type) {
179  FunctionMapType::iterator iter = functions.find(name);
180  if (iter != functions.end()) {
181  std::vector<Symbol *> funcs = iter->second;
182  for (int j = 0; j < (int)funcs.size(); ++j) {
183  if (Type::Equal(funcs[j]->type, type))
184  return funcs[j];
185  }
186  }
187  return NULL;
188 }
189 
190 
191 bool
192 SymbolTable::AddType(const char *name, const Type *type, SourcePos pos) {
193  const Type *t = LookupType(name);
194  if (t != NULL && CastType<UndefinedStructType>(t) == NULL) {
195  // If we have a previous declaration of anything other than an
196  // UndefinedStructType with this struct name, issue an error. If
197  // we have an UndefinedStructType, then we'll fall through to the
198  // code below that adds the definition to the type map.
199  Error(pos, "Ignoring redefinition of type \"%s\".", name);
200  return false;
201  }
202 
203  types[name] = type;
204  return true;
205 }
206 
207 
208 const Type *
209 SymbolTable::LookupType(const char *name) const {
210  // Again, search through the type maps backward to get scoping right.
211  TypeMapType::const_iterator iter = types.find(name);
212  if (iter != types.end())
213  return iter->second;
214  return NULL;
215 }
216 
217 bool
218 SymbolTable::ContainsType(const Type *type) const {
219  TypeMapType::const_iterator iter = types.begin();
220  while (iter != types.end()) {
221  if (iter->second == type) {
222  return true;
223  }
224  iter++;
225  }
226  return false;
227 }
228 
229 std::vector<std::string>
231  // This is a little wasteful, but we'll look through all of the
232  // variable and function symbols and compute the edit distance from the
233  // given string to them. If the edit distance is under maxDelta, then
234  // it goes in the entry of the matches[] array corresponding to its
235  // edit distance.
236  const int maxDelta = 2;
237  std::vector<std::string> matches[maxDelta+1];
238 
239  for (int i = 0; i < (int)variables.size(); ++i) {
240  const SymbolMapType &sv = *(variables[i]);
241  SymbolMapType::const_iterator iter;
242  for (iter = sv.begin(); iter != sv.end(); ++iter) {
243  const Symbol *sym = iter->second;
244  int dist = StringEditDistance(str, sym->name, maxDelta+1);
245  if (dist <= maxDelta)
246  matches[dist].push_back(sym->name);
247  }
248  }
249 
250  FunctionMapType::const_iterator iter;
251  for (iter = functions.begin(); iter != functions.end(); ++iter) {
252  int dist = StringEditDistance(str, iter->first, maxDelta+1);
253  if (dist <= maxDelta)
254  matches[dist].push_back(iter->first);
255  }
256 
257  // Now, return the first entry of matches[] that is non-empty, if any.
258  for (int i = 0; i <= maxDelta; ++i) {
259  if (matches[i].size())
260  return matches[i];
261  }
262 
263  // Otherwise, no joy.
264  return std::vector<std::string>();
265 }
266 
267 
268 std::vector<std::string>
269 SymbolTable::ClosestTypeMatch(const char *str) const {
270  return closestTypeMatch(str, true);
271 }
272 
273 
274 std::vector<std::string>
275 SymbolTable::ClosestEnumTypeMatch(const char *str) const {
276  return closestTypeMatch(str, false);
277 }
278 
279 
280 std::vector<std::string>
281 SymbolTable::closestTypeMatch(const char *str, bool structsVsEnums) const {
282  // This follows the same approach as ClosestVariableOrFunctionMatch()
283  // above; compute all edit distances, keep the ones shorter than
284  // maxDelta, return the first non-empty vector of one or more sets of
285  // alternatives with minimal edit distance.
286  const int maxDelta = 2;
287  std::vector<std::string> matches[maxDelta+1];
288 
289  TypeMapType::const_iterator iter;
290  for (iter = types.begin(); iter != types.end(); ++iter) {
291  // Skip over either StructTypes or EnumTypes, depending on the
292  // value of the structsVsEnums parameter
293  bool isEnum = (CastType<EnumType>(iter->second) != NULL);
294  if (isEnum && structsVsEnums)
295  continue;
296  else if (!isEnum && !structsVsEnums)
297  continue;
298 
299  int dist = StringEditDistance(str, iter->first, maxDelta+1);
300  if (dist <= maxDelta)
301  matches[dist].push_back(iter->first);
302  }
303 
304  for (int i = 0; i <= maxDelta; ++i) {
305  if (matches[i].size())
306  return matches[i];
307  }
308  return std::vector<std::string>();
309 }
310 
311 
312 void
314  int depth = 0;
315  fprintf(stderr, "Variables:\n----------------\n");
316  for (int i = 0; i < (int)variables.size(); ++i) {
317  SymbolMapType &sm = *(variables[i]);
318  SymbolMapType::iterator iter;
319  for (iter = sm.begin(); iter != sm.end(); ++iter) {
320  fprintf(stderr, "%*c", depth, ' ');
321  Symbol *sym = iter->second;
322  fprintf(stderr, "%s [%s]", sym->name.c_str(),
323  sym->type->GetString().c_str());
324  }
325  fprintf(stderr, "\n");
326  depth += 4;
327  }
328 
329  fprintf(stderr, "Functions:\n----------------\n");
330  FunctionMapType::iterator fiter = functions.begin();
331  while (fiter != functions.end()) {
332  fprintf(stderr, "%s\n", fiter->first.c_str());
333  std::vector<Symbol *> &syms = fiter->second;
334  for (unsigned int j = 0; j < syms.size(); ++j)
335  fprintf(stderr, " %s\n", syms[j]->type->GetString().c_str());
336  ++fiter;
337  }
338 
339  depth = 0;
340  fprintf(stderr, "Named types:\n---------------\n");
341  TypeMapType::iterator siter = types.begin();
342  while (siter != types.end()) {
343  fprintf(stderr, "%*c", depth, ' ');
344  fprintf(stderr, "%s -> %s\n", siter->first.c_str(),
345  siter->second->GetString().c_str());
346  ++siter;
347  }
348 }
349 
350 
351 inline int ispcRand() {
352 #ifdef ISPC_IS_WINDOWS
353  return rand();
354 #else
355  return lrand48();
356 #endif
357 }
358 
359 
360 Symbol *
362  int v = ispcRand() % variables.size();
363  if (variables[v]->size() == 0)
364  return NULL;
365  int count = ispcRand() % variables[v]->size();
366  SymbolMapType::iterator iter = variables[v]->begin();
367  while (count-- > 0) {
368  ++iter;
369  Assert(iter != variables[v]->end());
370  }
371  return iter->second;
372 }
373 
374 
375 const Type *
377  int count = types.size();
378  TypeMapType::iterator iter = types.begin();
379  while (count-- > 0) {
380  ++iter;
381  Assert(iter != types.end());
382  }
383  return iter->second;
384 }
llvm::Value * storagePtr
Definition: sym.h:72
std::vector< std::string > closestTypeMatch(const char *str, bool structsVsEnums) const
Definition: sym.cpp:281
bool ContainsType(const Type *type) const
Definition: sym.cpp:218
void Print()
Definition: sym.cpp:313
bool AddFunction(Symbol *symbol)
Definition: sym.cpp:147
void PushScope()
Definition: sym.cpp:75
bool AddVariable(Symbol *symbol)
Definition: sym.cpp:98
#define Assert(expr)
Definition: ispc.h:170
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
virtual std::string GetString() const =0
ConstExpr * constValue
Definition: sym.h:87
header file with declarations for symbol and symbol table classes.
TypeMapType types
Definition: sym.h:282
std::vector< SymbolMapType * > freeSymbolMaps
Definition: sym.h:269
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
int StringEditDistance(const std::string &str1, const std::string &str2, int maxDist)
Definition: util.cpp:482
void Error(SourcePos p, const char *format,...) PRINTF_FUNC
Definition: util.cpp:385
std::vector< SymbolMapType * > variables
Definition: sym.h:267
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
StorageClass
Definition: ispc.h:118
void Warning(SourcePos p, const char *format,...) PRINTF_FUNC
Definition: util.cpp:410
SymbolTable()
Definition: sym.cpp:62
static bool Equal(const Type *a, const Type *b)
Definition: type.cpp:3619
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
int ispcRand()
Definition: sym.cpp:351
llvm::Function * exportedFunction
Definition: sym.h:79
File with declarations for classes related to type representation.