1 // 2 // Copyright (c) 2002-2014 The ANGLE Project Authors. All rights reserved. 3 // Use of this source code is governed by a BSD-style license that can be 4 // found in the LICENSE file. 5 // 6 7 #ifndef COMPILER_TRANSLATOR_SYMBOLTABLE_H_ 8 #define COMPILER_TRANSLATOR_SYMBOLTABLE_H_ 9 10 // 11 // Symbol table for parsing. Has these design characteristics: 12 // 13 // * Same symbol table can be used to compile many shaders, to preserve 14 // effort of creating and loading with the large numbers of built-in 15 // symbols. 16 // 17 // * Name mangling will be used to give each function a unique name 18 // so that symbol table lookups are never ambiguous. This allows 19 // a simpler symbol table structure. 20 // 21 // * Pushing and popping of scope, so symbol table will really be a stack 22 // of symbol tables. Searched from the top, with new inserts going into 23 // the top. 24 // 25 // * Constants: Compile time constant symbols will keep their values 26 // in the symbol table. The parser can substitute constants at parse 27 // time, including doing constant folding and constant propagation. 28 // 29 // * No temporaries: Temporaries made from operations (+, --, .xy, etc.) 30 // are tracked in the intermediate representation, not the symbol table. 31 // 32 33 #include <array> 34 #include <assert.h> 35 #include <set> 36 37 #include "common/angleutils.h" 38 #include "compiler/translator/ExtensionBehavior.h" 39 #include "compiler/translator/InfoSink.h" 40 #include "compiler/translator/IntermNode.h" 41 #include "compiler/translator/SymbolUniqueId.h" 42 43 namespace sh 44 { 45 46 // Symbol base class. (Can build functions or variables out of these...) 47 class TSymbol : angle::NonCopyable 48 { 49 public: 50 POOL_ALLOCATOR_NEW_DELETE(); 51 TSymbol(TSymbolTable *symbolTable, const TString *n); 52 ~TSymbol()53 virtual ~TSymbol() 54 { 55 // don't delete name, it's from the pool 56 } 57 getName()58 const TString &getName() const { return *name; } getMangledName()59 virtual const TString &getMangledName() const { return getName(); } isFunction()60 virtual bool isFunction() const { return false; } isVariable()61 virtual bool isVariable() const { return false; } getUniqueId()62 const TSymbolUniqueId &getUniqueId() const { return uniqueId; } relateToExtension(TExtension ext)63 void relateToExtension(TExtension ext) { extension = ext; } getExtension()64 TExtension getExtension() const { return extension; } 65 66 private: 67 const TSymbolUniqueId uniqueId; 68 const TString *name; 69 TExtension extension; 70 }; 71 72 // Variable, meaning a symbol that's not a function. 73 // 74 // May store the value of a constant variable of any type (float, int, bool or struct). 75 class TVariable : public TSymbol 76 { 77 public: ~TVariable()78 ~TVariable() override {} isVariable()79 bool isVariable() const override { return true; } getType()80 TType &getType() { return type; } getType()81 const TType &getType() const { return type; } isUserType()82 bool isUserType() const { return userType; } setQualifier(TQualifier qualifier)83 void setQualifier(TQualifier qualifier) { type.setQualifier(qualifier); } 84 getConstPointer()85 const TConstantUnion *getConstPointer() const { return unionArray; } 86 shareConstPointer(const TConstantUnion * constArray)87 void shareConstPointer(const TConstantUnion *constArray) { unionArray = constArray; } 88 89 private: 90 friend class TSymbolTable; 91 92 TVariable(TSymbolTable *symbolTable, 93 const TString *name, 94 const TType &t, 95 bool isUserTypeDefinition = false) TSymbol(symbolTable,name)96 : TSymbol(symbolTable, name), type(t), userType(isUserTypeDefinition), unionArray(0) 97 { 98 } 99 100 TType type; 101 102 // Set to true if this represents a struct type, as opposed to a variable. 103 bool userType; 104 105 // we are assuming that Pool Allocator will free the memory 106 // allocated to unionArray when this object is destroyed. 107 const TConstantUnion *unionArray; 108 }; 109 110 // Immutable version of TParameter. 111 struct TConstParameter 112 { TConstParameterTConstParameter113 TConstParameter() : name(nullptr), type(nullptr) {} TConstParameterTConstParameter114 explicit TConstParameter(const TString *n) : name(n), type(nullptr) {} TConstParameterTConstParameter115 explicit TConstParameter(const TType *t) : name(nullptr), type(t) {} TConstParameterTConstParameter116 TConstParameter(const TString *n, const TType *t) : name(n), type(t) {} 117 118 // Both constructor arguments must be const. 119 TConstParameter(TString *n, TType *t) = delete; 120 TConstParameter(const TString *n, TType *t) = delete; 121 TConstParameter(TString *n, const TType *t) = delete; 122 123 const TString *const name; 124 const TType *const type; 125 }; 126 127 // The function sub-class of symbols and the parser will need to 128 // share this definition of a function parameter. 129 struct TParameter 130 { 131 // Destructively converts to TConstParameter. 132 // This method resets name and type to nullptrs to make sure 133 // their content cannot be modified after the call. turnToConstTParameter134 TConstParameter turnToConst() 135 { 136 const TString *constName = name; 137 const TType *constType = type; 138 name = nullptr; 139 type = nullptr; 140 return TConstParameter(constName, constType); 141 } 142 143 const TString *name; 144 TType *type; 145 }; 146 147 // The function sub-class of a symbol. 148 class TFunction : public TSymbol 149 { 150 public: 151 TFunction(TSymbolTable *symbolTable, 152 const TString *name, 153 const TType *retType, 154 TOperator tOp = EOpNull, 155 TExtension ext = TExtension::UNDEFINED) TSymbol(symbolTable,name)156 : TSymbol(symbolTable, name), 157 returnType(retType), 158 mangledName(nullptr), 159 op(tOp), 160 defined(false), 161 mHasPrototypeDeclaration(false) 162 { 163 relateToExtension(ext); 164 } 165 ~TFunction() override; isFunction()166 bool isFunction() const override { return true; } 167 addParameter(const TConstParameter & p)168 void addParameter(const TConstParameter &p) 169 { 170 parameters.push_back(p); 171 mangledName = nullptr; 172 } 173 174 void swapParameters(const TFunction ¶metersSource); 175 getMangledName()176 const TString &getMangledName() const override 177 { 178 if (mangledName == nullptr) 179 { 180 mangledName = buildMangledName(); 181 } 182 return *mangledName; 183 } 184 185 static const TString &GetMangledNameFromCall(const TString &functionName, 186 const TIntermSequence &arguments); 187 getReturnType()188 const TType &getReturnType() const { return *returnType; } 189 getBuiltInOp()190 TOperator getBuiltInOp() const { return op; } 191 setDefined()192 void setDefined() { defined = true; } isDefined()193 bool isDefined() { return defined; } setHasPrototypeDeclaration()194 void setHasPrototypeDeclaration() { mHasPrototypeDeclaration = true; } hasPrototypeDeclaration()195 bool hasPrototypeDeclaration() const { return mHasPrototypeDeclaration; } 196 getParamCount()197 size_t getParamCount() const { return parameters.size(); } getParam(size_t i)198 const TConstParameter &getParam(size_t i) const { return parameters[i]; } 199 200 private: 201 void clearParameters(); 202 203 const TString *buildMangledName() const; 204 205 typedef TVector<TConstParameter> TParamList; 206 TParamList parameters; 207 const TType *returnType; 208 mutable const TString *mangledName; 209 TOperator op; 210 bool defined; 211 bool mHasPrototypeDeclaration; 212 }; 213 214 // Interface block name sub-symbol 215 class TInterfaceBlockName : public TSymbol 216 { 217 public: ~TInterfaceBlockName()218 virtual ~TInterfaceBlockName() {} 219 220 private: 221 friend class TSymbolTable; TInterfaceBlockName(TSymbolTable * symbolTable,const TString * name)222 TInterfaceBlockName(TSymbolTable *symbolTable, const TString *name) : TSymbol(symbolTable, name) 223 { 224 } 225 }; 226 227 class TSymbolTableLevel 228 { 229 public: 230 typedef TUnorderedMap<TString, TSymbol *> tLevel; 231 typedef tLevel::const_iterator const_iterator; 232 typedef const tLevel::value_type tLevelPair; 233 typedef std::pair<tLevel::iterator, bool> tInsertResult; 234 TSymbolTableLevel()235 TSymbolTableLevel() : mGlobalInvariant(false) {} 236 ~TSymbolTableLevel(); 237 238 bool insert(TSymbol *symbol); 239 240 // Insert a function using its unmangled name as the key. 241 bool insertUnmangled(TFunction *function); 242 243 TSymbol *find(const TString &name) const; 244 addInvariantVarying(const std::string & name)245 void addInvariantVarying(const std::string &name) { mInvariantVaryings.insert(name); } 246 isVaryingInvariant(const std::string & name)247 bool isVaryingInvariant(const std::string &name) 248 { 249 return (mGlobalInvariant || mInvariantVaryings.count(name) > 0); 250 } 251 setGlobalInvariant(bool invariant)252 void setGlobalInvariant(bool invariant) { mGlobalInvariant = invariant; } 253 insertUnmangledBuiltInName(const std::string & name)254 void insertUnmangledBuiltInName(const std::string &name) 255 { 256 mUnmangledBuiltInNames.insert(name); 257 } 258 hasUnmangledBuiltIn(const std::string & name)259 bool hasUnmangledBuiltIn(const std::string &name) 260 { 261 return mUnmangledBuiltInNames.count(name) > 0; 262 } 263 264 protected: 265 tLevel level; 266 std::set<std::string> mInvariantVaryings; 267 bool mGlobalInvariant; 268 269 private: 270 std::set<std::string> mUnmangledBuiltInNames; 271 }; 272 273 // Define ESymbolLevel as int rather than an enum since level can go 274 // above GLOBAL_LEVEL and cause atBuiltInLevel() to fail if the 275 // compiler optimizes the >= of the last element to ==. 276 typedef int ESymbolLevel; 277 const int COMMON_BUILTINS = 0; 278 const int ESSL1_BUILTINS = 1; 279 const int ESSL3_BUILTINS = 2; 280 const int ESSL3_1_BUILTINS = 3; 281 // GLSL_BUILTINS are desktop GLSL builtins that don't exist in ESSL but are used to implement 282 // features in ANGLE's GLSL backend. They're not visible to the parser. 283 const int GLSL_BUILTINS = 4; 284 const int LAST_BUILTIN_LEVEL = GLSL_BUILTINS; 285 const int GLOBAL_LEVEL = 5; 286 287 class TSymbolTable : angle::NonCopyable 288 { 289 public: TSymbolTable()290 TSymbolTable() : mUniqueIdCounter(0), mEmptySymbolId(this) 291 { 292 // The symbol table cannot be used until push() is called, but 293 // the lack of an initial call to push() can be used to detect 294 // that the symbol table has not been preloaded with built-ins. 295 } 296 297 ~TSymbolTable(); 298 299 // When the symbol table is initialized with the built-ins, there should 300 // 'push' calls, so that built-ins are at level 0 and the shader 301 // globals are at level 1. isEmpty()302 bool isEmpty() const { return table.empty(); } atBuiltInLevel()303 bool atBuiltInLevel() const { return currentLevel() <= LAST_BUILTIN_LEVEL; } atGlobalLevel()304 bool atGlobalLevel() const { return currentLevel() == GLOBAL_LEVEL; } push()305 void push() 306 { 307 table.push_back(new TSymbolTableLevel); 308 precisionStack.push_back(new PrecisionStackLevel); 309 } 310 pop()311 void pop() 312 { 313 delete table.back(); 314 table.pop_back(); 315 316 delete precisionStack.back(); 317 precisionStack.pop_back(); 318 } 319 320 // The declare* entry points are used when parsing and declare symbols at the current scope. 321 // They return the created symbol in case the declaration was successful, and nullptr if the 322 // declaration failed due to redefinition. 323 TVariable *declareVariable(const TString *name, const TType &type); 324 TVariable *declareStructType(TStructure *str); 325 TInterfaceBlockName *declareInterfaceBlockName(const TString *name); 326 327 // The insert* entry points are used when initializing the symbol table with built-ins. 328 // They return the created symbol in case the declaration was successful, and nullptr if the 329 // declaration failed due to redefinition. 330 TVariable *insertVariable(ESymbolLevel level, const char *name, const TType &type); 331 TVariable *insertVariableExt(ESymbolLevel level, 332 TExtension ext, 333 const char *name, 334 const TType &type); 335 TVariable *insertStructType(ESymbolLevel level, TStructure *str); 336 TInterfaceBlockName *insertInterfaceBlockNameExt(ESymbolLevel level, 337 TExtension ext, 338 const TString *name); 339 insertConstInt(ESymbolLevel level,const char * name,int value,TPrecision precision)340 bool insertConstInt(ESymbolLevel level, const char *name, int value, TPrecision precision) 341 { 342 TVariable *constant = 343 new TVariable(this, NewPoolTString(name), TType(EbtInt, precision, EvqConst, 1)); 344 TConstantUnion *unionArray = new TConstantUnion[1]; 345 unionArray[0].setIConst(value); 346 constant->shareConstPointer(unionArray); 347 return insert(level, constant); 348 } 349 insertConstIntExt(ESymbolLevel level,TExtension ext,const char * name,int value,TPrecision precision)350 bool insertConstIntExt(ESymbolLevel level, 351 TExtension ext, 352 const char *name, 353 int value, 354 TPrecision precision) 355 { 356 TVariable *constant = 357 new TVariable(this, NewPoolTString(name), TType(EbtInt, precision, EvqConst, 1)); 358 TConstantUnion *unionArray = new TConstantUnion[1]; 359 unionArray[0].setIConst(value); 360 constant->shareConstPointer(unionArray); 361 return insert(level, ext, constant); 362 } 363 insertConstIvec3(ESymbolLevel level,const char * name,const std::array<int,3> & values,TPrecision precision)364 bool insertConstIvec3(ESymbolLevel level, 365 const char *name, 366 const std::array<int, 3> &values, 367 TPrecision precision) 368 { 369 TVariable *constantIvec3 = 370 new TVariable(this, NewPoolTString(name), TType(EbtInt, precision, EvqConst, 3)); 371 372 TConstantUnion *unionArray = new TConstantUnion[3]; 373 for (size_t index = 0u; index < 3u; ++index) 374 { 375 unionArray[index].setIConst(values[index]); 376 } 377 constantIvec3->shareConstPointer(unionArray); 378 379 return insert(level, constantIvec3); 380 } 381 382 void insertBuiltIn(ESymbolLevel level, 383 TOperator op, 384 TExtension ext, 385 const TType *rvalue, 386 const char *name, 387 const TType *ptype1, 388 const TType *ptype2 = 0, 389 const TType *ptype3 = 0, 390 const TType *ptype4 = 0, 391 const TType *ptype5 = 0); 392 393 void insertBuiltIn(ESymbolLevel level, 394 const TType *rvalue, 395 const char *name, 396 const TType *ptype1, 397 const TType *ptype2 = 0, 398 const TType *ptype3 = 0, 399 const TType *ptype4 = 0, 400 const TType *ptype5 = 0) 401 { 402 insertUnmangledBuiltInName(name, level); 403 insertBuiltIn(level, EOpNull, TExtension::UNDEFINED, rvalue, name, ptype1, ptype2, ptype3, 404 ptype4, ptype5); 405 } 406 407 void insertBuiltIn(ESymbolLevel level, 408 TExtension ext, 409 const TType *rvalue, 410 const char *name, 411 const TType *ptype1, 412 const TType *ptype2 = 0, 413 const TType *ptype3 = 0, 414 const TType *ptype4 = 0, 415 const TType *ptype5 = 0) 416 { 417 insertUnmangledBuiltInName(name, level); 418 insertBuiltIn(level, EOpNull, ext, rvalue, name, ptype1, ptype2, ptype3, ptype4, ptype5); 419 } 420 421 void insertBuiltInOp(ESymbolLevel level, 422 TOperator op, 423 const TType *rvalue, 424 const TType *ptype1, 425 const TType *ptype2 = 0, 426 const TType *ptype3 = 0, 427 const TType *ptype4 = 0, 428 const TType *ptype5 = 0); 429 430 void insertBuiltInOp(ESymbolLevel level, 431 TOperator op, 432 TExtension ext, 433 const TType *rvalue, 434 const TType *ptype1, 435 const TType *ptype2 = 0, 436 const TType *ptype3 = 0, 437 const TType *ptype4 = 0, 438 const TType *ptype5 = 0); 439 440 void insertBuiltInFunctionNoParameters(ESymbolLevel level, 441 TOperator op, 442 const TType *rvalue, 443 const char *name); 444 445 void insertBuiltInFunctionNoParametersExt(ESymbolLevel level, 446 TExtension ext, 447 TOperator op, 448 const TType *rvalue, 449 const char *name); 450 451 TSymbol *find(const TString &name, 452 int shaderVersion, 453 bool *builtIn = nullptr, 454 bool *sameScope = nullptr) const; 455 456 TSymbol *findGlobal(const TString &name) const; 457 458 TSymbol *findBuiltIn(const TString &name, int shaderVersion) const; 459 460 TSymbol *findBuiltIn(const TString &name, int shaderVersion, bool includeGLSLBuiltins) const; 461 getOuterLevel()462 TSymbolTableLevel *getOuterLevel() 463 { 464 assert(currentLevel() >= 1); 465 return table[currentLevel() - 1]; 466 } 467 setDefaultPrecision(TBasicType type,TPrecision prec)468 void setDefaultPrecision(TBasicType type, TPrecision prec) 469 { 470 int indexOfLastElement = static_cast<int>(precisionStack.size()) - 1; 471 // Uses map operator [], overwrites the current value 472 (*precisionStack[indexOfLastElement])[type] = prec; 473 } 474 475 // Searches down the precisionStack for a precision qualifier 476 // for the specified TBasicType 477 TPrecision getDefaultPrecision(TBasicType type) const; 478 479 // This records invariant varyings declared through 480 // "invariant varying_name;". addInvariantVarying(const std::string & originalName)481 void addInvariantVarying(const std::string &originalName) 482 { 483 ASSERT(atGlobalLevel()); 484 table[currentLevel()]->addInvariantVarying(originalName); 485 } 486 // If this returns false, the varying could still be invariant 487 // if it is set as invariant during the varying variable 488 // declaration - this piece of information is stored in the 489 // variable's type, not here. isVaryingInvariant(const std::string & originalName)490 bool isVaryingInvariant(const std::string &originalName) const 491 { 492 ASSERT(atGlobalLevel()); 493 return table[currentLevel()]->isVaryingInvariant(originalName); 494 } 495 setGlobalInvariant(bool invariant)496 void setGlobalInvariant(bool invariant) 497 { 498 ASSERT(atGlobalLevel()); 499 table[currentLevel()]->setGlobalInvariant(invariant); 500 } 501 nextUniqueId()502 const TSymbolUniqueId nextUniqueId() { return TSymbolUniqueId(this); } 503 504 // The empty symbol id is shared between all empty string ("") symbols. They are used in the 505 // AST for unused function parameters and struct type declarations that don't declare a 506 // variable, for example. getEmptySymbolId()507 const TSymbolUniqueId &getEmptySymbolId() { return mEmptySymbolId; } 508 509 // Checks whether there is a built-in accessible by a shader with the specified version. 510 bool hasUnmangledBuiltInForShaderVersion(const char *name, int shaderVersion); 511 512 private: 513 friend class TSymbolUniqueId; nextUniqueIdValue()514 int nextUniqueIdValue() { return ++mUniqueIdCounter; } 515 currentLevel()516 ESymbolLevel currentLevel() const { return static_cast<ESymbolLevel>(table.size() - 1); } 517 518 TVariable *insertVariable(ESymbolLevel level, const TString *name, const TType &type); 519 insert(ESymbolLevel level,TSymbol * symbol)520 bool insert(ESymbolLevel level, TSymbol *symbol) { return table[level]->insert(symbol); } 521 insert(ESymbolLevel level,TExtension ext,TSymbol * symbol)522 bool insert(ESymbolLevel level, TExtension ext, TSymbol *symbol) 523 { 524 symbol->relateToExtension(ext); 525 return table[level]->insert(symbol); 526 } 527 528 // Used to insert unmangled functions to check redeclaration of built-ins in ESSL 3.00 and 529 // above. 530 void insertUnmangledBuiltInName(const char *name, ESymbolLevel level); 531 532 bool hasUnmangledBuiltInAtLevel(const char *name, ESymbolLevel level); 533 534 std::vector<TSymbolTableLevel *> table; 535 typedef TMap<TBasicType, TPrecision> PrecisionStackLevel; 536 std::vector<PrecisionStackLevel *> precisionStack; 537 538 int mUniqueIdCounter; 539 540 const TSymbolUniqueId mEmptySymbolId; 541 }; 542 543 } // namespace sh 544 545 #endif // COMPILER_TRANSLATOR_SYMBOLTABLE_H_ 546