1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/angle/src/compiler/depgraph/DependencyGraphBuilder.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,227 @@
1.4 +//
1.5 +// Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.
1.6 +// Use of this source code is governed by a BSD-style license that can be
1.7 +// found in the LICENSE file.
1.8 +//
1.9 +
1.10 +#include "compiler/depgraph/DependencyGraphBuilder.h"
1.11 +
1.12 +void TDependencyGraphBuilder::build(TIntermNode* node, TDependencyGraph* graph)
1.13 +{
1.14 + TDependencyGraphBuilder builder(graph);
1.15 + builder.build(node);
1.16 +}
1.17 +
1.18 +bool TDependencyGraphBuilder::visitAggregate(Visit visit, TIntermAggregate* intermAggregate)
1.19 +{
1.20 + switch (intermAggregate->getOp()) {
1.21 + case EOpFunction: visitFunctionDefinition(intermAggregate); break;
1.22 + case EOpFunctionCall: visitFunctionCall(intermAggregate); break;
1.23 + default: visitAggregateChildren(intermAggregate); break;
1.24 + }
1.25 +
1.26 + return false;
1.27 +}
1.28 +
1.29 +void TDependencyGraphBuilder::visitFunctionDefinition(TIntermAggregate* intermAggregate)
1.30 +{
1.31 + // Currently, we do not support user defined functions.
1.32 + if (intermAggregate->getName() != "main(")
1.33 + return;
1.34 +
1.35 + visitAggregateChildren(intermAggregate);
1.36 +}
1.37 +
1.38 +// Takes an expression like "f(x)" and creates a dependency graph like
1.39 +// "x -> argument 0 -> function call".
1.40 +void TDependencyGraphBuilder::visitFunctionCall(TIntermAggregate* intermFunctionCall)
1.41 +{
1.42 + TGraphFunctionCall* functionCall = mGraph->createFunctionCall(intermFunctionCall);
1.43 +
1.44 + // Run through the function call arguments.
1.45 + int argumentNumber = 0;
1.46 + TIntermSequence& intermArguments = intermFunctionCall->getSequence();
1.47 + for (TIntermSequence::const_iterator iter = intermArguments.begin();
1.48 + iter != intermArguments.end();
1.49 + ++iter, ++argumentNumber)
1.50 + {
1.51 + TNodeSetMaintainer nodeSetMaintainer(this);
1.52 +
1.53 + TIntermNode* intermArgument = *iter;
1.54 + intermArgument->traverse(this);
1.55 +
1.56 + if (TParentNodeSet* argumentNodes = mNodeSets.getTopSet()) {
1.57 + TGraphArgument* argument = mGraph->createArgument(intermFunctionCall, argumentNumber);
1.58 + connectMultipleNodesToSingleNode(argumentNodes, argument);
1.59 + argument->addDependentNode(functionCall);
1.60 + }
1.61 + }
1.62 +
1.63 + // Push the leftmost symbol of this function call into the current set of dependent symbols to
1.64 + // represent the result of this function call.
1.65 + // Thus, an expression like "y = f(x)" will yield a dependency graph like
1.66 + // "x -> argument 0 -> function call -> y".
1.67 + // This line essentially passes the function call node back up to an earlier visitAssignment
1.68 + // call, which will create the connection "function call -> y".
1.69 + mNodeSets.insertIntoTopSet(functionCall);
1.70 +}
1.71 +
1.72 +void TDependencyGraphBuilder::visitAggregateChildren(TIntermAggregate* intermAggregate)
1.73 +{
1.74 + TIntermSequence& sequence = intermAggregate->getSequence();
1.75 + for(TIntermSequence::const_iterator iter = sequence.begin(); iter != sequence.end(); ++iter)
1.76 + {
1.77 + TIntermNode* intermChild = *iter;
1.78 + intermChild->traverse(this);
1.79 + }
1.80 +}
1.81 +
1.82 +void TDependencyGraphBuilder::visitSymbol(TIntermSymbol* intermSymbol)
1.83 +{
1.84 + // Push this symbol into the set of dependent symbols for the current assignment or condition
1.85 + // that we are traversing.
1.86 + TGraphSymbol* symbol = mGraph->getOrCreateSymbol(intermSymbol);
1.87 + mNodeSets.insertIntoTopSet(symbol);
1.88 +
1.89 + // If this symbol is the current leftmost symbol under an assignment, replace the previous
1.90 + // leftmost symbol with this symbol.
1.91 + if (!mLeftmostSymbols.empty() && mLeftmostSymbols.top() != &mRightSubtree) {
1.92 + mLeftmostSymbols.pop();
1.93 + mLeftmostSymbols.push(symbol);
1.94 + }
1.95 +}
1.96 +
1.97 +bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary* intermBinary)
1.98 +{
1.99 + TOperator op = intermBinary->getOp();
1.100 + if (op == EOpInitialize || intermBinary->modifiesState())
1.101 + visitAssignment(intermBinary);
1.102 + else if (op == EOpLogicalAnd || op == EOpLogicalOr)
1.103 + visitLogicalOp(intermBinary);
1.104 + else
1.105 + visitBinaryChildren(intermBinary);
1.106 +
1.107 + return false;
1.108 +}
1.109 +
1.110 +void TDependencyGraphBuilder::visitAssignment(TIntermBinary* intermAssignment)
1.111 +{
1.112 + TIntermTyped* intermLeft = intermAssignment->getLeft();
1.113 + if (!intermLeft)
1.114 + return;
1.115 +
1.116 + TGraphSymbol* leftmostSymbol = NULL;
1.117 +
1.118 + {
1.119 + TNodeSetMaintainer nodeSetMaintainer(this);
1.120 +
1.121 + {
1.122 + TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mLeftSubtree);
1.123 + intermLeft->traverse(this);
1.124 + leftmostSymbol = mLeftmostSymbols.top();
1.125 +
1.126 + // After traversing the left subtree of this assignment, we should have found a real
1.127 + // leftmost symbol, and the leftmost symbol should not be a placeholder.
1.128 + ASSERT(leftmostSymbol != &mLeftSubtree);
1.129 + ASSERT(leftmostSymbol != &mRightSubtree);
1.130 + }
1.131 +
1.132 + if (TIntermTyped* intermRight = intermAssignment->getRight()) {
1.133 + TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
1.134 + intermRight->traverse(this);
1.135 + }
1.136 +
1.137 + if (TParentNodeSet* assignmentNodes = mNodeSets.getTopSet())
1.138 + connectMultipleNodesToSingleNode(assignmentNodes, leftmostSymbol);
1.139 + }
1.140 +
1.141 + // Push the leftmost symbol of this assignment into the current set of dependent symbols to
1.142 + // represent the result of this assignment.
1.143 + // An expression like "a = (b = c)" will yield a dependency graph like "c -> b -> a".
1.144 + // This line essentially passes the leftmost symbol of the nested assignment ("b" in this
1.145 + // example) back up to the earlier visitAssignment call for the outer assignment, which will
1.146 + // create the connection "b -> a".
1.147 + mNodeSets.insertIntoTopSet(leftmostSymbol);
1.148 +}
1.149 +
1.150 +void TDependencyGraphBuilder::visitLogicalOp(TIntermBinary* intermLogicalOp)
1.151 +{
1.152 + if (TIntermTyped* intermLeft = intermLogicalOp->getLeft()) {
1.153 + TNodeSetPropagatingMaintainer nodeSetMaintainer(this);
1.154 +
1.155 + intermLeft->traverse(this);
1.156 + if (TParentNodeSet* leftNodes = mNodeSets.getTopSet()) {
1.157 + TGraphLogicalOp* logicalOp = mGraph->createLogicalOp(intermLogicalOp);
1.158 + connectMultipleNodesToSingleNode(leftNodes, logicalOp);
1.159 + }
1.160 + }
1.161 +
1.162 + if (TIntermTyped* intermRight = intermLogicalOp->getRight()) {
1.163 + TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
1.164 + intermRight->traverse(this);
1.165 + }
1.166 +}
1.167 +
1.168 +void TDependencyGraphBuilder::visitBinaryChildren(TIntermBinary* intermBinary)
1.169 +{
1.170 + if (TIntermTyped* intermLeft = intermBinary->getLeft())
1.171 + intermLeft->traverse(this);
1.172 +
1.173 + if (TIntermTyped* intermRight = intermBinary->getRight()) {
1.174 + TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
1.175 + intermRight->traverse(this);
1.176 + }
1.177 +}
1.178 +
1.179 +bool TDependencyGraphBuilder::visitSelection(Visit visit, TIntermSelection* intermSelection)
1.180 +{
1.181 + if (TIntermNode* intermCondition = intermSelection->getCondition()) {
1.182 + TNodeSetMaintainer nodeSetMaintainer(this);
1.183 +
1.184 + intermCondition->traverse(this);
1.185 + if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
1.186 + TGraphSelection* selection = mGraph->createSelection(intermSelection);
1.187 + connectMultipleNodesToSingleNode(conditionNodes, selection);
1.188 + }
1.189 + }
1.190 +
1.191 + if (TIntermNode* intermTrueBlock = intermSelection->getTrueBlock())
1.192 + intermTrueBlock->traverse(this);
1.193 +
1.194 + if (TIntermNode* intermFalseBlock = intermSelection->getFalseBlock())
1.195 + intermFalseBlock->traverse(this);
1.196 +
1.197 + return false;
1.198 +}
1.199 +
1.200 +bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop* intermLoop)
1.201 +{
1.202 + if (TIntermTyped* intermCondition = intermLoop->getCondition()) {
1.203 + TNodeSetMaintainer nodeSetMaintainer(this);
1.204 +
1.205 + intermCondition->traverse(this);
1.206 + if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
1.207 + TGraphLoop* loop = mGraph->createLoop(intermLoop);
1.208 + connectMultipleNodesToSingleNode(conditionNodes, loop);
1.209 + }
1.210 + }
1.211 +
1.212 + if (TIntermNode* intermBody = intermLoop->getBody())
1.213 + intermBody->traverse(this);
1.214 +
1.215 + if (TIntermTyped* intermExpression = intermLoop->getExpression())
1.216 + intermExpression->traverse(this);
1.217 +
1.218 + return false;
1.219 +}
1.220 +
1.221 +
1.222 +void TDependencyGraphBuilder::connectMultipleNodesToSingleNode(TParentNodeSet* nodes,
1.223 + TGraphNode* node) const
1.224 +{
1.225 + for (TParentNodeSet::const_iterator iter = nodes->begin(); iter != nodes->end(); ++iter)
1.226 + {
1.227 + TGraphParentNode* currentNode = *iter;
1.228 + currentNode->addDependentNode(node);
1.229 + }
1.230 +}
