diff options
Diffstat (limited to 'gfx/angle/checkout/src/compiler/translator/tree_ops/SimplifyLoopConditions.cpp')
| -rw-r--r-- | gfx/angle/checkout/src/compiler/translator/tree_ops/SimplifyLoopConditions.cpp | 499 |
1 files changed, 499 insertions, 0 deletions
diff --git a/gfx/angle/checkout/src/compiler/translator/tree_ops/SimplifyLoopConditions.cpp b/gfx/angle/checkout/src/compiler/translator/tree_ops/SimplifyLoopConditions.cpp new file mode 100644 index 0000000000..c6a3e0b9ee --- /dev/null +++ b/gfx/angle/checkout/src/compiler/translator/tree_ops/SimplifyLoopConditions.cpp @@ -0,0 +1,499 @@ +// +// Copyright 2016 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. +// +// SimplifyLoopConditions is an AST traverser that converts loop conditions and loop expressions +// to regular statements inside the loop. This way further transformations that generate statements +// from loop conditions and loop expressions work correctly. +// + +#include "compiler/translator/tree_ops/SimplifyLoopConditions.h" + +#include "compiler/translator/StaticType.h" +#include "compiler/translator/tree_util/IntermNodePatternMatcher.h" +#include "compiler/translator/tree_util/IntermNode_util.h" +#include "compiler/translator/tree_util/IntermTraverse.h" + +namespace sh +{ + +namespace +{ + +struct LoopInfo +{ + const TVariable *conditionVariable = nullptr; + TIntermTyped *condition = nullptr; + TIntermTyped *expression = nullptr; +}; + +class SimplifyLoopConditionsTraverser : public TLValueTrackingTraverser +{ + public: + SimplifyLoopConditionsTraverser(const IntermNodePatternMatcher *conditionsToSimplify, + TSymbolTable *symbolTable); + + void traverseLoop(TIntermLoop *node) override; + + bool visitUnary(Visit visit, TIntermUnary *node) override; + bool visitBinary(Visit visit, TIntermBinary *node) override; + bool visitAggregate(Visit visit, TIntermAggregate *node) override; + bool visitTernary(Visit visit, TIntermTernary *node) override; + bool visitDeclaration(Visit visit, TIntermDeclaration *node) override; + bool visitBranch(Visit visit, TIntermBranch *node) override; + + bool foundLoopToChange() const { return mFoundLoopToChange; } + + protected: + // Marked to true once an operation that needs to be hoisted out of a loop expression has been + // found. + bool mFoundLoopToChange; + bool mInsideLoopInitConditionOrExpression; + const IntermNodePatternMatcher *mConditionsToSimplify; + + private: + LoopInfo mLoop; +}; + +SimplifyLoopConditionsTraverser::SimplifyLoopConditionsTraverser( + const IntermNodePatternMatcher *conditionsToSimplify, + TSymbolTable *symbolTable) + : TLValueTrackingTraverser(true, false, false, symbolTable), + mFoundLoopToChange(false), + mInsideLoopInitConditionOrExpression(false), + mConditionsToSimplify(conditionsToSimplify) +{} + +// 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. + +bool SimplifyLoopConditionsTraverser::visitUnary(Visit visit, TIntermUnary *node) +{ + if (!mInsideLoopInitConditionOrExpression) + return false; + + if (mFoundLoopToChange) + return false; // Already decided to change this loop. + + ASSERT(mConditionsToSimplify); + mFoundLoopToChange = mConditionsToSimplify->match(node); + return !mFoundLoopToChange; +} + +bool SimplifyLoopConditionsTraverser::visitBinary(Visit visit, TIntermBinary *node) +{ + if (!mInsideLoopInitConditionOrExpression) + return false; + + if (mFoundLoopToChange) + return false; // Already decided to change this loop. + + ASSERT(mConditionsToSimplify); + mFoundLoopToChange = + mConditionsToSimplify->match(node, getParentNode(), isLValueRequiredHere()); + return !mFoundLoopToChange; +} + +bool SimplifyLoopConditionsTraverser::visitAggregate(Visit visit, TIntermAggregate *node) +{ + if (!mInsideLoopInitConditionOrExpression) + return false; + + if (mFoundLoopToChange) + return false; // Already decided to change this loop. + + ASSERT(mConditionsToSimplify); + mFoundLoopToChange = mConditionsToSimplify->match(node, getParentNode()); + return !mFoundLoopToChange; +} + +bool SimplifyLoopConditionsTraverser::visitTernary(Visit visit, TIntermTernary *node) +{ + if (!mInsideLoopInitConditionOrExpression) + return false; + + if (mFoundLoopToChange) + return false; // Already decided to change this loop. + + ASSERT(mConditionsToSimplify); + mFoundLoopToChange = mConditionsToSimplify->match(node); + return !mFoundLoopToChange; +} + +bool SimplifyLoopConditionsTraverser::visitDeclaration(Visit visit, TIntermDeclaration *node) +{ + if (!mInsideLoopInitConditionOrExpression) + return false; + + if (mFoundLoopToChange) + return false; // Already decided to change this loop. + + ASSERT(mConditionsToSimplify); + mFoundLoopToChange = mConditionsToSimplify->match(node); + return !mFoundLoopToChange; +} + +bool SimplifyLoopConditionsTraverser::visitBranch(Visit visit, TIntermBranch *node) +{ + if (node->getFlowOp() == EOpContinue && (mLoop.condition || mLoop.expression)) + { + TIntermBlock *parent = getParentNode()->getAsBlock(); + ASSERT(parent); + TIntermSequence seq; + if (mLoop.expression) + { + seq.push_back(mLoop.expression->deepCopy()); + } + if (mLoop.condition) + { + ASSERT(mLoop.conditionVariable); + seq.push_back( + CreateTempAssignmentNode(mLoop.conditionVariable, mLoop.condition->deepCopy())); + } + seq.push_back(node); + mMultiReplacements.push_back(NodeReplaceWithMultipleEntry(parent, node, std::move(seq))); + } + + return true; +} + +TIntermBlock *CreateFromBody(TIntermLoop *node, bool *bodyEndsInBranchOut) +{ + TIntermBlock *newBody = new TIntermBlock(); + *bodyEndsInBranchOut = false; + + TIntermBlock *nodeBody = node->getBody(); + if (nodeBody != nullptr) + { + newBody->getSequence()->push_back(nodeBody); + *bodyEndsInBranchOut = EndsInBranch(nodeBody); + } + return newBody; +} + +void SimplifyLoopConditionsTraverser::traverseLoop(TIntermLoop *node) +{ + // 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; + mFoundLoopToChange = !mConditionsToSimplify; + + if (!mFoundLoopToChange && node->getInit()) + { + node->getInit()->traverse(this); + } + + if (!mFoundLoopToChange && node->getCondition()) + { + node->getCondition()->traverse(this); + } + + if (!mFoundLoopToChange && node->getExpression()) + { + node->getExpression()->traverse(this); + } + + mInsideLoopInitConditionOrExpression = false; + + const LoopInfo prevLoop = mLoop; + + if (mFoundLoopToChange) + { + const TType *boolType = StaticType::Get<EbtBool, EbpUndefined, EvqTemporary, 1, 1>(); + mLoop.conditionVariable = CreateTempVariable(mSymbolTable, boolType); + mLoop.condition = node->getCondition(); + mLoop.expression = node->getExpression(); + + // Replace the loop condition with a boolean variable that's updated on each iteration. + TLoopType loopType = node->getType(); + if (loopType == ELoopWhile) + { + ASSERT(!mLoop.expression); + + if (mLoop.condition->getAsSymbolNode()) + { + // Mask continue statement condition variable update. + mLoop.condition = nullptr; + } + else if (mLoop.condition->getAsConstantUnion()) + { + // Transform: + // while (expr) { body; } + // into + // bool s0 = expr; + // while (s0) { body; } + TIntermDeclaration *tempInitDeclaration = + CreateTempInitDeclarationNode(mLoop.conditionVariable, mLoop.condition); + insertStatementInParentBlock(tempInitDeclaration); + + node->setCondition(CreateTempSymbolNode(mLoop.conditionVariable)); + + // Mask continue statement condition variable update. + mLoop.condition = nullptr; + } + else + { + // Transform: + // while (expr) { body; } + // into + // bool s0 = expr; + // while (s0) { { body; } s0 = expr; } + // + // Local case statements are transformed into: + // s0 = expr; continue; + TIntermDeclaration *tempInitDeclaration = + CreateTempInitDeclarationNode(mLoop.conditionVariable, mLoop.condition); + insertStatementInParentBlock(tempInitDeclaration); + + bool bodyEndsInBranch; + TIntermBlock *newBody = CreateFromBody(node, &bodyEndsInBranch); + if (!bodyEndsInBranch) + { + newBody->getSequence()->push_back(CreateTempAssignmentNode( + mLoop.conditionVariable, mLoop.condition->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 - the new body will still be + // traversed, but that won't create any problems. + node->setBody(newBody); + node->setCondition(CreateTempSymbolNode(mLoop.conditionVariable)); + } + } + else if (loopType == ELoopDoWhile) + { + ASSERT(!mLoop.expression); + + if (mLoop.condition->getAsSymbolNode()) + { + // Mask continue statement condition variable update. + mLoop.condition = nullptr; + } + else if (mLoop.condition->getAsConstantUnion()) + { + // Transform: + // do { + // body; + // } while (expr); + // into + // bool s0 = expr; + // do { + // body; + // } while (s0); + TIntermDeclaration *tempInitDeclaration = + CreateTempInitDeclarationNode(mLoop.conditionVariable, mLoop.condition); + insertStatementInParentBlock(tempInitDeclaration); + + node->setCondition(CreateTempSymbolNode(mLoop.conditionVariable)); + + // Mask continue statement condition variable update. + mLoop.condition = nullptr; + } + else + { + // Transform: + // do { + // body; + // } while (expr); + // into + // bool s0; + // do { + // { body; } + // s0 = expr; + // } while (s0); + // Local case statements are transformed into: + // s0 = expr; continue; + TIntermDeclaration *tempInitDeclaration = + CreateTempDeclarationNode(mLoop.conditionVariable); + insertStatementInParentBlock(tempInitDeclaration); + + bool bodyEndsInBranch; + TIntermBlock *newBody = CreateFromBody(node, &bodyEndsInBranch); + if (!bodyEndsInBranch) + { + newBody->getSequence()->push_back( + CreateTempAssignmentNode(mLoop.conditionVariable, mLoop.condition)); + } + + // Can't use queueReplacement to replace old body, since it may have been nullptr. + // 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(CreateTempSymbolNode(mLoop.conditionVariable)); + } + } + else if (loopType == ELoopFor) + { + if (!mLoop.condition) + { + mLoop.condition = CreateBoolNode(true); + } + + TIntermLoop *whileLoop; + TIntermBlock *loopScope = new TIntermBlock(); + TIntermSequence *loopScopeSequence = loopScope->getSequence(); + + // Insert "init;" + if (node->getInit()) + { + loopScopeSequence->push_back(node->getInit()); + } + + if (mLoop.condition->getAsSymbolNode()) + { + // Move the loop condition inside the loop. + // Transform: + // for (init; expr; exprB) { body; } + // into + // { + // init; + // while (expr) { + // { body; } + // exprB; + // } + // } + // + // Local case statements are transformed into: + // exprB; continue; + + // Insert "{ body; }" in the while loop + bool bodyEndsInBranch; + TIntermBlock *whileLoopBody = CreateFromBody(node, &bodyEndsInBranch); + // Insert "exprB;" in the while loop + if (!bodyEndsInBranch && node->getExpression()) + { + whileLoopBody->getSequence()->push_back(node->getExpression()); + } + // Create "while(expr) { whileLoopBody }" + whileLoop = + new TIntermLoop(ELoopWhile, nullptr, mLoop.condition, nullptr, whileLoopBody); + + // Mask continue statement condition variable update. + mLoop.condition = nullptr; + } + else if (mLoop.condition->getAsConstantUnion()) + { + // Move the loop condition inside the loop. + // Transform: + // for (init; expr; exprB) { body; } + // into + // { + // init; + // bool s0 = expr; + // while (s0) { + // { body; } + // exprB; + // } + // } + // + // Local case statements are transformed into: + // exprB; continue; + + // Insert "bool s0 = expr;" + loopScopeSequence->push_back( + CreateTempInitDeclarationNode(mLoop.conditionVariable, mLoop.condition)); + // Insert "{ body; }" in the while loop + bool bodyEndsInBranch; + TIntermBlock *whileLoopBody = CreateFromBody(node, &bodyEndsInBranch); + // Insert "exprB;" in the while loop + if (!bodyEndsInBranch && node->getExpression()) + { + whileLoopBody->getSequence()->push_back(node->getExpression()); + } + // Create "while(s0) { whileLoopBody }" + whileLoop = new TIntermLoop(ELoopWhile, nullptr, + CreateTempSymbolNode(mLoop.conditionVariable), nullptr, + whileLoopBody); + + // Mask continue statement condition variable update. + mLoop.condition = nullptr; + } + else + { + // Move the loop condition inside the loop. + // Transform: + // for (init; expr; exprB) { body; } + // into + // { + // init; + // bool s0 = expr; + // while (s0) { + // { body; } + // exprB; + // s0 = expr; + // } + // } + // + // Local case statements are transformed into: + // exprB; s0 = expr; continue; + + // Insert "bool s0 = expr;" + loopScopeSequence->push_back( + CreateTempInitDeclarationNode(mLoop.conditionVariable, mLoop.condition)); + // Insert "{ body; }" in the while loop + bool bodyEndsInBranch; + TIntermBlock *whileLoopBody = CreateFromBody(node, &bodyEndsInBranch); + // Insert "exprB;" in the while loop + if (!bodyEndsInBranch && node->getExpression()) + { + whileLoopBody->getSequence()->push_back(node->getExpression()); + } + // Insert "s0 = expr;" in the while loop + if (!bodyEndsInBranch) + { + whileLoopBody->getSequence()->push_back(CreateTempAssignmentNode( + mLoop.conditionVariable, mLoop.condition->deepCopy())); + } + // Create "while(s0) { whileLoopBody }" + whileLoop = new TIntermLoop(ELoopWhile, nullptr, + CreateTempSymbolNode(mLoop.conditionVariable), nullptr, + whileLoopBody); + } + + loopScope->getSequence()->push_back(whileLoop); + queueReplacement(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. + } + } + + mFoundLoopToChange = false; + + // We traverse the body of the loop even if the loop is transformed. + if (node->getBody()) + node->getBody()->traverse(this); + + mLoop = prevLoop; +} + +} // namespace + +bool SimplifyLoopConditions(TCompiler *compiler, TIntermNode *root, TSymbolTable *symbolTable) +{ + SimplifyLoopConditionsTraverser traverser(nullptr, symbolTable); + root->traverse(&traverser); + return traverser.updateTree(compiler, root); +} + +bool SimplifyLoopConditions(TCompiler *compiler, + TIntermNode *root, + unsigned int conditionsToSimplifyMask, + TSymbolTable *symbolTable) +{ + IntermNodePatternMatcher conditionsToSimplify(conditionsToSimplifyMask); + SimplifyLoopConditionsTraverser traverser(&conditionsToSimplify, symbolTable); + root->traverse(&traverser); + return traverser.updateTree(compiler, root); +} + +} // namespace sh |