oceani: improve construction of per-function stack frame

The stack-frame management was confused - not properly transitioned from
a single function to multiple functions.
Now we pass in the function to be processed, and it has a known list of
variables that were in-scope in that function.

We track when each variable went into or out-of scope, sort them, and
re-use frame space for variables which have already gone out-of-scope.

Signed-off-by: NeilBrown <neil@brown.name>

diff --git a/csrc/oceani.mdc b/csrc/oceani.mdc
index f375db62f818b5f07faf7cefb6d2cebef05ec562..c2a19ce0c7744190c2fedba910f7205c851e83db 100644 (file)
--- a/csrc/oceani.mdc
+++ b/csrc/oceani.mdc
@@ -935,6 +935,12 @@ is used to distinguish between the first of a set of parallel scopes,
 in which declared variables must not be in scope, and subsequent
 branches, whether they may already be conditionally scoped.
 
 in which declared variables must not be in scope, and subsequent
 branches, whether they may already be conditionally scoped.
 

+We need a total ordering of scopes so we can easily compare to variables
+to see if they are concurrently in scope.  To achieve this we record a
+`scope_count` which is actually a count of both beginnings and endings
+of scopes.  Then each variable has a record of the scope count where it
+enters scope, and where it leaves.
+

 To push a new frame *before* any code in the frame is parsed, we need a
 grammar reduction.  This is most easily achieved with a grammar
 element which derives the empty string, and creates the new scope when
 To push a new frame *before* any code in the frame is parsed, we need a
 grammar reduction.  This is most easily achieved with a grammar
 element which derives the empty string, and creates the new scope when


@@ -949,8 +955,12 @@ like "if" and the code following it.
 
 ###### parse context
        int scope_depth;
 
 ###### parse context
        int scope_depth;

+       int scope_count;

        struct scope *scope_stack;
 
        struct scope *scope_stack;
 

+###### variable fields
+       int scope_start, scope_end;
+

 ###### ast functions
        static void scope_pop(struct parse_context *c)
        {
 ###### ast functions
        static void scope_pop(struct parse_context *c)
        {


@@ -959,6 +969,7 @@ like "if" and the code following it.
                c->scope_stack = s->parent;
                free(s);
                c->scope_depth -= 1;
                c->scope_stack = s->parent;
                free(s);
                c->scope_depth -= 1;

+               c->scope_count += 1;

        }
 
        static void scope_push(struct parse_context *c)
        }
 
        static void scope_push(struct parse_context *c)


@@ -969,6 +980,7 @@ like "if" and the code following it.
                s->parent = c->scope_stack;
                c->scope_stack = s;
                c->scope_depth += 1;
                s->parent = c->scope_stack;
                c->scope_stack = s;
                c->scope_depth += 1;

+               c->scope_count += 1;

        }
 
 ###### Grammar
        }
 
 ###### Grammar


@@ -1005,7 +1017,10 @@ Each variable records a scope depth and is in one of four states:
 
 - "out of scope".  The variable is neither in scope nor conditionally
   in scope.  It is permanently out of scope now and can be removed from
 
 - "out of scope".  The variable is neither in scope nor conditionally
   in scope.  It is permanently out of scope now and can be removed from

-  the "in scope" stack.
+  the "in scope" stack.  When a variable becomes out-of-scope it is
+  moved to a separate list (`out_scope`) of variables which have fully
+  known scope.  This will be used at the end of each function to assign
+  each variable a place in the stack frame.

 
 ###### variable fields
        int depth, min_depth;
 
 ###### variable fields
        int depth, min_depth;


@@ -1015,6 +1030,7 @@ Each variable records a scope depth and is in one of four states:
 ###### parse context
 
        struct variable *in_scope;
 ###### parse context
 
        struct variable *in_scope;

+       struct variable *out_scope;

 
 All variables with the same name are linked together using the
 'previous' link.  Those variable that have been affirmatively merged all
 
 All variables with the same name are linked together using the
 'previous' link.  Those variable that have been affirmatively merged all


@@ -1052,6 +1068,10 @@ need to be freed.  For this we need to be able to find it, so assume that
                            v->merged == secondary->merged) {
                                v->scope = OutScope;
                                v->merged = primary;
                            v->merged == secondary->merged) {
                                v->scope = OutScope;
                                v->merged = primary;

+                               if (v->scope_start < primary->scope_start)
+                                       primary->scope_start = v->scope_start;
+                               if (v->scope_end > primary->scope_end)
+                                       primary->scope_end = v->scope_end;      // NOTEST

                                variable_unlink_exec(v);
                        }
        }
                                variable_unlink_exec(v);
                        }
        }


@@ -1082,13 +1102,15 @@ need to be freed.  For this we need to be able to find it, so assume that
 
 #### Manipulating Bindings
 
 
 #### Manipulating Bindings
 

