1//
2// Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.
3// Use of this source code is governed by a BSD-style license that can be
4// found in the LICENSE file.
5//
6
7#ifndef COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
8#define COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
9
10#include "compiler/translator/depgraph/DependencyGraph.h"
11
12//
13// Creates a dependency graph of symbols, function calls, conditions etc. by
14// traversing a intermediate tree.
15//
16class TDependencyGraphBuilder : public TIntermTraverser
17{
18  public:
19    static void build(TIntermNode *node, TDependencyGraph *graph);
20
21    virtual void visitSymbol(TIntermSymbol *);
22    virtual bool visitBinary(Visit visit, TIntermBinary *);
23    virtual bool visitSelection(Visit visit, TIntermSelection *);
24    virtual bool visitAggregate(Visit visit, TIntermAggregate *);
25    virtual bool visitLoop(Visit visit, TIntermLoop *);
26
27  private:
28    typedef std::stack<TGraphSymbol *> TSymbolStack;
29    typedef std::set<TGraphParentNode *> TParentNodeSet;
30
31    //
32    // For collecting the dependent nodes of assignments, conditions, etc.
33    // while traversing the intermediate tree.
34    //
35    // This data structure is stack of sets. Each set contains dependency graph
36    // parent nodes.
37    //
38    class TNodeSetStack
39    {
40      public:
41        TNodeSetStack() {};
42        ~TNodeSetStack() { clear(); }
43
44        // This should only be called after a pushSet.
45        // Returns NULL if the top set is empty.
46        TParentNodeSet *getTopSet() const
47        {
48            ASSERT(!mNodeSets.empty());
49            TParentNodeSet *topSet = mNodeSets.top();
50            return !topSet->empty() ? topSet : NULL;
51        }
52
53        void pushSet() { mNodeSets.push(new TParentNodeSet()); }
54        void popSet()
55        {
56            ASSERT(!mNodeSets.empty());
57            delete mNodeSets.top();
58            mNodeSets.pop();
59        }
60
61        // Pops the top set and adds its contents to the new top set.
62        // This should only be called after a pushSet.
63        // If there is no set below the top set, the top set is just deleted.
64        void popSetIntoNext()
65        {
66            ASSERT(!mNodeSets.empty());
67            TParentNodeSet *oldTopSet = mNodeSets.top();
68            mNodeSets.pop();
69
70            if (!mNodeSets.empty())
71            {
72                TParentNodeSet *newTopSet = mNodeSets.top();
73                newTopSet->insert(oldTopSet->begin(), oldTopSet->end());
74            }
75
76            delete oldTopSet;
77        }
78
79        // Does nothing if there is no top set.
80        // This can be called when there is no top set if we are visiting
81        // symbols that are not under an assignment or condition.
82        // We don't need to track those symbols.
83        void insertIntoTopSet(TGraphParentNode *node)
84        {
85            if (mNodeSets.empty())
86                return;
87
88            mNodeSets.top()->insert(node);
89        }
90
91        void clear()
92        {
93            while (!mNodeSets.empty())
94                popSet();
95        }
96
97      private:
98        typedef std::stack<TParentNodeSet *> TParentNodeSetStack;
99
100        TParentNodeSetStack mNodeSets;
101    };
102
103    //
104    // An instance of this class pushes a new node set when instantiated.
105    // When the instance goes out of scope, it and pops the node set.
106    //
107    class TNodeSetMaintainer
108    {
109      public:
110        TNodeSetMaintainer(TDependencyGraphBuilder *factory)
111            : mSets(factory->mNodeSets)
112        {
113            mSets.pushSet();
114        }
115        ~TNodeSetMaintainer() { mSets.popSet(); }
116      protected:
117        TNodeSetStack &mSets;
118    };
119
120    //
121    // An instance of this class pushes a new node set when instantiated.
122    // When the instance goes out of scope, it and pops the top node set and adds
123    // its contents to the new top node set.
124    //
125    class TNodeSetPropagatingMaintainer
126    {
127      public:
128        TNodeSetPropagatingMaintainer(TDependencyGraphBuilder *factory)
129            : mSets(factory->mNodeSets)
130        {
131            mSets.pushSet();
132        }
133        ~TNodeSetPropagatingMaintainer() { mSets.popSetIntoNext(); }
134      protected:
135        TNodeSetStack &mSets;
136    };
137
138    //
139    // An instance of this class keeps track of the leftmost symbol while we're
140    // exploring an assignment.
141    // It will push the placeholder symbol kLeftSubtree when instantiated under a
142    // left subtree, and kRightSubtree under a right subtree.
143    // When it goes out of scope, it will pop the leftmost symbol at the top of the
144    // scope.
145    // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with
146    // a real symbol.
147    // kRightSubtree will never be replaced by a real symbol because we are tracking
148    // the leftmost symbol.
149    //
150    class TLeftmostSymbolMaintainer
151    {
152      public:
153        TLeftmostSymbolMaintainer(
154            TDependencyGraphBuilder *factory, TGraphSymbol &subtree)
155            : mLeftmostSymbols(factory->mLeftmostSymbols)
156        {
157            mNeedsPlaceholderSymbol =
158                mLeftmostSymbols.empty() || mLeftmostSymbols.top() != &subtree;
159            if (mNeedsPlaceholderSymbol)
160                mLeftmostSymbols.push(&subtree);
161        }
162
163        ~TLeftmostSymbolMaintainer()
164        {
165            if (mNeedsPlaceholderSymbol)
166                mLeftmostSymbols.pop();
167        }
168
169      protected:
170        TSymbolStack& mLeftmostSymbols;
171        bool mNeedsPlaceholderSymbol;
172    };
173
174    TDependencyGraphBuilder(TDependencyGraph *graph)
175        : TIntermTraverser(true, false, false),
176          mLeftSubtree(NULL),
177          mRightSubtree(NULL),
178          mGraph(graph) {}
179    void build(TIntermNode *intermNode) { intermNode->traverse(this); }
180
181    void connectMultipleNodesToSingleNode(
182        TParentNodeSet *nodes, TGraphNode *node) const;
183
184    void visitAssignment(TIntermBinary *);
185    void visitLogicalOp(TIntermBinary *);
186    void visitBinaryChildren(TIntermBinary *);
187    void visitFunctionDefinition(TIntermAggregate *);
188    void visitFunctionCall(TIntermAggregate *intermFunctionCall);
189    void visitAggregateChildren(TIntermAggregate *);
190
191    TGraphSymbol mLeftSubtree;
192    TGraphSymbol mRightSubtree;
193
194    TDependencyGraph *mGraph;
195    TNodeSetStack mNodeSets;
196    TSymbolStack mLeftmostSymbols;
197};
198
199#endif  // COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
200