Source code
Revision control
Copy as Markdown
Other Tools
//
// 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