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 symbol.setUniqueId(nextUniqueId()); 212 213 // 214 // returning true means symbol was added to the table 215 // 216 tInsertResult result; 217 result = level.insert(tLevelPair(symbol.getMangledName(), &symbol)); 218 219 return result.second; 220 } 221 222 TSymbol* find(const TString& name) const 223 { 224 tLevel::const_iterator it = level.find(name); 225 if (it == level.end()) 226 return 0; 227 else 228 return (*it).second; 229 } 230 231 static int nextUniqueId() 232 { 233 return ++uniqueId; 234 } 235 236 protected: 237 tLevel level; 238 static int uniqueId; // for unique identification in code generation 239 }; 240 241 enum ESymbolLevel 242 { 243 COMMON_BUILTINS, 244 ESSL1_BUILTINS, 245 ESSL3_BUILTINS, 246 LAST_BUILTIN_LEVEL = ESSL3_BUILTINS, 247 GLOBAL_LEVEL 248 }; 249 250 inline bool IsGenType(const TType *type) 251 { 252 if(type) 253 { 254 TBasicType basicType = type->getBasicType(); 255 return basicType == EbtGenType || basicType == EbtGenIType || basicType == EbtGenUType || basicType == EbtGenBType; 256 } 257 258 return false; 259 } 260 261 inline bool IsVecType(const TType *type) 262 { 263 if(type) 264 { 265 TBasicType basicType = type->getBasicType(); 266 return basicType == EbtVec || basicType == EbtIVec || basicType == EbtUVec || basicType == EbtBVec; 267 } 268 269 return false; 270 } 271 272 inline TType *GenType(TType *type, int size) 273 { 274 ASSERT(size >= 1 && size <= 4); 275 276 if(!type) 277 { 278 return nullptr; 279 } 280 281 ASSERT(!IsVecType(type)); 282 283 switch(type->getBasicType()) 284 { 285 case EbtGenType: return new TType(EbtFloat, size); 286 case EbtGenIType: return new TType(EbtInt, size); 287 case EbtGenUType: return new TType(EbtUInt, size); 288 case EbtGenBType: return new TType(EbtBool, size); 289 default: return type; 290 } 291 } 292 293 inline TType *VecType(TType *type, int size) 294 { 295 ASSERT(size >= 2 && size <= 4); 296 297 if(!type) 298 { 299 return nullptr; 300 } 301 302 ASSERT(!IsGenType(type)); 303 304 switch(type->getBasicType()) 305 { 306 case EbtVec: return new TType(EbtFloat, size); 307 case EbtIVec: return new TType(EbtInt, size); 308 case EbtUVec: return new TType(EbtUInt, size); 309 case EbtBVec: return new TType(EbtBool, size); 310 default: return type; 311 } 312 } 313 314 class TSymbolTable 315 { 316 public: 317 TSymbolTable() 318 : mGlobalInvariant(false) 319 { 320 // 321 // The symbol table cannot be used until push() is called, but 322 // the lack of an initial call to push() can be used to detect 323 // that the symbol table has not been preloaded with built-ins. 324 // 325 } 326 327 ~TSymbolTable() 328 { 329 while(currentLevel() > LAST_BUILTIN_LEVEL) 330 { 331 pop(); 332 } 333 } 334 335 bool isEmpty() { return table.empty(); } 336 bool atBuiltInLevel() { return currentLevel() <= LAST_BUILTIN_LEVEL; } 337 bool atGlobalLevel() { return currentLevel() <= GLOBAL_LEVEL; } 338 void push() 339 { 340 table.push_back(new TSymbolTableLevel); 341 precisionStack.push_back( PrecisionStackLevel() ); 342 } 343 344 void pop() 345 { 346 delete table[currentLevel()]; 347 table.pop_back(); 348 precisionStack.pop_back(); 349 } 350 351 bool declare(TSymbol &symbol) 352 { 353 return insert(currentLevel(), symbol); 354 } 355 356 bool insert(ESymbolLevel level, TSymbol &symbol) 357 { 358 return table[level]->insert(symbol); 359 } 360 361 bool insertConstInt(ESymbolLevel level, const char *name, int value) 362 { 363 TVariable *constant = new TVariable(NewPoolTString(name), TType(EbtInt, EbpUndefined, EvqConstExpr, 1)); 364 constant->getConstPointer()->setIConst(value); 365 return insert(level, *constant); 366 } 367 368 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) 369 { 370 if(ptype1->getBasicType() == EbtGSampler2D) 371 { 372 insertUnmangledBuiltIn(name); 373 bool gvec4 = (rvalue->getBasicType() == EbtGVec4); 374 insertBuiltIn(level, gvec4 ? new TType(EbtFloat, 4) : rvalue, name, new TType(EbtSampler2D), ptype2, ptype3, ptype4, ptype5); 375 insertBuiltIn(level, gvec4 ? new TType(EbtInt, 4) : rvalue, name, new TType(EbtISampler2D), ptype2, ptype3, ptype4, ptype5); 376 insertBuiltIn(level, gvec4 ? new TType(EbtUInt, 4) : rvalue, name, new TType(EbtUSampler2D), ptype2, ptype3, ptype4, ptype5); 377 } 378 else if(ptype1->getBasicType() == EbtGSampler3D) 379 { 380 insertUnmangledBuiltIn(name); 381 bool gvec4 = (rvalue->getBasicType() == EbtGVec4); 382 insertBuiltIn(level, gvec4 ? new TType(EbtFloat, 4) : rvalue, name, new TType(EbtSampler3D), ptype2, ptype3, ptype4, ptype5); 383 insertBuiltIn(level, gvec4 ? new TType(EbtInt, 4) : rvalue, name, new TType(EbtISampler3D), ptype2, ptype3, ptype4, ptype5); 384 insertBuiltIn(level, gvec4 ? new TType(EbtUInt, 4) : rvalue, name, new TType(EbtUSampler3D), ptype2, ptype3, ptype4, ptype5); 385 } 386 else if(ptype1->getBasicType() == EbtGSamplerCube) 387 { 388 insertUnmangledBuiltIn(name); 389 bool gvec4 = (rvalue->getBasicType() == EbtGVec4); 390 insertBuiltIn(level, gvec4 ? new TType(EbtFloat, 4) : rvalue, name, new TType(EbtSamplerCube), ptype2, ptype3, ptype4, ptype5); 391 insertBuiltIn(level, gvec4 ? new TType(EbtInt, 4) : rvalue, name, new TType(EbtISamplerCube), ptype2, ptype3, ptype4, ptype5); 392 insertBuiltIn(level, gvec4 ? new TType(EbtUInt, 4) : rvalue, name, new TType(EbtUSamplerCube), ptype2, ptype3, ptype4, ptype5); 393 } 394 else if(ptype1->getBasicType() == EbtGSampler2DArray) 395 { 396 insertUnmangledBuiltIn(name); 397 bool gvec4 = (rvalue->getBasicType() == EbtGVec4); 398 insertBuiltIn(level, gvec4 ? new TType(EbtFloat, 4) : rvalue, name, new TType(EbtSampler2DArray), ptype2, ptype3, ptype4, ptype5); 399 insertBuiltIn(level, gvec4 ? new TType(EbtInt, 4) : rvalue, name, new TType(EbtISampler2DArray), ptype2, ptype3, ptype4, ptype5); 400 insertBuiltIn(level, gvec4 ? new TType(EbtUInt, 4) : rvalue, name, new TType(EbtUSampler2DArray), ptype2, ptype3, ptype4, ptype5); 401 } 402 else if(IsGenType(rvalue) || IsGenType(ptype1) || IsGenType(ptype2) || IsGenType(ptype3)) 403 { 404 ASSERT(!ptype4); 405 insertUnmangledBuiltIn(name); 406 insertBuiltIn(level, op, ext, GenType(rvalue, 1), name, GenType(ptype1, 1), GenType(ptype2, 1), GenType(ptype3, 1)); 407 insertBuiltIn(level, op, ext, GenType(rvalue, 2), name, GenType(ptype1, 2), GenType(ptype2, 2), GenType(ptype3, 2)); 408 insertBuiltIn(level, op, ext, GenType(rvalue, 3), name, GenType(ptype1, 3), GenType(ptype2, 3), GenType(ptype3, 3)); 409 insertBuiltIn(level, op, ext, GenType(rvalue, 4), name, GenType(ptype1, 4), GenType(ptype2, 4), GenType(ptype3, 4)); 410 } 411 else if(IsVecType(rvalue) || IsVecType(ptype1) || IsVecType(ptype2) || IsVecType(ptype3)) 412 { 413 ASSERT(!ptype4); 414 insertUnmangledBuiltIn(name); 415 insertBuiltIn(level, op, ext, VecType(rvalue, 2), name, VecType(ptype1, 2), VecType(ptype2, 2), VecType(ptype3, 2)); 416 insertBuiltIn(level, op, ext, VecType(rvalue, 3), name, VecType(ptype1, 3), VecType(ptype2, 3), VecType(ptype3, 3)); 417 insertBuiltIn(level, op, ext, VecType(rvalue, 4), name, VecType(ptype1, 4), VecType(ptype2, 4), VecType(ptype3, 4)); 418 } 419 else 420 { 421 TFunction *function = new TFunction(NewPoolTString(name), *rvalue, op, ext); 422 423 TParameter param1 = {0, ptype1}; 424 function->addParameter(param1); 425 426 if(ptype2) 427 { 428 TParameter param2 = {0, ptype2}; 429 function->addParameter(param2); 430 } 431 432 if(ptype3) 433 { 434 TParameter param3 = {0, ptype3}; 435 function->addParameter(param3); 436 } 437 438 if(ptype4) 439 { 440 TParameter param4 = {0, ptype4}; 441 function->addParameter(param4); 442 } 443 444 if(ptype5) 445 { 446 TParameter param5 = {0, ptype5}; 447 function->addParameter(param5); 448 } 449 450 ASSERT(hasUnmangledBuiltIn(name)); 451 insert(level, *function); 452 } 453 } 454 455 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) 456 { 457 insertUnmangledBuiltIn(name); 458 insertBuiltIn(level, op, "", rvalue, name, ptype1, ptype2, ptype3, ptype4, ptype5); 459 } 460 461 void insertBuiltIn(ESymbolLevel level, TType *rvalue, const char *name, TType *ptype1, TType *ptype2 = 0, TType *ptype3 = 0, TType *ptype4 = 0, TType *ptype5 = 0) 462 { 463 insertUnmangledBuiltIn(name); 464 insertBuiltIn(level, EOpNull, rvalue, name, ptype1, ptype2, ptype3, ptype4, ptype5); 465 } 466 467 TSymbol *find(const TString &name, int shaderVersion, bool *builtIn = nullptr, bool *sameScope = nullptr) const; 468 TSymbol *findBuiltIn(const TString &name, int shaderVersion) const; 469 470 TSymbolTableLevel *getOuterLevel() const 471 { 472 assert(currentLevel() >= 1); 473 return table[currentLevel() - 1]; 474 } 475 476 bool setDefaultPrecision(const TPublicType &type, TPrecision prec) 477 { 478 if (IsSampler(type.type)) 479 return true; // Skip sampler types for the time being 480 if (type.type != EbtFloat && type.type != EbtInt) 481 return false; // Only set default precision for int/float 482 if (type.primarySize > 1 || type.secondarySize > 1 || type.array) 483 return false; // Not allowed to set for aggregate types 484 int indexOfLastElement = static_cast<int>(precisionStack.size()) - 1; 485 precisionStack[indexOfLastElement][type.type] = prec; // Uses map operator [], overwrites the current value 486 return true; 487 } 488 489 // Searches down the precisionStack for a precision qualifier for the specified TBasicType 490 TPrecision getDefaultPrecision( TBasicType type) 491 { 492 // unsigned integers use the same precision as signed 493 if (type == EbtUInt) type = EbtInt; 494 495 if( type != EbtFloat && type != EbtInt ) return EbpUndefined; 496 int level = static_cast<int>(precisionStack.size()) - 1; 497 assert( level >= 0); // Just to be safe. Should not happen. 498 PrecisionStackLevel::iterator it; 499 TPrecision prec = EbpUndefined; // If we dont find anything we return this. Should we error check this? 500 while( level >= 0 ){ 501 it = precisionStack[level].find( type ); 502 if( it != precisionStack[level].end() ){ 503 prec = (*it).second; 504 break; 505 } 506 level--; 507 } 508 return prec; 509 } 510 511 // This records invariant varyings declared through 512 // "invariant varying_name;". 513 void addInvariantVarying(const std::string &originalName) 514 { 515 mInvariantVaryings.insert(originalName); 516 } 517 // If this returns false, the varying could still be invariant 518 // if it is set as invariant during the varying variable 519 // declaration - this piece of information is stored in the 520 // variable's type, not here. 521 bool isVaryingInvariant(const std::string &originalName) const 522 { 523 return (mGlobalInvariant || 524 mInvariantVaryings.count(originalName) > 0); 525 } 526 527 void setGlobalInvariant() { mGlobalInvariant = true; } 528 bool getGlobalInvariant() const { return mGlobalInvariant; } 529 530 bool hasUnmangledBuiltIn(const char *name) { return mUnmangledBuiltinNames.count(std::string(name)) > 0; } 531 532 private: 533 // Used to insert unmangled functions to check redeclaration of built-ins in ESSL 3.00. 534 void insertUnmangledBuiltIn(const char *name) { mUnmangledBuiltinNames.insert(std::string(name)); } 535 536 protected: 537 ESymbolLevel currentLevel() const { return static_cast<ESymbolLevel>(table.size() - 1); } 538 539 std::vector<TSymbolTableLevel*> table; 540 typedef std::map< TBasicType, TPrecision > PrecisionStackLevel; 541 std::vector< PrecisionStackLevel > precisionStack; 542 543 std::set<std::string> mUnmangledBuiltinNames; 544 545 std::set<std::string> mInvariantVaryings; 546 bool mGlobalInvariant; 547 }; 548 549 #endif // _SYMBOL_TABLE_INCLUDED_ 550