src/compiler/translator/CallDAG.cpp - angle/angle.git - Git at Google

 //
 // 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/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
	//
	// 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/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