From: Mikko Rasa <tdb@tdb.fi>
Date: Thu, 22 Apr 2021 10:38:08 +0000 (+0300)
Subject: Recognize backwards dependencies in GLSL loops
X-Git-Url: http://git.tdb.fi/?p=libs%2Fgl.git;a=commitdiff_plain;h=83186c4a01ada8bfb0199c4396c0aaa64631577f

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 0139ec5f..b1201e9f 100644
--- 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),
-	composite_reference(false)
+	composite_reference(false),
+	in_loop(0)
 { }
 
 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)
 	{
+		bool loop_external = false;
 		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]);
 			}
+
 			if(covered)
+			{
 				(*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;
+	assign_info.in_loop = in_loop;
 
 	/* 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;
-	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
diff --git a/source/glsl/optimize.h b/source/glsl/optimize.h
index 7d064056..6d8a6194 100644
--- 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;
+		unsigned in_loop;
 
 		AssignmentInfo(): node(0) { }
 	};
@@ -305,6 +306,8 @@ private:
 	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;
 
diff --git a/tests/glsl/unused_variable_removal_iteration.glsl b/tests/glsl/unused_variable_removal_iteration.glsl
new file mode 100644
index 00000000..fc1782b2
--- /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);
+}
+*/