From 4e49830e09772ba930f40194c75397a706adfc04 Mon Sep 17 00:00:00 2001
From: David Given <dg@cowlark.com>
Date: Sat, 8 Oct 2016 00:21:23 +0200
Subject: [PATCH] Overhaul of everything phi related; critical edge splitting
 now happens before anything SSA happens; liveness calculations now look like
 they might be working.

---
 mach/proto/mcg/basicblock.h                |  12 +-
 mach/proto/mcg/graph.c                     |   2 +
 mach/proto/mcg/graph.h                     |   1 +
 mach/proto/mcg/hop.c                       |  10 +-
 mach/proto/mcg/hop.h                       |   5 +-
 mach/proto/mcg/ir.c                        |   4 +-
 mach/proto/mcg/ir.h                        |   2 +-
 mach/proto/mcg/main.c                      |  32 +++++-
 mach/proto/mcg/mcg.h                       |   8 +-
 mach/proto/mcg/pass_convertstackops.c      |  10 +-
 mach/proto/mcg/pass_instructionselection.c |  29 +++--
 mach/proto/mcg/pass_livevreganalysis.c     |  73 ++++++++++++
 mach/proto/mcg/pass_registerallocator.c    |  25 +----
 mach/proto/mcg/pass_ssa.c                  |   3 +-
 mach/proto/mcg/procedure.c                 | 124 +++++++++++++++++++--
 mach/proto/mcg/reg.h                       |   2 +
 16 files changed, 286 insertions(+), 56 deletions(-)
 create mode 100644 mach/proto/mcg/pass_livevreganalysis.c

diff --git a/mach/proto/mcg/basicblock.h b/mach/proto/mcg/basicblock.h
index 75aa38e84..4c65721e4 100644
--- a/mach/proto/mcg/basicblock.h
+++ b/mach/proto/mcg/basicblock.h
@@ -1,6 +1,12 @@
 #ifndef BASICBLOCK_H
 #define BASICBLOCK_H
 
+struct phi
+{
+    struct basicblock* prev; /* Predecessor that this phi is referring to */
+    struct ir* ir;           /* IR of variable definition */
+};
+
 struct basicblock
 {
     const char* name;
@@ -12,7 +18,11 @@ struct basicblock
     ARRAYOF(struct basicblock) nexts;
     int order; /* used by dominance graph code */
 
-	ARRAYOF(struct vreg) liveins;
+    PMAPOF(struct vreg, struct phi) phis;
+
+    /* Used by liveness calculation. */
+    ARRAYOF(struct vreg) liveins;
+    ARRAYOF(struct vreg) liveouts;
 
     bool is_fake : 1;
     bool is_root : 1;
diff --git a/mach/proto/mcg/graph.c b/mach/proto/mcg/graph.c
index 2897bc78a..9c976735b 100644
--- a/mach/proto/mcg/graph.c
+++ b/mach/proto/mcg/graph.c
@@ -13,6 +13,7 @@ static bool collect_outputs_cb(struct ir* ir, void* user)
     {
         array_appendu(&caller->nexts, ir->u.bvalue);
         array_appendu(&ir->u.bvalue->prevs, caller);
+        pmap_add(&cfg.graph, caller, ir->u.bvalue);
     }
     return false;
 }