-When a name is conditionally visible, a new declaration discards the
-old binding - the condition lapses.  Conversely a usage of the name
-affirms the visibility and extends it to the end of the containing
-block - i.e. the block that contains both the original declaration and
-the latest usage.  This is determined from `min_depth`.  When a
-conditionally visible variable gets affirmed like this, it is also
-merged with other conditionally visible variables with the same name.
+When a name is conditionally visible, a new declaration discards the old
+binding - the condition lapses.  Similarly when we reach the end of a
+function (outermost non-global scope) any conditional scope must lapse.
+Conversely a usage of the name affirms the visibility and extends it to
+the end of the containing block - i.e.  the block that contains both the
+original declaration and the latest usage.  This is determined from
+`min_depth`.  When a conditionally visible variable gets affirmed like
+this, it is also merged with other conditionally visible variables with
+the same name.

 
 When we parse a variable declaration we either report an error if the
 name is currently bound, or create a new variable at the current nest
 
 When we parse a variable declaration we either report an error if the
 name is currently bound, or create a new variable at the current nest


@@ -1123,7 +1145,7 @@ we need to mark all pending-scope variable as out-of-scope.  Otherwise
 all pending-scope variables become conditionally scoped.
 
 ###### ast
 all pending-scope variables become conditionally scoped.
 
 ###### ast

-       enum closetype { CloseSequential, CloseParallel, CloseElse };
+       enum closetype { CloseSequential, CloseFunction, CloseParallel, CloseElse };

 
 ###### ast functions
 
 
 ###### ast functions
 


@@ -1152,6 +1174,7 @@ all pending-scope variables become conditionally scoped.
                v->min_depth = v->depth = c->scope_depth;
                v->scope = InScope;
                v->in_scope = c->in_scope;
                v->min_depth = v->depth = c->scope_depth;
                v->scope = InScope;
                v->in_scope = c->in_scope;

+               v->scope_start = c->scope_count;

                c->in_scope = v;
                ## variable init
                return v;
                c->in_scope = v;
                ## variable init
                return v;


@@ -1185,6 +1208,19 @@ all pending-scope variables become conditionally scoped.
                return v;
        }
 
                return v;
        }
 

