Geometry Nodes: new evaluation system

This refactors the geometry nodes evaluation system. No changes for the
user are expected. At a high level the goals are:
* Support using geometry nodes outside of the geometry nodes modifier.
* Support using the evaluator infrastructure for other purposes like field evaluation.
* Support more nodes, especially when many of them are disabled behind switch nodes.
* Support doing preprocessing on node groups.

For more details see T98492.

There are fairly detailed comments in the code, but here is a high level overview
for how it works now:
* There is a new "lazy-function" system. It is similar in spirit to the multi-function
  system but with different goals. Instead of optimizing throughput for highly
  parallelizable work, this system is designed to compute only the data that is actually
  necessary. What data is necessary can be determined dynamically during evaluation.
  Many lazy-functions can be composed in a graph to form a new lazy-function, which can
  again be used in a graph etc.
* Each geometry node group is converted into a lazy-function graph prior to evaluation.
  To evaluate geometry nodes, one then just has to evaluate that graph. Node groups are
  no longer inlined into their parents.

Next steps for the evaluation system is to reduce the use of threads in some situations
to avoid overhead. Many small node groups don't benefit from multi-threading at all.
This is much easier to do now because not everything has to be inlined in one huge
node tree anymore.

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

1 files changed, 384 insertions, 0 deletions