@@ -191,6 +192,7 @@ static void walk_dominance_graph(void)
 void update_graph_data(struct procedure* proc)
 {
     cfg.entry = proc->blocks.item[0];
+    cfg.graph.count = 0;
     update_block_pointers_from_ir(proc);
 
     walk_cfg_graph();
diff --git a/mach/proto/mcg/graph.h b/mach/proto/mcg/graph.h
index 59c93137e..93991b82f 100644
--- a/mach/proto/mcg/graph.h
+++ b/mach/proto/mcg/graph.h
@@ -4,6 +4,7 @@
 struct graph_data
 {
     struct basicblock* entry;
+    PMAPOF(struct basicblock, struct basicblock) graph;
     ARRAYOF(struct basicblock) preorder;
     ARRAYOF(struct basicblock) postorder;
 };
diff --git a/mach/proto/mcg/hop.c b/mach/proto/mcg/hop.c
index 352ad9b2b..d175147b6 100644
--- a/mach/proto/mcg/hop.c
+++ b/mach/proto/mcg/hop.c
@@ -5,11 +5,11 @@ static struct hop* current_hop;
 
 static const struct burm_emitter_data emitter_data;
 
-struct hop* new_hop(int insn_no, struct ir* ir)
+struct hop* new_hop(struct basicblock* bb, struct ir* ir)
 {
 	struct hop* hop = calloc(1, sizeof *hop);
 	hop->id = hop_count++;
-	hop->insn_no = insn_no;
+    hop->bb = bb;
 	hop->ir = ir;
 	return hop;
 }
@@ -63,9 +63,11 @@ void hop_print(char k, struct hop* hop)
 			tracef(k, "%c: %d from $%d:", k, hop->id, hop->ir->id);
 
 			for (j=0; j<hop->ins.count; j++)
-				tracef(k, " <%%%d", hop->ins.item[j]->id);
+				tracef(k, " r%%%d", hop->ins.item[j]->id);
+			for (j=0; j<hop->throughs.count; j++)
+				tracef(k, " =%%%d", hop->throughs.item[j]->id);
 			for (j=0; j<hop->outs.count; j++)
-				tracef(k, " >%%%d", hop->outs.item[j]->id);
+				tracef(k, " w%%%d", hop->outs.item[j]->id);
 			tracef(k, " ");
 
 			soi = false;
diff --git a/mach/proto/mcg/hop.h b/mach/proto/mcg/hop.h
index 66903cbfe..18e70d3b4 100644
--- a/mach/proto/mcg/hop.h
+++ b/mach/proto/mcg/hop.h
@@ -24,17 +24,18 @@ struct insel
 struct hop
 {
 	int id;
-	int insn_no;
+    struct basicblock* bb;
 	struct ir* ir;
 	ARRAYOF(struct insel) insels;
 	struct vreg* output;
 
 	ARRAYOF(struct vreg) ins;
 	ARRAYOF(struct vreg) outs;
+    ARRAYOF(struct vreg) throughs;
 	PMAPOF(struct vreg, struct hreg) registers;
 };
 
-extern struct hop* new_hop(int insn_no, struct ir* ir);
+extern struct hop* new_hop(struct basicblock* bb, struct ir* ir);
 
 extern void hop_add_string_insel(struct hop* hop, const char* string);
 extern void hop_add_vreg_insel(struct hop* hop, struct vreg* vreg);
diff --git a/mach/proto/mcg/ir.c b/mach/proto/mcg/ir.c
index de3ec396f..74fbac060 100644
--- a/mach/proto/mcg/ir.c
+++ b/mach/proto/mcg/ir.c
@@ -132,7 +132,9 @@ static void print_expr(char k, const struct ir* ir)
             {
                 if (i > 0)
                     tracef(k, ", ");
-                tracef(k, "$%d", ir->u.phivalue.item[i]->id);
+                tracef(k, "%s=>$%d",
+                    ir->u.phivalue.item[i].left->name,
+                    ir->u.phivalue.item[i].right->id);
             }
             break;
         }
diff --git a/mach/proto/mcg/ir.h b/mach/proto/mcg/ir.h
index a12b9642c..c273709f2 100644
--- a/mach/proto/mcg/ir.h
+++ b/mach/proto/mcg/ir.h
@@ -17,7 +17,7 @@ struct ir
 		int rvalue;
 		const char* lvalue;
 		struct basicblock* bvalue;
-		ARRAYOF(struct ir) phivalue;
+        PMAPOF(struct basicblock, struct ir) phivalue;
 	} u;
 
 	struct vreg* result;     /* vreg containing IR result */
diff --git a/mach/proto/mcg/main.c b/mach/proto/mcg/main.c
index 5789a1379..235e9f357 100644
--- a/mach/proto/mcg/main.c
+++ b/mach/proto/mcg/main.c
@@ -1,8 +1,12 @@
 #include "mcg.h"
+#include <errno.h>
 #include <unistd.h>
 
 static const char* tracechars = NULL;
 
