1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
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_
|
