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//
16// Definition of the in-memory high-level intermediate representation
17// of shaders. This is a tree that parser creates.
18//
19// Nodes in the tree are defined as a hierarchy of classes derived from
20// TIntermNode. Each is a node in a tree. There is no preset branching factor;
21// each node can have it's own type of list of children.
22//
23
24#ifndef __INTERMEDIATE_H
25#define __INTERMEDIATE_H
26
27#include "Common.h"
28#include "Types.h"
29#include "ConstantUnion.h"
30
31//
32// Operators used by the high-level (parse tree) representation.
33//
34enum TOperator {
35 EOpNull, // if in a node, should only mean a node is still being built
36 EOpSequence, // denotes a list of statements, or parameters, etc.
37 EOpFunctionCall,
38 EOpFunction, // For function definition
39 EOpParameters, // an aggregate listing the parameters to a function
40
41 EOpDeclaration,
42 EOpInvariantDeclaration, // Specialized declarations for attributing invariance
43 EOpPrototype,
44
45 //
46 // Unary operators
47 //
48
49 EOpNegative,
50 EOpLogicalNot,
51 EOpVectorLogicalNot,
52 EOpBitwiseNot,
53
54 EOpPostIncrement,
55 EOpPostDecrement,
56 EOpPreIncrement,
57 EOpPreDecrement,
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 EOpOuterProduct,
78 EOpTranspose,
79 EOpDeterminant,
80 EOpInverse,
81
82 EOpVectorTimesScalar,
83 EOpVectorTimesMatrix,
84 EOpMatrixTimesVector,
85 EOpMatrixTimesScalar,
86
87 EOpLogicalOr,
88 EOpLogicalXor,
89 EOpLogicalAnd,
90
91 EOpIMod,
92 EOpBitShiftLeft,
93 EOpBitShiftRight,
94 EOpBitwiseAnd,
95 EOpBitwiseXor,
96 EOpBitwiseOr,
97
98 EOpIndexDirect,
99 EOpIndexIndirect,
100 EOpIndexDirectStruct,
101 EOpIndexDirectInterfaceBlock,
102
103 EOpVectorSwizzle,
104
105 //
106 // Built-in functions potentially mapped to operators
107 //
108
109 EOpRadians,
110 EOpDegrees,
111 EOpSin,
112 EOpCos,
113 EOpTan,
114 EOpAsin,
115 EOpAcos,
116 EOpAtan,
117 EOpSinh,
118 EOpCosh,
119 EOpTanh,
120 EOpAsinh,
121 EOpAcosh,
122 EOpAtanh,
123
124 EOpPow,
125 EOpExp,
126 EOpLog,
127 EOpExp2,
128 EOpLog2,
129 EOpSqrt,
130 EOpInverseSqrt,
131
132 EOpAbs,
133 EOpSign,
134 EOpFloor,
135 EOpTrunc,
136 EOpRound,
137 EOpRoundEven,
138 EOpCeil,
139 EOpFract,
140 EOpMod,
141 EOpModf,
142 EOpMin,
143 EOpMax,
144 EOpClamp,
145 EOpMix,
146 EOpStep,
147 EOpSmoothStep,
148 EOpIsNan,
149 EOpIsInf,
150 EOpFloatBitsToInt,
151 EOpFloatBitsToUint,
152 EOpIntBitsToFloat,
153 EOpUintBitsToFloat,
154 EOpPackSnorm2x16,
155 EOpPackUnorm2x16,
156 EOpPackHalf2x16,
157 EOpUnpackSnorm2x16,
158 EOpUnpackUnorm2x16,
159 EOpUnpackHalf2x16,
160
161 EOpLength,
162 EOpDistance,
163 EOpDot,
164 EOpCross,
165 EOpNormalize,
166 EOpFaceForward,
167 EOpReflect,
168 EOpRefract,
169
170 EOpDFdx, // Fragment only, OES_standard_derivatives extension
171 EOpDFdy, // Fragment only, OES_standard_derivatives extension
172 EOpFwidth, // Fragment only, OES_standard_derivatives extension
173
174 EOpMatrixTimesMatrix,
175
176 EOpAny,
177 EOpAll,
178
179 //
180 // Branch
181 //
182
183 EOpKill, // Fragment only
184 EOpReturn,
185 EOpBreak,
186 EOpContinue,
187
188 //
189 // Constructors
190 //
191
192 EOpConstructInt,
193 EOpConstructUInt,
194 EOpConstructBool,
195 EOpConstructFloat,
196 EOpConstructVec2,
197 EOpConstructVec3,
198 EOpConstructVec4,
199 EOpConstructBVec2,
200 EOpConstructBVec3,
201 EOpConstructBVec4,
202 EOpConstructIVec2,
203 EOpConstructIVec3,
204 EOpConstructIVec4,
205 EOpConstructUVec2,
206 EOpConstructUVec3,
207 EOpConstructUVec4,
208 EOpConstructMat2,
209 EOpConstructMat2x3,
210 EOpConstructMat2x4,
211 EOpConstructMat3x2,
212 EOpConstructMat3,
213 EOpConstructMat3x4,
214 EOpConstructMat4x2,
215 EOpConstructMat4x3,
216 EOpConstructMat4,
217 EOpConstructStruct,
218
219 //
220 // moves
221 //
222
223 EOpAssign,
224 EOpInitialize,
225 EOpAddAssign,
226 EOpSubAssign,
227 EOpMulAssign,
228 EOpVectorTimesMatrixAssign,
229 EOpVectorTimesScalarAssign,
230 EOpMatrixTimesScalarAssign,
231 EOpMatrixTimesMatrixAssign,
232 EOpDivAssign,
233 EOpIModAssign,
234 EOpBitShiftLeftAssign,
235 EOpBitShiftRightAssign,
236 EOpBitwiseAndAssign,
237 EOpBitwiseXorAssign,
238 EOpBitwiseOrAssign
239};
240
241extern TOperator TypeToConstructorOperator(const TType &type);
242extern const char* getOperatorString(TOperator op);
243
244class TIntermTraverser;
245class TIntermAggregate;
246class TIntermBinary;
247class TIntermUnary;
248class TIntermConstantUnion;
249class TIntermSelection;
250class TIntermTyped;
251class TIntermSymbol;
252class TIntermLoop;
253class TIntermBranch;
254class TInfoSink;
255class TIntermSwitch;
256class TIntermCase;
257
258//
259// Base class for the tree nodes
260//
261class TIntermNode {
262public:
263 POOL_ALLOCATOR_NEW_DELETE()
264
265 TIntermNode()
266 {
267 // TODO: Move this to TSourceLoc constructor
268 // after getting rid of TPublicType.
269 line.first_file = line.last_file = 0;
270 line.first_line = line.last_line = 0;
271 }
272
273 const TSourceLoc& getLine() const { return line; }
274 void setLine(const TSourceLoc& l) { line = l; }
275
276 virtual void traverse(TIntermTraverser*) = 0;
277 virtual TIntermTyped* getAsTyped() { return 0; }
278 virtual TIntermConstantUnion* getAsConstantUnion() { return 0; }
279 virtual TIntermAggregate* getAsAggregate() { return 0; }
280 virtual TIntermBinary* getAsBinaryNode() { return 0; }
281 virtual TIntermUnary* getAsUnaryNode() { return 0; }
282 virtual TIntermSelection* getAsSelectionNode() { return 0; }
283 virtual TIntermSymbol* getAsSymbolNode() { return 0; }
284 virtual TIntermLoop* getAsLoopNode() { return 0; }
285 virtual TIntermBranch* getAsBranchNode() { return 0; }
286 virtual TIntermSwitch *getAsSwitchNode() { return 0; }
287 virtual TIntermCase *getAsCaseNode() { return 0; }
288 virtual ~TIntermNode() { }
289
290protected:
291 TSourceLoc line;
292};
293
294//
295// This is just to help yacc.
296//
297struct TIntermNodePair {
298 TIntermNode* node1;
299 TIntermNode* node2;
300};
301
302//
303// Intermediate class for nodes that have a type.
304//
305class TIntermTyped : public TIntermNode {
306public:
307 TIntermTyped(const TType& t) : type(t) { }
308 virtual TIntermTyped* getAsTyped() { return this; }
309
310 virtual void setType(const TType& t) { type = t; }
311 const TType& getType() const { return type; }
312 TType* getTypePointer() { return &type; }
313
314 TBasicType getBasicType() const { return type.getBasicType(); }
315 TQualifier getQualifier() const { return type.getQualifier(); }
316 TPrecision getPrecision() const { return type.getPrecision(); }
317 int getNominalSize() const { return type.getNominalSize(); }
318 int getSecondarySize() const { return type.getSecondarySize(); }
319
320 bool isInterfaceBlock() const { return type.isInterfaceBlock(); }
321 bool isMatrix() const { return type.isMatrix(); }
322 bool isArray() const { return type.isArray(); }
323 bool isVector() const { return type.isVector(); }
324 bool isScalar() const { return type.isScalar(); }
325 bool isScalarInt() const { return type.isScalarInt(); }
326 bool isRegister() const { return type.isRegister(); } // Fits in a 4-element register
327 bool isStruct() const { return type.isStruct(); }
328 const char* getBasicString() const { return type.getBasicString(); }
329 const char* getQualifierString() const { return type.getQualifierString(); }
330 TString getCompleteString() const { return type.getCompleteString(); }
331
332 int totalRegisterCount() const { return type.totalRegisterCount(); }
333 int blockRegisterCount(bool samplersOnly) const { return samplersOnly ? type.totalSamplerRegisterCount() : type.blockRegisterCount(); }
334 int elementRegisterCount() const { return type.elementRegisterCount(); }
335 int registerSize() const { return type.registerSize(); }
336 int getArraySize() const { return type.getArraySize(); }
337
338 static TIntermTyped *CreateIndexNode(int index);
339protected:
340 TType type;
341};
342
343//
344// Handle for, do-while, and while loops.
345//
346enum TLoopType {
347 ELoopFor,
348 ELoopWhile,
349 ELoopDoWhile
350};
351
352class TIntermLoop : public TIntermNode {
353public:
354 TIntermLoop(TLoopType aType,
355 TIntermNode *aInit, TIntermTyped* aCond, TIntermTyped* aExpr,
356 TIntermNode* aBody) :
357 type(aType),
358 init(aInit),
359 cond(aCond),
360 expr(aExpr),
361 body(aBody),
362 unrollFlag(false) { }
363
364 virtual TIntermLoop* getAsLoopNode() { return this; }
365 virtual void traverse(TIntermTraverser*);
366
367 TLoopType getType() const { return type; }
368 TIntermNode* getInit() { return init; }
369 TIntermTyped* getCondition() { return cond; }
370 TIntermTyped* getExpression() { return expr; }
371 TIntermNode* getBody() { return body; }
372
373 void setUnrollFlag(bool flag) { unrollFlag = flag; }
374 bool getUnrollFlag() { return unrollFlag; }
375
376protected:
377 TLoopType type;
378 TIntermNode* init; // for-loop initialization
379 TIntermTyped* cond; // loop exit condition
380 TIntermTyped* expr; // for-loop expression
381 TIntermNode* body; // loop body
382
383 bool unrollFlag; // Whether the loop should be unrolled or not.
384};
385
386//
387// Handle break, continue, return, and kill.
388//
389class TIntermBranch : public TIntermNode {
390public:
391 TIntermBranch(TOperator op, TIntermTyped* e) :
392 flowOp(op),
393 expression(e) { }
394
395 virtual TIntermBranch* getAsBranchNode() { return this; }
396 virtual void traverse(TIntermTraverser*);
397
398 TOperator getFlowOp() { return flowOp; }
399 TIntermTyped* getExpression() { return expression; }
400
401protected:
402 TOperator flowOp;
403 TIntermTyped* expression; // non-zero except for "return exp;" statements
404};
405
406//
407// Nodes that correspond to symbols or constants in the source code.
408//
409class TIntermSymbol : public TIntermTyped {
410public:
411 // if symbol is initialized as symbol(sym), the memory comes from the poolallocator of sym. If sym comes from
412 // per process globalpoolallocator, then it causes increased memory usage per compile
413 // it is essential to use "symbol = sym" to assign to symbol
414 TIntermSymbol(int i, const TString& sym, const TType& t) :
415 TIntermTyped(t), id(i) { symbol = sym; }
416
417 int getId() const { return id; }
418 const TString& getSymbol() const { return symbol; }
419
420 void setId(int newId) { id = newId; }
421
422 virtual void traverse(TIntermTraverser*);
423 virtual TIntermSymbol* getAsSymbolNode() { return this; }
424
425protected:
426 int id;
427 TString symbol;
428};
429
430class TIntermConstantUnion : public TIntermTyped {
431public:
432 TIntermConstantUnion(ConstantUnion *unionPointer, const TType& t) : TIntermTyped(t), unionArrayPointer(unionPointer)
433 {
434 getTypePointer()->setQualifier(EvqConstExpr);
435 }
436
437 ConstantUnion* getUnionArrayPointer() const { return unionArrayPointer; }
438
439 int getIConst(int index) const { return unionArrayPointer ? unionArrayPointer[index].getIConst() : 0; }
440 int getUConst(int index) const { return unionArrayPointer ? unionArrayPointer[index].getUConst() : 0; }
441 float getFConst(int index) const { return unionArrayPointer ? unionArrayPointer[index].getFConst() : 0.0f; }
442 bool getBConst(int index) const { return unionArrayPointer ? unionArrayPointer[index].getBConst() : false; }
443
444 // Previous union pointer freed on pool deallocation.
445 void replaceConstantUnion(ConstantUnion *safeConstantUnion) { unionArrayPointer = safeConstantUnion; }
446
447 virtual TIntermConstantUnion* getAsConstantUnion() { return this; }
448 virtual void traverse(TIntermTraverser*);
449
450 TIntermTyped* fold(TOperator, TIntermTyped*, TInfoSink&);
451
452protected:
453 ConstantUnion *unionArrayPointer;
454};
455
456//
457// Intermediate class for node types that hold operators.
458//
459class TIntermOperator : public TIntermTyped {
460public:
461 TOperator getOp() const { return op; }
462 void setOp(TOperator o) { op = o; }
463
464 bool modifiesState() const;
465 bool isConstructor() const;
466
467protected:
468 TIntermOperator(TOperator o) : TIntermTyped(TType(EbtFloat, EbpUndefined)), op(o) {}
469 TIntermOperator(TOperator o, TType& t) : TIntermTyped(t), op(o) {}
470 TOperator op;
471};
472
473//
474// Nodes for all the basic binary math operators.
475//
476class TIntermBinary : public TIntermOperator {
477public:
478 TIntermBinary(TOperator o) : TIntermOperator(o) {}
479
480 TIntermBinary* getAsBinaryNode() override { return this; }
481 void traverse(TIntermTraverser*) override;
482
483 void setType(const TType &t) override
484 {
485 type = t;
486
487 if(left->getQualifier() == EvqConstExpr && right->getQualifier() == EvqConstExpr)
488 {
489 type.setQualifier(EvqConstExpr);
490 }
491 }
492
493 void setLeft(TIntermTyped* n) { left = n; }
494 void setRight(TIntermTyped* n) { right = n; }
495 TIntermTyped* getLeft() const { return left; }
496 TIntermTyped* getRight() const { return right; }
497 bool promote(TInfoSink&);
498
499protected:
500 TIntermTyped* left;
501 TIntermTyped* right;
502};
503
504//
505// Nodes for unary math operators.
506//
507class TIntermUnary : public TIntermOperator {
508public:
509 TIntermUnary(TOperator o, TType& t) : TIntermOperator(o, t), operand(0) {}
510 TIntermUnary(TOperator o) : TIntermOperator(o), operand(0) {}
511
512 void setType(const TType &t) override
513 {
514 type = t;
515
516 if(operand->getQualifier() == EvqConstExpr)
517 {
518 type.setQualifier(EvqConstExpr);
519 }
520 }
521
522 void traverse(TIntermTraverser*) override;
523 TIntermUnary* getAsUnaryNode() override { return this; }
524
525 void setOperand(TIntermTyped* o) { operand = o; }
526 TIntermTyped* getOperand() { return operand; }
527 bool promote(TInfoSink&, const TType *funcReturnType);
528
529protected:
530 TIntermTyped* operand;
531};
532
533typedef TVector<TIntermNode*> TIntermSequence;
534typedef TVector<int> TQualifierList;
535
536//
537// Nodes that operate on an arbitrary sized set of children.
538//
539class TIntermAggregate : public TIntermOperator {
540public:
541 TIntermAggregate() : TIntermOperator(EOpNull), userDefined(false) { endLine = { 0, 0, 0, 0 }; }
542 TIntermAggregate(TOperator o) : TIntermOperator(o), userDefined(false) { endLine = { 0, 0, 0, 0 }; }
543 ~TIntermAggregate() { }
544
545 TIntermAggregate* getAsAggregate() override { return this; }
546 void traverse(TIntermTraverser*) override;
547
548 TIntermSequence& getSequence() { return sequence; }
549
550 void setType(const TType &t) override
551 {
552 type = t;
553
554 if(op != EOpFunctionCall)
555 {
556 for(TIntermNode *node : sequence)
557 {
558 if(!node->getAsTyped() || node->getAsTyped()->getQualifier() != EvqConstExpr)
559 {
560 return;
561 }
562 }
563
564 type.setQualifier(EvqConstExpr);
565 }
566 }
567
568 void setName(const TString& n) { name = n; }
569 const TString& getName() const { return name; }
570
571 void setUserDefined() { userDefined = true; }
572 bool isUserDefined() const { return userDefined; }
573
574 void setOptimize(bool o) { optimize = o; }
575 bool getOptimize() { return optimize; }
576 void setDebug(bool d) { debug = d; }
577 bool getDebug() { return debug; }
578
579 void setEndLine(const TSourceLoc& line) { endLine = line; }
580 const TSourceLoc& getEndLine() const { return endLine; }
581
582 bool isConstantFoldable()
583 {
584 for(TIntermNode *node : sequence)
585 {
586 if(!node->getAsConstantUnion() || !node->getAsConstantUnion()->getUnionArrayPointer())
587 {
588 return false;
589 }
590 }
591
592 return true;
593 }
594
595protected:
596 TIntermAggregate(const TIntermAggregate&); // disallow copy constructor
597 TIntermAggregate& operator=(const TIntermAggregate&); // disallow assignment operator
598 TIntermSequence sequence;
599 TString name;
600 bool userDefined; // used for user defined function names
601
602 bool optimize;
603 bool debug;
604 TSourceLoc endLine;
605};
606
607//
608// For if tests. Simplified since there is no switch statement.
609//
610class TIntermSelection : public TIntermTyped {
611public:
612 TIntermSelection(TIntermTyped* cond, TIntermNode* trueB, TIntermNode* falseB) :
613 TIntermTyped(TType(EbtVoid, EbpUndefined)), condition(cond), trueBlock(trueB), falseBlock(falseB) {}
614 TIntermSelection(TIntermTyped* cond, TIntermNode* trueB, TIntermNode* falseB, const TType& type) :
615 TIntermTyped(type), condition(cond), trueBlock(trueB), falseBlock(falseB)
616 {
617 this->type.setQualifier(EvqTemporary);
618 }
619
620 virtual void traverse(TIntermTraverser*);
621
622 bool usesTernaryOperator() const { return getBasicType() != EbtVoid; }
623 TIntermTyped* getCondition() const { return condition; }
624 TIntermNode* getTrueBlock() const { return trueBlock; }
625 TIntermNode* getFalseBlock() const { return falseBlock; }
626 TIntermSelection* getAsSelectionNode() { return this; }
627
628protected:
629 TIntermTyped* condition;
630 TIntermNode* trueBlock;
631 TIntermNode* falseBlock;
632};
633
634//
635// Switch statement.
636//
637class TIntermSwitch : public TIntermNode
638{
639public:
640 TIntermSwitch(TIntermTyped *init, TIntermAggregate *statementList)
641 : TIntermNode(), mInit(init), mStatementList(statementList)
642 {}
643
644 void traverse(TIntermTraverser *it);
645
646 TIntermSwitch *getAsSwitchNode() { return this; }
647
648 TIntermTyped *getInit() { return mInit; }
649 TIntermAggregate *getStatementList() { return mStatementList; }
650 void setStatementList(TIntermAggregate *statementList) { mStatementList = statementList; }
651
652protected:
653 TIntermTyped *mInit;
654 TIntermAggregate *mStatementList;
655};
656
657//
658// Case label.
659//
660class TIntermCase : public TIntermNode
661{
662public:
663 TIntermCase(TIntermTyped *condition)
664 : TIntermNode(), mCondition(condition)
665 {}
666
667 void traverse(TIntermTraverser *it);
668
669 TIntermCase *getAsCaseNode() { return this; }
670
671 bool hasCondition() const { return mCondition != nullptr; }
672 TIntermTyped *getCondition() const { return mCondition; }
673
674protected:
675 TIntermTyped *mCondition;
676};
677
678enum Visit
679{
680 PreVisit,
681 InVisit,
682 PostVisit
683};
684
685//
686// For traversing the tree. User should derive from this,
687// put their traversal specific data in it, and then pass
688// it to a Traverse method.
689//
690// When using this, just fill in the methods for nodes you want visited.
691// Return false from a pre-visit to skip visiting that node's subtree.
692//
693class TIntermTraverser
694{
695public:
696 POOL_ALLOCATOR_NEW_DELETE()
697 TIntermTraverser(bool preVisit = true, bool inVisit = false, bool postVisit = false, bool rightToLeft = false) :
698 preVisit(preVisit),
699 inVisit(inVisit),
700 postVisit(postVisit),
701 rightToLeft(rightToLeft),
702 mDepth(0) {}
703 virtual ~TIntermTraverser() {}
704
705 virtual void visitSymbol(TIntermSymbol*) {}
706 virtual void visitConstantUnion(TIntermConstantUnion*) {}
707 virtual bool visitBinary(Visit visit, TIntermBinary*) {return true;}
708 virtual bool visitUnary(Visit visit, TIntermUnary*) {return true;}
709 virtual bool visitSelection(Visit visit, TIntermSelection*) {return true;}
710 virtual bool visitAggregate(Visit visit, TIntermAggregate*) {return true;}
711 virtual bool visitLoop(Visit visit, TIntermLoop*) {return true;}
712 virtual bool visitBranch(Visit visit, TIntermBranch*) {return true;}
713 virtual bool visitSwitch(Visit, TIntermSwitch*) { return true; }
714 virtual bool visitCase(Visit, TIntermCase*) { return true; }
715
716 void incrementDepth(TIntermNode *current)
717 {
718 mDepth++;
719 mPath.push_back(current);
720 }
721
722 void decrementDepth()
723 {
724 mDepth--;
725 mPath.pop_back();
726 }
727
728 TIntermNode *getParentNode()
729 {
730 return mPath.size() == 0 ? nullptr : mPath.back();
731 }
732
733 const bool preVisit;
734 const bool inVisit;
735 const bool postVisit;
736 const bool rightToLeft;
737
738protected:
739 int mDepth;
740
741 // All the nodes from root to the current node's parent during traversing.
742 TVector<TIntermNode *> mPath;
743
744private:
745 struct ParentBlock
746 {
747 ParentBlock(TIntermAggregate *nodeIn, TIntermSequence::size_type posIn)
748 : node(nodeIn), pos(posIn)
749 {}
750
751 TIntermAggregate *node;
752 TIntermSequence::size_type pos;
753 };
754 // All the code blocks from the root to the current node's parent during traversal.
755 std::vector<ParentBlock> mParentBlockStack;
756};
757
758#endif // __INTERMEDIATE_H
759