Bug 673075 - import ANGLE r711 - r=upstream
authorBenoit Jacob <bjacob@mozilla.com>
Mon, 15 Aug 2011 15:54:25 -0400
changeset 75304 7a92e6b3093ff71524aa9b3f165aafc9cc00aa08
parent 75303 ddf7263c56d7f77bdfd0ed3747052f269d007edf
child 75305 f597467fac5e2a1f455994b20625b5bb9e4f2eb3
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
reviewersupstream
bugs673075
milestone8.0a1
Bug 673075 - import ANGLE r711 - r=upstream This lets ANGLE reject shaders that have recursive functions.
gfx/angle/Makefile.in
gfx/angle/README.mozilla
gfx/angle/src/compiler/Compiler.cpp
gfx/angle/src/compiler/DetectRecursion.cpp
gfx/angle/src/compiler/DetectRecursion.h
gfx/angle/src/compiler/ShHandle.h
gfx/angle/src/libEGL/Makefile.in
gfx/angle/src/libGLESv2/Makefile.in
--- a/gfx/angle/Makefile.in
+++ b/gfx/angle/Makefile.in
@@ -57,16 +57,17 @@ EXPORTS_angle = \
 LOCAL_INCLUDES += -I$(srcdir)/include -I$(srcdir)/src
 
 VPATH += $(srcdir)/src
 VPATH += $(srcdir)/src/compiler
 VPATH += $(srcdir)/src/compiler/preprocessor
 
 CPPSRCS = \
 	Compiler.cpp \
+        DetectRecursion.cpp \
         InfoSink.cpp \
         Initialize.cpp \
         InitializeDll.cpp \
         Intermediate.cpp \
         intermOut.cpp \
         IntermTraverse.cpp \
         MozAngleLink.cpp \
         parseConst.cpp \
--- a/gfx/angle/README.mozilla
+++ b/gfx/angle/README.mozilla
@@ -10,16 +10,17 @@ In this order:
   angle-intrinsic-msvc2005.patch - work around a MSVC 2005 compile error
   angle-amap-arev-fix.patch - plain bug fix, this is ANGLE r699
   angle-r702.patch - this is ANGLE r702
   angle-limit-identifiers-to-250-chars.patch - see bug 675625
   angle-r712.patch - this is ANGLE r712
   angle-win64.patch - Win64 support. This is ANGLE r697
   angle-r707.patch - this is ANGLE r707 for Win64 bug fix
   angle-r719.patch - this is ANGLE r719
+  angle-r711.patch - this is ANGLE r711
 
 In addition to these patches, the Makefile.in files are ours, they're not present in upsteam ANGLE.
 
 == How to update this ANGLE copy ==
 
 1. Unapply patches
 2. Apply diff with new ANGLE version
 3. Reapply patches.
--- a/gfx/angle/src/compiler/Compiler.cpp
+++ b/gfx/angle/src/compiler/Compiler.cpp
@@ -1,14 +1,15 @@
 //
 // Copyright (c) 2002-2010 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.
 //
 
