Source code
Revision control
Copy as Markdown
Other Tools
//
// Copyright 2002 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.
//
#include "compiler/translator/tree_util/IntermTraverse.h"
#include "compiler/translator/Compiler.h"
#include "compiler/translator/InfoSink.h"
#include "compiler/translator/SymbolTable.h"
#include "compiler/translator/tree_util/IntermNode_util.h"
#include "compiler/translator/util.h"
namespace sh
{
// Traverse the intermediate representation tree, and call a node type specific visit function for
// each node. Traversal is done recursively through the node member function traverse(). Nodes with
// children can have their whole subtree skipped if preVisit is turned on and the type specific
// function returns false.
template <typename T>
void TIntermTraverser::traverse(T *node)
{
ScopedNodeInTraversalPath addToPath(this, node);
if (!addToPath.isWithinDepthLimit())
return;
bool visit = true;
// Visit the node before children if pre-visiting.
if (preVisit)
visit = node->visit(PreVisit, this);
if (visit)
{
size_t childIndex = 0;
size_t childCount = node->getChildCount();
while (childIndex < childCount && visit)
{
mCurrentChildIndex = childIndex;
node->getChildNode(childIndex)->traverse(this);
mCurrentChildIndex = childIndex;
if (inVisit && childIndex != childCount - 1)
{
visit = node->visit(InVisit, this);
}
++childIndex;
}
if (visit && postVisit)
node->visit(PostVisit, this);
}
}
// Instantiate template for RewriteAtomicFunctionExpressions, in case this gets inlined thus not
// exported from the TU.
template void TIntermTraverser::traverse(TIntermNode *);
void TIntermNode::traverse(TIntermTraverser *it)
{
it->traverse(this);
}
void TIntermSymbol::traverse(TIntermTraverser *it)
{
TIntermTraverser::ScopedNodeInTraversalPath addToPath(it, this);
it->visitSymbol(this);
}
void TIntermConstantUnion::traverse(TIntermTraverser *it)
{
TIntermTraverser::ScopedNodeInTraversalPath addToPath(it, this);
it->visitConstantUnion(this);
}
void TIntermFunctionPrototype::traverse(TIntermTraverser *it)
{
TIntermTraverser::ScopedNodeInTraversalPath addToPath(it, this);
it->visitFunctionPrototype(this);
}
void TIntermBinary::traverse(TIntermTraverser *it)
{
it->traverseBinary(this);
}
void TIntermUnary::traverse(TIntermTraverser *it)
{
it->traverseUnary(this);
}
void TIntermFunctionDefinition::traverse(TIntermTraverser *it)
{
it->traverseFunctionDefinition(this);
}
void TIntermBlock::traverse(TIntermTraverser *it)
{
it->traverseBlock(this);
}
void TIntermAggregate::traverse(TIntermTraverser *it)
{
it->traverseAggregate(this);
}
void TIntermLoop::traverse(TIntermTraverser *it)
{
it->traverseLoop(this);
}
void TIntermPreprocessorDirective::traverse(TIntermTraverser *it)
{
it->visitPreprocessorDirective(this);
}
bool TIntermSymbol::visit(Visit visit, TIntermTraverser *it)
{
it->visitSymbol(this);
return false;
}
bool TIntermConstantUnion::visit(Visit visit, TIntermTraverser *it)
{
it->visitConstantUnion(this);
return false;
}
bool TIntermFunctionPrototype::visit(Visit visit, TIntermTraverser *it)
{
it->visitFunctionPrototype(this);
return false;
}
bool TIntermFunctionDefinition::visit(Visit visit, TIntermTraverser *it)
{
return it->visitFunctionDefinition(visit, this);
}
bool TIntermUnary::visit(Visit visit, TIntermTraverser *it)
{
return it->visitUnary(visit, this);
}
bool TIntermSwizzle::visit(Visit visit, TIntermTraverser *it)
{
return it->visitSwizzle(visit, this);
}
bool TIntermBinary::visit(Visit visit, TIntermTraverser *it)
{
return it->visitBinary(visit, this);
}
bool TIntermTernary::visit(Visit visit, TIntermTraverser *it)
{
return it->visitTernary(visit, this);
}
bool TIntermAggregate::visit(Visit visit, TIntermTraverser *it)
{
return it->visitAggregate(visit, this);
}
bool TIntermDeclaration::visit(Visit visit, TIntermTraverser *it)
{
return it->visitDeclaration(visit, this);
}
bool TIntermGlobalQualifierDeclaration::visit(Visit visit, TIntermTraverser *it)
{
return it->visitGlobalQualifierDeclaration(visit, this);
}
bool TIntermBlock::visit(Visit visit, TIntermTraverser *it)
{
return it->visitBlock(visit, this);
}
bool TIntermIfElse::visit(Visit visit, TIntermTraverser *it)
{
return it->visitIfElse(visit, this);
}
bool TIntermLoop::visit(Visit visit, TIntermTraverser *it)
{
return it->visitLoop(visit, this);
}
bool TIntermBranch::visit(Visit visit, TIntermTraverser *it)
{
return it->visitBranch(visit, this);
}
bool TIntermSwitch::visit(Visit visit, TIntermTraverser *it)
{
return it->visitSwitch(visit, this);
}
bool TIntermCase::visit(Visit visit, TIntermTraverser *it)
{
return it->visitCase(visit, this);
}
bool TIntermPreprocessorDirective::visit(Visit visit, TIntermTraverser *it)
{
it->visitPreprocessorDirective(this);
return false;
}
TIntermTraverser::TIntermTraverser(bool preVisit,
bool inVisit,
bool postVisit,
TSymbolTable *symbolTable)
: preVisit(preVisit),
inVisit(inVisit),
postVisit(postVisit),
mMaxDepth(0),
mMaxAllowedDepth(std::numeric_limits<int>::max()),
mInGlobalScope(true),
mSymbolTable(symbolTable),
mCurrentChildIndex(0)
{
// Only enabling inVisit is not supported.
ASSERT(!(inVisit && !preVisit && !postVisit));
}
TIntermTraverser::~TIntermTraverser() {}
void TIntermTraverser::setMaxAllowedDepth(int depth)
{
mMaxAllowedDepth = depth;
}
const TIntermBlock *TIntermTraverser::getParentBlock() const
{
if (!mParentBlockStack.empty())
{
return mParentBlockStack.back().node;
}
return nullptr;
}
void TIntermTraverser::pushParentBlock(TIntermBlock *node)
{
mParentBlockStack.push_back(ParentBlock(node, 0));
}
void TIntermTraverser::incrementParentBlockPos()
{
++mParentBlockStack.back().pos;
}
void TIntermTraverser::popParentBlock()
{
ASSERT(!mParentBlockStack.empty());
mParentBlockStack.pop_back();
}
void TIntermTraverser::insertStatementsInParentBlock(const TIntermSequence &insertions)
{
TIntermSequence emptyInsertionsAfter;
insertStatementsInParentBlock(insertions, emptyInsertionsAfter);
}
void TIntermTraverser::insertStatementsInParentBlock(const TIntermSequence &insertionsBefore,
const TIntermSequence &insertionsAfter)
{
ASSERT(!mParentBlockStack.empty());
ParentBlock &parentBlock = mParentBlockStack.back();
if (mPath.back() == parentBlock.node)
{
ASSERT(mParentBlockStack.size() >= 2u);
// The current node is a block node, so the parent block is not the topmost one in the block
// stack, but the one below that.
parentBlock = mParentBlockStack.at(mParentBlockStack.size() - 2u);
}
NodeInsertMultipleEntry insert(parentBlock.node, parentBlock.pos, insertionsBefore,
insertionsAfter);
mInsertions.push_back(insert);
}
void TIntermTraverser::insertStatementInParentBlock(TIntermNode *statement)
{
TIntermSequence insertions;
insertions.push_back(statement);
insertStatementsInParentBlock(insertions);
}
void TIntermTraverser::insertStatementsInBlockAtPosition(TIntermBlock *parent,
size_t position,
const TIntermSequence &insertionsBefore,
const TIntermSequence &insertionsAfter)
{
ASSERT(parent);
ASSERT(position >= 0);
ASSERT(position < parent->getChildCount());
mInsertions.emplace_back(parent, position, insertionsBefore, insertionsAfter);
}
void TLValueTrackingTraverser::setInFunctionCallOutParameter(bool inOutParameter)
{
mInFunctionCallOutParameter = inOutParameter;
}
bool TLValueTrackingTraverser::isInFunctionCallOutParameter() const
{
return mInFunctionCallOutParameter;
}
void TIntermTraverser::traverseBinary(TIntermBinary *node)
{
traverse(node);
}
void TLValueTrackingTraverser::traverseBinary(TIntermBinary *node)
{
ScopedNodeInTraversalPath addToPath(this, node);
if (!addToPath.isWithinDepthLimit())
return;
bool visit = true;
// visit the node before children if pre-visiting.
if (preVisit)
visit = node->visit(PreVisit, this);
// Visit the children, in the right order.
if (visit)
{
if (node->isAssignment())
{
ASSERT(!isLValueRequiredHere());
setOperatorRequiresLValue(true);
}
node->getLeft()->traverse(this);
if (node->isAssignment())
setOperatorRequiresLValue(false);
if (inVisit)
visit = node->visit(InVisit, this);
if (visit)
{
// Some binary operations like indexing can be inside an expression which must be an
// l-value.
bool parentOperatorRequiresLValue = operatorRequiresLValue();
bool parentInFunctionCallOutParameter = isInFunctionCallOutParameter();
// Index is not required to be an l-value even when the surrounding expression is
// required to be an l-value.
TOperator op = node->getOp();
if (op == EOpIndexDirect || op == EOpIndexDirectInterfaceBlock ||
op == EOpIndexDirectStruct || op == EOpIndexIndirect)
{
setOperatorRequiresLValue(false);
setInFunctionCallOutParameter(false);
}
node->getRight()->traverse(this);
setOperatorRequiresLValue(parentOperatorRequiresLValue);
setInFunctionCallOutParameter(parentInFunctionCallOutParameter);
// Visit the node after the children, if requested and the traversal
// hasn't been cancelled yet.
if (postVisit)
visit = node->visit(PostVisit, this);
}
}
}
void TIntermTraverser::traverseUnary(TIntermUnary *node)
{
traverse(node);
}
void TLValueTrackingTraverser::traverseUnary(TIntermUnary *node)
{
ScopedNodeInTraversalPath addToPath(this, node);
if (!addToPath.isWithinDepthLimit())
return;
bool visit = true;
if (preVisit)
visit = node->visit(PreVisit, this);
if (visit)
{
ASSERT(!operatorRequiresLValue());
switch (node->getOp())
{
case EOpPostIncrement:
case EOpPostDecrement:
case EOpPreIncrement:
case EOpPreDecrement:
setOperatorRequiresLValue(true);
break;
default:
break;
}
node->getOperand()->traverse(this);
setOperatorRequiresLValue(false);
if (postVisit)
visit = node->visit(PostVisit, this);
}
}
// Traverse a function definition node. This keeps track of global scope.
void TIntermTraverser::traverseFunctionDefinition(TIntermFunctionDefinition *node)
{
ScopedNodeInTraversalPath addToPath(this, node);
if (!addToPath.isWithinDepthLimit())
return;
bool visit = true;
if (preVisit)
visit = node->visit(PreVisit, this);
if (visit)
{
mCurrentChildIndex = 0;
node->getFunctionPrototype()->traverse(this);
mCurrentChildIndex = 0;
if (inVisit)
visit = node->visit(InVisit, this);
if (visit)
{
mInGlobalScope = false;
mCurrentChildIndex = 1;
node->getBody()->traverse(this);
mCurrentChildIndex = 1;
mInGlobalScope = true;
if (postVisit)
visit = node->visit(PostVisit, this);
}
}
}
// Traverse a block node. This keeps track of the position of traversed child nodes within the block
// so that nodes may be inserted before or after them.
void TIntermTraverser::traverseBlock(TIntermBlock *node)
{
ScopedNodeInTraversalPath addToPath(this, node);
if (!addToPath.isWithinDepthLimit())
return;
pushParentBlock(node);
bool visit = true;
TIntermSequence *sequence = node->getSequence();
if (preVisit)
visit = node->visit(PreVisit, this);
if (visit)
{
for (size_t childIndex = 0; childIndex < sequence->size(); ++childIndex)
{
TIntermNode *child = (*sequence)[childIndex];
if (visit)
{
mCurrentChildIndex = childIndex;
child->traverse(this);
mCurrentChildIndex = childIndex;
if (inVisit)
{
if (child != sequence->back())
visit = node->visit(InVisit, this);
}
incrementParentBlockPos();
}
}
if (visit && postVisit)
visit = node->visit(PostVisit, this);
}
popParentBlock();
}
void TIntermTraverser::traverseAggregate(TIntermAggregate *node)
{
traverse(node);
}
bool TIntermTraverser::CompareInsertion(const NodeInsertMultipleEntry &a,
const NodeInsertMultipleEntry &b)
{
if (a.parent != b.parent)
{
return a.parent < b.parent;
}
return a.position < b.position;
}
bool TIntermTraverser::updateTree(TCompiler *compiler, TIntermNode *node)
{
// Sort the insertions so that insertion position is increasing and same position insertions are
// not reordered. The insertions are processed in reverse order so that multiple insertions to
// the same parent node are handled correctly.
std::stable_sort(mInsertions.begin(), mInsertions.end(), CompareInsertion);
for (size_t ii = 0; ii < mInsertions.size(); ++ii)
{
// If two insertions are to the same position, insert them in the order they were specified.
// The std::stable_sort call above will automatically guarantee this.
const NodeInsertMultipleEntry &insertion = mInsertions[mInsertions.size() - ii - 1];
ASSERT(insertion.parent);
if (!insertion.insertionsAfter.empty())
{
bool inserted = insertion.parent->insertChildNodes(insertion.position + 1,
insertion.insertionsAfter);
ASSERT(inserted);
}
if (!insertion.insertionsBefore.empty())
{
bool inserted =
insertion.parent->insertChildNodes(insertion.position, insertion.insertionsBefore);
ASSERT(inserted);
}
}
for (size_t ii = 0; ii < mReplacements.size(); ++ii)
{
const NodeUpdateEntry &replacement = mReplacements[ii];
ASSERT(replacement.parent);
bool replaced =
replacement.parent->replaceChildNode(replacement.original, replacement.replacement);
ASSERT(replaced);
// Make sure the precision is not accidentally dropped. It's ok if the precision is not the
// same, as the transformations are allowed to replace an expression with one that is
// temporarily evaluated at a different (likely higher) precision.
TIntermTyped *originalAsTyped = replacement.original->getAsTyped();
TIntermTyped *replacementAsTyped =
replacement.replacement ? replacement.replacement->getAsTyped() : nullptr;
if (originalAsTyped != nullptr && replacementAsTyped != nullptr)
{
const TType &originalType = originalAsTyped->getType();
const TType &replacementType = replacementAsTyped->getType();
ASSERT(!IsPrecisionApplicableToType(originalType.getBasicType()) ||
!IsPrecisionApplicableToType(replacementType.getBasicType()) ||
originalType.getPrecision() == EbpUndefined ||
replacementType.getPrecision() != EbpUndefined);
}
if (!replacement.originalBecomesChildOfReplacement)
{
// In AST traversing, a parent is visited before its children.
// After we replace a node, if its immediate child is to
// be replaced, we need to make sure we don't update the replaced
// node; instead, we update the replacement node.
for (size_t jj = ii + 1; jj < mReplacements.size(); ++jj)
{
NodeUpdateEntry &replacement2 = mReplacements[jj];
if (replacement2.parent == replacement.original)
replacement2.parent = replacement.replacement;
}
}
}
for (size_t ii = 0; ii < mMultiReplacements.size(); ++ii)
{
const NodeReplaceWithMultipleEntry &replacement = mMultiReplacements[ii];
ASSERT(replacement.parent);
bool replaced = replacement.parent->replaceChildNodeWithMultiple(replacement.original,
replacement.replacements);
ASSERT(replaced);
}
clearReplacementQueue();
return compiler->validateAST(node);
}
void TIntermTraverser::clearReplacementQueue()
{
mReplacements.clear();
mMultiReplacements.clear();
mInsertions.clear();
}
void TIntermTraverser::queueReplacement(TIntermNode *replacement, OriginalNode originalStatus)
{
queueReplacementWithParent(getParentNode(), mPath.back(), replacement, originalStatus);
}
void TIntermTraverser::queueReplacementWithParent(TIntermNode *parent,
TIntermNode *original,
TIntermNode *replacement,
OriginalNode originalStatus)
{
bool originalBecomesChild = (originalStatus == OriginalNode::BECOMES_CHILD);
mReplacements.push_back(NodeUpdateEntry(parent, original, replacement, originalBecomesChild));
}
void TIntermTraverser::queueAccessChainReplacement(TIntermTyped *replacement)
{
uint32_t ancestorIndex = 0;
TIntermTyped *toReplace = nullptr;
while (true)
{
TIntermNode *ancestor = getAncestorNode(ancestorIndex);
ASSERT(ancestor != nullptr);
TIntermBinary *asBinary = ancestor->getAsBinaryNode();
if (asBinary == nullptr ||
(asBinary->getOp() != EOpIndexDirect && asBinary->getOp() != EOpIndexIndirect))
{
break;
}
replacement = new TIntermBinary(asBinary->getOp(), replacement, asBinary->getRight());
toReplace = asBinary;
++ancestorIndex;
}
if (toReplace == nullptr)
{
queueReplacement(replacement, OriginalNode::IS_DROPPED);
}
else
{
queueReplacementWithParent(getAncestorNode(ancestorIndex), toReplace, replacement,
OriginalNode::IS_DROPPED);
}
}
TLValueTrackingTraverser::TLValueTrackingTraverser(bool preVisitIn,
bool inVisitIn,
bool postVisitIn,
TSymbolTable *symbolTable)
: TIntermTraverser(preVisitIn, inVisitIn, postVisitIn, symbolTable),
mOperatorRequiresLValue(false),
mInFunctionCallOutParameter(false)
{
ASSERT(symbolTable);
}
void TLValueTrackingTraverser::traverseAggregate(TIntermAggregate *node)
{
ScopedNodeInTraversalPath addToPath(this, node);
if (!addToPath.isWithinDepthLimit())
return;
bool visit = true;
TIntermSequence *sequence = node->getSequence();
if (preVisit)
visit = node->visit(PreVisit, this);
if (visit)
{
size_t paramIndex = 0u;
for (auto *child : *sequence)
{
if (visit)
{
if (node->getFunction())
{
// Both built-ins and user defined functions should have the function symbol
// set.
ASSERT(paramIndex < node->getFunction()->getParamCount());
TQualifier qualifier =
node->getFunction()->getParam(paramIndex)->getType().getQualifier();
setInFunctionCallOutParameter(qualifier == EvqParamOut ||
qualifier == EvqParamInOut);
++paramIndex;
}
else
{
ASSERT(node->isConstructor());
}
child->traverse(this);
if (inVisit)
{
if (child != sequence->back())
visit = node->visit(InVisit, this);
}
}
}
setInFunctionCallOutParameter(false);
if (visit && postVisit)
visit = node->visit(PostVisit, this);
}
}
void TIntermTraverser::traverseLoop(TIntermLoop *node)
{
traverse(node);
}
} // namespace sh