tor-browser

CallDAG.cpp (9702B)

---

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