Blender V5.3
scheduler.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#include <algorithm>
6#include <type_traits>
7
8#include "BLI_index_range.hh"
9#include "BLI_map.hh"
10#include "BLI_set.hh"
11#include "BLI_stack.hh"
12#include "BLI_vector.hh"
13#include "BLI_vector_set.hh"
14
15#include "DNA_node_types.h"
16
17#include "BKE_compositor.hh"
20#include "BKE_node.hh"
21#include "BKE_node_runtime.hh"
24
27
28#include "COM_context.hh"
29#include "COM_scheduler.hh"
30#include "COM_utilities.hh"
31
32namespace blender::compositor {
33
34/* Checks if the given node group with the given compute context has an active Viewer node in it or
35 * in one of its descendants with the given viewer compute context. */
36static bool has_viewer_node(const bNodeTree &node_group,
37 const ComputeContext &compute_context,
38 const ComputeContext &viewer_compute_context,
39 bke::ComputeContextCache &compute_context_cache)
40{
41 node_group.ensure_topology_cache();
42
43 /* Check if any of the nodes match the viewer compute context. */
44 for (const bNode *node : node_group.nodes_by_type("CompositorNodeViewer"_ustr)) {
45 if (!(node->flag & NODE_DO_OUTPUT) || node->is_muted()) {
46 continue;
47 }
48
49 const ComputeContext *zone_viewer_compute_context =
51 *node, nullptr, compute_context, compute_context_cache);
52 if (!zone_viewer_compute_context) {
53 break;
54 }
55
56 if (&viewer_compute_context == zone_viewer_compute_context) {
57 return true;
58 }
59 }
60
61 /* Otherwise, we have to check node groups recursively. */
62 for (const bNode *group_node : node_group.group_nodes()) {
63 if (group_node->is_muted() || !group_node->id) {
64 continue;
65 }
66
67 const ComputeContext *zone_viewer_compute_context =
69 *group_node, nullptr, compute_context, compute_context_cache);
70 if (!zone_viewer_compute_context) {
71 continue;
72 }
73
74 const bNodeTree &child_node_group = *reinterpret_cast<const bNodeTree *>(group_node->id);
75 const bke::GroupNodeComputeContext &node_compute_context =
76 compute_context_cache.for_group_node(
77 zone_viewer_compute_context, group_node->identifier, &group_node->owner_tree());
79 child_node_group, node_compute_context, viewer_compute_context, compute_context_cache))
80 {
81 return true;
82 }
83 }
84
85 return false;
86}
87
88/* Checks if the node group has a File Output node in it or in one of its descendants. */
89static bool has_file_output_recursive(const bNodeTree &node_group)
90{
91 node_group.ensure_topology_cache();
92 for (const bNode *node : node_group.nodes_by_type("CompositorNodeOutputFile"_ustr)) {
93 if (!node->is_muted()) {
94 return true;
95 }
96 }
97
98 for (const bNode *group_node : node_group.group_nodes()) {
99 if (!group_node->is_muted() && group_node->id) {
100 if (has_file_output_recursive(*reinterpret_cast<const bNodeTree *>(group_node->id))) {
101 return true;
102 }
103 }
104 }
105
106 return false;
107}
108
109/* Returns the value of the given input if it can be determined statically, otherwise nullopt is
110 * returned. The value is only known statically if the socket_result_fn returns an allocated result
111 * for it or the input is connected to a context-based nodes like the Is Viewport node. */
112template<typename T, typename SocketT>
113static std::optional<T> get_input_socket_value(const Context &context,
114 const bNodeSocket &input,
115 SocketResultFn socket_result_fn)
116{
117 if (!input.is_logically_linked()) {
118 return T(input.default_value_typed<SocketT>()->value);
119 }
120
121 const bNodeSocket *linked_output = input.logically_linked_sockets()[0];
122 if (linked_output->owner_node().is_type("GeometryNodeIsViewport"_ustr)) {
123 /* Is Viewport node's value can be determined statically.
124 * Convert according to the same implicit conversion table used at runtime. */
125 const bool is_viewport = context.is_viewport();
126 if constexpr (std::is_same_v<T, bool>) {
127 return is_viewport;
128 }
129 else {
130 const CPPType &from_type = CPPType::get<bool>();
133 if (!conversions.is_convertible(from_type, to_type)) {
134 return std::nullopt;
135 }
136 T converted_value;
137 conversions.convert_to_uninitialized(from_type, to_type, &is_viewport, &converted_value);
138 return converted_value;
139 }
140 }
141
142 if (linked_output->type != input.type) {
143 return std::nullopt;
144 }
145
146 const Result *result = socket_result_fn(*linked_output);
147 if (!result || !result->is_allocated()) {
148 return std::nullopt;
149 }
150
151 return result->get_single_value_default<T>();
152}
153
154/* Returns true if the given input of the given Switch node in the given operation is needed by the
155 * node. */
156static bool is_switch_node_input_needed(const Context &context,
157 const bNode &node,
158 const bNodeSocket &input,
159 SocketResultFn socket_result_fn)
160{
161 const UString condition_identifier = "Switch"_ustr;
162 if (input.identifier_ustr() == condition_identifier) {
163 return true;
164 }
165
167 context, *node.input_by_identifier(condition_identifier), socket_result_fn);
168 if (!condition.has_value()) {
169 return true;
170 }
171
172 return (input.identifier_ustr() == "True"_ustr) == condition.value();
173}
174
175/* Returns true if the given input of the given menu switch node in the given operation is needed
176 * by the node. */
177static bool is_menu_switch_node_input_needed(const Context &context,
178 const bNode &node,
179 const bNodeSocket &input,
180 SocketResultFn socket_result_fn)
181{
182 const UString menu_identifier = "Menu"_ustr;
183 if (input.identifier_ustr() == menu_identifier) {
184 return true;
185 }
186
187 const std::optional<nodes::MenuValue> menu =
189 context, *node.input_by_identifier(menu_identifier), socket_result_fn);
190 if (!menu.has_value()) {
191 return true;
192 }
193
194 const NodeEnumItem menu_item = NodeEnumItem{nullptr, nullptr, menu.value().value};
196 menu_item);
197 return input.identifier == identifier;
198}
199
200/* Returns true if the given input of the given Index Switch node in the given operation is needed
201 * by the node. */
203 const bNode &node,
204 const bNodeSocket &input,
205 SocketResultFn socket_result_fn)
206{
207 const UString index_identifier = "Index"_ustr;
208 if (input.identifier_ustr() == index_identifier) {
209 return true;
210 }
211
213 context, *node.input_by_identifier(index_identifier), socket_result_fn);
214 if (!index.has_value()) {
215 return true;
216 }
217
218 const NodeIndexSwitch &storage = *static_cast<const NodeIndexSwitch *>(node.storage);
219 if (!IndexRange(storage.items_num).contains(index.value())) {
220 return false;
221 }
222
224 storage.items[index.value()]);
225 return input.identifier == identifier;
226}
227
228/* Returns true if the given input of the given node in the given operation is needed by the
229 * compositor. */
230static bool is_input_needed(const Context &context,
231 const bNode &node,
232 const bNodeSocket &input,
233 SocketResultFn socket_result_fn)
234{
235 /* Lazy evaluation of inputs that reference outputs outside of their own zone are currently not
236 * supported. */
237 const bke::bNodeTreeZones &zones = *node.owner_tree().zones();
239 if (output && zones.get_zone_by_socket(input) != zones.get_zone_by_socket(*output)) {
240 return true;
241 }
242
243 if (node.is_group_output()) {
244 const Result *result = socket_result_fn(input);
245 if (!result) {
246 return true;
247 }
248 return result->should_compute();
249 }
250
251 if (node.is_type("GeometryNodeSwitch"_ustr)) {
252 return is_switch_node_input_needed(context, node, input, socket_result_fn);
253 }
254
255 if (node.is_type("GeometryNodeMenuSwitch"_ustr)) {
256 return is_menu_switch_node_input_needed(context, node, input, socket_result_fn);
257 }
258
259 if (node.is_type("GeometryNodeIndexSwitch"_ustr)) {
260 return is_index_switch_node_input_needed(context, node, input, socket_result_fn);
261 }
262
263 return true;
264}
265
266/* Get a stack of the output nodes whose result should be computed. This typically includes the
267 * main output node like the Group Output node, as well as side-effect nodes if requested by the
268 * context like the File Output, Viewer nodes, group nodes whose group that have those side effect
269 * nodes, or zones that have those side effect nodes. If zone is not nullptr, only output nodes in
270 * that zone will be included. */
272 const bNodeTree &node_group,
273 const ComputeContext &compute_context,
274 const bke::bNodeTreeZone *zone,
275 SocketResultFn socket_result_fn)
276{
277 node_group.ensure_topology_cache();
278 const bke::bNodeTreeZones &zones = *node_group.zones();
279 const SideEffectOutputTypes needed_side_effect_output_types =
280 context.needed_side_effect_output_types();
281
282 Stack<const bNode *> node_stack;
283
284 /* If the node is in the same zone, we push the node to the stack, otherwise, we push the output
285 * node of the immediate child zone that contain the node. */
286 auto push_node_to_stack = [&](const bNode &node) {
287 const bke::bNodeTreeZone *node_zone = zones.get_zone_by_node(node.identifier);
288 if (node_zone == zone) {
289 node_stack.push(&node);
290 }
291 else {
292 node_stack.push(zones.get_zones_to_enter(zone, node_zone)[0]->output_node());
293 }
294 };
295
296 /* Add group nodes that contain File Output and Viewer nodes. */
297 for (const bNode *group_node : node_group.group_nodes()) {
298 if (group_node->is_muted() || !group_node->id) {
299 continue;
300 }
301
302 /* Only consider nodes inside the same zone being scheduled. */
303 if (zone && !zone->contains_node_recursively(*group_node)) {
304 continue;
305 }
306
307 const bNodeTree &child_tree = *reinterpret_cast<const bNodeTree *>(group_node->id);
308 if (flag_is_set(needed_side_effect_output_types, SideEffectOutputTypes::FileOutputNode) &&
309 has_file_output_recursive(child_tree))
310 {
311 push_node_to_stack(*group_node);
312 continue;
313 }
314
315 const ComputeContext *zone_viewer_compute_context =
317 *group_node, zone, compute_context, context.compute_context_cache());
318 if (!zone_viewer_compute_context) {
319 continue;
320 }
321
322 const bke::GroupNodeComputeContext &node_compute_context =
323 context.compute_context_cache().for_group_node(
324 zone_viewer_compute_context, group_node->identifier, &group_node->owner_tree());
325 const ComputeContext *viewer_compute_context = context.viewer_compute_context();
326 if (flag_is_set(needed_side_effect_output_types, SideEffectOutputTypes::ViewerNode) &&
327 viewer_compute_context &&
328 has_viewer_node(child_tree,
329 node_compute_context,
330 *viewer_compute_context,
331 context.compute_context_cache()))
332 {
333 push_node_to_stack(*group_node);
334 continue;
335 }
336 }
337
338 /* Add Warning nodes. */
339 for (const bNode *node : node_group.nodes_by_type("GeometryNodeWarning"_ustr)) {
340 if (node->is_muted()) {
341 continue;
342 }
343
344 /* Only consider nodes inside the same zone being scheduled. */
345 if (zone && !zone->contains_node_recursively(*node)) {
346 continue;
347 }
348
349 push_node_to_stack(*node);
350 }
351
352 /* Add File Output nodes. */
353 if (flag_is_set(needed_side_effect_output_types, SideEffectOutputTypes::FileOutputNode)) {
354 for (const bNode *node : node_group.nodes_by_type("CompositorNodeOutputFile"_ustr)) {
355 if (node->is_muted()) {
356 continue;
357 }
358
359 /* Only consider nodes inside the same zone being scheduled. */
360 if (zone && !zone->contains_node_recursively(*node)) {
361 continue;
362 }
363
364 push_node_to_stack(*node);
365 }
366 }
367
368 /* Add Viewer node. */
369 const ComputeContext *viewer_compute_context = context.viewer_compute_context();
370 if (flag_is_set(needed_side_effect_output_types, SideEffectOutputTypes::ViewerNode) &&
371 viewer_compute_context)
372 {
373 for (const bNode *node : node_group.nodes_by_type("CompositorNodeViewer"_ustr)) {
374 if (!(node->flag & NODE_DO_OUTPUT) || node->is_muted()) {
375 continue;
376 }
377
378 /* Only consider nodes inside the same zone being scheduled. */
379 if (zone && !zone->contains_node_recursively(*node)) {
380 break;
381 }
382
383 /* Only consider nodes in the viewer compute context. */
384 const ComputeContext *zone_viewer_compute_context =
386 *node, zone, compute_context, context.compute_context_cache());
387 if (!zone_viewer_compute_context) {
388 break;
389 }
390
391 if (viewer_compute_context != zone_viewer_compute_context) {
392 break;
393 }
394
395 push_node_to_stack(*node);
396 break;
397 }
398 }
399
400 /* Add Group Output node if any of its inputs are needed and we are not scheduling a zone. */
401 const bNode *output_node = node_group.group_output_node();
402 if (!zone && output_node && !output_node->is_muted()) {
403 for (const bNodeSocket *input : output_node->input_sockets()) {
404 if (!is_socket_available(input)) {
405 continue;
406 }
407
408 if (is_input_needed(context, *output_node, *input, socket_result_fn)) {
409 node_stack.push(output_node);
410 break;
411 }
412 }
413 }
414
415 /* Add the Zone Output node if we are scheduling a zone. */
416 if (zone) {
417 node_stack.push(zone->output_node());
418 }
419
420 return node_stack;
421}
422
423/* A type representing a mapping that associates each node with a heuristic estimation of the
424 * number of intermediate buffers needed to compute it and all of its dependencies. See the
425 * compute_number_of_needed_buffers function for more information. */
427
428/* Compute a heuristic estimation of the number of intermediate buffers needed to compute each node
429 * and all of its dependencies for all nodes that the given node depends on. The output is a map
430 * that maps each node with the number of intermediate buffers needed to compute it and all of its
431 * dependencies.
432 *
433 * Consider a node that takes n number of buffers as an input from a number of node dependencies,
434 * which we shall call the input nodes. The node also computes and outputs m number of buffers.
435 * In order for the node to compute its output, a number of intermediate buffers will be needed.
436 * Since the node takes n buffers and outputs m buffers, then the number of buffers directly
437 * needed by the node is (n + m). But each of the input buffers are computed by a node that, in
438 * turn, needs a number of buffers to compute its output. So the total number of buffers needed
439 * to compute the output of the node is max(n + m, d) where d is the number of buffers needed by
440 * the input node that needs the largest number of buffers. We only consider the input node that
441 * needs the largest number of buffers, because those buffers can be reused by any input node
442 * that needs a lesser number of buffers.
443 *
444 * Pixel nodes, however, are a special case because links between two pixel nodes inside the same
445 * pixel operation don't pass a buffer, but a single value in the pixel processor. So for pixel
446 * nodes, only inputs and outputs linked to nodes that are not pixel nodes should be considered.
447 * Note that this might not actually be true, because the compiler may decide to split a pixel
448 * operation into multiples ones that will pass buffers, but this is not something that can be
449 * known at scheduling-time. See the description of NodeTreeEvaluator and COM_shader_operation.hh
450 * for more information. In the node tree shown below, node 4 will have exactly the same number of
451 * needed buffers by node 3, because its inputs and outputs are all internally linked in the pixel
452 * operation.
453 *
454 * Pixel Operation
455 * +------------------------------------------------------+
456 * .------------. | .------------. .------------. .------------. | .------------.
457 * | Node 1 | | | Node 3 | | Node 4 | | Node 5 | | | Node 6 |
458 * | |----|--| |--| |------| |--|--| |
459 * | | .-|--| | | | .---| | | | |
460 * '------------' | | '------------' '------------' | '------------' | '------------'
461 * | +----------------------------------|-------------------+
462 * .------------. | |
463 * | Node 2 | | |
464 * | |--'------------------------------------'
465 * | |
466 * '------------'
467 *
468 * Note that the computed output is not guaranteed to be accurate, and will not be in most cases.
469 * The computation is merely a heuristic estimation that works well in most cases. This is due to a
470 * number of reasons:
471 * - The node tree is actually a graph that allows output sharing, which is not something that was
472 * taken into consideration in this implementation because it is difficult to correctly consider.
473 * - Each node may allocate any number of internal buffers, which is not taken into account in this
474 * implementation because it rarely affects the output and is done by very few nodes.
475 * - The compiler may decide to compiler the schedule differently depending on runtime information
476 * which we can merely speculate at scheduling-time as described above. */
478 Stack<const bNode *> &output_nodes,
479 SocketResultFn socket_result_fn)
480{
481 NeededBuffers needed_buffers;
482
483 /* A stack of nodes used to traverse the node group starting from the output nodes. */
484 Stack<const bNode *> node_stack = output_nodes;
485
486 /* Traverse the node group in a post order depth first manner and compute the number of needed
487 * buffers for each node. Post order traversal guarantee that all the node dependencies of each
488 * node are computed before it. This is done by pushing all the uncomputed node dependencies to
489 * the node stack first and only popping and computing the node when all its node dependencies
490 * were computed. */
491 while (!node_stack.is_empty()) {
492 /* Do not pop the node immediately, as it may turn out that we can't compute its number of
493 * needed buffers just yet because its dependencies weren't computed, it will be popped later
494 * when needed. */
495 const bNode &node = *node_stack.peek();
496
497 /* Go over the node dependencies connected to the inputs of the node and push them to the node
498 * stack if they were not computed already. */
499 Set<const bNode *> pushed_nodes;
500 for (const bNodeSocket *input : node.input_sockets()) {
501 if (!is_socket_available(input)) {
502 continue;
503 }
504
505 if (!is_input_needed(context, node, *input, socket_result_fn)) {
506 continue;
507 }
508
509 /* Get the output linked to the input. If it is null, that means the input is unlinked and
510 * has no dependency node. */
512 if (!output) {
513 continue;
514 }
515
516 /* The node dependency was already computed or pushed before, so skip it. */
517 if (needed_buffers.contains(&output->owner_node()) ||
518 pushed_nodes.contains(&output->owner_node()))
519 {
520 continue;
521 }
522
523 /* The output node needs to be computed, push the node dependency to the node stack and
524 * indicate that it was pushed. */
525 node_stack.push(&output->owner_node());
526 pushed_nodes.add_new(&output->owner_node());
527 }
528
529 /* If any of the node dependencies were pushed, that means that not all of them were computed
530 * and consequently we can't compute the number of needed buffers for this node just yet. */
531 if (!pushed_nodes.is_empty()) {
532 continue;
533 }
534
535 /* We don't need to store the result of the pop because we already peeked at it before. */
536 node_stack.pop();
537
538 /* Compute the number of buffers that the node takes as an input as well as the number of
539 * buffers needed to compute the most demanding of the node dependencies. */
540 int number_of_input_buffers = 0;
541 int buffers_needed_by_dependencies = 0;
542 for (const bNodeSocket *input : node.input_sockets()) {
543 if (!is_socket_available(input)) {
544 continue;
545 }
546
547 if (!is_input_needed(context, node, *input, socket_result_fn)) {
548 continue;
549 }
550
551 /* Get the output linked to the input. If it is null, that means the input is unlinked.
552 * Unlinked inputs do not take a buffer, so skip those inputs. */
554 if (!output) {
555 continue;
556 }
557
558 /* Since this input is linked, if the link is not between two pixel nodes, it means that the
559 * node takes a buffer through this input and so we increment the number of input buffers. */
560 if (!is_pixel_node(node) || !is_pixel_node(output->owner_node())) {
561 number_of_input_buffers++;
562 }
563
564 /* If the number of buffers needed by the node dependency is more than the total number of
565 * buffers needed by the dependencies, then update the latter to be the former. This is
566 * computing the "d" in the aforementioned equation "max(n + m, d)". */
567 const int buffers_needed_by_dependency = needed_buffers.lookup(&output->owner_node());
568 buffers_needed_by_dependencies = std::max(buffers_needed_by_dependency,
569 buffers_needed_by_dependencies);
570 }
571
572 /* Compute the number of buffers that will be computed/output by this node. */
573 int number_of_output_buffers = 0;
574 for (const bNodeSocket *output : node.output_sockets()) {
576 continue;
577 }
578
579 /* The output is not linked, it outputs no buffer. */
580 if (!output->is_logically_linked()) {
581 continue;
582 }
583
584 /* If any of the links is not between two pixel nodes, it means that the node outputs
585 * a buffer through this output and so we increment the number of output buffers. */
586 if (!is_pixel_node(node) ||
588 *output,
589 [&](const bNodeSocket &input) { return !is_pixel_node(input.owner_node()); }))
590 {
591 number_of_output_buffers++;
592 }
593 }
594
595 /* Compute the heuristic estimation of the number of needed intermediate buffers to compute
596 * this node and all of its dependencies. This is computing the aforementioned equation
597 * "max(n + m, d)". */
598 const int total_buffers = std::max(number_of_input_buffers + number_of_output_buffers,
599 buffers_needed_by_dependencies);
600 needed_buffers.add(&node, total_buffers);
601 }
602
603 return needed_buffers;
604}
605
606/* Find the nodes that the given node depends on. Nodes already scheduled are not included. Only
607 * nodes in the given zone are included, except for zone output nodes of child zones, which acts as
608 * representatives for the zone in the schedule. Unneeded inputs are marked in the schedule. */
610 Schedule &schedule,
611 const bNode &node,
612 const bke::bNodeTreeZone *zone,
613 SocketResultFn socket_result_fn)
614{
615 const bke::bNodeTreeZones &zones = *node.owner_tree().zones();
616
617 VectorSet<const bNode *> dependency_nodes;
618 for (const bNodeSocket *input : node.input_sockets()) {
619 if (!is_socket_available(input)) {
620 continue;
621 }
622
623 if (!is_input_needed(context, node, *input, socket_result_fn)) {
624 schedule.unneeded_inputs.add(input);
625 continue;
626 }
627
629 if (!output) {
630 continue;
631 }
632
633 /* The dependency node was already scheduled, so skip it. */
634 if (schedule.nodes.contains(&output->owner_node())) {
635 continue;
636 }
637
638 /* Dependency node is not in the same zone, so skip it. */
639 const bke::bNodeTreeZone *dependency_node_zone = zones.get_zone_by_socket(*output);
640 if (dependency_node_zone != zone) {
641 continue;
642 }
643
644 dependency_nodes.add(&output->owner_node());
645 }
646
647 return dependency_nodes.extract_vector();
648}
649
650/* Find the nodes that the given zone depends on, this includes both source nodes of zone border
651 * links as well as the dependencies of the inputs of the zone input node. Nodes already scheduled
652 * are not included. Only dependencies in the parent zone are included. */
654 Schedule &schedule,
655 const bke::bNodeTreeZone &zone,
656 SocketResultFn socket_result_fn)
657{
658 VectorSet<const bNode *> dependency_nodes;
659 for (const bNodeLink *link : zone.border_links) {
661 if (!output) {
662 continue;
663 }
664
665 /* The dependency node was already scheduled, so skip it. */
666 if (schedule.nodes.contains(&output->owner_node())) {
667 continue;
668 }
669
670 /* Only consider nodes in the same zone being scheduled. */
671 if (zone.owner->get_zone_by_socket(*output) != zone.parent_zone) {
672 continue;
673 }
674
675 dependency_nodes.add(&output->owner_node());
676 }
677
678 Vector<const bNode *> zone_input_dependency_nodes = find_node_dependency_nodes(
679 context, schedule, *zone.input_node(), zone.parent_zone, socket_result_fn);
680 dependency_nodes.add_multiple(zone_input_dependency_nodes);
681 return dependency_nodes.extract_vector();
682}
683
684/* Find the nodes that the given node depends on. Nodes already scheduled are not included. Only
685 * nodes in the given zone are included, except for zone output nodes of child zones, which acts as
686 * representatives for the zone in the schedule. Unneeded inputs are marked in the schedule. */
688 Schedule &schedule,
689 const bNode &node,
690 const bke::bNodeTreeZone *zone,
691 SocketResultFn socket_result_fn)
692{
693
694 /* If the node is a zone output of a child zone, we find the dependencies of the zone not its
695 * inner nodes. */
696 const bke::bNodeTreeZones &zones = *node.owner_tree().zones();
697 const bke::bNodeTreeZone *node_zone = zones.get_zone_by_node(node.identifier);
698 if (node_zone && node_zone->output_node() == &node && node_zone->parent_zone == zone) {
699 return find_zone_dependency_nodes(context, schedule, *node_zone, socket_result_fn);
700 }
701
702 return find_node_dependency_nodes(context, schedule, node, zone, socket_result_fn);
703}
704
705/* There are multiple different possible orders of evaluating a node graph, each of which needs
706 * to allocate a number of intermediate buffers to store its intermediate results. It follows
707 * that we need to find the evaluation order which uses the least amount of intermediate buffers.
708 * For instance, consider a node that takes two input buffers A and B. Each of those buffers is
709 * computed through a number of nodes constituting a sub-graph whose root is the node that
710 * outputs that buffer. Suppose the number of intermediate buffers needed to compute A and B are
711 * N(A) and N(B) respectively and N(A) > N(B). Then evaluating the sub-graph computing A would be
712 * a better option than that of B, because had B was computed first, its outputs will need to be
713 * stored in extra buffers in addition to the buffers needed by A. The number of buffers needed by
714 * each node is estimated as described in the compute_number_of_needed_buffers function.
715 *
716 * This is a heuristic generalization of the Sethi-Ullman algorithm, a generalization that
717 * doesn't always guarantee an optimal evaluation order, as the optimal evaluation order is very
718 * difficult to compute, however, this method works well in most cases. Moreover it assumes that
719 * all buffers will have roughly the same size, which may not always be the case. */
721 const bNodeTree &node_group,
722 const ComputeContext &compute_context,
723 const SocketResultFn socket_result_fn,
724 const bke::bNodeTreeZone *zone)
725{
726 Schedule schedule = Schedule{node_group, zone};
727
728 /* Validate node group. */
729 node_group.ensure_topology_cache();
730 const bke::bNodeTreeZones *zones = schedule.node_group.zones();
731 if (node_group.has_available_link_cycle() || !zones) {
732 return schedule;
733 }
734
735 /* Get a stack of the initial output nodes used to traverse the node group. */
737 context, node_group, compute_context, zone, socket_result_fn);
738
739 /* No output nodes, the node group has no effect, return an empty schedule. */
740 if (node_stack.is_empty()) {
741 return schedule;
742 }
743
744 /* Compute the number of buffers needed by each node connected to the outputs. */
745 const NeededBuffers needed_buffers = compute_number_of_needed_buffers(
746 context, node_stack, socket_result_fn);
747
748 /* Traverse the node group in a post order depth first manner, scheduling the nodes in an order
749 * informed by the number of buffers needed by each node. Post order traversal guarantee that all
750 * the node dependencies of each node are scheduled before it. This is done by pushing all the
751 * unscheduled node dependencies to the node stack first and only popping and scheduling the node
752 * when all its node dependencies were scheduled. */
753 while (!node_stack.is_empty()) {
754 /* Do not pop the node immediately, as it may turn out that we can't schedule it just yet
755 * because its dependencies weren't scheduled, it will be popped later when needed. */
756 const bNode &node = *node_stack.peek();
757
759 context, schedule, node, zone, socket_result_fn);
760
761 /* Push the dependency nodes to the node stack such that the node with the highest number of
762 * needed buffers is scheduled first, so we push the nodes in ascending order. */
763 std::ranges::stable_sort(dependency_nodes, [&](const bNode *a, const bNode *b) {
764 return needed_buffers.lookup(a) < needed_buffers.lookup(b);
765 });
766 node_stack.push_multiple(dependency_nodes);
767
768 /* If there are no sorted dependency nodes, that means they were all already scheduled or that
769 * none exists in the first place, so we can pop and schedule the node now. */
770 if (dependency_nodes.is_empty()) {
771 /* The node might have already been scheduled, so we don't use add_new here and simply don't
772 * add it if it was already scheduled. */
773 schedule.nodes.add(node_stack.pop());
774 }
775 }
776
777 return schedule;
778}
779
781 const Schedule &schedule,
782 const VectorSet<const bNode *> *ignored_nodes)
783{
784 int count = 0;
785 Set<const bke::bNodeTreeZone *> child_zones_counted;
786 const bke::bNodeTreeZones &zones = *schedule.node_group.zones();
787 for (const bNodeSocket *input : output.logically_linked_sockets()) {
788 /* Input is explicitly ignored by the schedule and is thus not referenced. */
789 if (schedule.unneeded_inputs.contains(input)) {
790 continue;
791 }
792
793 /* The node of the input is explicitly ignored and is thus not referenced. */
794 if (ignored_nodes && ignored_nodes->contains(&input->owner_node())) {
795 continue;
796 }
797
798 /* If the input is in the same zone being scheduled and is part of the schedule, it is
799 * referenced. */
800 const bke::bNodeTreeZone *target_zone = zones.get_zone_by_socket(*input);
801 if (target_zone == schedule.zone && schedule.nodes.contains(&input->owner_node())) {
802 count++;
803 continue;
804 }
805
806 /* An exception to the above condition for inputs of zone input nodes. If the zone retrieved
807 * from the input socket is not the same as that of the owner node, that means the input is on
808 * a zone input node. In that case, we check the schedule for the zone output node, since the
809 * zone input does not exist in the schedule. */
810 const bke::bNodeTreeZone *target_node_zone = zones.get_zone_by_node(
811 input->owner_node().identifier);
812 if (target_zone == schedule.zone && target_zone != target_node_zone &&
813 schedule.nodes.contains(target_node_zone->output_node()))
814 {
815 count++;
816 continue;
817 }
818
819 /* If the input is not in a zone that is a descendant of the zone being scheduled, then it is
820 * not referenced. */
821 if (!target_zone || (schedule.zone && !schedule.zone->contains_zone_recursively(*target_zone)))
822 {
823 continue;
824 }
825
826 /* Get the immediate child of the zone being scheduled in the nested zone chain toward the
827 * target. */
828 const bke::bNodeTreeZone *child_zone = zones.get_zones_to_enter(schedule.zone, target_zone)[0];
829
830 /* The child zone is not scheduled, so the input is not referenced. */
831 if (!schedule.nodes.contains(child_zone->output_node())) {
832 continue;
833 }
834
835 /* Zones consider all incoming links from the same output as a single input, so we skip
836 * counting the child zone if it was already counted. */
837 if (child_zones_counted.contains(child_zone)) {
838 continue;
839 }
840
841 count++;
842 child_zones_counted.add_new(child_zone);
843 }
844 return count;
845}
846
847} // namespace blender::compositor
#define output
static const CPPType & get()
constexpr IndexRange()=default
bool add(const Key &key, const Value &value)
Definition BLI_map.hh:295
const Value & lookup(const Key &key) const
Definition BLI_map.hh:545
bool contains(const Key &key) const
Definition BLI_map.hh:353
bool contains(const Key &key) const
Definition BLI_set.hh:310
bool is_empty() const
Definition BLI_set.hh:614
void add_new(const Key &key)
Definition BLI_set.hh:233
bool is_empty() const
Definition BLI_stack.hh:310
void push(const T &value)
Definition BLI_stack.hh:215
void push_multiple(Span< T > values)
Definition BLI_stack.hh:283
bool add(const Key &key)
void add_multiple(Span< Key > keys)
bool contains(const Key &key) const
const GroupNodeComputeContext & for_group_node(const ComputeContext *parent, int32_t node_id, const bNodeTree *tree=nullptr)
void convert_to_uninitialized(const CPPType &from_type, const CPPType &to_type, const void *from_value, void *to_value) const
bool is_convertible(const CPPType &from_type, const CPPType &to_type) const
bool contains_zone_recursively(const bNodeTreeZone &other_zone) const
const bNode * output_node() const
Vector< const bNodeLink * > border_links
bool contains_node_recursively(const bNode &node) const
const bNode * input_node() const
Vector< const bNodeTreeZone * > get_zones_to_enter(const bNodeTreeZone *outer_zone, const bNodeTreeZone *inner_zone) const
const bNodeTreeZone * get_zone_by_node(const int32_t node_id) const
const bNodeTreeZone * get_zone_by_socket(const bNodeSocket &socket) const
#define storage(slot, qualifiers)
#define condition(cond)
uint to_type(bool)
#define T
const ComputeContext * get_zone_viewer_compute_context(const bNode &node, const bke::bNodeTreeZone *zone, const ComputeContext &compute_context, bke::ComputeContextCache &compute_context_cache)
const DataTypeConversions & get_implicit_type_conversions()
int compute_output_reference_count(const bNodeSocket &output, const Schedule &schedule, const VectorSet< const bNode * > *ignored_nodes=nullptr)
Definition scheduler.cc:780
static Stack< const bNode * > get_output_nodes(const Context &context, const bNodeTree &node_group, const ComputeContext &compute_context, const bke::bNodeTreeZone *zone, SocketResultFn socket_result_fn)
Definition scheduler.cc:271
static bool is_input_needed(const Context &context, const bNode &node, const bNodeSocket &input, SocketResultFn socket_result_fn)
Definition scheduler.cc:230
Map< const bNode *, int > NeededBuffers
Definition scheduler.cc:426
static bool is_index_switch_node_input_needed(const Context &context, const bNode &node, const bNodeSocket &input, SocketResultFn socket_result_fn)
Definition scheduler.cc:202
Schedule compute_schedule(const Context &context, const bNodeTree &node_group, const ComputeContext &compute_context, SocketResultFn socket_result_fn, const bke::bNodeTreeZone *zone=nullptr)
Definition scheduler.cc:720
static Vector< const bNode * > find_node_dependency_nodes(const Context &context, Schedule &schedule, const bNode &node, const bke::bNodeTreeZone *zone, SocketResultFn socket_result_fn)
Definition scheduler.cc:609
const bNodeSocket * get_output_linked_to_input(const bNodeSocket &input)
Definition utilities.cc:31
static bool is_switch_node_input_needed(const Context &context, const bNode &node, const bNodeSocket &input, SocketResultFn socket_result_fn)
Definition scheduler.cc:156
static Vector< const bNode * > find_dependency_nodes(const Context &context, Schedule &schedule, const bNode &node, const bke::bNodeTreeZone *zone, SocketResultFn socket_result_fn)
Definition scheduler.cc:687
bool is_output_linked_to_input_conditioned(const bNodeSocket &output, FunctionRef< bool(const bNodeSocket &)> condition)
Definition utilities.cc:143
static bool is_menu_switch_node_input_needed(const Context &context, const bNode &node, const bNodeSocket &input, SocketResultFn socket_result_fn)
Definition scheduler.cc:177
static bool has_file_output_recursive(const bNodeTree &node_group)
Definition scheduler.cc:89
bool is_pixel_node(const bNode &node)
Definition utilities.cc:154
FunctionRef< Result *(const bNodeSocket &)> SocketResultFn
static std::optional< T > get_input_socket_value(const Context &context, const bNodeSocket &input, SocketResultFn socket_result_fn)
Definition scheduler.cc:113
static NeededBuffers compute_number_of_needed_buffers(const Context &context, Stack< const bNode * > &output_nodes, SocketResultFn socket_result_fn)
Definition scheduler.cc:477
bool is_socket_available(const bNodeSocket *socket)
Definition utilities.cc:26
static bool has_viewer_node(const bNodeTree &node_group, const ComputeContext &compute_context, const ComputeContext &viewer_compute_context, bke::ComputeContextCache &compute_context_cache)
Definition scheduler.cc:36
static Vector< const bNode * > find_zone_dependency_nodes(const Context &context, Schedule &schedule, const bke::bNodeTreeZone &zone, SocketResultFn socket_result_fn)
Definition scheduler.cc:653
eNodeSocketDatatype type
Set< const bNodeSocket * > unneeded_inputs
const bke::bNodeTreeZone * zone
VectorSet< const bNode * > nodes
static std::string socket_identifier_for_item(const IndexSwitchItem &item)
static std::string socket_identifier_for_item(const NodeEnumItem &item)