[PATCH olang 0/5] fix multiple variables

[PATCH olang 0/5] fix multiple variables

[Carlos Maniero]

The expressions in x86 performs stack instructions which was causing
conflicts with the space that was reserved for variables.

This patchset ensures that theses instructions no longer messes with the
stack.

Carlos Maniero (5):
  map: add function to retrieve all key-value pairs
  scope: make scope a bi-directional tree
  ast: checker: add function scope
  codegen: reset variable offset on block leave
  codegen: preserve function's variable stack location

 src/ast.h                                     |  1 +
 src/checker.c                                 |  1 +
 src/codegen_linux_x86_64.c                    | 47 ++++++++++++++++++-
 src/map.c                                     | 17 +++++++
 src/map.h                                     | 10 ++++
 src/scope.c                                   | 14 ++++++
 src/scope.h                                   |  2 +
 .../tests/0025_var_definition_nested.ol       | 35 ++++++++++++++
 tests/unit/map_test.c                         | 30 ++++++++++++
 9 files changed, 156 insertions(+), 1 deletion(-)
 create mode 100644 tests/integration/tests/0025_var_definition_nested.ol


base-commit: cb4b63f5879862d2f8282382128995d4e6eff76c
-- 
2.34.1

[PATCH olang 1/5] map: add function to retrieve all key-value pairs

[Carlos Maniero]

Signed-off-by: Carlos Maniero <carlos@maniero.me>
Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>
---
 src/map.c             | 17 +++++++++++++++++
 src/map.h             | 10 ++++++++++
 tests/unit/map_test.c | 30 ++++++++++++++++++++++++++++++
 3 files changed, 57 insertions(+)

diff --git a/src/map.c b/src/map.c
index 6665e18..a6bc3a3 100644
--- a/src/map.c
+++ b/src/map.c
@@ -80,6 +80,8 @@ bool
 map_put(map_t *map, char *key, void *value)
 {
     assert(map && key);
+    map->size++;
+
     uint32_t hash = u32_fnv1a_hash(key);
     map_entry_t *entry = map->entries + map_get_index(map, hash);
 
@@ -126,6 +128,21 @@ map_get_index(map_t *map, uint32_t hash)
     return hash & capacity_mask;
 }
 
+void
+map_get_kvs(map_t *map, map_kv_t **kvs)
+{
+    size_t index = 0;
+
+    for (size_t j = 0; j < map->capacity; ++j) {
+        map_entry_t *entry = map->entries + j;
+
+        while (entry != NULL && entry->key != NULL) {
+            kvs[index++] = (map_kv_t *)entry;
+            entry = entry->next;
+        }
+    }
+}
+
 static char *
 _strdup(const char *s, arena_t *arena)
 {
diff --git a/src/map.h b/src/map.h
index 123ad4d..6f8681c 100644
--- a/src/map.h
+++ b/src/map.h
@@ -37,8 +37,15 @@ typedef struct map
     arena_t *arena;
     map_entry_t *entries;
     size_t capacity;
+    size_t size;
 } map_t;
 
+typedef struct map_kv
+{
+    char *key;
+    void *value;
+} map_kv_t;
+
 typedef struct map_entry
 {
     char *key;
@@ -56,4 +63,7 @@ map_put(map_t *map, char *key, void *value);
 void *
 map_get(map_t *map, char *key);
 
+void
+map_get_kvs(map_t *map, map_kv_t **kvs);
+
 #endif /* MAP_H */
diff --git a/tests/unit/map_test.c b/tests/unit/map_test.c
index 449bca6..9497c7c 100644
--- a/tests/unit/map_test.c
+++ b/tests/unit/map_test.c
@@ -49,6 +49,7 @@ test_map_put_and_get(const MunitParameter params[], void *user_data_or_fixture)
     map_put(map, "n1", (void *)&n1);
     map_put(map, "n2", (void *)&n2);
 
+    assert_int(map->size, ==, 2);
     assert_int(*((int *)map_get(map, "n1")), ==, n1);
     assert_int(*((int *)map_get(map, "n2")), ==, n2);
 
@@ -61,6 +62,35 @@ test_map_put_and_get(const MunitParameter params[], void *user_data_or_fixture)
     return MUNIT_OK;
 }
 
