diff options
Diffstat (limited to 'gfx/angle/checkout/src/compiler/translator/tree_util/IntermTraverse.cpp')
| -rw-r--r-- | gfx/angle/checkout/src/compiler/translator/tree_util/IntermTraverse.cpp | 708 |
1 files changed, 708 insertions, 0 deletions
diff --git a/gfx/angle/checkout/src/compiler/translator/tree_util/IntermTraverse.cpp b/gfx/angle/checkout/src/compiler/translator/tree_util/IntermTraverse.cpp new file mode 100644 index 0000000000..c4bbe1fa4d --- /dev/null +++ b/gfx/angle/checkout/src/compiler/translator/tree_util/IntermTraverse.cpp @@ -0,0 +1,708 @@ +// +// 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 |