[Bug c++/105989] New: Coroutine frame space for temporaries in a co_await expression is not reused

[Bug c++/105989] New: Coroutine frame space for temporaries in a co_await expression is not reused

[michal.jankovic59 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105989

            Bug ID: 105989
           Summary: Coroutine frame space for temporaries in a co_await
                    expression is not reused
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: michal.jankovic59 at gmail dot com
  Target Milestone: ---

Created attachment 53142
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53142&action=edit
Minimal reproduction of the described issue.

Space in a coroutine frame that is allocated for temporaries in a co_await
expression (in particular the awaiter object) is not reused for subsequent
co_await-s. Writing the same co_await expression multiple times results in a
larger coroutine frame than using a for loop, where the space is only allocated
once. This is a bummer for me, as I would like to use coroutines for embedded
systems with limited memory, and every byte counts.

I would expect that the space in the coroutine frame for the temporaries of two
subsequent co_await expressions would overlap. This appears to work on Clang
(allthough it has a similar issue with HALO, where the space for the subroutine
frames do not overlap).

The attached minimal example shows the issue by logging allocations of the
coroutine frames; change the number of co_await expressions in coro_1() and the
size of the dummy array in the awaiter object to see that the space for the
awaiter is not reclaimed. Change it to 1 co_await in a for loop, and the
temporaries are only allocated once.

Compilation command (the issue is on all optimization levels, not just -O3):
g++ -std=c++20 -fcoroutines -O3 --save-temps report.cpp

gcc -v output:
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /build/gcc/src/gcc/configure
--enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-bootstrap
--prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man
--infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/
--with-linker-hash-style=gnu --with-system-zlib --enable-__cxa_atexit
--enable-cet=auto --enable-checking=release --enable-clocale=gnu
--enable-default-pie --enable-default-ssp --enable-gnu-indirect-function
--enable-gnu-unique-object --enable-linker-build-id --enable-lto
--enable-multilib --enable-plugin --enable-shared --enable-threads=posix
--disable-libssp --disable-libstdcxx-pch --disable-werror
--with-build-config=bootstrap-lto --enable-link-serialization=1
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.1.0 (GCC)

[Bug c++/105989] Coroutine frame space for temporaries in a co_await expression is not reused

[michal.jankovic59 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105989

--- Comment #1 from Michal Jankovič <michal.jankovic59 at gmail dot com> ---
Exploring further, this seems to be a symptom of a deeper issue - the coroutine
frame contains space for ALL variables of the coroutine, not just for the
maximally sized subset of the variables that can be alive across suspension.
Temporaries in co_await are just promoted to stored variables, so exhibit the
same problem.

This is easy to see when changing coro_1() body to:
  { std::byte _[500]; co_await coro_2(); }
  { std::byte _[500]; co_await coro_2(); }
  { std::byte _[500]; co_await coro_2(); }
  { std::byte _[500]; co_await coro_2(); }
  { std::byte _[500]; co_await coro_2(); }

The size of coro_1's frame is now 3408 - all of the variables are allocated
separately, even though they cannot be alive at the same time.

I would not call this a missed optimization - this seems like something that
should work on -O0, by using a smarter allocation scheme for the coroutine
frame.

[Bug c++/105989] Coroutine frame space for temporaries in a co_await expression is not reused

[michal.jankovic59 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105989

--- Comment #2 from Michal Jankovič <michal.jankovic59 at gmail dot com> ---
Reading through gcc/cp/coroutines.cc, it seems like the coroutine frame is
indeed composed as a flat struct with fields for all the local variables,
temps, and special stuff needed by the actor. 

Relevant code:
coro_make_frame_entry - adds a field to the coro_frame_type structure.
register_local_var_uses - here coro_make_frame_entry is called for each local
variable.
morph_fn_to_coro - here the coro_frame_type structure definition is created
from the collected fields.

Comments in the code state that the mid-end should be able to optimize out
unused fields from this struct, which currently does not happen, but even if it
did, this does not solve the overlapping of variables.

I think that instead of a flat struct, the frontend should generate a structure
recursively composed of unions of structures, having a union for each disjunct
scope (including an implicit scope for expression temporaries).

Example:

task task_1() {
  {
    char a[128];
    co_await task_2();
  }
  {
    char b[128];
    co_await task_3(get_temporary());

    static awaiter awaiter_not_stored_in_frame;
    co_await awaiter_not_stored_in_frame;
  }
}

Currently, this generates a coro frame struct that looks something like this:
struct coro_frame {
  // builtin state ...
  char a[128];
  awaiter task_2_awaiter;
  char b[128];
  int get_temporary_result;
  awaiter task_3_awaiter;  
  awaiter* awaiter_not_stored_in_frame;
};

Instead, the frontend could generate something like this:
struct coro_frame {
  // builtin state ...
  union {
    struct {
      char a[128];
      awaiter task_2_awaiter;
    };
    struct {
      char b[128];
      union {
        struct { 
          int get_temporary_result;
          awaiter task_3_awaiter; 
        };
        struct { awaiter* awaiter_not_stored_in_frame; };
      };
    };
  };
};

[Bug c++/105989] Coroutine frame space for temporaries in a co_await expression is not reused

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105989

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug c++/105989] Coroutine frame space for temporaries in a co_await expression is not reused

[michal.jankovic59 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105989

--- Comment #3 from Michal Jankovič <michal.jankovic59 at gmail dot com> ---
Created attachment 53273
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53273&action=edit
Experimental patch implementing the proposed transformation

This patch implements the proposed coroutine frame layout with nested structs
and unions.

[Bug c++/105989] Coroutine frame space for temporaries in a co_await expression is not reused

[michal.jankovic59 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105989

--- Comment #4 from Michal Jankovič <michal.jankovic59 at gmail dot com> ---
Comment on attachment 53273
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53273
Experimental patch implementing the proposed transformation

diff --git a/gcc/cp/coroutines.cc b/gcc/cp/coroutines.cc
index edb3b706ddc..ed1ac4decaf 100644
--- a/gcc/cp/coroutines.cc
+++ b/gcc/cp/coroutines.cc
@@ -1997,6 +1997,7 @@ struct local_var_info
   bool is_static;
   bool has_value_expr_p;
   location_t def_loc;
+  vec<tree, va_gc> *field_access_path;
 };

 /* For figuring out what local variable usage we have.  */
@@ -2009,6 +2010,26 @@ struct local_vars_transform
   hash_map<tree, local_var_info> *local_var_uses;
 };

+/* Build a COMPONENT_REF chain for accessing a nested variable in the
coroutine
+   frame.  */
+static tree
+build_local_var_frame_access_expr (local_vars_transform *lvt,
+                                  local_var_info *local_var)
+{
+  tree access_expr = lvt->actor_frame;
+
+  for (tree path_elem_id : *local_var->field_access_path)
+    {
+      tree path_elem_member = lookup_member (
+       TREE_TYPE (access_expr), path_elem_id, 1, 0, tf_warning_or_error);
+      access_expr = build3_loc (
+       lvt->loc, COMPONENT_REF, TREE_TYPE (path_elem_member),
+       access_expr, path_elem_member, NULL_TREE);
+    }
+
+  return access_expr;
+}
+
 static tree
 transform_local_var_uses (tree *stmt, int *do_subtree, void *d)
 {
@@ -2040,12 +2061,7 @@ transform_local_var_uses (tree *stmt, int *do_subtree,
void *d)
          if (local_var.field_id == NULL_TREE)
            continue; /* Wasn't used.  */

-         tree fld_ref
-           = lookup_member (lvd->coro_frame_type, local_var.field_id,
-                            /*protect=*/1, /*want_type=*/0,
-                            tf_warning_or_error);
-         tree fld_idx = build3_loc (lvd->loc, COMPONENT_REF, TREE_TYPE (lvar),
-                                    lvd->actor_frame, fld_ref, NULL_TREE);
+         tree fld_idx = build_local_var_frame_access_expr (lvd, &local_var);
          local_var.field_idx = fld_idx;
          SET_DECL_VALUE_EXPR (lvar, fld_idx);
          DECL_HAS_VALUE_EXPR_P (lvar) = true;
@@ -3873,14 +3889,24 @@ analyze_fn_parms (tree orig)
 /* Small helper for the repetitive task of adding a new field to the coro
    frame type.  */

+static void
+coro_make_frame_entry_id (tree *field_list, tree id, tree fld_type,
+                         location_t loc)
+{
+  tree decl = build_decl (loc, FIELD_DECL, id, fld_type);
+  DECL_CHAIN (decl) = *field_list;
+  *field_list = decl;
+}
+
+/* Same as coro_make_frame_entry_id, but creates an identifier from string. 
*/
+
 static tree
 coro_make_frame_entry (tree *field_list, const char *name, tree fld_type,
                       location_t loc)
 {
   tree id = get_identifier (name);
-  tree decl = build_decl (loc, FIELD_DECL, id, fld_type);
-  DECL_CHAIN (decl) = *field_list;
-  *field_list = decl;
+  coro_make_frame_entry_id (field_list, id, fld_type, loc);
+
   return id;
 }

@@ -3894,6 +3920,8 @@ struct local_vars_frame_data
   location_t loc;
   bool saw_capture;
   bool local_var_seen;
+  tree orig;
+  vec<tree, va_gc> *field_access_path;
 };

 /* A tree-walk callback that processes one bind expression noting local
@@ -3912,6 +3940,21 @@ register_local_var_uses (tree *stmt, int *do_subtree,
void *d)

   if (TREE_CODE (*stmt) == BIND_EXPR)
     {
+      tree scope_field_id = NULL_TREE;
+      if (lvd->nest_depth != 0)
+       {
+         /* Create identifier under which fields for this bind-expression will
+            be accessed.  */
+         char *scope_field_name
+           = xasprintf ("_Scope%u_%u", lvd->nest_depth, lvd->bind_indx);
+         scope_field_id = get_identifier (scope_field_name);
+         free (scope_field_name);
+
+         vec_safe_push (lvd->field_access_path, scope_field_id);
+       }
+
+      tree scope_variables = NULL_TREE;
+
       tree lvar;
       unsigned serial = 0;
       for (lvar = BIND_EXPR_VARS (*stmt); lvar != NULL;
@@ -3980,17 +4023,99 @@ register_local_var_uses (tree *stmt, int *do_subtree,
void *d)

          /* TODO: Figure out if we should build a local type that has any
             excess alignment or size from the original decl.  */
-         local_var.field_id = coro_make_frame_entry (lvd->field_list, buf,
+
+         local_var.field_id = coro_make_frame_entry (&scope_variables, buf,
                                                      lvtype, lvd->loc);
          free (buf);
          /* We don't walk any of the local var sub-trees, they won't contain
             any bind exprs.  */
+
+         local_var.field_access_path = make_tree_vector_copy (
+           lvd->field_access_path);
+         vec_safe_push (local_var.field_access_path, local_var.field_id);
        }
+
+      unsigned bind_indx = lvd->bind_indx;
+      tree* parent_field_list = lvd->field_list;
+
+      /* Collect the scope structs of child bind-expressions when recursing. 
*/
+      tree child_scopes = NULL_TREE;
+      lvd->field_list = &child_scopes;
+
+      /* Create identifier under which fields for child bind-expressions will
be
+        accessed.  */
+      char *child_scopes_field_name
+       = xasprintf ("_Scope_list%u_%u", lvd->nest_depth, bind_indx);
+      tree child_scopes_field_id = get_identifier (child_scopes_field_name);
+      free (child_scopes_field_name);
+
+      /* Recurse to child bind expressions.  */
       lvd->bind_indx++;
       lvd->nest_depth++;
+      vec_safe_push (lvd->field_access_path, child_scopes_field_id);
       cp_walk_tree (&BIND_EXPR_BODY (*stmt), register_local_var_uses, d,
NULL);
       *do_subtree = 0; /* We've done this.  */
+      lvd->field_access_path->pop ();
       lvd->nest_depth--;
+
+      /* Restore the parent field list.  */
+      lvd->field_list = parent_field_list;
+
+      if (child_scopes != NULL_TREE)
+       {
+         /* Create a union to house the child scopes, so that they are
+            overlapped in the coroutine frame.  */
+         char *child_scopes_union_name_suffix
+           = xasprintf ("Frame_scope_list%u_%u", lvd->nest_depth, bind_indx);
+         tree child_scopes_union_name = get_fn_local_identifier (
+           lvd->orig, child_scopes_union_name_suffix);
+         free (child_scopes_union_name_suffix);
+         tree child_scopes_union
+           = xref_tag (union_type, child_scopes_union_name);
+         DECL_CONTEXT (TYPE_NAME (child_scopes_union)) = current_scope ();
+         child_scopes_union = begin_class_definition (child_scopes_union);
+         TYPE_FIELDS (child_scopes_union) = child_scopes;
+         TYPE_BINFO (child_scopes_union) = make_tree_binfo (0);
+         BINFO_OFFSET (TYPE_BINFO (child_scopes_union)) = size_zero_node;
+         BINFO_TYPE (TYPE_BINFO (child_scopes_union)) = child_scopes_union;
+         child_scopes_union = finish_struct (child_scopes_union, NULL_TREE);
+
+         /* Add it to the current scope fields.  */
+         coro_make_frame_entry_id (
+           &scope_variables, child_scopes_field_id,
+           child_scopes_union, lvd->loc);
+       }
+
+      if (lvd->nest_depth == 0)
+       {
+         /* The outermost scope contains special variables, embed them
directly
+            in the coroutine frame without nesting.  */
+         *lvd->field_list = scope_variables;
+       } else
+       {
+         /* Create a struct for housing the vars of this bind-expr
+            in the coroutine frame.  */
+         char *scope_struct_name_suffix
+           = xasprintf ("Frame_scope%u_%u", lvd->nest_depth, bind_indx);
+         tree scope_struct_name
+           = get_fn_local_identifier (lvd->orig, scope_struct_name_suffix);
+         free (scope_struct_name_suffix);
+         tree scope_struct = xref_tag (record_type, scope_struct_name);
+         DECL_CONTEXT (TYPE_NAME (scope_struct)) = current_scope ();
+         scope_struct = begin_class_definition (scope_struct);
+         TYPE_FIELDS (scope_struct) = scope_variables;
+         TYPE_BINFO (scope_struct) = make_tree_binfo (0);
+         BINFO_OFFSET (TYPE_BINFO (scope_struct)) = size_zero_node;
+         BINFO_TYPE (TYPE_BINFO (scope_struct)) = scope_struct;
+         scope_struct = finish_struct (scope_struct, NULL_TREE);
+
+         /* Add the scope struct to the parent field list.  */
+         coro_make_frame_entry_id (parent_field_list, scope_field_id,
+                                   scope_struct,
+                                   lvd->loc);
+
+         lvd->field_access_path->pop ();
+       }
     }
   return NULL_TREE;
 }
