[Bf-blender-cvs] [c882d15] object_nodes: Generalized algorithm for constructing node blocks based on local arguments.
Lukas Tönne
noreply at git.blender.org
Tue Jan 12 12:38:27 CET 2016
Commit: c882d15626fd5e013ed0a40f4ab86baeedd3c028
Author: Lukas Tönne
Date: Fri Jan 8 11:48:43 2016 +0100
Branches: object_nodes
https://developer.blender.org/rBc882d15626fd5e013ed0a40f4ab86baeedd3c028
Generalized algorithm for constructing node blocks based on local arguments.
Nodes can have expression inputs and override argument nodes with local
variables. This means that a local block must be created for each expression
input. The boundaries of such blocks are defined implicitly by upstream nodes
which define their own local arguments (or ultimately by the graph arguments).
The current version is still not quite generic enough to allow arbitrary
nesting of blocks, but it should ensure that expressions don't include all
the parent nodes which don't depend on local arguments and therefore should
be calculated in the parent block (a form of constant folding).
===================================================================
M source/blender/blenvm/compile/bvm_codegen.cc
M source/blender/blenvm/compile/bvm_codegen.h
M source/blender/blenvm/compile/bvm_codegen_debug.cc
===================================================================
diff --git a/source/blender/blenvm/compile/bvm_codegen.cc b/source/blender/blenvm/compile/bvm_codegen.cc
index 43508f7..c838eba 100644
--- a/source/blender/blenvm/compile/bvm_codegen.cc
+++ b/source/blender/blenvm/compile/bvm_codegen.cc
@@ -48,6 +48,177 @@ Compiler::~Compiler()
{
}
+void Compiler::get_local_args(const NodeGraph &graph, const NodeInstance *node, OutputSet &local_args)
+{
+ if (!node->type->is_kernel_node())
+ return;
+
+ for (int i = 0; i < node->num_outputs(); ++i) {
+ const NodeOutput *output = node->type->find_output(i);
+
+ if (output->value_type == OUTPUT_LOCAL) {
+ const NodeGraph::Input *graph_input = graph.get_input(output->name);
+ assert(graph_input);
+
+ if (graph_input->key) {
+ local_args.insert(graph_input->key);
+ }
+ }
+ }
+}
+
+static bool is_arg_node(const NodeInstance *node, const OutputSet &args)
+{
+ for (int i = 0; i < node->num_outputs(); ++i) {
+ ConstOutputKey output = node->output(i);
+ if (args.find(output) != args.end())
+ return true;
+ }
+ return false;
+}
+
+static void count_output_users(const NodeGraph &graph,
+ BasicBlock &block)
+{
+ block.output_users.clear();
+ for (OrderedNodeSet::const_iterator it = block.nodes.begin(); it != block.nodes.end(); ++it) {
+ const NodeInstance *node = *it;
+
+ for (int i = 0; i < node->num_outputs(); ++i) {
+ ConstOutputKey key = node->output(i);
+ block.output_users[key] = 0;
+ }
+ }
+
+ for (OrderedNodeSet::const_iterator it = block.nodes.begin(); it != block.nodes.end(); ++it) {
+ const NodeInstance *node = *it;
+
+ /* note: pass nodes are normally removed, but can exist for debugging purposes */
+ if (node->type->is_pass_node())
+ continue;
+
+ for (int i = 0; i < node->num_inputs(); ++i) {
+ if (node->link(i)) {
+ block.output_users[node->link(i)] += 1;
+ }
+ }
+ }
+
+ /* inputs are defined externally, they should be retained during evaluation */
+ for (NodeGraph::InputList::const_iterator it = graph.inputs.begin(); it != graph.inputs.end(); ++it) {
+ const NodeGraph::Input &input = *it;
+ block.output_users[input.key] += 1;
+ }
+
+ /* outputs are passed on to the caller, who is responsible for freeing them */
+ for (NodeGraph::OutputList::const_iterator it = graph.outputs.begin(); it != graph.outputs.end(); ++it) {
+ const NodeGraph::Output &output = *it;
+ block.output_users[output.key] += 1;
+ }
+}
+
+bool Compiler::add_block_node(const NodeGraph &graph, const NodeInstance *node, const OutputSet &block_args,
+ BasicBlock &block, int depth)
+{
+ bool is_block_node = false; /* determines if the node is part of the block */
+
+ is_block_node |= is_arg_node(node, block_args);
+
+ OutputSet local_args;
+ get_local_args(graph, node, local_args);
+
+ for (int i = 0; i < node->num_inputs(); ++i) {
+ ConstInputKey input = node->input(i);
+ if (input.is_constant()) {
+ if (depth == 0)
+ is_block_node |= true;
+ }
+ else if (input.is_expression()) {
+ if (depth == 0)
+ is_block_node |= parse_expression_block(graph, input, block_args, local_args, block, depth);
+ }
+ else {
+ ConstOutputKey output = input.link();
+ if (output) {
+ is_block_node |= add_block_node(graph, output.node, block_args, block, depth);
+ }
+ }
+ }
+
+ if (is_block_node) {
+ block.nodes.insert(node);
+ return true;
+ }
+ else
+ return false;
+}
+
+bool Compiler::parse_expression_block(const NodeGraph &graph, const ConstInputKey &input,
+ const OutputSet &block_args, const OutputSet &local_args,
+ BasicBlock &block, int depth)
+{
+ ConstOutputKey output = input.link();
+ if (!output)
+ return false;
+ const NodeInstance *node = output.node;
+
+ bool is_block_node = false;
+
+ /* generate a local block for the input expression */
+ BasicBlock &expr_block = block.expression_blocks[input];
+
+ add_block_node(graph, node, local_args, expr_block, depth + 1);
+ if (expr_block.nodes.empty()) {
+ /* use the input directly if no expression nodes are generated (no local arg dependencies) */
+ is_block_node |= add_block_node(graph, node, block_args, block, depth);
+ }
+
+ count_output_users(graph, expr_block);
+
+ /* find node inputs in the expression block that use values outside of it,
+ * which means these must be included in the parent block
+ */
+ for (OrderedNodeSet::const_iterator it = expr_block.nodes.begin(); it != expr_block.nodes.end(); ++it) {
+ const NodeInstance *node = *it;
+ for (int i = 0; i < node->num_inputs(); ++i) {
+ ConstInputKey expr_input = node->input(i);
+ const NodeInstance *link_node = expr_input.link().node;
+ if (link_node && expr_block.nodes.find(link_node) == expr_block.nodes.end())
+ is_block_node |= add_block_node(graph, link_node, block_args, block, depth);
+ }
+ }
+
+ return is_block_node;
+}
+
+void Compiler::parse_blocks(const NodeGraph &graph)
+{
+ OutputSet main_args;
+ for (NodeGraph::InputList::const_iterator it = graph.inputs.begin(); it != graph.inputs.end(); ++it) {
+ const NodeGraph::Input &input = *it;
+ if (input.key)
+ main_args.insert(input.key);
+ }
+
+ main = BasicBlock();
+
+ for (NodeGraph::OutputList::const_iterator it = graph.outputs.begin(); it != graph.outputs.end(); ++it) {
+ const NodeGraph::Output &output = *it;
+ if (output.key)
+ add_block_node(graph, output.key.node, main_args, main, 0);
+ }
+ /* input argument nodes must always be included in main,
+ * to provide reliable storage for caller arguments
+ */
+ for (NodeGraph::InputList::const_iterator it = graph.inputs.begin(); it != graph.inputs.end(); ++it) {
+ const NodeGraph::Input &input = *it;
+ if (input.key)
+ add_block_node(graph, input.key.node, main_args, main, 0);
+ }
+
+ count_output_users(graph, main);
+}
+
StackIndex Compiler::find_stack_index(int size) const
{
int unused = 0;
@@ -123,7 +294,7 @@ void Compiler::resolve_basic_block_symbols(const NodeGraph &graph, BasicBlock &b
/* stored directly in the instructions list after creating values */
}
else if (key.is_expression()) {
- BasicBlock &expr_block = expression_map.at(key);
+ BasicBlock &expr_block = block.expression_blocks.at(key);
/* initialize local arguments */
expr_block.output_index.insert(local_output_index.begin(), local_output_index.end());
@@ -148,73 +319,10 @@ void Compiler::resolve_basic_block_symbols(const NodeGraph &graph, BasicBlock &b
}
}
-void Compiler::expression_node_append(const NodeInstance *node,
- OrderedNodeSet &nodes,
- OrderedNodeSet &visited)
-{
- if (node->type->is_kernel_node())
- return;
-
- if (visited.find(node) != visited.end())
- return;
- visited.insert(node);
-
- for (size_t i = 0; i < node->num_inputs(); ++i) {
- ConstOutputKey link = node->link(i);
- if (link) {
- expression_node_append(link.node, nodes, visited);
- }
- }
-
- nodes.insert(node);
-}
-
-void Compiler::graph_node_append(const NodeInstance *node,
- OrderedNodeSet &nodes,
- OrderedNodeSet &visited)
-{
- if (visited.find(node) != visited.end())
- return;
- visited.insert(node);
-
- for (size_t i = 0; i < node->num_inputs(); ++i) {
- const NodeInput *socket = node->type->find_input(i);
- ConstOutputKey link = node->link(i);
-
- if (socket->value_type == INPUT_EXPRESSION) {
- BasicBlock &expr_block = expression_map[node->input(i)];
-
- if (link) {
- OrderedNodeSet expr_visited;
- expression_node_append(link.node, expr_block.nodes, expr_visited);
- }
- }
- else {
- if (link) {
- graph_node_append(link.node, nodes, visited);
- }
- }
- }
-
- nodes.insert(node);
-}
-
-void Compiler::sort_graph_nodes(const NodeGraph &graph)
-{
- OrderedNodeSet visited;
-
- for (NodeGraph::NodeInstanceMap::const_iterator it = graph.nodes.begin(); it != graph.nodes.end(); ++it) {
- graph_node_append(it->second, main.nodes, visited);
- }
-}
-
void Compiler::resolve_symbols(const NodeGraph &graph)
{
- main = BasicBlock();
- expression_map.clear();
-
/* recursively sort node lists for functions */
- sort_graph_nodes(graph);
+ parse_blocks(graph);
/* recursively resolve all stack assignments */
resolve_basic_block_symbols(graph, main);
@@ -399,47 +507,16 @@ static OpCode ptr_release_opcode(const TypeDesc &typedesc)
return OP_NOOP;
}
-static void count_output_users(const NodeGraph &graph,
- SocketUserMap &users)
+int Compiler::codegen_basic_block(BasicBlock &block) const
{
- users.clear();
- for (NodeGraph::NodeInstanceMap::const_iterator it = graph.nodes.begin(); it != graph.nodes.end(); ++it) {
- const NodeInstance *node = it->second;
- for (int i = 0; i < node->num_outputs(); ++i) {
- ConstOutputKey key(node, node->type->find_output(i)->name);
- users[key] = 0;
- }
+ /* do internal blocks first */
+ for (BasicBlock::BasicBlockMap::iterator it = block.expression_blocks.begin(); it != block.expression_blocks.end(); ++it) {
+ BasicBlock &expr_block = it->second;
+ codegen_basic_block(expr_block);
}
- for (NodeGraph::NodeInstanceMap::const_iterator it = graph.nodes.begin(); it != graph.nodes.end(); ++it) {
- const NodeInstance *node = it->second;
-
- /* note: pass nodes are normally removed, but can exist for debugging purposes */
- if (node->type->is_pass_node())
- continue;
-
- for (int i = 0; i < node->num_inputs(); ++i) {
- if (node->link(i)) {
- users[node->link(i)] += 1;
- }
- }
- }
- /* inputs are defined externally, they should be retained during evaluation */
- for (NodeGraph::InputList::const_iterator it = graph.inputs.begin(); it != graph.inputs.end(); ++it) {
- const NodeGraph::Input &input = *it;
- users[input.key] += 1;
- }
- /* outputs are passed on to the caller, which is responsible for freeing them */
- for (NodeGraph::OutputList::const_iterator it = graph.outputs.begin(); it != graph.outputs.end(); ++it) {
- const NodeGraph::Output &output = *it;
- users[output.key] += 1;
- }
-}
-
-int Compiler::codegen_basic_block(const BasicBlock &block,
-
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list