+FILE* dominance_dot_file = NULL;
+FILE* cfg_dot_file = NULL;
+
 bool tracing(char k)
 {
     if (!tracechars)
@@ -39,12 +43,28 @@ int main(int argc, char* const argv[])
     opterr = 1;
     for (;;)
     {
-        int c = getopt(argc, argv, "-d:");
+        int c = getopt(argc, argv, "-d:D:C:");
         if (c == -1)
             break;
 
         switch (c)
         {
+            case 'C':
+                cfg_dot_file = fopen(optarg, "w");
+                if (!cfg_dot_file)
+                    fatal("couldn't open output file '%s': %s",
+                        optarg, strerror(errno));
+                fprintf(cfg_dot_file, "digraph {\n");
+                break;
+
+            case 'D':
+                dominance_dot_file = fopen(optarg, "w");
+                if (!dominance_dot_file)
+                    fatal("couldn't open output file '%s': %s",
+                        optarg, strerror(errno));
+                fprintf(dominance_dot_file, "digraph {\n");
+                break;
+
             case 'd':
                 tracechars = optarg;
                 break;
@@ -74,6 +94,16 @@ int main(int argc, char* const argv[])
     symbol_walk(find_procedures_cb, NULL);
 
 	EM_close();
+    if (cfg_dot_file)
+    {
+        fprintf(cfg_dot_file, "}\n");
+        fclose(cfg_dot_file);
+    }
+    if (dominance_dot_file)
+    {
+        fprintf(dominance_dot_file, "}\n");
+        fclose(dominance_dot_file);
+    }
 	return 0;
 }
 
diff --git a/mach/proto/mcg/mcg.h b/mach/proto/mcg/mcg.h
index bad088ee3..f4e33f2af 100644
--- a/mach/proto/mcg/mcg.h
+++ b/mach/proto/mcg/mcg.h
@@ -105,12 +105,16 @@ extern void pass_convert_locals_to_ssa(struct procedure* proc);
 extern void pass_convert_stack_ops(struct procedure* proc);
 extern void pass_eliminate_trivial_blocks(struct procedure* proc);
 extern void pass_group_irs(struct procedure* proc);
-extern void pass_instruction_selector(struct procedure* proc);
+extern void pass_instruction_selector(void);
+extern void pass_live_vreg_analysis(void);
 extern void pass_promote_float_ops(struct procedure* proc);
-extern void pass_register_allocator(struct procedure* proc);
+extern void pass_register_allocator(void);
 extern void pass_remove_dead_blocks(struct procedure* proc);
 extern void pass_split_critical_edges(struct procedure* proc);
 
+extern FILE* dominance_dot_file;
+extern FILE* cfg_dot_file;
+
 #endif
 
 /* vim: set sw=4 ts=4 expandtab : */
diff --git a/mach/proto/mcg/pass_convertstackops.c b/mach/proto/mcg/pass_convertstackops.c
index dbc1f8276..d73924d67 100644
--- a/mach/proto/mcg/pass_convertstackops.c
+++ b/mach/proto/mcg/pass_convertstackops.c
@@ -1,7 +1,7 @@
 #include "mcg.h"
 
 static ARRAYOF(struct ir) pops;
-static ARRAYOF(struct ir) pushes;
+static PMAPOF(struct basicblock, struct ir) pushes;
 
 static struct ir* get_last_push(struct basicblock* bb)
 {
@@ -74,7 +74,7 @@ static void convert_block(struct procedure* proc, struct basicblock* bb)
                 ir = get_last_push(inbb);
                 if (!ir || (ir->size != lastpush->size))
                     return;
-                array_appendu(&pushes, ir);
+                pmap_add(&pushes, inbb, ir);
             }
         }
 
@@ -87,7 +87,7 @@ static void convert_block(struct procedure* proc, struct basicblock* bb)
 
         for (i=0; i<pushes.count; i++)
         {
-            struct ir* ir = pushes.item[i];
+            struct ir* ir = pushes.item[i].right;
             *ir = *ir->left;
         }
 
@@ -97,7 +97,9 @@ static void convert_block(struct procedure* proc, struct basicblock* bb)
             struct ir* phi = new_ir0(IR_PHI, ir->size);
 
             for (j=0; j<pushes.count; j++)
-                array_appendu(&phi->u.phivalue, pushes.item[j]);
+                pmap_add(&phi->u.phivalue,
+                    pushes.item[j].left,
+                    pushes.item[j].right);
             phi->root = phi;
 
             *ir = *phi;
diff --git a/mach/proto/mcg/pass_instructionselection.c b/mach/proto/mcg/pass_instructionselection.c
index ca7589e86..029cacd4b 100644
--- a/mach/proto/mcg/pass_instructionselection.c
+++ b/mach/proto/mcg/pass_instructionselection.c
@@ -52,7 +52,10 @@ static void emit_reg(int child)
     struct vreg* vreg = find_vreg_of_child(child);
 
     if (vreg)
+    {
         hop_add_vreg_insel(current_hop, vreg);
+        array_appendu(&vreg->used, current_hop);
+    }
 }
 
 static void emit_string(const char* data)
