1// Copyright 2016 The SwiftShader Authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef _SYMBOL_TABLE_INCLUDED_
16#define _SYMBOL_TABLE_INCLUDED_
17
18//
19// Symbol table for parsing. Has these design characteristics:
20//
21// * Same symbol table can be used to compile many shaders, to preserve
22// effort of creating and loading with the large numbers of built-in
23// symbols.
24//
25// * Name mangling will be used to give each function a unique name
26// so that symbol table lookups are never ambiguous. This allows
27// a simpler symbol table structure.
28//
29// * Pushing and popping of scope, so symbol table will really be a stack
30// of symbol tables. Searched from the top, with new inserts going into
31// the top.
32//
33// * Constants: Compile time constant symbols will keep their values
34// in the symbol table. The parser can substitute constants at parse
35// time, including doing constant folding and constant propagation.
36//
37// * No temporaries: Temporaries made from operations (+, --, .xy, etc.)
38// are tracked in the intermediate representation, not the symbol table.
39//
40
41#if defined(__ANDROID__) && !defined(ANDROID_HOST_BUILD) && !defined(ANDROID_NDK_BUILD)
42#include "../../Common/DebugAndroid.hpp"
43#else
44#include <assert.h>
45#endif
46
47#include "InfoSink.h"
48#include "intermediate.h"
49#include <set>
50
51//
52// Symbol base class. (Can build functions or variables out of these...)
53//
54class TSymbol
55{
56public:
57 POOL_ALLOCATOR_NEW_DELETE()
58 TSymbol(const TString *n) : name(n) { }
59 virtual ~TSymbol() { /* don't delete name, it's from the pool */ }
60
61 const TString& getName() const { return *name; }
62 virtual const TString& getMangledName() const { return getName(); }
63 virtual bool isFunction() const { return false; }
64 virtual bool isVariable() const { return false; }
65 void setUniqueId(int id) { uniqueId = id; }
66 int getUniqueId() const { return uniqueId; }
67 TSymbol(const TSymbol&);
68
69protected:
70 const TString *name;
71 unsigned int uniqueId; // For real comparing during code generation
72};
73
74//
75// Variable class, meaning a symbol that's not a function.
76//
77// There could be a separate class heirarchy for Constant variables;
78// Only one of int, bool, or float, (or none) is correct for
79// any particular use, but it's easy to do this way, and doesn't
80// seem worth having separate classes, and "getConst" can't simply return
81// different values for different types polymorphically, so this is
82// just simple and pragmatic.
83//
84class TVariable : public TSymbol
85{
86public:
87 TVariable(const TString *name, const TType& t, bool uT = false ) : TSymbol(name), type(t), userType(uT), unionArray(0), arrayInformationType(0) { }
88 virtual ~TVariable() { }
89 virtual bool isVariable() const { return true; }
90 TType& getType() { return type; }
91 const TType& getType() const { return type; }
92 bool isUserType() const { return userType; }
93 void setQualifier(TQualifier qualifier) { type.setQualifier(qualifier); }
94 void updateArrayInformationType(TType *t) { arrayInformationType = t; }
95 TType* getArrayInformationType() { return arrayInformationType; }
96
97 ConstantUnion* getConstPointer()
98 {
99 if (!unionArray)
100 unionArray = new ConstantUnion[type.getObjectSize()];
101
102 return unionArray;
103 }
104
105 ConstantUnion* getConstPointer() const { return unionArray; }
106 bool isConstant() const { return unionArray != nullptr; }
107
108 void shareConstPointer( ConstantUnion *constArray)
109 {
110 if (unionArray == constArray)
111 return;
112
113 delete[] unionArray;
114 unionArray = constArray;
115 }
116
117protected:
118 TType type;
119 bool userType;
120 // we are assuming that Pool Allocator will free the memory allocated to unionArray
121 // when this object is destroyed
122 ConstantUnion *unionArray;
123 TType *arrayInformationType; // this is used for updating maxArraySize in all the references to a given symbol
124};
125
126//
127// The function sub-class of symbols and the parser will need to
128// share this definition of a function parameter.
129//
130struct TParameter
131{
132 TString *name;
133 TType *type;
134};
135
136//
137// The function sub-class of a symbol.
138//
139class TFunction : public TSymbol
140{
141public:
142 TFunction(TOperator o) :
143 TSymbol(0),
144 returnType(TType(EbtVoid, EbpUndefined)),
145 op(o),
146 defined(false),
147 prototypeDeclaration(false) { }
148 TFunction(const TString *name, const TType& retType, TOperator tOp = EOpNull, const char *ext = "") :
149 TSymbol(name),
150 returnType(retType),
151 mangledName(TFunction::mangleName(*name)),
152 op(tOp),
153 extension(ext),
154 defined(false),
155 prototypeDeclaration(false) { }
156 virtual ~TFunction();
157 virtual bool isFunction() const { return true; }
158
159 static TString mangleName(const TString& name) { return name + '('; }
160 static TString unmangleName(const TString& mangledName)
161 {
162 return TString(mangledName.c_str(), mangledName.find_first_of('('));
163 }
164
165 void addParameter(TParameter& p)
166 {
167 parameters.push_back(p);
168 mangledName = mangledName + p.type->getMangledName();
169 }
170
171 const TString& getMangledName() const { return mangledName; }
172 const TType& getReturnType() const { return returnType; }
173
174 TOperator getBuiltInOp() const { return op; }
175 const TString& getExtension() const { return extension; }
176
177 void setDefined() { defined = true; }
178 bool isDefined() { return defined; }
179 void setHasPrototypeDeclaration() { prototypeDeclaration = true; }
180 bool hasPrototypeDeclaration() const { return prototypeDeclaration; }
181
182 size_t getParamCount() const { return parameters.size(); }
183 const TParameter& getParam(int i) const { return parameters[i]; }
184
185protected:
186 typedef TVector<TParameter> TParamList;
187 TParamList parameters;
188 TType returnType;
189 TString mangledName;
190 TOperator op;
191 TString extension;
192 bool defined;
193 bool prototypeDeclaration;
194};
195
196
197class TSymbolTableLevel
198{
199public:
200 typedef TMap<TString, TSymbol*> tLevel;
201 typedef tLevel::const_iterator const_iterator;
202 typedef const tLevel::value_type tLevelPair;
203 typedef std::pair<tLevel::iterator, bool> tInsertResult;
204
205 POOL_ALLOCATOR_NEW_DELETE()
206 TSymbolTableLevel() { }
207 ~TSymbolTableLevel();
208
209 bool insert(TSymbol *symbol);
210
211 // Insert a function using its unmangled name as the key.
212 bool insertUnmangled(TFunction *function);
213
214 TSymbol *find(const TString &name) const;
215
216 static int nextUniqueId()
217 {
218 return ++uniqueId;
219 }
220
221protected:
222 tLevel level;
223 static int uniqueId; // for unique identification in code generation
224};
225
226enum ESymbolLevel
227{
228 COMMON_BUILTINS,
229 ESSL1_BUILTINS,
230 ESSL3_BUILTINS,
231 LAST_BUILTIN_LEVEL = ESSL3_BUILTINS,
232 GLOBAL_LEVEL
233};
234
235inline bool IsGenType(const TType *type)
236{
237 if(type)
238 {
239 TBasicType basicType = type->getBasicType();
240 return basicType == EbtGenType || basicType == EbtGenIType || basicType == EbtGenUType || basicType == EbtGenBType;
241 }
242
243 return false;
244}
245
246inline bool IsVecType(const TType *type)
247{
248 if(type)
249 {
250 TBasicType basicType = type->getBasicType();
251 return basicType == EbtVec || basicType == EbtIVec || basicType == EbtUVec || basicType == EbtBVec;
252 }
253
254 return false;
255}
256
257inline TType *GenType(TType *type, int size)
258{
259 ASSERT(size >= 1 && size <= 4);
260
261 if(!type)
262 {
263 return nullptr;
264 }
265
266 ASSERT(!IsVecType(type));
267
268 switch(type->getBasicType())
269 {
270 case EbtGenType: return new TType(EbtFloat, size);
271 case EbtGenIType: return new TType(EbtInt, size);
272 case EbtGenUType: return new TType(EbtUInt, size);
273 case EbtGenBType: return new TType(EbtBool, size);
274 default: return type;
275 }
276}
277
278inline TType *VecType(TType *type, int size)
279{
280 ASSERT(size >= 2 && size <= 4);
281
282 if(!type)
283 {
284 return nullptr;
285 }
286
287 ASSERT(!IsGenType(type));
288
289 switch(type->getBasicType())
290 {
291 case EbtVec: return new TType(EbtFloat, size);
292 case EbtIVec: return new TType(EbtInt, size);
293 case EbtUVec: return new TType(EbtUInt, size);
294 case EbtBVec: return new TType(EbtBool, size);
295 default: return type;
296 }
297}
298
299class TSymbolTable
300{
301public:
302 TSymbolTable()
303 : mGlobalInvariant(false)
304 {
305 //
306 // The symbol table cannot be used until push() is called, but
307 // the lack of an initial call to push() can be used to detect
308 // that the symbol table has not been preloaded with built-ins.
309 //
310 }
311
312 ~TSymbolTable()
313 {
314 while(currentLevel() > LAST_BUILTIN_LEVEL)
315 {
316 pop();
317 }
318 }
319
320 bool isEmpty() { return table.empty(); }
321 bool atBuiltInLevel() { return currentLevel() <= LAST_BUILTIN_LEVEL; }
322 bool atGlobalLevel() { return currentLevel() <= GLOBAL_LEVEL; }
323 void push()
324 {
325 table.push_back(new TSymbolTableLevel);
326 precisionStack.push_back( PrecisionStackLevel() );
327 }
328
329 void pop()
330 {
331 delete table[currentLevel()];
332 table.pop_back();
333 precisionStack.pop_back();
334 }
335
336 bool declare(TSymbol *symbol)
337 {
338 return insert(currentLevel(), symbol);
339 }
340
341 bool insert(ESymbolLevel level, TSymbol *symbol)
342 {
343 return table[level]->insert(symbol);
344 }
345
346 bool insertConstInt(ESymbolLevel level, const char *name, int value)
347 {
348 TVariable *constant = new TVariable(NewPoolTString(name), TType(EbtInt, EbpUndefined, EvqConstExpr, 1));
349 constant->getConstPointer()->setIConst(value);
350 return insert(level, constant);
351 }
352
353 void insertBuiltIn(ESymbolLevel level, TOperator op, const char *ext, TType *rvalue, const char *name, TType *ptype1, TType *ptype2 = 0, TType *ptype3 = 0, TType *ptype4 = 0, TType *ptype5 = 0)
354 {
355 if(ptype1->getBasicType() == EbtGSampler2D)
356 {
357 insertUnmangledBuiltIn(name);
358 bool gvec4 = (rvalue->getBasicType() == EbtGVec4);
359 insertBuiltIn(level, gvec4 ? new TType(EbtFloat, 4) : rvalue, name, new TType(EbtSampler2D), ptype2, ptype3, ptype4, ptype5);
360 insertBuiltIn(level, gvec4 ? new TType(EbtInt, 4) : rvalue, name, new TType(EbtISampler2D), ptype2, ptype3, ptype4, ptype5);
361 insertBuiltIn(level, gvec4 ? new TType(EbtUInt, 4) : rvalue, name, new TType(EbtUSampler2D), ptype2, ptype3, ptype4, ptype5);
362 }
363 else if(ptype1->getBasicType() == EbtGSampler3D)
364 {
365 insertUnmangledBuiltIn(name);
366 bool gvec4 = (rvalue->getBasicType() == EbtGVec4);
367 insertBuiltIn(level, gvec4 ? new TType(EbtFloat, 4) : rvalue, name, new TType(EbtSampler3D), ptype2, ptype3, ptype4, ptype5);
368 insertBuiltIn(level, gvec4 ? new TType(EbtInt, 4) : rvalue, name, new TType(EbtISampler3D), ptype2, ptype3, ptype4, ptype5);
369 insertBuiltIn(level, gvec4 ? new TType(EbtUInt, 4) : rvalue, name, new TType(EbtUSampler3D), ptype2, ptype3, ptype4, ptype5);
370 }
371 else if(ptype1->getBasicType() == EbtGSamplerCube)
372 {
373 insertUnmangledBuiltIn(name);
374 bool gvec4 = (rvalue->getBasicType() == EbtGVec4);
375 insertBuiltIn(level, gvec4 ? new TType(EbtFloat, 4) : rvalue, name, new TType(EbtSamplerCube), ptype2, ptype3, ptype4, ptype5);
376 insertBuiltIn(level, gvec4 ? new TType(EbtInt, 4) : rvalue, name, new TType(EbtISamplerCube), ptype2, ptype3, ptype4, ptype5);
377 insertBuiltIn(level, gvec4 ? new TType(EbtUInt, 4) : rvalue, name, new TType(EbtUSamplerCube), ptype2, ptype3, ptype4, ptype5);
378 }
379 else if(ptype1->getBasicType() == EbtGSampler2DArray)
380 {
381 insertUnmangledBuiltIn(name);
382 bool gvec4 = (rvalue->getBasicType() == EbtGVec4);
383 insertBuiltIn(level, gvec4 ? new TType(EbtFloat, 4) : rvalue, name, new TType(EbtSampler2DArray), ptype2, ptype3, ptype4, ptype5);
384 insertBuiltIn(level, gvec4 ? new TType(EbtInt, 4) : rvalue, name, new TType(EbtISampler2DArray), ptype2, ptype3, ptype4, ptype5);
385 insertBuiltIn(level, gvec4 ? new TType(EbtUInt, 4) : rvalue, name, new TType(EbtUSampler2DArray), ptype2, ptype3, ptype4, ptype5);
386 }
387 else if(IsGenType(rvalue) || IsGenType(ptype1) || IsGenType(ptype2) || IsGenType(ptype3))
388 {
389 ASSERT(!ptype4);
390 insertUnmangledBuiltIn(name);
391 insertBuiltIn(level, op, ext, GenType(rvalue, 1), name, GenType(ptype1, 1), GenType(ptype2, 1), GenType(ptype3, 1));
392 insertBuiltIn(level, op, ext, GenType(rvalue, 2), name, GenType(ptype1, 2), GenType(ptype2, 2), GenType(ptype3, 2));
393 insertBuiltIn(level, op, ext, GenType(rvalue, 3), name, GenType(ptype1, 3), GenType(ptype2, 3), GenType(ptype3, 3));
394 insertBuiltIn(level, op, ext, GenType(rvalue, 4), name, GenType(ptype1, 4), GenType(ptype2, 4), GenType(ptype3, 4));
395 }
396 else if(IsVecType(rvalue) || IsVecType(ptype1) || IsVecType(ptype2) || IsVecType(ptype3))
397 {
398 ASSERT(!ptype4);
399 insertUnmangledBuiltIn(name);
400 insertBuiltIn(level, op, ext, VecType(rvalue, 2), name, VecType(ptype1, 2), VecType(ptype2, 2), VecType(ptype3, 2));
401 insertBuiltIn(level, op, ext, VecType(rvalue, 3), name, VecType(ptype1, 3), VecType(ptype2, 3), VecType(ptype3, 3));
402 insertBuiltIn(level, op, ext, VecType(rvalue, 4), name, VecType(ptype1, 4), VecType(ptype2, 4), VecType(ptype3, 4));
403 }
404 else
405 {
406 TFunction *function = new TFunction(NewPoolTString(name), *rvalue, op, ext);
407
408 TParameter param1 = {0, ptype1};
409 function->addParameter(param1);
410
411 if(ptype2)
412 {
413 TParameter param2 = {0, ptype2};
414 function->addParameter(param2);
415 }
416
417 if(ptype3)
418 {
419 TParameter param3 = {0, ptype3};
420 function->addParameter(param3);
421 }
422
423 if(ptype4)
424 {
425 TParameter param4 = {0, ptype4};
426 function->addParameter(param4);
427 }
428
429 if(ptype5)
430 {
431 TParameter param5 = {0, ptype5};
432 function->addParameter(param5);
433 }
434
435 ASSERT(hasUnmangledBuiltIn(name));
436 insert(level, function);
437 }
438 }
439
440 void insertBuiltIn(ESymbolLevel level, TOperator op, TType *rvalue, const char *name, TType *ptype1, TType *ptype2 = 0, TType *ptype3 = 0, TType *ptype4 = 0, TType *ptype5 = 0)
441 {
442 insertUnmangledBuiltIn(name);
443 insertBuiltIn(level, op, "", rvalue, name, ptype1, ptype2, ptype3, ptype4, ptype5);
444 }
445
446 void insertBuiltIn(ESymbolLevel level, TType *rvalue, const char *name, TType *ptype1, TType *ptype2 = 0, TType *ptype3 = 0, TType *ptype4 = 0, TType *ptype5 = 0)
447 {
448 insertUnmangledBuiltIn(name);
449 insertBuiltIn(level, EOpNull, rvalue, name, ptype1, ptype2, ptype3, ptype4, ptype5);
450 }
451
452 TSymbol *find(const TString &name, int shaderVersion, bool *builtIn = nullptr, bool *sameScope = nullptr) const;
453 TSymbol *findBuiltIn(const TString &name, int shaderVersion) const;
454
455 TSymbolTableLevel *getOuterLevel() const
456 {
457 assert(currentLevel() >= 1);
458 return table[currentLevel() - 1];
459 }
460
461 bool setDefaultPrecision(const TPublicType &type, TPrecision prec)
462 {
463 if (IsSampler(type.type))
464 return true; // Skip sampler types for the time being
465 if (type.type != EbtFloat && type.type != EbtInt)
466 return false; // Only set default precision for int/float
467 if (type.primarySize > 1 || type.secondarySize > 1 || type.array)
468 return false; // Not allowed to set for aggregate types
469 int indexOfLastElement = static_cast<int>(precisionStack.size()) - 1;
470 precisionStack[indexOfLastElement][type.type] = prec; // Uses map operator [], overwrites the current value
471 return true;
472 }
473
474 // Searches down the precisionStack for a precision qualifier for the specified TBasicType
475 TPrecision getDefaultPrecision( TBasicType type)
476 {
477 // unsigned integers use the same precision as signed
478 if (type == EbtUInt) type = EbtInt;
479
480 if( type != EbtFloat && type != EbtInt ) return EbpUndefined;
481 int level = static_cast<int>(precisionStack.size()) - 1;
482 assert( level >= 0); // Just to be safe. Should not happen.
483 PrecisionStackLevel::iterator it;
484 TPrecision prec = EbpUndefined; // If we dont find anything we return this. Should we error check this?
485 while( level >= 0 ){
486 it = precisionStack[level].find( type );
487 if( it != precisionStack[level].end() ){
488 prec = (*it).second;
489 break;
490 }
491 level--;
492 }
493 return prec;
494 }
495
496 // This records invariant varyings declared through
497 // "invariant varying_name;".
498 void addInvariantVarying(const std::string &originalName)
499 {
500 mInvariantVaryings.insert(originalName);
501 }
502 // If this returns false, the varying could still be invariant
503 // if it is set as invariant during the varying variable
504 // declaration - this piece of information is stored in the
505 // variable's type, not here.
506 bool isVaryingInvariant(const std::string &originalName) const
507 {
508 return (mGlobalInvariant ||
509 mInvariantVaryings.count(originalName) > 0);
510 }
511
512 void setGlobalInvariant() { mGlobalInvariant = true; }
513 bool getGlobalInvariant() const { return mGlobalInvariant; }
514
515 bool hasUnmangledBuiltIn(const char *name) { return mUnmangledBuiltinNames.count(std::string(name)) > 0; }
516
517private:
518 // Used to insert unmangled functions to check redeclaration of built-ins in ESSL 3.00.
519 void insertUnmangledBuiltIn(const char *name) { mUnmangledBuiltinNames.insert(std::string(name)); }
520
521protected:
522 ESymbolLevel currentLevel() const { return static_cast<ESymbolLevel>(table.size() - 1); }
523
524 std::vector<TSymbolTableLevel*> table;
525 typedef std::map< TBasicType, TPrecision > PrecisionStackLevel;
526 std::vector< PrecisionStackLevel > precisionStack;
527
528 std::set<std::string> mUnmangledBuiltinNames;
529
530 std::set<std::string> mInvariantVaryings;
531 bool mGlobalInvariant;
532};
533
534#endif // _SYMBOL_TABLE_INCLUDED_
535