Cycles: Avoid recursion when doing constant fold

This reduces stress on the the stack memory which could be really handy
on certain operation systems which applies strict limits on the stack.

Reviewers: brecht, juicyfruit, dingto

Reviewed By: brecht, juicyfruit, dingto

Differential Revision: https://developer.blender.org/D1656

4 files changed, 99 insertions, 23 deletions

diff --git a/intern/cycles/render/graph.cpp b/intern/cycles/render/graph.cpp
index ffd99626f81..c9f39d449a4 100644
--- a/intern/cycles/render/graph.cpp
+++ b/intern/cycles/render/graph.cpp
@@ -22,9 +22,37 @@
 #include "util_algorithm.h"
 #include "util_debug.h"
 #include "util_foreach.h"
+#include "util_queue.h"
 
 CCL_NAMESPACE_BEGIN
 
+namespace {
+
+bool check_node_inputs_has_links(const ShaderNode *node)
+{
+	foreach(const ShaderInput *in, node->inputs) {
+		if(in->link) {
+			return true;
+		}
+	}
+	return false;
+}
+
+bool check_node_inputs_traversed(const ShaderNode *node,
+                                 const ShaderNodeSet& done)
+{
+	foreach(const ShaderInput *in, node->inputs) {
+		if(in->link) {
+			if(done.find(in->link->parent) == done.end()) {
+				return false;
+			}
+		}
+	}
+	return true;
+}
+
+}  /* namespace */
+
 /* Input and Output */
 
 ShaderInput::ShaderInput(ShaderNode *parent_, const char *name_, ShaderSocketType type_)
@@ -566,31 +594,50 @@ void ShaderGraph::remove_unneeded_nodes()
  * Try to constant fold some nodes, and pipe result directly to
  * the input socket of connected nodes.
  */
-void ShaderGraph::constant_fold(set<ShaderNode*>& done, ShaderNode *node)
+void ShaderGraph::constant_fold()
 {
-	/* Only fold each node once. */
-	if(done.find(node) != done.end())
-		return;
+	ShaderNodeSet done, scheduled;
+	queue<ShaderNode*> traverse_queue;
 
-	done.insert(node);
-
-	/* Fold nodes connected to inputs first. */
-	foreach(ShaderInput *in, node->inputs) {
-		if(in->link) {
-			constant_fold(done, in->link->parent);
+	/* Schedule nodes which doesn't have any dependencies. */
+	foreach(ShaderNode *node, nodes) {
+		if(!check_node_inputs_has_links(node)) {
+			traverse_queue.push(node);
+			scheduled.insert(node);
 		}
 	}
 
-	/* Then fold self. */
-	foreach(ShaderOutput *output, node->outputs) {
-		float3 optimized_value = make_float3(0.0f, 0.0f, 0.0f);
-
-		if(node->constant_fold(output, &optimized_value)) {
-			/* Apply optimized value to connected sockets. */
-			vector<ShaderInput*> links(output->links);
-			foreach(ShaderInput *in, links) {
-				in->value = optimized_value;
-				disconnect(in);
+	while(!traverse_queue.empty()) {
+		ShaderNode *node = traverse_queue.front();
+		traverse_queue.pop();
+		done.insert(node);
+		foreach(ShaderOutput *output, node->outputs) {
+			/* Schedule node which was depending on the value,
+			 * when possible. Do it before disconnect.
+			 */
+			foreach(ShaderInput *input, output->links) {
+				if(scheduled.find(input->parent) != scheduled.end()) {
+					/* Node might be not yet optimized but scheduled already
+					 * by other dependencies. No need to re-schedule it.
+					 */
+					continue;
+				}
+				/* Schedule node if its inputs are fully done. */
+				if(check_node_inputs_traversed(input->parent, done)) {
+					traverse_queue.push(input->parent);
+					scheduled.insert(input->parent);
+				}
+			}
+			/* Optimize current node. */
+			float3 optimized_value = make_float3(0.0f, 0.0f, 0.0f);
+			if(node->constant_fold(output, &optimized_value)) {
+				/* Apply optimized value to connected sockets. */
+				vector<ShaderInput*> links(output->links);
+				foreach(ShaderInput *input, links) {
+					/* Assign value and disconnect the optimizedinput. */
+					input->value = optimized_value;
+					disconnect(input);
+				}
 			}
 		}
 	}
@@ -641,8 +688,7 @@ void ShaderGraph::clean(Scene *scene)
 	remove_unneeded_nodes();
 
 	/* 2: Constant folding. */
-	set<ShaderNode*> done;
-	constant_fold(done, output());
+	constant_fold();
 
 	/* 3: Simplification. */
 	simplify_settings(scene);
diff --git a/intern/cycles/render/graph.h b/intern/cycles/render/graph.h
index 17fb75d459f..420648f6425 100644
--- a/intern/cycles/render/graph.h
+++ b/intern/cycles/render/graph.h
@@ -316,7 +316,7 @@ protected:
 	void break_cycles(ShaderNode *node, vector<bool>& visited, vector<bool>& on_stack);
 	void clean(Scene *scene);
 	void simplify_settings(Scene *scene);
-	void constant_fold(set<ShaderNode*>& visited, ShaderNode *node);
+	void constant_fold();
 	void bump_from_displacement();
 	void refine_bump_nodes();
 	void default_inputs(bool do_osl);
diff --git a/intern/cycles/util/CMakeLists.txt b/intern/cycles/util/CMakeLists.txt
index e103cfa4eee..47ac2800d6d 100644
--- a/intern/cycles/util/CMakeLists.txt
+++ b/intern/cycles/util/CMakeLists.txt
@@ -58,6 +58,7 @@ set(SRC_HEADERS
 	util_param.h
 	util_path.h
 	util_progress.h
+	util_queue.h
 	util_set.h
 	util_simd.h
 	util_sseb.h
diff --git a/intern/cycles/util/util_queue.h b/intern/cycles/util/util_queue.h
new file mode 100644
index 00000000000..f4c802785f9
--- /dev/null
+++ b/intern/cycles/util/util_queue.h
@@ -0,0 +1,29 @@
+/*
+ * Copyright 2011-2015 Blender Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __UTIL_QUEUE_H__
+#define __UTIL_QUEUE_H__
+
+#include <queue>
+
+CCL_NAMESPACE_BEGIN
+
+using std::queue;
+
+CCL_NAMESPACE_END
+
+#endif /* __UTIL_LIST_H__ */
+