Phi node

2 files changed, 80 insertions, 71 deletions

diff --git a/bxgen.c b/bxgen.c
index 7288b70..0739211 100755
--- a/bxgen.c
+++ b/bxgen.c
@@ -209,10 +209,11 @@ enum {
   OP_OR,
   OP_XOR,
   OP_NOT,
-  OP_IF,
   OP_ADDRESS,
   OP_CALL,
+  OP_IF,
   OP_RET,
+  OP_PHI,
 
   //  Calling conventions
 
@@ -297,6 +298,11 @@ typedef struct {
 } Ret;
 
 typedef struct {
+  i64          branch;
+  Chunk_Handle vals;
+} Phi;
+
+typedef struct {
   //  NOTE
   //  We may call a local procedure by it's id,
   //  or a global procedure by name.
@@ -315,17 +321,12 @@ typedef struct {
   i64 index_in_proc;
   union {
     Chunk_Handle lit;
+    Var          bin_op[2];
     Var          ref;
-    struct {
-      i64 ctrl_previous;
-      i64 ctrl_index;
-      union {
-        If   if_;
-        Ret  ret;
-        Call call;
-        Var  bin_op[2];
-      };
-    };
+    Call         call;
+    If           if_;
+    Ret          ret;
+    Phi          phi;
   };
 } Node;
 
@@ -483,12 +484,13 @@ i64  node_data_i64      (Pool *pool, i64 value);
 i64  node_data_add      (Pool *pool, Var x, Var y);
 i64  node_data_sub      (Pool *pool, Var x, Var y);
 
-i64  node_ctrl_call        (Pool *pool, i64 previous, i64 index, i64 target_proc, i64 num_args, Var *args);
-i64  node_ctrl_call_by_name(Pool *pool, i64 previous, i64 index, i64 name_size, c8 *name, i64 num_args, Var *args);
-i64  node_ctrl_if          (Pool *pool, i64 previous, i64 index, Var condition);
-i64  node_ctrl_ret         (Pool *pool, i64 previous, i64 index, i64 num_values, Var *values);
+i64  node_ctrl_call        (Pool *pool, i64 target_proc, i64 num_args, Var *args);
+i64  node_ctrl_call_by_name(Pool *pool, i64 name_size, c8 *name, i64 num_args, Var *args);
+i64  node_ctrl_if          (Pool *pool, Var condition);
+i64  node_ctrl_ret         (Pool *pool, i64 num_values, Var *values);
+i64  node_ctrl_phi         (Pool *pool, i64 branch, i64 num_vals, Var *vals);
 
-i64  proc_initi         (Pool *pool);
+i64  proc_init          (Pool *pool);
 void proc_destroy       (Pool *pool, i64 proc);
 void proc_set_convention(Pool *pool, i64 proc, u16 convention);
 void proc_set_name      (Pool *pool, i64 proc, i64 name_size, c8 *name);
@@ -531,10 +533,11 @@ i64  n_i64(i64 proc, i64 value);
 i64  n_add(i64 proc, Var x, Var y);
 i64  n_sub(i64 proc, Var x, Var y);
 
-i64  n_call        (i64 proc, i64 ctrl_previous, i64 ctrl_index, i64 target_proc, i64 num_args, Var *args);
-i64  n_call_by_name(i64 proc, i64 ctrl_previous, i64 ctrl_index, c8 *name, i64 num_args, Var *args);
-i64  n_if          (i64 proc, i64 ctrl_previous, i64 ctrl_index, Var condition);
-i64  n_ret         (i64 proc, i64 ctrl_previous, i64 ctrl_index, i64 num_vals, Var *vals);
+i64  n_call        (i64 proc, i64 target_proc, i64 num_args, Var *args);
+i64  n_call_by_name(i64 proc, c8 *name, i64 num_args, Var *args);
+i64  n_if          (i64 proc, Var condition);
+i64  n_ret         (i64 proc, i64 num_vals, Var *vals);
+i64  n_phi         (i64 proc, i64 branch, i64 num_vals, Var *vals);
 
 i64  p_new(i64 unit, c8 *name);
 i64  p_new_entry(i64 unit);
@@ -553,9 +556,10 @@ c8 * l_find(c8 *name, b8 silent);
 #define ARGS(...)                                  \
   (sizeof((Var[]) { __VA_ARGS__ }) / sizeof(Var)), \
   (Var[]) { __VA_ARGS__ }
-#define N_CALL(proc, prev_, index_, target_proc, ...)  n_call        ((proc), (prev_), (index_), (target_proc), ARGS(__VA_ARGS__))
-#define N_CALL_BY_NAME(proc, prev_, index_, name, ...) n_call_by_name((proc), (prev_), (index_), (name), ARGS(__VA_ARGS__))
-#define N_RET(proc, prev_, index_, ...)                n_ret         ((proc), (prev_), (index_), ARGS(__VA_ARGS__))
+#define N_CALL(proc, target_proc, ...)  n_call        ((proc), (target_proc), ARGS(__VA_ARGS__))
+#define N_CALL_BY_NAME(proc, name, ...) n_call_by_name((proc), (name), ARGS(__VA_ARGS__))
+#define N_RET(proc, ...)                n_ret         ((proc), ARGS(__VA_ARGS__))
+#define N_PHI(proc, branch, ...)        n_phi         ((proc), (branch), ARGS(__VA_ARGS__))
 
 #endif
 
@@ -1044,11 +1048,9 @@ u16 resolve_calling_convention(Pool *pool, i64 proc) {
   return p->convention;
 }
 
-i64 node_ctrl_call(Pool *pool, i64 previous, i64 index, i64 target_proc, i64 num_args, Var *args) {
+i64 node_ctrl_call(Pool *pool, i64 target_proc, i64 num_args, Var *args) {
   return node_init(pool, (Node) {
-    .op            = OP_CALL,
-    .ctrl_previous = previous,
-    .ctrl_index    = index,
+    .op   = OP_CALL,
     .call = {
       .convention  = resolve_calling_convention(pool, target_proc),
       .target_proc = target_proc,
@@ -1057,11 +1059,9 @@ i64 node_ctrl_call(Pool *pool, i64 previous, i64 index, i64 target_proc, i64 num
   });
 }
 
-i64 node_ctrl_call_by_name(Pool *pool, i64 previous, i64 index, i64 name_size, c8 *name, i64 num_args, Var *args) {
+i64 node_ctrl_call_by_name(Pool *pool, i64 name_size, c8 *name, i64 num_args, Var *args) {
   return node_init(pool, (Node) {
-    .op            = OP_CALL,
-    .ctrl_previous = previous,
-    .ctrl_index    = index,
+    .op   = OP_CALL,
     .call = {
       .convention  = CONV_CDECL,
       .target_proc = UNDEFINED,
@@ -1071,28 +1071,34 @@ i64 node_ctrl_call_by_name(Pool *pool, i64 previous, i64 index, i64 name_size, c
   });
 }
 
-i64 node_ctrl_if(Pool *pool, i64 previous, i64 index, Var condition) {
+i64 node_ctrl_if(Pool *pool, Var condition) {
   return node_init(pool, (Node) {
-    .op            = OP_IF,
-    .ctrl_previous = previous,
-    .ctrl_index    = index,
+    .op  = OP_IF,
     .if_ = {
       .condition = condition,
     },
   });
 }
 
-i64 node_ctrl_ret(Pool *pool, i64 previous, i64 index, i64 num_values, Var *values) {
+i64 node_ctrl_ret(Pool *pool, i64 num_values, Var *values) {
   return node_init(pool, (Node) {
-    .op            = OP_RET,
-    .ctrl_previous = previous,
-    .ctrl_index    = index,
+    .op  = OP_RET,
     .ret = {
       .vals = chunk_add(pool, num_values * sizeof *values, values),
     },
   });
 }
 
+i64 node_ctrl_phi(Pool *pool, i64 branch, i64 num_vals, Var *vals) {
+  return node_init(pool, (Node) {
+    .op  = OP_PHI,
+    .phi = {
+      .branch = branch,
+      .vals   = chunk_add(pool, num_vals *sizeof *vals, vals),
+    },
+  });
+}
+
 i64 proc_init(Pool *pool) {
   return pool_add(pool, (Entity) {
     .type = ENTITY_PROC,
@@ -2550,6 +2556,10 @@ b8 x86_64_emit_node(
       }
     } break;
 
+    case OP_IF: {
+      FAIL("Not implemented", 0);
+    } break;
+
     case OP_RET: {
       u8 *begin = CHUNK(pool, codegen->buffer_code, u8) + codegen->offset_code;
       u8 *end   = begin + codegen->buffer_code.size;
@@ -2677,6 +2687,10 @@ b8 x86_64_emit_node(
       }
     } break;
 
+    case OP_PHI: {
+      FAIL("Not implemented", 0);
+    } break;
+
     default:
       FAIL("Unknown operation", 0);
   }
@@ -4753,26 +4767,32 @@ i64 n_sub(i64 proc, Var x, Var y) {
   return n;
 }
 
-i64 n_call(i64 proc, i64 ctrl_previous, i64 ctrl_index, i64 target_proc, i64 num_args, Var *args) {
-  i64 n = node_ctrl_call(&g_pool, ctrl_previous, ctrl_index, target_proc, num_args, args);
+i64 n_call(i64 proc, i64 target_proc, i64 num_args, Var *args) {
+  i64 n = node_ctrl_call(&g_pool, target_proc, num_args, args);
+  p_add(proc, n);
+  return n;
+}
+
+i64 n_call_by_name(i64 proc, c8 *name, i64 num_args, Var *args) {
+  i64 n = node_ctrl_call_by_name(&g_pool, str_len(name, name + MAX_STRING_SIZE), name, num_args, args);
   p_add(proc, n);
   return n;
 }
 
-i64 n_call_by_name(i64 proc, i64 ctrl_previous, i64 ctrl_index, c8 *name, i64 num_args, Var *args) {
-  i64 n = node_ctrl_call_by_name(&g_pool, ctrl_previous, ctrl_index, str_len(name, name + MAX_STRING_SIZE), name, num_args, args);
+i64 n_if(i64 proc, Var condition) {
+  i64 n = node_ctrl_if(&g_pool, condition);
   p_add(proc, n);
   return n;
 }
 
-i64 n_if(i64 proc, i64 ctrl_previous, i64 ctrl_index, Var condition) {
-  i64 n = node_ctrl_if(&g_pool, ctrl_previous, ctrl_index, condition);
+i64 n_ret(i64 proc, i64 num_vals, Var *vals) {
+  i64 n = node_ctrl_ret(&g_pool, num_vals, vals);
   p_add(proc, n);
   return n;
 }
 
-i64 n_ret(i64 proc, i64 ctrl_previous, i64 ctrl_index, i64 num_vals, Var *vals) {
-  i64 n = node_ctrl_ret(&g_pool, ctrl_previous, ctrl_index, num_vals, vals);
+i64 n_phi(i64 proc, i64 branch, i64 num_vals, Var *vals) {
+  i64 n = node_ctrl_phi(&g_pool, branch, num_vals, vals);
   p_add(proc, n);
   return n;
 }
@@ -4955,7 +4975,6 @@ ADD_TEST_(link_with_libc, 42,
     //  Call puts
     N_CALL_BY_NAME(
       p,
-      0, 0,
       "puts",                         // proc name
       n_str(p, "hello sailor") // the first argument
     );
@@ -4963,7 +4982,6 @@ ADD_TEST_(link_with_libc, 42,
     //  Return 42
     N_RET(
       p,
-      0, 0,
       n_i32(p, 42) // the return value
     );
   }
@@ -4982,7 +5000,6 @@ ADD_TEST_(math_two_plus_two, 4,
 
   N_RET(
     p,
-    0, 0,
     n_add(p, n_i32(p, 2), n_i32(p, 2))
   );
 )
@@ -4992,7 +5009,6 @@ ADD_TEST_(math_sixty_nine, 69,
 
   N_RET(
     p,
-    0, 0,
     n_add(p, n_i32(p, 27), n_i32(p, 42))
   );
 )
@@ -5005,7 +5021,6 @@ ADD_TEST_(math_add_3, 1+2+3,
 
   N_RET(
     p,
-    0, 0,
     n_add(p, a, b)
   );
 )
@@ -5018,7 +5033,6 @@ ADD_TEST_(math_add_4a, 1+2+3+4,
 
   N_RET(
     p,
-    0, 0,
     n_add(p, a, b)
   );
 )
@@ -5033,7 +5047,6 @@ ADD_TEST_(math_add_5, 1+2+3+4+5,
 
   N_RET(
     p,
-    0, 0,
     n_add(p, a_b, c)
   );
 )
@@ -5048,7 +5061,6 @@ ADD_TEST_(math_add_6, 1+2+3+4+5+6,
 
   N_RET(
     p,
-    0, 0,
     n_add(p, a_b, c)
   );
 )
@@ -5065,7 +5077,6 @@ ADD_TEST_(math_add_7, 1+2+3+4+5+6+7,
 
   N_RET(
     p,
-    0, 0,
     n_add(p, a_b, c_d)
   );
 )
@@ -5083,7 +5094,6 @@ ADD_TEST_(math_add_4b, 5+6+7+8,
 
   N_RET(
     p,
-    0, 0,
     c_d
   );
 )
@@ -5100,7 +5110,6 @@ ADD_TEST_(math_add_8, 1+2+3+4+5+6+7+8,
 
   N_RET(
     p,
-    0, 0,
     n_add(p, a_b, c_d)
   );
 )
@@ -5113,7 +5122,6 @@ ADD_TEST_(math_sub_3, 3-2-1,
 
   N_RET(
     p,
-    0, 0,
     n_sub(p, a, b)
   );
 )
@@ -5126,7 +5134,6 @@ ADD_TEST_(math_sub_4, (4-3)-(2-1),
 
   N_RET(
     p,
-    0, 0,
     n_sub(p, a, b)
   );
 )
@@ -5141,7 +5148,6 @@ ADD_TEST_(math_sub_5, ((5-3)-(1-4))-2,
 
   N_RET(
     p,
-    0, 0,
     n_sub(p, a_b, c)
   );
 )
@@ -5156,7 +5162,6 @@ ADD_TEST_(math_sub_6, ((6-1)-(5-4))-(3-2),
 
   N_RET(
     p,
-    0, 0,
     n_sub(p, a_b, c)
   );
 )
@@ -5173,7 +5178,6 @@ ADD_TEST_(math_sub_7, ((7-2)-(2-3))-((4-5)-1),
 
   N_RET(
     p,
-    0, 0,
     n_sub(p, a_b, c_d)
   );
 )
@@ -5190,7 +5194,6 @@ ADD_TEST_(math_sub_8, ((8-1)-(2-3))-((4-5)-(7-6)),
 
   N_RET(
     p,
-    0, 0,
     n_sub(p, a_b, c_d)
   );
 )
@@ -5209,25 +5212,29 @@ ADD_TEST_(math_reg_reuse, (1+2+3+4+5+6+7+8+9+10),
   i64 i = n_add(p, h, n_i32(p,  9));
   i64 j = n_add(p, i, n_i32(p, 10));
 
-  N_RET(p, 0, 0, j);
+  N_RET(p, j);
 )
 
 ADD_TEST_(cond_1, 1,
   i64 p = p_new_entry(u);
 
   i64 a = n_i32(p, 1);
-  i64 b = n_if(p, 0, 0, a);
-  N_RET(p, b, 0, 1);
-  N_RET(p, b, 1, 2);
+  i64 b = n_if(p, a);
+  i64 c = n_i32(p, 1);
+  i64 d = n_i32(p, 2);
+  i64 e = N_PHI(p, b, c, d);
+  N_RET(p, e);
 )
 
 ADD_TEST_(cond_2, 2,
   i64 p = p_new_entry(u);
 
   i64 a = n_i32(p, 0);
-  i64 b = n_if(p, 0, 0, a);
-  N_RET(p, b, 0, 1);
-  N_RET(p, b, 1, 2);
+  i64 b = n_if(p, a);
+  i64 c = n_i32(p, 1);
+  i64 d = n_i32(p, 2);
+  i64 e = N_PHI(p, b, c, d);
+  N_RET(p, e);
 )
 
 #endif // HELPERS
@@ -5314,6 +5321,8 @@ i32 main(i32 argc, c8 **argv) {
   RUN_TEST_(math_sub_7);
   RUN_TEST_(math_sub_8);
   RUN_TEST_(math_reg_reuse);
+  // RUN_TEST_(cond_1);
+  // RUN_TEST_(cond_2);
   #endif
 
   #undef RUN_TEST_
diff --git a/test_cond_1 b/test_cond_1
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test_cond_1