michael@0: //
michael@0: // Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: //
michael@0: 
michael@0: #ifndef COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_H
michael@0: #define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_H
michael@0: 
michael@0: #include "compiler/intermediate.h"
michael@0: 
michael@0: #include <set>
michael@0: #include <stack>
michael@0: 
michael@0: class TGraphNode;
michael@0: class TGraphParentNode;
michael@0: class TGraphArgument;
michael@0: class TGraphFunctionCall;
michael@0: class TGraphSymbol;
michael@0: class TGraphSelection;
michael@0: class TGraphLoop;
michael@0: class TGraphLogicalOp;
michael@0: class TDependencyGraphTraverser;
michael@0: class TDependencyGraphOutput;
michael@0: 
michael@0: typedef std::set<TGraphNode*> TGraphNodeSet;
michael@0: typedef std::vector<TGraphNode*> TGraphNodeVector;
michael@0: typedef std::vector<TGraphSymbol*> TGraphSymbolVector;
michael@0: typedef std::vector<TGraphFunctionCall*> TFunctionCallVector;
michael@0: 
michael@0: //
michael@0: // Base class for all dependency graph nodes.
michael@0: //
michael@0: class TGraphNode {
michael@0: public:
michael@0:     TGraphNode(TIntermNode* node) : intermNode(node) {}
michael@0:     virtual ~TGraphNode() {}
michael@0:     virtual void traverse(TDependencyGraphTraverser* graphTraverser);
michael@0: protected:
michael@0:     TIntermNode* intermNode;
michael@0: };
michael@0: 
michael@0: //
michael@0: // Base class for dependency graph nodes that may have children.
michael@0: //
michael@0: class TGraphParentNode : public TGraphNode {
michael@0: public:
michael@0:     TGraphParentNode(TIntermNode* node) : TGraphNode(node) {}
michael@0:     virtual ~TGraphParentNode() {}
michael@0:     void addDependentNode(TGraphNode* node) { if (node != this) mDependentNodes.insert(node); }
michael@0:     virtual void traverse(TDependencyGraphTraverser* graphTraverser);
michael@0: private:
michael@0:     TGraphNodeSet mDependentNodes;
michael@0: };
michael@0: 
michael@0: //
michael@0: // Handle function call arguments.
michael@0: //
michael@0: class TGraphArgument : public TGraphParentNode {
michael@0: public:
michael@0:     TGraphArgument(TIntermAggregate* intermFunctionCall, int argumentNumber)
michael@0:         : TGraphParentNode(intermFunctionCall)
michael@0:         , mArgumentNumber(argumentNumber) {}
michael@0:     virtual ~TGraphArgument() {}
michael@0:     const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); }
michael@0:     int getArgumentNumber() const { return mArgumentNumber; }
michael@0:     virtual void traverse(TDependencyGraphTraverser* graphTraverser);
michael@0: private:
michael@0:     int mArgumentNumber;
michael@0: };
michael@0: 
michael@0: //
michael@0: // Handle function calls.
michael@0: //
michael@0: class TGraphFunctionCall : public TGraphParentNode {
michael@0: public:
michael@0:     TGraphFunctionCall(TIntermAggregate* intermFunctionCall)
michael@0:         : TGraphParentNode(intermFunctionCall) {}
michael@0:     virtual ~TGraphFunctionCall() {}
michael@0:     const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); }
michael@0:     virtual void traverse(TDependencyGraphTraverser* graphTraverser);
michael@0: };
michael@0: 
michael@0: //
michael@0: // Handle symbols.
michael@0: //
michael@0: class TGraphSymbol : public TGraphParentNode {
michael@0: public:
michael@0:     TGraphSymbol(TIntermSymbol* intermSymbol) : TGraphParentNode(intermSymbol) {}
michael@0:     virtual ~TGraphSymbol() {}
michael@0:     const TIntermSymbol* getIntermSymbol() const { return intermNode->getAsSymbolNode(); }
michael@0:     virtual void traverse(TDependencyGraphTraverser* graphTraverser);
michael@0: };
michael@0: 
michael@0: //
michael@0: // Handle if statements and ternary operators.
michael@0: //
michael@0: class TGraphSelection : public TGraphNode {
michael@0: public:
michael@0:     TGraphSelection(TIntermSelection* intermSelection) : TGraphNode(intermSelection) {}
michael@0:     virtual ~TGraphSelection() {}
michael@0:     const TIntermSelection* getIntermSelection() const { return intermNode->getAsSelectionNode(); }
michael@0:     virtual void traverse(TDependencyGraphTraverser* graphTraverser);
michael@0: };
michael@0: 
michael@0: //
michael@0: // Handle for, do-while, and while loops.
michael@0: //
michael@0: class TGraphLoop : public TGraphNode {
michael@0: public:
michael@0:     TGraphLoop(TIntermLoop* intermLoop) : TGraphNode(intermLoop) {}
michael@0:     virtual ~TGraphLoop() {}
michael@0:     const TIntermLoop* getIntermLoop() const { return intermNode->getAsLoopNode(); }
michael@0:     virtual void traverse(TDependencyGraphTraverser* graphTraverser);
michael@0: };
michael@0: 
michael@0: //
michael@0: // Handle logical and, or.
michael@0: //
michael@0: class TGraphLogicalOp : public TGraphNode {
michael@0: public:
michael@0:     TGraphLogicalOp(TIntermBinary* intermLogicalOp) : TGraphNode(intermLogicalOp) {}
michael@0:     virtual ~TGraphLogicalOp() {}
michael@0:     const TIntermBinary* getIntermLogicalOp() const { return intermNode->getAsBinaryNode(); }
michael@0:     const char* getOpString() const;
michael@0:     virtual void traverse(TDependencyGraphTraverser* graphTraverser);
michael@0: };
michael@0: 
michael@0: //
michael@0: // A dependency graph of symbols, function calls, conditions etc.
michael@0: //
michael@0: // This class provides an interface to the entry points of the dependency graph.
michael@0: //
michael@0: // Dependency graph nodes should be created by using one of the provided "create..." methods.
michael@0: // This class (and nobody else) manages the memory of the created nodes.
michael@0: // Nodes may not be removed after being added, so all created nodes will exist while the
michael@0: // TDependencyGraph instance exists.
michael@0: //
michael@0: class TDependencyGraph {
michael@0: public:
michael@0:     TDependencyGraph(TIntermNode* intermNode);
michael@0:     ~TDependencyGraph();
michael@0:     TGraphNodeVector::const_iterator begin() const { return mAllNodes.begin(); }
michael@0:     TGraphNodeVector::const_iterator end() const { return mAllNodes.end(); }
michael@0: 
michael@0:     TGraphSymbolVector::const_iterator beginSamplerSymbols() const
michael@0:     {
michael@0:         return mSamplerSymbols.begin();
michael@0:     }
michael@0: 
michael@0:     TGraphSymbolVector::const_iterator endSamplerSymbols() const
michael@0:     {
michael@0:         return mSamplerSymbols.end();
michael@0:     }
michael@0: 
michael@0:     TFunctionCallVector::const_iterator beginUserDefinedFunctionCalls() const
michael@0:     {
michael@0:         return mUserDefinedFunctionCalls.begin();
michael@0:     }
michael@0: 
michael@0:     TFunctionCallVector::const_iterator endUserDefinedFunctionCalls() const
michael@0:     {
michael@0:         return mUserDefinedFunctionCalls.end();
michael@0:     }
michael@0: 
michael@0:     TGraphArgument* createArgument(TIntermAggregate* intermFunctionCall, int argumentNumber);
michael@0:     TGraphFunctionCall* createFunctionCall(TIntermAggregate* intermFunctionCall);
michael@0:     TGraphSymbol* getOrCreateSymbol(TIntermSymbol* intermSymbol);
michael@0:     TGraphSelection* createSelection(TIntermSelection* intermSelection);
michael@0:     TGraphLoop* createLoop(TIntermLoop* intermLoop);
michael@0:     TGraphLogicalOp* createLogicalOp(TIntermBinary* intermLogicalOp);
michael@0: private:
michael@0:     typedef TMap<int, TGraphSymbol*> TSymbolIdMap;
michael@0:     typedef std::pair<int, TGraphSymbol*> TSymbolIdPair;
michael@0: 
michael@0:     TGraphNodeVector mAllNodes;
michael@0:     TGraphSymbolVector mSamplerSymbols;
michael@0:     TFunctionCallVector mUserDefinedFunctionCalls;
michael@0:     TSymbolIdMap mSymbolIdMap;
michael@0: };
michael@0: 
michael@0: //
michael@0: // For traversing the dependency graph. Users should derive from this,
michael@0: // put their traversal specific data in it, and then pass it to a
michael@0: // traverse method.
michael@0: //
michael@0: // When using this, just fill in the methods for nodes you want visited.
michael@0: //
michael@0: class TDependencyGraphTraverser {
michael@0: public:
michael@0:     TDependencyGraphTraverser() : mDepth(0) {}
michael@0: 
michael@0:     virtual void visitSymbol(TGraphSymbol* symbol) {};
michael@0:     virtual void visitArgument(TGraphArgument* selection) {};
michael@0:     virtual void visitFunctionCall(TGraphFunctionCall* functionCall) {};
michael@0:     virtual void visitSelection(TGraphSelection* selection) {};
michael@0:     virtual void visitLoop(TGraphLoop* loop) {};
michael@0:     virtual void visitLogicalOp(TGraphLogicalOp* logicalOp) {};
michael@0: 
michael@0:     int getDepth() const { return mDepth; }
michael@0:     void incrementDepth() { ++mDepth; }
michael@0:     void decrementDepth() { --mDepth; }
michael@0: 
michael@0:     void clearVisited() { mVisited.clear(); }
michael@0:     void markVisited(TGraphNode* node) { mVisited.insert(node); }
michael@0:     bool isVisited(TGraphNode* node) const { return mVisited.find(node) != mVisited.end(); }
michael@0: private:
michael@0:     int mDepth;
michael@0:     TGraphNodeSet mVisited;
michael@0: };
michael@0: 
michael@0: #endif