@@ -165,13 +168,17 @@ static struct insn* walk_instructions(struct burm_node* node, int goal)
                     vreg = new_vreg();
             }
 
-            insn->hop = current_hop = new_hop(0, insn->ir);
+            insn->hop = current_hop = new_hop(current_bb, insn->ir);
             insn->hop->output = vreg;
             if (vreg)
+            {
                 array_appendu(&current_hop->outs, vreg);
+                vreg->defined = current_hop;
+            }
 
             emit(insn);
             hop_print('I', current_hop);
+            array_append(&current_bb->hops, current_hop);
 
             if (goal != 1)
                 insn->ir->result = insn->hop->output;
@@ -220,10 +227,18 @@ static void select_instructions(void)
             int j;
 
             current_ir->result = new_vreg();
-            array_append(&current_bb->liveins, current_ir->result);
-            tracef('I', "I: %d is phi:", current_ir->result->id);
+            tracef('I', "I: $%d is phi:", current_ir->result->id);
             for (j=0; j<current_ir->u.phivalue.count; j++)
-                tracef('I', " $%d", current_ir->u.phivalue.item[j]->id);
+            {
+                struct basicblock* parentbb = current_ir->u.phivalue.item[j].left;
+                struct ir* parentir = current_ir->u.phivalue.item[j].right;
+                struct phi* phi = calloc(1, sizeof(*phi));
+                tracef('I', " %s=>$%d", parentbb->name, parentir->id);
+
+                phi->prev = parentbb;
+                phi->ir = parentir;
+                pmap_add(&current_bb->phis, current_ir->result, phi);
+            }
             tracef('I', "\n");
         }
         else
@@ -241,13 +256,13 @@ static void select_instructions(void)
 	}
 }
 
-void pass_instruction_selector(struct procedure* proc)
+void pass_instruction_selector(void)
 {
     int i;
 
-    for (i=0; i<proc->blocks.count; i++)
+    for (i=0; i<cfg.preorder.count; i++)
     {
-        current_bb = proc->blocks.item[i];
+        current_bb = cfg.preorder.item[i];
         select_instructions();
     }
 }
diff --git a/mach/proto/mcg/pass_livevreganalysis.c b/mach/proto/mcg/pass_livevreganalysis.c
new file mode 100644
index 000000000..889fe35b5
--- /dev/null
+++ b/mach/proto/mcg/pass_livevreganalysis.c
@@ -0,0 +1,73 @@
+#include "mcg.h"
+
+static bool finished;
+
+static void preload_blocks(void)
+{
+    /* Any variable referenced in a phi *must* be a liveout of one of our
+     * predecessors. */
+
+    int i, j;
+    for (i=0; i<cfg.preorder.count; i++)
+    {
+        struct basicblock* bb = cfg.preorder.item[i];
+
+        for (j=0; j<bb->phis.count; j++)
+        {
+            struct vreg* vreg = bb->phis.item[j].left;
+            struct phi* phi = bb->phis.item[j].right;
+
+            assert(array_contains(&bb->prevs, phi->prev));
+            array_appendu(&phi->prev->liveouts, phi->ir->result);
+        }
+    }
+}
+
+static void propagate_liveness(struct basicblock* bb)
+{
+	static ARRAYOF(struct vreg) current;
+	int i;
+
+	current.count = 0;
+	array_appendall(&current, &bb->liveouts);
+
+	for (i=bb->hops.count-1; i>=0; i--)
+	{
+		struct hop* hop = bb->hops.item[i];
+
+		array_removeall(&current, &hop->outs);
+		finished &= array_appendallu(&hop->throughs, &current);
+		array_appendallu(&current, &hop->ins);
+	}
+
+    for (i=0; i<bb->phis.count; i++)
+        array_remove(&current, bb->phis.item[i].left);
+
+	finished &= array_appendallu(&bb->liveins, &current);
+
+	for (i=0; i<bb->prevs.count; i++)
+	{
+		struct basicblock* prev = bb->prevs.item[i];
+		finished &= array_appendallu(&prev->liveouts, &current);
+	}
+}
+
+void pass_live_vreg_analysis(void)
+{
+	int i;
+
+    preload_blocks();
+
+	do
+	{
+		finished = true;
+
+		tracef('L', "L: beginning liveness pass\n");
+		for (i=0; i<dominance.postorder.count; i++)
+			propagate_liveness(dominance.postorder.item[i]);
+	}
+	while (!finished);
+}
+
+/* vim: set sw=4 ts=4 expandtab : */
+
diff --git a/mach/proto/mcg/pass_registerallocator.c b/mach/proto/mcg/pass_registerallocator.c
index 23121bc42..e7cf1d7dd 100644
--- a/mach/proto/mcg/pass_registerallocator.c
+++ b/mach/proto/mcg/pass_registerallocator.c
@@ -1,30 +1,7 @@
 #include "mcg.h"
 
