np: codegen: Implement initial stack based codegen

This commit introduces the groundwork for the AMD64 PIIR backend. We
will not follow through with the plans of using abstract syntax trees as
they'll overly complicate the project. Instead we'll utilize a ring
buffer to store the list of instructions and a stack machine for the IR
code.

Signed-off-by: Ian Moffett <ian@osmora.org>

3 files changed, 65 insertions, 23 deletions

diff --git a/src/sys/include/np/piir.h b/src/sys/include/np/piir.h
index 9c4b322..8277c1f 100644
--- a/src/sys/include/np/piir.h
+++ b/src/sys/include/np/piir.h
@@ -35,7 +35,13 @@
 #include <os/spinlock.h>
 #include <os/np.h>
 
-typedef uint8_t ir_byte_t;
+/*
+ * Represents two different kinds of bytes, MI IR
+ * bytes and MD opcode / instruction bytes, less than
+ * zero values are reserved for error indication.
+ */
+typedef int8_t ir_byte_t;
+typedef int8_t md_byte_t;
 
 /*
  * The maxiumum size of the bytecode stack per
@@ -49,16 +55,33 @@ typedef uint8_t ir_byte_t;
 #define PIIR_LOAD_R16 0x02
 #define PIIR_LOAD_R32 0x03
 #define PIIR_LOAD_R64 0x04
+#define PIIR_RET_NIL  0x05  /* Return nothing */
+
+/*
+ * Represents the PIIR virtual machine for storing
+ * state while converting IR to instruction bytes
+ *
+ * @code: Generated machine code
+ * @last_ir: Last IR byte used
+ * @code_i: Current index into code buffer
+ */
+struct piir_vm {
+    md_byte_t code[4096];
+    ir_byte_t last_ir;
+    uint32_t code_i;
+};
 
 /*
  * Represents the Pi-IR (PIIR) bytecode stack
  *
  * @opstore: The actual stack
- * @op_i: Index into the stack
+ * @op_head: Where new ops are written
+ * @op_tail: Where new ops are read
  */
 struct piir_stack {
     ir_byte_t opstore[PIIR_STACK_SIZE];
-    uint16_t op_i;
+    uint16_t op_head;
+    uint16_t op_tail;
     struct spinlock lock;
 };
 
@@ -94,4 +117,14 @@ int piir_push(struct piir_stack *stack, ir_byte_t byte);
  */
 int piir_pop(struct piir_stack *stack);
 
+/*
+ * Inject control flow via stack machine
+ *
+ * @work: Current work
+ *
+ * Returns zero on success, otherwise a less than
+ * zero value on failure.
+ */
+int piir_inject(struct np_work *work);
+
 #endif  /* !_NP_PIIR_H_ */
diff --git a/src/sys/np/codegen/gen_piir.c b/src/sys/np/codegen/gen_piir.c
index e139465..e6623ac 100644
--- a/src/sys/np/codegen/gen_piir.c
+++ b/src/sys/np/codegen/gen_piir.c
@@ -66,12 +66,12 @@ piir_push(struct piir_stack *stack, ir_byte_t byte)
         return -EINVAL;
     }
 
-    if (stack->op_i >= PIIR_STACK_SIZE - 1) {
+    if (stack->op_head >= PIIR_STACK_SIZE - 1) {
         return -1;
     }
 
     spinlock_acquire(&stack->lock);
-    stack->opstore[stack->op_i++] = byte;
+    stack->opstore[stack->op_head++] = byte;
     spinlock_release(&stack->lock);
     return 0;
 }
@@ -88,12 +88,22 @@ piir_pop(struct piir_stack *stack)
         return -EINVAL;
     }
 
-    if (stack->op_i == 0) {
+    /* Don't read past what we can */
+    if (stack->op_tail == stack->op_head) {
+        stack->op_tail = 0;
+        stack->op_head = 0;
         return -1;
     }
 
     spinlock_acquire(&stack->lock);
-    byte = stack->opstore[--stack->op_i];
+
+    /* Grab a byte, reset pointers if empty */
+    byte = stack->opstore[stack->op_tail++];
+    if (stack->op_tail == stack->op_head) {
+        stack->op_tail = 0;
+        stack->op_head = 0;
+    }
+
     spinlock_release(&stack->lock);
     return byte;
 }
diff --git a/src/sys/np/core/np_parse.c b/src/sys/np/core/np_parse.c
index fd35e3c..3eefde5 100644
--- a/src/sys/np/core/np_parse.c
+++ b/src/sys/np/core/np_parse.c
@@ -269,16 +269,16 @@ parse_proc(struct np_work *work, struct ast_node **npp, struct lex_token *tok)
  * Parse a token
  *
  * @work: Input work
- * @root: Root AST node
  * @tok: Current token
  */
 static int
-parse_token(struct np_work *work, struct ast_node *root, struct lex_token *tok)
+parse_token(struct np_work *work, struct lex_token *tok)
 {
     tt_t tt;
     int error;
     struct ast_node *np;
 
+#define PIIR_PUSH(BYTE) piir_push(work->piir_stack, (BYTE))
     /*
      * XXX: wrapped in "[]" indicates optional
      *
@@ -296,9 +296,15 @@ parse_token(struct np_work *work, struct ast_node *root, struct lex_token *tok)
 
         ++work->begin_depth;
     case TT_END:
-        /* Do the begin statements match? */
+        /*
+         * Check if the 'begin' statements match, if they do
+         * we'll decrease the depth and push a NIL return
+         *
+         * TODO: We'll need to handle returns better
+         */
         if (work->begin_depth > 0) {
             --work->begin_depth;
+            PIIR_PUSH(PIIR_RET_NIL);
             break;
         }
 
@@ -321,18 +327,17 @@ parse_token(struct np_work *work, struct ast_node *root, struct lex_token *tok)
             return -1;
         }
 
-        root->left = NULL;  /* arguments */
-        root->right = np;
+        /* XXX: NOP for testing */
+        PIIR_PUSH(PIIR_NOP);
         break;
     }
-
+#undef PIIR_PUSH
     return 0;
 }
 
 int
 parse_work(struct np_work *work)
 {
-    struct ast_node *root;
     struct lex_token tok;
     int error = 0;
 
@@ -341,14 +346,6 @@ parse_work(struct np_work *work)
         return -EINVAL;
     }
 
-    /* Get the AST root node */
-    work->ast_root = ast_alloc(work);
-    root = work->ast_root;
-    if (work->ast_root == NULL) {
-        pr_error("failed to alloc root AST\n");
-        return -ENOMEM;
-    }
-
     /* Initialize PIIR */
     error = piir_stack_new(work, &work->piir_stack);
     if (error < 0) {
@@ -371,11 +368,13 @@ parse_work(struct np_work *work)
             return -1;
         }
 
-        if (parse_token(work, root, &tok) < 0) {
+        if (parse_token(work, &tok) < 0) {
             return -1;
         }
     }
 
+    piir_inject(work);
+
     /*
      * If there are more begin clauses than end
      * clauses, someone mismatched them.