summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/angle/src/compiler/translator/CallDAG.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/angle/src/compiler/translator/CallDAG.cpp')
-rw-r--r--src/3rdparty/angle/src/compiler/translator/CallDAG.cpp346
1 files changed, 0 insertions, 346 deletions
diff --git a/src/3rdparty/angle/src/compiler/translator/CallDAG.cpp b/src/3rdparty/angle/src/compiler/translator/CallDAG.cpp
deleted file mode 100644
index 5f54e80898..0000000000
--- a/src/3rdparty/angle/src/compiler/translator/CallDAG.cpp
+++ /dev/null
@@ -1,346 +0,0 @@
-//
-// Copyright (c) 2002-2015 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/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(TDiagnostics *diagnostics)
- : TIntermTraverser(true, false, true),
- mDiagnostics(diagnostics),
- mCurrentFunction(nullptr),
- mCurrentIndex(0)
- {
- }
-
- InitResult assignIndices()
- {
- int skipped = 0;
- for (auto &it : mFunctions)
- {
- // Skip unimplemented functions
- if (it.second.node)
- {
- 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.node)
- {
- continue;
- }
- ASSERT(data.index < records->size());
- Record &record = (*records)[data.index];
-
- record.name = data.name.data();
- record.node = data.node;
-
- record.callees.reserve(data.callees.size());
- for (auto &callee : data.callees)
- {
- record.callees.push_back(static_cast<int>(callee->index));
- }
-
- (*idToIndex)[data.node->getFunctionSymbolInfo()->getId().get()] =
- static_cast<int>(data.index);
- }
- }
-
- private:
- struct CreatorFunctionData
- {
- CreatorFunctionData() : node(nullptr), index(0), indexAssigned(false), visiting(false) {}
-
- std::set<CreatorFunctionData *> callees;
- TIntermFunctionDefinition *node;
- TString name;
- size_t index;
- bool indexAssigned;
- bool visiting;
- };
-
- bool visitFunctionDefinition(Visit visit, TIntermFunctionDefinition *node) override
- {
- // Create the record if need be and remember the node.
- if (visit == PreVisit)
- {
- auto it = mFunctions.find(node->getFunctionSymbolInfo()->getId().get());
-
- if (it == mFunctions.end())
- {
- mCurrentFunction = &mFunctions[node->getFunctionSymbolInfo()->getId().get()];
- mCurrentFunction->name = node->getFunctionSymbolInfo()->getName();
- }
- else
- {
- mCurrentFunction = &it->second;
- ASSERT(mCurrentFunction->name == node->getFunctionSymbolInfo()->getName());
- }
-
- mCurrentFunction->node = node;
- }
- else if (visit == PostVisit)
- {
- mCurrentFunction = nullptr;
- }
- return true;
- }
-
- bool visitFunctionPrototype(Visit visit, TIntermFunctionPrototype *node) override
- {
- ASSERT(visit == PreVisit);
- if (mCurrentFunction != nullptr)
- {
- return false;
- }
-
- // 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)
- {
- 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;
-
- 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->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)
- {
- 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 TFunctionSymbolInfo *functionInfo) const
-{
- auto it = mFunctionIdToIndex.find(functionInfo->getId().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];
-}
-
-const CallDAG::Record &CallDAG::getRecord(const TIntermAggregate *function) const
-{
- size_t index = findIndex(function->getFunctionSymbolInfo());
- 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-06 14:51:21 +0000