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