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#include "compiler/translator/depgraph/DependencyGraphBuilder.h"
8
9void TDependencyGraphBuilder::build(TIntermNode *node, TDependencyGraph *graph)
10{
11    TDependencyGraphBuilder builder(graph);
12    builder.build(node);
13}
14
15bool TDependencyGraphBuilder::visitAggregate(
16    Visit visit, TIntermAggregate *intermAggregate)
17{
18    switch (intermAggregate->getOp())
19    {
20      case EOpFunction:
21        visitFunctionDefinition(intermAggregate);
22        break;
23      case EOpFunctionCall:
24        visitFunctionCall(intermAggregate);
25        break;
26      default:
27        visitAggregateChildren(intermAggregate);
28        break;
29    }
30    return false;
31}
32
33void TDependencyGraphBuilder::visitFunctionDefinition(
34    TIntermAggregate *intermAggregate)
35{
36    // Currently, we do not support user defined functions.
37    if (intermAggregate->getName() != "main(")
38        return;
39
40    visitAggregateChildren(intermAggregate);
41}
42
43// Takes an expression like "f(x)" and creates a dependency graph like
44// "x -> argument 0 -> function call".
45void TDependencyGraphBuilder::visitFunctionCall(
46    TIntermAggregate *intermFunctionCall)
47{
48    TGraphFunctionCall *functionCall =
49        mGraph->createFunctionCall(intermFunctionCall);
50
51    // Run through the function call arguments.
52    int argumentNumber = 0;
53    TIntermSequence *intermArguments = intermFunctionCall->getSequence();
54    for (TIntermSequence::const_iterator iter = intermArguments->begin();
55         iter != intermArguments->end();
56         ++iter, ++argumentNumber)
57    {
58        TNodeSetMaintainer nodeSetMaintainer(this);
59
60        TIntermNode *intermArgument = *iter;
61        intermArgument->traverse(this);
62
63        if (TParentNodeSet *argumentNodes = mNodeSets.getTopSet())
64        {
65            TGraphArgument *argument = mGraph->createArgument(
66                intermFunctionCall, argumentNumber);
67            connectMultipleNodesToSingleNode(argumentNodes, argument);
68            argument->addDependentNode(functionCall);
69        }
70    }
71
72    // Push the leftmost symbol of this function call into the current set of
73    // dependent symbols to represent the result of this function call.
74    // Thus, an expression like "y = f(x)" will yield a dependency graph like
75    // "x -> argument 0 -> function call -> y".
76    // This line essentially passes the function call node back up to an earlier
77    // visitAssignment call, which will create the connection "function call -> y".
78    mNodeSets.insertIntoTopSet(functionCall);
79}
80
81void TDependencyGraphBuilder::visitAggregateChildren(
82    TIntermAggregate *intermAggregate)
83{
84    TIntermSequence *sequence = intermAggregate->getSequence();
85    for (TIntermSequence::const_iterator iter = sequence->begin();
86         iter != sequence->end(); ++iter)
87    {
88        TIntermNode *intermChild = *iter;
89        intermChild->traverse(this);
90    }
91}
92
93void TDependencyGraphBuilder::visitSymbol(TIntermSymbol *intermSymbol)
94{
95    // Push this symbol into the set of dependent symbols for the current
96    // assignment or condition that we are traversing.
97    TGraphSymbol *symbol = mGraph->getOrCreateSymbol(intermSymbol);
98    mNodeSets.insertIntoTopSet(symbol);
99
100    // If this symbol is the current leftmost symbol under an assignment, replace
101    // the previous leftmost symbol with this symbol.
102    if (!mLeftmostSymbols.empty() && mLeftmostSymbols.top() != &mRightSubtree)
103    {
104        mLeftmostSymbols.pop();
105        mLeftmostSymbols.push(symbol);
106    }
107}
108
109bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary *intermBinary)
110{
111    TOperator op = intermBinary->getOp();
112    if (op == EOpInitialize || intermBinary->isAssignment())
113        visitAssignment(intermBinary);
114    else if (op == EOpLogicalAnd || op == EOpLogicalOr)
115        visitLogicalOp(intermBinary);
116    else
117        visitBinaryChildren(intermBinary);
118
119    return false;
120}
121
122void TDependencyGraphBuilder::visitAssignment(TIntermBinary *intermAssignment)
123{
124    TIntermTyped *intermLeft = intermAssignment->getLeft();
125    if (!intermLeft)
126        return;
127
128    TGraphSymbol *leftmostSymbol = NULL;
129
130    {
131        TNodeSetMaintainer nodeSetMaintainer(this);
132
133        {
134            TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mLeftSubtree);
135            intermLeft->traverse(this);
136            leftmostSymbol = mLeftmostSymbols.top();
137
138            // After traversing the left subtree of this assignment, we should
139            // have found a real leftmost symbol, and the leftmost symbol should
140            // not be a placeholder.
141            ASSERT(leftmostSymbol != &mLeftSubtree);
142            ASSERT(leftmostSymbol != &mRightSubtree);
143        }
144
145        if (TIntermTyped *intermRight = intermAssignment->getRight())
146        {
147            TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
148            intermRight->traverse(this);
149        }
150
151        if (TParentNodeSet *assignmentNodes = mNodeSets.getTopSet())
152            connectMultipleNodesToSingleNode(assignmentNodes, leftmostSymbol);
153    }
154
155    // Push the leftmost symbol of this assignment into the current set of dependent
156    // symbols to represent the result of this assignment.
157    // An expression like "a = (b = c)" will yield a dependency graph like
158    // "c -> b -> a".
159    // This line essentially passes the leftmost symbol of the nested assignment
160    // ("b" in this example) back up to the earlier visitAssignment call for the
161    // outer assignment, which will create the connection "b -> a".
162    mNodeSets.insertIntoTopSet(leftmostSymbol);
163}
164
165void TDependencyGraphBuilder::visitLogicalOp(TIntermBinary *intermLogicalOp)
166{
167    if (TIntermTyped *intermLeft = intermLogicalOp->getLeft())
168    {
169        TNodeSetPropagatingMaintainer nodeSetMaintainer(this);
170
171        intermLeft->traverse(this);
172        if (TParentNodeSet *leftNodes = mNodeSets.getTopSet())
173        {
174            TGraphLogicalOp *logicalOp = mGraph->createLogicalOp(intermLogicalOp);
175            connectMultipleNodesToSingleNode(leftNodes, logicalOp);
176        }
177    }
178
179    if (TIntermTyped *intermRight = intermLogicalOp->getRight())
180    {
181        TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
182        intermRight->traverse(this);
183    }
184}
185
186void TDependencyGraphBuilder::visitBinaryChildren(TIntermBinary *intermBinary)
187{
188    if (TIntermTyped *intermLeft = intermBinary->getLeft())
189        intermLeft->traverse(this);
190
191    if (TIntermTyped *intermRight = intermBinary->getRight())
192    {
193        TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
194        intermRight->traverse(this);
195    }
196}
197
198bool TDependencyGraphBuilder::visitSelection(
199    Visit visit, TIntermSelection *intermSelection)
200{
201    if (TIntermNode *intermCondition = intermSelection->getCondition())
202    {
203        TNodeSetMaintainer nodeSetMaintainer(this);
204
205        intermCondition->traverse(this);
206        if (TParentNodeSet *conditionNodes = mNodeSets.getTopSet())
207        {
208            TGraphSelection *selection = mGraph->createSelection(intermSelection);
209            connectMultipleNodesToSingleNode(conditionNodes, selection);
210        }
211    }
212
213    if (TIntermNode *intermTrueBlock = intermSelection->getTrueBlock())
214        intermTrueBlock->traverse(this);
215
216    if (TIntermNode *intermFalseBlock = intermSelection->getFalseBlock())
217        intermFalseBlock->traverse(this);
218
219    return false;
220}
221
222bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop *intermLoop)
223{
224    if (TIntermTyped *intermCondition = intermLoop->getCondition())
225    {
226        TNodeSetMaintainer nodeSetMaintainer(this);
227
228        intermCondition->traverse(this);
229        if (TParentNodeSet *conditionNodes = mNodeSets.getTopSet())
230        {
231            TGraphLoop *loop = mGraph->createLoop(intermLoop);
232            connectMultipleNodesToSingleNode(conditionNodes, loop);
233        }
234    }
235
236    if (TIntermNode* intermBody = intermLoop->getBody())
237        intermBody->traverse(this);
238
239    if (TIntermTyped *intermExpression = intermLoop->getExpression())
240        intermExpression->traverse(this);
241
242    return false;
243}
244
245
246void TDependencyGraphBuilder::connectMultipleNodesToSingleNode(
247    TParentNodeSet *nodes, TGraphNode *node) const
248{
249    for (TParentNodeSet::const_iterator iter = nodes->begin();
250         iter != nodes->end(); ++iter)
251    {
252        TGraphParentNode *currentNode = *iter;
253        currentNode->addDependentNode(node);
254    }
255}
256