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/IntermNode.cpp b/src/compiler/translator/IntermNode.cpp
index 159958c..3f4c6c1 100644
--- a/src/compiler/translator/IntermNode.cpp
+++ b/src/compiler/translator/IntermNode.cpp
@@ -3300,10 +3300,27 @@
return hashedName;
}
+bool TIntermTraverser::CompareInsertion(const NodeInsertMultipleEntry &a,
+ const NodeInsertMultipleEntry &b)
+{
+ if (a.parent != b.parent)
+ {
+ return a.parent > b.parent;
+ }
+ return a.position > b.position;
+}
+
void TIntermTraverser::updateTree()
{
+ // Sort the insertions so that insertion position is decreasing. This way multiple insertions to
+ // the same parent node are handled correctly.
+ std::sort(mInsertions.begin(), mInsertions.end(), CompareInsertion);
for (size_t ii = 0; ii < mInsertions.size(); ++ii)
{
+ // We can't know here what the intended ordering of two insertions to the same position is,
+ // so it is not supported.
+ ASSERT(ii == 0 || mInsertions[ii].position != mInsertions[ii - 1].position ||
+ mInsertions[ii].parent != mInsertions[ii - 1].parent);
const NodeInsertMultipleEntry &insertion = mInsertions[ii];
ASSERT(insertion.parent);
if (!insertion.insertionsAfter.empty())
diff --git a/src/compiler/translator/IntermNode.h b/src/compiler/translator/IntermNode.h
index ea3f097..65c9bdc 100644
--- a/src/compiler/translator/IntermNode.h
+++ b/src/compiler/translator/IntermNode.h
@@ -1087,9 +1087,7 @@
// traversed.
// The statements will be inserted before the node being traversed once updateTree is called.
// Should only be called during PreVisit or PostVisit from sequence nodes.
- // Note that inserting more than one set of nodes to the same parent node on a single updateTree
- // call is not
- // supported.
+ // Note that two insertions to the same position in the same block are not supported.
void insertStatementsInParentBlock(const TIntermSequence &insertions);
// Same as above, but supports simultaneous insertion of statements before and after the node
@@ -1149,6 +1147,9 @@
private:
static TName GetInternalFunctionName(const char *name);
+ static bool CompareInsertion(const NodeInsertMultipleEntry &a,
+ const NodeInsertMultipleEntry &b);
+
// To replace a single node with another on the parent node
struct NodeUpdateEntry
{
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