Handle multiple AST insertions to the same parent in updateTree()
Multiple insertions to the same parent can be handled as long as the
insertions don't have the same position as well. They're sorted in
reverse order so that insertions to greater indices get processed
first.
This helps to make some AST transformations faster - they don't need
multiple tree traversals and updateTree() steps anymore. The
SimplifyLoopConditions AST transformation is changed to only use a
single traversal.
BUG=angleproject:1966
TEST=angle_unittests, angle_end2end_tests,
WebGL conformance tests,
dEQP-GLES2.functional.shaders.*select_iteration_count*
Change-Id: I3183f2644ad58b282926093c77b204fb7e4e9b71
Reviewed-on: https://chromium-review.googlesource.com/506202
Reviewed-by: Jamie Madill <jmadill@chromium.org>
Reviewed-by: Corentin Wallez <cwallez@chromium.org>
Commit-Queue: Olli Etuaho <oetuaho@nvidia.com>
diff --git a/src/compiler/translator/SimplifyLoopConditions.cpp b/src/compiler/translator/SimplifyLoopConditions.cpp
index a2ed7f3..2e40a76 100644
--- a/src/compiler/translator/SimplifyLoopConditions.cpp
+++ b/src/compiler/translator/SimplifyLoopConditions.cpp
@@ -42,12 +42,11 @@
bool visitTernary(Visit visit, TIntermTernary *node) override;
bool visitDeclaration(Visit visit, TIntermDeclaration *node) override;
- void nextIteration();
bool foundLoopToChange() const { return mFoundLoopToChange; }
protected:
- // Marked to true once an operation that needs to be hoisted out of the expression has been
- // found. After that, no more AST updates are performed on that traversal.
+ // Marked to true once an operation that needs to be hoisted out of a loop expression has been
+ // found.
bool mFoundLoopToChange;
bool mInsideLoopInitConditionOrExpression;
IntermNodePatternMatcher mConditionsToSimplify;
@@ -64,81 +63,69 @@
{
}
-void SimplifyLoopConditionsTraverser::nextIteration()
-{
- mFoundLoopToChange = false;
- mInsideLoopInitConditionOrExpression = false;
- nextTemporaryIndex();
-}
+// If we're inside a loop initialization, condition, or expression, we check for expressions that
+// should be moved out of the loop condition or expression. If one is found, the loop is
+// transformed.
+// If we're not inside loop initialization, condition, or expression, we only need to traverse nodes
+// that may contain loops.
-// The visit functions operate in three modes:
-// 1. If a matching expression has already been found, we return early since only one loop can
-// be transformed on one traversal.
-// 2. We try to find loops. In case a node is not inside a loop and can not contain loops, we
-// stop traversing the subtree.
-// 3. If we're inside a loop initialization, condition or expression, we check for expressions
-// that should be moved out of the loop condition or expression. If one is found, the loop
-// is processed.
bool SimplifyLoopConditionsTraverser::visitBinary(Visit visit, TIntermBinary *node)
{
-
- if (mFoundLoopToChange)
- return false;
-
if (!mInsideLoopInitConditionOrExpression)
return false;
+ if (mFoundLoopToChange)
+ return false; // Already decided to change this loop.
+
mFoundLoopToChange = mConditionsToSimplify.match(node, getParentNode(), isLValueRequiredHere());
return !mFoundLoopToChange;
}
bool SimplifyLoopConditionsTraverser::visitAggregate(Visit visit, TIntermAggregate *node)
{
- if (mFoundLoopToChange)
- return false;
-
if (!mInsideLoopInitConditionOrExpression)
return false;
+ if (mFoundLoopToChange)
+ return false; // Already decided to change this loop.
+
mFoundLoopToChange = mConditionsToSimplify.match(node, getParentNode());
return !mFoundLoopToChange;
}
bool SimplifyLoopConditionsTraverser::visitTernary(Visit visit, TIntermTernary *node)
{
- if (mFoundLoopToChange)
- return false;
-
if (!mInsideLoopInitConditionOrExpression)
return false;
+ if (mFoundLoopToChange)
+ return false; // Already decided to change this loop.
+
mFoundLoopToChange = mConditionsToSimplify.match(node);
return !mFoundLoopToChange;
}
bool SimplifyLoopConditionsTraverser::visitDeclaration(Visit visit, TIntermDeclaration *node)
{
- if (mFoundLoopToChange)
- return false;
-
if (!mInsideLoopInitConditionOrExpression)
return false;
+ if (mFoundLoopToChange)
+ return false; // Already decided to change this loop.
+
mFoundLoopToChange = mConditionsToSimplify.match(node);
return !mFoundLoopToChange;
}
void SimplifyLoopConditionsTraverser::traverseLoop(TIntermLoop *node)
{
- if (mFoundLoopToChange)
- return;
-
- // Mark that we're inside a loop condition or expression, and transform the loop if needed.
+ // Mark that we're inside a loop condition or expression, and determine if the loop needs to be
+ // transformed.
ScopedNodeInTraversalPath addToPath(this, node);
mInsideLoopInitConditionOrExpression = true;
- TLoopType loopType = node->getType();
+ mFoundLoopToChange = false;
if (!mFoundLoopToChange && node->getInit())
{
@@ -155,9 +142,14 @@
node->getExpression()->traverse(this);
}
+ mInsideLoopInitConditionOrExpression = false;
+
if (mFoundLoopToChange)
{
+ nextTemporaryIndex();
+
// Replace the loop condition with a boolean variable that's updated on each iteration.
+ TLoopType loopType = node->getType();
if (loopType == ELoopWhile)
{
// Transform:
@@ -178,8 +170,8 @@
createTempAssignment(node->getCondition()->deepCopy()));
// Can't use queueReplacement to replace old body, since it may have been nullptr.
- // It's safe to do the replacements in place here - this node won't be traversed
- // further.
+ // It's safe to do the replacements in place here - the new body will still be
+ // traversed, but that won't create any problems.
node->setBody(newBody);
node->setCondition(createTempSymbol(node->getCondition()->getType()));
}
@@ -208,8 +200,8 @@
createTempAssignment(node->getCondition()->deepCopy()));
// Can't use queueReplacement to replace old body, since it may have been nullptr.
- // It's safe to do the replacements in place here - this node won't be traversed
- // further.
+ // It's safe to do the replacements in place here - the new body will still be
+ // traversed, but that won't create any problems.
node->setBody(newBody);
node->setCondition(createTempSymbol(node->getCondition()->getType()));
}
@@ -273,12 +265,18 @@
whileLoopBody);
loopScope->getSequence()->push_back(whileLoop);
queueReplacement(node, loopScope, OriginalNode::IS_DROPPED);
+
+ // After this the old body node will be traversed and loops inside it may be
+ // transformed. This is fine, since the old body node will still be in the AST after the
+ // transformation that's queued here, and transforming loops inside it doesn't need to
+ // know the exact post-transform path to it.
}
}
- mInsideLoopInitConditionOrExpression = false;
+ mFoundLoopToChange = false;
- if (!mFoundLoopToChange && node->getBody())
+ // We traverse the body of the loop even if the loop is transformed.
+ if (node->getBody())
node->getBody()->traverse(this);
}
@@ -293,14 +291,8 @@
SimplifyLoopConditionsTraverser traverser(conditionsToSimplifyMask, symbolTable, shaderVersion);
ASSERT(temporaryIndex != nullptr);
traverser.useTemporaryIndex(temporaryIndex);
- // Process one loop at a time, and reset the traverser between iterations.
- do
- {
- traverser.nextIteration();
- root->traverse(&traverser);
- if (traverser.foundLoopToChange())
- traverser.updateTree();
- } while (traverser.foundLoopToChange());
+ root->traverse(&traverser);
+ traverser.updateTree();
}
} // namespace sh