Source code
Revision control
Copy as Markdown
Other Tools
//
// Copyright 2017 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.
//
// IntermTraverse.h : base classes for AST traversers that walk the AST and
// also have the ability to transform it by replacing nodes.
#ifndef COMPILER_TRANSLATOR_TREEUTIL_INTERMTRAVERSE_H_
#define COMPILER_TRANSLATOR_TREEUTIL_INTERMTRAVERSE_H_
#include "compiler/translator/IntermNode.h"
#include "compiler/translator/tree_util/Visit.h"
namespace sh
{
class TCompiler;
class TSymbolTable;
class TSymbolUniqueId;
// For traversing the tree. User should derive from this class overriding the visit functions,
// and then pass an object of the subclass to a traverse method of a node.
//
// The traverse*() functions may also be overridden to do other bookkeeping on the tree to provide
// contextual information to the visit functions, such as whether the node is the target of an
// assignment. This is complex to maintain and so should only be done in special cases.
//
// When using this, just fill in the methods for nodes you want visited.
// Return false from a pre-visit to skip visiting that node's subtree.
//
// See also how to write AST transformations documentation:
class TIntermTraverser : angle::NonCopyable
{
public:
POOL_ALLOCATOR_NEW_DELETE
TIntermTraverser(bool preVisitIn,
bool inVisitIn,
bool postVisitIn,
TSymbolTable *symbolTable = nullptr);
virtual ~TIntermTraverser();
virtual void visitSymbol(TIntermSymbol *node) {}
virtual void visitConstantUnion(TIntermConstantUnion *node) {}
virtual bool visitSwizzle(Visit visit, TIntermSwizzle *node) { return true; }
virtual bool visitBinary(Visit visit, TIntermBinary *node) { return true; }
virtual bool visitUnary(Visit visit, TIntermUnary *node) { return true; }
virtual bool visitTernary(Visit visit, TIntermTernary *node) { return true; }
virtual bool visitIfElse(Visit visit, TIntermIfElse *node) { return true; }
virtual bool visitSwitch(Visit visit, TIntermSwitch *node) { return true; }
virtual bool visitCase(Visit visit, TIntermCase *node) { return true; }
virtual void visitFunctionPrototype(TIntermFunctionPrototype *node) {}
virtual bool visitFunctionDefinition(Visit visit, TIntermFunctionDefinition *node)
{
return true;
}
virtual bool visitAggregate(Visit visit, TIntermAggregate *node) { return true; }
virtual bool visitBlock(Visit visit, TIntermBlock *node) { return true; }
virtual bool visitGlobalQualifierDeclaration(Visit visit,
TIntermGlobalQualifierDeclaration *node)
{
return true;
}
virtual bool visitDeclaration(Visit visit, TIntermDeclaration *node) { return true; }
virtual bool visitLoop(Visit visit, TIntermLoop *node) { return true; }
virtual bool visitBranch(Visit visit, TIntermBranch *node) { return true; }
virtual void visitPreprocessorDirective(TIntermPreprocessorDirective *node) {}
// The traverse functions contain logic for iterating over the children of the node
// and calling the visit functions in the appropriate places. They also track some
// context that may be used by the visit functions.
// The generic traverse() function is used for nodes that don't need special handling.
// It's templated in order to avoid virtual function calls, this gains around 2% compiler
// performance.
template <typename T>
void traverse(T *node);
// Specialized traverse functions are implemented for node types where traversal logic may need
// to be overridden or where some special bookkeeping needs to be done.
virtual void traverseBinary(TIntermBinary *node);
virtual void traverseUnary(TIntermUnary *node);
virtual void traverseFunctionDefinition(TIntermFunctionDefinition *node);
virtual void traverseAggregate(TIntermAggregate *node);
virtual void traverseBlock(TIntermBlock *node);
virtual void traverseLoop(TIntermLoop *node);
int getMaxDepth() const { return mMaxDepth; }
// If traversers need to replace nodes, they can add the replacements in
// mReplacements/mMultiReplacements during traversal and the user of the traverser should call
// this function after traversal to perform them.
//
// Compiler is used to validate the tree. Node is the same given to traverse(). Returns false
// if the tree is invalid after update.
[[nodiscard]] bool updateTree(TCompiler *compiler, TIntermNode *node);
protected:
void setMaxAllowedDepth(int depth);
// Should only be called from traverse*() functions
bool incrementDepth(TIntermNode *current)
{
mMaxDepth = std::max(mMaxDepth, static_cast<int>(mPath.size()));
mPath.push_back(current);
return mMaxDepth < mMaxAllowedDepth;
}
// Should only be called from traverse*() functions
void decrementDepth() { mPath.pop_back(); }
int getCurrentTraversalDepth() const { return static_cast<int>(mPath.size()) - 1; }
int getCurrentBlockDepth() const { return static_cast<int>(mParentBlockStack.size()) - 1; }
// RAII helper for incrementDepth/decrementDepth
class [[nodiscard]] ScopedNodeInTraversalPath
{
public:
ScopedNodeInTraversalPath(TIntermTraverser *traverser, TIntermNode *current)
: mTraverser(traverser)
{
mWithinDepthLimit = mTraverser->incrementDepth(current);
}
~ScopedNodeInTraversalPath() { mTraverser->decrementDepth(); }
bool isWithinDepthLimit() { return mWithinDepthLimit; }
private:
TIntermTraverser *mTraverser;
bool mWithinDepthLimit;
};
// Optimized traversal functions for leaf nodes directly access ScopedNodeInTraversalPath.
friend void TIntermSymbol::traverse(TIntermTraverser *);
friend void TIntermConstantUnion::traverse(TIntermTraverser *);
friend void TIntermFunctionPrototype::traverse(TIntermTraverser *);
TIntermNode *getParentNode() const
{
return mPath.size() <= 1 ? nullptr : mPath[mPath.size() - 2u];
}
// Return the nth ancestor of the node being traversed. getAncestorNode(0) == getParentNode()
TIntermNode *getAncestorNode(unsigned int n) const
{
if (mPath.size() > n + 1u)
{
return mPath[mPath.size() - n - 2u];
}
return nullptr;
}
// Returns what child index is currently being visited. For example when visiting the children
// of an aggregate, it can be used to find out which argument of the parent (aggregate) node
// they correspond to. Only valid in the PreVisit call of the child.
size_t getParentChildIndex(Visit visit) const
{
ASSERT(visit == PreVisit);
return mCurrentChildIndex;
}
// Returns what child index has just been processed. Only valid in the InVisit and PostVisit
// calls of the parent node.
size_t getLastTraversedChildIndex(Visit visit) const
{
ASSERT(visit != PreVisit);
return mCurrentChildIndex;
}
const TIntermBlock *getParentBlock() const;
TIntermNode *getRootNode() const
{
ASSERT(!mPath.empty());
return mPath.front();
}
void pushParentBlock(TIntermBlock *node);
void incrementParentBlockPos();
void popParentBlock();
// To replace a single node with multiple nodes in the parent aggregate. May be used with blocks
// but also with other nodes like declarations.
struct NodeReplaceWithMultipleEntry
{
NodeReplaceWithMultipleEntry(TIntermAggregateBase *parentIn,
TIntermNode *originalIn,
TIntermSequence &&replacementsIn)
: parent(parentIn), original(originalIn), replacements(std::move(replacementsIn))
{}
TIntermAggregateBase *parent;
TIntermNode *original;
TIntermSequence replacements;
};
// Helper to insert statements in the parent block of the node currently being traversed.
// The statements will be inserted before the node being traversed once updateTree is called.
// Should only be called during PreVisit or PostVisit if called from block nodes.
// 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
// currently being traversed.
void insertStatementsInParentBlock(const TIntermSequence &insertionsBefore,
const TIntermSequence &insertionsAfter);
// Helper to insert a single statement.
void insertStatementInParentBlock(TIntermNode *statement);
// Explicitly specify where to insert statements. The statements are inserted before and after
// the specified position. The statements will be inserted once updateTree is called. Note that
// two insertions to the same position in the same block are not supported.
void insertStatementsInBlockAtPosition(TIntermBlock *parent,
size_t position,
const TIntermSequence &insertionsBefore,
const TIntermSequence &insertionsAfter);
enum class OriginalNode
{
BECOMES_CHILD,
IS_DROPPED
};
void clearReplacementQueue();
// Replace the node currently being visited with replacement.
void queueReplacement(TIntermNode *replacement, OriginalNode originalStatus);
// Explicitly specify a node to replace with replacement.
void queueReplacementWithParent(TIntermNode *parent,
TIntermNode *original,
TIntermNode *replacement,
OriginalNode originalStatus);
// Walk the ancestors and replace the access chain that leads to this symbol. This fixes up the
// types of the intermediate nodes, so it should be used when the type of the symbol changes.
// The AST transformation must still visit the (indirect) index nodes to transform the
// expression inside those nodes. Note that due to the way these replacements work, the AST
// transformation should not attempt to replace the actual index node itself, but only a subnode
// of that.
//
// Node 1 Node 6
// EOpIndexDirect EOpIndexDirect
// / \ / \
// Node 2 Node 3 Node 7 Node 3
// EOpIndexIndirect N --> replaced with --> EOpIndexIndirect N
// / \ / \
// Node 4 Node 5 Node 8 Node 5
// symbol expression replacement expression
// ^ ^
// | |
// This symbol is being replaced, This node is directly placed in the
// and the replacement is given new access chain, and its parent is
// to this function. is changed. This is why a
// replacment attempt for this node
// itself will not work.
//
void queueAccessChainReplacement(TIntermTyped *replacement);
const bool preVisit;
const bool inVisit;
const bool postVisit;
int mMaxDepth;
int mMaxAllowedDepth;
bool mInGlobalScope;
// During traversing, save all the changes that need to happen into
// mReplacements/mMultiReplacements, then do them by calling updateTree().
// Multi replacements are processed after single replacements.
std::vector<NodeReplaceWithMultipleEntry> mMultiReplacements;
TSymbolTable *mSymbolTable;
private:
// To insert multiple nodes into the parent block.
struct NodeInsertMultipleEntry
{
NodeInsertMultipleEntry(TIntermBlock *_parent,
TIntermSequence::size_type _position,
TIntermSequence _insertionsBefore,
TIntermSequence _insertionsAfter)
: parent(_parent),
position(_position),
insertionsBefore(_insertionsBefore),
insertionsAfter(_insertionsAfter)
{}
TIntermBlock *parent;
TIntermSequence::size_type position;
TIntermSequence insertionsBefore;
TIntermSequence insertionsAfter;
};
static bool CompareInsertion(const NodeInsertMultipleEntry &a,
const NodeInsertMultipleEntry &b);
// To replace a single node with another on the parent node
struct NodeUpdateEntry
{
NodeUpdateEntry(TIntermNode *_parent,
TIntermNode *_original,
TIntermNode *_replacement,
bool _originalBecomesChildOfReplacement)
: parent(_parent),
original(_original),
replacement(_replacement),
originalBecomesChildOfReplacement(_originalBecomesChildOfReplacement)
{}
TIntermNode *parent;
TIntermNode *original;
TIntermNode *replacement;
bool originalBecomesChildOfReplacement;
};
struct ParentBlock
{
ParentBlock(TIntermBlock *nodeIn, TIntermSequence::size_type posIn)
: node(nodeIn), pos(posIn)
{}
TIntermBlock *node;
TIntermSequence::size_type pos;
};
std::vector<NodeInsertMultipleEntry> mInsertions;
std::vector<NodeUpdateEntry> mReplacements;
// All the nodes from root to the current node during traversing.
TVector<TIntermNode *> mPath;
// The current child of parent being traversed.
size_t mCurrentChildIndex;
// All the code blocks from the root to the current node's parent during traversal.
std::vector<ParentBlock> mParentBlockStack;
};
// Traverser parent class that tracks where a node is a destination of a write operation and so is
// required to be an l-value.
class TLValueTrackingTraverser : public TIntermTraverser
{
public:
TLValueTrackingTraverser(bool preVisit,
bool inVisit,
bool postVisit,
TSymbolTable *symbolTable);
~TLValueTrackingTraverser() override {}
void traverseBinary(TIntermBinary *node) final;
void traverseUnary(TIntermUnary *node) final;
void traverseAggregate(TIntermAggregate *node) final;
protected:
bool isLValueRequiredHere() const
{
return mOperatorRequiresLValue || mInFunctionCallOutParameter;
}
private:
// Track whether an l-value is required in the node that is currently being traversed by the
// surrounding operator.
// Use isLValueRequiredHere to check all conditions which require an l-value.
void setOperatorRequiresLValue(bool lValueRequired)
{
mOperatorRequiresLValue = lValueRequired;
}
bool operatorRequiresLValue() const { return mOperatorRequiresLValue; }
// Track whether an l-value is required inside a function call.
void setInFunctionCallOutParameter(bool inOutParameter);
bool isInFunctionCallOutParameter() const;
bool mOperatorRequiresLValue;
bool mInFunctionCallOutParameter;
};
} // namespace sh
#endif // COMPILER_TRANSLATOR_TREEUTIL_INTERMTRAVERSE_H_