Home | History | Annotate | Download | only in depgraph 
      1 //
      2 // Copyright (c) 2012 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/depgraph/DependencyGraphBuilder.h"
      8 
      9 void TDependencyGraphBuilder::build(TIntermNode* node, TDependencyGraph* graph)
     10 {
     11     TDependencyGraphBuilder builder(graph);
     12     builder.build(node);
     13 }
     14 
     15 bool TDependencyGraphBuilder::visitAggregate(Visit visit, TIntermAggregate* intermAggregate)
     16 {
     17     switch (intermAggregate->getOp()) {
     18         case EOpFunction: visitFunctionDefinition(intermAggregate); break;
     19         case EOpFunctionCall: visitFunctionCall(intermAggregate); break;
     20         default: visitAggregateChildren(intermAggregate); break;
     21     }
     22 
     23     return false;
     24 }
     25 
     26 void TDependencyGraphBuilder::visitFunctionDefinition(TIntermAggregate* intermAggregate)
     27 {
     28     // Currently, we do not support user defined functions.
     29     if (intermAggregate->getName() != "main(")
     30         return;
     31 
     32     visitAggregateChildren(intermAggregate);
     33 }
     34 
     35 // Takes an expression like "f(x)" and creates a dependency graph like
     36 // "x -> argument 0 -> function call".
     37 void TDependencyGraphBuilder::visitFunctionCall(TIntermAggregate* intermFunctionCall)
     38 {
     39     TGraphFunctionCall* functionCall = mGraph->createFunctionCall(intermFunctionCall);
     40 
     41     // Run through the function call arguments.
     42     int argumentNumber = 0;
     43     TIntermSequence& intermArguments = intermFunctionCall->getSequence();
     44     for (TIntermSequence::const_iterator iter = intermArguments.begin();
     45          iter != intermArguments.end();
     46          ++iter, ++argumentNumber)
     47     {
     48         TNodeSetMaintainer nodeSetMaintainer(this);
     49 
     50         TIntermNode* intermArgument = *iter;
     51         intermArgument->traverse(this);
     52 
     53         if (TParentNodeSet* argumentNodes = mNodeSets.getTopSet()) {
     54             TGraphArgument* argument = mGraph->createArgument(intermFunctionCall, argumentNumber);
     55             connectMultipleNodesToSingleNode(argumentNodes, argument);
     56             argument->addDependentNode(functionCall);
     57         }
     58     }
     59 
     60     // Push the leftmost symbol of this function call into the current set of dependent symbols to
     61     // represent the result of this function call.
     62     // Thus, an expression like "y = f(x)" will yield a dependency graph like
     63     // "x -> argument 0 -> function call -> y".
     64     // This line essentially passes the function call node back up to an earlier visitAssignment
     65     // call, which will create the connection "function call -> y".
     66     mNodeSets.insertIntoTopSet(functionCall);
     67 }
     68 
     69 void TDependencyGraphBuilder::visitAggregateChildren(TIntermAggregate* intermAggregate)
     70 {
     71     TIntermSequence& sequence = intermAggregate->getSequence();
     72     for(TIntermSequence::const_iterator iter = sequence.begin(); iter != sequence.end(); ++iter)
     73     {
     74         TIntermNode* intermChild = *iter;
     75         intermChild->traverse(this);
     76     }
     77 }
     78 
     79 void TDependencyGraphBuilder::visitSymbol(TIntermSymbol* intermSymbol)
     80 {
     81     // Push this symbol into the set of dependent symbols for the current assignment or condition
     82     // that we are traversing.
     83     TGraphSymbol* symbol = mGraph->getOrCreateSymbol(intermSymbol);
     84     mNodeSets.insertIntoTopSet(symbol);
     85 
     86     // If this symbol is the current leftmost symbol under an assignment, replace the previous
     87     // leftmost symbol with this symbol.
     88     if (!mLeftmostSymbols.empty() && mLeftmostSymbols.top() != &mRightSubtree) {
     89         mLeftmostSymbols.pop();
     90         mLeftmostSymbols.push(symbol);
     91     }
     92 }
     93 
     94 bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary* intermBinary)
     95 {
     96     TOperator op = intermBinary->getOp();
     97     if (op == EOpInitialize || intermBinary->isAssignment())
     98         visitAssignment(intermBinary);
     99     else if (op == EOpLogicalAnd || op == EOpLogicalOr)
    100         visitLogicalOp(intermBinary);
    101     else
    102         visitBinaryChildren(intermBinary);
    103 
    104     return false;
    105 }
    106 
    107 void TDependencyGraphBuilder::visitAssignment(TIntermBinary* intermAssignment)
    108 {
    109     TIntermTyped* intermLeft = intermAssignment->getLeft();
    110     if (!intermLeft)
    111         return;
    112 
    113     TGraphSymbol* leftmostSymbol = NULL;
    114 
    115     {
    116         TNodeSetMaintainer nodeSetMaintainer(this);
    117 
    118         {
    119             TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mLeftSubtree);
    120             intermLeft->traverse(this);
    121             leftmostSymbol = mLeftmostSymbols.top();
    122 
    123             // After traversing the left subtree of this assignment, we should have found a real
    124             // leftmost symbol, and the leftmost symbol should not be a placeholder.
    125             ASSERT(leftmostSymbol != &mLeftSubtree);
    126             ASSERT(leftmostSymbol != &mRightSubtree);
    127         }
    128 
    129         if (TIntermTyped* intermRight = intermAssignment->getRight()) {
    130             TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
    131             intermRight->traverse(this);
    132         }
    133 
    134         if (TParentNodeSet* assignmentNodes = mNodeSets.getTopSet())
    135             connectMultipleNodesToSingleNode(assignmentNodes, leftmostSymbol);
    136     }
    137 
    138     // Push the leftmost symbol of this assignment into the current set of dependent symbols to
    139     // represent the result of this assignment.
    140     // An expression like "a = (b = c)" will yield a dependency graph like "c -> b -> a".
    141     // This line essentially passes the leftmost symbol of the nested assignment ("b" in this
    142     // example) back up to the earlier visitAssignment call for the outer assignment, which will
    143     // create the connection "b -> a".
    144     mNodeSets.insertIntoTopSet(leftmostSymbol);
    145 }
    146 
    147 void TDependencyGraphBuilder::visitLogicalOp(TIntermBinary* intermLogicalOp)
    148 {
    149     if (TIntermTyped* intermLeft = intermLogicalOp->getLeft()) {
    150         TNodeSetPropagatingMaintainer nodeSetMaintainer(this);
    151 
    152         intermLeft->traverse(this);
    153         if (TParentNodeSet* leftNodes = mNodeSets.getTopSet()) {
    154             TGraphLogicalOp* logicalOp = mGraph->createLogicalOp(intermLogicalOp);
    155             connectMultipleNodesToSingleNode(leftNodes, logicalOp);
    156         }
    157     }
    158 
    159     if (TIntermTyped* intermRight = intermLogicalOp->getRight()) {
    160         TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
    161         intermRight->traverse(this);
    162     }
    163 }
    164 
    165 void TDependencyGraphBuilder::visitBinaryChildren(TIntermBinary* intermBinary)
    166 {
    167     if (TIntermTyped* intermLeft = intermBinary->getLeft())
    168         intermLeft->traverse(this);
    169 
    170     if (TIntermTyped* intermRight = intermBinary->getRight()) {
    171         TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
    172         intermRight->traverse(this);
    173     }
    174 }
    175 
    176 bool TDependencyGraphBuilder::visitSelection(Visit visit, TIntermSelection* intermSelection)
    177 {
    178     if (TIntermNode* intermCondition = intermSelection->getCondition()) {
    179         TNodeSetMaintainer nodeSetMaintainer(this);
    180 
    181         intermCondition->traverse(this);
    182         if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
    183             TGraphSelection* selection = mGraph->createSelection(intermSelection);
    184             connectMultipleNodesToSingleNode(conditionNodes, selection);
    185         }
    186     }
    187 
    188     if (TIntermNode* intermTrueBlock = intermSelection->getTrueBlock())
    189         intermTrueBlock->traverse(this);
    190 
    191     if (TIntermNode* intermFalseBlock = intermSelection->getFalseBlock())
    192         intermFalseBlock->traverse(this);
    193 
    194     return false;
    195 }
    196 
    197 bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop* intermLoop)
    198 {
    199     if (TIntermTyped* intermCondition = intermLoop->getCondition()) {
    200         TNodeSetMaintainer nodeSetMaintainer(this);
    201 
    202         intermCondition->traverse(this);
    203         if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
    204             TGraphLoop* loop = mGraph->createLoop(intermLoop);
    205             connectMultipleNodesToSingleNode(conditionNodes, loop);
    206         }
    207     }
    208 
    209     if (TIntermNode* intermBody = intermLoop->getBody())
    210         intermBody->traverse(this);
    211 
    212     if (TIntermTyped* intermExpression = intermLoop->getExpression())
    213         intermExpression->traverse(this);
    214 
    215     return false;
    216 }
    217 
    218 
    219 void TDependencyGraphBuilder::connectMultipleNodesToSingleNode(TParentNodeSet* nodes,
    220                                                                TGraphNode* node) const
    221 {
    222     for (TParentNodeSet::const_iterator iter = nodes->begin(); iter != nodes->end(); ++iter)
    223     {
    224         TGraphParentNode* currentNode = *iter;
    225         currentNode->addDependentNode(node);
    226     }
    227 }
    228