Recognize backwards dependencies in GLSL loops

Assignments at the end of a loop may get used by references earlier in
the same loop and should not be removed.

The added testcase also triggers some other bugs which will be fixed
over the next few commits.

diff --git a/source/glsl/optimize.cpp b/source/glsl/optimize.cpp
index 0139ec5fbec94d4f1c47493549914d8977b2af8e..b1201e9fb84cec84c8a7236121963f982cfa43cb 100644 (file)
--- a/source/glsl/optimize.cpp
+++ b/source/glsl/optimize.cpp
@@ -1056,7 +1056,8 @@ UnusedVariableRemover::UnusedVariableRemover():
        assignment_target(false),
        r_side_effects(false),
        in_struct(false),
        assignment_target(false),
        r_side_effects(false),
        in_struct(false),

-       composite_reference(false)
+       composite_reference(false),
+       in_loop(0)

 { }
 
 bool UnusedVariableRemover::apply(Stage &s)
 { }
 
 bool UnusedVariableRemover::apply(Stage &s)


@@ -1100,6 +1101,7 @@ void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &n
        var_info.referenced = true;
        if(!assignment_target)
        {
        var_info.referenced = true;
        if(!assignment_target)
        {

+               bool loop_external = false;

                for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
                {
                        bool covered = true;
                for(vector<AssignmentInfo *>::const_iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
                {
                        bool covered = true;


@@ -1123,9 +1125,17 @@ void UnusedVariableRemover::referenced(const Assignment::Target &target, Node &n
                                else
                                        covered = ((*i)->target.chain[j]==target.chain[j]);
                        }
                                else
                                        covered = ((*i)->target.chain[j]==target.chain[j]);
                        }

+

                        if(covered)
                        if(covered)

+                       {

                                (*i)->used_by.push_back(&node);
                                (*i)->used_by.push_back(&node);

+                               if((*i)->in_loop<in_loop)
+                                       loop_external = true;
+                       }

                }
                }

+
+               if(loop_external)
+                       loop_ext_refs.push_back(&node);

        }
 }
 
        }
 }
 


@@ -1247,6 +1257,7 @@ void UnusedVariableRemover::record_assignment(const Assignment::Target &target,
        AssignmentInfo &assign_info = assignments.back();
        assign_info.node = &node;
        assign_info.target = target;
        AssignmentInfo &assign_info = assignments.back();
        assign_info.node = &node;
        assign_info.target = target;

+       assign_info.in_loop = in_loop;

 
        /* An assignment to the target hides any assignments to the same target or
        its subfields. */
 
        /* An assignment to the target hides any assignments to the same target or
        its subfields. */


@@ -1378,7 +1389,18 @@ void UnusedVariableRemover::visit(Conditional &cond)
 void UnusedVariableRemover::visit(Iteration &iter)
 {
        BlockVariableMap saved_vars = variables;
 void UnusedVariableRemover::visit(Iteration &iter)
 {
        BlockVariableMap saved_vars = variables;

-       TraversingVisitor::visit(iter);
+       vector<Node *> saved_refs;
+       swap(loop_ext_refs, saved_refs);
+       {
+               SetForScope<unsigned> set_loop(in_loop, in_loop+1);
+               TraversingVisitor::visit(iter);
+       }
+       swap(loop_ext_refs, saved_refs);
+
+       /* Visit the external references of the loop again to record assignments
+       done in the loop as used. */
+       for(vector<Node *>::const_iterator i=saved_refs.begin(); i!=saved_refs.end(); ++i)
+               (*i)->visit(*this);

 
        /* Merge assignments from the iteration, without clearing previous state.
        Further analysis is needed to determine which parts of the iteration body
 
        /* Merge assignments from the iteration, without clearing previous state.
        Further analysis is needed to determine which parts of the iteration body

diff --git a/source/glsl/optimize.h b/source/glsl/optimize.h
index 7d064056e48ceb6d72bb7d9a4b2e9d5099f2e401..6d8a6194e7e9f5d2076fa81938a75aff421e39c2 100644 (file)
--- a/source/glsl/optimize.h
+++ b/source/glsl/optimize.h
@@ -279,6 +279,7 @@ private:
                Node *node;
                Assignment::Target target;
                std::vector<Node *> used_by;
                Node *node;
                Assignment::Target target;
                std::vector<Node *> used_by;

+               unsigned in_loop;

 
                AssignmentInfo(): node(0) { }
        };
 
                AssignmentInfo(): node(0) { }
        };


@@ -305,6 +306,8 @@ private:
        bool r_side_effects;
        bool in_struct;
        bool composite_reference;
        bool r_side_effects;
        bool in_struct;
        bool composite_reference;

+       unsigned in_loop;
+       std::vector<Node *> loop_ext_refs;

        Assignment::Target r_reference;
        std::set<Node *> unused_nodes;
 
        Assignment::Target r_reference;
        std::set<Node *> unused_nodes;
 

diff --git a/tests/glsl/unused_variable_removal_iteration.glsl b/tests/glsl/unused_variable_removal_iteration.glsl
new file mode 100644 (file)
index 0000000..fc1782b
--- /dev/null
+++ b/tests/glsl/unused_variable_removal_iteration.glsl
@@ -0,0 +1,77 @@
+uniform Params
+{
+       float start_height;
+       float max_height;
+       float min_height;
+       float step_size;
+};
+
+#pragma MSP stage(vertex)
+layout(location=0) in vec4 position;
+void main()
+{
+       gl_Position = position;
+       out vec3 dir = vec3(position.xy, 1.0);
+}
+
+#pragma MSP stage(fragment)
+layout(location=0) out vec4 frag_color;
+void main()
+{
+       vec3 ndir = normalize(dir);
+       vec3 pos = vec3(0.0, 0.0, start_height);
+       float luminance = 0.0;
+       float extinction = 0.0;
+       while(true)
+       {
+               if(pos.z<min_height || pos.z>max_height)
+                       break;
+
+               float density = exp(pos.z/-1000.0);
+               luminance += density*exp(-extinction);
+
+               extinction += density*step_size;
+               pos += ndir*step_size;
+       }
+
+       frag_color = vec4(vec3(luminance), 1.0);
+}
+
+/* Expected output: vertex
+layout(location=0) in vec4 position;
+layout(location=0) out vec3 dir;
+void main()
+{
+       gl_Position = position;
+       dir = vec3(position.xy, 1.0);
+}
+*/
+
+/* Expected output: fragment
+layout(binding=80) uniform Params
+{
+       float start_height;
+       float max_height;
+       float min_height;
+       float step_size;
+};
+layout(location=0) out vec4 frag_color;
+layout(location=0) in vec3 dir;
+void main()
+{
+       vec3 ndir = normalize(dir);
+       vec3 pos = vec3(0.0, 0.0, start_height);
+       float luminance = 0.0;
+       float extinction = 0.0;
+       while(true)
+       {
+               if(pos.z<min_height || pos.z>max_height)
+                       break;
+               float density = exp(pos.z/-1000.0);
+               luminance += density*exp(-extinction);
+               extinction += density*step_size;
+               pos += ndir*step_size;
+       }
+       frag_color = vec4(vec3(luminance), 1.0);
+}
+*/