-static ARRAYOF(struct basicblock) blocks;
-
-static void recursively_walk_dominance_graph(struct basicblock* bb)
-{
-	int i;
-
-	array_append(&blocks, bb);
-	tracef('R', "R: considering block %s\n", bb->name);
-
-	/* Skip the entry block (which is its own dominator). */
-	
-	for (i=1; i<dominance.graph.count; i++)
-	{
-		struct basicblock* left = dominance.graph.item[i].left;
-		struct basicblock* right = dominance.graph.item[i].right;
-		if (right == bb)
-			recursively_walk_dominance_graph(left);
-	}
-}
-
-void pass_register_allocator(struct procedure* proc)
+void pass_register_allocator(void)
 {
-	blocks.count = 0;
-	recursively_walk_dominance_graph(cfg.entry);
-	assert(blocks.count == proc->blocks.count);
 }
 
 /* vim: set sw=4 ts=4 expandtab : */
diff --git a/mach/proto/mcg/pass_ssa.c b/mach/proto/mcg/pass_ssa.c
index 0f7fc2d37..64f67698a 100644
--- a/mach/proto/mcg/pass_ssa.c
+++ b/mach/proto/mcg/pass_ssa.c
@@ -125,7 +125,8 @@ static void recursively_rewrite_tree(struct basicblock* bb)
             (ir->opcode == IR_PHI) &&
             array_contains(&needsphis, nextbb))
         {
-            array_appendu(&ir->u.phivalue, definitions.item[definitions.count-1]);
+            pmap_add(&ir->u.phivalue,
+                bb, definitions.item[definitions.count-1]);
         }
 
         recursively_rewrite_tree(nextbb);
diff --git a/mach/proto/mcg/procedure.c b/mach/proto/mcg/procedure.c
index 69aba0af8..b6216542a 100644
--- a/mach/proto/mcg/procedure.c
+++ b/mach/proto/mcg/procedure.c
@@ -36,6 +36,108 @@ static void print_blocks(char k, struct procedure* proc)
 	}
 }
 
