diff options
Diffstat (limited to 'gfx/angle/src/compiler/translator/depgraph')
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); +} |