blob: 9e960cf578b86b78a90b31ab717bb7cdf4ab628e [file] [log] [blame]
Jamie Madillb1a85f42014-08-19 15:23:24 -04001//
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//
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
Geoff Lang0a73dd82014-11-19 16:18:08 -050016#ifndef COMPILER_TRANSLATOR_INTERMNODE_H_
17#define COMPILER_TRANSLATOR_INTERMNODE_H_
Jamie Madillb1a85f42014-08-19 15:23:24 -040018
19#include "GLSLANG/ShaderLang.h"
20
21#include <algorithm>
22#include <queue>
23
Jamie Madill80d934b2015-02-19 10:16:12 -050024#include "common/angleutils.h"
Jamie Madillb1a85f42014-08-19 15:23:24 -040025#include "compiler/translator/Common.h"
Jamie Madillb1a85f42014-08-19 15:23:24 -040026#include "compiler/translator/ConstantUnion.h"
Olli Etuaho1033e1d2015-02-12 12:03:13 +020027#include "compiler/translator/Operator.h"
Jamie Madill6ba6ead2015-05-04 14:21:21 -040028#include "compiler/translator/Types.h"
Jamie Madillb1a85f42014-08-19 15:23:24 -040029
30class TIntermTraverser;
31class TIntermAggregate;
32class TIntermBinary;
33class TIntermUnary;
34class TIntermConstantUnion;
35class TIntermSelection;
Olli Etuahoa3a36662015-02-17 13:46:51 +020036class TIntermSwitch;
37class TIntermCase;
Jamie Madillb1a85f42014-08-19 15:23:24 -040038class TIntermTyped;
39class TIntermSymbol;
40class TIntermLoop;
41class TInfoSink;
Olli Etuahoa3a5cc62015-02-13 13:12:22 +020042class TInfoSinkBase;
Jamie Madillb1a85f42014-08-19 15:23:24 -040043class TIntermRaw;
44
45//
46// Base class for the tree nodes
47//
48class TIntermNode
49{
50 public:
51 POOL_ALLOCATOR_NEW_DELETE();
52 TIntermNode()
53 {
54 // TODO: Move this to TSourceLoc constructor
55 // after getting rid of TPublicType.
56 mLine.first_file = mLine.last_file = 0;
57 mLine.first_line = mLine.last_line = 0;
58 }
59 virtual ~TIntermNode() { }
60
61 const TSourceLoc &getLine() const { return mLine; }
62 void setLine(const TSourceLoc &l) { mLine = l; }
63
64 virtual void traverse(TIntermTraverser *) = 0;
65 virtual TIntermTyped *getAsTyped() { return 0; }
66 virtual TIntermConstantUnion *getAsConstantUnion() { return 0; }
67 virtual TIntermAggregate *getAsAggregate() { return 0; }
68 virtual TIntermBinary *getAsBinaryNode() { return 0; }
69 virtual TIntermUnary *getAsUnaryNode() { return 0; }
70 virtual TIntermSelection *getAsSelectionNode() { return 0; }
Olli Etuahoa3a36662015-02-17 13:46:51 +020071 virtual TIntermSwitch *getAsSwitchNode() { return 0; }
72 virtual TIntermCase *getAsCaseNode() { return 0; }
Jamie Madillb1a85f42014-08-19 15:23:24 -040073 virtual TIntermSymbol *getAsSymbolNode() { return 0; }
74 virtual TIntermLoop *getAsLoopNode() { return 0; }
75 virtual TIntermRaw *getAsRawNode() { return 0; }
76
77 // Replace a child node. Return true if |original| is a child
78 // node and it is replaced; otherwise, return false.
79 virtual bool replaceChildNode(
80 TIntermNode *original, TIntermNode *replacement) = 0;
81
Jamie Madillb1a85f42014-08-19 15:23:24 -040082 protected:
83 TSourceLoc mLine;
84};
85
86//
87// This is just to help yacc.
88//
89struct TIntermNodePair
90{
91 TIntermNode *node1;
92 TIntermNode *node2;
93};
94
95//
96// Intermediate class for nodes that have a type.
97//
98class TIntermTyped : public TIntermNode
99{
100 public:
101 TIntermTyped(const TType &t) : mType(t) { }
102 virtual TIntermTyped *getAsTyped() { return this; }
103
104 virtual bool hasSideEffects() const = 0;
105
106 void setType(const TType &t) { mType = t; }
Olli Etuahod2a67b92014-10-21 16:42:57 +0300107 void setTypePreservePrecision(const TType &t);
Jamie Madillb1a85f42014-08-19 15:23:24 -0400108 const TType &getType() const { return mType; }
109 TType *getTypePointer() { return &mType; }
110
111 TBasicType getBasicType() const { return mType.getBasicType(); }
112 TQualifier getQualifier() const { return mType.getQualifier(); }
113 TPrecision getPrecision() const { return mType.getPrecision(); }
114 int getCols() const { return mType.getCols(); }
115 int getRows() const { return mType.getRows(); }
116 int getNominalSize() const { return mType.getNominalSize(); }
117 int getSecondarySize() const { return mType.getSecondarySize(); }
118
119 bool isInterfaceBlock() const { return mType.isInterfaceBlock(); }
120 bool isMatrix() const { return mType.isMatrix(); }
121 bool isArray() const { return mType.isArray(); }
122 bool isVector() const { return mType.isVector(); }
123 bool isScalar() const { return mType.isScalar(); }
124 bool isScalarInt() const { return mType.isScalarInt(); }
125 const char *getBasicString() const { return mType.getBasicString(); }
Jamie Madillb1a85f42014-08-19 15:23:24 -0400126 TString getCompleteString() const { return mType.getCompleteString(); }
127
128 int getArraySize() const { return mType.getArraySize(); }
129
130 protected:
131 TType mType;
132};
133
134//
135// Handle for, do-while, and while loops.
136//
137enum TLoopType
138{
139 ELoopFor,
140 ELoopWhile,
141 ELoopDoWhile
142};
143
144class TIntermLoop : public TIntermNode
145{
146 public:
147 TIntermLoop(TLoopType type,
148 TIntermNode *init, TIntermTyped *cond, TIntermTyped *expr,
149 TIntermNode *body)
150 : mType(type),
151 mInit(init),
152 mCond(cond),
153 mExpr(expr),
154 mBody(body),
155 mUnrollFlag(false) { }
156
157 virtual TIntermLoop *getAsLoopNode() { return this; }
158 virtual void traverse(TIntermTraverser *);
159 virtual bool replaceChildNode(
160 TIntermNode *original, TIntermNode *replacement);
161
162 TLoopType getType() const { return mType; }
163 TIntermNode *getInit() { return mInit; }
164 TIntermTyped *getCondition() { return mCond; }
165 TIntermTyped *getExpression() { return mExpr; }
166 TIntermNode *getBody() { return mBody; }
167
168 void setUnrollFlag(bool flag) { mUnrollFlag = flag; }
169 bool getUnrollFlag() const { return mUnrollFlag; }
170
Jamie Madillb1a85f42014-08-19 15:23:24 -0400171 protected:
172 TLoopType mType;
173 TIntermNode *mInit; // for-loop initialization
174 TIntermTyped *mCond; // loop exit condition
175 TIntermTyped *mExpr; // for-loop expression
176 TIntermNode *mBody; // loop body
177
178 bool mUnrollFlag; // Whether the loop should be unrolled or not.
179};
180
181//
182// Handle break, continue, return, and kill.
183//
184class TIntermBranch : public TIntermNode
185{
186 public:
187 TIntermBranch(TOperator op, TIntermTyped *e)
188 : mFlowOp(op),
189 mExpression(e) { }
190
191 virtual void traverse(TIntermTraverser *);
192 virtual bool replaceChildNode(
193 TIntermNode *original, TIntermNode *replacement);
194
195 TOperator getFlowOp() { return mFlowOp; }
196 TIntermTyped* getExpression() { return mExpression; }
197
Jamie Madillb1a85f42014-08-19 15:23:24 -0400198protected:
199 TOperator mFlowOp;
200 TIntermTyped *mExpression; // non-zero except for "return exp;" statements
201};
202
203//
204// Nodes that correspond to symbols or constants in the source code.
205//
206class TIntermSymbol : public TIntermTyped
207{
208 public:
209 // if symbol is initialized as symbol(sym), the memory comes from the poolallocator of sym.
210 // If sym comes from per process globalpoolallocator, then it causes increased memory usage
211 // per compile it is essential to use "symbol = sym" to assign to symbol
212 TIntermSymbol(int id, const TString &symbol, const TType &type)
213 : TIntermTyped(type),
Olli Etuaho78174db2015-04-21 16:14:00 +0300214 mId(id),
215 mInternal(false)
Jamie Madillb1a85f42014-08-19 15:23:24 -0400216 {
217 mSymbol = symbol;
218 }
219
220 virtual bool hasSideEffects() const { return false; }
221
222 int getId() const { return mId; }
223 const TString &getSymbol() const { return mSymbol; }
224
225 void setId(int newId) { mId = newId; }
226
Olli Etuaho78174db2015-04-21 16:14:00 +0300227 bool isInternal() const { return mInternal; }
228 void setInternal(bool isInternal) { mInternal = isInternal; }
229
Jamie Madillb1a85f42014-08-19 15:23:24 -0400230 virtual void traverse(TIntermTraverser *);
231 virtual TIntermSymbol *getAsSymbolNode() { return this; }
232 virtual bool replaceChildNode(TIntermNode *, TIntermNode *) { return false; }
233
Jamie Madillb1a85f42014-08-19 15:23:24 -0400234 protected:
235 int mId;
Olli Etuaho78174db2015-04-21 16:14:00 +0300236 bool mInternal;
Jamie Madillb1a85f42014-08-19 15:23:24 -0400237 TString mSymbol;
238};
239
240// A Raw node stores raw code, that the translator will insert verbatim
241// into the output stream. Useful for transformation operations that make
242// complex code that might not fit naturally into the GLSL model.
243class TIntermRaw : public TIntermTyped
244{
245 public:
246 TIntermRaw(const TType &type, const TString &rawText)
247 : TIntermTyped(type),
248 mRawText(rawText) { }
249
250 virtual bool hasSideEffects() const { return false; }
251
252 TString getRawText() const { return mRawText; }
253
254 virtual void traverse(TIntermTraverser *);
255
256 virtual TIntermRaw *getAsRawNode() { return this; }
257 virtual bool replaceChildNode(TIntermNode *, TIntermNode *) { return false; }
Jamie Madillb1a85f42014-08-19 15:23:24 -0400258
259 protected:
260 TString mRawText;
261};
262
263class TIntermConstantUnion : public TIntermTyped
264{
265 public:
Jamie Madill6ba6ead2015-05-04 14:21:21 -0400266 TIntermConstantUnion(TConstantUnion *unionPointer, const TType &type)
Jamie Madillb1a85f42014-08-19 15:23:24 -0400267 : TIntermTyped(type),
268 mUnionArrayPointer(unionPointer) { }
269
270 virtual bool hasSideEffects() const { return false; }
271
Jamie Madillb11e2482015-05-04 14:21:22 -0400272 const TConstantUnion *getUnionArrayPointer() const { return mUnionArrayPointer; }
273 TConstantUnion *getUnionArrayPointer() { return mUnionArrayPointer; }
Jamie Madillb1a85f42014-08-19 15:23:24 -0400274
275 int getIConst(size_t index) const
276 {
277 return mUnionArrayPointer ? mUnionArrayPointer[index].getIConst() : 0;
278 }
279 unsigned int getUConst(size_t index) const
280 {
281 return mUnionArrayPointer ? mUnionArrayPointer[index].getUConst() : 0;
282 }
283 float getFConst(size_t index) const
284 {
285 return mUnionArrayPointer ? mUnionArrayPointer[index].getFConst() : 0.0f;
286 }
287 bool getBConst(size_t index) const
288 {
289 return mUnionArrayPointer ? mUnionArrayPointer[index].getBConst() : false;
290 }
291
Jamie Madillb11e2482015-05-04 14:21:22 -0400292 void replaceConstantUnion(TConstantUnion *safeConstantUnion)
293 {
294 // Previous union pointer freed on pool deallocation.
295 mUnionArrayPointer = safeConstantUnion;
296 }
297
Jamie Madillb1a85f42014-08-19 15:23:24 -0400298 virtual TIntermConstantUnion *getAsConstantUnion() { return this; }
299 virtual void traverse(TIntermTraverser *);
300 virtual bool replaceChildNode(TIntermNode *, TIntermNode *) { return false; }
301
Olli Etuaho2c4b7462015-06-08 11:30:31 +0300302 TConstantUnion *foldBinary(TOperator op, TIntermConstantUnion *rightNode, TInfoSink &infoSink);
Olli Etuaho95310b02015-06-02 17:43:38 +0300303 TConstantUnion *foldUnary(TOperator op, TInfoSink &infoSink);
Jamie Madillb1a85f42014-08-19 15:23:24 -0400304
Arun Patolebf790422015-05-18 17:53:04 +0530305 static TIntermTyped *FoldAggregateBuiltIn(TOperator op, TIntermAggregate *aggregate, TInfoSink &infoSink);
Arun Patole274f0702015-05-05 13:33:30 +0530306
Jamie Madillb1a85f42014-08-19 15:23:24 -0400307 protected:
Jamie Madill6ba6ead2015-05-04 14:21:21 -0400308 TConstantUnion *mUnionArrayPointer;
Arun Patole9dea48f2015-04-02 11:45:09 +0530309
310 private:
311 typedef float(*FloatTypeUnaryFunc) (float);
Jamie Madill6ba6ead2015-05-04 14:21:21 -0400312 bool foldFloatTypeUnary(const TConstantUnion &parameter, FloatTypeUnaryFunc builtinFunc, TInfoSink &infoSink, TConstantUnion *result) const;
Jamie Madillb1a85f42014-08-19 15:23:24 -0400313};
314
315//
316// Intermediate class for node types that hold operators.
317//
318class TIntermOperator : public TIntermTyped
319{
320 public:
321 TOperator getOp() const { return mOp; }
322 void setOp(TOperator op) { mOp = op; }
323
324 bool isAssignment() const;
Olli Etuaho8f76bcc2015-06-02 13:54:20 +0300325 bool isMultiplication() const;
Jamie Madillb1a85f42014-08-19 15:23:24 -0400326 bool isConstructor() const;
327
328 virtual bool hasSideEffects() const { return isAssignment(); }
329
330 protected:
331 TIntermOperator(TOperator op)
332 : TIntermTyped(TType(EbtFloat, EbpUndefined)),
333 mOp(op) {}
334 TIntermOperator(TOperator op, const TType &type)
335 : TIntermTyped(type),
336 mOp(op) {}
337
338 TOperator mOp;
339};
340
341//
342// Nodes for all the basic binary math operators.
343//
344class TIntermBinary : public TIntermOperator
345{
346 public:
347 TIntermBinary(TOperator op)
348 : TIntermOperator(op),
349 mAddIndexClamp(false) {}
350
351 virtual TIntermBinary *getAsBinaryNode() { return this; }
352 virtual void traverse(TIntermTraverser *);
353 virtual bool replaceChildNode(
354 TIntermNode *original, TIntermNode *replacement);
355
356 virtual bool hasSideEffects() const
357 {
358 return isAssignment() || mLeft->hasSideEffects() || mRight->hasSideEffects();
359 }
360
361 void setLeft(TIntermTyped *node) { mLeft = node; }
362 void setRight(TIntermTyped *node) { mRight = node; }
363 TIntermTyped *getLeft() const { return mLeft; }
364 TIntermTyped *getRight() const { return mRight; }
365 bool promote(TInfoSink &);
Olli Etuaho2c4b7462015-06-08 11:30:31 +0300366 TIntermTyped *fold(TInfoSink &infoSink);
Jamie Madillb1a85f42014-08-19 15:23:24 -0400367
368 void setAddIndexClamp() { mAddIndexClamp = true; }
369 bool getAddIndexClamp() { return mAddIndexClamp; }
370
Jamie Madillb1a85f42014-08-19 15:23:24 -0400371 protected:
372 TIntermTyped* mLeft;
373 TIntermTyped* mRight;
374
375 // If set to true, wrap any EOpIndexIndirect with a clamp to bounds.
376 bool mAddIndexClamp;
377};
378
379//
380// Nodes for unary math operators.
381//
382class TIntermUnary : public TIntermOperator
383{
384 public:
385 TIntermUnary(TOperator op, const TType &type)
386 : TIntermOperator(op, type),
387 mOperand(NULL),
388 mUseEmulatedFunction(false) {}
389 TIntermUnary(TOperator op)
390 : TIntermOperator(op),
391 mOperand(NULL),
392 mUseEmulatedFunction(false) {}
393
394 virtual void traverse(TIntermTraverser *);
395 virtual TIntermUnary *getAsUnaryNode() { return this; }
396 virtual bool replaceChildNode(
397 TIntermNode *original, TIntermNode *replacement);
398
399 virtual bool hasSideEffects() const
400 {
401 return isAssignment() || mOperand->hasSideEffects();
402 }
403
404 void setOperand(TIntermTyped *operand) { mOperand = operand; }
405 TIntermTyped *getOperand() { return mOperand; }
Olli Etuahof6c694b2015-03-26 14:50:53 +0200406 void promote(const TType *funcReturnType);
Olli Etuaho95310b02015-06-02 17:43:38 +0300407 TIntermTyped *fold(TInfoSink &infoSink);
Jamie Madillb1a85f42014-08-19 15:23:24 -0400408
409 void setUseEmulatedFunction() { mUseEmulatedFunction = true; }
410 bool getUseEmulatedFunction() { return mUseEmulatedFunction; }
411
Jamie Madillb1a85f42014-08-19 15:23:24 -0400412 protected:
413 TIntermTyped *mOperand;
414
415 // If set to true, replace the built-in function call with an emulated one
416 // to work around driver bugs.
417 bool mUseEmulatedFunction;
418};
419
420typedef TVector<TIntermNode *> TIntermSequence;
421typedef TVector<int> TQualifierList;
422
423//
424// Nodes that operate on an arbitrary sized set of children.
425//
426class TIntermAggregate : public TIntermOperator
427{
428 public:
429 TIntermAggregate()
430 : TIntermOperator(EOpNull),
431 mUserDefined(false),
432 mUseEmulatedFunction(false) { }
433 TIntermAggregate(TOperator op)
434 : TIntermOperator(op),
435 mUseEmulatedFunction(false) { }
436 ~TIntermAggregate() { }
437
438 virtual TIntermAggregate *getAsAggregate() { return this; }
439 virtual void traverse(TIntermTraverser *);
440 virtual bool replaceChildNode(
441 TIntermNode *original, TIntermNode *replacement);
Olli Etuahofc0e2bc2015-04-16 13:39:56 +0300442 bool replaceChildNodeWithMultiple(TIntermNode *original, TIntermSequence replacements);
Olli Etuahoa6f22092015-05-08 18:31:10 +0300443 bool insertChildNodes(TIntermSequence::size_type position, TIntermSequence insertions);
Jamie Madillb1a85f42014-08-19 15:23:24 -0400444 // Conservatively assume function calls and other aggregate operators have side-effects
445 virtual bool hasSideEffects() const { return true; }
446
447 TIntermSequence *getSequence() { return &mSequence; }
448
449 void setName(const TString &name) { mName = name; }
450 const TString &getName() const { return mName; }
451
452 void setUserDefined() { mUserDefined = true; }
453 bool isUserDefined() const { return mUserDefined; }
454
455 void setOptimize(bool optimize) { mOptimize = optimize; }
456 bool getOptimize() const { return mOptimize; }
457 void setDebug(bool debug) { mDebug = debug; }
458 bool getDebug() const { return mDebug; }
459
Corentin Wallez71d147f2015-02-11 11:15:24 -0800460 void setFunctionId(int functionId) { mFunctionId = functionId; }
461 int getFunctionId() const { return mFunctionId; }
462
Jamie Madillb1a85f42014-08-19 15:23:24 -0400463 void setUseEmulatedFunction() { mUseEmulatedFunction = true; }
464 bool getUseEmulatedFunction() { return mUseEmulatedFunction; }
465
Olli Etuahod2a67b92014-10-21 16:42:57 +0300466 void setPrecisionFromChildren();
467 void setBuiltInFunctionPrecision();
468
Jamie Madillb1a85f42014-08-19 15:23:24 -0400469 protected:
470 TIntermAggregate(const TIntermAggregate &); // disallow copy constructor
471 TIntermAggregate &operator=(const TIntermAggregate &); // disallow assignment operator
472 TIntermSequence mSequence;
473 TString mName;
474 bool mUserDefined; // used for user defined function names
Corentin Wallez71d147f2015-02-11 11:15:24 -0800475 int mFunctionId;
Jamie Madillb1a85f42014-08-19 15:23:24 -0400476
477 bool mOptimize;
478 bool mDebug;
479
480 // If set to true, replace the built-in function call with an emulated one
481 // to work around driver bugs.
482 bool mUseEmulatedFunction;
483};
484
485//
Olli Etuahoa3a36662015-02-17 13:46:51 +0200486// For if tests.
Jamie Madillb1a85f42014-08-19 15:23:24 -0400487//
488class TIntermSelection : public TIntermTyped
489{
490 public:
491 TIntermSelection(TIntermTyped *cond, TIntermNode *trueB, TIntermNode *falseB)
492 : TIntermTyped(TType(EbtVoid, EbpUndefined)),
493 mCondition(cond),
494 mTrueBlock(trueB),
495 mFalseBlock(falseB) {}
496 TIntermSelection(TIntermTyped *cond, TIntermNode *trueB, TIntermNode *falseB,
497 const TType &type)
498 : TIntermTyped(type),
499 mCondition(cond),
500 mTrueBlock(trueB),
501 mFalseBlock(falseB) {}
502
503 virtual void traverse(TIntermTraverser *);
504 virtual bool replaceChildNode(
505 TIntermNode *original, TIntermNode *replacement);
506
507 // Conservatively assume selections have side-effects
508 virtual bool hasSideEffects() const { return true; }
509
510 bool usesTernaryOperator() const { return getBasicType() != EbtVoid; }
511 TIntermNode *getCondition() const { return mCondition; }
512 TIntermNode *getTrueBlock() const { return mTrueBlock; }
513 TIntermNode *getFalseBlock() const { return mFalseBlock; }
514 TIntermSelection *getAsSelectionNode() { return this; }
515
Jamie Madillb1a85f42014-08-19 15:23:24 -0400516protected:
517 TIntermTyped *mCondition;
518 TIntermNode *mTrueBlock;
519 TIntermNode *mFalseBlock;
520};
521
Olli Etuahoa3a36662015-02-17 13:46:51 +0200522//
523// Switch statement.
524//
525class TIntermSwitch : public TIntermNode
526{
527 public:
528 TIntermSwitch(TIntermTyped *init, TIntermAggregate *statementList)
529 : TIntermNode(),
530 mInit(init),
531 mStatementList(statementList)
532 {
533 }
534
535 void traverse(TIntermTraverser *it) override;
536 bool replaceChildNode(
537 TIntermNode *original, TIntermNode *replacement) override;
538
539 TIntermSwitch *getAsSwitchNode() override { return this; }
540
Olli Etuaho01cd8af2015-02-20 10:39:20 +0200541 TIntermAggregate *getStatementList() { return mStatementList; }
Olli Etuaho2cd7a0e2015-02-27 13:57:32 +0200542 void setStatementList(TIntermAggregate *statementList) { mStatementList = statementList; }
Olli Etuaho01cd8af2015-02-20 10:39:20 +0200543
Olli Etuahoa3a36662015-02-17 13:46:51 +0200544 protected:
545 TIntermTyped *mInit;
546 TIntermAggregate *mStatementList;
547};
548
549//
550// Case label.
551//
552class TIntermCase : public TIntermNode
553{
554 public:
555 TIntermCase(TIntermTyped *condition)
556 : TIntermNode(),
557 mCondition(condition)
558 {
559 }
560
561 void traverse(TIntermTraverser *it) override;
562 bool replaceChildNode(
563 TIntermNode *original, TIntermNode *replacement) override;
564
565 TIntermCase *getAsCaseNode() override { return this; }
566
567 bool hasCondition() const { return mCondition != nullptr; }
568 TIntermTyped *getCondition() const { return mCondition; }
569
570 protected:
571 TIntermTyped *mCondition;
572};
573
Jamie Madillb1a85f42014-08-19 15:23:24 -0400574enum Visit
575{
576 PreVisit,
577 InVisit,
578 PostVisit
579};
580
581//
582// For traversing the tree. User should derive from this,
583// put their traversal specific data in it, and then pass
584// it to a Traverse method.
585//
586// When using this, just fill in the methods for nodes you want visited.
587// Return false from a pre-visit to skip visiting that node's subtree.
588//
Jamie Madillf0d10f82015-03-31 12:56:52 -0400589class TIntermTraverser : angle::NonCopyable
Jamie Madillb1a85f42014-08-19 15:23:24 -0400590{
591 public:
592 POOL_ALLOCATOR_NEW_DELETE();
Olli Etuaho3d0d9a42015-06-01 12:16:36 +0300593 TIntermTraverser(bool preVisit, bool inVisit, bool postVisit)
Jamie Madillb1a85f42014-08-19 15:23:24 -0400594 : preVisit(preVisit),
595 inVisit(inVisit),
596 postVisit(postVisit),
Jamie Madillb1a85f42014-08-19 15:23:24 -0400597 mDepth(0),
Olli Etuahod4f303e2015-05-20 17:09:06 +0300598 mMaxDepth(0),
599 mTemporaryIndex(nullptr)
600 {
601 }
Jamie Madillb1a85f42014-08-19 15:23:24 -0400602 virtual ~TIntermTraverser() {}
603
604 virtual void visitSymbol(TIntermSymbol *) {}
605 virtual void visitRaw(TIntermRaw *) {}
606 virtual void visitConstantUnion(TIntermConstantUnion *) {}
607 virtual bool visitBinary(Visit, TIntermBinary *) { return true; }
608 virtual bool visitUnary(Visit, TIntermUnary *) { return true; }
609 virtual bool visitSelection(Visit, TIntermSelection *) { return true; }
Olli Etuahoa3a36662015-02-17 13:46:51 +0200610 virtual bool visitSwitch(Visit, TIntermSwitch *) { return true; }
611 virtual bool visitCase(Visit, TIntermCase *) { return true; }
Jamie Madillb1a85f42014-08-19 15:23:24 -0400612 virtual bool visitAggregate(Visit, TIntermAggregate *) { return true; }
613 virtual bool visitLoop(Visit, TIntermLoop *) { return true; }
614 virtual bool visitBranch(Visit, TIntermBranch *) { return true; }
615
616 int getMaxDepth() const { return mMaxDepth; }
617
618 void incrementDepth(TIntermNode *current)
619 {
620 mDepth++;
621 mMaxDepth = std::max(mMaxDepth, mDepth);
622 mPath.push_back(current);
623 }
624
625 void decrementDepth()
626 {
627 mDepth--;
628 mPath.pop_back();
629 }
630
631 TIntermNode *getParentNode()
632 {
633 return mPath.size() == 0 ? NULL : mPath.back();
634 }
635
Olli Etuaho56eea882015-05-18 12:41:03 +0300636 void pushParentBlock(TIntermAggregate *node);
637 void incrementParentBlockPos();
638 void popParentBlock();
639
Olli Etuahoa5316a12015-05-15 15:25:16 +0300640 bool parentNodeIsBlock()
641 {
642 return !mParentBlockStack.empty() && getParentNode() == mParentBlockStack.back().node;
643 }
644
Jamie Madillb1a85f42014-08-19 15:23:24 -0400645 // Return the original name if hash function pointer is NULL;
646 // otherwise return the hashed name.
647 static TString hash(const TString& name, ShHashFunction64 hashFunction);
648
649 const bool preVisit;
650 const bool inVisit;
651 const bool postVisit;
Jamie Madillb1a85f42014-08-19 15:23:24 -0400652
Olli Etuaho853dc1a2014-11-06 17:25:48 +0200653 // If traversers need to replace nodes, they can add the replacements in
Olli Etuahofc0e2bc2015-04-16 13:39:56 +0300654 // mReplacements/mMultiReplacements during traversal and the user of the traverser should call
Olli Etuaho853dc1a2014-11-06 17:25:48 +0200655 // this function after traversal to perform them.
656 void updateTree();
657
Olli Etuahod4f303e2015-05-20 17:09:06 +0300658 // Start creating temporary symbols from the given temporary symbol index + 1.
659 void useTemporaryIndex(unsigned int *temporaryIndex);
660
Jamie Madillb1a85f42014-08-19 15:23:24 -0400661 protected:
662 int mDepth;
663 int mMaxDepth;
664
665 // All the nodes from root to the current node's parent during traversing.
666 TVector<TIntermNode *> mPath;
Olli Etuaho853dc1a2014-11-06 17:25:48 +0200667
Olli Etuahofc0e2bc2015-04-16 13:39:56 +0300668 // To replace a single node with another on the parent node
Olli Etuaho853dc1a2014-11-06 17:25:48 +0200669 struct NodeUpdateEntry
670 {
671 NodeUpdateEntry(TIntermNode *_parent,
672 TIntermNode *_original,
673 TIntermNode *_replacement,
674 bool _originalBecomesChildOfReplacement)
675 : parent(_parent),
676 original(_original),
677 replacement(_replacement),
678 originalBecomesChildOfReplacement(_originalBecomesChildOfReplacement) {}
679
680 TIntermNode *parent;
681 TIntermNode *original;
682 TIntermNode *replacement;
683 bool originalBecomesChildOfReplacement;
684 };
685
Olli Etuahofc0e2bc2015-04-16 13:39:56 +0300686 // To replace a single node with multiple nodes on the parent aggregate node
687 struct NodeReplaceWithMultipleEntry
688 {
689 NodeReplaceWithMultipleEntry(TIntermAggregate *_parent, TIntermNode *_original, TIntermSequence _replacements)
690 : parent(_parent),
691 original(_original),
692 replacements(_replacements)
693 {
694 }
695
696 TIntermAggregate *parent;
697 TIntermNode *original;
698 TIntermSequence replacements;
699 };
700
Olli Etuahoa6f22092015-05-08 18:31:10 +0300701 // To insert multiple nodes on the parent aggregate node
702 struct NodeInsertMultipleEntry
703 {
704 NodeInsertMultipleEntry(TIntermAggregate *_parent, TIntermSequence::size_type _position, TIntermSequence _insertions)
705 : parent(_parent),
706 position(_position),
707 insertions(_insertions)
708 {
709 }
710
711 TIntermAggregate *parent;
712 TIntermSequence::size_type position;
713 TIntermSequence insertions;
714 };
715
Olli Etuaho853dc1a2014-11-06 17:25:48 +0200716 // During traversing, save all the changes that need to happen into
Olli Etuahofc0e2bc2015-04-16 13:39:56 +0300717 // mReplacements/mMultiReplacements, then do them by calling updateTree().
718 // Multi replacements are processed after single replacements.
Olli Etuaho853dc1a2014-11-06 17:25:48 +0200719 std::vector<NodeUpdateEntry> mReplacements;
Olli Etuahofc0e2bc2015-04-16 13:39:56 +0300720 std::vector<NodeReplaceWithMultipleEntry> mMultiReplacements;
Olli Etuahoa6f22092015-05-08 18:31:10 +0300721 std::vector<NodeInsertMultipleEntry> mInsertions;
Olli Etuaho56eea882015-05-18 12:41:03 +0300722
723 // Helper to insert statements in the parent block (sequence) of the node currently being traversed.
724 // The statements will be inserted before the node being traversed once updateTree is called.
725 // Should only be called during PreVisit or PostVisit from sequence nodes.
726 // Note that inserting more than one set of nodes to the same parent node on a single updateTree call is not
727 // supported.
728 void insertStatementsInParentBlock(const TIntermSequence &insertions);
729
Olli Etuahod4f303e2015-05-20 17:09:06 +0300730 // Helper to create a temporary symbol node.
731 TIntermSymbol *createTempSymbol(const TType &type);
Olli Etuaho4f1af782015-05-25 11:55:07 +0300732 // Create a node that declares but doesn't initialize a temporary symbol.
733 TIntermAggregate *createTempDeclaration(const TType &type);
Olli Etuahod4f303e2015-05-20 17:09:06 +0300734 // Create a node that initializes the current temporary symbol with initializer.
735 TIntermAggregate *createTempInitDeclaration(TIntermTyped *initializer);
736 // Create a node that assigns rightNode to the current temporary symbol.
737 TIntermBinary *createTempAssignment(TIntermTyped *rightNode);
738 // Increment temporary symbol index.
739 void nextTemporaryIndex();
740
Olli Etuaho56eea882015-05-18 12:41:03 +0300741 private:
742 struct ParentBlock
743 {
744 ParentBlock(TIntermAggregate *nodeIn, TIntermSequence::size_type posIn)
745 : node(nodeIn),
746 pos(posIn)
747 {
748 }
749
750 TIntermAggregate *node;
751 TIntermSequence::size_type pos;
752 };
753 // All the code blocks from the root to the current node's parent during traversal.
754 std::vector<ParentBlock> mParentBlockStack;
Olli Etuahod4f303e2015-05-20 17:09:06 +0300755
756 unsigned int *mTemporaryIndex;
Jamie Madillb1a85f42014-08-19 15:23:24 -0400757};
758
759//
760// For traversing the tree, and computing max depth.
761// Takes a maximum depth limit to prevent stack overflow.
762//
763class TMaxDepthTraverser : public TIntermTraverser
764{
765 public:
766 POOL_ALLOCATOR_NEW_DELETE();
767 TMaxDepthTraverser(int depthLimit)
Olli Etuaho64f0be92015-06-03 17:38:34 +0300768 : TIntermTraverser(true, true, false),
Jamie Madillb1a85f42014-08-19 15:23:24 -0400769 mDepthLimit(depthLimit) { }
770
771 virtual bool visitBinary(Visit, TIntermBinary *) { return depthCheck(); }
772 virtual bool visitUnary(Visit, TIntermUnary *) { return depthCheck(); }
773 virtual bool visitSelection(Visit, TIntermSelection *) { return depthCheck(); }
774 virtual bool visitAggregate(Visit, TIntermAggregate *) { return depthCheck(); }
775 virtual bool visitLoop(Visit, TIntermLoop *) { return depthCheck(); }
776 virtual bool visitBranch(Visit, TIntermBranch *) { return depthCheck(); }
777
Jamie Madill80d934b2015-02-19 10:16:12 -0500778 protected:
Jamie Madillb1a85f42014-08-19 15:23:24 -0400779 bool depthCheck() const { return mMaxDepth < mDepthLimit; }
780
781 int mDepthLimit;
782};
783
Geoff Lang0a73dd82014-11-19 16:18:08 -0500784#endif // COMPILER_TRANSLATOR_INTERMNODE_H_