diff --git a/source/blender/functions/FN_lazy_function.hh b/source/blender/functions/FN_lazy_function.hh
new file mode 100644
index 00000000000..8dceb9ed993
--- /dev/null
+++ b/source/blender/functions/FN_lazy_function.hh
@@ -0,0 +1,384 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+/** \file
+ * \ingroup fn
+ *
+ * A `LazyFunction` encapsulates a computation which has inputs, outputs and potentially side
+ * effects. Most importantly, a `LazyFunction` supports lazyness in its inputs and outputs:
+ * - Only outputs that are actually used have to be computed.
+ * - Inputs can be requested lazily based on which outputs are used or what side effects the
+ *   function has.
+ *
+ * A lazy-function that uses lazyness may be executed more than once. The most common example is
+ * the geometry nodes switch node. Depending on a condition input, it decides which one of the
+ * other inputs is actually used. From the perspective of the switch node, its execution works as
+ * follows:
+ * 1. The switch node is first executed. It sees that the output is used. Now it requests the
+ *    condition input from the caller and exits.
+ * 2. Once the caller is able to provide the condition input the switch node is executed again.
+ *    This time it retrieves the condition and requests one of the other inputs. Then the node
+ *    exits again, giving back control to the caller.
+ * 3. When the caller computed the second requested input the switch node executes a last time.
+ *    This time it retrieves the new input and forwards it to the output.
+ *
+ * In some sense, a lazy-function can be thought of like a state machine. Every time it is
+ * executed, it advances its state until all required outputs are ready.
+ *
+ * The lazy-function interface is designed to support composition of many such functions into a new
+ * lazy-functions, all while keeping the lazyness working. For example, in geometry nodes a switch
+ * node in a node group should still be able to decide whether a node in the parent group will be
+ * executed or not. This is essential to avoid doing unnecessary work.
+ *
+ * The lazy-function system consists of multiple core components:
+ * - The interface of a lazy-function itself including its calling convention.
+ * - A graph data structure that allows composing many lazy-functions by connecting their inputs
+ *   and outputs.
+ * - An executor that allows multi-threaded execution or such a graph.
+ */
+
+#include "BLI_cpp_type.hh"
+#include "BLI_generic_pointer.hh"
+#include "BLI_linear_allocator.hh"
+#include "BLI_vector.hh"
+
+namespace blender::fn::lazy_function {
+
+enum class ValueUsage {
+  /**
+   * The value is definitely used and therefore has to be computed.
+   */
+  Used,
+  /**
+   * It's unknown whether this value will be used or not. Computing it is ok but the result may be
+   * discarded.
+   */
+  Maybe,
+  /**
+   * The value will definitely not be used. It can still be computed but the result will be
+   * discarded in all cases.
+   */
+  Unused,
+};
+
+class LazyFunction;
+
+/**
+ * This allows passing arbitrary data into a lazy-function during execution. For that, #UserData
+ * has to be subclassed. This mainly exists because it's more type safe than passing a `void *`
+ * with no type information attached.
+ *
+ * Some lazy-functions may expect to find a certain type of user data when executed.
+ */
+class UserData {
+ public:
+  virtual ~UserData() = default;
+};
+
+/**
+ * Passed to the lazy-function when it is executed.
+ */
+struct Context {
+  /**
+   * If the lazy-function has some state (which only makes sense when it is executed more than once
+   * to finish its job), the state is stored here. This points to memory returned from
+   * #LazyFunction::init_storage.
+   */
+  void *storage;
+  /**
+   * Custom user data that can be used in the function.
+   */
+  UserData *user_data;
+};
+
+/**
+ * Defines the calling convention for a lazy-function. During execution, a lazy-function retrieves
+ * its inputs and sets the outputs through #Params.
+ */
+class Params {
+ public:
+  /**
+   * The lazy-function this #Params has been prepared for.
+   */
+  const LazyFunction &fn_;
+
+ public:
+  Params(const LazyFunction &fn);
+
+  /**
+   * Get a pointer to an input value if the value is available already. Otherwise null is returned.
+   *
+   * The #LazyFunction must leave returned object in an initialized state, but can move from it.
+   */
+  void *try_get_input_data_ptr(int index) const;
+
+  /**
+   * Same as #try_get_input_data_ptr, but if the data is not yet available, request it. This makes
+   * sure that the data will be available in a future execution of the #LazyFunction.
+   */
+  void *try_get_input_data_ptr_or_request(int index);
+
+  /**
+   * Get a pointer to where the output value should be stored.
+   * The value at the pointer is in an uninitialized state at first.
+   * The #LazyFunction is responsible for initializing the value.
+   * After the output has been initialized to its final value, #output_set has to be called.
+   */
+  void *get_output_data_ptr(int index);
+
+  /**
+   * Call this after the output value is initialized. After this is called, the value must not be
+   * touched anymore. It may be moved or destructed immediatly.
+   */
+  void output_set(int index);
+
+  /**
+   * Allows the #LazyFunction to check whether an output was computed already without keeping
+   * track of it itself.
+   */
+  bool output_was_set(int index) const;
+
+  /**
+   * Can be used to detect which outputs have to be computed.
+   */
+  ValueUsage get_output_usage(int index) const;
+
+  /**
+   * Tell the caller of the #LazyFunction that a specific input will definitely not be used.
+   * Only an input that was not #ValueUsage::Used can become unused.
+   */
+  void set_input_unused(int index);
+
+  /**
+   * Typed utility methods that wrap the methods above.
+   */
+  template<typename T> T extract_input(int index);
+  template<typename T> const T &get_input(int index);
+  template<typename T> T *try_get_input_data_ptr_or_request(int index);
+  template<typename T> void set_output(int index, T &&value);
+
+  /**
+   * Utility to initialize all outputs that haven't been set yet.
+   */
+  void set_default_remaining_outputs();
+
+ private:
+  /**
+   * Methods that need to be implemented by subclasses. Those are separate from the non-virtual
+   * methods above to make it easy to insert additional debugging logic on top of the
+   * implementations.
+   */
+  virtual void *try_get_input_data_ptr_impl(int index) const = 0;
+  virtual void *try_get_input_data_ptr_or_request_impl(int index) = 0;
+  virtual void *get_output_data_ptr_impl(int index) = 0;
+  virtual void output_set_impl(int index) = 0;
+  virtual bool output_was_set_impl(int index) const = 0;
+  virtual ValueUsage get_output_usage_impl(int index) const = 0;
+  virtual void set_input_unused_impl(int index) = 0;
+};
+
+/**
+ * Describes an input of a #LazyFunction.
+ */
+struct Input {
+  /**
+   * Name used for debugging purposes. The string has to be static or has to be owned by something
+   * else.
+   */
+  const char *debug_name;
+  /**
+   * Data type of this input.
+   */
+  const CPPType *type;
+  /**
+   * Can be used to indicate a caller or this function if this input is used statically before
+   * executing it the first time. This is technically not needed but can improve efficiency because
+   * a round-trip through the `execute` method can be avoided.
+   *
+   * When this is #ValueUsage::Used, the caller has to ensure that the input is definitely
+   * available when the #execute method is first called. The #execute method does not have to check
+   * whether the value is actually available.
+   */
+  ValueUsage usage;
+
+  Input(const char *debug_name, const CPPType &type, const ValueUsage usage = ValueUsage::Used)
+      : debug_name(debug_name), type(&type), usage(usage)
+  {
+  }
+};
+
+struct Output {
+  /**
+   * Name used for debugging purposes. The string has to be static or has to be owned by something
+   * else.
+   */
+  const char *debug_name;
+  /**
+   * Data type of this output.
+   */
+  const CPPType *type = nullptr;
+
+  Output(const char *debug_name, const CPPType &type) : debug_name(debug_name), type(&type)
+  {
+  }
+};
+
+/**
+ * A function that can compute outputs and request inputs lazily. For more details see the comment
+ * at the top of the file.
+ */
+class LazyFunction {
+ protected:
+  const char *debug_name_ = "<unknown>";
+  Vector<Input> inputs_;
+  Vector<Output> outputs_;
+
+ public:
+  virtual ~LazyFunction() = default;
+
+  /**
+   * Get a name of the function or an input or output. This is mainly used for debugging.
+   * These are virtual functions because the names are often not used outside of debugging
+   * workflows. This way the names are only generated when they are actually needed.
+   */
+  virtual std::string name() const;
+  virtual std::string input_name(int index) const;
+  virtual std::string output_name(int index) const;
+
+  /**
+   * Allocates storage for this function. The storage will be passed to every call to #execute.
+   * If the function does not keep track of any state, this does not have to be implemented.
+   */
+  virtual void *init_storage(LinearAllocator<> &allocator) const;
+
+  /**
+   * Destruct the storage created in #init_storage.
+   */
+  virtual void destruct_storage(void *storage) const;
+
+  /**
+   * Inputs of the function.
+   */
+  Span<Input> inputs() const;
+  /**
+   * Outputs of the function.
+   */
+  Span<Output> outputs() const;
+
+  /**
+   * During execution the function retrieves inputs and sets outputs in #params. For some
+   * functions, this method is called more than once. After execution, the function either has
+   * computed all required outputs or is waiting for more inputs.
+   */
+  void execute(Params &params, const Context &context) const;
+
+  /**
+   * Utility to check that the guarantee by #Input::usage is followed.
+   */
+  bool always_used_inputs_available(const Params &params) const;
+
+ private:
+  /**
+   * Needs to be implemented by subclasses. This is separate from #execute so that additional
+   * debugging logic can be implemented in #execute.
+   */
+  virtual void execute_impl(Params &params, const Context &context) const = 0;
+};
+
+/* -------------------------------------------------------------------- */
+/** \name #LazyFunction Inline Methods
+ * \{ */
+
+inline Span<Input> LazyFunction::inputs() const
+{
+  return inputs_;
+}
+
+inline Span<Output> LazyFunction::outputs() const
+{
+  return outputs_;
+}
+
+inline void LazyFunction::execute(Params &params, const Context &context) const
+{
+  BLI_assert(this->always_used_inputs_available(params));
+  this->execute_impl(params, context);
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name #Params Inline Methods
+ * \{ */
+
+inline Params::Params(const LazyFunction &fn) : fn_(fn)
+{
+}
+
+inline void *Params::try_get_input_data_ptr(const int index) const
+{
+  return this->try_get_input_data_ptr_impl(index);
+}
+
+inline void *Params::try_get_input_data_ptr_or_request(const int index)
+{
+  return this->try_get_input_data_ptr_or_request_impl(index);
+}
+
+inline void *Params::get_output_data_ptr(const int index)
+{
+  return this->get_output_data_ptr_impl(index);
+}
+
+inline void Params::output_set(const int index)
+{
+  this->output_set_impl(index);
+}
+
+inline bool Params::output_was_set(const int index) const
+{
+  return this->output_was_set_impl(index);
+}
+
+inline ValueUsage Params::get_output_usage(const int index) const
+{
+  return this->get_output_usage_impl(index);
+}
+
+inline void Params::set_input_unused(const int index)
+{
+  this->set_input_unused_impl(index);
+}
+
+template<typename T> inline T Params::extract_input(const int index)
+{
+  void *data = this->try_get_input_data_ptr(index);
+  BLI_assert(data != nullptr);
+  T return_value = std::move(*static_cast<T *>(data));
+  return return_value;
+}
+
+template<typename T> inline const T &Params::get_input(const int index)
+{
+  const void *data = this->try_get_input_data_ptr(index);
+  BLI_assert(data != nullptr);
+  return *static_cast<const T *>(data);
+}
+
+template<typename T> inline T *Params::try_get_input_data_ptr_or_request(const int index)
+{
+  return static_cast<T *>(this->try_get_input_data_ptr_or_request(index));
+}
+
+template<typename T> inline void Params::set_output(const int index, T &&value)
+{
+  using DecayT = std::decay_t<T>;
+  void *data = this->get_output_data_ptr(index);
+  new (data) DecayT(std::forward<T>(value));
+  this->output_set(index);
+}
+
+/** \} */
+
+}  // namespace blender::fn::lazy_function