Generalized code generation for nodes to support more complex control flow in the future.

The basic idea is that a node represents a function F, without assuming anything about
how the input expressions are evaluated:

F = F()

In most common case this function can be decomposed and defined in terms of concrete values,
which are given by the input expressions:

F = F'(G1(), G2(), ...), where Gn are the respective inputs of the node

This is a first *very* naive implementation. It would rely heavily on common-subexpression-
elimination (CSE) to avoid generating the same code paths over and over again. There should
probably be some initial optimization on the BVM node level instead of relying just on LLVM passes.

The purpose of this generalization is to allow more complicated control flow inside node functions.
Nodes would then also be able to take additional variable arguments (e.g. an index), which can
be modified before being used as internal arguments for input expressions.

5 files changed, 152 insertions, 106 deletions

diff --git a/source/blender/blenvm/compile/node_graph.cc b/source/blender/blenvm/compile/node_graph.cc
index ed93dde06ff..eef6fe7c77f 100644
--- a/source/blender/blenvm/compile/node_graph.cc
+++ b/source/blender/blenvm/compile/node_graph.cc
@@ -956,6 +956,7 @@ void NodeGraph::skip_pass_nodes()
 	remap_outputs(replacements);
 }
 
+#if 0
 NodeInstance *NodeGraph::inline_node(NodeInstance *old_node, const VariableMap &vars)
 {
 	/* Note: Don't copy nodes without inputs!
@@ -1039,6 +1040,7 @@ void NodeGraph::inline_function_calls()
 		}
 	}
 }
+#endif
 
 bool NodeGraph::add_block_node(NodeBlock &block, const OutputSet &local_vars,
                                NodeInstance *node, NodeSet &visited)
diff --git a/source/blender/blenvm/compile/node_graph.h b/source/blender/blenvm/compile/node_graph.h
index 47228138993..9227d13dcb5 100644
--- a/source/blender/blenvm/compile/node_graph.h
+++ b/source/blender/blenvm/compile/node_graph.h
@@ -213,7 +213,9 @@ struct InputKey {
 
 typedef std::set<ConstInputKey> InputSet;
 typedef std::set<ConstOutputKey> OutputSet;
+#if 0
 typedef std::map<string, OutputKey> VariableMap;
+#endif
 
 struct NodeInstance {
 	struct InputInstance {
@@ -388,8 +390,10 @@ protected:
 	
 	void skip_pass_nodes();
 	
+#if 0
 	NodeInstance *inline_node(NodeInstance *old_node, const VariableMap &vars);
 	void inline_function_calls();
+#endif
 	
 	void remove_unused_nodes();
 	
diff --git a/source/blender/blenvm/llvm/llvm_compiler.cc b/source/blender/blenvm/llvm/llvm_compiler.cc
index 6bbc4fe311a..e19476699b5 100644
--- a/source/blender/blenvm/llvm/llvm_compiler.cc
+++ b/source/blender/blenvm/llvm/llvm_compiler.cc
@@ -89,23 +89,6 @@ void LLVMCompilerBase::destroy_module()
 	m_module = NULL;
 }
 
-void LLVMCompilerBase::codegen_node(llvm::BasicBlock *block,
-                                    const NodeInstance *node)
-{
-	switch (node->type->kind()) {
-		case NODE_TYPE_FUNCTION:
-		case NODE_TYPE_KERNEL:
-			expand_function_node(block, node);
-			break;
-		case NODE_TYPE_PASS:
-			expand_pass_node(block, node);
-			break;
-		case NODE_TYPE_ARG:
-			expand_argument_node(block, node);
-			break;
-	}
-}
-
 /* Compile nodes as a simple expression.
  * Every node can be treated as a single statement. Each node is translated
  * into a function call, with regular value arguments. The resulting value is
@@ -136,23 +119,23 @@ llvm::BasicBlock *LLVMCompilerBase::codegen_function_body_expression(const NodeG
 	
 	for (int i = 0; i < num_inputs; ++i) {
 		const NodeGraph::Input &input = graph.inputs[i];
-		if (input.key)
-			map_argument(block, input.key, input_args[i]);
-	}
-	
-	OrderedNodeSet nodes;
-	for (NodeGraph::NodeInstanceMap::const_iterator it = graph.nodes.begin(); it != graph.nodes.end(); ++it)
-		nodes.insert(it->second);
-	
-	for (OrderedNodeSet::const_iterator it = nodes.begin(); it != nodes.end(); ++it) {
-		const NodeInstance &node = **it;
+		const TypeSpec *typespec = input.typedesc.get_typespec();
 		
-		codegen_node(block, &node);
+		if (input.key) {
+			ValueHandle handle = map_argument(block, typespec, input_args[i]);
+			m_argument_values.insert(ArgumentValueMap::value_type(input.key, handle));
+		}
 	}
 	
 	for (int i = 0; i < num_outputs; ++i) {
 		const NodeGraph::Output &output = graph.outputs[i];
-		store_return_value(block, output.key, output_args[i]);
+		const TypeSpec *typespec = output.typedesc.get_typespec();
+		
+		ExpressionMap node_outputs;
+		expand_node(block, output.key.node, node_outputs);
+		ValueHandle value = node_outputs.at(output.key);
+		
+		store_return_value(block, typespec, value, output_args[i]);
 	}
 	
 	builder.CreateRetVoid();
@@ -236,13 +219,26 @@ void LLVMCompilerBase::optimize_function(llvm::Function *func, int opt_level)
 	FPM.run(*func);
 }
 
-void LLVMCompilerBase::expand_pass_node(llvm::BasicBlock *block, const NodeInstance *node)
+void LLVMCompilerBase::expand_node(llvm::BasicBlock *block, const NodeInstance *node, ExpressionMap &outputs)
+{
+	switch (node->type->kind()) {
+		case NODE_TYPE_FUNCTION:
+		case NODE_TYPE_KERNEL:
+			expand_expression_node(block, node, outputs);
+			break;
+		case NODE_TYPE_PASS:
+			expand_pass_node(block, node, outputs);
+			break;
+		case NODE_TYPE_ARG:
+			expand_argument_node(block, node, outputs);
+			break;
+	}
+}
+
+void LLVMCompilerBase::expand_pass_node(llvm::BasicBlock *block, const NodeInstance *node, ExpressionMap &outputs)
 {
 	using namespace llvm;
 	
-	IRBuilder<> builder(context());
-	builder.SetInsertPoint(block);
-	
 	BLI_assert(node->num_inputs() == 1);
 	BLI_assert(node->num_outputs() == 1);
 	
@@ -250,18 +246,25 @@ void LLVMCompilerBase::expand_pass_node(llvm::BasicBlock *block, const NodeInsta
 	ConstOutputKey output = node->output(0);
 	BLI_assert(input.value_type() == INPUT_EXPRESSION);
 	
-	copy_node_value(input.link(), output);
+	ExpressionMap pass_outputs;
+	expand_node(block, input.link().node, pass_outputs);
+	
+	outputs[output] = pass_outputs.at(input.link());
 }
 
-void LLVMCompilerBase::expand_argument_node(llvm::BasicBlock *block, const NodeInstance *node)
+void LLVMCompilerBase::expand_argument_node(llvm::BasicBlock *block, const NodeInstance *node, ExpressionMap &outputs)
 {
 	using namespace llvm;
-	/* input arguments are mapped in advance */
-	BLI_assert(has_node_value(node->output(0)) && "Input argument value node mapped!");
-	UNUSED_VARS(block, node);
+	
+	BLI_assert(node->num_outputs() == 1);
+	
+	ConstOutputKey output = node->output(0);
+	outputs[output] = m_argument_values.at(output);
+	
+	UNUSED_VARS(block);
 }
 
