Use a heap-memory traversal to free compiler resources.
The stack-memory traversal is prone to stack overflow. See the
WebGL conformance test long-expressions-should-not-crash.
BUG=angle:584
Change-Id: I02d72bc2e4101b7141d609c50303403ea8298e60
Reviewed-on: https://chromium-review.googlesource.com/191930
Reviewed-by: Zhenyao Mo <zmo@chromium.org>
Reviewed-by: Nicolas Capens <nicolascapens@chromium.org>
Tested-by: Jamie Madill <jmadill@chromium.org>
diff --git a/src/compiler/translator/Intermediate.cpp b/src/compiler/translator/Intermediate.cpp
index 74b9a6e..9df2afc 100644
--- a/src/compiler/translator/Intermediate.cpp
+++ b/src/compiler/translator/Intermediate.cpp
@@ -786,6 +786,26 @@
return false;
}
+void TIntermLoop::enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const
+{
+ if (init)
+ {
+ nodeQueue->push(init);
+ }
+ if (cond)
+ {
+ nodeQueue->push(cond);
+ }
+ if (expr)
+ {
+ nodeQueue->push(expr);
+ }
+ if (body)
+ {
+ nodeQueue->push(body);
+ }
+}
+
bool TIntermBranch::replaceChildNode(
TIntermNode *original, TIntermNode *replacement)
{
@@ -793,6 +813,14 @@
return false;
}
+void TIntermBranch::enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const
+{
+ if (expression)
+ {
+ nodeQueue->push(expression);
+ }
+}
+
bool TIntermBinary::replaceChildNode(
TIntermNode *original, TIntermNode *replacement)
{
@@ -801,6 +829,18 @@
return false;
}
+void TIntermBinary::enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const
+{
+ if (left)
+ {
+ nodeQueue->push(left);
+ }
+ if (right)
+ {
+ nodeQueue->push(right);
+ }
+}
+
bool TIntermUnary::replaceChildNode(
TIntermNode *original, TIntermNode *replacement)
{
@@ -808,6 +848,14 @@
return false;
}
+void TIntermUnary::enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const
+{
+ if (operand)
+ {
+ nodeQueue->push(operand);
+ }
+}
+
bool TIntermAggregate::replaceChildNode(
TIntermNode *original, TIntermNode *replacement)
{
@@ -818,6 +866,14 @@
return false;
}
+void TIntermAggregate::enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const
+{
+ for (size_t childIndex = 0; childIndex < sequence.size(); childIndex++)
+ {
+ nodeQueue->push(sequence[childIndex]);
+ }
+}
+
bool TIntermSelection::replaceChildNode(
TIntermNode *original, TIntermNode *replacement)
{
@@ -827,6 +883,22 @@
return false;
}
+void TIntermSelection::enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const
+{
+ if (condition)
+ {
+ nodeQueue->push(condition);
+ }
+ if (trueBlock)
+ {
+ nodeQueue->push(trueBlock);
+ }
+ if (falseBlock)
+ {
+ nodeQueue->push(falseBlock);
+ }
+}
+
//
// Say whether or not an operation node changes the value of a variable.
//
diff --git a/src/compiler/translator/RemoveTree.cpp b/src/compiler/translator/RemoveTree.cpp
index 92e5dbb..e381c32 100644
--- a/src/compiler/translator/RemoveTree.cpp
+++ b/src/compiler/translator/RemoveTree.cpp
@@ -8,70 +8,22 @@
#include "compiler/translator/RemoveTree.h"
//
-// Code to recursively delete the intermediate tree.
-//
-
-class RemoveTree : public TIntermTraverser
-{
-public:
- RemoveTree() : TIntermTraverser(false, false, true)
- {
- }
-
-protected:
- void visitSymbol(TIntermSymbol*);
- void visitConstantUnion(TIntermConstantUnion*);
- bool visitBinary(Visit visit, TIntermBinary*);
- bool visitUnary(Visit visit, TIntermUnary*);
- bool visitSelection(Visit visit, TIntermSelection*);
- bool visitAggregate(Visit visit, TIntermAggregate*);
-};
-
-void RemoveTree::visitSymbol(TIntermSymbol* node)
-{
- delete node;
-}
-
-bool RemoveTree::visitBinary(Visit visit, TIntermBinary* node)
-{
- delete node;
-
- return true;
-}
-
-bool RemoveTree::visitUnary(Visit visit, TIntermUnary* node)
-{
- delete node;
-
- return true;
-}
-
-bool RemoveTree::visitAggregate(Visit visit, TIntermAggregate* node)
-{
- delete node;
-
- return true;
-}
-
-bool RemoveTree::visitSelection(Visit visit, TIntermSelection* node)
-{
- delete node;
-
- return true;
-}
-
-void RemoveTree::visitConstantUnion(TIntermConstantUnion* node)
-{
- delete node;
-}
-
-//
-// Entry point.
+// Code to delete the intermediate tree.
//
void RemoveAllTreeNodes(TIntermNode* root)
{
- RemoveTree it;
+ std::queue<TIntermNode*> nodeQueue;
- root->traverse(&it);
+ nodeQueue.push(root);
+
+ while (!nodeQueue.empty())
+ {
+ TIntermNode *node = nodeQueue.front();
+ nodeQueue.pop();
+
+ node->enqueueChildren(&nodeQueue);
+
+ delete node;
+ }
}
diff --git a/src/compiler/translator/intermediate.h b/src/compiler/translator/intermediate.h
index db3481c..b09fc9e 100644
--- a/src/compiler/translator/intermediate.h
+++ b/src/compiler/translator/intermediate.h
@@ -19,6 +19,7 @@
#include "GLSLANG/ShaderLang.h"
#include <algorithm>
+#include <queue>
#include "compiler/translator/Common.h"
#include "compiler/translator/Types.h"
#include "compiler/translator/ConstantUnion.h"
@@ -243,6 +244,10 @@
virtual bool replaceChildNode(
TIntermNode *original, TIntermNode *replacement) = 0;
+ // For traversing a tree in no particular order, but using
+ // heap memory.
+ virtual void enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const = 0;
+
protected:
TSourceLoc line;
};
@@ -328,6 +333,8 @@
void setUnrollFlag(bool flag) { unrollFlag = flag; }
bool getUnrollFlag() { return unrollFlag; }
+ virtual void enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const;
+
protected:
TLoopType type;
TIntermNode* init; // for-loop initialization
@@ -354,6 +361,8 @@
TOperator getFlowOp() { return flowOp; }
TIntermTyped* getExpression() { return expression; }
+ virtual void enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const;
+
protected:
TOperator flowOp;
TIntermTyped* expression; // non-zero except for "return exp;" statements
@@ -381,6 +390,8 @@
virtual TIntermSymbol* getAsSymbolNode() { return this; }
virtual bool replaceChildNode(TIntermNode *, TIntermNode *) { return false; }
+ virtual void enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const {}
+
protected:
int id;
TString symbol;
@@ -405,6 +416,8 @@
TIntermTyped* fold(TOperator, TIntermTyped*, TInfoSink&);
+ virtual void enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const {}
+
protected:
ConstantUnion *unionArrayPointer;
};
@@ -451,6 +464,8 @@
void setAddIndexClamp() { addIndexClamp = true; }
bool getAddIndexClamp() { return addIndexClamp; }
+ virtual void enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const;
+
protected:
TIntermTyped* left;
TIntermTyped* right;
@@ -481,6 +496,8 @@
void setUseEmulatedFunction() { useEmulatedFunction = true; }
bool getUseEmulatedFunction() { return useEmulatedFunction; }
+ virtual void enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const;
+
protected:
TIntermTyped* operand;
@@ -525,6 +542,8 @@
void setUseEmulatedFunction() { useEmulatedFunction = true; }
bool getUseEmulatedFunction() { return useEmulatedFunction; }
+ virtual void enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const;
+
protected:
TIntermAggregate(const TIntermAggregate&); // disallow copy constructor
TIntermAggregate& operator=(const TIntermAggregate&); // disallow assignment operator
@@ -563,6 +582,8 @@
TIntermNode* getFalseBlock() const { return falseBlock; }
TIntermSelection* getAsSelectionNode() { return this; }
+ virtual void enqueueChildren(std::queue<TIntermNode*> *nodeQueue) const;
+
protected:
TIntermTyped* condition;
TIntermNode* trueBlock;