compiler: Optimize renaming in SSA a little more.
authorTyler J. Stachecki <stachecki.tyler@gmail.com>
Sun, 23 Apr 2017 14:03:10 +0000 (10:03 -0400)
committerTyler J. Stachecki <stachecki.tyler@gmail.com>
Sun, 23 Apr 2017 14:03:10 +0000 (10:03 -0400)
When populating phi nodes in immediate successors, we can
break out of the loop when scanning for our predecessor
index early (the compiler can't do this for us, as it does
not know that we're the only basic block in the list).

Also, augment the stack_top method so that it returns a
value if the stack does not currently have any items. In
most cases, this would be NULL... however, we can save a
conditional branch in mosts cases if it's not.

Signed-off-by: Tyler J. Stachecki <stachecki.tyler@gmail.com>
compiler/passes/ssa_conversion.c
compiler/stack.c
compiler/stack.h

index a4d54e1..2a5e7a4 100644 (file)
@@ -559,31 +559,31 @@ int rename_variables_in_bb(struct cen64_compiler *compiler,
     }
   }
 
-  /* Fill all the phi sources in each of the successors */
+  /* For each phi node in each immediate successor, populate the jth entry  */
+  /* of the phi node, where j = index of this block in the predecessor list */
   succs = bb->node.basic_block.successors;
 
   for (i = 0; i < succs->size; i++) {
-    struct cen64_compiler_node *succ = succs->list[i];
+    struct cen64_compiler_node *phi, *succ = succs->list[i];
     struct cen64_compiler_list *preds = succ->node.basic_block.predecessors;
     unsigned j;
 
     for (j = 0; j < preds->size; j++) {
-      if (preds->list[j] == bb) {
-        struct cen64_compiler_node *phi;
+      if (preds->list[j] == bb)
+        break;
+    }
 
-        for (phi = succ->node.basic_block.head;
-            phi != NULL && phi->type == kVariable; phi = phi->next);
+    for (phi = succ->node.basic_block.head;
+        phi != NULL && phi->type == kVariable; phi = phi->next);
 
-        for (; phi != NULL && phi->type == kStorePhi; phi = phi->next) {
-          struct cen64_compiler_stack *var_stack;
+    for (; phi != NULL && phi->type == kStorePhi; phi = phi->next) {
+      struct cen64_compiler_stack *var_stack;
 
-          orig_var = phi->node.store.value;
-          var_stack = orig_var->node.variable.ssa.stack;
-          var = cen64_compiler_stack_top(var_stack);
+      orig_var = phi->node.store.value;
+      var_stack = orig_var->node.variable.ssa.stack;
+      var = cen64_compiler_stack_top_or_value(var_stack, orig_var);
 
-          phi->node.store.ssa.phi_list->list[j] = var ? var : orig_var;
-        }
-      }
+      phi->node.store.ssa.phi_list->list[j] = var;
     }
   }
 
@@ -606,8 +606,7 @@ int rename_variables_in_bb(struct cen64_compiler *compiler,
 
 int rename_variables_in_expr(struct cen64_compiler *compiler,
     struct cen64_compiler_node *node) {
-  struct cen64_compiler_node *left, *right, *param;
-  struct cen64_compiler_node *check, *var;
+  struct cen64_compiler_node *left, *right, *param, *var;
 
   switch (node->type) {
     case kBinaryOperation:
@@ -636,11 +635,8 @@ int rename_variables_in_expr(struct cen64_compiler *compiler,
 
     case kLoad:
       var = node->node.load.variable;
-
-      if ((check = cen64_compiler_stack_top(
-          var->node.variable.ssa.stack)) != NULL) {
-        var = check;
-      }
+      var = cen64_compiler_stack_top_or_value(
+          var->node.variable.ssa.stack, var);
 
       node->node.load.name = var->node.variable.name;
       node->node.load.variable = var;
index 332adea..c7914bc 100644 (file)
@@ -69,12 +69,13 @@ void *cen64_compiler_stack_pop(struct cen64_compiler_stack *stack) {
   return ret;
 }
 
-void *cen64_compiler_stack_top(struct cen64_compiler_stack *stack) {
+void *cen64_compiler_stack_top_or_value(
+    struct cen64_compiler_stack *stack, void *i) {
   struct cen64_compiler_stack_frame *frame = stack->top;
 
   if (frame->top == 0) {
     if (!frame->prev)
-      return NULL;
+      return i;
 
     frame = frame->prev;
     stack->top = frame;
index 0a65656..1928d1f 100644 (file)
@@ -48,7 +48,9 @@ void cen64_compiler_stack_destroy(struct cen64_compiler_stack *stack);
 
 void cen64_compiler_stack_push(struct cen64_compiler_stack *stack, void *i);
 void *cen64_compiler_stack_pop(struct cen64_compiler_stack *stack);
-void *cen64_compiler_stack_top(struct cen64_compiler_stack *stack);
+
+void *cen64_compiler_stack_top_or_value(
+    struct cen64_compiler_stack *stack, void *i);
 
 void cen64_compiler_stack_top_replace(
     struct cen64_compiler_stack *stack, void *i);