-void LLVMCompilerBase::expand_function_node(llvm::BasicBlock *block, const NodeInstance *node)
+void LLVMCompilerBase::expand_expression_node(llvm::BasicBlock *block, const NodeInstance *node, ExpressionMap &outputs)
 {
 	using namespace llvm;
 	
@@ -281,9 +284,12 @@ void LLVMCompilerBase::expand_function_node(llvm::BasicBlock *block, const NodeI
 	
 	for (int i = 0; i < node->num_outputs(); ++i) {
 		ConstOutputKey output = node->output(i);
+		const TypeSpec *typespec = output.socket->typedesc.get_typespec();
+		
+		ValueHandle value = alloc_node_value(block, typespec);
+		append_output_arguments(args, typespec, value);
 		
-		alloc_node_value(block, output);
-		append_output_arguments(args, output);
+		outputs.insert(ExpressionMap::value_type(output, value));
 	}
 	
 	/* set input arguments */
@@ -297,7 +303,10 @@ void LLVMCompilerBase::expand_function_node(llvm::BasicBlock *block, const NodeI
 				break;
 			}
 			case INPUT_EXPRESSION: {
-				append_input_value(block, args, typespec, input.link());
+				ExpressionMap link_outputs;
+				expand_node(block, input.link().node, link_outputs);
+				
+				append_input_value(block, args, typespec, link_outputs.at(input.link()));
 				break;
 			}
 			case INPUT_VARIABLE: {
diff --git a/source/blender/blenvm/llvm/llvm_compiler.h b/source/blender/blenvm/llvm/llvm_compiler.h
index f48f7813c9c..c05935ba5f9 100644
--- a/source/blender/blenvm/llvm/llvm_compiler.h
+++ b/source/blender/blenvm/llvm/llvm_compiler.h
@@ -74,7 +74,43 @@ struct FunctionParameter {
 };
 typedef std::vector<FunctionParameter> FunctionParameterList;
 
+typedef void* ValueHandle;
+typedef std::map<ConstOutputKey, ValueHandle> ExpressionMap;
+
+#if 0
+struct Expression {
+	explicit Expression(const NodeInstance *node) :
+	    m_node(node)
+	{}
+	
+	bool operator < (const Expression &other) const
+	{
+		if (m_node == other.m_node) {
+			return false;
+		}
+		else
+			return m_node < other.m_node;
+	}
+	
+	bool operator == (const Expression &other) const
+	{
+		if (m_node == other.m_node) {
+			return true;
+		}
+		else
+			return false;
+	}
+	
+	const NodeInstance *node() const { return m_node; }
+	
+private:
+	const NodeInstance *m_node;
+};
+#endif
+
 struct LLVMCompilerBase {
+	typedef std::map<ConstOutputKey, ValueHandle> ArgumentValueMap;
+	
 	virtual ~LLVMCompilerBase();
 	
 	FunctionLLVM *compile_function(const string &name, const NodeGraph &graph, int opt_level);
@@ -90,29 +126,26 @@ protected:
 	
 	void optimize_function(llvm::Function *func, int opt_level);
 	
-	void codegen_node(llvm::BasicBlock *block,
-	                  const NodeInstance *node);
-	
 	llvm::BasicBlock *codegen_function_body_expression(const NodeGraph &graph, llvm::Function *func);
 	llvm::Function *codegen_node_function(const string &name, const NodeGraph &graph);
 	
-	void expand_pass_node(llvm::BasicBlock *block, const NodeInstance *node);
-	void expand_argument_node(llvm::BasicBlock *block, const NodeInstance *node);
-	void expand_function_node(llvm::BasicBlock *block, const NodeInstance *node);
+	void expand_node(llvm::BasicBlock *block, const NodeInstance *node, ExpressionMap &outputs);
+	void expand_pass_node(llvm::BasicBlock *block, const NodeInstance *node, ExpressionMap &outputs);
+	void expand_argument_node(llvm::BasicBlock *block, const NodeInstance *node, ExpressionMap &outputs);
+	void expand_expression_node(llvm::BasicBlock *block, const NodeInstance *node, ExpressionMap &outputs);
 	
 	virtual void node_graph_begin() = 0;
 	virtual void node_graph_end() = 0;
 	
-	virtual bool has_node_value(const ConstOutputKey &output) const = 0;
-	virtual void alloc_node_value(llvm::BasicBlock *block, const ConstOutputKey &output) = 0;
-	virtual void copy_node_value(const ConstOutputKey &from, const ConstOutputKey &to) = 0;
-	virtual void append_output_arguments(std::vector<llvm::Value*> &args, const ConstOutputKey &output) = 0;
+	virtual ValueHandle alloc_node_value(llvm::BasicBlock *block, const TypeSpec *typespec) = 0;
+	virtual void append_output_arguments(std::vector<llvm::Value*> &args, const TypeSpec *typespec, ValueHandle handle) = 0;
 	virtual void append_input_value(llvm::BasicBlock *block, std::vector<llvm::Value*> &args,
-	                                const TypeSpec *typespec, const ConstOutputKey &link) = 0;
+	                                const TypeSpec *typespec, ValueHandle handle) = 0;
 	virtual void append_input_constant(llvm::BasicBlock *block, std::vector<llvm::Value*> &args,
 	                                   const TypeSpec *typespec, const NodeConstant *node_value) = 0;
-	virtual void map_argument(llvm::BasicBlock *block, const OutputKey &output, llvm::Argument *arg) = 0;
-	virtual void store_return_value(llvm::BasicBlock *block, const OutputKey &output, llvm::Value *arg) = 0;
+	virtual ValueHandle map_argument(llvm::BasicBlock *block, const TypeSpec *typespec, llvm::Argument *arg) = 0;
+	virtual void store_return_value(llvm::BasicBlock *block, const TypeSpec *typespec,
+	                                ValueHandle handle, llvm::Value *arg) = 0;
 	
 	virtual llvm::Type *get_argument_type(const TypeSpec *spec) const = 0;
 	virtual llvm::Type *get_return_type(const TypeSpec *spec) const = 0;
@@ -130,25 +163,28 @@ protected:
 private:
 	llvm::Module *m_module;
 	llvm::Value *m_globals_ptr;
+	
+	ArgumentValueMap m_argument_values;
 };
 
 struct LLVMTextureCompiler : public LLVMCompilerBase {
 	typedef Dual2<llvm::Value*> DualValue;
-	typedef std::map<ConstOutputKey, DualValue> OutputValueMap;
+	typedef std::map<ValueHandle, DualValue> HandleValueMap;
+	
+	static ValueHandle get_handle(const DualValue &value);
 	
 	void node_graph_begin();
 	void node_graph_end();
 	
-	bool has_node_value(const ConstOutputKey &output) const;
-	void alloc_node_value(llvm::BasicBlock *block, const ConstOutputKey &output);
-	void copy_node_value(const ConstOutputKey &from, const ConstOutputKey &to);
-	void append_output_arguments(std::vector<llvm::Value*> &args, const ConstOutputKey &output);
+	ValueHandle alloc_node_value(llvm::BasicBlock *block, const TypeSpec *typespec);
+	void append_output_arguments(std::vector<llvm::Value*> &args, const TypeSpec *typespec, ValueHandle handle);
 	void append_input_value(llvm::BasicBlock *block, std::vector<llvm::Value*> &args,
-	                            const TypeSpec *typespec, const ConstOutputKey &link);
+	                            const TypeSpec *typespec, ValueHandle handle);
 	void append_input_constant(llvm::BasicBlock *block, std::vector<llvm::Value*> &args,
 	                           const TypeSpec *typespec, const NodeConstant *node_value);
-	void map_argument(llvm::BasicBlock *block, const OutputKey &output, llvm::Argument *arg);
-	void store_return_value(llvm::BasicBlock *block, const OutputKey &output, llvm::Value *arg);
+	ValueHandle map_argument(llvm::BasicBlock *block, const TypeSpec *typespec, llvm::Argument *arg);
+	void store_return_value(llvm::BasicBlock *block, const TypeSpec *typespec,
+	                        ValueHandle handle, llvm::Value *arg);
 	
 	llvm::Type *get_argument_type(const TypeSpec *spec) const;
 	llvm::Type *get_return_type(const TypeSpec *spec) const;
@@ -172,7 +208,7 @@ struct LLVMTextureCompiler : public LLVMCompilerBase {
 	
 private:
 	static llvm::Module *m_nodes_module;
-	OutputValueMap m_output_values;
+	HandleValueMap m_values;
 };
 
 } /* namespace blenvm */
diff --git a/source/blender/blenvm/llvm/llvm_compiler_dual.cc b/source/blender/blenvm/llvm/llvm_compiler_dual.cc
index f01cf7197af..785c8b547f6 100644
--- a/source/blender/blenvm/llvm/llvm_compiler_dual.cc
+++ b/source/blender/blenvm/llvm/llvm_compiler_dual.cc
@@ -50,73 +50,63 @@ namespace blenvm {
 
 llvm::Module *LLVMTextureCompiler::m_nodes_module = NULL;
 
-void LLVMTextureCompiler::node_graph_begin()
+ValueHandle LLVMTextureCompiler::get_handle(const DualValue &value)
 {
-	
+	return value.value();
 }
 
-void LLVMTextureCompiler::node_graph_end()
+void LLVMTextureCompiler::node_graph_begin()
 {
-	m_output_values.clear();
+	
 }
 
-bool LLVMTextureCompiler::has_node_value(const ConstOutputKey &output) const
+void LLVMTextureCompiler::node_graph_end()
 {
-	return m_output_values.find(output) != m_output_values.end();
+	m_values.clear();
 }
 
-void LLVMTextureCompiler::alloc_node_value(llvm::BasicBlock *block, const ConstOutputKey &output)
+ValueHandle LLVMTextureCompiler::alloc_node_value(llvm::BasicBlock *block, const TypeSpec *typespec)
 {
 	using namespace llvm;
 	
 	IRBuilder<> builder(context());
 	builder.SetInsertPoint(block);
 	
-	const TypeSpec *typespec = output.socket->typedesc.get_typespec();
 	Type *type = bvm_get_llvm_type(context(), typespec, false);
 	BLI_assert(type != NULL);
 	
-	DualValue value(builder.CreateAlloca(type),
-	                builder.CreateAlloca(type),
-	                builder.CreateAlloca(type));
+	DualValue dval(builder.CreateAlloca(type),
+	               builder.CreateAlloca(type),
+	               builder.CreateAlloca(type));
 	
-	/* use as node output values */
-	bool ok = m_output_values.insert(OutputValueMap::value_type(output, value)).second;
-	BLI_assert(ok && "Value for node output already defined!");
+	ValueHandle handle = get_handle(dval);
+	bool ok = m_values.insert(HandleValueMap::value_type(handle, dval)).second;
+	BLI_assert(ok && "Could not insert value!");
 	UNUSED_VARS(ok);
-}
-
-void LLVMTextureCompiler::copy_node_value(const ConstOutputKey &from, const ConstOutputKey &to)
-{
-	using namespace llvm;
 	
-	DualValue value = m_output_values.at(from);
-	bool ok = m_output_values.insert(OutputValueMap::value_type(to, value)).second;
-	BLI_assert(ok && "Value for node output already defined!");
-	UNUSED_VARS(ok);
+	return handle;
 }
 
-void LLVMTextureCompiler::append_output_arguments(std::vector<llvm::Value*> &args, const ConstOutputKey &output)
+void LLVMTextureCompiler::append_output_arguments(std::vector<llvm::Value*> &args, const TypeSpec *typespec, ValueHandle handle)
 {
-	const TypeSpec *typespec = output.socket->typedesc.get_typespec();
+	DualValue dval = m_values.at(handle);
 	
-	DualValue val = m_output_values.at(output);
-	args.push_back(val.value());
+	args.push_back(dval.value());
 	if (bvm_type_has_dual_value(typespec)) {
-		args.push_back(val.dx());
-		args.push_back(val.dy());
+		args.push_back(dval.dx());
+		args.push_back(dval.dy());
 	}
 }
 
 void LLVMTextureCompiler::append_input_value(llvm::BasicBlock *block, std::vector<llvm::Value*> &args,
-                                             const TypeSpec *typespec, const ConstOutputKey &link)
+                                             const TypeSpec *typespec, ValueHandle handle)
 {
 	using namespace llvm;
 	
 	IRBuilder<> builder(context());
 	builder.SetInsertPoint(block);
 	
-	DualValue ptr = m_output_values.at(link);
+	DualValue ptr = m_values.at(handle);
 	if (use_argument_pointer(typespec, false)) {
 		args.push_back(ptr.value());
 		if (bvm_type_has_dual_value(typespec)) {
@@ -156,32 +146,37 @@ void LLVMTextureCompiler::append_input_constant(llvm::BasicBlock *block, std::ve
 	}
 }
 
-void LLVMTextureCompiler::map_argument(llvm::BasicBlock *block, const OutputKey &output, llvm::Argument *arg)
+ValueHandle LLVMTextureCompiler::map_argument(llvm::BasicBlock *block, const TypeSpec *typespec, llvm::Argument *arg)
 {
 	using namespace llvm;
 	
-	const TypeSpec *typespec = output.socket->typedesc.get_typespec();
-	
 	IRBuilder<> builder(context());
 	builder.SetInsertPoint(block);
 	
+	DualValue dval;
 	if (bvm_type_has_dual_value(typespec)) {
 		/* argument is a struct, use GEP instructions to get the individual elements */
-		m_output_values[output] = DualValue(builder.CreateStructGEP(arg, 0),
-		                                    builder.CreateStructGEP(arg, 1),
-		                                    builder.CreateStructGEP(arg, 2));
+		dval = DualValue(builder.CreateStructGEP(arg, 0),
+		                 builder.CreateStructGEP(arg, 1),
+		                 builder.CreateStructGEP(arg, 2));
 	}
 	else {
-		m_output_values[output] = DualValue(arg, NULL, NULL);
+		dval = DualValue(arg, NULL, NULL);
 	}
+	
+	ValueHandle handle = get_handle(dval);
+	bool ok = m_values.insert(HandleValueMap::value_type(handle, dval)).second;
+	BLI_assert(ok && "Could not insert value!");
+	UNUSED_VARS(ok);
+	
+	return handle;
 }
 
-void LLVMTextureCompiler::store_return_value(llvm::BasicBlock *block, const OutputKey &output, llvm::Value *arg)
+void LLVMTextureCompiler::store_return_value(llvm::BasicBlock *block, const TypeSpec *typespec,
+                                             ValueHandle handle, llvm::Value *arg)
 {
 	using namespace llvm;
 	
-	const TypeSpec *typespec = output.socket->typedesc.get_typespec();
-	
 	IRBuilder<> builder(context());
 	builder.SetInsertPoint(block);
 	
@@ -189,7 +184,7 @@ void LLVMTextureCompiler::store_return_value(llvm::BasicBlock *block, const Outp
 	Value *dx_ptr = builder.CreateStructGEP(arg, 1);
 	Value *dy_ptr = builder.CreateStructGEP(arg, 2);
 	
-	DualValue dual = m_output_values.at(output);
+	DualValue dual = m_values.at(handle);
 	bvm_llvm_copy_value(context(), block, value_ptr, dual.value(), typespec);
 	bvm_llvm_copy_value(context(), block, dx_ptr, dual.dx(), typespec);
 	bvm_llvm_copy_value(context(), block, dy_ptr, dual.dy(), typespec);