Add the SH_TIMING_RESTRICTIONS compile flag and dependency graph implementation.
Description of the algorithm:
http://code.google.com/p/mvujovic/wiki/ShaderControlFlowAnalysis
This flag is one potential solution to timing attacks on textures containing cross-domain content
or user agent data.
This kind of analysis could be useful for both WebGL and CSS Shaders.
The SH_TIMING_RESTRICTIONS flag will reject a shader if it uses texture dependent data to affect
control flow.
Other ways of affecting shader timing such as using NaNs in basic arithmetic operations or using
built-in functions (e.g. atan) with different inputs are still under investigation.
Issue=329
Review URL: http://codereview.appspot.com/6195062/
git-svn-id: https://angleproject.googlecode.com/svn/trunk@1101 736b8ea6-26fd-11df-bfd4-992fa37f6226
diff --git a/src/compiler/depgraph/DependencyGraphBuilder.cpp b/src/compiler/depgraph/DependencyGraphBuilder.cpp
new file mode 100644
index 0000000..8e45c37
--- /dev/null
+++ b/src/compiler/depgraph/DependencyGraphBuilder.cpp
@@ -0,0 +1,241 @@
+//
+// 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.
+//
+
+#include "compiler/depgraph/DependencyGraphBuilder.h"
+
+TDependencyGraphBuilder::TLeftmostSymbolMaintainer::TSubtreePlaceholder
+ TDependencyGraphBuilder::TLeftmostSymbolMaintainer::kLeftSubtree;
+
+TDependencyGraphBuilder::TLeftmostSymbolMaintainer::TSubtreePlaceholder
+ TDependencyGraphBuilder::TLeftmostSymbolMaintainer::kRightSubtree;
+
+void TDependencyGraphBuilder::build(TIntermNode* node, TDependencyGraph* graph)
+{
+ TDependencyGraphBuilder builder(graph);
+ builder.build(node);
+}
+
+bool TDependencyGraphBuilder::visitAggregate(Visit visit, TIntermAggregate* intermAggregate)
+{
+ switch (intermAggregate->getOp()) {
+ case EOpFunction: visitFunctionDefinition(intermAggregate); break;
+ case EOpFunctionCall: visitFunctionCall(intermAggregate); break;
+ default: visitAggregateChildren(intermAggregate); break;
+ }
+
+ return false;
+}
+
+void TDependencyGraphBuilder::visitFunctionDefinition(TIntermAggregate* intermAggregate)
+{
+ // Function defintions should only exist in the global scope.
+ ASSERT(mIsGlobalScope);
+
+ // Currently, we do not support user defined functions.
+ if (intermAggregate->getName() != "main(")
+ return;
+
+ mIsGlobalScope = false;
+
+ visitAggregateChildren(intermAggregate);
+
+ mIsGlobalScope = true;
+}
+
+// Takes an expression like "f(x)" and creates a dependency graph like
+// "x -> argument 0 -> function call".
+void TDependencyGraphBuilder::visitFunctionCall(TIntermAggregate* intermFunctionCall)
+{
+ TGraphFunctionCall* functionCall = mGraph->createFunctionCall(intermFunctionCall);
+
+ // Run through the function call arguments.
+ int argumentNumber = 0;
+ TIntermSequence& intermArguments = intermFunctionCall->getSequence();
+ for (TIntermSequence::const_iterator iter = intermArguments.begin();
+ iter != intermArguments.end();
+ ++iter, ++argumentNumber)
+ {
+ TNodeSetMaintainer nodeSetMaintainer(this);
+
+ TIntermNode* intermArgument = *iter;
+ intermArgument->traverse(this);
+
+ if (TParentNodeSet* argumentNodes = mNodeSets.getTopSet()) {
+ TGraphArgument* argument = mGraph->createArgument(intermFunctionCall, argumentNumber);
+ connectMultipleNodesToSingleNode(argumentNodes, argument);
+ argument->addDependentNode(functionCall);
+ }
+ }
+
+ // Push the leftmost symbol of this function call into the current set of dependent symbols to
+ // represent the result of this function call.
+ // Thus, an expression like "y = f(x)" will yield a dependency graph like
+ // "x -> argument 0 -> function call -> y".
+ // This line essentially passes the function call node back up to an earlier visitAssignment
+ // call, which will create the connection "function call -> y".
+ mNodeSets.insertIntoTopSet(functionCall);
+}
+
+void TDependencyGraphBuilder::visitAggregateChildren(TIntermAggregate* intermAggregate)
+{
+ TIntermSequence& sequence = intermAggregate->getSequence();
+ for(TIntermSequence::const_iterator iter = sequence.begin(); iter != sequence.end(); ++iter)
+ {
+ TIntermNode* intermChild = *iter;
+ intermChild->traverse(this);
+ }
+}
+
+void TDependencyGraphBuilder::visitSymbol(TIntermSymbol* intermSymbol)
+{
+ // Push this symbol into the set of dependent symbols for the current assignment or condition
+ // that we are traversing.
+ TGraphSymbol* symbol = mGraph->getOrCreateSymbol(intermSymbol, mIsGlobalScope);
+ mNodeSets.insertIntoTopSet(symbol);
+
+ // If this symbol is the current leftmost symbol under an assignment, replace the previous
+ // leftmost symbol with this symbol.
+ if (!mLeftmostSymbols.empty() && mLeftmostSymbols.top() !=
+ &TLeftmostSymbolMaintainer::kRightSubtree) {
+ mLeftmostSymbols.pop();
+ mLeftmostSymbols.push(symbol);
+ }
+}
+
+bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary* intermBinary)
+{
+ TOperator op = intermBinary->getOp();
+ if (op == EOpInitialize || intermBinary->modifiesState())
+ visitAssignment(intermBinary);
+ else if (op == EOpLogicalAnd || op == EOpLogicalOr)
+ visitLogicalOp(intermBinary);
+ else
+ visitBinaryChildren(intermBinary);
+
+ return false;
+}
+
+void TDependencyGraphBuilder::visitAssignment(TIntermBinary* intermAssignment)
+{
+ TIntermTyped* intermLeft = intermAssignment->getLeft();
+ if (!intermLeft)
+ return;
+
+ TGraphSymbol* leftmostSymbol = NULL;
+
+ {
+ TNodeSetMaintainer nodeSetMaintainer(this);
+
+ {
+ TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, TLeftmostSymbolMaintainer::kLeftSubtree);
+ intermLeft->traverse(this);
+ leftmostSymbol = mLeftmostSymbols.top();
+
+ // After traversing the left subtree of this assignment, we should have found a real
+ // leftmost symbol, and the leftmost symbol should not be a placeholder.
+ ASSERT(leftmostSymbol != &TLeftmostSymbolMaintainer::kLeftSubtree);
+ ASSERT(leftmostSymbol != &TLeftmostSymbolMaintainer::kRightSubtree);
+ }
+
+ if (TIntermTyped* intermRight = intermAssignment->getRight()) {
+ TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, TLeftmostSymbolMaintainer::kRightSubtree);
+ intermRight->traverse(this);
+ }
+
+ if (TParentNodeSet* assignmentNodes = mNodeSets.getTopSet())
+ connectMultipleNodesToSingleNode(assignmentNodes, leftmostSymbol);
+ }
+
+ // Push the leftmost symbol of this assignment into the current set of dependent symbols to
+ // represent the result of this assignment.
+ // An expression like "a = (b = c)" will yield a dependency graph like "c -> b -> a".
+ // This line essentially passes the leftmost symbol of the nested assignment ("b" in this
+ // example) back up to the earlier visitAssignment call for the outer assignment, which will
+ // create the connection "b -> a".
+ mNodeSets.insertIntoTopSet(leftmostSymbol);
+}
+
+void TDependencyGraphBuilder::visitLogicalOp(TIntermBinary* intermLogicalOp)
+{
+ if (TIntermTyped* intermLeft = intermLogicalOp->getLeft()) {
+ TNodeSetPropagatingMaintainer nodeSetMaintainer(this);
+
+ intermLeft->traverse(this);
+ if (TParentNodeSet* leftNodes = mNodeSets.getTopSet()) {
+ TGraphLogicalOp* logicalOp = mGraph->createLogicalOp(intermLogicalOp);
+ connectMultipleNodesToSingleNode(leftNodes, logicalOp);
+ }
+ }
+
+ if (TIntermTyped* intermRight = intermLogicalOp->getRight()) {
+ TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, TLeftmostSymbolMaintainer::kRightSubtree);
+ intermRight->traverse(this);
+ }
+}
+
+void TDependencyGraphBuilder::visitBinaryChildren(TIntermBinary* intermBinary)
+{
+ if (TIntermTyped* intermLeft = intermBinary->getLeft())
+ intermLeft->traverse(this);
+
+ if (TIntermTyped* intermRight = intermBinary->getRight()) {
+ TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, TLeftmostSymbolMaintainer::kRightSubtree);
+ intermRight->traverse(this);
+ }
+}
+
+bool TDependencyGraphBuilder::visitSelection(Visit visit, TIntermSelection* intermSelection)
+{
+ if (TIntermNode* intermCondition = intermSelection->getCondition()) {
+ TNodeSetMaintainer nodeSetMaintainer(this);
+
+ intermCondition->traverse(this);
+ if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
+ TGraphSelection* selection = mGraph->createSelection(intermSelection);
+ connectMultipleNodesToSingleNode(conditionNodes, selection);
+ }
+ }
+
+ if (TIntermNode* intermTrueBlock = intermSelection->getTrueBlock())
+ intermTrueBlock->traverse(this);
+
+ if (TIntermNode* intermFalseBlock = intermSelection->getFalseBlock())
+ intermFalseBlock->traverse(this);
+
+ return false;
+}
+
+bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop* intermLoop)
+{
+ if (TIntermTyped* intermCondition = intermLoop->getCondition()) {
+ TNodeSetMaintainer nodeSetMaintainer(this);
+
+ intermCondition->traverse(this);
+ if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
+ TGraphLoop* loop = mGraph->createLoop(intermLoop);
+ connectMultipleNodesToSingleNode(conditionNodes, loop);
+ }
+ }
+
+ if (TIntermNode* intermBody = intermLoop->getBody())
+ intermBody->traverse(this);
+
+ if (TIntermTyped* intermExpression = intermLoop->getExpression())
+ intermExpression->traverse(this);
+
+ return false;
+}
+
+
+void TDependencyGraphBuilder::connectMultipleNodesToSingleNode(TParentNodeSet* nodes,
+ TGraphNode* node) const
+{
+ for (TParentNodeSet::const_iterator iter = nodes->begin(); iter != nodes->end(); ++iter)
+ {
+ TGraphParentNode* currentNode = *iter;
+ currentNode->addDependentNode(node);
+ }
+}