Blender V5.3
node_tree_reference_lifetimes.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 Blender Foundation
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <iostream>
10
11#include <fmt/format.h>
12#include <fmt/ranges.h>
13
15#include "BKE_node_runtime.hh"
19
21#include "BLI_bit_span_ops.hh"
22
24#include "NOD_socket.hh"
25
26#include "BLI_resource_scope.hh"
27
29
30using bits::BitInt;
31using nodes::NodeDeclaration;
32namespace rl = nodes::rl;
33
34std::ostream &operator<<(std::ostream &stream, const ReferenceSetInfo &info)
35{
36 switch (info.type) {
38 stream << "Group Output Data: " << info.index;
39 break;
41 stream << "Group Input Reference: " << info.index;
42 break;
44 stream << "Local: " << info.socket->name;
45 break;
47 stream << "Closure Input Reference: " << info.socket->name;
48 break;
50 stream << "Closure Output Data: " << info.socket->name;
51 break;
52 }
53 stream << " (";
54 for (const bNodeSocket *socket : info.potential_data_origins) {
55 stream << socket->name << ", ";
56 }
57 stream << ")";
58 return stream;
59}
60
61static bool socket_may_have_reference(const bNodeSocket &socket)
62{
63 return socket.may_be_field() || ELEM(socket.type, SOCK_BUNDLE, SOCK_CLOSURE, SOCK_GEOMETRY);
64}
65
68 const BoundedBitSpan mask)
69{
71 return false;
72 }
75 return true;
76}
77
79{
80 if (bits::spans_equal(a, b)) {
81 return false;
82 }
83 a |= b;
84 b |= a;
85 return true;
86}
87
89{
90 return nodes::socket_type_supports_fields(socket_type) ||
92}
93
95{
96 return ELEM(socket_type, SOCK_GEOMETRY, SOCK_BUNDLE, SOCK_CLOSURE);
97}
98
100 const bNode &node)
101{
102 if (!zones) {
103 return nullptr;
104 }
105 const bNodeTreeZone *zone = zones->get_zone_by_node(node.identifier);
106 if (!zone) {
107 return nullptr;
108 }
109 if (!zone->input_node_id || !zone->output_node_id) {
110 return nullptr;
111 }
112 return zone;
113}
114
116 ResourceScope &scope)
117{
118 Array<const rl::RelationsInNode *> relations_by_node(tree.all_nodes().size());
119 for (const bNode *node : tree.all_nodes()) {
120 const rl::RelationsInNode *node_relations = nullptr;
121 switch (node->type_legacy) {
124 case GEO_NODE_BAKE: {
125 /* The relations of these nodes depend on field evaluation to avoid unnecessary
126 * relations, but besides that they don't need special handling. */
127 rl::RelationsInNode &relations = scope.construct<rl::RelationsInNode>();
128 {
129 /* Add eval relations. */
130 int prev_geometry_index = -1;
131 for (const int i : node->input_sockets().index_range()) {
132 const bNodeSocket &socket = node->input_socket(i);
133 if (socket.type == SOCK_GEOMETRY) {
134 prev_geometry_index = i;
135 continue;
136 }
137 if (prev_geometry_index == -1) {
138 continue;
139 }
140 if (socket_may_have_reference(socket)) {
141 relations.use_relations.append({i, prev_geometry_index});
142 }
143 }
144 }
145 {
146 /* Add available relations. */
147 int prev_geometry_index = -1;
148 for (const int i : node->output_sockets().index_range()) {
149 const bNodeSocket &socket = node->output_socket(i);
150 if (socket.type == SOCK_GEOMETRY) {
151 prev_geometry_index = i;
152 }
153 if (prev_geometry_index == -1) {
154 continue;
155 }
156 if (socket_may_have_reference(socket)) {
157 relations.available_relations.append({i, prev_geometry_index});
158 }
159 }
160 }
161 node_relations = &relations;
162 break;
163 }
166 rl::RelationsInNode &relations = scope.construct<rl::RelationsInNode>();
167 for (const bNodeSocket *socket : node->output_sockets()) {
168 if (can_contain_referenced_data(socket->type)) {
169 for (const bNodeSocket *other_output : node->output_sockets()) {
170 if (socket_may_have_reference(*other_output)) {
171 relations.available_relations.append({other_output->index(), socket->index()});
172 }
173 }
174 }
175 }
176 for (const bNodeSocket *socket : node->input_sockets()) {
177 if (can_contain_referenced_data(socket->type)) {
178 for (const bNodeSocket *other_input : node->input_sockets()) {
179 if (socket_may_have_reference(*other_input)) {
180 relations.use_relations.append({other_input->index(), socket->index()});
181 }
182 }
183 }
184 }
185 /* Only create propagate and reference relations for the input node. The output node
186 * needs special handling because attributes created inside of the zone are not directly
187 * referenced on the outside. */
188 if (node->type_legacy == GEO_NODE_REPEAT_INPUT) {
189 const int input_items_start = 1;
190 const int output_items_start = 1;
191 const int items_num = node->output_sockets().size() - 1 - output_items_start;
192 for (const int i : IndexRange(items_num)) {
193 const int input_index = input_items_start + i;
194 const int output_index = output_items_start + i;
195 const bNodeSocket &input_socket = node->input_socket(input_index);
196 if (can_contain_referenced_data(input_socket.type)) {
197 relations.data_propagations.append({input_index, output_index});
198 }
199 else if (socket_may_have_reference(input_socket)) {
200 relations.reference_propagations.append({input_index, output_index});
201 }
202 }
203 }
204 node_relations = &relations;
205 break;
206 }
207 case NODE_REROUTE: {
208 static const rl::RelationsInNode reroute_relations = []() {
209 rl::RelationsInNode relations;
210 relations.data_propagations.append({0, 0});
211 relations.reference_propagations.append({0, 0});
212 return relations;
213 }();
214 node_relations = &reroute_relations;
215 break;
216 }
217 case NODE_GROUP:
218 case NODE_CUSTOM_GROUP: {
219 if (const bNodeTree *group = reinterpret_cast<const bNodeTree *>(node->id)) {
220 if (group->runtime->reference_lifetimes_info) {
221 node_relations = &group->runtime->reference_lifetimes_info->tree_relations;
222 }
223 }
224 break;
225 }
226 default: {
227 if (const NodeDeclaration *node_decl = node->declaration()) {
228 node_relations = node_decl->reference_lifetime_relations();
229 }
230 break;
231 }
232 }
233 relations_by_node[node->index()] = node_relations;
234 }
235 return relations_by_node;
236}
237
239 const bNodeTree &tree,
240 const Span<const rl::RelationsInNode *> &relations_by_node,
241 Vector<int> &r_group_output_reference_sets,
242 MultiValueMap<const bNodeTreeZone *, int> &r_output_set_sources_by_closure_zone)
243{
244 Vector<ReferenceSetInfo> reference_sets;
245 const Span<const bNodeTreeInterfaceSocket *> interface_inputs = tree.interface_inputs();
246 const Span<const bNodeTreeInterfaceSocket *> interface_outputs = tree.interface_outputs();
247
248 /* Handle references coming from field inputs. */
249 for (const int input_i : interface_inputs.index_range()) {
250 const bNodeTreeInterfaceSocket &interface_input = *interface_inputs[input_i];
251 const bNodeSocketType *stype = interface_input.socket_typeinfo();
252 const eNodeSocketDatatype socket_type = stype ? stype->type : SOCK_CUSTOM;
253 if (can_contain_reference(socket_type)) {
254 reference_sets.append({ReferenceSetType::GroupInputReferenceSet, input_i});
255 }
256 }
257 /* Handle references required by output geometries. */
258 for (const int output_i : interface_outputs.index_range()) {
259 const bNodeTreeInterfaceSocket &interface_output = *interface_outputs[output_i];
260 const bNodeSocketType *stype = interface_output.socket_typeinfo();
261 const eNodeSocketDatatype socket_type = stype ? stype->type : SOCK_CUSTOM;
262 if (can_contain_referenced_data(socket_type)) {
263 r_group_output_reference_sets.append(
264 reference_sets.append_and_get_index({ReferenceSetType::GroupOutputData, output_i}));
265 }
266 }
267 /* All references referenced by the sources found so far can exist on all geometry inputs. */
268 for (const int input_i : interface_inputs.index_range()) {
269 const bNodeTreeInterfaceSocket &interface_input = *interface_inputs[input_i];
270 const bNodeSocketType *stype = interface_input.socket_typeinfo();
271 const eNodeSocketDatatype socket_type = stype ? stype->type : SOCK_CUSTOM;
272 if (can_contain_referenced_data(socket_type)) {
273 for (const bNode *node : tree.group_input_nodes()) {
274 const bNodeSocket &socket = node->output_socket(input_i);
275 for (ReferenceSetInfo &source : reference_sets) {
276 source.potential_data_origins.append(&socket);
277 }
278 }
279 }
280 }
281 /* Handle references created by nodes in the current tree. */
282 for (const bNode *node : tree.all_nodes()) {
283 if (node->is_muted()) {
284 continue;
285 }
286 if (const rl::RelationsInNode *relations = relations_by_node[node->index()]) {
287 for (const rl::AvailableRelation &relation : relations->available_relations) {
288 const bNodeSocket &data_socket = node->output_socket(relation.data_output);
289 const bNodeSocket &reference_socket = node->output_socket(relation.reference_output);
290 if (!reference_socket.is_available() || !data_socket.is_available()) {
291 continue;
292 }
293 if (!reference_socket.is_directly_linked() || !data_socket.is_directly_linked()) {
294 continue;
295 }
296 reference_sets.append({ReferenceSetType::LocalReferenceSet, &reference_socket});
297 reference_sets.last().potential_data_origins.append(&data_socket);
298 }
299 }
300 }
301
302 const bNodeTreeZones *zones = tree.zones();
303 if (!zones) {
304 return reference_sets;
305 }
306 for (const bNodeTreeZone *zone : zones->zones) {
307 const bNode &input_node = *zone->input_node();
308 const bNode &output_node = *zone->output_node();
309 if (output_node.type_legacy != NODE_CLOSURE_OUTPUT) {
310 continue;
311 }
312 const auto &storage = *static_cast<const NodeClosureOutput *>(output_node.storage);
313 const int old_reference_sets_count = reference_sets.size();
314 /* Handle references coming from field inputs in the closure. */
315 for (const int input_i : IndexRange(storage.input_items.items_num)) {
316 const bNodeSocket &socket = input_node.output_socket(input_i);
317 if (can_contain_reference(socket.type)) {
318 reference_sets.append({ReferenceSetType::ClosureInputReferenceSet, &socket});
319 }
320 }
321 /* Handle references required by output geometries in the closure. */
322 for (const int output_i : IndexRange(storage.output_items.items_num)) {
323 const bNodeSocket &socket = output_node.input_socket(output_i);
324 if (can_contain_referenced_data(socket.type)) {
325 r_output_set_sources_by_closure_zone.add(
326 zone,
327 reference_sets.append_and_get_index({ReferenceSetType::ClosureOutputData, &socket}));
328 }
329 }
330 /* All references referenced passed into this zone may exist on the geometry inputs. */
331 MutableSpan<ReferenceSetInfo> new_reference_sets = reference_sets.as_mutable_span().drop_front(
332 old_reference_sets_count);
333 for (const int input_i : IndexRange(storage.input_items.items_num)) {
334 const bNodeSocket &socket = input_node.output_socket(input_i);
335 if (can_contain_referenced_data(socket.type)) {
336 for (ReferenceSetInfo &source : new_reference_sets) {
337 source.potential_data_origins.append(&socket);
338 }
339 }
340 }
341 }
342 return reference_sets;
343}
344
346 const Span<ReferenceSetInfo> reference_sets,
347 BitGroupVector<> &r_potential_data_by_socket,
348 BitGroupVector<> &r_potential_reference_by_socket)
349{
350 for (const int reference_set_i : reference_sets.index_range()) {
351 const ReferenceSetInfo &reference_set = reference_sets[reference_set_i];
352 for (const bNodeSocket *socket : reference_set.potential_data_origins) {
353 r_potential_data_by_socket[socket->index_in_tree()][reference_set_i].set();
354 }
355 switch (reference_set.type) {
358 r_potential_reference_by_socket[reference_set.socket->index_in_tree()][reference_set_i]
359 .set();
360 break;
361 }
363 for (const bNode *node : tree.group_input_nodes()) {
364 const bNodeSocket &socket = node->output_socket(reference_set.index);
365 r_potential_reference_by_socket[socket.index_in_tree()][reference_set_i].set();
366 }
367 break;
368 }
371 /* Nothing to do. */
372 break;
373 }
374 }
375 }
376}
377
379 const bNodeTreeZone &zone, const Span<const BitGroupVector<> *> sources)
380{
381 BitVector<> found(sources.first()->group_size(), false);
382 /* Gather references that are passed into the zone from the outside, either through the input
383 * node or border links. */
384 for (const bNodeSocket *socket : zone.input_node()->input_sockets()) {
385 const int src = socket->index_in_tree();
386 for (const BitGroupVector<> *source : sources) {
387 found |= (*source)[src];
388 }
389 }
390 for (const bNodeLink *link : zone.border_links) {
391 const int src = link->fromsock->index_in_tree();
392 for (const BitGroupVector<> *source : sources) {
393 found |= (*source)[src];
394 }
395 }
396 return found;
397}
398
402static bool pass_left_to_right(const bNodeTree &tree,
403 const Span<const rl::RelationsInNode *> &relations_by_node,
404 BitGroupVector<> &r_potential_data_by_socket,
405 BitGroupVector<> &r_potential_reference_by_socket)
406{
407 bool needs_extra_pass = false;
408 const bNodeTreeZones *zones = tree.zones();
409 for (const bNode *node : tree.toposort_left_to_right()) {
410 for (const bNodeSocket *socket : node->input_sockets()) {
411 if (!socket->is_available()) {
412 continue;
413 }
414 const int dst_index = socket->index_in_tree();
415 for (const bNodeLink *link : socket->directly_linked_links()) {
416 if (!link->is_used()) {
417 continue;
418 }
419 const int src_index = link->fromsock->index_in_tree();
420 r_potential_data_by_socket[dst_index] |= r_potential_data_by_socket[src_index];
421 r_potential_reference_by_socket[dst_index] |= r_potential_reference_by_socket[src_index];
422 }
423 }
424 if (node->is_muted()) {
425 for (const bNodeInternalLink &link : node->internal_links()) {
426 const bNodeSocket &input_socket = *link.in;
427 const bNodeSocket &output_socket = *link.out;
428 if (!input_socket.is_available() || !output_socket.is_available()) {
429 continue;
430 }
431 const int src_index = input_socket.index_in_tree();
432 const int dst_index = output_socket.index_in_tree();
433 r_potential_data_by_socket[dst_index] |= r_potential_data_by_socket[src_index];
434 r_potential_reference_by_socket[dst_index] |= r_potential_reference_by_socket[src_index];
435 }
436 continue;
437 }
438 if (const rl::RelationsInNode *relations = relations_by_node[node->index()]) {
439 /* Propagate references. */
440 for (const rl::ReferencePropagation &relation : relations->reference_propagations) {
441 const bNodeSocket &from_socket = node->input_socket(relation.from_input);
442 const bNodeSocket &to_socket = node->output_socket(relation.to_output);
443 if (!from_socket.is_available() || !to_socket.is_available()) {
444 continue;
445 }
446 const int src_index = from_socket.index_in_tree();
447 const int dst_index = to_socket.index_in_tree();
448 r_potential_reference_by_socket[dst_index] |= r_potential_reference_by_socket[src_index];
449 }
450 /* Propagate data. */
451 for (const rl::DataPropagation &relation : relations->data_propagations) {
452 const bNodeSocket &from_socket = node->input_socket(relation.from_input);
453 const bNodeSocket &to_socket = node->output_socket(relation.to_output);
454 if (!from_socket.is_available() || !to_socket.is_available()) {
455 continue;
456 }
457 const int src_index = from_socket.index_in_tree();
458 const int dst_index = to_socket.index_in_tree();
459 r_potential_data_by_socket[dst_index] |= r_potential_data_by_socket[src_index];
460 }
461 }
462 switch (node->type_legacy) {
463 /* This zone needs additional special handling because attributes from the input geometry
464 * are propagated to the output node. */
466 const bNodeTreeZone *zone = get_zone_of_node_if_full(zones, *node);
467 if (!zone) {
468 break;
469 }
470 const bNode *input_node = zone->input_node();
471 const bNode *output_node = node;
472 const auto *storage = static_cast<const NodeGeometryForeachGeometryElementOutput *>(
473 node->storage);
474 const int src_index = input_node->input_socket(0).index_in_tree();
475 for (const bNodeSocket *output_socket : output_node->output_sockets()) {
476 if (output_socket->type == SOCK_GEOMETRY) {
477 const int dst_index = output_socket->index_in_tree();
478 r_potential_data_by_socket[dst_index] |= r_potential_data_by_socket[src_index];
479 }
480 }
481
482 /* Propagate references from the inside to the outside. Like in the repeat zone, new
483 * references created in the zone stay local inside the zone and are not propagated to the
484 * outside. Instead, the foreach-element output node creates new references. */
485 const BitVector<> outside_references = get_references_coming_from_outside_zone(
486 *zone, {&r_potential_data_by_socket, &r_potential_reference_by_socket});
487 for (const int item_i : IndexRange(storage->generation_items.items_num)) {
488 const int src_index =
489 node->input_socket(storage->main_items.items_num + item_i).index_in_tree();
490 const int dst_index =
491 node->output_socket(1 + storage->main_items.items_num + item_i).index_in_tree();
492 bits::inplace_or_masked(r_potential_data_by_socket[dst_index],
493 outside_references,
494 r_potential_data_by_socket[src_index]);
495 bits::inplace_or_masked(r_potential_reference_by_socket[dst_index],
496 outside_references,
497 r_potential_reference_by_socket[src_index]);
498 }
499 break;
500 }
501 case NODE_CLOSURE_INPUT: {
502 const bNodeTreeZone *zone = get_zone_of_node_if_full(zones, *node);
503 if (!zone) {
504 break;
505 }
506 const bNode &input_node = *zone->input_node();
507 /* Data referenced by border links may also be passed into the closure as input. */
508 const BitVector<> outside_references = get_references_coming_from_outside_zone(
509 *zone, {&r_potential_data_by_socket, &r_potential_reference_by_socket});
510 for (const int i : node->output_sockets().index_range()) {
511 const int dst_index = input_node.output_socket(i).index_in_tree();
512 r_potential_data_by_socket[dst_index] |= outside_references;
513 r_potential_reference_by_socket[dst_index] |= outside_references;
514 }
515 break;
516 }
517 case NODE_CLOSURE_OUTPUT: {
518 const bNodeTreeZone *zone = get_zone_of_node_if_full(zones, *node);
519 if (!zone) {
520 break;
521 }
522 const bNode &output_node = *zone->output_node();
523 /* References passed through border links are referenced by the closure. */
524 const BitVector<> passed_in_references = get_references_coming_from_outside_zone(
525 *zone, {&r_potential_reference_by_socket});
527 *zone, {&r_potential_data_by_socket});
528 const int dst_index = output_node.output_socket(0).index_in_tree();
529 for ([[maybe_unused]] const int i : node->input_sockets().index_range()) {
530 r_potential_data_by_socket[dst_index] |= passed_in_data;
531 r_potential_reference_by_socket[dst_index] |= passed_in_references;
532 }
533 break;
534 }
536 BitVector<> potential_input_references(r_potential_reference_by_socket.group_size());
537 BitVector<> potential_input_data(r_potential_data_by_socket.group_size());
538 /* Gather all references and data from all inputs, including the once on the closure input.
539 * The output may reference any of those. */
540 for (const bNodeSocket *socket : node->input_sockets()) {
541 const int src_index = socket->index_in_tree();
542 potential_input_references |= r_potential_reference_by_socket[src_index];
543 potential_input_data |= r_potential_data_by_socket[src_index];
544 }
545 for (const bNodeSocket *out_socket : node->output_sockets()) {
546 const int dst_index = out_socket->index_in_tree();
547 r_potential_reference_by_socket[dst_index] |= potential_input_references;
548 r_potential_data_by_socket[dst_index] |= potential_input_data;
549 }
550 break;
551 }
553 const bNodeTreeZone *zone = get_zone_of_node_if_full(zones, *node);
554 if (!zone) {
555 break;
556 }
557 const bNode &input_node = *zone->input_node();
558 const bNode &output_node = *zone->output_node();
559 const int items_num = output_node.output_sockets().size() - 1;
560
561 /* Handle data propagation in the case when the iteration count is zero. */
562 for (const int i : IndexRange(items_num)) {
563 const int src_index = input_node.input_socket(i + 1).index_in_tree();
564 const int dst_index = output_node.output_socket(i).index_in_tree();
565 r_potential_data_by_socket[dst_index] |= r_potential_data_by_socket[src_index];
566 r_potential_reference_by_socket[dst_index] |= r_potential_reference_by_socket[src_index];
567 }
568
569 const BitVector<> outside_references = get_references_coming_from_outside_zone(
570 *zone, {&r_potential_data_by_socket, &r_potential_reference_by_socket});
571
572 /* Propagate within output node. */
573 for (const int i : IndexRange(items_num)) {
574 const int src_index = output_node.input_socket(i).index_in_tree();
575 const int dst_index = output_node.output_socket(i).index_in_tree();
576 bits::inplace_or_masked(r_potential_data_by_socket[dst_index],
577 outside_references,
578 r_potential_data_by_socket[src_index]);
579 bits::inplace_or_masked(r_potential_reference_by_socket[dst_index],
580 outside_references,
581 r_potential_reference_by_socket[src_index]);
582 }
583
584 /* Ensure that references and data on the input and output node are equal. Since this may
585 * propagate information backwards, an additional pass can be necessary. */
586 for (const int i : IndexRange(items_num)) {
587 const bNodeSocket &body_input_socket = input_node.output_socket(i + 1);
588 const bNodeSocket &body_output_socket = output_node.input_socket(i);
589 const int in_index = body_output_socket.index_in_tree();
590 const int out_index = body_input_socket.index_in_tree();
591 needs_extra_pass |= or_into_each_other_masked(r_potential_data_by_socket[in_index],
592 r_potential_data_by_socket[out_index],
593 outside_references);
594 needs_extra_pass |= or_into_each_other_masked(r_potential_reference_by_socket[in_index],
595 r_potential_reference_by_socket[out_index],
596 outside_references);
597 }
598 break;
599 }
600 }
601 }
602 return needs_extra_pass;
603}
604
606 const bNodeTree &tree,
607 const Span<ReferenceSetInfo> reference_sets,
608 const Span<int> group_output_set_sources,
609 const BitGroupVector<> &potential_data_by_socket,
610 const BitGroupVector<> &potential_reference_by_socket,
611 BitGroupVector<> &r_required_data_by_socket)
612{
613 if (const bNode *group_output_node = tree.group_output_node()) {
614 const Span<const bNodeSocket *> sockets = group_output_node->input_sockets().drop_back(1);
615 for (const int reference_set_i : group_output_set_sources) {
616 const ReferenceSetInfo &reference_set = reference_sets[reference_set_i];
618 const int index = sockets[reference_set.index]->index_in_tree();
619 r_required_data_by_socket[index][reference_set_i].set();
620 }
621 BitVector<> potential_output_references(reference_sets.size(), false);
622 for (const bNodeSocket *socket : sockets) {
623 potential_output_references |= potential_reference_by_socket[socket->index_in_tree()];
624 }
625 for (const bNodeSocket *socket : sockets) {
626 if (!can_contain_referenced_data(socket->type)) {
627 continue;
628 }
629 const int index = socket->index_in_tree();
630 r_required_data_by_socket[index] |= potential_output_references;
631 /* Make sure that only available data is also required. This is enforced in the end anyway,
632 * but may reduce some unnecessary work. */
633 r_required_data_by_socket[index] &= potential_data_by_socket[index];
634 }
635 }
636}
637
639 const bNodeTree &tree,
640 const Span<ReferenceSetInfo> reference_sets,
641 MultiValueMap<const bNodeTreeZone *, int> &output_set_sources_by_closure_zone,
642 const BitGroupVector<> &potential_data_by_socket,
643 const BitGroupVector<> &potential_reference_by_socket,
644 BitGroupVector<> &r_required_data_by_socket)
645{
646 const bNodeTreeZones *zones = tree.zones();
647 if (!zones) {
648 return;
649 }
650 for (const bNodeTreeZone *zone : zones->zones) {
651 if (!zone->input_node_id || !zone->output_node_id) {
652 continue;
653 }
654 const bNode &output_node = *zone->output_node();
655 if (output_node.type_legacy != NODE_CLOSURE_OUTPUT) {
656 continue;
657 }
658 const Span<int> closure_output_set_sources = output_set_sources_by_closure_zone.lookup(zone);
659 for (const int reference_set_i : closure_output_set_sources) {
660 const ReferenceSetInfo &reference_set = reference_sets[reference_set_i];
662 r_required_data_by_socket[reference_set.socket->index_in_tree()][reference_set_i].set();
663 }
664 BitVector<> potential_output_references(reference_sets.size(), false);
665 const Span<const bNodeSocket *> sockets = output_node.input_sockets().drop_back(1);
666 for (const bNodeSocket *socket : sockets) {
667 potential_output_references |= potential_reference_by_socket[socket->index_in_tree()];
668 }
669 for (const bNodeSocket *socket : sockets) {
670 if (!can_contain_referenced_data(socket->type)) {
671 continue;
672 }
673 const int index = socket->index_in_tree();
674 r_required_data_by_socket[index] |= potential_output_references;
675 /* Make sure that only available data is also required. This is enforced in the end anyway,
676 * but may reduce some unnecessary work. */
677 r_required_data_by_socket[index] &= potential_data_by_socket[index];
678 }
679 }
680}
681
683 const bNodeTree &tree,
684 const Span<ReferenceSetInfo> reference_sets,
685 const Span<int> group_output_set_sources,
686 MultiValueMap<const bNodeTreeZone *, int> &output_set_sources_by_closure_zone,
687 const BitGroupVector<> &potential_data_by_socket,
688 const BitGroupVector<> &potential_reference_by_socket,
689 BitGroupVector<> &r_required_data_by_socket)
690{
692 reference_sets,
693 group_output_set_sources,
694 potential_data_by_socket,
695 potential_reference_by_socket,
696 r_required_data_by_socket);
698 reference_sets,
699 output_set_sources_by_closure_zone,
700 potential_data_by_socket,
701 potential_reference_by_socket,
702 r_required_data_by_socket);
703}
704
705static bool pass_right_to_left(const bNodeTree &tree,
706 const Span<const rl::RelationsInNode *> &relations_by_node,
707 const BitGroupVector<> &potential_reference_by_socket,
708 BitGroupVector<> &r_required_data_by_socket)
709{
710 bool needs_extra_pass = false;
711 const bNodeTreeZones *zones = tree.zones();
712 for (const bNode *node : tree.toposort_right_to_left()) {
713 for (const bNodeSocket *socket : node->output_sockets()) {
714 if (!socket->is_available()) {
715 continue;
716 }
717 const int dst_index = socket->index_in_tree();
718 for (const bNodeLink *link : socket->directly_linked_links()) {
719 if (!link->is_used()) {
720 continue;
721 }
722 const int src_index = link->tosock->index_in_tree();
723 r_required_data_by_socket[dst_index] |= r_required_data_by_socket[src_index];
724 }
725 }
726 if (node->is_muted()) {
727 for (const bNodeInternalLink &link : node->internal_links()) {
728 const bNodeSocket &input_socket = *link.in;
729 const bNodeSocket &output_socket = *link.out;
730 if (!input_socket.is_available() || !output_socket.is_available()) {
731 continue;
732 }
733 const int dst_index = input_socket.index_in_tree();
734 const int src_index = output_socket.index_in_tree();
735 r_required_data_by_socket[dst_index] |= r_required_data_by_socket[src_index];
736 }
737 continue;
738 }
739 if (const rl::RelationsInNode *relations = relations_by_node[node->index()]) {
740 for (const rl::DataPropagation &relation : relations->data_propagations) {
741 const bNodeSocket &output_socket = node->output_socket(relation.to_output);
742 const bNodeSocket &input_socket = node->input_socket(relation.from_input);
743 if (!input_socket.is_available() || !output_socket.is_available()) {
744 continue;
745 }
746 const int dst_index = input_socket.index_in_tree();
747 const int src_index = output_socket.index_in_tree();
748 r_required_data_by_socket[dst_index] |= r_required_data_by_socket[src_index];
749 }
750 for (const rl::UseRelation &relation : relations->use_relations) {
751 const bNodeSocket &data_socket = node->input_socket(relation.data_input);
752 const bNodeSocket &reference_socket = node->input_socket(relation.reference_input);
753 if (!data_socket.is_available() || !reference_socket.is_available()) {
754 continue;
755 }
756 r_required_data_by_socket[data_socket.index_in_tree()] |=
757 potential_reference_by_socket[reference_socket.index_in_tree()];
758 }
759 }
760
761 switch (node->type_legacy) {
762 /* Propagate from the geometry outputs to the geometry input. */
764 const bNodeTreeZone *zone = get_zone_of_node_if_full(zones, *node);
765 if (!zone) {
766 break;
767 }
768 const bNode *input_node = node;
769 const bNode *output_node = zone->output_node();
770 const int dst_index = input_node->input_socket(0).index_in_tree();
771 for (const bNodeSocket *output_socket : output_node->output_sockets()) {
772 if (output_socket->type == SOCK_GEOMETRY) {
773 const int src_index = output_socket->index_in_tree();
774 r_required_data_by_socket[dst_index] |= r_required_data_by_socket[src_index];
775 }
776 }
777 break;
778 }
780 const bNode *output_node = node;
781 const auto *storage = static_cast<NodeGeometryForeachGeometryElementOutput *>(
782 output_node->storage);
783
784 for (const int item_i : IndexRange(storage->generation_items.items_num)) {
785 const int src_index =
786 node->output_socket(1 + storage->main_items.items_num + item_i).index_in_tree();
787 const int dst_index =
788 node->input_socket(storage->main_items.items_num + item_i).index_in_tree();
789 r_required_data_by_socket[dst_index] |= r_required_data_by_socket[src_index];
790 }
791 break;
792 }
794 const bNodeTreeZone *zone = get_zone_of_node_if_full(zones, *node);
795 if (!zone) {
796 break;
797 }
798 /* Propagate within output node. */
799 const int items_num = node->output_sockets().size() - 1;
800 for (const int i : IndexRange(items_num)) {
801 const int src_index = node->output_socket(i).index_in_tree();
802 const int dst_index = node->input_socket(i).index_in_tree();
803 r_required_data_by_socket[dst_index] |= r_required_data_by_socket[src_index];
804 }
805 break;
806 }
808 const bNodeTreeZone *zone = get_zone_of_node_if_full(zones, *node);
809 if (!zone) {
810 break;
811 }
812 const bNode *input_node = node;
813 const bNode *output_node = zone->output_node();
814 const int items_num = output_node->output_sockets().size() - 1;
815 for (const int i : IndexRange(items_num)) {
816 const bNodeSocket &body_input_socket = input_node->output_socket(i + 1);
817 const bNodeSocket &body_output_socket = output_node->input_socket(i);
818 const int in_index = body_input_socket.index_in_tree();
819 const int out_index = body_output_socket.index_in_tree();
820 needs_extra_pass |= or_into_each_other(r_required_data_by_socket[in_index],
821 r_required_data_by_socket[out_index]);
822 }
823 break;
824 }
825 case NODE_CLOSURE_OUTPUT: {
826 const bNodeTreeZone *zone = get_zone_of_node_if_full(zones, *node);
827 if (!zone) {
828 break;
829 }
830 /* Data that's required on the closure is also required on all inputs of the closure. */
831 const bNodeSocket &output_socket = node->output_socket(0);
832 const BoundedBitSpan required_data =
833 r_required_data_by_socket[output_socket.index_in_tree()];
834 for (const bNodeSocket *input_socket : node->input_sockets()) {
835 r_required_data_by_socket[input_socket->index_in_tree()] |= required_data;
836 }
837 break;
838 }
839 }
840 }
841 return needs_extra_pass;
842}
843
845 private:
846 Vector<BitGroupVector<>> bit_groups_;
847
848 public:
850 : bit_groups_(bit_groups)
851 {
852 }
853
854 std::string socket_name(const bNodeSocket &socket) const override
855 {
856 Vector<std::string> extra_data;
857 for (const BitGroupVector<> &bit_group : bit_groups_) {
858 const BoundedBitSpan bits = bit_group[socket.index_in_tree()];
859 Vector<int> indices;
860 bits::foreach_1_index(bits, [&](const int i) { indices.append(i); });
861 extra_data.append(fmt::format("({})", fmt::join(indices, ",")));
862 }
863 return fmt::format("{} {}", socket.name, fmt::join(extra_data, " "));
864 }
865};
866
867static rl::RelationsInNode get_tree_relations(
868 const bNodeTree &tree,
869 const Span<ReferenceSetInfo> reference_sets,
870 const BitGroupVector<> &potential_data_by_socket,
871 const BitGroupVector<> &potential_reference_by_socket,
872 const BitGroupVector<> &required_data_by_socket)
873{
874 rl::RelationsInNode tree_relations;
875 const bNode *group_output_node = tree.group_output_node();
876
877 for (const int input_i : tree.interface_inputs().index_range()) {
878 const bNodeTreeInterfaceSocket &interface_input = *tree.interface_inputs()[input_i];
879 const eNodeSocketDatatype socket_type = interface_input.socket_typeinfo()->type;
880 if (can_contain_referenced_data(socket_type)) {
881 BitVector<> required_data(required_data_by_socket.group_size(), false);
882 for (const bNode *input_node : tree.group_input_nodes()) {
883 required_data |=
884 required_data_by_socket[input_node->output_socket(input_i).index_in_tree()];
885 }
886 bits::foreach_1_index(required_data, [&](const int reference_set_i) {
887 const ReferenceSetInfo &reference_set = reference_sets[reference_set_i];
888 switch (reference_set.type) {
890 tree_relations.data_propagations.append_non_duplicates({input_i, reference_set.index});
891 break;
892 }
894 tree_relations.use_relations.append_non_duplicates({reference_set.index, input_i});
895 break;
896 }
897 default:
898 break;
899 }
900 });
901 }
902 }
903 if (group_output_node) {
904 for (const int output_i : tree.interface_outputs().index_range()) {
905 const bNodeSocket &socket = group_output_node->input_socket(output_i);
906 const eNodeSocketDatatype socket_type = socket.type;
907 if (can_contain_reference(socket_type)) {
908 const BoundedBitSpan potential_references =
909 potential_reference_by_socket[socket.index_in_tree()];
910 bits::foreach_1_index(potential_references, [&](const int reference_set_i) {
911 const ReferenceSetInfo &reference_set = reference_sets[reference_set_i];
912 switch (reference_set.type) {
914 tree_relations.reference_propagations.append_non_duplicates(
915 {reference_set.index, output_i});
916 break;
917 }
918 default: {
919 break;
920 }
921 }
922 });
923 }
924 if (can_contain_referenced_data(socket_type)) {
925 const BoundedBitSpan potential_data = potential_data_by_socket[socket.index_in_tree()];
926 bits::foreach_1_index(potential_data, [&](const int reference_set_i) {
927 const ReferenceSetInfo &reference_set = reference_sets[reference_set_i];
928 switch (reference_set.type) {
930 for (const bNodeSocket *other_socket :
931 group_output_node->input_sockets().drop_back(1))
932 {
933 if (!can_contain_reference(other_socket->type)) {
934 continue;
935 }
936 const BoundedBitSpan potential_references =
937 potential_reference_by_socket[other_socket->index_in_tree()];
938 if (potential_references[reference_set_i].test()) {
939 tree_relations.available_relations.append_non_duplicates(
940 {other_socket->index(), output_i});
941 }
942 }
943 break;
944 }
945 default: {
946 break;
947 }
948 }
949 });
950 }
951 }
952 }
953
954 return tree_relations;
955}
956
963 const Span<ReferenceSetInfo> reference_sets,
964 const Span<rl::DataPropagation> &propagate_relations,
965 BitGroupVector<> &required_data_by_socket)
966{
967 Vector<int> propagate_targets;
968 for (const auto relation : propagate_relations) {
969 propagate_targets.append(relation.to_output);
970 }
971 BitVector<> reference_sets_mask(reference_sets.size(), true);
972 for (const int i : reference_sets.index_range()) {
973 const ReferenceSetInfo &reference_set = reference_sets[i];
974 if (reference_set.type == ReferenceSetType::GroupOutputData) {
975 if (!propagate_targets.contains(reference_set.index)) {
976 reference_sets_mask[i].reset();
977 }
978 }
979 }
980 required_data_by_socket.foreach_and(reference_sets_mask);
981}
982
983static std::unique_ptr<ReferenceLifetimesInfo> make_reference_lifetimes_info(const bNodeTree &tree)
984{
985 tree.ensure_topology_cache();
986 tree.ensure_interface_cache();
987 if (tree.has_available_link_cycle()) {
988 return {};
989 }
990 const bNodeTreeZones *zones = tree.zones();
991 if (zones == nullptr) {
992 return {};
993 }
994
995 std::unique_ptr<ReferenceLifetimesInfo> reference_lifetimes_info =
996 std::make_unique<ReferenceLifetimesInfo>();
997
998 ResourceScope scope;
999 Array<const rl::RelationsInNode *> relations_by_node = prepare_relations_by_node(tree, scope);
1000
1001 Vector<int> group_output_set_sources;
1002 MultiValueMap<const bNodeTreeZone *, int> output_set_sources_by_closure_zone;
1003 reference_lifetimes_info->reference_sets = find_reference_sets(
1004 tree, relations_by_node, group_output_set_sources, output_set_sources_by_closure_zone);
1005 const Span<ReferenceSetInfo> reference_sets = reference_lifetimes_info->reference_sets;
1006
1007 const int sockets_num = tree.all_sockets().size();
1008 const int reference_sets_num = reference_sets.size();
1009
1010 BitGroupVector<> potential_data_by_socket(sockets_num, reference_sets_num, false);
1011 BitGroupVector<> potential_reference_by_socket(sockets_num, reference_sets_num, false);
1013 tree, reference_sets, potential_data_by_socket, potential_reference_by_socket);
1014
1015 /* Propagate data and reference from left to right. This may need to be done multiple times
1016 * because there may be some back-links. */
1017 while (pass_left_to_right(
1018 tree, relations_by_node, potential_data_by_socket, potential_reference_by_socket))
1019 {
1020 }
1021
1022 BitGroupVector<> required_data_by_socket(sockets_num, reference_sets_num, false);
1024 reference_sets,
1025 group_output_set_sources,
1026 output_set_sources_by_closure_zone,
1027 potential_data_by_socket,
1028 potential_reference_by_socket,
1029 required_data_by_socket);
1030
1031 while (pass_right_to_left(
1032 tree, relations_by_node, potential_reference_by_socket, required_data_by_socket))
1033 {
1034 }
1035
1036 /* Make sure that all required data is also potentially available. */
1037 required_data_by_socket.all_bits() &= potential_data_by_socket.all_bits();
1038
1039 reference_lifetimes_info->tree_relations = get_tree_relations(tree,
1040 reference_sets,
1041 potential_data_by_socket,
1042 potential_reference_by_socket,
1043 required_data_by_socket);
1045 reference_sets,
1046 reference_lifetimes_info->tree_relations.data_propagations,
1047 required_data_by_socket);
1048
1049/* Only useful when debugging the reference lifetimes analysis. */
1050#if 0
1051 std::cout << "\n\n"
1052 << node_tree_to_dot(tree,
1053 bNodeTreeBitGroupVectorOptions({potential_data_by_socket,
1054 potential_reference_by_socket,
1055 required_data_by_socket}))
1056
1057 << "\n\n";
1058#endif
1059
1060 reference_lifetimes_info->required_data_by_socket = std::move(required_data_by_socket);
1061 return reference_lifetimes_info;
1062}
1063
1065{
1066 std::unique_ptr<ReferenceLifetimesInfo> reference_lifetimes_info = make_reference_lifetimes_info(
1067 tree);
1068 std::unique_ptr<ReferenceLifetimesInfo> &stored_reference_lifetimes_info =
1070 if (!reference_lifetimes_info) {
1071 if (!tree.runtime->reference_lifetimes_info) {
1072 return false;
1073 }
1074 stored_reference_lifetimes_info.reset();
1075 return true;
1076 }
1077
1078 const bool interface_changed = stored_reference_lifetimes_info &&
1079 stored_reference_lifetimes_info->tree_relations !=
1080 reference_lifetimes_info->tree_relations;
1081 stored_reference_lifetimes_info = std::move(reference_lifetimes_info);
1082 return interface_changed;
1083}
1084
1085} // namespace blender::bke::node_tree_reference_lifetimes
#define NODE_REROUTE
Definition BKE_node.hh:867
#define NODE_CUSTOM_GROUP
Definition BKE_node.hh:870
#define NODE_GROUP
Definition BKE_node.hh:865
#define NODE_EVALUATE_CLOSURE
#define GEO_NODE_FOREACH_GEOMETRY_ELEMENT_INPUT
#define GEO_NODE_FOREACH_GEOMETRY_ELEMENT_OUTPUT
#define GEO_NODE_SIMULATION_OUTPUT
#define NODE_CLOSURE_OUTPUT
#define GEO_NODE_BAKE
#define GEO_NODE_REPEAT_OUTPUT
#define GEO_NODE_REPEAT_INPUT
#define GEO_NODE_SIMULATION_INPUT
#define NODE_CLOSURE_INPUT
#define ELEM(...)
constexpr IndexRange()=default
Span< Value > lookup(const Key &key) const
void add(const Key &key, const Value &value)
T & construct(Args &&...args)
constexpr Span drop_back(int64_t n) const
Definition BLI_span.hh:186
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
int64_t size() const
int64_t append_and_get_index(const T &value)
bool contains(const T &value) const
void append(const T &value)
const T & last(const int64_t n=0) const
MutableSpan< T > as_mutable_span()
void foreach_and(const BoundedBitSpan bits)
std::unique_ptr< node_tree_reference_lifetimes::ReferenceLifetimesInfo > reference_lifetimes_info
std::optional< int > output_node_id
const bNode * output_node() const
Vector< const bNodeLink * > border_links
std::optional< int > input_node_id
const bNode * input_node() const
Vector< bNodeTreeZone * > zones
const bNodeTreeZone * get_zone_by_node(const int32_t node_id) const
#define storage(slot, qualifiers)
uint64_t BitInt
void inplace_or_masked(FirstBitSpanT &&first_arg, const MaskBitSpanT &mask, const BitSpanT &...args)
void foreach_1_index(const BitSpanT &data, Fn &&fn)
bool spans_equal(const BitSpanT1 &a, const BitSpanT2 &b)
bool spans_equal_masked(const BitSpanT1 &a, const BitSpanT2 &b, const BitSpanT3 &mask)
static bool or_into_each_other(MutableBoundedBitSpan a, MutableBoundedBitSpan b)
static Array< const rl::RelationsInNode * > prepare_relations_by_node(const bNodeTree &tree, ResourceScope &scope)
static bool pass_left_to_right(const bNodeTree &tree, const Span< const rl::RelationsInNode * > &relations_by_node, BitGroupVector<> &r_potential_data_by_socket, BitGroupVector<> &r_potential_reference_by_socket)
static bool pass_right_to_left(const bNodeTree &tree, const Span< const rl::RelationsInNode * > &relations_by_node, const BitGroupVector<> &potential_reference_by_socket, BitGroupVector<> &r_required_data_by_socket)
static rl::RelationsInNode get_tree_relations(const bNodeTree &tree, const Span< ReferenceSetInfo > reference_sets, const BitGroupVector<> &potential_data_by_socket, const BitGroupVector<> &potential_reference_by_socket, const BitGroupVector<> &required_data_by_socket)
static void set_initial_data_and_reference_bits(const bNodeTree &tree, const Span< ReferenceSetInfo > reference_sets, BitGroupVector<> &r_potential_data_by_socket, BitGroupVector<> &r_potential_reference_by_socket)
static void prepare_required_data_for_group_outputs(const bNodeTree &tree, const Span< ReferenceSetInfo > reference_sets, const Span< int > group_output_set_sources, const BitGroupVector<> &potential_data_by_socket, const BitGroupVector<> &potential_reference_by_socket, BitGroupVector<> &r_required_data_by_socket)
static BitVector get_references_coming_from_outside_zone(const bNodeTreeZone &zone, const Span< const BitGroupVector<> * > sources)
static void prepare_required_data_for_closure_outputs(const bNodeTree &tree, const Span< ReferenceSetInfo > reference_sets, MultiValueMap< const bNodeTreeZone *, int > &output_set_sources_by_closure_zone, const BitGroupVector<> &potential_data_by_socket, const BitGroupVector<> &potential_reference_by_socket, BitGroupVector<> &r_required_data_by_socket)
bool can_contain_reference(eNodeSocketDatatype socket_type)
static void disable_unused_group_output_propagation(const Span< ReferenceSetInfo > reference_sets, const Span< rl::DataPropagation > &propagate_relations, BitGroupVector<> &required_data_by_socket)
bool can_contain_referenced_data(eNodeSocketDatatype socket_type)
static std::unique_ptr< ReferenceLifetimesInfo > make_reference_lifetimes_info(const bNodeTree &tree)
static const bNodeTreeZone * get_zone_of_node_if_full(const bNodeTreeZones *zones, const bNode &node)
static bool or_into_each_other_masked(MutableBoundedBitSpan a, MutableBoundedBitSpan b, const BoundedBitSpan mask)
static bool socket_may_have_reference(const bNodeSocket &socket)
static void prepare_required_data_for_outputs(const bNodeTree &tree, const Span< ReferenceSetInfo > reference_sets, const Span< int > group_output_set_sources, MultiValueMap< const bNodeTreeZone *, int > &output_set_sources_by_closure_zone, const BitGroupVector<> &potential_data_by_socket, const BitGroupVector<> &potential_reference_by_socket, BitGroupVector<> &r_required_data_by_socket)
static Vector< ReferenceSetInfo > find_reference_sets(const bNodeTree &tree, const Span< const rl::RelationsInNode * > &relations_by_node, Vector< int > &r_group_output_reference_sets, MultiValueMap< const bNodeTreeZone *, int > &r_output_set_sources_by_closure_zone)
std::string node_tree_to_dot(const bNodeTree &tree, const bNodeTreeToDotOptions &options=bNodeTreeToDotOptions())
bool socket_type_supports_fields(const eNodeSocketDatatype socket_type)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
eNodeSocketDatatype type
bke::bNodeTreeRuntime * runtime
Defines a socket type.
Definition BKE_node.hh:163
eNodeSocketDatatype type
Definition BKE_node.hh:198
friend std::ostream & operator<<(std::ostream &stream, const ReferenceSetInfo &info)