@@ -4487,7 +4612,8 @@ morph_fn_to_coro (tree orig, tree *resumer, tree
*destroyer)
      would expect to delete unused entries later.  */
   hash_map<tree, local_var_info> local_var_uses;
   local_vars_frame_data local_vars_data
-    = {&field_list, &local_var_uses, 0, 0, fn_start, false, false};
+    = {&field_list, &local_var_uses, 0, 0, fn_start, false, false, orig,
+       make_tree_vector ()};
   cp_walk_tree (&fnbody, register_local_var_uses, &local_vars_data, NULL);

   /* Tie off the struct for now, so that we can build offsets to the
diff --git a/gcc/testsuite/g++.dg/coroutines/pr105989.C
b/gcc/testsuite/g++.dg/coroutines/pr105989.C
new file mode 100644
index 00000000000..c8b9be634aa
--- /dev/null
+++ b/gcc/testsuite/g++.dg/coroutines/pr105989.C
@@ -0,0 +1,124 @@
+//  { dg-do run }
+
+#include <cstddef>
+
+#include "coro.h"
+
+struct promise;
+
+struct task
+{
+  coro::coroutine_handle<promise> handle;
+
+  ~task ()
+  {
+    if (handle)
+      {
+       handle.destroy ();
+      }
+  }
+};
+
+std::size_t frame_size = 0u;
+
+struct promise
+{
+  coro::coroutine_handle<> continuation = coro::noop_coroutine ();
+
+  auto get_return_object () noexcept
+  {
+    return task{coro::coroutine_handle<promise>::from_promise (*this)};
+  }
+
+  void unhandled_exception () noexcept {}
+
+  void return_void () {}
+
+  auto initial_suspend () noexcept { return coro::suspend_always{}; }
+
+  auto final_suspend () noexcept
+  {
+    struct awaiter_type : coro::suspend_always
+    {
+      auto await_suspend (coro::coroutine_handle <promise> handle) noexcept
+      {
+       return handle.promise ().continuation;
+      }
+    };
+
+    return awaiter_type{};
+  }
+
+  void * operator new (std::size_t size)
+  {
+    frame_size = size;
+    return new std::byte[size];
+  }
+
+  void operator delete (void *ptr, std::size_t size)
+  {
+    return delete[] static_cast<std::byte *>(ptr);
+  }
+};
+
+auto operator co_await (task &&t)
+{
+  struct awaiter_type : coro::suspend_always
+  {
+    coro::coroutine_handle<promise> handle;
+
+    auto await_suspend (coro::coroutine_handle<promise> continuation)
+    {
+      handle.promise ().continuation = continuation;
+      return handle;
+    }
+  };
+
+  return awaiter_type{{}, t.handle};
+}
+
+template<typename... Args>
+struct coro::coroutine_traits<task, Args...>
+{
+  using promise_type = promise;
+};
+
+auto coro_3 () -> task
+{
+  co_return;
+}
+
+std::byte *arr_ptr = nullptr;
+
+task coro_2 ()
+{
+  {
+    std::byte arr[256];
+    co_await coro_3 ();
+    arr_ptr = arr;
+  }
+  {
+    std::byte arr[256];
+    co_await coro_3 ();
+    arr_ptr = arr;
+  }
+}
+
+task coro_1 ()
+{
+  std::byte arr[256];
+  co_await coro_3 ();
+  arr_ptr = arr;
+}
+
+int main ()
+{
+  coro_1 ();
+  auto first_frame_size = frame_size;
+  coro_2 ();
+  auto second_frame_size = frame_size;
+
+  /* coro_1 frame should be the same size as coro_2 frame.  */
+
+  return first_frame_size == second_frame_size ? 0 : 1;
+}

[Bug c++/105989] Coroutine frame space for temporaries in a co_await expression is not reused

[michal.jankovic59 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105989

Michal Jankovič <michal.jankovic59 at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #53273|0                           |1
        is obsolete|                            |

--- Comment #5 from Michal Jankovič <michal.jankovic59 at gmail dot com> ---
Created attachment 53290
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53290&action=edit
Patch implementing the proposed transformation

Submitted patch implementing the proposed transformation, along with a test
case.