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