+static MunitResult
+test_map_get_kvs(const MunitParameter params[], void *user_data_or_fixture)
+{
+    arena_t arena = arena_new(MAP_TEST_ARENA_CAPACITY);
+    map_t *map = map_new(&arena);
+
+    int n1 = 1;
+    int n2 = 2;
+
+    map_put(map, "n1", (void *)&n1);
+    map_put(map, "n2", (void *)&n2);
+
+    assert_int(map->size, ==, 2);
+
+    map_kv_t map_kvs[map->size];
+
+    map_get_kvs(map, (map_kv_t **)map_kvs);
+
+    assert_string_equal(map_kvs[0].key, "n1");
+    assert_int(*((int *)(map_kvs[0].value)), ==, 1);
+
+    assert_string_equal(map_kvs[1].key, "n2");
+    assert_int(*((int *)(map_kvs[1].value)), ==, 2);
+
+    arena_free(&arena);
+
+    return MUNIT_OK;
+}
+
 static MunitTest tests[] = {
     { "/test_create_new", test_create_new, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
     { "/test_map_put_and_get", test_map_put_and_get, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
-- 
2.34.1

[PATCH olang 2/5] scope: make scope a bi-directional tree

[Carlos Maniero]

In x86 architecture it is needed to reserve the stack space for local
variables. The code generators needs to compute this value from diving into
the tree from the function scope to the deepest level. So a
bi-directional scope are required.

Signed-off-by: Carlos Maniero <carlos@maniero.me>
Co-authored-by: Johnny Richard <johnny@johnnyrichard.com>
---
 src/scope.c | 14 ++++++++++++++
 src/scope.h |  2 ++
 2 files changed, 16 insertions(+)

diff --git a/src/scope.c b/src/scope.c
index 3271856..b23e865 100644
--- a/src/scope.c
+++ b/src/scope.c
@@ -33,6 +33,18 @@ scope_new(arena_t *arena)
     }
     scope->arena = arena;
     scope->symbols = map_new(arena);
+
+    // FIXME: create a list_new function to avoid spreading this.
+    list_t *children = (list_t *)arena_alloc(arena, sizeof(list_t));
+
+    if (children == NULL) {
+        fprintf(stderr, "[FATAL] Out of memory: scope_new: %s\n", strerror(errno));
+        exit(EXIT_FAILURE);
+    }
+
+    list_init(children, arena);
+
+    scope->children = children;
     return scope;
 }
 
@@ -89,6 +101,8 @@ scope_push(scope_t *scope)
     scope_t *child = scope_new(scope->arena);
     child->parent = scope;
 
+    list_append(scope->children, child);
+
     return child;
 }
 
diff --git a/src/scope.h b/src/scope.h
index ddb0cd0..7f7eaae 100644
--- a/src/scope.h
+++ b/src/scope.h
@@ -18,6 +18,7 @@
 #define SCOPE_H
 
 #include "arena.h"
+#include "list.h"
 #include "map.h"
 #include "string_view.h"
 
@@ -29,6 +30,7 @@ typedef struct symbol
 typedef struct scope
 {
     struct scope *parent;
+    list_t *children;
     arena_t *arena;
     map_t *symbols;
 } scope_t;
-- 
2.34.1

[PATCH olang 3/5] ast: checker: add function scope

[Carlos Maniero]

Signed-off-by: Carlos Maniero <carlos@maniero.me>
Co-authored-by: Johnny Richard <johnny@johnnyrichard.com>
---
 src/ast.h     | 1 +
 src/checker.c | 1 +
 2 files changed, 2 insertions(+)

diff --git a/src/ast.h b/src/ast.h
index 7d065c6..a45a271 100644
--- a/src/ast.h
+++ b/src/ast.h
@@ -60,6 +60,7 @@ typedef struct ast_fn_definition
     string_view_t identifier;
     type_t return_type;
     ast_node_t *block;
+    scope_t *scope;
 } ast_fn_definition_t;
 
 typedef struct ast_var_definition
diff --git a/src/checker.c b/src/checker.c
index 5925158..3b713f7 100644
--- a/src/checker.c
+++ b/src/checker.c
@@ -59,6 +59,7 @@ populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast)
         }
 
         case AST_NODE_FN_DEF: {
+            ast->as_fn_def.scope = scope;
             // FIXME: insert function symbol to scope
             populate_scope(checker, scope, ast->as_fn_def.block);
             return;
-- 
2.34.1

[PATCH olang 4/5] codegen: reset variable offset on block leave

[Carlos Maniero]

The block should reset the offset to avoid unnecessary stack consumption.

Signed-off-by: Carlos Maniero <carlos@maniero.me>
Co-authored-by: Johnny Richard <johnny@johnnyrichard.com>
---
 src/codegen_linux_x86_64.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/src/codegen_linux_x86_64.c b/src/codegen_linux_x86_64.c
index 4e0ea52..640c9fb 100644
--- a/src/codegen_linux_x86_64.c
+++ b/src/codegen_linux_x86_64.c
@@ -333,7 +333,7 @@ codegen_linux_x86_64_emit_expression(codegen_x86_64_t *codegen, ast_node_t *expr
 static void
 codegen_linux_x86_64_emit_block(codegen_x86_64_t *codegen, ast_block_t *block)
 {
-
+    size_t block_offset = codegen->base_offset;
     size_t nodes_len = list_size(block->nodes);
 
     for (size_t i = 0; i < nodes_len; ++i) {
@@ -414,6 +414,8 @@ codegen_linux_x86_64_emit_block(codegen_x86_64_t *codegen, ast_block_t *block)
             }
         }
     }
+
+    codegen->base_offset = block_offset;
 }
 
 static void
