gas: Optimize the stack utilization

Until now, every computation was pushed onto stack witch creates
unnecessary stack manipulation and makes the generated code hard to read
and understand.

Now, the latest computation is stored and could be either a literal or a
value on a register.

When it is a register we may need to push the value to stack to avoid
data loss. Now if it is a literal, hence, we can just set the value onto
a register.

  example/main.pipa before this commit:

    .global _start
    .text
    _start:
      push %rbp
      mov %rsp, %rbp
      mov $69, %rax    ; <- There is no reason to store data in rax
      mov %rax, %rdi
      mov $60, %rax
      syscall
      pop %rbp

  example/main.pipa after this commit:

    .global _start
    .text
    _start:
      push %rbp
      mov %rsp, %rbp
      mov $69, %rdi   ; <- Fixed!
      mov $60, %rax
      syscall
      pop %rbp

  example/variables.pipa before this commit:

    .global _start
    .text
    _start:
      push %rbp
      mov %rsp, %rbp
      mov $12, %rax
      mov %rax, -8(%rbp)
      mov $32, %rax
      mov %rax, -16(%rbp)
      mov -8(%rbp), %rax
      mov %rax, -32(%rbp)
      mov -16(%rbp), %rax
      mov -32(%rbp), %rcx
      add %rcx, %rax
      mov %rax, -32(%rbp)
      mov $2, %rax
      mov -32(%rbp), %rcx
      mul %rcx
      mov %rax, -24(%rbp)
      mov $1, %rax
      mov %rax, -40(%rbp)
      mov $33, %rax
      mov %rax, -48(%rbp)
      mov -24(%rbp), %rax
      mov -48(%rbp), %rcx
      sub %rcx, %rax
      mov -40(%rbp), %rcx
      add %rcx, %rax
      mov %rax, -32(%rbp)
      mov $2, %rax
      mov %rax, -40(%rbp)
      mov -32(%rbp), %rax
      mov -40(%rbp), %rcx
      xor %rdx, %rdx
      div %rcx
      mov %rax, %rdi
      mov $60, %rax
      syscall
      pop %rbp

  example/variables.pipa after this commit:

    .global _start
    .text
    _start:
      push %rbp
      mov %rsp, %rbp
      mov $12, -8(%rbp)
      mov $32, -16(%rbp)
      mov -8(%rbp), %rax
      mov %rax, -32(%rbp)
      mov -16(%rbp), %rax
      mov -32(%rbp), %rcx
      add %rcx, %rax
      mov %rax, -32(%rbp)
      mov -32(%rbp), %rcx
      mov $2, %rax
      mul %rcx
      mov %rax, -24(%rbp)
      mov -24(%rbp), %rax
      mov $33, %rcx
      sub %rcx, %rax
      mov $1, %rcx
      add %rcx, %rax
      mov %rax, -32(%rbp)
      mov -32(%rbp), %rax
      mov $2, %rcx
      xor %rdx, %rdx
      div %rcx
      mov %rax, %rdi
      mov $60, %rax
      syscall
      pop %rbp

Less 8 instructions!

Signed-off-by: Carlos Maniero <carlosmaniero@gmail.com>
Reviewed-by: Johnny Richard <johnny@johnnyrichard.com>

2 files changed, 76 insertions, 8 deletions

