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