-- 
2.34.1

[PATCH olang 5/5] codegen: preserve function's variable stack location

[Carlos Maniero]

Since the x86 expressions uses stack instructions (push/pop), a prologue
is required to ensure the space reserved for variables are not modified
by these instructions.

Signed-off-by: Carlos Maniero <carlos@maniero.me>
Co-authored-by: Johnny Richard <johnny@johnnyrichard.com>
---
 src/codegen_linux_x86_64.c                    | 43 +++++++++++++++++++
 .../tests/0025_var_definition_nested.ol       | 35 +++++++++++++++
 2 files changed, 78 insertions(+)
 create mode 100644 tests/integration/tests/0025_var_definition_nested.ol

diff --git a/src/codegen_linux_x86_64.c b/src/codegen_linux_x86_64.c
index 640c9fb..3ce11a7 100644
--- a/src/codegen_linux_x86_64.c
+++ b/src/codegen_linux_x86_64.c
@@ -346,6 +346,7 @@ codegen_linux_x86_64_emit_block(codegen_x86_64_t *codegen, ast_block_t *block)
 
                 codegen_linux_x86_64_emit_expression(codegen, expr);
 
+                fprintf(codegen->out, "    mov %%rbp, %%rsp\n");
                 fprintf(codegen->out, "    ret\n");
 
                 break;
@@ -418,6 +419,40 @@ codegen_linux_x86_64_emit_block(codegen_x86_64_t *codegen, ast_block_t *block)
     codegen->base_offset = block_offset;
 }
 
+static size_t
+calculate_fn_local_size(scope_t *scope)
+{
+    assert(scope);
+
+    size_t local_size = 0;
+
+    map_kv_t kvs[scope->symbols->size];
+
+    map_get_kvs(scope->symbols, (map_kv_t **)kvs);
+
+    for (size_t i = 0; i < scope->symbols->size; ++i) {
+        // FIXME: symbols must have their types. Since we just have 8bytes
+        //        variables it is hard coded.
+        local_size += 8;
+    }
+
+    size_t max_child_local_size = 0;
+
+    list_item_t *item = list_head(scope->children);
+
+    while (item != NULL) {
+        size_t child_local_size = calculate_fn_local_size((scope_t *)item->value);
+
+        if (child_local_size > max_child_local_size) {
+            max_child_local_size = child_local_size;
+        }
+
+        item = list_next(item);
+    }
+
+    return local_size + max_child_local_size;
+}
+
 static void
 codegen_linux_x86_64_emit_function(codegen_x86_64_t *codegen, ast_fn_definition_t *fn)
 {
@@ -427,6 +462,14 @@ codegen_linux_x86_64_emit_function(codegen_x86_64_t *codegen, ast_fn_definition_
 
     fprintf(codegen->out, "    mov %%rsp, %%rbp\n");
 
+    size_t local_size = calculate_fn_local_size(fn->scope);
+
+    // TODO: get the local_size from function scope
+
+    if (local_size != 0) {
+        fprintf(codegen->out, "    sub $%ld, %%rsp\n", local_size);
+    }
+
     assert(block_node->kind == AST_NODE_BLOCK);
     ast_block_t block = block_node->as_block;
 
diff --git a/tests/integration/tests/0025_var_definition_nested.ol b/tests/integration/tests/0025_var_definition_nested.ol
new file mode 100644
index 0000000..fdbe903
--- /dev/null
+++ b/tests/integration/tests/0025_var_definition_nested.ol
@@ -0,0 +1,35 @@
+# Copyright (C) 2024 olang mantainers
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <https://www.gnu.org/licenses/>.
+
+fn main(): u32 {
+  var a: u32 = 1
+
+  if a == 1 {
+    var b: u32 = 43
+    var c: u32 = 2
+
+    return a + b - c
+  } else {
+    var b: u32 = 41
+
+    return a + b
+  }
+
+  return a
+}
+
+# TEST test_compile(exit_code=0)
+
+# TEST test_run_binary(exit_code=42)
-- 
2.34.1

[olang/patches/.build.yml] build success

[builds.sr.ht]

olang/patches/.build.yml: SUCCESS in 20s

[fix multiple variables][0] from [Carlos Maniero][1]

[0]: https://lists.sr.ht/~johnnyrichard/olang-devel/patches/55133
[1]: mailto:carlos@maniero.me

✓ #1333568 SUCCESS olang/patches/.build.yml https://builds.sr.ht/~johnnyrichard/job/1333568

Re: [PATCH olang 0/5] fix multiple variables

[Johnny Richard]

Great work! We are getting there my friend! <3

Applied.

Build started: https://builds.sr.ht/~johnnyrichard/job/1333586

To git.sr.ht:~johnnyrichard/olang
   cb4b63f..0d9ff9c  HEAD -> main