From 234ae7c044ea183c719799a5369b2cfcbc69fd27 Mon Sep 17 00:00:00 2001 From: NeilBrown Date: Sat, 20 Nov 2021 09:10:36 +1100 Subject: [PATCH] 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 --- csrc/oceani.mdc | 136 +++++++++++++++++++++++++++++++++++------------- 1 file changed, 99 insertions(+), 37 deletions(-) diff --git a/csrc/oceani.mdc b/csrc/oceani.mdc index f375db6..c2a19ce 100644 --- 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. +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 @@ -949,8 +955,12 @@ like "if" and the code following it. ###### parse context int scope_depth; + int scope_count; struct scope *scope_stack; +###### variable fields + int scope_start, scope_end; + ###### 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_count += 1; } 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; + c->scope_count += 1; } ###### 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 - 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; @@ -1015,6 +1030,7 @@ Each variable records a scope depth and is in one of four states: ###### 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 @@ -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; + 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); } } @@ -1082,13 +1102,15 @@ need to be freed. For this we need to be able to find it, so assume that #### 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 @@ -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 - enum closetype { CloseSequential, CloseParallel, CloseElse }; + enum closetype { CloseSequential, CloseFunction, CloseParallel, CloseElse }; ###### 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->scope_start = c->scope_count; c->in_scope = v; ## variable init return v; @@ -1185,6 +1208,19 @@ all pending-scope variables become conditionally scoped. 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) { @@ -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) - ? (*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) @@ -1211,7 +1247,9 @@ all pending-scope variables become conditionally scoped. */ 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; @@ -1258,6 +1296,11 @@ all pending-scope variables become conditionally scoped. 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; @@ -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. -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 - 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; - - 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 @@ -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); + 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); @@ -2411,6 +2470,7 @@ further detailed when Expression Lists are introduced. struct { struct binode *params; struct type *return_type; + struct variable *scope; 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); - 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); - var_block_close(c, CloseSequential, NULL); + var_block_close(c, CloseFunction, NULL); } + c->out_scope = NULL; 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->type->function.local_size = scope_finalize(c); + scope_finalize(c, v->type); } return all_ok; } -- 2.43.0