diff options
Diffstat (limited to 'src/3rdparty/angle/src/compiler/translator/depgraph')
7 files changed, 881 insertions, 0 deletions
diff --git a/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraph.cpp b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraph.cpp new file mode 100644 index 0000000000..19ddf5c439 --- /dev/null +++ b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraph.cpp @@ -0,0 +1,97 @@ +// +// 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. +// + +#pragma warning(disable: 4718) + +#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/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraph.h b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraph.h new file mode 100644 index 0000000000..5ea1cbb837 --- /dev/null +++ b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraph.h @@ -0,0 +1,212 @@ +// +// 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_DEPGRAPH_DEPENDENCY_GRAPH_H +#define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_H + +#include "compiler/translator/intermediate.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) {} + virtual ~TGraphParentNode() {} + void addDependentNode(TGraphNode* node) { if (node != this) mDependentNodes.insert(node); } + virtual void traverse(TDependencyGraphTraverser* graphTraverser); +private: + TGraphNodeSet mDependentNodes; +}; + +// +// Handle function call arguments. +// +class TGraphArgument : public TGraphParentNode { +public: + TGraphArgument(TIntermAggregate* intermFunctionCall, int argumentNumber) + : TGraphParentNode(intermFunctionCall) + , mArgumentNumber(argumentNumber) {} + virtual ~TGraphArgument() {} + const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); } + int getArgumentNumber() const { return mArgumentNumber; } + virtual void traverse(TDependencyGraphTraverser* graphTraverser); +private: + int mArgumentNumber; +}; + +// +// Handle function calls. +// +class TGraphFunctionCall : public TGraphParentNode { +public: + TGraphFunctionCall(TIntermAggregate* intermFunctionCall) + : TGraphParentNode(intermFunctionCall) {} + virtual ~TGraphFunctionCall() {} + const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); } + virtual void traverse(TDependencyGraphTraverser* graphTraverser); +}; + +// +// Handle symbols. +// +class TGraphSymbol : public TGraphParentNode { +public: + TGraphSymbol(TIntermSymbol* intermSymbol) : TGraphParentNode(intermSymbol) {} + virtual ~TGraphSymbol() {} + const TIntermSymbol* getIntermSymbol() const { return intermNode->getAsSymbolNode(); } + virtual void traverse(TDependencyGraphTraverser* graphTraverser); +}; + +// +// Handle if statements and ternary operators. +// +class TGraphSelection : public TGraphNode { +public: + TGraphSelection(TIntermSelection* intermSelection) : TGraphNode(intermSelection) {} + virtual ~TGraphSelection() {} + const TIntermSelection* getIntermSelection() const { return intermNode->getAsSelectionNode(); } + virtual void traverse(TDependencyGraphTraverser* graphTraverser); +}; + +// +// Handle for, do-while, and while loops. +// +class TGraphLoop : public TGraphNode { +public: + TGraphLoop(TIntermLoop* intermLoop) : TGraphNode(intermLoop) {} + virtual ~TGraphLoop() {} + const TIntermLoop* getIntermLoop() const { return intermNode->getAsLoopNode(); } + virtual void traverse(TDependencyGraphTraverser* graphTraverser); +}; + +// +// Handle logical and, or. +// +class TGraphLogicalOp : public TGraphNode { +public: + TGraphLogicalOp(TIntermBinary* intermLogicalOp) : TGraphNode(intermLogicalOp) {} + virtual ~TGraphLogicalOp() {} + const TIntermBinary* getIntermLogicalOp() const { return intermNode->getAsBinaryNode(); } + const char* getOpString() const; + virtual void traverse(TDependencyGraphTraverser* graphTraverser); +}; + +// +// 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(); + TGraphNodeVector::const_iterator begin() const { return mAllNodes.begin(); } + TGraphNodeVector::const_iterator end() const { return mAllNodes.end(); } + + TGraphSymbolVector::const_iterator beginSamplerSymbols() const + { + return mSamplerSymbols.begin(); + } + + TGraphSymbolVector::const_iterator endSamplerSymbols() const + { + return mSamplerSymbols.end(); + } + + TFunctionCallVector::const_iterator beginUserDefinedFunctionCalls() const + { + return mUserDefinedFunctionCalls.begin(); + } + + TFunctionCallVector::const_iterator endUserDefinedFunctionCalls() const + { + return mUserDefinedFunctionCalls.end(); + } + + 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 { +public: + TDependencyGraphTraverser() : mDepth(0) {} + + 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 diff --git a/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.cpp b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.cpp new file mode 100644 index 0000000000..d5f2cba5fc --- /dev/null +++ b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.cpp @@ -0,0 +1,227 @@ +// +// 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/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h new file mode 100644 index 0000000000..3e928fb77e --- /dev/null +++ b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h @@ -0,0 +1,181 @@ +// +// 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_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H +#define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_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); + + virtual void visitSymbol(TIntermSymbol*); + virtual bool visitBinary(Visit visit, TIntermBinary*); + virtual bool visitSelection(Visit visit, TIntermSelection*); + virtual bool visitAggregate(Visit visit, TIntermAggregate*); + virtual bool visitLoop(Visit visit, TIntermLoop*); + +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(!nodeSets.empty()); + TParentNodeSet* topSet = nodeSets.top(); + return !topSet->empty() ? topSet : NULL; + } + + void pushSet() { nodeSets.push(new TParentNodeSet()); } + void popSet() + { + ASSERT(!nodeSets.empty()); + delete nodeSets.top(); + nodeSets.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(!nodeSets.empty()); + TParentNodeSet* oldTopSet = nodeSets.top(); + nodeSets.pop(); + + if (!nodeSets.empty()) { + TParentNodeSet* newTopSet = nodeSets.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 (nodeSets.empty()) + return; + + nodeSets.top()->insert(node); + } + + void clear() + { + while (!nodeSets.empty()) + popSet(); + } + + private: + typedef std::stack<TParentNodeSet*> TParentNodeSetStack; + + TParentNodeSetStack nodeSets; + }; + + // + // 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 { + public: + TNodeSetMaintainer(TDependencyGraphBuilder* factory) + : sets(factory->mNodeSets) { sets.pushSet(); } + ~TNodeSetMaintainer() { sets.popSet(); } + protected: + TNodeSetStack& sets; + }; + + // + // 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 { + public: + TNodeSetPropagatingMaintainer(TDependencyGraphBuilder* factory) + : sets(factory->mNodeSets) { sets.pushSet(); } + ~TNodeSetPropagatingMaintainer() { sets.popSetIntoNext(); } + protected: + TNodeSetStack& sets; + }; + + // + // 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 { + public: + TLeftmostSymbolMaintainer(TDependencyGraphBuilder* factory, TGraphSymbol& subtree) + : leftmostSymbols(factory->mLeftmostSymbols) + { + needsPlaceholderSymbol = leftmostSymbols.empty() || leftmostSymbols.top() != &subtree; + if (needsPlaceholderSymbol) + leftmostSymbols.push(&subtree); + } + + ~TLeftmostSymbolMaintainer() + { + if (needsPlaceholderSymbol) + leftmostSymbols.pop(); + } + + protected: + TSymbolStack& leftmostSymbols; + bool needsPlaceholderSymbol; + }; + + 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_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H diff --git a/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphOutput.cpp b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphOutput.cpp new file mode 100644 index 0000000000..e226333545 --- /dev/null +++ b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphOutput.cpp @@ -0,0 +1,65 @@ +// +// 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 (TGraphNodeVector::const_iterator iter = graph.begin(); iter != graph.end(); ++iter) + { + TGraphNode* symbol = *iter; + mSink << "--- Dependency graph spanning tree ---\n"; + clearVisited(); + symbol->traverse(this); + mSink << "\n"; + } +} diff --git a/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphOutput.h b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphOutput.h new file mode 100644 index 0000000000..c3a4112278 --- /dev/null +++ b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphOutput.h @@ -0,0 +1,30 @@ +// +// 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_DEPGRAPH_DEPENDENCY_GRAPH_OUTPUT_H +#define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_OUTPUT_H + +#include "compiler/translator/depgraph/DependencyGraph.h" +#include "compiler/translator/InfoSink.h" + +class TDependencyGraphOutput : public TDependencyGraphTraverser { +public: + TDependencyGraphOutput(TInfoSinkBase& sink) : mSink(sink) {} + virtual void visitSymbol(TGraphSymbol* symbol); + virtual void visitArgument(TGraphArgument* parameter); + virtual void visitFunctionCall(TGraphFunctionCall* functionCall); + virtual void visitSelection(TGraphSelection* selection); + virtual void visitLoop(TGraphLoop* loop); + virtual void visitLogicalOp(TGraphLogicalOp* logicalOp); + + void outputAllSpanningTrees(TDependencyGraph& graph); +private: + void outputIndentation(); + + TInfoSinkBase& mSink; +}; + +#endif // COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_OUTPUT_H diff --git a/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphTraverse.cpp b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphTraverse.cpp new file mode 100644 index 0000000000..197fde97e2 --- /dev/null +++ b/src/3rdparty/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); +} |