Merge branch 'ANGLE-rollback'

This resolves #624

Note: Cherry-picked some fixes on top of the ANGLE version that we want to keep.

7 files changed, 912 insertions, 0 deletions

diff --git a/gfx/angle/src/compiler/translator/depgraph/DependencyGraph.cpp b/gfx/angle/src/compiler/translator/depgraph/DependencyGraph.cpp
new file mode 100644
index 000000000..4dee0dbd2
--- /dev/null
+++ b/gfx/angle/src/compiler/translator/depgraph/DependencyGraph.cpp
@@ -0,0 +1,95 @@
+//
+// 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/DependencyGraph.h"
+#include "compiler/translator/depgraph/DependencyGraphBuilder.h"
+
+TDependencyGraph::TDependencyGraph(TIntermNode* intermNode)
+{
+    TDependencyGraphBuilder::build(intermNode, this);
+}
+
+TDependencyGraph::~TDependencyGraph()
+{
+    for (TGraphNodeVector::const_iterator iter = mAllNodes.begin(); iter != mAllNodes.end(); ++iter)
+    {
+        TGraphNode* node = *iter;
+        delete node;
+    }
+}
+
+TGraphArgument* TDependencyGraph::createArgument(TIntermAggregate* intermFunctionCall,
+                                                 int argumentNumber)
+{
+    TGraphArgument* argument = new TGraphArgument(intermFunctionCall, argumentNumber);
+    mAllNodes.push_back(argument);
+    return argument;
+}
+
+TGraphFunctionCall* TDependencyGraph::createFunctionCall(TIntermAggregate* intermFunctionCall)
+{
+    TGraphFunctionCall* functionCall = new TGraphFunctionCall(intermFunctionCall);
+    mAllNodes.push_back(functionCall);
+    if (functionCall->getIntermFunctionCall()->isUserDefined())
+        mUserDefinedFunctionCalls.push_back(functionCall);
+    return functionCall;
+}
+
+TGraphSymbol* TDependencyGraph::getOrCreateSymbol(TIntermSymbol* intermSymbol)
+{
+    TSymbolIdMap::const_iterator iter = mSymbolIdMap.find(intermSymbol->getId());
+
+    TGraphSymbol* symbol = NULL;
+
+    if (iter != mSymbolIdMap.end()) {
+        TSymbolIdPair pair = *iter;
+        symbol = pair.second;
+    } else {
+        symbol = new TGraphSymbol(intermSymbol);
+        mAllNodes.push_back(symbol);
+
+        TSymbolIdPair pair(intermSymbol->getId(), symbol);
+        mSymbolIdMap.insert(pair);
+
+        // We save all sampler symbols in a collection, so we can start graph traversals from them quickly.
+        if (IsSampler(intermSymbol->getBasicType()))
+            mSamplerSymbols.push_back(symbol);
+    }
+
+    return symbol;
+}
+
+TGraphSelection* TDependencyGraph::createSelection(TIntermSelection* intermSelection)
+{
+    TGraphSelection* selection = new TGraphSelection(intermSelection);
+    mAllNodes.push_back(selection);
+    return selection;
+}
+
+TGraphLoop* TDependencyGraph::createLoop(TIntermLoop* intermLoop)
+{
+    TGraphLoop* loop = new TGraphLoop(intermLoop);
+    mAllNodes.push_back(loop);
+    return loop;
+}
+
+TGraphLogicalOp* TDependencyGraph::createLogicalOp(TIntermBinary* intermLogicalOp)
+{
+    TGraphLogicalOp* logicalOp = new TGraphLogicalOp(intermLogicalOp);
+    mAllNodes.push_back(logicalOp);
+    return logicalOp;
+}
+
+const char* TGraphLogicalOp::getOpString() const
+{
+    const char* opString = NULL;
+    switch (getIntermLogicalOp()->getOp()) {
+        case EOpLogicalAnd: opString = "and"; break;
+        case EOpLogicalOr: opString = "or"; break;
+        default: opString = "unknown"; break;
+    }
+    return opString;
+}
diff --git a/gfx/angle/src/compiler/translator/depgraph/DependencyGraph.h b/gfx/angle/src/compiler/translator/depgraph/DependencyGraph.h
new file mode 100644
index 000000000..2f7f7b9ab
--- /dev/null
+++ b/gfx/angle/src/compiler/translator/depgraph/DependencyGraph.h
@@ -0,0 +1,199 @@
+//
+// 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.
+//
+
+#ifndef COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCYGRAPH_H_
+#define COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCYGRAPH_H_
+
+#include "compiler/translator/IntermNode.h"
+
+#include <set>
+#include <stack>
+
+class TGraphNode;
+class TGraphParentNode;
+class TGraphArgument;
+class TGraphFunctionCall;
+class TGraphSymbol;
+class TGraphSelection;
+class TGraphLoop;
+class TGraphLogicalOp;
+class TDependencyGraphTraverser;
+class TDependencyGraphOutput;
+
+typedef std::set<TGraphNode*> TGraphNodeSet;
+typedef std::vector<TGraphNode*> TGraphNodeVector;
+typedef std::vector<TGraphSymbol*> TGraphSymbolVector;
+typedef std::vector<TGraphFunctionCall*> TFunctionCallVector;
+
+//
+// Base class for all dependency graph nodes.
+//
+class TGraphNode {
+public:
+    TGraphNode(TIntermNode* node) : intermNode(node) {}
+    virtual ~TGraphNode() {}
+    virtual void traverse(TDependencyGraphTraverser* graphTraverser);
+protected:
+    TIntermNode* intermNode;
+};
+
+//
+// Base class for dependency graph nodes that may have children.
+//
+class TGraphParentNode : public TGraphNode {
+public:
+    TGraphParentNode(TIntermNode* node) : TGraphNode(node) {}
+    ~TGraphParentNode() override {}
+    void addDependentNode(TGraphNode* node) { if (node != this) mDependentNodes.insert(node); }
+    void traverse(TDependencyGraphTraverser *graphTraverser) override;
+
+private:
+    TGraphNodeSet mDependentNodes;
+};
+
+//
+// Handle function call arguments.
+//
+class TGraphArgument : public TGraphParentNode {
+public:
+    TGraphArgument(TIntermAggregate* intermFunctionCall, int argumentNumber)
+        : TGraphParentNode(intermFunctionCall)
+        , mArgumentNumber(argumentNumber) {}
+    ~TGraphArgument() override {}
+    const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); }
+    int getArgumentNumber() const { return mArgumentNumber; }
+    void traverse(TDependencyGraphTraverser *graphTraverser) override;
+
+private:
+    int mArgumentNumber;
+};
+
+//
+// Handle function calls.
+//
+class TGraphFunctionCall : public TGraphParentNode {
+public:
+    TGraphFunctionCall(TIntermAggregate* intermFunctionCall)
+        : TGraphParentNode(intermFunctionCall) {}
+    ~TGraphFunctionCall() override {}
+    const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); }
+    void traverse(TDependencyGraphTraverser *graphTraverser) override;
+};
+
+//
+// Handle symbols.
+//
+class TGraphSymbol : public TGraphParentNode {
+public:
+    TGraphSymbol(TIntermSymbol* intermSymbol) : TGraphParentNode(intermSymbol) {}
+    ~TGraphSymbol() override {}
+    const TIntermSymbol* getIntermSymbol() const { return intermNode->getAsSymbolNode(); }
+    void traverse(TDependencyGraphTraverser *graphTraverser) override;
+};
+
+//
+// Handle if statements and ternary operators.
+//
+class TGraphSelection : public TGraphNode {
+public:
+    TGraphSelection(TIntermSelection* intermSelection) : TGraphNode(intermSelection) {}
+    ~TGraphSelection() override {}
+    const TIntermSelection* getIntermSelection() const { return intermNode->getAsSelectionNode(); }
+    void traverse(TDependencyGraphTraverser *graphTraverser) override;
+};
+
+//
+// Handle for, do-while, and while loops.
+//
+class TGraphLoop : public TGraphNode {
+public:
+    TGraphLoop(TIntermLoop* intermLoop) : TGraphNode(intermLoop) {}
+    ~TGraphLoop() override {}
+    const TIntermLoop* getIntermLoop() const { return intermNode->getAsLoopNode(); }
+    void traverse(TDependencyGraphTraverser *graphTraverser) override;
+};
+
+//
+// Handle logical and, or.
+//
+class TGraphLogicalOp : public TGraphNode {
+public:
+    TGraphLogicalOp(TIntermBinary* intermLogicalOp) : TGraphNode(intermLogicalOp) {}
+    ~TGraphLogicalOp() override {}
+    const TIntermBinary* getIntermLogicalOp() const { return intermNode->getAsBinaryNode(); }
+    const char* getOpString() const;
+    void traverse(TDependencyGraphTraverser *graphTraverser) override;
+};
+
+//
+// A dependency graph of symbols, function calls, conditions etc.
+//
+// This class provides an interface to the entry points of the dependency graph.
+//
+// Dependency graph nodes should be created by using one of the provided "create..." methods.
+// This class (and nobody else) manages the memory of the created nodes.
+// Nodes may not be removed after being added, so all created nodes will exist while the
+// TDependencyGraph instance exists.
+//
+class TDependencyGraph {
+public:
+    TDependencyGraph(TIntermNode* intermNode);
+    ~TDependencyGraph();
+    const TGraphNodeVector &allNodes() const { return mAllNodes; }
+    const TGraphSymbolVector &samplerSymbols() const { return mSamplerSymbols; }
+    const TFunctionCallVector &userDefinedFunctionCalls() const
+    {
+        return mUserDefinedFunctionCalls;
+    }
+
+    TGraphArgument* createArgument(TIntermAggregate* intermFunctionCall, int argumentNumber);
+    TGraphFunctionCall* createFunctionCall(TIntermAggregate* intermFunctionCall);
+    TGraphSymbol* getOrCreateSymbol(TIntermSymbol* intermSymbol);
+    TGraphSelection* createSelection(TIntermSelection* intermSelection);
+    TGraphLoop* createLoop(TIntermLoop* intermLoop);
+    TGraphLogicalOp* createLogicalOp(TIntermBinary* intermLogicalOp);
+private:
+    typedef TMap<int, TGraphSymbol*> TSymbolIdMap;
+    typedef std::pair<int, TGraphSymbol*> TSymbolIdPair;
+
+    TGraphNodeVector mAllNodes;
+    TGraphSymbolVector mSamplerSymbols;
+    TFunctionCallVector mUserDefinedFunctionCalls;
+    TSymbolIdMap mSymbolIdMap;
+};
+
+//
+// For traversing the dependency graph. Users should derive from this,
+// put their traversal specific data in it, and then pass it to a
+// traverse method.
+//
+// When using this, just fill in the methods for nodes you want visited.
+//
+class TDependencyGraphTraverser : angle::NonCopyable {
+public:
+    TDependencyGraphTraverser() : mDepth(0) {}
+    virtual ~TDependencyGraphTraverser() {}
+
+    virtual void visitSymbol(TGraphSymbol* symbol) {};
+    virtual void visitArgument(TGraphArgument* selection) {};
+    virtual void visitFunctionCall(TGraphFunctionCall* functionCall) {};
+    virtual void visitSelection(TGraphSelection* selection) {};
+    virtual void visitLoop(TGraphLoop* loop) {};
+    virtual void visitLogicalOp(TGraphLogicalOp* logicalOp) {};
+
+    int getDepth() const { return mDepth; }
+    void incrementDepth() { ++mDepth; }
+    void decrementDepth() { --mDepth; }
+
+    void clearVisited() { mVisited.clear(); }
+    void markVisited(TGraphNode* node) { mVisited.insert(node); }
+    bool isVisited(TGraphNode* node) const { return mVisited.find(node) != mVisited.end(); }
+private:
+    int mDepth;
+    TGraphNodeSet mVisited;
+};
+
+#endif // COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCYGRAPH_H_
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);
+    }
+}
diff --git a/gfx/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h b/gfx/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h
new file mode 100644
index 000000000..c7b54f66b
--- /dev/null
+++ b/gfx/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h
@@ -0,0 +1,199 @@
+//
+// 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.
+//
+
+#ifndef COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCYGRAPHBUILDER_H_
+#define COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCYGRAPHBUILDER_H_
+
+#include "compiler/translator/depgraph/DependencyGraph.h"
+
+//
+// Creates a dependency graph of symbols, function calls, conditions etc. by
+// traversing a intermediate tree.
+//
+class TDependencyGraphBuilder : public TIntermTraverser
+{
+  public:
+    static void build(TIntermNode *node, TDependencyGraph *graph);
+
+    void visitSymbol(TIntermSymbol *) override;
+    bool visitBinary(Visit visit, TIntermBinary *) override;
+    bool visitSelection(Visit visit, TIntermSelection *) override;
+    bool visitAggregate(Visit visit, TIntermAggregate *) override;
+    bool visitLoop(Visit visit, TIntermLoop *) override;
+
+  private:
+    typedef std::stack<TGraphSymbol *> TSymbolStack;
+    typedef std::set<TGraphParentNode *> TParentNodeSet;
+
+    //
+    // For collecting the dependent nodes of assignments, conditions, etc.
+    // while traversing the intermediate tree.
+    //
+    // This data structure is stack of sets. Each set contains dependency graph
+    // parent nodes.
+    //
+    class TNodeSetStack
+    {
+      public:
+        TNodeSetStack() {};
+        ~TNodeSetStack() { clear(); }
+
+        // This should only be called after a pushSet.
+        // Returns NULL if the top set is empty.
+        TParentNodeSet *getTopSet() const
+        {
+            ASSERT(!mNodeSets.empty());
+            TParentNodeSet *topSet = mNodeSets.top();
+            return !topSet->empty() ? topSet : NULL;
+        }
+
+        void pushSet() { mNodeSets.push(new TParentNodeSet()); }
+        void popSet()
+        {
+            ASSERT(!mNodeSets.empty());
+            delete mNodeSets.top();
+            mNodeSets.pop();
+        }
+
+        // Pops the top set and adds its contents to the new top set.
+        // This should only be called after a pushSet.
+        // If there is no set below the top set, the top set is just deleted.
+        void popSetIntoNext()
+        {
+            ASSERT(!mNodeSets.empty());
+            TParentNodeSet *oldTopSet = mNodeSets.top();
+            mNodeSets.pop();
+
+            if (!mNodeSets.empty())
+            {
+                TParentNodeSet *newTopSet = mNodeSets.top();
+                newTopSet->insert(oldTopSet->begin(), oldTopSet->end());
+            }
+
+            delete oldTopSet;
+        }
+
+        // Does nothing if there is no top set.
+        // This can be called when there is no top set if we are visiting
+        // symbols that are not under an assignment or condition.
+        // We don't need to track those symbols.
+        void insertIntoTopSet(TGraphParentNode *node)
+        {
+            if (mNodeSets.empty())
+                return;
+
+            mNodeSets.top()->insert(node);
+        }
+
+        void clear()
+        {
+            while (!mNodeSets.empty())
+                popSet();
+        }
+
+      private:
+        typedef std::stack<TParentNodeSet *> TParentNodeSetStack;
+
+        TParentNodeSetStack mNodeSets;
+    };
+
+    //
+    // An instance of this class pushes a new node set when instantiated.
+    // When the instance goes out of scope, it and pops the node set.
+    //
+    class TNodeSetMaintainer : angle::NonCopyable
+    {
+      public:
+        TNodeSetMaintainer(TDependencyGraphBuilder *factory)
+            : mSets(factory->mNodeSets)
+        {
+            mSets.pushSet();
+        }
+        ~TNodeSetMaintainer() { mSets.popSet(); }
+      protected:
+        TNodeSetStack &mSets;
+    };
+
+    //
+    // An instance of this class pushes a new node set when instantiated.
+    // When the instance goes out of scope, it and pops the top node set and adds
+    // its contents to the new top node set.
+    //
+    class TNodeSetPropagatingMaintainer : angle::NonCopyable
+    {
+      public:
+        TNodeSetPropagatingMaintainer(TDependencyGraphBuilder *factory)
+            : mSets(factory->mNodeSets)
+        {
+            mSets.pushSet();
+        }
+        ~TNodeSetPropagatingMaintainer() { mSets.popSetIntoNext(); }
+      protected:
+        TNodeSetStack &mSets;
+    };
+
+    //
+    // An instance of this class keeps track of the leftmost symbol while we're
+    // exploring an assignment.
+    // It will push the placeholder symbol kLeftSubtree when instantiated under a
+    // left subtree, and kRightSubtree under a right subtree.
+    // When it goes out of scope, it will pop the leftmost symbol at the top of the
+    // scope.
+    // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with
+    // a real symbol.
+    // kRightSubtree will never be replaced by a real symbol because we are tracking
+    // the leftmost symbol.
+    //
+    class TLeftmostSymbolMaintainer : angle::NonCopyable
+    {
+      public:
+        TLeftmostSymbolMaintainer(
+            TDependencyGraphBuilder *factory, TGraphSymbol &subtree)
+            : mLeftmostSymbols(factory->mLeftmostSymbols)
+        {
+            mNeedsPlaceholderSymbol =
+                mLeftmostSymbols.empty() || mLeftmostSymbols.top() != &subtree;
+            if (mNeedsPlaceholderSymbol)
+                mLeftmostSymbols.push(&subtree);
+        }
+
+        ~TLeftmostSymbolMaintainer()
+        {
+            if (mNeedsPlaceholderSymbol)
+                mLeftmostSymbols.pop();
+        }
+
+      protected:
+        TSymbolStack& mLeftmostSymbols;
+        bool mNeedsPlaceholderSymbol;
+    };
+
+    TDependencyGraphBuilder(TDependencyGraph *graph)
+        : TIntermTraverser(true, false, false),
+          mLeftSubtree(NULL),
+          mRightSubtree(NULL),
+          mGraph(graph) {}
+    void build(TIntermNode *intermNode) { intermNode->traverse(this); }
+
+    void connectMultipleNodesToSingleNode(
+        TParentNodeSet *nodes, TGraphNode *node) const;
+
+    void visitAssignment(TIntermBinary *);
+    void visitLogicalOp(TIntermBinary *);
+    void visitBinaryChildren(TIntermBinary *);
+    void visitFunctionDefinition(TIntermAggregate *);
+    void visitFunctionCall(TIntermAggregate *intermFunctionCall);
+    void visitAggregateChildren(TIntermAggregate *);
+
+    TGraphSymbol mLeftSubtree;
+    TGraphSymbol mRightSubtree;
+
+    TDependencyGraph *mGraph;
+    TNodeSetStack mNodeSets;
+    TSymbolStack mLeftmostSymbols;
+};
+
+#endif  // COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCYGRAPHBUILDER_H_
diff --git a/gfx/angle/src/compiler/translator/depgraph/DependencyGraphOutput.cpp b/gfx/angle/src/compiler/translator/depgraph/DependencyGraphOutput.cpp
new file mode 100644
index 000000000..32a2f3014
--- /dev/null
+++ b/gfx/angle/src/compiler/translator/depgraph/DependencyGraphOutput.cpp
@@ -0,0 +1,64 @@
+//
+// 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/DependencyGraphOutput.h"
+
+void TDependencyGraphOutput::outputIndentation()
+{
+    for (int i = 0; i < getDepth(); ++i)
+        mSink << "  ";
+}
+
+void TDependencyGraphOutput::visitArgument(TGraphArgument* parameter)
+{
+    outputIndentation();
+    mSink << "argument " << parameter->getArgumentNumber() << " of call to "
+          << parameter->getIntermFunctionCall()->getName() << "\n";
+}
+
+void TDependencyGraphOutput::visitFunctionCall(TGraphFunctionCall* functionCall)
+{
+    outputIndentation();
+    mSink << "function call " <<  functionCall->getIntermFunctionCall()->getName() << "\n";
+}
+
+void TDependencyGraphOutput::visitSymbol(TGraphSymbol* symbol)
+{
+    outputIndentation();
+    mSink << symbol->getIntermSymbol()->getSymbol() << " (symbol id: "
+          << symbol->getIntermSymbol()->getId() << ")\n";
+}
+
+void TDependencyGraphOutput::visitSelection(TGraphSelection* selection)
+{
+    outputIndentation();
+    mSink << "selection\n";
+}
+
+void TDependencyGraphOutput::visitLoop(TGraphLoop* loop)
+{
+    outputIndentation();
+    mSink << "loop condition\n";
+}
+
+void TDependencyGraphOutput::visitLogicalOp(TGraphLogicalOp* logicalOp)
+{
+    outputIndentation();
+    mSink << "logical " << logicalOp->getOpString() << "\n";
+}
+
+void TDependencyGraphOutput::outputAllSpanningTrees(TDependencyGraph& graph)
+{
+    mSink << "\n";
+
+    for (auto symbol : graph.allNodes())
+    {
+        mSink << "--- Dependency graph spanning tree ---\n";
+        clearVisited();
+        symbol->traverse(this);
+        mSink << "\n";
+    }
+}
diff --git a/gfx/angle/src/compiler/translator/depgraph/DependencyGraphOutput.h b/gfx/angle/src/compiler/translator/depgraph/DependencyGraphOutput.h
new file mode 100644
index 000000000..b201e0a67
--- /dev/null
+++ b/gfx/angle/src/compiler/translator/depgraph/DependencyGraphOutput.h
@@ -0,0 +1,31 @@
+//
+// 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.
+//
+
+#ifndef COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCYGRAPHOUTPUT_H_
+#define COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCYGRAPHOUTPUT_H_
+
+#include "compiler/translator/depgraph/DependencyGraph.h"
+#include "compiler/translator/InfoSink.h"
+
+class TDependencyGraphOutput : public TDependencyGraphTraverser
+{
+  public:
+    TDependencyGraphOutput(TInfoSinkBase& sink) : mSink(sink) {}
+    void visitSymbol(TGraphSymbol* symbol) override;
+    void visitArgument(TGraphArgument* parameter) override;
+    void visitFunctionCall(TGraphFunctionCall* functionCall) override;
+    void visitSelection(TGraphSelection* selection) override;
+    void visitLoop(TGraphLoop* loop) override;
+    void visitLogicalOp(TGraphLogicalOp* logicalOp) override;
+
+    void outputAllSpanningTrees(TDependencyGraph& graph);
+  private:
+    void outputIndentation();
+
+    TInfoSinkBase& mSink;
+};
+
+#endif  // COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCYGRAPHOUTPUT_H_
diff --git a/gfx/angle/src/compiler/translator/depgraph/DependencyGraphTraverse.cpp b/gfx/angle/src/compiler/translator/depgraph/DependencyGraphTraverse.cpp
new file mode 100644
index 000000000..197fde97e
--- /dev/null
+++ b/gfx/angle/src/compiler/translator/depgraph/DependencyGraphTraverse.cpp
@@ -0,0 +1,69 @@
+//
+// 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/DependencyGraph.h"
+
+// These methods do a breadth-first traversal through the graph and mark visited nodes.
+
+void TGraphNode::traverse(TDependencyGraphTraverser* graphTraverser)
+{
+    graphTraverser->markVisited(this);
+}
+
+void TGraphParentNode::traverse(TDependencyGraphTraverser* graphTraverser)
+{
+    TGraphNode::traverse(graphTraverser);
+
+    graphTraverser->incrementDepth();
+
+    // Visit the parent node's children.
+    for (TGraphNodeSet::const_iterator iter = mDependentNodes.begin();
+         iter != mDependentNodes.end();
+         ++iter)
+    {
+        TGraphNode* node = *iter;
+        if (!graphTraverser->isVisited(node))
+            node->traverse(graphTraverser);
+    }
+
+    graphTraverser->decrementDepth();
+}
+
+void TGraphArgument::traverse(TDependencyGraphTraverser* graphTraverser)
+{
+    graphTraverser->visitArgument(this);
+    TGraphParentNode::traverse(graphTraverser);
+}
+
+void TGraphFunctionCall::traverse(TDependencyGraphTraverser* graphTraverser)
+{
+    graphTraverser->visitFunctionCall(this);
+    TGraphParentNode::traverse(graphTraverser);
+}
+
+void TGraphSymbol::traverse(TDependencyGraphTraverser* graphTraverser)
+{
+    graphTraverser->visitSymbol(this);
+    TGraphParentNode::traverse(graphTraverser);
+}
+
+void TGraphSelection::traverse(TDependencyGraphTraverser* graphTraverser)
+{
+    graphTraverser->visitSelection(this);
+    TGraphNode::traverse(graphTraverser);
+}
+
+void TGraphLoop::traverse(TDependencyGraphTraverser* graphTraverser)
+{
+    graphTraverser->visitLoop(this);
+    TGraphNode::traverse(graphTraverser);
+}
+
+void TGraphLogicalOp::traverse(TDependencyGraphTraverser* graphTraverser)
+{
+    graphTraverser->visitLogicalOp(this);
+    TGraphNode::traverse(graphTraverser);
+}