← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/ThirdParty/ANGLE/src/compiler/depgraph/DependencyGraphBuilder.h

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

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