1 //
2 // Copyright 2002 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/SymbolTable.h"
8 #include "compiler/translator/tree_util/IntermTraverse.h"
9
10 namespace sh
11 {
12
13 namespace
14 {
15
OutputFunction(TInfoSinkBase & out,const char * str,const TFunction * func)16 void OutputFunction(TInfoSinkBase &out, const char *str, const TFunction *func)
17 {
18 const char *internal =
19 (func->symbolType() == SymbolType::AngleInternal) ? " (internal function)" : "";
20 out << str << internal << ": " << func->name() << " (symbol id " << func->uniqueId().get()
21 << ")";
22 }
23
24 // Two purposes:
25 // 1. Show an example of how to iterate tree. Functions can also directly call traverse() on
26 // children themselves to have finer grained control over the process than shown here, though
27 // that's not recommended if it can be avoided.
28 // 2. Print out a text based description of the tree.
29
30 // The traverser subclass is used to carry along data from node to node in the traversal.
31 class TOutputTraverser : public TIntermTraverser
32 {
33 public:
TOutputTraverser(TInfoSinkBase & out)34 TOutputTraverser(TInfoSinkBase &out)
35 : TIntermTraverser(true, false, false), mOut(out), mIndentDepth(0)
36 {}
37
38 protected:
39 void visitSymbol(TIntermSymbol *) override;
40 void visitConstantUnion(TIntermConstantUnion *) override;
41 bool visitSwizzle(Visit visit, TIntermSwizzle *node) override;
42 bool visitBinary(Visit visit, TIntermBinary *) override;
43 bool visitUnary(Visit visit, TIntermUnary *) override;
44 bool visitTernary(Visit visit, TIntermTernary *node) override;
45 bool visitIfElse(Visit visit, TIntermIfElse *node) override;
46 bool visitSwitch(Visit visit, TIntermSwitch *node) override;
47 bool visitCase(Visit visit, TIntermCase *node) override;
48 void visitFunctionPrototype(TIntermFunctionPrototype *node) override;
49 bool visitFunctionDefinition(Visit visit, TIntermFunctionDefinition *node) override;
50 bool visitAggregate(Visit visit, TIntermAggregate *) override;
51 bool visitBlock(Visit visit, TIntermBlock *) override;
52 bool visitGlobalQualifierDeclaration(Visit visit,
53 TIntermGlobalQualifierDeclaration *node) override;
54 bool visitDeclaration(Visit visit, TIntermDeclaration *node) override;
55 bool visitLoop(Visit visit, TIntermLoop *) override;
56 bool visitBranch(Visit visit, TIntermBranch *) override;
57
getCurrentIndentDepth() const58 int getCurrentIndentDepth() const { return mIndentDepth + getCurrentTraversalDepth(); }
59
60 TInfoSinkBase &mOut;
61 int mIndentDepth;
62 };
63
64 //
65 // Helper functions for printing, not part of traversing.
66 //
OutputTreeText(TInfoSinkBase & out,TIntermNode * node,const int depth)67 void OutputTreeText(TInfoSinkBase &out, TIntermNode *node, const int depth)
68 {
69 int i;
70
71 out.location(node->getLine().first_file, node->getLine().first_line);
72
73 for (i = 0; i < depth; ++i)
74 out << " ";
75 }
76
77 //
78 // The rest of the file are the traversal functions. The last one
79 // is the one that starts the traversal.
80 //
81 // Return true from interior nodes to have the external traversal
82 // continue on to children. If you process children yourself,
83 // return false.
84 //
85
visitSymbol(TIntermSymbol * node)86 void TOutputTraverser::visitSymbol(TIntermSymbol *node)
87 {
88 OutputTreeText(mOut, node, getCurrentIndentDepth());
89
90 if (node->variable().symbolType() == SymbolType::Empty)
91 {
92 mOut << "''";
93 }
94 else
95 {
96 mOut << "'" << node->getName() << "' ";
97 }
98 mOut << "(symbol id " << node->uniqueId().get() << ") ";
99 mOut << "(" << node->getType() << ")";
100 mOut << "\n";
101 }
102
visitSwizzle(Visit visit,TIntermSwizzle * node)103 bool TOutputTraverser::visitSwizzle(Visit visit, TIntermSwizzle *node)
104 {
105 OutputTreeText(mOut, node, getCurrentIndentDepth());
106 mOut << "vector swizzle (";
107 node->writeOffsetsAsXYZW(&mOut);
108 mOut << ")";
109
110 mOut << " (" << node->getType() << ")";
111 mOut << "\n";
112 return true;
113 }
114
visitBinary(Visit visit,TIntermBinary * node)115 bool TOutputTraverser::visitBinary(Visit visit, TIntermBinary *node)
116 {
117 OutputTreeText(mOut, node, getCurrentIndentDepth());
118
119 switch (node->getOp())
120 {
121 case EOpComma:
122 mOut << "comma";
123 break;
124 case EOpAssign:
125 mOut << "move second child to first child";
126 break;
127 case EOpInitialize:
128 mOut << "initialize first child with second child";
129 break;
130 case EOpAddAssign:
131 mOut << "add second child into first child";
132 break;
133 case EOpSubAssign:
134 mOut << "subtract second child into first child";
135 break;
136 case EOpMulAssign:
137 mOut << "multiply second child into first child";
138 break;
139 case EOpVectorTimesMatrixAssign:
140 mOut << "matrix mult second child into first child";
141 break;
142 case EOpVectorTimesScalarAssign:
143 mOut << "vector scale second child into first child";
144 break;
145 case EOpMatrixTimesScalarAssign:
146 mOut << "matrix scale second child into first child";
147 break;
148 case EOpMatrixTimesMatrixAssign:
149 mOut << "matrix mult second child into first child";
150 break;
151 case EOpDivAssign:
152 mOut << "divide second child into first child";
153 break;
154 case EOpIModAssign:
155 mOut << "modulo second child into first child";
156 break;
157 case EOpBitShiftLeftAssign:
158 mOut << "bit-wise shift first child left by second child";
159 break;
160 case EOpBitShiftRightAssign:
161 mOut << "bit-wise shift first child right by second child";
162 break;
163 case EOpBitwiseAndAssign:
164 mOut << "bit-wise and second child into first child";
165 break;
166 case EOpBitwiseXorAssign:
167 mOut << "bit-wise xor second child into first child";
168 break;
169 case EOpBitwiseOrAssign:
170 mOut << "bit-wise or second child into first child";
171 break;
172
173 case EOpIndexDirect:
174 mOut << "direct index";
175 break;
176 case EOpIndexIndirect:
177 mOut << "indirect index";
178 break;
179 case EOpIndexDirectStruct:
180 mOut << "direct index for structure";
181 break;
182 case EOpIndexDirectInterfaceBlock:
183 mOut << "direct index for interface block";
184 break;
185
186 case EOpAdd:
187 mOut << "add";
188 break;
189 case EOpSub:
190 mOut << "subtract";
191 break;
192 case EOpMul:
193 mOut << "component-wise multiply";
194 break;
195 case EOpDiv:
196 mOut << "divide";
197 break;
198 case EOpIMod:
199 mOut << "modulo";
200 break;
201 case EOpBitShiftLeft:
202 mOut << "bit-wise shift left";
203 break;
204 case EOpBitShiftRight:
205 mOut << "bit-wise shift right";
206 break;
207 case EOpBitwiseAnd:
208 mOut << "bit-wise and";
209 break;
210 case EOpBitwiseXor:
211 mOut << "bit-wise xor";
212 break;
213 case EOpBitwiseOr:
214 mOut << "bit-wise or";
215 break;
216
217 case EOpEqual:
218 mOut << "Compare Equal";
219 break;
220 case EOpNotEqual:
221 mOut << "Compare Not Equal";
222 break;
223 case EOpLessThan:
224 mOut << "Compare Less Than";
225 break;
226 case EOpGreaterThan:
227 mOut << "Compare Greater Than";
228 break;
229 case EOpLessThanEqual:
230 mOut << "Compare Less Than or Equal";
231 break;
232 case EOpGreaterThanEqual:
233 mOut << "Compare Greater Than or Equal";
234 break;
235
236 case EOpVectorTimesScalar:
237 mOut << "vector-scale";
238 break;
239 case EOpVectorTimesMatrix:
240 mOut << "vector-times-matrix";
241 break;
242 case EOpMatrixTimesVector:
243 mOut << "matrix-times-vector";
244 break;
245 case EOpMatrixTimesScalar:
246 mOut << "matrix-scale";
247 break;
248 case EOpMatrixTimesMatrix:
249 mOut << "matrix-multiply";
250 break;
251
252 case EOpLogicalOr:
253 mOut << "logical-or";
254 break;
255 case EOpLogicalXor:
256 mOut << "logical-xor";
257 break;
258 case EOpLogicalAnd:
259 mOut << "logical-and";
260 break;
261 default:
262 mOut << "<unknown op>";
263 }
264
265 mOut << " (" << node->getType() << ")";
266
267 mOut << "\n";
268
269 // Special handling for direct indexes. Because constant
270 // unions are not aware they are struct indexes, treat them
271 // here where we have that contextual knowledge.
272 if (node->getOp() == EOpIndexDirectStruct || node->getOp() == EOpIndexDirectInterfaceBlock)
273 {
274 node->getLeft()->traverse(this);
275
276 TIntermConstantUnion *intermConstantUnion = node->getRight()->getAsConstantUnion();
277 ASSERT(intermConstantUnion);
278
279 OutputTreeText(mOut, intermConstantUnion, getCurrentIndentDepth() + 1);
280
281 // The following code finds the field name from the constant union
282 const TConstantUnion *constantUnion = intermConstantUnion->getConstantValue();
283 const TStructure *structure = node->getLeft()->getType().getStruct();
284 const TInterfaceBlock *interfaceBlock = node->getLeft()->getType().getInterfaceBlock();
285 ASSERT(structure || interfaceBlock);
286
287 const TFieldList &fields = structure ? structure->fields() : interfaceBlock->fields();
288
289 const TField *field = fields[constantUnion->getIConst()];
290
291 mOut << constantUnion->getIConst() << " (field '" << field->name() << "')";
292
293 mOut << "\n";
294
295 return false;
296 }
297
298 return true;
299 }
300
visitUnary(Visit visit,TIntermUnary * node)301 bool TOutputTraverser::visitUnary(Visit visit, TIntermUnary *node)
302 {
303 OutputTreeText(mOut, node, getCurrentIndentDepth());
304
305 const TOperator op = node->getOp();
306
307 switch (op)
308 {
309 // Give verbose names for ops that have special syntax and some built-in functions that are
310 // easy to confuse with others, but mostly use GLSL names for functions.
311 case EOpNegative:
312 mOut << "Negate value";
313 break;
314 case EOpPositive:
315 mOut << "Positive sign";
316 break;
317 case EOpLogicalNot:
318 mOut << "negation";
319 break;
320 case EOpBitwiseNot:
321 mOut << "bit-wise not";
322 break;
323
324 case EOpPostIncrement:
325 mOut << "Post-Increment";
326 break;
327 case EOpPostDecrement:
328 mOut << "Post-Decrement";
329 break;
330 case EOpPreIncrement:
331 mOut << "Pre-Increment";
332 break;
333 case EOpPreDecrement:
334 mOut << "Pre-Decrement";
335 break;
336
337 case EOpArrayLength:
338 mOut << "Array length";
339 break;
340
341 case EOpNotComponentWise:
342 mOut << "component-wise not";
343 break;
344
345 default:
346 if (BuiltInGroup::IsBuiltIn(op))
347 {
348 OutputFunction(mOut, "Call a built-in function", node->getFunction());
349 }
350 else
351 {
352 mOut << GetOperatorString(node->getOp());
353 }
354 break;
355 }
356
357 mOut << " (" << node->getType() << ")";
358
359 mOut << "\n";
360
361 return true;
362 }
363
visitFunctionDefinition(Visit visit,TIntermFunctionDefinition * node)364 bool TOutputTraverser::visitFunctionDefinition(Visit visit, TIntermFunctionDefinition *node)
365 {
366 OutputTreeText(mOut, node, getCurrentIndentDepth());
367 mOut << "Function Definition:\n";
368 return true;
369 }
370
visitGlobalQualifierDeclaration(Visit visit,TIntermGlobalQualifierDeclaration * node)371 bool TOutputTraverser::visitGlobalQualifierDeclaration(Visit visit,
372 TIntermGlobalQualifierDeclaration *node)
373 {
374 OutputTreeText(mOut, node, getCurrentIndentDepth());
375 if (node->isPrecise())
376 {
377 mOut << "Precise Declaration:\n";
378 }
379 else
380 {
381 mOut << "Invariant Declaration:\n";
382 }
383 return true;
384 }
385
visitFunctionPrototype(TIntermFunctionPrototype * node)386 void TOutputTraverser::visitFunctionPrototype(TIntermFunctionPrototype *node)
387 {
388 OutputTreeText(mOut, node, getCurrentIndentDepth());
389 OutputFunction(mOut, "Function Prototype", node->getFunction());
390 mOut << " (" << node->getType() << ")";
391 mOut << "\n";
392 size_t paramCount = node->getFunction()->getParamCount();
393 for (size_t i = 0; i < paramCount; ++i)
394 {
395 const TVariable *param = node->getFunction()->getParam(i);
396 OutputTreeText(mOut, node, getCurrentIndentDepth() + 1);
397 mOut << "parameter: " << param->name() << " (" << param->getType() << ")\n";
398 }
399 }
400
visitAggregate(Visit visit,TIntermAggregate * node)401 bool TOutputTraverser::visitAggregate(Visit visit, TIntermAggregate *node)
402 {
403 OutputTreeText(mOut, node, getCurrentIndentDepth());
404
405 const TOperator op = node->getOp();
406
407 if (op == EOpNull)
408 {
409 mOut.prefix(SH_ERROR);
410 mOut << "node is still EOpNull!\n";
411 return true;
412 }
413
414 // Give verbose names for some built-in functions that are easy to confuse with others, but
415 // mostly use GLSL names for functions.
416 switch (op)
417 {
418 case EOpCallFunctionInAST:
419 OutputFunction(mOut, "Call a user-defined function", node->getFunction());
420 break;
421 case EOpCallInternalRawFunction:
422 OutputFunction(mOut, "Call an internal function with raw implementation",
423 node->getFunction());
424 break;
425
426 case EOpConstruct:
427 // The type of the constructor will be printed below.
428 mOut << "Construct";
429 break;
430
431 case EOpEqualComponentWise:
432 mOut << "component-wise equal";
433 break;
434 case EOpNotEqualComponentWise:
435 mOut << "component-wise not equal";
436 break;
437 case EOpLessThanComponentWise:
438 mOut << "component-wise less than";
439 break;
440 case EOpGreaterThanComponentWise:
441 mOut << "component-wise greater than";
442 break;
443 case EOpLessThanEqualComponentWise:
444 mOut << "component-wise less than or equal";
445 break;
446 case EOpGreaterThanEqualComponentWise:
447 mOut << "component-wise greater than or equal";
448 break;
449
450 case EOpDot:
451 mOut << "dot product";
452 break;
453 case EOpCross:
454 mOut << "cross product";
455 break;
456 case EOpMatrixCompMult:
457 mOut << "component-wise multiply";
458 break;
459
460 default:
461 if (BuiltInGroup::IsBuiltIn(op))
462 {
463 OutputFunction(mOut, "Call a built-in function", node->getFunction());
464 }
465 else
466 {
467 mOut << GetOperatorString(node->getOp());
468 }
469 break;
470 }
471
472 mOut << " (" << node->getType() << ")";
473
474 mOut << "\n";
475
476 return true;
477 }
478
visitBlock(Visit visit,TIntermBlock * node)479 bool TOutputTraverser::visitBlock(Visit visit, TIntermBlock *node)
480 {
481 OutputTreeText(mOut, node, getCurrentIndentDepth());
482 mOut << "Code block\n";
483
484 return true;
485 }
486
visitDeclaration(Visit visit,TIntermDeclaration * node)487 bool TOutputTraverser::visitDeclaration(Visit visit, TIntermDeclaration *node)
488 {
489 OutputTreeText(mOut, node, getCurrentIndentDepth());
490 mOut << "Declaration\n";
491
492 return true;
493 }
494
visitTernary(Visit visit,TIntermTernary * node)495 bool TOutputTraverser::visitTernary(Visit visit, TIntermTernary *node)
496 {
497 OutputTreeText(mOut, node, getCurrentIndentDepth());
498
499 mOut << "Ternary selection";
500 mOut << " (" << node->getType() << ")\n";
501
502 ++mIndentDepth;
503
504 OutputTreeText(mOut, node, getCurrentIndentDepth());
505 mOut << "Condition\n";
506 node->getCondition()->traverse(this);
507
508 OutputTreeText(mOut, node, getCurrentIndentDepth());
509 if (node->getTrueExpression())
510 {
511 mOut << "true case\n";
512 node->getTrueExpression()->traverse(this);
513 }
514 if (node->getFalseExpression())
515 {
516 OutputTreeText(mOut, node, getCurrentIndentDepth());
517 mOut << "false case\n";
518 node->getFalseExpression()->traverse(this);
519 }
520
521 --mIndentDepth;
522
523 return false;
524 }
525
visitIfElse(Visit visit,TIntermIfElse * node)526 bool TOutputTraverser::visitIfElse(Visit visit, TIntermIfElse *node)
527 {
528 OutputTreeText(mOut, node, getCurrentIndentDepth());
529
530 mOut << "If test\n";
531
532 ++mIndentDepth;
533
534 OutputTreeText(mOut, node, getCurrentIndentDepth());
535 mOut << "Condition\n";
536 node->getCondition()->traverse(this);
537
538 OutputTreeText(mOut, node, getCurrentIndentDepth());
539 if (node->getTrueBlock())
540 {
541 mOut << "true case\n";
542 node->getTrueBlock()->traverse(this);
543 }
544 else
545 {
546 mOut << "true case is null\n";
547 }
548
549 if (node->getFalseBlock())
550 {
551 OutputTreeText(mOut, node, getCurrentIndentDepth());
552 mOut << "false case\n";
553 node->getFalseBlock()->traverse(this);
554 }
555
556 --mIndentDepth;
557
558 return false;
559 }
560
visitSwitch(Visit visit,TIntermSwitch * node)561 bool TOutputTraverser::visitSwitch(Visit visit, TIntermSwitch *node)
562 {
563 OutputTreeText(mOut, node, getCurrentIndentDepth());
564
565 mOut << "Switch\n";
566
567 return true;
568 }
569
visitCase(Visit visit,TIntermCase * node)570 bool TOutputTraverser::visitCase(Visit visit, TIntermCase *node)
571 {
572 OutputTreeText(mOut, node, getCurrentIndentDepth());
573
574 if (node->getCondition() == nullptr)
575 {
576 mOut << "Default\n";
577 }
578 else
579 {
580 mOut << "Case\n";
581 }
582
583 return true;
584 }
585
visitConstantUnion(TIntermConstantUnion * node)586 void TOutputTraverser::visitConstantUnion(TIntermConstantUnion *node)
587 {
588 size_t size = node->getType().getObjectSize();
589
590 for (size_t i = 0; i < size; i++)
591 {
592 OutputTreeText(mOut, node, getCurrentIndentDepth());
593 switch (node->getConstantValue()[i].getType())
594 {
595 case EbtBool:
596 if (node->getConstantValue()[i].getBConst())
597 mOut << "true";
598 else
599 mOut << "false";
600
601 mOut << " ("
602 << "const bool"
603 << ")";
604 mOut << "\n";
605 break;
606 case EbtFloat:
607 mOut << node->getConstantValue()[i].getFConst();
608 mOut << " (const float)\n";
609 break;
610 case EbtInt:
611 mOut << node->getConstantValue()[i].getIConst();
612 mOut << " (const int)\n";
613 break;
614 case EbtUInt:
615 mOut << node->getConstantValue()[i].getUConst();
616 mOut << " (const uint)\n";
617 break;
618 case EbtYuvCscStandardEXT:
619 mOut << getYuvCscStandardEXTString(
620 node->getConstantValue()[i].getYuvCscStandardEXTConst());
621 mOut << " (const yuvCscStandardEXT)\n";
622 break;
623 default:
624 mOut.prefix(SH_ERROR);
625 mOut << "Unknown constant\n";
626 break;
627 }
628 }
629 }
630
visitLoop(Visit visit,TIntermLoop * node)631 bool TOutputTraverser::visitLoop(Visit visit, TIntermLoop *node)
632 {
633 OutputTreeText(mOut, node, getCurrentIndentDepth());
634
635 mOut << "Loop with condition ";
636 if (node->getType() == ELoopDoWhile)
637 mOut << "not ";
638 mOut << "tested first\n";
639
640 ++mIndentDepth;
641
642 OutputTreeText(mOut, node, getCurrentIndentDepth());
643 if (node->getCondition())
644 {
645 mOut << "Loop Condition\n";
646 node->getCondition()->traverse(this);
647 }
648 else
649 {
650 mOut << "No loop condition\n";
651 }
652
653 OutputTreeText(mOut, node, getCurrentIndentDepth());
654 if (node->getBody())
655 {
656 mOut << "Loop Body\n";
657 node->getBody()->traverse(this);
658 }
659 else
660 {
661 mOut << "No loop body\n";
662 }
663
664 if (node->getExpression())
665 {
666 OutputTreeText(mOut, node, getCurrentIndentDepth());
667 mOut << "Loop Terminal Expression\n";
668 node->getExpression()->traverse(this);
669 }
670
671 --mIndentDepth;
672
673 return false;
674 }
675
visitBranch(Visit visit,TIntermBranch * node)676 bool TOutputTraverser::visitBranch(Visit visit, TIntermBranch *node)
677 {
678 OutputTreeText(mOut, node, getCurrentIndentDepth());
679
680 switch (node->getFlowOp())
681 {
682 case EOpKill:
683 mOut << "Branch: Kill";
684 break;
685 case EOpBreak:
686 mOut << "Branch: Break";
687 break;
688 case EOpContinue:
689 mOut << "Branch: Continue";
690 break;
691 case EOpReturn:
692 mOut << "Branch: Return";
693 break;
694 default:
695 mOut << "Branch: Unknown Branch";
696 break;
697 }
698
699 if (node->getExpression())
700 {
701 mOut << " with expression\n";
702 ++mIndentDepth;
703 node->getExpression()->traverse(this);
704 --mIndentDepth;
705 }
706 else
707 {
708 mOut << "\n";
709 }
710
711 return false;
712 }
713
714 } // anonymous namespace
715
OutputTree(TIntermNode * root,TInfoSinkBase & out)716 void OutputTree(TIntermNode *root, TInfoSinkBase &out)
717 {
718 TOutputTraverser it(out);
719 ASSERT(root);
720 root->traverse(&it);
721 }
722
723 } // namespace sh
724