michael@0: //
michael@0: // Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: //
michael@0: 
michael@0: #include "compiler/depgraph/DependencyGraphBuilder.h"
michael@0: 
michael@0: void TDependencyGraphBuilder::build(TIntermNode* node, TDependencyGraph* graph)
michael@0: {
michael@0:     TDependencyGraphBuilder builder(graph);
michael@0:     builder.build(node);
michael@0: }
michael@0: 
michael@0: bool TDependencyGraphBuilder::visitAggregate(Visit visit, TIntermAggregate* intermAggregate)
michael@0: {
michael@0:     switch (intermAggregate->getOp()) {
michael@0:         case EOpFunction: visitFunctionDefinition(intermAggregate); break;
michael@0:         case EOpFunctionCall: visitFunctionCall(intermAggregate); break;
michael@0:         default: visitAggregateChildren(intermAggregate); break;
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: void TDependencyGraphBuilder::visitFunctionDefinition(TIntermAggregate* intermAggregate)
michael@0: {
michael@0:     // Currently, we do not support user defined functions.
michael@0:     if (intermAggregate->getName() != "main(")
michael@0:         return;
michael@0: 
michael@0:     visitAggregateChildren(intermAggregate);
michael@0: }
michael@0: 
michael@0: // Takes an expression like "f(x)" and creates a dependency graph like
michael@0: // "x -> argument 0 -> function call".
michael@0: void TDependencyGraphBuilder::visitFunctionCall(TIntermAggregate* intermFunctionCall)
michael@0: {
michael@0:     TGraphFunctionCall* functionCall = mGraph->createFunctionCall(intermFunctionCall);
michael@0: 
michael@0:     // Run through the function call arguments.
michael@0:     int argumentNumber = 0;
michael@0:     TIntermSequence& intermArguments = intermFunctionCall->getSequence();
michael@0:     for (TIntermSequence::const_iterator iter = intermArguments.begin();
michael@0:          iter != intermArguments.end();
michael@0:          ++iter, ++argumentNumber)
michael@0:     {
michael@0:         TNodeSetMaintainer nodeSetMaintainer(this);
michael@0: 
michael@0:         TIntermNode* intermArgument = *iter;
michael@0:         intermArgument->traverse(this);
michael@0: 
michael@0:         if (TParentNodeSet* argumentNodes = mNodeSets.getTopSet()) {
michael@0:             TGraphArgument* argument = mGraph->createArgument(intermFunctionCall, argumentNumber);
michael@0:             connectMultipleNodesToSingleNode(argumentNodes, argument);
michael@0:             argument->addDependentNode(functionCall);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Push the leftmost symbol of this function call into the current set of dependent symbols to
michael@0:     // represent the result of this function call.
michael@0:     // Thus, an expression like "y = f(x)" will yield a dependency graph like
michael@0:     // "x -> argument 0 -> function call -> y".
michael@0:     // This line essentially passes the function call node back up to an earlier visitAssignment
michael@0:     // call, which will create the connection "function call -> y".
michael@0:     mNodeSets.insertIntoTopSet(functionCall);
michael@0: }
michael@0: 
michael@0: void TDependencyGraphBuilder::visitAggregateChildren(TIntermAggregate* intermAggregate)
michael@0: {
michael@0:     TIntermSequence& sequence = intermAggregate->getSequence();
michael@0:     for(TIntermSequence::const_iterator iter = sequence.begin(); iter != sequence.end(); ++iter)
michael@0:     {
michael@0:         TIntermNode* intermChild = *iter;
michael@0:         intermChild->traverse(this);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void TDependencyGraphBuilder::visitSymbol(TIntermSymbol* intermSymbol)
michael@0: {
michael@0:     // Push this symbol into the set of dependent symbols for the current assignment or condition
michael@0:     // that we are traversing.
michael@0:     TGraphSymbol* symbol = mGraph->getOrCreateSymbol(intermSymbol);
michael@0:     mNodeSets.insertIntoTopSet(symbol);
michael@0: 
michael@0:     // If this symbol is the current leftmost symbol under an assignment, replace the previous
michael@0:     // leftmost symbol with this symbol.
michael@0:     if (!mLeftmostSymbols.empty() && mLeftmostSymbols.top() != &mRightSubtree) {
michael@0:         mLeftmostSymbols.pop();
michael@0:         mLeftmostSymbols.push(symbol);
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary* intermBinary)
michael@0: {
michael@0:     TOperator op = intermBinary->getOp();
michael@0:     if (op == EOpInitialize || intermBinary->modifiesState())
michael@0:         visitAssignment(intermBinary);
michael@0:     else if (op == EOpLogicalAnd || op == EOpLogicalOr)
michael@0:         visitLogicalOp(intermBinary);
michael@0:     else
michael@0:         visitBinaryChildren(intermBinary);
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: void TDependencyGraphBuilder::visitAssignment(TIntermBinary* intermAssignment)
michael@0: {
michael@0:     TIntermTyped* intermLeft = intermAssignment->getLeft();
michael@0:     if (!intermLeft)
michael@0:         return;
michael@0: 
michael@0:     TGraphSymbol* leftmostSymbol = NULL;
michael@0: 
michael@0:     {
michael@0:         TNodeSetMaintainer nodeSetMaintainer(this);
michael@0: 
michael@0:         {
michael@0:             TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mLeftSubtree);
michael@0:             intermLeft->traverse(this);
michael@0:             leftmostSymbol = mLeftmostSymbols.top();
michael@0: 
michael@0:             // After traversing the left subtree of this assignment, we should have found a real
michael@0:             // leftmost symbol, and the leftmost symbol should not be a placeholder.
michael@0:             ASSERT(leftmostSymbol != &mLeftSubtree);
michael@0:             ASSERT(leftmostSymbol != &mRightSubtree);
michael@0:         }
michael@0: 
michael@0:         if (TIntermTyped* intermRight = intermAssignment->getRight()) {
michael@0:             TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
michael@0:             intermRight->traverse(this);
michael@0:         }
michael@0: 
michael@0:         if (TParentNodeSet* assignmentNodes = mNodeSets.getTopSet())
michael@0:             connectMultipleNodesToSingleNode(assignmentNodes, leftmostSymbol);
michael@0:     }
michael@0: 
michael@0:     // Push the leftmost symbol of this assignment into the current set of dependent symbols to
michael@0:     // represent the result of this assignment.
michael@0:     // An expression like "a = (b = c)" will yield a dependency graph like "c -> b -> a".
michael@0:     // This line essentially passes the leftmost symbol of the nested assignment ("b" in this
michael@0:     // example) back up to the earlier visitAssignment call for the outer assignment, which will
michael@0:     // create the connection "b -> a".
michael@0:     mNodeSets.insertIntoTopSet(leftmostSymbol);
michael@0: }
michael@0: 
michael@0: void TDependencyGraphBuilder::visitLogicalOp(TIntermBinary* intermLogicalOp)
michael@0: {
michael@0:     if (TIntermTyped* intermLeft = intermLogicalOp->getLeft()) {
michael@0:         TNodeSetPropagatingMaintainer nodeSetMaintainer(this);
michael@0: 
michael@0:         intermLeft->traverse(this);
michael@0:         if (TParentNodeSet* leftNodes = mNodeSets.getTopSet()) {
michael@0:             TGraphLogicalOp* logicalOp = mGraph->createLogicalOp(intermLogicalOp);
michael@0:             connectMultipleNodesToSingleNode(leftNodes, logicalOp);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (TIntermTyped* intermRight = intermLogicalOp->getRight()) {
michael@0:         TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
michael@0:         intermRight->traverse(this);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void TDependencyGraphBuilder::visitBinaryChildren(TIntermBinary* intermBinary)
michael@0: {
michael@0:     if (TIntermTyped* intermLeft = intermBinary->getLeft())
michael@0:         intermLeft->traverse(this);
michael@0: 
michael@0:     if (TIntermTyped* intermRight = intermBinary->getRight()) {
michael@0:         TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
michael@0:         intermRight->traverse(this);
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool TDependencyGraphBuilder::visitSelection(Visit visit, TIntermSelection* intermSelection)
michael@0: {
michael@0:     if (TIntermNode* intermCondition = intermSelection->getCondition()) {
michael@0:         TNodeSetMaintainer nodeSetMaintainer(this);
michael@0: 
michael@0:         intermCondition->traverse(this);
michael@0:         if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
michael@0:             TGraphSelection* selection = mGraph->createSelection(intermSelection);
michael@0:             connectMultipleNodesToSingleNode(conditionNodes, selection);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (TIntermNode* intermTrueBlock = intermSelection->getTrueBlock())
michael@0:         intermTrueBlock->traverse(this);
michael@0: 
michael@0:     if (TIntermNode* intermFalseBlock = intermSelection->getFalseBlock())
michael@0:         intermFalseBlock->traverse(this);
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop* intermLoop)
michael@0: {
michael@0:     if (TIntermTyped* intermCondition = intermLoop->getCondition()) {
michael@0:         TNodeSetMaintainer nodeSetMaintainer(this);
michael@0: 
michael@0:         intermCondition->traverse(this);
michael@0:         if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
michael@0:             TGraphLoop* loop = mGraph->createLoop(intermLoop);
michael@0:             connectMultipleNodesToSingleNode(conditionNodes, loop);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (TIntermNode* intermBody = intermLoop->getBody())
michael@0:         intermBody->traverse(this);
michael@0: 
michael@0:     if (TIntermTyped* intermExpression = intermLoop->getExpression())
michael@0:         intermExpression->traverse(this);
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: 
michael@0: void TDependencyGraphBuilder::connectMultipleNodesToSingleNode(TParentNodeSet* nodes,
michael@0:                                                                TGraphNode* node) const
michael@0: {
michael@0:     for (TParentNodeSet::const_iterator iter = nodes->begin(); iter != nodes->end(); ++iter)
michael@0:     {
michael@0:         TGraphParentNode* currentNode = *iter;
michael@0:         currentNode->addDependentNode(node);
michael@0:     }
michael@0: }