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