1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/angle/src/compiler/DetectCallDepth.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,185 @@
1.4 +//
1.5 +// Copyright (c) 2002-2011 The ANGLE Project Authors. All rights reserved.
1.6 +// Use of this source code is governed by a BSD-style license that can be
1.7 +// found in the LICENSE file.
1.8 +//
1.9 +
1.10 +#include "compiler/DetectCallDepth.h"
1.11 +#include "compiler/InfoSink.h"
1.12 +
1.13 +DetectCallDepth::FunctionNode::FunctionNode(const TString& fname)
1.14 + : name(fname),
1.15 + visit(PreVisit)
1.16 +{
1.17 +}
1.18 +
1.19 +const TString& DetectCallDepth::FunctionNode::getName() const
1.20 +{
1.21 + return name;
1.22 +}
1.23 +
1.24 +void DetectCallDepth::FunctionNode::addCallee(
1.25 + DetectCallDepth::FunctionNode* callee)
1.26 +{
1.27 + for (size_t i = 0; i < callees.size(); ++i) {
1.28 + if (callees[i] == callee)
1.29 + return;
1.30 + }
1.31 + callees.push_back(callee);
1.32 +}
1.33 +
1.34 +int DetectCallDepth::FunctionNode::detectCallDepth(DetectCallDepth* detectCallDepth, int depth)
1.35 +{
1.36 + ASSERT(visit == PreVisit);
1.37 + ASSERT(detectCallDepth);
1.38 +
1.39 + int maxDepth = depth;
1.40 + visit = InVisit;
1.41 + for (size_t i = 0; i < callees.size(); ++i) {
1.42 + switch (callees[i]->visit) {
1.43 + case InVisit:
1.44 + // cycle detected, i.e., recursion detected.
1.45 + return kInfiniteCallDepth;
1.46 + case PostVisit:
1.47 + break;
1.48 + case PreVisit: {
1.49 + // Check before we recurse so we don't go too depth
1.50 + if (detectCallDepth->checkExceedsMaxDepth(depth))
1.51 + return depth;
1.52 + int callDepth = callees[i]->detectCallDepth(detectCallDepth, depth + 1);
1.53 + // Check after we recurse so we can exit immediately and provide info.
1.54 + if (detectCallDepth->checkExceedsMaxDepth(callDepth)) {
1.55 + detectCallDepth->getInfoSink().info << "<-" << callees[i]->getName();
1.56 + return callDepth;
1.57 + }
1.58 + maxDepth = std::max(callDepth, maxDepth);
1.59 + break;
1.60 + }
1.61 + default:
1.62 + UNREACHABLE();
1.63 + break;
1.64 + }
1.65 + }
1.66 + visit = PostVisit;
1.67 + return maxDepth;
1.68 +}
1.69 +
1.70 +void DetectCallDepth::FunctionNode::reset()
1.71 +{
1.72 + visit = PreVisit;
1.73 +}
1.74 +
1.75 +DetectCallDepth::DetectCallDepth(TInfoSink& infoSink, bool limitCallStackDepth, int maxCallStackDepth)
1.76 + : TIntermTraverser(true, false, true, false),
1.77 + currentFunction(NULL),
1.78 + infoSink(infoSink),
1.79 + maxDepth(limitCallStackDepth ? maxCallStackDepth : FunctionNode::kInfiniteCallDepth)
1.80 +{
1.81 +}
1.82 +
1.83 +DetectCallDepth::~DetectCallDepth()
1.84 +{
1.85 + for (size_t i = 0; i < functions.size(); ++i)
1.86 + delete functions[i];
1.87 +}
1.88 +
1.89 +bool DetectCallDepth::visitAggregate(Visit visit, TIntermAggregate* node)
1.90 +{
1.91 + switch (node->getOp())
1.92 + {
1.93 + case EOpPrototype:
1.94 + // Function declaration.
1.95 + // Don't add FunctionNode here because node->getName() is the
1.96 + // unmangled function name.
1.97 + break;
1.98 + case EOpFunction: {
1.99 + // Function definition.
1.100 + if (visit == PreVisit) {
1.101 + currentFunction = findFunctionByName(node->getName());
1.102 + if (currentFunction == NULL) {
1.103 + currentFunction = new FunctionNode(node->getName());
1.104 + functions.push_back(currentFunction);
1.105 + }
1.106 + } else if (visit == PostVisit) {
1.107 + currentFunction = NULL;
1.108 + }
1.109 + break;
1.110 + }
1.111 + case EOpFunctionCall: {
1.112 + // Function call.
1.113 + if (visit == PreVisit) {
1.114 + FunctionNode* func = findFunctionByName(node->getName());
1.115 + if (func == NULL) {
1.116 + func = new FunctionNode(node->getName());
1.117 + functions.push_back(func);
1.118 + }
1.119 + if (currentFunction)
1.120 + currentFunction->addCallee(func);
1.121 + }
1.122 + break;
1.123 + }
1.124 + default:
1.125 + break;
1.126 + }
1.127 + return true;
1.128 +}
1.129 +
1.130 +bool DetectCallDepth::checkExceedsMaxDepth(int depth)
1.131 +{
1.132 + return depth >= maxDepth;
1.133 +}
1.134 +
1.135 +void DetectCallDepth::resetFunctionNodes()
1.136 +{
1.137 + for (size_t i = 0; i < functions.size(); ++i) {
1.138 + functions[i]->reset();
1.139 + }
1.140 +}
1.141 +
1.142 +DetectCallDepth::ErrorCode DetectCallDepth::detectCallDepthForFunction(FunctionNode* func)
1.143 +{
1.144 + currentFunction = NULL;
1.145 + resetFunctionNodes();
1.146 +
1.147 + int maxCallDepth = func->detectCallDepth(this, 1);
1.148 +
1.149 + if (maxCallDepth == FunctionNode::kInfiniteCallDepth)
1.150 + return kErrorRecursion;
1.151 +
1.152 + if (maxCallDepth >= maxDepth)
1.153 + return kErrorMaxDepthExceeded;
1.154 +
1.155 + return kErrorNone;
1.156 +}
1.157 +
1.158 +DetectCallDepth::ErrorCode DetectCallDepth::detectCallDepth()
1.159 +{
1.160 + if (maxDepth != FunctionNode::kInfiniteCallDepth) {
1.161 + // Check all functions because the driver may fail on them
1.162 + // TODO: Before detectingRecursion, strip unused functions.
1.163 + for (size_t i = 0; i < functions.size(); ++i) {
1.164 + ErrorCode error = detectCallDepthForFunction(functions[i]);
1.165 + if (error != kErrorNone)
1.166 + return error;
1.167 + }
1.168 + } else {
1.169 + FunctionNode* main = findFunctionByName("main(");
1.170 + if (main == NULL)
1.171 + return kErrorMissingMain;
1.172 +
1.173 + return detectCallDepthForFunction(main);
1.174 + }
1.175 +
1.176 + return kErrorNone;
1.177 +}
1.178 +
1.179 +DetectCallDepth::FunctionNode* DetectCallDepth::findFunctionByName(
1.180 + const TString& name)
1.181 +{
1.182 + for (size_t i = 0; i < functions.size(); ++i) {
1.183 + if (functions[i]->getName() == name)
1.184 + return functions[i];
1.185 + }
1.186 + return NULL;
1.187 +}
1.188 +
