diff options
Diffstat (limited to 'src/3rdparty/angle/src/compiler/translator/CallDAG.cpp')
-rw-r--r-- | src/3rdparty/angle/src/compiler/translator/CallDAG.cpp | 261 |
1 files changed, 157 insertions, 104 deletions
diff --git a/src/3rdparty/angle/src/compiler/translator/CallDAG.cpp b/src/3rdparty/angle/src/compiler/translator/CallDAG.cpp index 10f0eb937c..5f54e80898 100644 --- a/src/3rdparty/angle/src/compiler/translator/CallDAG.cpp +++ b/src/3rdparty/angle/src/compiler/translator/CallDAG.cpp @@ -9,16 +9,22 @@ // order. #include "compiler/translator/CallDAG.h" -#include "compiler/translator/InfoSink.h" + +#include "compiler/translator/Diagnostics.h" +#include "compiler/translator/IntermTraverse.h" +#include "compiler/translator/SymbolTable.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(TInfoSinkBase *info) + CallDAGCreator(TDiagnostics *diagnostics) : TIntermTraverser(true, false, true), - mCreationInfo(info), + mDiagnostics(diagnostics), mCurrentFunction(nullptr), mCurrentIndex(0) { @@ -35,7 +41,6 @@ class CallDAG::CallDAGCreator : public TIntermTraverser InitResult result = assignIndicesInternal(&it.second); if (result != INITDAG_SUCCESS) { - *mCreationInfo << "\n"; return result; } } @@ -44,6 +49,7 @@ class CallDAG::CallDAGCreator : public TIntermTraverser skipped++; } } + ASSERT(mFunctions.size() == mCurrentIndex + skipped); return INITDAG_SUCCESS; } @@ -75,147 +81,196 @@ class CallDAG::CallDAGCreator : public TIntermTraverser record.callees.push_back(static_cast<int>(callee->index)); } - (*idToIndex)[data.node->getFunctionId()] = static_cast<int>(data.index); + (*idToIndex)[data.node->getFunctionSymbolInfo()->getId().get()] = + static_cast<int>(data.index); } } private: - struct CreatorFunctionData { - CreatorFunctionData() - : node(nullptr), - index(0), - indexAssigned(false), - visiting(false) - { - } + CreatorFunctionData() : node(nullptr), index(0), indexAssigned(false), visiting(false) {} - std::set<CreatorFunctionData*> callees; - TIntermAggregate *node; + std::set<CreatorFunctionData *> callees; + TIntermFunctionDefinition *node; TString name; size_t index; bool indexAssigned; bool visiting; }; - // Aggregates the AST node for each function as well as the name of the functions called by it - bool visitAggregate(Visit visit, TIntermAggregate *node) override + bool visitFunctionDefinition(Visit visit, TIntermFunctionDefinition *node) override { - switch (node->getOp()) + // Create the record if need be and remember the node. + if (visit == PreVisit) { - case EOpPrototype: - if (visit == PreVisit) + auto it = mFunctions.find(node->getFunctionSymbolInfo()->getId().get()); + + if (it == mFunctions.end()) { - // Function declaration, create an empty record. - auto& record = mFunctions[node->getName()]; - record.name = node->getName(); + mCurrentFunction = &mFunctions[node->getFunctionSymbolInfo()->getId().get()]; + mCurrentFunction->name = node->getFunctionSymbolInfo()->getName(); } - break; - case EOpFunction: + else { - // Function definition, create the record if need be and remember the node. - if (visit == PreVisit) - { - auto it = mFunctions.find(node->getName()); + mCurrentFunction = &it->second; + ASSERT(mCurrentFunction->name == node->getFunctionSymbolInfo()->getName()); + } - if (it == mFunctions.end()) - { - mCurrentFunction = &mFunctions[node->getName()]; - } - else - { - mCurrentFunction = &it->second; - } + mCurrentFunction->node = node; + } + else if (visit == PostVisit) + { + mCurrentFunction = nullptr; + } + return true; + } - mCurrentFunction->node = node; - mCurrentFunction->name = node->getName(); + bool visitFunctionPrototype(Visit visit, TIntermFunctionPrototype *node) override + { + ASSERT(visit == PreVisit); + if (mCurrentFunction != nullptr) + { + return false; + } - } - else if (visit == PostVisit) - { - mCurrentFunction = nullptr; - } - break; - } - case EOpFunctionCall: + // Function declaration, create an empty record. + auto &record = mFunctions[node->getFunctionSymbolInfo()->getId().get()]; + record.name = node->getFunctionSymbolInfo()->getName(); + + // No need to traverse the parameters. + return false; + } + + // Aggregates the AST node for each function as well as the name of the functions called by it + bool visitAggregate(Visit visit, TIntermAggregate *node) override + { + if (visit == PreVisit && node->getOp() == EOpCallFunctionInAST) + { + // Function call, add the callees + auto it = mFunctions.find(node->getFunctionSymbolInfo()->getId().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) { - // Function call, add the callees - if (visit == PreVisit) - { - // Do not handle calls to builtin functions - if (node->isUserDefined()) - { - auto it = mFunctions.find(node->getName()); - ASSERT(it != mFunctions.end()); - - // We might be in a top-level function call to set a global variable - if (mCurrentFunction) - { - mCurrentFunction->callees.insert(&it->second); - } - } - } - break; + mCurrentFunction->callees.insert(&it->second); } - default: - break; } return true; } // Recursively assigns indices to a sub DAG - InitResult assignIndicesInternal(CreatorFunctionData *function) + InitResult assignIndicesInternal(CreatorFunctionData *root) { - ASSERT(function); + // 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). - if (!function->node) - { - *mCreationInfo << "Undefined function '" << function->name - << ")' used in the following call chain:"; - return INITDAG_UNDEFINED; - } + ASSERT(root); - if (function->indexAssigned) + if (root->indexAssigned) { return INITDAG_SUCCESS; } - if (function->visiting) + // 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; + + while (!functionsToProcess.empty()) { - if (mCreationInfo) + CreatorFunctionData *function = functionsToProcess.back(); + + if (function->visiting) + { + function->visiting = false; + function->index = mCurrentIndex++; + function->indexAssigned = true; + + functionsToProcess.pop_back(); + continue; + } + + if (!function->node) + { + 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) { - *mCreationInfo << "Recursive function call in the following call chain:" << function->name; + break; } - return INITDAG_RECURSION; } - function->visiting = true; - for (auto &callee : function->callees) + // The call chain is made of the function we were visiting when the error was detected. + if (result != INITDAG_SUCCESS) { - InitResult result = assignIndicesInternal(callee); - if (result != INITDAG_SUCCESS) + bool first = true; + for (auto function : functionsToProcess) { - // We know that there is an issue with the call chain in the AST, - // print the link of the chain we were processing. - if (mCreationInfo) + if (function->visiting) { - *mCreationInfo << " <- " << function->name << ")"; + if (!first) + { + errorStream << " -> "; + } + errorStream << function->name << ")"; + first = false; } - return result; + } + if (mDiagnostics) + { + std::string errorStr = errorStream.str(); + mDiagnostics->globalError(errorStr.c_str()); } } - function->index = mCurrentIndex++; - function->indexAssigned = true; - - function->visiting = false; - return INITDAG_SUCCESS; + return result; } - TInfoSinkBase *mCreationInfo; + TDiagnostics *mDiagnostics; - std::map<TString, CreatorFunctionData> mFunctions; + std::map<int, CreatorFunctionData> mFunctions; CreatorFunctionData *mCurrentFunction; size_t mCurrentIndex; }; @@ -232,13 +287,9 @@ CallDAG::~CallDAG() const size_t CallDAG::InvalidIndex = std::numeric_limits<size_t>::max(); -size_t CallDAG::findIndex(const TIntermAggregate *function) const +size_t CallDAG::findIndex(const TFunctionSymbolInfo *functionInfo) const { - TOperator op = function->getOp(); - ASSERT(op == EOpPrototype || op == EOpFunction || op == EOpFunctionCall); - UNUSED_ASSERTION_VARIABLE(op); - - auto it = mFunctionIdToIndex.find(function->getFunctionId()); + auto it = mFunctionIdToIndex.find(functionInfo->getId().get()); if (it == mFunctionIdToIndex.end()) { @@ -258,7 +309,7 @@ const CallDAG::Record &CallDAG::getRecordFromIndex(size_t index) const const CallDAG::Record &CallDAG::getRecord(const TIntermAggregate *function) const { - size_t index = findIndex(function); + size_t index = findIndex(function->getFunctionSymbolInfo()); ASSERT(index != InvalidIndex && index < mRecords.size()); return mRecords[index]; } @@ -274,9 +325,9 @@ void CallDAG::clear() mFunctionIdToIndex.clear(); } -CallDAG::InitResult CallDAG::init(TIntermNode *root, TInfoSinkBase *info) +CallDAG::InitResult CallDAG::init(TIntermNode *root, TDiagnostics *diagnostics) { - CallDAGCreator creator(info); + CallDAGCreator creator(diagnostics); // Creates the mapping of functions to callees root->traverse(&creator); @@ -291,3 +342,5 @@ CallDAG::InitResult CallDAG::init(TIntermNode *root, TInfoSinkBase *info) creator.fillDataStructures(&mRecords, &mFunctionIdToIndex); return INITDAG_SUCCESS; } + +} // namespace sh |