+       static int var_refile(struct parse_context *c, struct variable *v)
+       {
+               /* Variable just went out of scope.  Add it to the out_scope
+                * list, sorted by ->scope_start
+                */
+               struct variable **vp = &c->out_scope;
+               while ((*vp) && (*vp)->scope_start < v->scope_start)
+                       vp = &(*vp)->in_scope;
+               v->in_scope = *vp;
+               *vp = v;
+               return 0;               
+       }
+

        static void var_block_close(struct parse_context *c, enum closetype ct,
                                    struct exec *e)
        {
        static void var_block_close(struct parse_context *c, enum closetype ct,
                                    struct exec *e)
        {


@@ -1202,7 +1238,7 @@ all pending-scope variables become conditionally scoped.
                for (vp = &c->in_scope;
                     (v = *vp) && v->min_depth > c->scope_depth;
                     (v->scope == OutScope || v->name->var != v)
                for (vp = &c->in_scope;
                     (v = *vp) && v->min_depth > c->scope_depth;
                     (v->scope == OutScope || v->name->var != v)

-                    ? (*vp =  v->in_scope, 0)
+                    ? (*vp =  v->in_scope, var_refile(c, v))

                     : ( vp = &v->in_scope, 0)) {
                        v->min_depth = c->scope_depth;
                        if (v->name->var != v)
                     : ( vp = &v->in_scope, 0)) {
                        v->min_depth = c->scope_depth;
                        if (v->name->var != v)


@@ -1211,7 +1247,9 @@ all pending-scope variables become conditionally scoped.
                                 */
                                continue;
                        v->min_depth = c->scope_depth;
                                 */
                                continue;
                        v->min_depth = c->scope_depth;

-                       if (v->scope == InScope && e) {
+                       if (v->scope == InScope)
+                               v->scope_end = c->scope_count;
+                       if (v->scope == InScope && e && !v->global) {

                                /* This variable gets cleaned up when 'e' finishes */
                                variable_unlink_exec(v);
                                v->cleanup_exec = e;
                                /* This variable gets cleaned up when 'e' finishes */
                                variable_unlink_exec(v);
                                v->cleanup_exec = e;


@@ -1258,6 +1296,11 @@ all pending-scope variables become conditionally scoped.
                                        abort();                // NOTEST
                                }
                                break;
                                        abort();                // NOTEST
                                }
                                break;

+                       case CloseFunction:
+                               if (v->scope == CondScope)
+                                       /* Condition cannot continue past end of function */
+                                       v->scope = InScope;
+                               /* fallthrough */

                        case CloseSequential:
                                if (v->type == Tlabel)
                                        v->scope = PendingScope;
                        case CloseSequential:
                                if (v->type == Tlabel)
                                        v->scope = PendingScope;


@@ -1367,35 +1410,50 @@ tell if it was set or not later.
 As global values are found -- struct field initializers, labels etc --
 `global_alloc()` is called to record the value in the global frame.
 
 As global values are found -- struct field initializers, labels etc --
 `global_alloc()` is called to record the value in the global frame.
 

-When the program is fully parsed, we need to walk the list of variables
-to find any that weren't merged away and that aren't global, and to
-calculate the frame size and assign a frame position for each
-variable.  For this we have `scope_finalize()`.
+When the program is fully parsed, each function is analysed, we need to
+walk the list of variables local to that function and assign them an
+offset in the stack frame.  For this we have `scope_finalize()`.
+
+We keep the stack from dense by re-using space for between variables
+that are not in scope at the same time.  The `out_scope` list is sorted
+by `scope_start` and as we process a varible, we move it to an FIFO
+stack.  For each variable we consider, we first discard any from the
+stack anything that went out of scope before the new variable came in.
+Then we place the new variable just after the one at the top of the
+stack.

 
 ###### ast functions
 
 
 ###### ast functions
 

-       static int scope_finalize(struct parse_context *c)
+       static void scope_finalize(struct parse_context *c, struct type *ft)

        {
        {

-               struct binding *b;

                int size = 0;
                int size = 0;

-
-               for (b = c->varlist; b; b = b->next) {
-                       struct variable *v;
-                       for (v = b->var; v; v = v->previous) {
-                               struct type *t = v->type;
-                               if (v->merged != v)
-                                       continue;
-                               if (v->global)
-                                       continue;
-                               if (!t)
-                                       continue;
-                               if (size & (t->align - 1))
-                                       size = (size + t->align) & ~(t->align-1);
-                               v->frame_pos = size;
-                               size += v->type->size;
-                       }
+               struct variable *next = ft->function.scope;
+               struct variable *done = NULL;
+               while (next) {
+                       struct variable *v = next;
+                       struct type *t = v->type;
+                       int pos;
+                       next = v->in_scope;
+                       if (v->merged != v)
+                               continue;
+                       if (!t)
+                               continue;
+                       while (done && done->scope_end < v->scope_start)
+                               done = done->in_scope;
+                       if (done)
+                               pos = done->frame_pos + done->type->size;
+                       else
+                               pos = 0;
+                       if (pos & (t->align - 1))
+                               pos = (pos + t->align) & ~(t->align-1);
+                       v->frame_pos = pos;
+                       if (size < pos + v->type->size)
+                               size = pos + v->type->size;
+                       v->in_scope = done;
+                       done = v;

                }
                }

-               return size;
+               c->out_scope = NULL;
+               ft->function.local_size = size;

        }
 
 ###### free context storage
        }
 
 ###### free context storage


@@ -1549,6 +1607,7 @@ also want to know what sort of bracketing to use.
                        do_indent(indent, "/* FREE");
                        for (v = e->to_free; v; v = v->next_free) {
                                printf(" %.*s", v->name->name.len, v->name->name.txt);
                        do_indent(indent, "/* FREE");
                        for (v = e->to_free; v; v = v->next_free) {
                                printf(" %.*s", v->name->name.len, v->name->name.txt);

+                               printf("[%d,%d]", v->scope_start, v->scope_end);

                                if (v->frame_pos >= 0)
                                        printf("(%d+%d)", v->frame_pos,
                                               v->type ? v->type->size:0);
                                if (v->frame_pos >= 0)
                                        printf("(%d+%d)", v->frame_pos,
                                               v->type ? v->type->size:0);


@@ -2411,6 +2470,7 @@ further detailed when Expression Lists are introduced.
        struct {
                struct binode *params;
                struct type *return_type;
        struct {
                struct binode *params;
                struct type *return_type;

+               struct variable *scope;

                int local_size;
        } function;
 
                int local_size;
        } function;
 


@@ -4778,13 +4838,15 @@ is a bit more interesting at this level.
                        name->type->function.params = reorder_bilist(args);
                        name->type->function.return_type = ret;
                        global_alloc(c, name->type, name, &fn);
                        name->type->function.params = reorder_bilist(args);
                        name->type->function.return_type = ret;
                        global_alloc(c, name->type, name, &fn);

-                       var_block_close(c, CloseSequential, code);
+                       var_block_close(c, CloseFunction, code);
+                       name->type->function.scope = c->out_scope;

                } else {
                        free_binode(args);
                        free_type(ret);
                        free_exec(code);
                } else {
                        free_binode(args);
                        free_type(ret);
                        free_exec(code);

-                       var_block_close(c, CloseSequential, NULL);
+                       var_block_close(c, CloseFunction, NULL);

                }
                }

+               c->out_scope = NULL;

                return name;
        }
 
                return name;
        }
 


@@ -4871,7 +4933,7 @@ is a bit more interesting at this level.
                                         v->where_decl, v->type->function.return_type, 0, NULL);
                        }
 
                                         v->where_decl, v->type->function.return_type, 0, NULL);
                        }
 

-                       v->type->function.local_size = scope_finalize(c);
+                       scope_finalize(c, v->type);

                }
                return all_ok;
        }
                }
                return all_ok;
        }