Implemented a CallDAG to allow for more AST analysis
The CallDAG preprocesses the AST to construct a DAG of
functions that can be used for several analyses.
Use it to implement check for recursion and max call
depth. It will also be used to limit the usage of
[[flatten]] and [[unroll]].
BUG=angleproject:937
BUG=395048
Change-Id: I8578703f2d49513f315aecccbcff34914562e4ff
Reviewed-on: https://chromium-review.googlesource.com/263774
Reviewed-by: Jamie Madill <jmadill@chromium.org>
Reviewed-by: Nicolas Capens <capn@chromium.org>
Reviewed-by: Corentin Wallez <cwallez@chromium.org>
Tested-by: Corentin Wallez <cwallez@chromium.org>
diff --git a/src/compiler/translator/Compiler.cpp b/src/compiler/translator/Compiler.cpp
index 534861c..8c5e50f 100644
--- a/src/compiler/translator/Compiler.cpp
+++ b/src/compiler/translator/Compiler.cpp
@@ -5,7 +5,7 @@
//
#include "compiler/translator/Compiler.h"
-#include "compiler/translator/DetectCallDepth.h"
+#include "compiler/translator/CallDAG.h"
#include "compiler/translator/ForLoopUnroll.h"
#include "compiler/translator/Initialize.h"
#include "compiler/translator/InitializeParseContext.h"
@@ -231,8 +231,20 @@
if (success && (compileOptions & SH_LIMIT_EXPRESSION_COMPLEXITY))
success = limitExpressionComplexity(root);
+ // Create the function DAG and check there is no recursion
if (success)
- success = detectCallDepth(root, infoSink, (compileOptions & SH_LIMIT_CALL_STACK_DEPTH) != 0);
+ success = initCallDag(root);
+
+ if (success && (compileOptions & SH_LIMIT_CALL_STACK_DEPTH))
+ success = checkCallDepth();
+
+ // Checks which functions are used and if "main" exists
+ if (success)
+ {
+ functionMetadata.clear();
+ functionMetadata.resize(mCallDag.size());
+ success = tagUsedFunctions();
+ }
if (success && shaderVersion == 300 && shaderType == GL_FRAGMENT_SHADER)
success = validateOutputs(root);
@@ -456,29 +468,107 @@
mSourcePath = NULL;
}
-bool TCompiler::detectCallDepth(TIntermNode* inputRoot, TInfoSink& inputInfoSink, bool limitCallStackDepth)
+bool TCompiler::initCallDag(TIntermNode *root)
{
- DetectCallDepth detect(inputInfoSink, limitCallStackDepth, maxCallStackDepth);
- inputRoot->traverse(&detect);
- switch (detect.detectCallDepth())
+ mCallDag.clear();
+
+ switch (mCallDag.init(root, &infoSink.info))
{
- case DetectCallDepth::kErrorNone:
+ case CallDAG::INITDAG_SUCCESS:
return true;
- case DetectCallDepth::kErrorMissingMain:
- inputInfoSink.info.prefix(EPrefixError);
- inputInfoSink.info << "Missing main()";
+ case CallDAG::INITDAG_RECURSION:
+ infoSink.info.prefix(EPrefixError);
+ infoSink.info << "Function recursion detected";
return false;
- case DetectCallDepth::kErrorRecursion:
- inputInfoSink.info.prefix(EPrefixError);
- inputInfoSink.info << "Function recursion detected";
+ case CallDAG::INITDAG_UNDEFINED:
+ infoSink.info.prefix(EPrefixError);
+ infoSink.info << "Unimplemented function detected";
return false;
- case DetectCallDepth::kErrorMaxDepthExceeded:
- inputInfoSink.info.prefix(EPrefixError);
- inputInfoSink.info << "Function call stack too deep";
- return false;
- default:
- UNREACHABLE();
- return false;
+ }
+
+ UNREACHABLE();
+ return true;
+}
+
+bool TCompiler::checkCallDepth()
+{
+ std::vector<int> depths(mCallDag.size());
+
+ for (size_t i = 0; i < mCallDag.size(); i++)
+ {
+ int depth = 0;
+ auto &record = mCallDag.getRecordFromIndex(i);
+
+ for (auto &calleeIndex : record.callees)
+ {
+ depth = std::max(depth, depths[calleeIndex] + 1);
+ }
+
+ depths[i] = depth;
+
+ if (depth >= maxCallStackDepth)
+ {
+ // Trace back the function chain to have a meaningful info log.
+ infoSink.info.prefix(EPrefixError);
+ infoSink.info << "Call stack too deep (larger than " << maxCallStackDepth
+ << ") with the following call chain: " << record.name;
+
+ int currentFunction = i;
+ int currentDepth = depth;
+
+ while (currentFunction != -1)
+ {
+ infoSink.info << " -> " << mCallDag.getRecordFromIndex(currentFunction).name;
+
+ int nextFunction = -1;
+ for (auto& calleeIndex : mCallDag.getRecordFromIndex(currentFunction).callees)
+ {
+ if (depths[calleeIndex] == currentDepth - 1)
+ {
+ currentDepth--;
+ nextFunction = calleeIndex;
+ }
+ }
+
+ currentFunction = nextFunction;
+ }
+
+ return false;
+ }
+ }
+
+ return true;
+}
+
+bool TCompiler::tagUsedFunctions()
+{
+ // Search from main, starting from the end of the DAG as it usually is the root.
+ for (int i = mCallDag.size(); i-- > 0;)
+ {
+ if (mCallDag.getRecordFromIndex(i).name == "main(")
+ {
+ internalTagUsedFunction(i);
+ return true;
+ }
+ }
+
+ infoSink.info.prefix(EPrefixError);
+ infoSink.info << "Missing main()";
+ return false;
+}
+
+void TCompiler::internalTagUsedFunction(size_t index)
+{
+ if (functionMetadata[index].used)
+ {
+ return;
+ }
+
+ functionMetadata[index].used = true;
+
+ for (int calleeIndex : mCallDag.getRecordFromIndex(index).callees)
+ {
+ internalTagUsedFunction(calleeIndex);
}
}