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 #ifndef __ANDROID__ 42 #include <assert.h> 43 #else 44 #include "../../Common/DebugAndroid.hpp" 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