diff --git a/src/gas_assembly_generator.c b/src/gas_assembly_generator.c
index 5091120..fab4cd2 100644
--- a/src/gas_assembly_generator.c
+++ b/src/gas_assembly_generator.c
@@ -41,6 +41,19 @@ gas_assembly_generator_compile_variable_declaration(gas_assembly_generator_t *ge
 static void
 gas_assembly_generator_compile_variable(gas_assembly_generator_t *gen, ast_variable_t *variable);
 
+static void
+gas_assembly_generator_set_latest_evaluation_as_literal(gas_assembly_generator_t *gen, int64_t value)
+{
+  gen->latest_evaluation =
+    (evaluation_result_t){ .kind = EVALUATION_RESULT_LITERAL_INTEGER, .data = { .literal_int = value } };
+}
+
+static void
+gas_assembly_generator_set_latest_evaluation_as_register(gas_assembly_generator_t *gen)
+{
+  gen->latest_evaluation = (evaluation_result_t){ .kind = EVALUATION_RESULT_REGISTER };
+}
+
 typedef struct ref_entry_t
 {
   ast_identifier_t *id;
@@ -61,7 +74,6 @@ ref_entry_new(void)
   return entry;
 }
 
-
 void
 gas_assembly_generator_init(gas_assembly_generator_t *gen, FILE *stream)
 {
@@ -74,6 +86,8 @@ gas_assembly_generator_init(gas_assembly_generator_t *gen, FILE *stream)
 void
 gas_assembly_generator_compile(gas_assembly_generator_t *gen, ast_node_t *ast)
 {
+  gen->latest_evaluation.kind = EVALUATION_RESULT_VOID;
+
   switch (ast->kind) {
     case AST_BINARY_OPERATION:
       gas_assembly_generator_binary_operation(gen, &ast->data.binary_operation);
@@ -131,7 +145,11 @@ gas_assembly_generator_compile_return_stmt(gas_assembly_generator_t *gen, ast_re
 
   gas_assembly_generator_compile(gen, return_stmt->argument);
 
-  fprintf(gen->stream, "  mov %%rax, %%rdi\n");
+  if (gen->latest_evaluation.kind == EVALUATION_RESULT_LITERAL_INTEGER) {
+    fprintf(gen->stream, "  mov $%ld, %%rdi\n", gen->latest_evaluation.data.literal_int);
+  } else {
+    fprintf(gen->stream, "  mov %%rax, %%rdi\n");
+  }
   fprintf(gen->stream, "  mov $60, %%rax\n");
   fprintf(gen->stream, "  syscall\n");
 }
@@ -147,7 +165,17 @@ gas_assembly_generator_compile_variable_declaration(gas_assembly_generator_t *ge
   *entry = (ref_entry_t){ .id = &variable_declaration->identifier, .stack_offset = gen->stack_offset };
   vector_push_back(gen->refs, entry);
 
-  fprintf(gen->stream, "  mov %%rax, %d(%%rbp)\n", entry->stack_offset);
+  switch (gen->latest_evaluation.kind) {
+    case EVALUATION_RESULT_LITERAL_INTEGER:
+      fprintf(gen->stream, "  mov $%ld, %d(%%rbp)\n", gen->latest_evaluation.data.literal_int, entry->stack_offset);
+      break;
+    case EVALUATION_RESULT_REGISTER:
+      fprintf(gen->stream, "  mov %%rax, %d(%%rbp)\n", entry->stack_offset);
+      break;
+    case EVALUATION_RESULT_VOID:
+      assert(false && "Unexpected void result for variable declaration");
+      // FIXME: store the latest node at latest evaluation and print_ast
+  }
 }
 
 static void
@@ -163,6 +191,7 @@ gas_assembly_generator_compile_variable(gas_assembly_generator_t *gen, ast_varia
   }
   assert(entry && "reference not found");
   fprintf(gen->stream, "  mov %d(%%rbp), %%rax\n", entry->stack_offset);
+  gas_assembly_generator_set_latest_evaluation_as_register(gen);
 }
 
 static void
@@ -170,7 +199,7 @@ gas_assembly_generator_compile_literal(gas_assembly_generator_t *gen, ast_litera
 {
   switch (literal->kind) {
     case AST_LITERAL_INTEGER:
-      fprintf(gen->stream, "  mov $%d, %%rax\n", literal->value.integer);
+      gas_assembly_generator_set_latest_evaluation_as_literal(gen, literal->value.integer);
       return;
     default:
       assert(false && "no code generation strategy.");
@@ -181,14 +210,34 @@ static void
 gas_assembly_generator_binary_operation(gas_assembly_generator_t *gen, ast_binary_operation_t *binary_operation)
 {
   gas_assembly_generator_compile(gen, binary_operation->right);
+  evaluation_result_t right_evaluation = gen->latest_evaluation;
 
-  gen->stack_offset -= 8;
-  fprintf(gen->stream, "  mov %%rax, %d(%%rbp)\n", gen->stack_offset);
+  if (right_evaluation.kind == EVALUATION_RESULT_REGISTER) {
+    gen->stack_offset -= 8;
+    fprintf(gen->stream, "  mov %%rax, %d(%%rbp)\n", gen->stack_offset);
+  }
 
   gas_assembly_generator_compile(gen, binary_operation->left);
+  evaluation_result_t left_evaluation = gen->latest_evaluation;
 
-  fprintf(gen->stream, "  mov %d(%%rbp), %%rcx\n", gen->stack_offset);
-  gen->stack_offset += 8;
+  switch (right_evaluation.kind) {
+    case EVALUATION_RESULT_LITERAL_INTEGER:
+      fprintf(gen->stream, "  mov $%ld, %%rcx\n", right_evaluation.data.literal_int);
+      break;
+    case EVALUATION_RESULT_REGISTER:
+      fprintf(gen->stream, "  mov %d(%%rbp), %%rcx\n", gen->stack_offset);
+      gen->stack_offset += 8;
+      break;
+    case EVALUATION_RESULT_VOID:
+      assert(false && "Unexpected void result for variable declaration");
+      // FIXME: store the latest node at latest evaluation and print_ast
+  }
+
+  gas_assembly_generator_set_latest_evaluation_as_register(gen);
+
+  if (left_evaluation.kind == EVALUATION_RESULT_LITERAL_INTEGER) {
+    fprintf(gen->stream, "  mov $%ld, %%rax\n", left_evaluation.data.literal_int);
+  }
 
   if (binary_operation->kind == AST_BINOP_ADITION) {
     fprintf(gen->stream, "  add %%rcx, %%rax\n");
diff --git a/src/gas_assembly_generator.h b/src/gas_assembly_generator.h
index 044e8ed..d7d2e1e 100644
--- a/src/gas_assembly_generator.h
+++ b/src/gas_assembly_generator.h
@@ -21,11 +21,30 @@
 #include "vector.h"
 #include <stdio.h>
 
+typedef enum evaluation_result_kind_t
+{
+  EVALUATION_RESULT_VOID,
+  EVALUATION_RESULT_REGISTER,
+  EVALUATION_RESULT_LITERAL_INTEGER
+} evaluation_result_kind_t;
+
+typedef union evaluation_result_data_t
+{
+  int64_t literal_int;
+} evaluation_result_data_t;
+
+typedef struct evaluation_result_t
+{
+  evaluation_result_kind_t kind;
+  evaluation_result_data_t data;
+} evaluation_result_t;
+
 typedef struct gas_assembly_generator_t
 {
   FILE *stream;
   vector_t *refs;
   int stack_offset;
+  evaluation_result_t latest_evaluation;
 } gas_assembly_generator_t;
 
 void