diff options
Diffstat (limited to 'gfx/angle/checkout/src/compiler/translator/CallDAG.cpp')
| -rw-r--r-- | gfx/angle/checkout/src/compiler/translator/CallDAG.cpp | 316 |
1 files changed, 316 insertions, 0 deletions
diff --git a/gfx/angle/checkout/src/compiler/translator/CallDAG.cpp b/gfx/angle/checkout/src/compiler/translator/CallDAG.cpp new file mode 100644 index 0000000000..5d47518eba --- /dev/null +++ b/gfx/angle/checkout/src/compiler/translator/CallDAG.cpp @@ -0,0 +1,316 @@ +// +// 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. +// + +// CallDAG.h: Implements a call graph DAG of functions to be re-used accross +// analyses, allows to efficiently traverse the functions in topological +// order. + +#include "compiler/translator/CallDAG.h" + +#include "compiler/translator/Diagnostics.h" +#include "compiler/translator/SymbolTable.h" +#include "compiler/translator/tree_util/IntermTraverse.h" + +namespace sh +{ + +// The CallDAGCreator does all the processing required to create the CallDAG +// structure so that the latter contains only the necessary variables. +class CallDAG::CallDAGCreator : public TIntermTraverser +{ + public: + CallDAGCreator(TDiagnostics *diagnostics) + : TIntermTraverser(true, false, false), + mDiagnostics(diagnostics), + mCurrentFunction(nullptr), + mCurrentIndex(0) + {} + + InitResult assignIndices() + { + int skipped = 0; + for (auto &it : mFunctions) + { + // Skip unimplemented functions + if (it.second.definitionNode) + { + InitResult result = assignIndicesInternal(&it.second); + if (result != INITDAG_SUCCESS) + { + return result; + } + } + else + { + skipped++; + } + } + + ASSERT(mFunctions.size() == mCurrentIndex + skipped); + return INITDAG_SUCCESS; + } + + void fillDataStructures(std::vector<Record> *records, std::map<int, int> *idToIndex) + { + ASSERT(records->empty()); + ASSERT(idToIndex->empty()); + + records->resize(mCurrentIndex); + + for (auto &it : mFunctions) + { + CreatorFunctionData &data = it.second; + // Skip unimplemented functions + if (!data.definitionNode) + { + continue; + } + ASSERT(data.index < records->size()); + Record &record = (*records)[data.index]; + + record.node = data.definitionNode; + + record.callees.reserve(data.callees.size()); + for (auto &callee : data.callees) + { + record.callees.push_back(static_cast<int>(callee->index)); + } + + (*idToIndex)[it.first] = static_cast<int>(data.index); + } + } + + private: + struct CreatorFunctionData + { + CreatorFunctionData() + : definitionNode(nullptr), name(""), index(0), indexAssigned(false), visiting(false) + {} + + std::set<CreatorFunctionData *> callees; + TIntermFunctionDefinition *definitionNode; + ImmutableString name; + size_t index; + bool indexAssigned; + bool visiting; + }; + + bool visitFunctionDefinition(Visit visit, TIntermFunctionDefinition *node) override + { + // Create the record if need be and remember the definition node. + mCurrentFunction = &mFunctions[node->getFunction()->uniqueId().get()]; + // Name will be overwritten here. If we've already traversed the prototype of this function, + // it should have had the same name. + ASSERT(mCurrentFunction->name == "" || + mCurrentFunction->name == node->getFunction()->name()); + mCurrentFunction->name = node->getFunction()->name(); + mCurrentFunction->definitionNode = node; + + node->getBody()->traverse(this); + mCurrentFunction = nullptr; + return false; + } + + void visitFunctionPrototype(TIntermFunctionPrototype *node) override + { + ASSERT(mCurrentFunction == nullptr); + + // Function declaration, create an empty record. + auto &record = mFunctions[node->getFunction()->uniqueId().get()]; + record.name = node->getFunction()->name(); + } + + // Track functions called from another function. + bool visitAggregate(Visit visit, TIntermAggregate *node) override + { + if (node->getOp() == EOpCallFunctionInAST) + { + // Function call, add the callees + auto it = mFunctions.find(node->getFunction()->uniqueId().get()); + ASSERT(it != mFunctions.end()); + + // We might be traversing the initializer of a global variable. Even though function + // calls in global scope are forbidden by the parser, some subsequent AST + // transformations can add them to emulate particular features. + if (mCurrentFunction) + { + mCurrentFunction->callees.insert(&it->second); + } + } + return true; + } + + // Recursively assigns indices to a sub DAG + InitResult assignIndicesInternal(CreatorFunctionData *root) + { + // Iterative implementation of the index assignment algorithm. A recursive version + // would be prettier but since the CallDAG creation runs before the limiting of the + // call depth, we might get stack overflows (computation of the call depth uses the + // CallDAG). + + ASSERT(root); + + if (root->indexAssigned) + { + return INITDAG_SUCCESS; + } + + // If we didn't have to detect recursion, functionsToProcess could be a simple queue + // in which we add the function being processed's callees. However in order to detect + // recursion we need to know which functions we are currently visiting. For that reason + // functionsToProcess will look like a concatenation of segments of the form + // [F visiting = true, subset of F callees with visiting = false] and the following + // segment (if any) will be start with a callee of F. + // This way we can remember when we started visiting a function, to put visiting back + // to false. + TVector<CreatorFunctionData *> functionsToProcess; + functionsToProcess.push_back(root); + + InitResult result = INITDAG_SUCCESS; + + std::stringstream errorStream = sh::InitializeStream<std::stringstream>(); + + while (!functionsToProcess.empty()) + { + CreatorFunctionData *function = functionsToProcess.back(); + + if (function->visiting) + { + function->visiting = false; + function->index = mCurrentIndex++; + function->indexAssigned = true; + + functionsToProcess.pop_back(); + continue; + } + + if (!function->definitionNode) + { + errorStream << "Undefined function '" << function->name + << "()' used in the following call chain:"; + result = INITDAG_UNDEFINED; + break; + } + + if (function->indexAssigned) + { + functionsToProcess.pop_back(); + continue; + } + + function->visiting = true; + + for (auto callee : function->callees) + { + functionsToProcess.push_back(callee); + + // Check if the callee is already being visited after pushing it so that it appears + // in the chain printed in the info log. + if (callee->visiting) + { + errorStream << "Recursive function call in the following call chain:"; + result = INITDAG_RECURSION; + break; + } + } + + if (result != INITDAG_SUCCESS) + { + break; + } + } + + // The call chain is made of the function we were visiting when the error was detected. + if (result != INITDAG_SUCCESS) + { + bool first = true; + for (auto function : functionsToProcess) + { + if (function->visiting) + { + if (!first) + { + errorStream << " -> "; + } + errorStream << function->name << ")"; + first = false; + } + } + if (mDiagnostics) + { + std::string errorStr = errorStream.str(); + mDiagnostics->globalError(errorStr.c_str()); + } + } + + return result; + } + + TDiagnostics *mDiagnostics; + + std::map<int, CreatorFunctionData> mFunctions; + CreatorFunctionData *mCurrentFunction; + size_t mCurrentIndex; +}; + +// CallDAG + +CallDAG::CallDAG() {} + +CallDAG::~CallDAG() {} + +const size_t CallDAG::InvalidIndex = std::numeric_limits<size_t>::max(); + +size_t CallDAG::findIndex(const TSymbolUniqueId &id) const +{ + auto it = mFunctionIdToIndex.find(id.get()); + + if (it == mFunctionIdToIndex.end()) + { + return InvalidIndex; + } + else + { + return it->second; + } +} + +const CallDAG::Record &CallDAG::getRecordFromIndex(size_t index) const +{ + ASSERT(index != InvalidIndex && index < mRecords.size()); + return mRecords[index]; +} + +size_t CallDAG::size() const +{ + return mRecords.size(); +} + +void CallDAG::clear() +{ + mRecords.clear(); + mFunctionIdToIndex.clear(); +} + +CallDAG::InitResult CallDAG::init(TIntermNode *root, TDiagnostics *diagnostics) +{ + CallDAGCreator creator(diagnostics); + + // Creates the mapping of functions to callees + root->traverse(&creator); + + // Does the topological sort and detects recursions + InitResult result = creator.assignIndices(); + if (result != INITDAG_SUCCESS) + { + return result; + } + + creator.fillDataStructures(&mRecords, &mFunctionIdToIndex); + return INITDAG_SUCCESS; +} + +} // namespace sh |