1 // 2 // Copyright (c) 2002-2013 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 // 8 // Definition of the in-memory high-level intermediate representation 9 // of shaders. This is a tree that parser creates. 10 // 11 // Nodes in the tree are defined as a hierarchy of classes derived from 12 // TIntermNode. Each is a node in a tree. There is no preset branching factor; 13 // each node can have it's own type of list of children. 14 // 15 16 #ifndef __INTERMEDIATE_H 17 #define __INTERMEDIATE_H 18 19 #include "GLSLANG/ShaderLang.h" 20 21 #include <algorithm> 22 #include "compiler/Common.h" 23 #include "compiler/Types.h" 24 #include "compiler/ConstantUnion.h" 25 26 // 27 // Operators used by the high-level (parse tree) representation. 28 // 29 enum TOperator { 30 EOpNull, // if in a node, should only mean a node is still being built 31 EOpSequence, // denotes a list of statements, or parameters, etc. 32 EOpFunctionCall, 33 EOpFunction, // For function definition 34 EOpParameters, // an aggregate listing the parameters to a function 35 36 EOpDeclaration, 37 EOpPrototype, 38 39 // 40 // Unary operators 41 // 42 43 EOpNegative, 44 EOpLogicalNot, 45 EOpVectorLogicalNot, 46 47 EOpPostIncrement, 48 EOpPostDecrement, 49 EOpPreIncrement, 50 EOpPreDecrement, 51 52 EOpConvIntToBool, 53 EOpConvFloatToBool, 54 EOpConvBoolToFloat, 55 EOpConvIntToFloat, 56 EOpConvFloatToInt, 57 EOpConvBoolToInt, 58 59 // 60 // binary operations 61 // 62 63 EOpAdd, 64 EOpSub, 65 EOpMul, 66 EOpDiv, 67 EOpEqual, 68 EOpNotEqual, 69 EOpVectorEqual, 70 EOpVectorNotEqual, 71 EOpLessThan, 72 EOpGreaterThan, 73 EOpLessThanEqual, 74 EOpGreaterThanEqual, 75 EOpComma, 76 77 EOpVectorTimesScalar, 78 EOpVectorTimesMatrix, 79 EOpMatrixTimesVector, 80 EOpMatrixTimesScalar, 81 82 EOpLogicalOr, 83 EOpLogicalXor, 84 EOpLogicalAnd, 85 86 EOpIndexDirect, 87 EOpIndexIndirect, 88 EOpIndexDirectStruct, 89 90 EOpVectorSwizzle, 91 92 // 93 // Built-in functions potentially mapped to operators 94 // 95 96 EOpRadians, 97 EOpDegrees, 98 EOpSin, 99 EOpCos, 100 EOpTan, 101 EOpAsin, 102 EOpAcos, 103 EOpAtan, 104 105 EOpPow, 106 EOpExp, 107 EOpLog, 108 EOpExp2, 109 EOpLog2, 110 EOpSqrt, 111 EOpInverseSqrt, 112 113 EOpAbs, 114 EOpSign, 115 EOpFloor, 116 EOpCeil, 117 EOpFract, 118 EOpMod, 119 EOpMin, 120 EOpMax, 121 EOpClamp, 122 EOpMix, 123 EOpStep, 124 EOpSmoothStep, 125 126 EOpLength, 127 EOpDistance, 128 EOpDot, 129 EOpCross, 130 EOpNormalize, 131 EOpFaceForward, 132 EOpReflect, 133 EOpRefract, 134 135 EOpDFdx, // Fragment only, OES_standard_derivatives extension 136 EOpDFdy, // Fragment only, OES_standard_derivatives extension 137 EOpFwidth, // Fragment only, OES_standard_derivatives extension 138 139 EOpMatrixTimesMatrix, 140 141 EOpAny, 142 EOpAll, 143 144 // 145 // Branch 146 // 147 148 EOpKill, // Fragment only 149 EOpReturn, 150 EOpBreak, 151 EOpContinue, 152 153 // 154 // Constructors 155 // 156 157 EOpConstructInt, 158 EOpConstructBool, 159 EOpConstructFloat, 160 EOpConstructVec2, 161 EOpConstructVec3, 162 EOpConstructVec4, 163 EOpConstructBVec2, 164 EOpConstructBVec3, 165 EOpConstructBVec4, 166 EOpConstructIVec2, 167 EOpConstructIVec3, 168 EOpConstructIVec4, 169 EOpConstructMat2, 170 EOpConstructMat3, 171 EOpConstructMat4, 172 EOpConstructStruct, 173 174 // 175 // moves 176 // 177 178 EOpAssign, 179 EOpInitialize, 180 EOpAddAssign, 181 EOpSubAssign, 182 EOpMulAssign, 183 EOpVectorTimesMatrixAssign, 184 EOpVectorTimesScalarAssign, 185 EOpMatrixTimesScalarAssign, 186 EOpMatrixTimesMatrixAssign, 187 EOpDivAssign 188 }; 189 190 extern const char* getOperatorString(TOperator op); 191 192 class TIntermTraverser; 193 class TIntermAggregate; 194 class TIntermBinary; 195 class TIntermUnary; 196 class TIntermConstantUnion; 197 class TIntermSelection; 198 class TIntermTyped; 199 class TIntermSymbol; 200 class TIntermLoop; 201 class TInfoSink; 202 203 // 204 // Base class for the tree nodes 205 // 206 class TIntermNode { 207 public: 208 POOL_ALLOCATOR_NEW_DELETE(); 209 TIntermNode() { 210 // TODO: Move this to TSourceLoc constructor 211 // after getting rid of TPublicType. 212 line.first_file = line.last_file = 0; 213 line.first_line = line.last_line = 0; 214 } 215 virtual ~TIntermNode() { } 216 217 const TSourceLoc& getLine() const { return line; } 218 void setLine(const TSourceLoc& l) { line = l; } 219 220 virtual void traverse(TIntermTraverser*) = 0; 221 virtual TIntermTyped* getAsTyped() { return 0; } 222 virtual TIntermConstantUnion* getAsConstantUnion() { return 0; } 223 virtual TIntermAggregate* getAsAggregate() { return 0; } 224 virtual TIntermBinary* getAsBinaryNode() { return 0; } 225 virtual TIntermUnary* getAsUnaryNode() { return 0; } 226 virtual TIntermSelection* getAsSelectionNode() { return 0; } 227 virtual TIntermSymbol* getAsSymbolNode() { return 0; } 228 virtual TIntermLoop* getAsLoopNode() { return 0; } 229 230 // Replace a child node. Return true if |original| is a child 231 // node and it is replaced; otherwise, return false. 232 virtual bool replaceChildNode( 233 TIntermNode *original, TIntermNode *replacement) = 0; 234 235 protected: 236 TSourceLoc line; 237 }; 238 239 // 240 // This is just to help yacc. 241 // 242 struct TIntermNodePair { 243 TIntermNode* node1; 244 TIntermNode* node2; 245 }; 246 247 // 248 // Intermediate class for nodes that have a type. 249 // 250 class TIntermTyped : public TIntermNode { 251 public: 252 TIntermTyped(const TType& t) : type(t) { } 253 virtual TIntermTyped* getAsTyped() { return this; } 254 255 virtual bool hasSideEffects() const = 0; 256 257 void setType(const TType& t) { type = t; } 258 const TType& getType() const { return type; } 259 TType* getTypePointer() { return &type; } 260 261 TBasicType getBasicType() const { return type.getBasicType(); } 262 TQualifier getQualifier() const { return type.getQualifier(); } 263 TPrecision getPrecision() const { return type.getPrecision(); } 264 int getNominalSize() const { return type.getNominalSize(); } 265 266 bool isMatrix() const { return type.isMatrix(); } 267 bool isArray() const { return type.isArray(); } 268 bool isVector() const { return type.isVector(); } 269 bool isScalar() const { return type.isScalar(); } 270 const char* getBasicString() const { return type.getBasicString(); } 271 const char* getQualifierString() const { return type.getQualifierString(); } 272 TString getCompleteString() const { return type.getCompleteString(); } 273 274 int totalRegisterCount() const { return type.totalRegisterCount(); } 275 int elementRegisterCount() const { return type.elementRegisterCount(); } 276 int getArraySize() const { return type.getArraySize(); } 277 278 protected: 279 TType type; 280 }; 281 282 // 283 // Handle for, do-while, and while loops. 284 // 285 enum TLoopType { 286 ELoopFor, 287 ELoopWhile, 288 ELoopDoWhile 289 }; 290 291 class TIntermLoop : public TIntermNode { 292 public: 293 TIntermLoop(TLoopType aType, 294 TIntermNode *aInit, TIntermTyped* aCond, TIntermTyped* aExpr, 295 TIntermNode* aBody) : 296 type(aType), 297 init(aInit), 298 cond(aCond), 299 expr(aExpr), 300 body(aBody), 301 unrollFlag(false) { } 302 303 virtual TIntermLoop* getAsLoopNode() { return this; } 304 virtual void traverse(TIntermTraverser*); 305 virtual bool replaceChildNode( 306 TIntermNode *original, TIntermNode *replacement); 307 308 TLoopType getType() const { return type; } 309 TIntermNode* getInit() { return init; } 310 TIntermTyped* getCondition() { return cond; } 311 TIntermTyped* getExpression() { return expr; } 312 TIntermNode* getBody() { return body; } 313 314 void setUnrollFlag(bool flag) { unrollFlag = flag; } 315 bool getUnrollFlag() { return unrollFlag; } 316 317 protected: 318 TLoopType type; 319 TIntermNode* init; // for-loop initialization 320 TIntermTyped* cond; // loop exit condition 321 TIntermTyped* expr; // for-loop expression 322 TIntermNode* body; // loop body 323 324 bool unrollFlag; // Whether the loop should be unrolled or not. 325 }; 326 327 // 328 // Handle break, continue, return, and kill. 329 // 330 class TIntermBranch : public TIntermNode { 331 public: 332 TIntermBranch(TOperator op, TIntermTyped* e) : 333 flowOp(op), 334 expression(e) { } 335 336 virtual void traverse(TIntermTraverser*); 337 virtual bool replaceChildNode( 338 TIntermNode *original, TIntermNode *replacement); 339 340 TOperator getFlowOp() { return flowOp; } 341 TIntermTyped* getExpression() { return expression; } 342 343 protected: 344 TOperator flowOp; 345 TIntermTyped* expression; // non-zero except for "return exp;" statements 346 }; 347 348 // 349 // Nodes that correspond to symbols or constants in the source code. 350 // 351 class TIntermSymbol : public TIntermTyped { 352 public: 353 // if symbol is initialized as symbol(sym), the memory comes from the poolallocator of sym. If sym comes from 354 // per process globalpoolallocator, then it causes increased memory usage per compile 355 // it is essential to use "symbol = sym" to assign to symbol 356 TIntermSymbol(int i, const TString& sym, const TType& t) : 357 TIntermTyped(t), id(i) { symbol = sym; originalSymbol = sym; } 358 359 virtual bool hasSideEffects() const { return false; } 360 361 int getId() const { return id; } 362 const TString& getSymbol() const { return symbol; } 363 364 void setId(int newId) { id = newId; } 365 void setSymbol(const TString& sym) { symbol = sym; } 366 367 const TString& getOriginalSymbol() const { return originalSymbol; } 368 369 virtual void traverse(TIntermTraverser*); 370 virtual TIntermSymbol* getAsSymbolNode() { return this; } 371 virtual bool replaceChildNode(TIntermNode *, TIntermNode *) { return false; } 372 373 protected: 374 int id; 375 TString symbol; 376 TString originalSymbol; 377 }; 378 379 class TIntermConstantUnion : public TIntermTyped { 380 public: 381 TIntermConstantUnion(ConstantUnion *unionPointer, const TType& t) : TIntermTyped(t), unionArrayPointer(unionPointer) { } 382 383 virtual bool hasSideEffects() const { return false; } 384 385 ConstantUnion* getUnionArrayPointer() const { return unionArrayPointer; } 386 387 int getIConst(size_t index) const { return unionArrayPointer ? unionArrayPointer[index].getIConst() : 0; } 388 float getFConst(size_t index) const { return unionArrayPointer ? unionArrayPointer[index].getFConst() : 0.0f; } 389 bool getBConst(size_t index) const { return unionArrayPointer ? unionArrayPointer[index].getBConst() : false; } 390 391 virtual TIntermConstantUnion* getAsConstantUnion() { return this; } 392 virtual void traverse(TIntermTraverser*); 393 virtual bool replaceChildNode(TIntermNode *, TIntermNode *) { return false; } 394 395 TIntermTyped* fold(TOperator, TIntermTyped*, TInfoSink&); 396 397 protected: 398 ConstantUnion *unionArrayPointer; 399 }; 400 401 // 402 // Intermediate class for node types that hold operators. 403 // 404 class TIntermOperator : public TIntermTyped { 405 public: 406 TOperator getOp() const { return op; } 407 void setOp(TOperator o) { op = o; } 408 409 bool isAssignment() const; 410 bool isConstructor() const; 411 412 virtual bool hasSideEffects() const { return isAssignment(); } 413 414 protected: 415 TIntermOperator(TOperator o) : TIntermTyped(TType(EbtFloat, EbpUndefined)), op(o) {} 416 TIntermOperator(TOperator o, TType& t) : TIntermTyped(t), op(o) {} 417 TOperator op; 418 }; 419 420 // 421 // Nodes for all the basic binary math operators. 422 // 423 class TIntermBinary : public TIntermOperator { 424 public: 425 TIntermBinary(TOperator o) : TIntermOperator(o), addIndexClamp(false) {} 426 427 virtual TIntermBinary* getAsBinaryNode() { return this; } 428 virtual void traverse(TIntermTraverser*); 429 virtual bool replaceChildNode( 430 TIntermNode *original, TIntermNode *replacement); 431 432 virtual bool hasSideEffects() const { return (isAssignment() || left->hasSideEffects() || right->hasSideEffects()); } 433 434 void setLeft(TIntermTyped* n) { left = n; } 435 void setRight(TIntermTyped* n) { right = n; } 436 TIntermTyped* getLeft() const { return left; } 437 TIntermTyped* getRight() const { return right; } 438 bool promote(TInfoSink&); 439 440 void setAddIndexClamp() { addIndexClamp = true; } 441 bool getAddIndexClamp() { return addIndexClamp; } 442 443 protected: 444 TIntermTyped* left; 445 TIntermTyped* right; 446 447 // If set to true, wrap any EOpIndexIndirect with a clamp to bounds. 448 bool addIndexClamp; 449 }; 450 451 // 452 // Nodes for unary math operators. 453 // 454 class TIntermUnary : public TIntermOperator { 455 public: 456 TIntermUnary(TOperator o, TType& t) : TIntermOperator(o, t), operand(0), useEmulatedFunction(false) {} 457 TIntermUnary(TOperator o) : TIntermOperator(o), operand(0), useEmulatedFunction(false) {} 458 459 virtual void traverse(TIntermTraverser*); 460 virtual TIntermUnary* getAsUnaryNode() { return this; } 461 virtual bool replaceChildNode( 462 TIntermNode *original, TIntermNode *replacement); 463 464 virtual bool hasSideEffects() const { return (isAssignment() || operand->hasSideEffects()); } 465 466 void setOperand(TIntermTyped* o) { operand = o; } 467 TIntermTyped* getOperand() { return operand; } 468 bool promote(TInfoSink&); 469 470 void setUseEmulatedFunction() { useEmulatedFunction = true; } 471 bool getUseEmulatedFunction() { return useEmulatedFunction; } 472 473 protected: 474 TIntermTyped* operand; 475 476 // If set to true, replace the built-in function call with an emulated one 477 // to work around driver bugs. 478 bool useEmulatedFunction; 479 }; 480 481 typedef TVector<TIntermNode*> TIntermSequence; 482 typedef TVector<int> TQualifierList; 483 484 // 485 // Nodes that operate on an arbitrary sized set of children. 486 // 487 class TIntermAggregate : public TIntermOperator { 488 public: 489 TIntermAggregate() : TIntermOperator(EOpNull), userDefined(false), useEmulatedFunction(false) { } 490 TIntermAggregate(TOperator o) : TIntermOperator(o), useEmulatedFunction(false) { } 491 ~TIntermAggregate() { } 492 493 virtual TIntermAggregate* getAsAggregate() { return this; } 494 virtual void traverse(TIntermTraverser*); 495 virtual bool replaceChildNode( 496 TIntermNode *original, TIntermNode *replacement); 497 498 // Conservatively assume function calls and other aggregate operators have side-effects 499 virtual bool hasSideEffects() const { return true; } 500 501 TIntermSequence& getSequence() { return sequence; } 502 503 void setName(const TString& n) { name = n; } 504 const TString& getName() const { return name; } 505 506 void setUserDefined() { userDefined = true; } 507 bool isUserDefined() const { return userDefined; } 508 509 void setOptimize(bool o) { optimize = o; } 510 bool getOptimize() { return optimize; } 511 void setDebug(bool d) { debug = d; } 512 bool getDebug() { return debug; } 513 514 void setUseEmulatedFunction() { useEmulatedFunction = true; } 515 bool getUseEmulatedFunction() { return useEmulatedFunction; } 516 517 protected: 518 TIntermAggregate(const TIntermAggregate&); // disallow copy constructor 519 TIntermAggregate& operator=(const TIntermAggregate&); // disallow assignment operator 520 TIntermSequence sequence; 521 TString name; 522 bool userDefined; // used for user defined function names 523 524 bool optimize; 525 bool debug; 526 527 // If set to true, replace the built-in function call with an emulated one 528 // to work around driver bugs. 529 bool useEmulatedFunction; 530 }; 531 532 // 533 // For if tests. Simplified since there is no switch statement. 534 // 535 class TIntermSelection : public TIntermTyped { 536 public: 537 TIntermSelection(TIntermTyped* cond, TIntermNode* trueB, TIntermNode* falseB) : 538 TIntermTyped(TType(EbtVoid, EbpUndefined)), condition(cond), trueBlock(trueB), falseBlock(falseB) {} 539 TIntermSelection(TIntermTyped* cond, TIntermNode* trueB, TIntermNode* falseB, const TType& type) : 540 TIntermTyped(type), condition(cond), trueBlock(trueB), falseBlock(falseB) {} 541 542 virtual void traverse(TIntermTraverser*); 543 virtual bool replaceChildNode( 544 TIntermNode *original, TIntermNode *replacement); 545 546 // Conservatively assume selections have side-effects 547 virtual bool hasSideEffects() const { return true; } 548 549 bool usesTernaryOperator() const { return getBasicType() != EbtVoid; } 550 TIntermNode* getCondition() const { return condition; } 551 TIntermNode* getTrueBlock() const { return trueBlock; } 552 TIntermNode* getFalseBlock() const { return falseBlock; } 553 TIntermSelection* getAsSelectionNode() { return this; } 554 555 protected: 556 TIntermTyped* condition; 557 TIntermNode* trueBlock; 558 TIntermNode* falseBlock; 559 }; 560 561 enum Visit 562 { 563 PreVisit, 564 InVisit, 565 PostVisit 566 }; 567 568 // 569 // For traversing the tree. User should derive from this, 570 // put their traversal specific data in it, and then pass 571 // it to a Traverse method. 572 // 573 // When using this, just fill in the methods for nodes you want visited. 574 // Return false from a pre-visit to skip visiting that node's subtree. 575 // 576 class TIntermTraverser 577 { 578 public: 579 POOL_ALLOCATOR_NEW_DELETE(); 580 TIntermTraverser(bool preVisit = true, bool inVisit = false, bool postVisit = false, bool rightToLeft = false) : 581 preVisit(preVisit), 582 inVisit(inVisit), 583 postVisit(postVisit), 584 rightToLeft(rightToLeft), 585 depth(0), 586 maxDepth(0) {} 587 virtual ~TIntermTraverser() {} 588 589 virtual void visitSymbol(TIntermSymbol*) {} 590 virtual void visitConstantUnion(TIntermConstantUnion*) {} 591 virtual bool visitBinary(Visit visit, TIntermBinary*) {return true;} 592 virtual bool visitUnary(Visit visit, TIntermUnary*) {return true;} 593 virtual bool visitSelection(Visit visit, TIntermSelection*) {return true;} 594 virtual bool visitAggregate(Visit visit, TIntermAggregate*) {return true;} 595 virtual bool visitLoop(Visit visit, TIntermLoop*) {return true;} 596 virtual bool visitBranch(Visit visit, TIntermBranch*) {return true;} 597 598 int getMaxDepth() const {return maxDepth;} 599 600 void incrementDepth(TIntermNode *current) 601 { 602 depth++; 603 maxDepth = std::max(maxDepth, depth); 604 path.push_back(current); 605 } 606 607 void decrementDepth() 608 { 609 depth--; 610 path.pop_back(); 611 } 612 613 TIntermNode *getParentNode() 614 { 615 return path.size() == 0 ? NULL : path.back(); 616 } 617 618 // Return the original name if hash function pointer is NULL; 619 // otherwise return the hashed name. 620 static TString hash(const TString& name, ShHashFunction64 hashFunction); 621 622 const bool preVisit; 623 const bool inVisit; 624 const bool postVisit; 625 const bool rightToLeft; 626 627 protected: 628 int depth; 629 int maxDepth; 630 631 // All the nodes from root to the current node's parent during traversing. 632 TVector<TIntermNode *> path; 633 }; 634 635 #endif // __INTERMEDIATE_H 636
