Source code
Revision control
Copy as Markdown
Other Tools
//
// 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