compiler: Place phi nodes into CFG during SSA.
authorTyler J. Stachecki <stachecki.tyler@gmail.com>
Fri, 7 Apr 2017 23:51:10 +0000 (19:51 -0400)
committerTyler J. Stachecki <stachecki.tyler@gmail.com>
Fri, 7 Apr 2017 23:51:10 +0000 (19:51 -0400)
Signed-off-by: Tyler J. Stachecki <stachecki.tyler@gmail.com>
compiler/nodes.h
compiler/passes/list_builder.c
compiler/passes/semantic_analysis.c
compiler/passes/ssa_conversion.c
compiler/printer.c
compiler/variable_ht.c
compiler/variable_ht.h

index b8675db..06911cd 100644 (file)
@@ -71,6 +71,7 @@ enum cen64_compiler_node_type {
   kLoad,
   kObject,
   kObjectMember,
+  kPhi,
   kProgram,
   kStore,
   kVariable
@@ -187,6 +188,10 @@ struct cen64_compiler_object_node {
   char visited;
 };
 
+struct cen64_compiler_phi_node {
+  struct cen64_compiler_node *variable;
+};
+
 struct cen64_compiler_program_node {
   struct cen64_compiler_node *head;
   struct cen64_compiler_node *tail;
@@ -195,7 +200,10 @@ struct cen64_compiler_program_node {
 struct cen64_compiler_store_node {
   const char *name;
   struct cen64_compiler_node *value;
-  const void *ssa_ref;
+  struct cen64_compiler_node *bb;
+
+  /* Instrusive linked list (list of defs for variable) */
+  struct cen64_compiler_node *next_def;
 };
 
 struct cen64_compiler_variable_node {
@@ -206,7 +214,7 @@ struct cen64_compiler_variable_node {
 
   /* Intrusive linked list (variable hash table chain) */
   struct cen64_compiler_variable_node *next_ht_entry;
-  unsigned long hash_value;
+  struct cen64_compiler_node *def_chain;
 };
 
 struct cen64_compiler_node {
@@ -223,6 +231,7 @@ struct cen64_compiler_node {
     struct cen64_compiler_load_node load;
     struct cen64_compiler_object_node object;
     struct cen64_compiler_object_member_node object_member;
+    struct cen64_compiler_phi_node phi;
     struct cen64_compiler_program_node program;
     struct cen64_compiler_store_node store;
     struct cen64_compiler_variable_node variable;
index 839f47e..898d4d2 100644 (file)
@@ -14,6 +14,7 @@
 #include "compiler/driver.h"
 #include "compiler/passes.h"
 #include "compiler/passes/list_builder.h"
+#include "compiler/variable_ht.h"
 #include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
index ad3d4fb..8523ca5 100644 (file)
@@ -47,6 +47,7 @@ int check_body_with_existing_scope(struct cen64_compiler *compiler,
     unsigned end_scope_bb) {
   struct cen64_compiler_node *bb, *node, *self, *check;
   struct cen64_compiler_function_node *function;
+  struct cen64_compiler_variable_node *var;
   enum cen64_lexer_token type;
 
   for (bb = head; bb != NULL; ) {
@@ -144,7 +145,8 @@ int check_body_with_existing_scope(struct cen64_compiler *compiler,
           break;
 
         case kStore:
-          if (!cen64_variable_ht_lookup(variables, node->node.store.name)) {
+          if ((var = cen64_variable_ht_lookup(
+              variables, node->node.store.name)) == NULL) {
             compiler->pass_error_message = "Use of undefined variable name";
             compiler->pass_error_line_number = node->line_number_or_id;
             return 1;
@@ -155,6 +157,11 @@ int check_body_with_existing_scope(struct cen64_compiler *compiler,
             return 1;
           }
 
+          node->node.store.bb = bb;
+
+          /* Add the store to the def chain */
+          node->node.store.next_def = var->def_chain;
+          var->def_chain = node;
           break;
 
         case kVariable:
index 3c0a369..d35170e 100644 (file)
@@ -9,6 +9,7 @@
  * 'LICENSE', which is part of this source code package.
  */
 
+
 #include "common.h"
 #include "compiler/alloc.h"
 #include "compiler/bblist.h"
@@ -21,6 +22,9 @@
 #include <stddef.h>
 #include <string.h>
 
+#define CEN64_EVER_ON_WORK_LIST 0x1
+#define CEN64_ALREADY_HAS_PHI   0x2
+
 /* Helper functions used by Lengauer-Tarjan */
 
 /* TODO: Implement the sophisticated methods for performing the LINK and  */
@@ -61,6 +65,12 @@ static void ltd_link(struct ltd_array_item *ltd,
 static struct cen64_compiler_node *get_immediate_dominator(
     struct cen64_compiler *compiler, struct cen64_compiler_node *node);
 
+static void insert_phis_into_df(struct cen64_compiler *compiler,
+    struct cen64_compiler_set *dom_set, struct cen64_compiler_set_node *d,
+    struct cen64_compiler_node *var, struct cen64_compiler_set *work_list);
+
+static void insert_phi_nodes(struct cen64_compiler *compiler);
+
 static int run_ssa_conversion(struct cen64_compiler *compiler);
 
 const struct cen64_compiler_pass_info cen64_compiler_pass_ssa_conversion = {
@@ -79,6 +89,83 @@ struct cen64_compiler_node *get_immediate_dominator(
   return compiler->bb_list[idom];
 }
 
+static void insert_phis_into_df(struct cen64_compiler *compiler,
+    struct cen64_compiler_set *dom_set, struct cen64_compiler_set_node *d,
+    struct cen64_compiler_node *var, struct cen64_compiler_set *work_list) {
+  if (d->left != dom_set->nil)
+    insert_phis_into_df(compiler, dom_set, d->left, var, work_list);
+
+  if (d->right != dom_set->nil)
+    insert_phis_into_df(compiler, dom_set, d->right, var, work_list);
+
+  if (!(compiler->bb_flag_list[d->value] & CEN64_ALREADY_HAS_PHI)) {
+    struct cen64_compiler_node *bb = compiler->bb_list[d->value];
+    struct cen64_compiler_node *phi;
+
+    compiler->bb_flag_list[d->value] |= CEN64_ALREADY_HAS_PHI;
+    if (!(compiler->bb_flag_list[d->value] & CEN64_EVER_ON_WORK_LIST)) {
+      compiler->bb_flag_list[d->value] |= CEN64_EVER_ON_WORK_LIST;
+      cen64_compiler_set_add(work_list, d->value);
+    }
+
+    phi = cen64_node_alloc(&compiler->node_alloc, kPhi, 0);
+    phi->node.phi.variable = var;
+
+    phi->next = bb->node.basic_block.head;
+    phi->next->prev = phi;
+    phi->prev = NULL;
+
+    bb->node.basic_block.head = phi;
+  }
+}
+
+void insert_phi_nodes(struct cen64_compiler *compiler) {
+  unsigned i;
+
+  /* For each variable in the graph... */
+  for (i = 0; i < compiler->cunit.bb_count; i++) {
+    struct cen64_compiler_node *bb = compiler->bb_list[i];
+    struct cen64_compiler_node *node;
+
+    for (node = bb->node.basic_block.head; node != NULL; node = node->next) {
+      struct cen64_compiler_set *work_list;
+      struct cen64_compiler_node *def;
+
+      if (node->type != kVariable)
+        continue;
+
+      work_list = cen64_compiler_set_create(&compiler->arena_alloc);
+      memset(compiler->bb_flag_list, 0, compiler->cunit.bb_count);
+
+      /* Build the initial work list from the def chain */
+      for (def = node->node.variable.def_chain;
+          def != NULL; def = def->node.store.next_def) {
+        struct cen64_compiler_node *bb_containing_def = def->node.store.bb;
+
+        cen64_compiler_set_add(work_list, bb_containing_def->line_number_or_id);
+        compiler->bb_flag_list[bb_containing_def->line_number_or_id] =
+            CEN64_EVER_ON_WORK_LIST;
+      }
+
+      /* While the work list is not empty... */
+      while (work_list->root != work_list->nil) {
+        struct cen64_compiler_node *x;
+        struct cen64_compiler_set *df;
+
+        x = compiler->bb_list[work_list->root->value];
+        df = x->node.basic_block.temp.dom_set;
+
+        if (df->root != df->nil)
+          insert_phis_into_df(compiler, df, df->root, node, work_list);
+
+        cen64_compiler_set_remove(work_list, x->line_number_or_id);
+      }
+
+      cen64_compiler_set_destroy(work_list);
+    }
+  }
+}
+
 int lengauer_tarjan(struct cen64_compiler *compiler,
     struct ltd_array_item *ltd, struct cen64_compiler_node *node) {
   unsigned i, j, n = 0;
@@ -243,7 +330,7 @@ void ltd_link(struct ltd_array_item *ltd,
 }
 
 int run_ssa_conversion(struct cen64_compiler *compiler) {
-  struct cen64_compiler_set *work_list;
+  struct cen64_compiler_set *dom_set;
   struct cen64_compiler_node *node;
 
   struct ltd_array_item *ltd;
@@ -253,14 +340,14 @@ int run_ssa_conversion(struct cen64_compiler *compiler) {
   /* Pre-allocate buckets for Lengauer-Tarjan. Once the buckets are alloc'd, */
   /* no furthers allocations are needed and thus the arena slack can be used */
   /* to keep track of the state for Lengauer-Tarjan as it runs.              */
-  work_list = cen64_compiler_set_create(&compiler->arena_alloc);
+  dom_set = cen64_compiler_set_create(&compiler->arena_alloc);
 
   for (i = 0; i < compiler->cunit.bb_count; i++) {
     compiler->bb_list[i]->node.basic_block.temp.dom_set =
-        cen64_compiler_set_create_shared(work_list);
+        cen64_compiler_set_create_shared(dom_set);
   }
 
-  cen64_compiler_set_preallocate(work_list, compiler->cunit.bb_count);
+  cen64_compiler_set_preallocate(dom_set, compiler->cunit.bb_count);
 
   /* Use Lengauer-Tarjan to compute immediate dominators for each basic block */
   alloc_size = sizeof(*ltd) * compiler->cunit.bb_count;
@@ -303,6 +390,9 @@ int run_ssa_conversion(struct cen64_compiler *compiler) {
     }
   }
 
+  insert_phi_nodes(compiler);
+
+  cen64_compiler_set_destroy(dom_set);
   return 0;
 }
 
index 262d1f8..01e8a71 100644 (file)
@@ -204,11 +204,16 @@ void print_function_body(FILE *stream, struct cen64_compiler *compiler,
 
           break;
 
+        case kPhi:
+          fprintf(stream, "Phi [%s]\n", temp->node.phi.variable->
+              node.variable.name);
+
+          break;
+
         case kStore:
           inner = temp->node.store.value;
 
-          fprintf(stream, "Store [%s/%p <= ",
-              temp->node.store.name, temp->node.store.ssa_ref);
+          fprintf(stream, "Store [%s <= ", temp->node.store.name);
 
           assert(inner->prev == NULL &&
               "prev field in expression head in function body is non-NULL");
index e1d18f4..22698ff 100644 (file)
@@ -41,20 +41,19 @@ void cen64_variable_ht_insert(struct cen64_variable_ht *ht,
   unsigned long hash_value = hash(variable->name);
   size_t hash_index = hash_value % num_buckets;
 
-  variable->hash_value = hash_value;
   variable->next_ht_entry = ht->nodes[hash_index];
   ht->nodes[hash_index] = variable;
 }
 
-const struct cen64_compiler_variable_node *cen64_variable_ht_lookup(
-    const struct cen64_variable_ht *ht, const char *name) {
+struct cen64_compiler_variable_node *cen64_variable_ht_lookup(
+    struct cen64_variable_ht *ht, const char *name) {
   struct cen64_compiler_variable_node *node;
   static const size_t num_buckets = sizeof(ht->nodes) / sizeof(*ht->nodes);
   unsigned long hash_value = hash(name);
 
   for (node = ht->nodes[hash_value % num_buckets];
       node != NULL; node = node->next_ht_entry) {
-    if (node->hash_value == hash_value && likely(!strcmp(node->name, name)))
+    if (!strcmp(node->name, name))
       return node;
   }
 
index bca19f6..74cec08 100644 (file)
@@ -57,8 +57,9 @@ void cen64_variable_ht_insert(struct cen64_variable_ht *ht,
 void cen64_variable_ht_reset(struct cen64_variable_ht *ht,
     const struct cen64_variable_ht *parent_ht);
 
-pure_attribute const struct cen64_compiler_variable_node *cen64_variable_ht_lookup(
-    const struct cen64_variable_ht *ht, const char *name);
+struct cen64_compiler_variable_node *
+    cen64_variable_ht_lookup(struct cen64_variable_ht *ht,
+    const char *name);
 
 #endif