+#include "compiler/DetectRecursion.h"
 #include "compiler/Initialize.h"
 #include "compiler/ParseHelper.h"
 #include "compiler/ShHandle.h"
 #include "compiler/ValidateLimitations.h"
 #include "compiler/MapLongVariableNames.h"
 
 namespace {
 bool InitializeSymbolTable(
@@ -140,23 +141,26 @@ bool TCompiler::compile(const char* cons
     // Parse shader.
     bool success =
         (PaParseStrings(numStrings - firstSource, &shaderStrings[firstSource], NULL, &parseContext) == 0) &&
         (parseContext.treeRoot != NULL);
     if (success) {
         TIntermNode* root = parseContext.treeRoot;
         success = intermediate.postProcess(root);
 
+        if (success)
+            success = detectRecursion(root);
+
         if (success && (compileOptions & SH_VALIDATE_LOOP_INDEXING))
             success = validateLimitations(root);
 
         // Call mapLongVariableNames() before collectAttribsUniforms() so in
         // collectAttribsUniforms() we already have the mapped symbol names and
         // we could composite mapped and original variable names.
-        if (compileOptions & SH_MAP_LONG_VARIABLE_NAMES)
+        if (success && (compileOptions & SH_MAP_LONG_VARIABLE_NAMES))
             mapLongVariableNames(root);
 
         if (success && (compileOptions & SH_ATTRIBUTES_UNIFORMS))
             collectAttribsUniforms(root);
 
         if (success && (compileOptions & SH_INTERMEDIATE_TREE))
             intermediate.outputTree(root);
 
@@ -188,16 +192,35 @@ void TCompiler::clearResults()
     infoSink.info.erase();
     infoSink.obj.erase();
     infoSink.debug.erase();
 
     attribs.clear();
     uniforms.clear();
 }
 
+bool TCompiler::detectRecursion(TIntermNode* root)
+{
+    DetectRecursion detect;
+    root->traverse(&detect);
+    switch (detect.detectRecursion()) {
+        case DetectRecursion::kErrorNone:
+            return true;
+        case DetectRecursion::kErrorMissingMain:
+            infoSink.info.message(EPrefixError, "Missing main()");
+            return false;
+        case DetectRecursion::kErrorRecursion:
+            infoSink.info.message(EPrefixError, "Function recursion detected");
+            return false;
+        default:
+            UNREACHABLE();
+            return false;
+    }
+}
+
 bool TCompiler::validateLimitations(TIntermNode* root) {
     ValidateLimitations validate(shaderType, infoSink.info);
     root->traverse(&validate);
     return validate.numErrors() == 0;
 }
 
 void TCompiler::collectAttribsUniforms(TIntermNode* root)
 {
new file mode 100644
--- /dev/null
+++ b/gfx/angle/src/compiler/DetectRecursion.cpp
@@ -0,0 +1,158 @@
+//
+// Copyright (c) 2002-2011 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.
+//
+
+#include "compiler/DetectRecursion.h"
+
+DetectRecursion::FunctionNode::FunctionNode(const TString& fname)
+    : name(fname),
+      visit(PreVisit)
+{
+}
+
+const TString& DetectRecursion::FunctionNode::getName() const
+{
+    return name;
+}
+
+void DetectRecursion::FunctionNode::addCallee(
+    DetectRecursion::FunctionNode* callee)
+{
+    for (size_t i = 0; i < callees.size(); ++i) {
+        if (callees[i] == callee)
+            return;
+    }
+    callees.push_back(callee);
+}
+
+bool DetectRecursion::FunctionNode::detectRecursion()
+{
+    ASSERT(visit == PreVisit);
+    visit = InVisit;
+    for (size_t i = 0; i < callees.size(); ++i) {
+        switch (callees[i]->visit) {
+            case InVisit:
+                // cycle detected, i.e., recursion detected.
+                return true;
+            case PostVisit:
+                break;
+            case PreVisit: {
+                bool recursion = callees[i]->detectRecursion();
+                if (recursion)
+                    return true;
+                break;
+            }
+            default:
+                UNREACHABLE();
+                break;
+        }
+    }
+    visit = PostVisit;
+    return false;
+}
+
+DetectRecursion::DetectRecursion()
+    : currentFunction(NULL)
+{
+}
+
+DetectRecursion::~DetectRecursion()
+{
+    for (int i = 0; i < functions.size(); ++i)
+        delete functions[i];
+}
+
+void DetectRecursion::visitSymbol(TIntermSymbol*)
+{
+}
+
+void DetectRecursion::visitConstantUnion(TIntermConstantUnion*)
+{
+}
+
+bool DetectRecursion::visitBinary(Visit, TIntermBinary*)
+{
+    return true;
+}
+
+bool DetectRecursion::visitUnary(Visit, TIntermUnary*)
+{
+    return true;
+}
+
+bool DetectRecursion::visitSelection(Visit, TIntermSelection*)
+{
+    return true;
+}
+
+bool DetectRecursion::visitAggregate(Visit visit, TIntermAggregate* node)
+{
+    switch (node->getOp())
+    {
+        case EOpPrototype:
+            // Function declaration.
+            // Don't add FunctionNode here because node->getName() is the
+            // unmangled function name.
+            break;
+        case EOpFunction: {
+            // Function definition.
+            if (visit == PreVisit) {
+                currentFunction = findFunctionByName(node->getName());
+                if (currentFunction == NULL) {
+                    currentFunction = new FunctionNode(node->getName());
+                    functions.push_back(currentFunction);
+                }
+            }
+            break;
+        }
+        case EOpFunctionCall: {
+            // Function call.
+            if (visit == PreVisit) {
+                ASSERT(currentFunction != NULL);
+                FunctionNode* func = findFunctionByName(node->getName());
+                if (func == NULL) {
+                    func = new FunctionNode(node->getName());
+                    functions.push_back(func);
+                }
+                currentFunction->addCallee(func);
+            }
+            break;
+        }
+        default:
+            break;
+    }
+    return true;
+}
+
+bool DetectRecursion::visitLoop(Visit, TIntermLoop*)
+{
+    return true;
+}
+
+bool DetectRecursion::visitBranch(Visit, TIntermBranch*)
+{
+    return true;
+}
+
+DetectRecursion::ErrorCode DetectRecursion::detectRecursion()
+{
+    FunctionNode* main = findFunctionByName("main(");
+    if (main == NULL)
+        return kErrorMissingMain;
+    if (main->detectRecursion())
+        return kErrorRecursion;
+    return kErrorNone;
+}
+
+DetectRecursion::FunctionNode* DetectRecursion::findFunctionByName(
+    const TString& name)
+{
+    for (size_t i = 0; i < functions.size(); ++i) {
+        if (functions[i]->getName() == name)
+            return functions[i];
+    }
+    return NULL;
+}
+
new file mode 100644
--- /dev/null
+++ b/gfx/angle/src/compiler/DetectRecursion.h
@@ -0,0 +1,67 @@
+//
+// Copyright (c) 2002-2011 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.
+//
+
+#ifndef COMPILER_DETECT_RECURSION_H_
+#define COMPILER_DETECT_RECURSION_H_
+
+#include "GLSLANG/ShaderLang.h"
+
+#include "compiler/intermediate.h"
+#include "compiler/VariableInfo.h"
+
+// Traverses intermediate tree to detect function recursion.
+class DetectRecursion : public TIntermTraverser {
+public:
+    enum ErrorCode {
+        kErrorMissingMain,
+        kErrorRecursion,
+        kErrorNone
+    };
+
+    DetectRecursion();
+    ~DetectRecursion();
+
+    virtual void visitSymbol(TIntermSymbol*);
+    virtual void visitConstantUnion(TIntermConstantUnion*);
+    virtual bool visitBinary(Visit, TIntermBinary*);
+    virtual bool visitUnary(Visit, TIntermUnary*);
+    virtual bool visitSelection(Visit, TIntermSelection*);
+    virtual bool visitAggregate(Visit, TIntermAggregate*);
+    virtual bool visitLoop(Visit, TIntermLoop*);
+    virtual bool visitBranch(Visit, TIntermBranch*);
+
+    ErrorCode detectRecursion();
+
+private:
+    class FunctionNode {
+    public:
+        FunctionNode(const TString& fname);
+
+        const TString& getName() const;
+
+        // If a function is already in the callee list, this becomes a no-op.
+        void addCallee(FunctionNode* callee);
+
+        // Return true if recursive function calls are detected.
+        bool detectRecursion();
+
+    private:
+        // mangled function name is unique.
+        TString name;
+
+        // functions that are directly called by this function.
+        TVector<FunctionNode*> callees;
+
+        Visit visit;
+    };
+
+    FunctionNode* findFunctionByName(const TString& name);
+
+    TVector<FunctionNode*> functions;
+    FunctionNode* currentFunction;
+};
+
+#endif  // COMPILER_DETECT_RECURSION_H_
--- a/gfx/angle/src/compiler/ShHandle.h
+++ b/gfx/angle/src/compiler/ShHandle.h
@@ -61,16 +61,18 @@ public:
 
 protected:
     ShShaderType getShaderType() const { return shaderType; }
     ShShaderSpec getShaderSpec() const { return shaderSpec; }
     // Initialize symbol-table with built-in symbols.
     bool InitBuiltInSymbolTable(const ShBuiltInResources& resources);
     // Clears the results from the previous compilation.
     void clearResults();
+    // Return true if function recursion is detected.
+    bool detectRecursion(TIntermNode* root);
     // Returns true if the given shader does not exceed the minimum
     // functionality mandated in GLSL 1.0 spec Appendix A.
     bool validateLimitations(TIntermNode* root);
     // Collect info for all attribs and uniforms.
     void collectAttribsUniforms(TIntermNode* root);
     // Map long variable names into shorter ones.
     void mapLongVariableNames(TIntermNode* root);
     // Translate to object code.
--- a/gfx/angle/src/libEGL/Makefile.in
+++ b/gfx/angle/src/libEGL/Makefile.in
@@ -71,16 +71,17 @@ VPATH += $(srcdir)/.. \
   $(srcdir)/../compiler/preprocessor \
   $(srcdir)/../common \
   $(NULL)
 
 # Translator/compiler first
 
 CPPSRCS = \
   Compiler.cpp \
+  DetectRecursion.cpp \
   InfoSink.cpp \
   Initialize.cpp \
   InitializeDll.cpp \
   Intermediate.cpp \
   intermOut.cpp \
   IntermTraverse.cpp \
   MozAngleLink.cpp \
   parseConst.cpp \
--- a/gfx/angle/src/libGLESv2/Makefile.in
+++ b/gfx/angle/src/libGLESv2/Makefile.in
@@ -71,16 +71,17 @@ VPATH += $(srcdir)/..
 VPATH += $(srcdir)/../compiler
 VPATH += $(srcdir)/../compiler/preprocessor
 VPATH += $(srcdir)/../common
 
 # Translator/compiler first
 
 CPPSRCS = \
 	Compiler.cpp \
+        DetectRecursion.cpp \
         InfoSink.cpp \
         Initialize.cpp \
         InitializeDll.cpp \
         Intermediate.cpp \
         intermOut.cpp \
         IntermTraverse.cpp \
         MozAngleLink.cpp \
         parseConst.cpp \