1//
2// Copyright (c) 2002-2010 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#include "compiler/translator/tree_util/IntermTraverse.h"
8
9#include "compiler/translator/InfoSink.h"
10#include "compiler/translator/SymbolTable.h"
11#include "compiler/translator/tree_util/IntermNode_util.h"
12
13namespace sh
14{
15
16// Traverse the intermediate representation tree, and call a node type specific visit function for
17// each node. Traversal is done recursively through the node member function traverse(). Nodes with
18// children can have their whole subtree skipped if preVisit is turned on and the type specific
19// function returns false.
20template <typename T>
21void TIntermTraverser::traverse(T *node)
22{
23 ScopedNodeInTraversalPath addToPath(this, node);
24 if (!addToPath.isWithinDepthLimit())
25 return;
26
27 bool visit = true;
28
29 // Visit the node before children if pre-visiting.
30 if (preVisit)
31 visit = node->visit(PreVisit, this);
32
33 if (visit)
34 {
35 size_t childIndex = 0;
36 size_t childCount = node->getChildCount();
37
38 while (childIndex < childCount && visit)
39 {
40 node->getChildNode(childIndex)->traverse(this);
41 if (inVisit && childIndex != childCount - 1)
42 {
43 visit = node->visit(InVisit, this);
44 }
45 ++childIndex;
46 }
47
48 if (visit && postVisit)
49 node->visit(PostVisit, this);
50 }
51}
52
53void TIntermNode::traverse(TIntermTraverser *it)
54{
55 it->traverse(this);
56}
57
58void TIntermSymbol::traverse(TIntermTraverser *it)
59{
60 TIntermTraverser::ScopedNodeInTraversalPath addToPath(it, this);
61 it->visitSymbol(this);
62}
63
64void TIntermConstantUnion::traverse(TIntermTraverser *it)
65{
66 TIntermTraverser::ScopedNodeInTraversalPath addToPath(it, this);
67 it->visitConstantUnion(this);
68}
69
70void TIntermFunctionPrototype::traverse(TIntermTraverser *it)
71{
72 TIntermTraverser::ScopedNodeInTraversalPath addToPath(it, this);
73 it->visitFunctionPrototype(this);
74}
75
76void TIntermBinary::traverse(TIntermTraverser *it)
77{
78 it->traverseBinary(this);
79}
80
81void TIntermUnary::traverse(TIntermTraverser *it)
82{
83 it->traverseUnary(this);
84}
85
86void TIntermFunctionDefinition::traverse(TIntermTraverser *it)
87{
88 it->traverseFunctionDefinition(this);
89}
90
91void TIntermBlock::traverse(TIntermTraverser *it)
92{
93 it->traverseBlock(this);
94}
95
96void TIntermAggregate::traverse(TIntermTraverser *it)
97{
98 it->traverseAggregate(this);
99}
100
101void TIntermLoop::traverse(TIntermTraverser *it)
102{
103 it->traverseLoop(this);
104}
105
106void TIntermPreprocessorDirective::traverse(TIntermTraverser *it)
107{
108 it->visitPreprocessorDirective(this);
109}
110
111bool TIntermSymbol::visit(Visit visit, TIntermTraverser *it)
112{
113 it->visitSymbol(this);
114 return false;
115}
116
117bool TIntermConstantUnion::visit(Visit visit, TIntermTraverser *it)
118{
119 it->visitConstantUnion(this);
120 return false;
121}
122
123bool TIntermFunctionPrototype::visit(Visit visit, TIntermTraverser *it)
124{
125 it->visitFunctionPrototype(this);
126 return false;
127}
128
129bool TIntermFunctionDefinition::visit(Visit visit, TIntermTraverser *it)
130{
131 return it->visitFunctionDefinition(visit, this);
132}
133
134bool TIntermUnary::visit(Visit visit, TIntermTraverser *it)
135{
136 return it->visitUnary(visit, this);
137}
138
139bool TIntermSwizzle::visit(Visit visit, TIntermTraverser *it)
140{
141 return it->visitSwizzle(visit, this);
142}
143
144bool TIntermBinary::visit(Visit visit, TIntermTraverser *it)
145{
146 return it->visitBinary(visit, this);
147}
148
149bool TIntermTernary::visit(Visit visit, TIntermTraverser *it)
150{
151 return it->visitTernary(visit, this);
152}
153
154bool TIntermAggregate::visit(Visit visit, TIntermTraverser *it)
155{
156 return it->visitAggregate(visit, this);
157}
158
159bool TIntermDeclaration::visit(Visit visit, TIntermTraverser *it)
160{
161 return it->visitDeclaration(visit, this);
162}
163
164bool TIntermInvariantDeclaration::visit(Visit visit, TIntermTraverser *it)
165{
166 return it->visitInvariantDeclaration(visit, this);
167}
168
169bool TIntermBlock::visit(Visit visit, TIntermTraverser *it)
170{
171 return it->visitBlock(visit, this);
172}
173
174bool TIntermIfElse::visit(Visit visit, TIntermTraverser *it)
175{
176 return it->visitIfElse(visit, this);
177}
178
179bool TIntermLoop::visit(Visit visit, TIntermTraverser *it)
180{
181 return it->visitLoop(visit, this);
182}
183
184bool TIntermBranch::visit(Visit visit, TIntermTraverser *it)
185{
186 return it->visitBranch(visit, this);
187}
188
189bool TIntermSwitch::visit(Visit visit, TIntermTraverser *it)
190{
191 return it->visitSwitch(visit, this);
192}
193
194bool TIntermCase::visit(Visit visit, TIntermTraverser *it)
195{
196 return it->visitCase(visit, this);
197}
198
199bool TIntermPreprocessorDirective::visit(Visit visit, TIntermTraverser *it)
200{
201 it->visitPreprocessorDirective(this);
202 return false;
203}
204
205TIntermTraverser::TIntermTraverser(bool preVisit,
206 bool inVisit,
207 bool postVisit,
208 TSymbolTable *symbolTable)
209 : preVisit(preVisit),
210 inVisit(inVisit),
211 postVisit(postVisit),
212 mMaxDepth(0),
213 mMaxAllowedDepth(std::numeric_limits<int>::max()),
214 mInGlobalScope(true),
215 mSymbolTable(symbolTable)
216{
217 // Only enabling inVisit is not supported.
218 ASSERT(!(inVisit && !preVisit && !postVisit));
219}
220
221TIntermTraverser::~TIntermTraverser() {}
222
223void TIntermTraverser::setMaxAllowedDepth(int depth)
224{
225 mMaxAllowedDepth = depth;
226}
227
228const TIntermBlock *TIntermTraverser::getParentBlock() const
229{
230 if (!mParentBlockStack.empty())
231 {
232 return mParentBlockStack.back().node;
233 }
234 return nullptr;
235}
236
237void TIntermTraverser::pushParentBlock(TIntermBlock *node)
238{
239 mParentBlockStack.push_back(ParentBlock(node, 0));
240}
241
242void TIntermTraverser::incrementParentBlockPos()
243{
244 ++mParentBlockStack.back().pos;
245}
246
247void TIntermTraverser::popParentBlock()
248{
249 ASSERT(!mParentBlockStack.empty());
250 mParentBlockStack.pop_back();
251}
252
253void TIntermTraverser::insertStatementsInParentBlock(const TIntermSequence &insertions)
254{
255 TIntermSequence emptyInsertionsAfter;
256 insertStatementsInParentBlock(insertions, emptyInsertionsAfter);
257}
258
259void TIntermTraverser::insertStatementsInParentBlock(const TIntermSequence &insertionsBefore,
260 const TIntermSequence &insertionsAfter)
261{
262 ASSERT(!mParentBlockStack.empty());
263 ParentBlock &parentBlock = mParentBlockStack.back();
264 if (mPath.back() == parentBlock.node)
265 {
266 ASSERT(mParentBlockStack.size() >= 2u);
267 // The current node is a block node, so the parent block is not the topmost one in the block
268 // stack, but the one below that.
269 parentBlock = mParentBlockStack.at(mParentBlockStack.size() - 2u);
270 }
271 NodeInsertMultipleEntry insert(parentBlock.node, parentBlock.pos, insertionsBefore,
272 insertionsAfter);
273 mInsertions.push_back(insert);
274}
275
276void TIntermTraverser::insertStatementInParentBlock(TIntermNode *statement)
277{
278 TIntermSequence insertions;
279 insertions.push_back(statement);
280 insertStatementsInParentBlock(insertions);
281}
282
283void TIntermTraverser::insertStatementsInBlockAtPosition(TIntermBlock *parent,
284 size_t position,
285 const TIntermSequence &insertionsBefore,
286 const TIntermSequence &insertionsAfter)
287{
288 ASSERT(parent);
289 ASSERT(position >= 0);
290 ASSERT(position < parent->getChildCount());
291
292 mInsertions.emplace_back(parent, position, insertionsBefore, insertionsAfter);
293}
294
295void TLValueTrackingTraverser::setInFunctionCallOutParameter(bool inOutParameter)
296{
297 mInFunctionCallOutParameter = inOutParameter;
298}
299
300bool TLValueTrackingTraverser::isInFunctionCallOutParameter() const
301{
302 return mInFunctionCallOutParameter;
303}
304
305void TIntermTraverser::traverseBinary(TIntermBinary *node)
306{
307 traverse(node);
308}
309
310void TLValueTrackingTraverser::traverseBinary(TIntermBinary *node)
311{
312 ScopedNodeInTraversalPath addToPath(this, node);
313 if (!addToPath.isWithinDepthLimit())
314 return;
315
316 bool visit = true;
317
318 // visit the node before children if pre-visiting.
319 if (preVisit)
320 visit = node->visit(PreVisit, this);
321
322 // Visit the children, in the right order.
323 if (visit)
324 {
325 if (node->isAssignment())
326 {
327 ASSERT(!isLValueRequiredHere());
328 setOperatorRequiresLValue(true);
329 }
330
331 node->getLeft()->traverse(this);
332
333 if (node->isAssignment())
334 setOperatorRequiresLValue(false);
335
336 if (inVisit)
337 visit = node->visit(InVisit, this);
338
339 if (visit)
340 {
341 // Some binary operations like indexing can be inside an expression which must be an
342 // l-value.
343 bool parentOperatorRequiresLValue = operatorRequiresLValue();
344 bool parentInFunctionCallOutParameter = isInFunctionCallOutParameter();
345
346 // Index is not required to be an l-value even when the surrounding expression is
347 // required to be an l-value.
348 TOperator op = node->getOp();
349 if (op == EOpIndexDirect || op == EOpIndexDirectInterfaceBlock ||
350 op == EOpIndexDirectStruct || op == EOpIndexIndirect)
351 {
352 setOperatorRequiresLValue(false);
353 setInFunctionCallOutParameter(false);
354 }
355
356 node->getRight()->traverse(this);
357
358 setOperatorRequiresLValue(parentOperatorRequiresLValue);
359 setInFunctionCallOutParameter(parentInFunctionCallOutParameter);
360
361 // Visit the node after the children, if requested and the traversal
362 // hasn't been cancelled yet.
363 if (postVisit)
364 visit = node->visit(PostVisit, this);
365 }
366 }
367}
368
369void TIntermTraverser::traverseUnary(TIntermUnary *node)
370{
371 traverse(node);
372}
373
374void TLValueTrackingTraverser::traverseUnary(TIntermUnary *node)
375{
376 ScopedNodeInTraversalPath addToPath(this, node);
377 if (!addToPath.isWithinDepthLimit())
378 return;
379
380 bool visit = true;
381
382 if (preVisit)
383 visit = node->visit(PreVisit, this);
384
385 if (visit)
386 {
387 ASSERT(!operatorRequiresLValue());
388 switch (node->getOp())
389 {
390 case EOpPostIncrement:
391 case EOpPostDecrement:
392 case EOpPreIncrement:
393 case EOpPreDecrement:
394 setOperatorRequiresLValue(true);
395 break;
396 default:
397 break;
398 }
399
400 node->getOperand()->traverse(this);
401
402 setOperatorRequiresLValue(false);
403
404 if (postVisit)
405 visit = node->visit(PostVisit, this);
406 }
407}
408
409// Traverse a function definition node. This keeps track of global scope.
410void TIntermTraverser::traverseFunctionDefinition(TIntermFunctionDefinition *node)
411{
412 ScopedNodeInTraversalPath addToPath(this, node);
413 if (!addToPath.isWithinDepthLimit())
414 return;
415
416 bool visit = true;
417
418 if (preVisit)
419 visit = node->visit(PreVisit, this);
420
421 if (visit)
422 {
423 node->getFunctionPrototype()->traverse(this);
424 if (inVisit)
425 visit = node->visit(InVisit, this);
426 if (visit)
427 {
428 mInGlobalScope = false;
429 node->getBody()->traverse(this);
430 mInGlobalScope = true;
431 if (postVisit)
432 visit = node->visit(PostVisit, this);
433 }
434 }
435}
436
437// Traverse a block node. This keeps track of the position of traversed child nodes within the block
438// so that nodes may be inserted before or after them.
439void TIntermTraverser::traverseBlock(TIntermBlock *node)
440{
441 ScopedNodeInTraversalPath addToPath(this, node);
442 if (!addToPath.isWithinDepthLimit())
443 return;
444
445 pushParentBlock(node);
446
447 bool visit = true;
448
449 TIntermSequence *sequence = node->getSequence();
450
451 if (preVisit)
452 visit = node->visit(PreVisit, this);
453
454 if (visit)
455 {
456 for (auto *child : *sequence)
457 {
458 if (visit)
459 {
460 child->traverse(this);
461 if (inVisit)
462 {
463 if (child != sequence->back())
464 visit = node->visit(InVisit, this);
465 }
466
467 incrementParentBlockPos();
468 }
469 }
470
471 if (visit && postVisit)
472 visit = node->visit(PostVisit, this);
473 }
474
475 popParentBlock();
476}
477
478void TIntermTraverser::traverseAggregate(TIntermAggregate *node)
479{
480 traverse(node);
481}
482
483bool TIntermTraverser::CompareInsertion(const NodeInsertMultipleEntry &a,
484 const NodeInsertMultipleEntry &b)
485{
486 if (a.parent != b.parent)
487 {
488 return a.parent > b.parent;
489 }
490 return a.position > b.position;
491}
492
493void TIntermTraverser::updateTree()
494{
495 // Sort the insertions so that insertion position is decreasing. This way multiple insertions to
496 // the same parent node are handled correctly.
497 std::sort(mInsertions.begin(), mInsertions.end(), CompareInsertion);
498 for (size_t ii = 0; ii < mInsertions.size(); ++ii)
499 {
500 // We can't know here what the intended ordering of two insertions to the same position is,
501 // so it is not supported.
502 ASSERT(ii == 0 || mInsertions[ii].position != mInsertions[ii - 1].position ||
503 mInsertions[ii].parent != mInsertions[ii - 1].parent);
504 const NodeInsertMultipleEntry &insertion = mInsertions[ii];
505 ASSERT(insertion.parent);
506 if (!insertion.insertionsAfter.empty())
507 {
508 bool inserted = insertion.parent->insertChildNodes(insertion.position + 1,
509 insertion.insertionsAfter);
510 ASSERT(inserted);
511 }
512 if (!insertion.insertionsBefore.empty())
513 {
514 bool inserted =
515 insertion.parent->insertChildNodes(insertion.position, insertion.insertionsBefore);
516 ASSERT(inserted);
517 }
518 }
519 for (size_t ii = 0; ii < mReplacements.size(); ++ii)
520 {
521 const NodeUpdateEntry &replacement = mReplacements[ii];
522 ASSERT(replacement.parent);
523 bool replaced =
524 replacement.parent->replaceChildNode(replacement.original, replacement.replacement);
525 ASSERT(replaced);
526
527 if (!replacement.originalBecomesChildOfReplacement)
528 {
529 // In AST traversing, a parent is visited before its children.
530 // After we replace a node, if its immediate child is to
531 // be replaced, we need to make sure we don't update the replaced
532 // node; instead, we update the replacement node.
533 for (size_t jj = ii + 1; jj < mReplacements.size(); ++jj)
534 {
535 NodeUpdateEntry &replacement2 = mReplacements[jj];
536 if (replacement2.parent == replacement.original)
537 replacement2.parent = replacement.replacement;
538 }
539 }
540 }
541 for (size_t ii = 0; ii < mMultiReplacements.size(); ++ii)
542 {
543 const NodeReplaceWithMultipleEntry &replacement = mMultiReplacements[ii];
544 ASSERT(replacement.parent);
545 bool replaced = replacement.parent->replaceChildNodeWithMultiple(replacement.original,
546 replacement.replacements);
547 ASSERT(replaced);
548 }
549
550 clearReplacementQueue();
551}
552
553void TIntermTraverser::clearReplacementQueue()
554{
555 mReplacements.clear();
556 mMultiReplacements.clear();
557 mInsertions.clear();
558}
559
560void TIntermTraverser::queueReplacement(TIntermNode *replacement, OriginalNode originalStatus)
561{
562 queueReplacementWithParent(getParentNode(), mPath.back(), replacement, originalStatus);
563}
564
565void TIntermTraverser::queueReplacementWithParent(TIntermNode *parent,
566 TIntermNode *original,
567 TIntermNode *replacement,
568 OriginalNode originalStatus)
569{
570 bool originalBecomesChild = (originalStatus == OriginalNode::BECOMES_CHILD);
571 mReplacements.push_back(NodeUpdateEntry(parent, original, replacement, originalBecomesChild));
572}
573
574TLValueTrackingTraverser::TLValueTrackingTraverser(bool preVisit,
575 bool inVisit,
576 bool postVisit,
577 TSymbolTable *symbolTable)
578 : TIntermTraverser(preVisit, inVisit, postVisit, symbolTable),
579 mOperatorRequiresLValue(false),
580 mInFunctionCallOutParameter(false)
581{
582 ASSERT(symbolTable);
583}
584
585void TLValueTrackingTraverser::traverseAggregate(TIntermAggregate *node)
586{
587 ScopedNodeInTraversalPath addToPath(this, node);
588 if (!addToPath.isWithinDepthLimit())
589 return;
590
591 bool visit = true;
592
593 TIntermSequence *sequence = node->getSequence();
594
595 if (preVisit)
596 visit = node->visit(PreVisit, this);
597
598 if (visit)
599 {
600 size_t paramIndex = 0u;
601 for (auto *child : *sequence)
602 {
603 if (visit)
604 {
605 if (node->getFunction())
606 {
607 // Both built-ins and user defined functions should have the function symbol
608 // set.
609 ASSERT(paramIndex < node->getFunction()->getParamCount());
610 TQualifier qualifier =
611 node->getFunction()->getParam(paramIndex)->getType().getQualifier();
612 setInFunctionCallOutParameter(qualifier == EvqOut || qualifier == EvqInOut);
613 ++paramIndex;
614 }
615 else
616 {
617 ASSERT(node->isConstructor());
618 }
619 child->traverse(this);
620 if (inVisit)
621 {
622 if (child != sequence->back())
623 visit = node->visit(InVisit, this);
624 }
625 }
626 }
627 setInFunctionCallOutParameter(false);
628
629 if (visit && postVisit)
630 visit = node->visit(PostVisit, this);
631 }
632}
633
634void TIntermTraverser::traverseLoop(TIntermLoop *node)
635{
636 traverse(node);
637}
638} // namespace sh
639