+static void print_hops(char k, struct procedure* proc)
+{
+    int i;
+
+    tracef(k, "%c: procedure %s\n", k, proc->name);
+    for (int i=0; i<dominance.preorder.count; i++)
+    {
+		struct basicblock* bb = dominance.preorder.item[i];
+		int j;
+
+        tracef(k, "%c:\n", k);
+		tracef(k, "%c: %sBLOCK: %s\n", k,
+            bb->is_fake ? "FAKE " : "",
+            bb->name);
+
+        if (bb->prevs.count > 0)
+        {
+            tracef(k, "%c: FROM:", k);
+            for (j=0; j<bb->prevs.count; j++)
+                tracef(k, " %s", bb->prevs.item[j]->name);
+            tracef(k, "\n");
+        }
+
+        if (bb->nexts.count > 0)
+        {
+            tracef(k, "%c:   TO:", k);
+            for (j=0; j<bb->nexts.count; j++)
+                tracef(k, " %s", bb->nexts.item[j]->name);
+            tracef(k, "\n");
+        }
+
+        if (bb->liveins.count > 0)
+        {
+            tracef(k, "%c:  INS:", k);
+            for (j=0; j<bb->liveins.count; j++)
+                tracef(k, " %%%d", bb->liveins.item[j]->id);
+            tracef(k, "\n");
+        }
+
+        if (bb->liveouts.count > 0)
+        {
+            tracef(k, "%c: OUTS:", k);
+            for (j=0; j<bb->liveouts.count; j++)
+                tracef(k, " %%%d", bb->liveouts.item[j]->id);
+            tracef(k, "\n");
+        }
+
+        if (bb->phis.count > 0)
+        {
+            tracef(k, "%c: PHIS:", k);
+            for (j=0; j<bb->phis.count; j++)
+            {
+                struct vreg* vreg = bb->phis.item[j].left;
+                struct phi* phi = bb->phis.item[j].right;
+
+                tracef(k, " %%%d(via %s)=>%%%d",
+                    phi->ir->result->id,
+                    phi->prev->name,
+                    vreg->id);
+            }
+            tracef(k, "\n");
+        }
+
+		for (j=0; j<bb->hops.count; j++)
+			hop_print(k, bb->hops.item[j]);
+    }
+}
+
+static void write_cfg_graph(const char* name)
+{
+    int i;
+
+    fprintf(cfg_dot_file, "subgraph %s {\n", name);
+    fprintf(cfg_dot_file, "\t%s [color=red];\n", cfg.entry->name);
+
+    for (i=0; i<cfg.graph.count; i++)
+    {
+        fprintf(cfg_dot_file, "\t%s -> %s;\n",
+            cfg.graph.item[i].left->name,
+            cfg.graph.item[i].right->name);
+    }
+
+    fprintf(cfg_dot_file, "}\n");
+}
+
+static void write_dominance_graph(const char* name)
+{
+    int i;
+
+    fprintf(dominance_dot_file, "subgraph %s {\n", name);
+    fprintf(dominance_dot_file, "\t%s [color=green];\n", cfg.entry->name);
+
+    for (i=0; i<dominance.graph.count; i++)
+    {
+        fprintf(dominance_dot_file, "\t%s -> %s;\n",
+            dominance.graph.item[i].right->name,
+            dominance.graph.item[i].left->name);
+    }
+
+    fprintf(dominance_dot_file, "}\n");
+}
+
 void procedure_compile(struct procedure* proc)
 {
 	int i;
@@ -48,25 +150,31 @@ void procedure_compile(struct procedure* proc)
     pass_eliminate_trivial_blocks(proc);
     pass_remove_dead_blocks(proc);
 
+    print_blocks('2', proc);
+    update_graph_data(proc);
+    pass_split_critical_edges(proc);
     update_graph_data(proc);
 
     /* Passes from here on can't alter the BB graph without also updating prevs
      * and nexts (and then calling update_graph_data()). */
 
-    print_blocks('2', proc);
-    pass_convert_stack_ops(proc);
     print_blocks('3', proc);
-    pass_convert_locals_to_ssa(proc);
+    pass_convert_stack_ops(proc);
     print_blocks('4', proc);
-    pass_promote_float_ops(proc);
+    pass_convert_locals_to_ssa(proc);
     print_blocks('5', proc);
-    pass_split_critical_edges(proc);
+    pass_promote_float_ops(proc);
     print_blocks('6', proc);
 
-    update_graph_data(proc);
+    pass_instruction_selector();
+    pass_live_vreg_analysis();
+    print_hops('7', proc);
+    //pass_register_allocator();
 
-    pass_instruction_selector(proc);
-    pass_register_allocator(proc);
+    if (cfg_dot_file)
+        write_cfg_graph(proc->name);
+    if (dominance_dot_file)
+        write_dominance_graph(proc->name);
 }
 
 /* vim: set sw=4 ts=4 expandtab : */
diff --git a/mach/proto/mcg/reg.h b/mach/proto/mcg/reg.h
index 62bbb6900..b901eb667 100644
--- a/mach/proto/mcg/reg.h
+++ b/mach/proto/mcg/reg.h
@@ -14,6 +14,8 @@ struct hreg
 struct vreg
 {
 	int id;
+    struct hop* defined;
+    ARRAYOF(struct hop) used;
 };
 
 extern struct vreg* new_vreg(void);
-- 
2.34.1