Home | History | Annotate | Download | only in compiler
      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)
     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 //
     54 class TSymbol
     55 {
     56 public:
     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 
     69 protected:
     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 //
     84 class TVariable : public TSymbol
     85 {
     86 public:
     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 
    117 protected:
    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 //
    130 struct TParameter
    131 {
    132 	TString *name;
    133 	TType *type;
    134 };
    135 
    136 //
    137 // The function sub-class of a symbol.
    138 //
    139 class TFunction : public TSymbol
    140 {
    141 public:
    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 
    185 protected:
    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 
    197 class TSymbolTableLevel
    198 {
    199 public:
    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 
    221 protected:
    222 	tLevel level;
    223 	static int uniqueId;     // for unique identification in code generation
    224 };
    225 
    226 enum ESymbolLevel
    227 {
    228 	COMMON_BUILTINS,
    229 	ESSL1_BUILTINS,
    230 	ESSL3_BUILTINS,
    231 	LAST_BUILTIN_LEVEL = ESSL3_BUILTINS,
    232 	GLOBAL_LEVEL
    233 };
    234 
    235 inline 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 
    246 inline 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 
    257 inline 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 
    278 inline 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 
    299 class TSymbolTable
    300 {
    301 public:
    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 
    517 private:
    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 
    521 protected:
    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