From 3eb01865250c0495a2b35046ca94a4f9ef9d6044 Mon Sep 17 00:00:00 2001
From: David Given <dg@cowlark.com>
Date: Thu, 12 Jan 2017 21:03:27 +0100
Subject: [PATCH] Archival checkin (won't build): monster refactor; don't
 allocate vregs at instruction selection time, but instead deal with 'values'
 which are tied to their parent IR. The code is now way cleaner and more
 understandable. We'll aasign vregs in a later pass, as we convert to
 elementary form.

---
 mach/proto/mcg/basicblock.h                |  11 +-
 mach/proto/mcg/hop.c                       |  61 +++++---
 mach/proto/mcg/hop.h                       |  29 ++--
 mach/proto/mcg/ir.c                        |  15 ++
 mach/proto/mcg/ir.h                        |  17 ++-
 mach/proto/mcg/mcg.h                       |   5 +-
 mach/proto/mcg/pass_instructionselection.c | 167 +++++++++------------
 mach/proto/mcg/pass_livevalueanalysis.c    |  59 ++++++++
 mach/proto/mcg/pass_livevreganalysis.c     | 104 -------------
 mach/proto/mcg/procedure.c                 |  38 ++---
 mach/proto/mcg/procedure.h                 |   2 +-
 mach/proto/mcg/reg.c                       |   9 --
 mach/proto/mcg/reg.h                       |  15 --
 mach/proto/mcg/treebuilder.c               |   3 +-
 14 files changed, 234 insertions(+), 301 deletions(-)
 create mode 100644 mach/proto/mcg/pass_livevalueanalysis.c
 delete mode 100644 mach/proto/mcg/pass_livevreganalysis.c

diff --git a/mach/proto/mcg/basicblock.h b/mach/proto/mcg/basicblock.h
index 362a05f7f..00298f6c9 100644
--- a/mach/proto/mcg/basicblock.h
+++ b/mach/proto/mcg/basicblock.h
@@ -18,15 +18,8 @@ struct basicblock
     ARRAYOF(struct basicblock) nexts;
     int order; /* used by dominance graph code */
 
-    PMAPOF(struct vreg, struct phi) phis;
-
-    /* Used by liveness calculation. */
-    ARRAYOF(struct vreg) liveins;
-    ARRAYOF(struct vreg) liveouts;
-
-    /* Register assignments on entry and exit. */
-    register_assignment_t regsin;
-    register_assignment_t* regsout; /* points at regsout of the last insn. */
+    PMAPOF(struct ir, struct ir) imports;
+    PMAPOF(struct ir, struct ir) exports;
 
     bool is_fake : 1;
     bool is_root : 1;
diff --git a/mach/proto/mcg/hop.c b/mach/proto/mcg/hop.c
index ebf0568ff..1d9e857f9 100644
--- a/mach/proto/mcg/hop.c
+++ b/mach/proto/mcg/hop.c
@@ -17,14 +17,12 @@ struct hop* new_hop(struct basicblock* bb, struct ir* ir)
 	return hop;
 }
 
-struct hop* new_copy_hop(struct basicblock* bb, struct vreg* src, struct vreg* dest)
+struct hop* new_move_hop(struct basicblock* bb)
 {
 	struct hop* hop = heap_alloc(&proc_heap, 1, sizeof(*hop));
 	hop->id = hop_count++;
     hop->bb = bb;
     hop->is_move = true;
-    array_append(&hop->ins, src);
-    array_append(&hop->outs, dest);
 	return hop;
 }
 
@@ -37,9 +35,9 @@ static struct insel* new_insel(enum insel_type type)
 
 void hop_add_string_insel(struct hop* hop, const char* string)
 {
-	struct insel* insel = new_insel(INSEL_STRING);
-	insel->u.string = string;
-	array_append(&hop->insels, insel);
+    struct insel* insel = new_insel(INSEL_STRING);
+    insel->u.string = string;
+    array_append(&hop->insels, insel);
 }
 
 void hop_add_hreg_insel(struct hop* hop, struct hreg* hreg, int index)
@@ -50,10 +48,10 @@ void hop_add_hreg_insel(struct hop* hop, struct hreg* hreg, int index)
 	array_append(&hop->insels, insel);
 }
 
-void hop_add_vreg_insel(struct hop* hop, struct vreg* vreg, int index)
+void hop_add_vreg_insel(struct hop* hop, struct value* value, int index)
 {
 	struct insel* insel = new_insel(INSEL_VREG);
-	insel->u.vreg = vreg;
+	insel->u.value = value;
     insel->index = index;
 	array_append(&hop->insels, insel);
 }
@@ -61,7 +59,7 @@ void hop_add_vreg_insel(struct hop* hop, struct vreg* vreg, int index)
 void hop_add_value_insel(struct hop* hop, struct ir* ir)
 {
 	struct insel* insel = new_insel(INSEL_VALUE);
-	insel->u.value = ir;
+	insel->u.ir = ir;
 	array_append(&hop->insels, insel);
 }
 
@@ -88,8 +86,8 @@ void hop_add_lb_offset_insel(struct hop* hop, int offset)
 
 void hop_add_eoi_insel(struct hop* hop)
 {
-	struct insel* insel = new_insel(INSEL_EOI);
-	array_append(&hop->insels, insel);
+    struct insel* insel = new_insel(INSEL_EOI);
+    array_append(&hop->insels, insel);
 }
 
 void hop_add_insel(struct hop* hop, const char* fmt, ...)
@@ -145,7 +143,7 @@ void hop_add_insel(struct hop* hop, const char* fmt, ...)
                     break;
 
                 case 'V':
-                    hop_add_vreg_insel(hop, va_arg(ap, struct vreg*), index);
+                    hop_add_vreg_insel(hop, va_arg(ap, struct value*), index);
                     break;
             }
         }
@@ -198,12 +196,24 @@ static void print_header(char k, struct hop* hop)
         tracef(k, " from $%d", hop->ir->id);
     tracef(k, ":");
 
-    for (i=0; i<hop->ins.count; i++)
-        tracef(k, " r%%%d", hop->ins.item[i]->id);
+    for (i=0; i<hop->inputs.count; i++)
+    {
+        struct value* value = hop->inputs.item[i];
+        tracef(k, " r$%d:%d", value->ir->id, value->subid);
+    }
+
+    for (i=0; i<hop->outputs.count; i++)
+    {
+        struct value* value = hop->outputs.item[i];
+        tracef(k, " w$%d:%d", value->ir->id, value->subid);
+    }
+
     for (i=0; i<hop->throughs.count; i++)
-        tracef(k, " =%%%d", hop->throughs.item[i]->id);
-    for (i=0; i<hop->outs.count; i++)
-        tracef(k, " w%%%d", hop->outs.item[i]->id);
+    {
+        struct value* value = hop->throughs.item[i];
+        tracef(k, " =$%d:%d", value->ir->id, value->subid);
+    }
+
     tracef(k, " ");
 }
 
@@ -241,8 +251,11 @@ char* hop_render(struct hop* hop)
     bufferlen = 0;
 	buffer[0] = '\0';
 
+    if (hop->pseudo)
+        appendf("@");
+
     if (hop->is_move && (hop->insels.count == 0))
-        appendf("(move %%%d -> %%%d)\n", hop->ins.item[0]->id, hop->outs.item[0]->id);
+        appendf("(move)\n");
 
 	for (i=0; i<hop->insels.count; i++)
 	{
@@ -266,7 +279,8 @@ char* hop_render(struct hop* hop)
 
 			case INSEL_VREG:
             {
-                struct vreg* vreg = insel->u.vreg;
+                struct value* value = insel->u.value;
+                #if 0
                 struct hreg* hreg = pmap_findright(&hop->regsin, vreg);
                 if (!hreg)
                     hreg = pmap_findright(&hop->regsout, vreg);
@@ -274,6 +288,10 @@ char* hop_render(struct hop* hop)
                     appendf("%s", hreg->brd->names[insel->index]);
                 else
                     appendf("%%%d.%d", vreg->id, insel->index);
+                #endif
+                appendf("$%d:%d", value->ir->id, value->subid);
+                if (insel->index)
+                    appendf(".%d", insel->index);
 				break;
             }
 
@@ -295,7 +313,7 @@ char* hop_render(struct hop* hop)
 
 			case INSEL_VALUE:
 			{
-				struct ir* ir = insel->u.value;
+				struct ir* ir = insel->u.ir;
 				switch (ir->opcode)
 				{
 					case IR_BLOCK:
@@ -326,6 +344,9 @@ char* hop_render(struct hop* hop)
             default:
                 assert(false);
 		}
+
+        if (hop->pseudo)
+            appendf(" ");
 	}
 
     return buffer;
diff --git a/mach/proto/mcg/hop.h b/mach/proto/mcg/hop.h
index 1e6be2049..b97ed9b0e 100644
--- a/mach/proto/mcg/hop.h
+++ b/mach/proto/mcg/hop.h
@@ -21,20 +21,13 @@ struct insel
 	{
 		const char* string;
         struct hreg* hreg;
-		struct vreg* vreg;
-		struct ir* value;
+		struct value* value;
+		struct ir* ir;
         int offset;
 	}
 	u;
 };
 
-struct constraint
-{
-    uint32_t attrs;
-	bool preserved;
-    struct vreg* equals_to;
-};
-
 struct hop
 {
 	int id;
@@ -42,24 +35,22 @@ struct hop
 	struct ir* ir;
     const struct burm_instruction_data* insndata;
 	ARRAYOF(struct insel) insels;
-	struct vreg* output;
+	struct value* value;
 	bool is_move;
+	const char* pseudo;
+	PMAPOF(struct value, struct value) equals_constraint;
 
-    PMAPOF(struct vreg, struct constraint) constraints;
-
-	ARRAYOF(struct vreg) ins;
-	ARRAYOF(struct vreg) outs;
-    ARRAYOF(struct vreg) throughs;
-    register_assignment_t regsin;
-    register_assignment_t regsout;
+	ARRAYOF(struct value) inputs;
+	ARRAYOF(struct value) outputs;
+	ARRAYOF(struct value) throughs;
 };
 
 extern struct hop* new_hop(struct basicblock* bb, struct ir* ir);
-extern struct hop* new_copy_hop(struct basicblock* bb, struct vreg* src, struct vreg* dest);
+extern struct hop* new_move_hop(struct basicblock* bb);
 
 extern void hop_add_string_insel(struct hop* hop, const char* string);
 extern void hop_add_hreg_insel(struct hop* hop, struct hreg* hreg, int index);
-extern void hop_add_vreg_insel(struct hop* hop, struct vreg* vreg, int index);
+extern void hop_add_vreg_insel(struct hop* hop, struct value* value, int index);
 extern void hop_add_value_insel(struct hop* hop, struct ir* ir);
 extern void hop_add_st_offset_insel(struct hop* hop, struct hreg* hreg);
 extern void hop_add_ab_offset_insel(struct hop* hop, int offset);
diff --git a/mach/proto/mcg/ir.c b/mach/proto/mcg/ir.c
index 1a7436f5c..0e0459d86 100644
--- a/mach/proto/mcg/ir.c
+++ b/mach/proto/mcg/ir.c
@@ -2,9 +2,24 @@
 
 static int next_id = 0;
 
+uint32_t value_hash_function(void* key)
+{
+    struct value* value = key;
+    /* This is the standard C++ std::hash_combine. */
+    return value->ir->id + 0x9e3779b9 + (value->subid << 6) + (value->subid >> 2);
+}
+
+bool value_comparison_function(void* key1, void* key2)
+{
+    struct value* val1 = key1;
+    struct value* val2 = key2;
+    return (val1->ir->id == val2->ir->id) && (val1->subid == val2->subid);
+}
+
 struct ir* new_ir0(int opcode, int size)
 {
 	struct ir* ir = calloc(1,  sizeof(struct ir));
+    ir->value.ir = ir;
 	ir->id = next_id++;
 	ir->opcode = opcode;
 	ir->size = size;
diff --git a/mach/proto/mcg/ir.h b/mach/proto/mcg/ir.h
index 73e46b1b9..ec27b42ef 100644
--- a/mach/proto/mcg/ir.h
+++ b/mach/proto/mcg/ir.h
@@ -3,8 +3,23 @@
 
 #include "ircodes.h"
 
+struct value
+{
+	struct ir* ir;
+	int subid;
+	uint32_t attrs;
+};
+
+extern uint32_t value_hash_function(void* key);
+extern bool value_comparison_function(void* key1, void* key2);
+#define HASHTABLE_OF_VALUES \
+	{ value_hash_function, value_comparison_function }
+
 struct ir
 {
+	/* A struct ir must be castable to a struct value */
+	struct value value;
+
 	int id;
 	enum ir_opcode opcode;
 	int size;
@@ -21,8 +36,6 @@ struct ir
 		struct basicblock* bvalue;
         PMAPOF(struct basicblock, struct ir) phivalue;
 	} u;
-
-	struct vreg* result;     /* vreg containing IR result */
 };
 
 extern const char* ir_names[];
diff --git a/mach/proto/mcg/mcg.h b/mach/proto/mcg/mcg.h
index 96e9d6ec2..e8b46592e 100644
--- a/mach/proto/mcg/mcg.h
+++ b/mach/proto/mcg/mcg.h
@@ -18,7 +18,6 @@
 #include "em_flag.h"
 #include "em_ptyp.h"
 #include "array.h"
-#include "imap.h"
 #include "pmap.h"
 #include "heap.h"
 #include "diagnostics.h"
@@ -81,7 +80,7 @@ struct em
         } bvalue;
     } u;
 };
-    
+
 extern const char* aprintf(const char* fmt, ...);
 extern void tracef(char k, const char* fmt, ...);
 extern bool tracing(char k);
@@ -119,7 +118,7 @@ extern void pass_group_irs(void);
 extern void pass_infer_types(void);
 extern void pass_insert_moves(void);
 extern void pass_instruction_selector(void);
-extern void pass_live_vreg_analysis(void);
+extern void pass_live_value_analysis(void);
 extern void pass_add_prologue_epilogue(void);
 extern void pass_register_allocator(void);
 extern void pass_remove_dead_blocks(void);
diff --git a/mach/proto/mcg/pass_instructionselection.c b/mach/proto/mcg/pass_instructionselection.c
index 3dc187c96..cf959e382 100644
--- a/mach/proto/mcg/pass_instructionselection.c
+++ b/mach/proto/mcg/pass_instructionselection.c
@@ -4,6 +4,9 @@
 
 struct insn
 {
+    /* struct insn must be castable to a struct value */
+    struct value value;
+
     struct ir* ir;
     struct hop* hop;
     const struct burm_instruction_data* insndata;
@@ -12,6 +15,8 @@ struct insn
 };
 
 static struct basicblock* current_bb;
+static struct ir* root_ir;
+static int hop_id;
 static struct hop* current_hop;
 static struct ir* current_ir;
 static struct insn* current_insn;
@@ -34,27 +39,25 @@ void burm_panic_cannot_match(struct burm_node* node)
 
 static void emit_return_reg(int index)
 {
-    hop_add_vreg_insel(current_hop, current_hop->output, index);
+    hop_add_vreg_insel(current_hop, &current_insn->value, index);
 }
 
-static struct vreg* find_vreg_of_child(int child)
+static struct value* find_value_of_child(int child)
 {
     struct insn* insn = current_insn->children[child];
 
     if (insn->hop)
-        return insn->hop->output;
+        return insn->hop->value;
     else
-        return insn->ir->result;
+        return &insn->ir->value;
 }
 
 static void emit_reg(int child, int index)
 {
-    struct vreg* vreg = find_vreg_of_child(child);
+    struct value* value = find_value_of_child(child);
 
-    if (vreg)
-    {
-        hop_add_vreg_insel(current_hop, vreg, index);
-    }
+    assert(value);
+    hop_add_vreg_insel(current_hop, value, index);
 }
 
 static void emit_string(const char* data)
@@ -77,36 +80,21 @@ static void emit_eoi(void)
 	hop_add_eoi_insel(current_hop);
 }
 
-static struct constraint* get_constraint(struct vreg* vreg)
-{
-    struct constraint* c = pmap_findleft(&current_hop->constraints, vreg);
-    if (!c)
-    {
-        c = heap_alloc(&proc_heap, 1, sizeof(*c));
-        pmap_put(&current_hop->constraints, vreg, c);
-    }
-    return c;
-}
-
 static void constrain_input_reg(int child, uint32_t attr)
 {
-    struct vreg* vreg = find_vreg_of_child(child);
+    struct value* value = find_value_of_child(child);
     struct constraint* c;
 
-    assert(vreg);
-
-    array_appendu(&current_hop->ins, vreg);
-    get_constraint(vreg)->attrs = attr;
+    array_appendu(&current_hop->inputs, value);
+    value->attrs = attr;
 }
 
 static void constrain_input_reg_preserved(int child)
 {
-    struct vreg* vreg = find_vreg_of_child(child);
+    struct value* value = find_value_of_child(child);
     struct constraint* c;
 
-    assert(vreg);
-    array_appendu(&current_hop->throughs, vreg);
-    get_constraint(vreg)->preserved = true;
+    array_appendu(&current_hop->throughs, value);
 }
 
 static uint32_t find_type_from_constraint(uint32_t attr)
@@ -122,7 +110,7 @@ static uint32_t find_type_from_constraint(uint32_t attr)
     {
         if (brd->attrs & attr)
         {
-            const uint32_t type_attrs = 
+            const uint32_t type_attrs =
                 (burm_int_ATTR | burm_float_ATTR |
                  burm_long_ATTR | burm_double_ATTR);
 
@@ -139,22 +127,16 @@ static uint32_t find_type_from_constraint(uint32_t attr)
 
 static void constrain_output_reg(uint32_t attr)
 {
-    struct vreg* vreg = current_hop->output;
-
-    if (!vreg)
-        current_hop->output = vreg = new_vreg();
+    struct value* value = &current_insn->value;
 
-    array_appendu(&current_hop->outs, vreg);
-    vreg->type = find_type_from_constraint(attr);
-
-    get_constraint(vreg)->attrs = attr;
+    array_appendu(&current_hop->outputs, value);
+    value->attrs = find_type_from_constraint(attr);
 }
 
 static void constrain_output_reg_equal_to(int child)
 {
-    struct vreg* vreg = find_vreg_of_child(child);
-
-    get_constraint(current_hop->output)->equals_to = vreg;
+    struct value* value = find_value_of_child(child);
+    pmap_add(&current_hop->equals_constraint, &current_hop->value, value);
 }
 
 static const struct burm_emitter_data emitter_data =
@@ -186,6 +168,10 @@ static struct insn* walk_instructions(struct burm_node* node, int goal)
     struct insn* insn = heap_alloc(&proc_heap, 1, sizeof(*insn));
     int i;
 
+    insn->value.ir = current_ir;
+    /* hop IDs count in preorder, so the result is always in $thing:0. */
+    insn->value.subid = hop_id++;
+
     insn->ir = node->ir;
     insn->num_children = 0;
 
@@ -210,7 +196,8 @@ static struct insn* walk_instructions(struct burm_node* node, int goal)
             i++;
         }
 
-        tracef('I', "I: $%d goal %d %s selected %d: %s\n",
+        tracef('I', "I: $%d:%d for node $%d goal %d %s selected %d: %s\n",
+            insn->value.ir->id, insn->value.subid,
             node->ir->id,
             goal,
             insn->insndata->is_fragment ? "fragment" : "instruction",
@@ -223,30 +210,25 @@ static struct insn* walk_instructions(struct burm_node* node, int goal)
             current_hop->insndata = insn->insndata;
             emit(insn);
 
-            if (!current_hop->output)
+            current_hop->value = &insn->value;
+            switch (node->label)
             {
-                switch (node->label)
-                {
-                    case ir_to_esn(IR_REG, 0):
-                        current_hop->output = node->ir->result;
-                        assert(current_hop->output != NULL);
-                        break;
-
-                    case ir_to_esn(IR_NOP, 'I'):
-                    case ir_to_esn(IR_NOP, 'F'):
-                    case ir_to_esn(IR_NOP, 'L'):
-                    case ir_to_esn(IR_NOP, 'D'):
-                        current_hop->output = node->left->ir->result;
-                        assert(current_hop->output != NULL);
-                        break;
-                }
+                case ir_to_esn(IR_REG, 0):
+                    current_hop->value = &node->ir->value;
+                    break;
+
+                case ir_to_esn(IR_NOP, 'I'):
+                case ir_to_esn(IR_NOP, 'F'):
+                case ir_to_esn(IR_NOP, 'L'):
+                case ir_to_esn(IR_NOP, 'D'):
+                    array_appendu(&current_hop->inputs, &insn->children[0]->value);
+                    array_appendu(&current_hop->outputs, current_hop->value);
+                    hop_add_insel(current_hop, "@copy %V %V", &insn->children[0]->value, current_hop->value);
+                    break;
             }
 
             hop_print('I', current_hop);
             array_append(&current_bb->hops, current_hop);
-
-            if ((goal != burm_stmt_NT) && !insn->ir->result)
-                insn->ir->result = insn->hop->output;
         }
     }
 
@@ -276,48 +258,47 @@ static struct burm_node* build_shadow_tree(struct ir* root, struct ir* ir)
 
 static void select_instructions(void)
 {
-	int i;
+	int i, j;
 
 	tracef('I', "I: BLOCK: %s\n", current_bb->name);
 
-	for (i=0; i<current_bb->irs.count; i++)
-	{
-        struct burm_node* shadow;
-		int insnno;
-
+    for (i=0; i<current_bb->irs.count; i++)
+    {
 		current_ir = current_bb->irs.item[i];
+        if (current_ir->opcode != IR_PHI)
+            break;
 
-        if (current_ir->opcode == IR_PHI)
+        tracef('I', "I: $%d is phi:", current_ir->id);
+        for (j=0; j<current_ir->u.phivalue.count; j++)
         {
-            int j;
+            struct basicblock* parentbb = current_ir->u.phivalue.item[j].left;
+            struct ir* parentir = current_ir->u.phivalue.item[j].right;
+            tracef('I', " %s=>$%d", parentbb->name, parentir->id);
 
-            current_ir->result = new_vreg();
-            tracef('I', "I: $%d is phi:", current_ir->result->id);
-            for (j=0; j<current_ir->u.phivalue.count; j++)
-            {
-                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");
+            pmap_add(&current_bb->imports, parentir, current_ir);
+            pmap_add(&parentbb->exports, parentir, current_ir);
         }
-        else
-        {
-            ir_print('I', current_ir);
-            shadow = build_shadow_tree(current_ir, current_ir);
-            burm_label(shadow);
+        tracef('I', "\n");
+    }
 
-            insnno = burm_rule(shadow->state_label, 1);
-            if (!insnno)
-                burm_panic_cannot_match(shadow);
+	for (; i<current_bb->irs.count; i++)
+	{
+        struct burm_node* shadow;
+        int insnno;
 
-            walk_instructions(shadow, burm_stmt_NT);
-        }
+		current_ir = current_bb->irs.item[i];
+        assert(current_ir->opcode != IR_PHI);
+
+        ir_print('I', current_ir);
+        shadow = build_shadow_tree(current_ir, current_ir);
+        burm_label(shadow);
+
+        insnno = burm_rule(shadow->state_label, 1);
+        if (!insnno)
+            burm_panic_cannot_match(shadow);
+
+        hop_id = 0;
+        walk_instructions(shadow, burm_stmt_NT);
 	}
 }
 
diff --git a/mach/proto/mcg/pass_livevalueanalysis.c b/mach/proto/mcg/pass_livevalueanalysis.c
new file mode 100644
index 000000000..9ecc23b39
--- /dev/null
+++ b/mach/proto/mcg/pass_livevalueanalysis.c
@@ -0,0 +1,59 @@
+#include "mcg.h"
+
+static struct set known_live = { HASHTABLE_OF_VALUES };
+
+static void propagate_liveness(struct basicblock* bb)
+{
+    static struct set current;
+	int i, j;
+
+    set_empty(&known_live);
+
+    for (i=0; i<bb->exports.count; i++)
+        set_add(&known_live, bb->exports.item[i].left);
+
+	for (i=bb->hops.count-1; i>=0; i--)
+	{
+		struct hop* hop = bb->hops.item[i];
+
+        /* Values are only ever written once, so if we see a write then we
+         * know the value was not live before this. */
+
+        for (j=0; j<hop->outputs.count; j++)
+        {
+            struct value* value = hop->outputs.item[j];
+            set_remove(&known_live, value);
+        }
+
+        /* Propagate the set of live values across this hop. */
+
+        {
+            struct set_iterator si = {};
+            while (set_next(&known_live, &si))
+            {
+                struct value* value = si.item;
+                array_appendu(&hop->throughs, value);
+            }
+        }
+
+        /* Values which are read from must have come from somewhere, and so
+         * become live. */
+
+        for (j=0; j<hop->inputs.count; j++)
+        {
+            struct value* value = hop->inputs.item[j];
+            set_add(&known_live, value);
+        }
+	}
+}
+
+void pass_live_value_analysis(void)
+{
+	int i;
+
+    for (i=0; i<dominance.postorder.count; i++)
+        propagate_liveness(dominance.postorder.item[i]);
+}
+
+/* vim: set sw=4 ts=4 expandtab : */
+
diff --git a/mach/proto/mcg/pass_livevreganalysis.c b/mach/proto/mcg/pass_livevreganalysis.c
deleted file mode 100644
index 7e361b929..000000000
--- a/mach/proto/mcg/pass_livevreganalysis.c
+++ /dev/null
@@ -1,104 +0,0 @@
-#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 bool add_set_to_array(struct set* set, void* arrayp)
-{
-    bool nochange = true;
-    struct array* array = arrayp;
-    struct set_iterator sit = {};
-
-    while (set_next(set, &sit))
-        nochange &= array_appendu(array, sit.item);
-
-    return nochange;
-}
-
-static void add_array_to_set(void* arrayp, struct set* set)
-{
-    struct array* array = arrayp;
-    int i;
-
-    for (i=0; i<array->count; i++)
-        set_add(set, array->item[i]);
-}
-
-static void remove_array_from_set(void* arrayp, struct set* set)
-{
-    struct array* array = arrayp;
-    int i;
-
-    for (i=0; i<array->count; i++)
-        set_remove(set, array->item[i]);
-}
-
-static void propagate_liveness(struct basicblock* bb)
-{
-    static struct set current;
-	int i, j;
-
-    set_empty(&current);
-
-    add_array_to_set(&bb->liveouts, &current);
-
-	for (i=bb->hops.count-1; i>=0; i--)
-	{
-		struct hop* hop = bb->hops.item[i];
-
-        remove_array_from_set(&hop->outs, &current);
-        finished &= add_set_to_array(&current, &hop->throughs);
-        add_array_to_set(&hop->ins, &current);
-	}
-
-    for (i=0; i<bb->phis.count; i++)
-        set_remove(&current, bb->phis.item[i].left);
-
-    finished &= add_set_to_array(&current, &bb->liveins);
-
-	for (i=0; i<bb->prevs.count; i++)
-	{
-		struct basicblock* prev = bb->prevs.item[i];
-        finished &= add_set_to_array(&current, &prev->liveouts);
-	}
-}
-
-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/procedure.c b/mach/proto/mcg/procedure.c
index 393b8a1cc..c9e37579c 100644
--- a/mach/proto/mcg/procedure.c
+++ b/mach/proto/mcg/procedure.c
@@ -70,35 +70,21 @@ static void print_hops(char k)
             tracef(k, "\n");
         }
 
-        if (bb->liveins.count > 0)
+        if (bb->imports.count > 0)
         {
             tracef(k, "%c:  INS:", k);
-            for (j=0; j<bb->liveins.count; j++)
-                tracef(k, " %%%d", bb->liveins.item[j]->id);
+            for (j=0; j<bb->imports.count; j++)
+                tracef(k, " $%d->$%d",
+                    bb->imports.item[j].left->id, bb->imports.item[j].right->id);
             tracef(k, "\n");
         }
 
-        if (bb->liveouts.count > 0)
+        if (bb->exports.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);
-            }
+            for (j=0; j<bb->exports.count; j++)
+                tracef(k, " $%d->$%d",
+                    bb->exports.item[j].left->id, bb->exports.item[j].right->id);
             tracef(k, "\n");
         }
 
@@ -115,7 +101,7 @@ static void emit_procedure(struct procedure* proc)
     for (i=0; i<dominance.preorder.count; i++)
     {
         struct basicblock* bb = dominance.preorder.item[i];
-        
+
         fprintf(outputfile, "%s:\n", platform_label(bb->name));
         for (j=0; j<bb->hops.count; j++)
         {
@@ -197,11 +183,12 @@ void procedure_compile(struct procedure* proc)
     print_blocks('6');
     pass_instruction_selector();
     print_hops('7');
+    pass_live_value_analysis();
+    print_hops('8');
+#if 0
     pass_split_live_ranges();
     pass_determine_vreg_usage();
-    print_hops('8');
 
-    pass_live_vreg_analysis();
     pass_register_allocator();
     pass_add_prologue_epilogue();
     print_hops('9');
@@ -209,6 +196,7 @@ void procedure_compile(struct procedure* proc)
     emit_procedure(proc);
 
     heap_free(&proc_heap);
+#endif
 }
 
 /* vim: set sw=4 ts=4 expandtab : */
diff --git a/mach/proto/mcg/procedure.h b/mach/proto/mcg/procedure.h
index 55ed71022..fba03390c 100644
--- a/mach/proto/mcg/procedure.h
+++ b/mach/proto/mcg/procedure.h
@@ -21,7 +21,7 @@ struct procedure
     int fp_to_sb; /* spill base (indexes up) */
     int fp_to_rb; /* saved registers base (indexes up) */
     ARRAYOF(struct basicblock) blocks;
-    IMAPOF(struct local) locals;
+    PMAPOF(void, struct local) locals;
     ARRAYOF(struct hreg) usedregs;
 };
 
diff --git a/mach/proto/mcg/reg.c b/mach/proto/mcg/reg.c
index 5c57790ef..f94ab00ad 100644
--- a/mach/proto/mcg/reg.c
+++ b/mach/proto/mcg/reg.c
@@ -1,14 +1,5 @@
 #include "mcg.h"
 
-static int vreg_count = 1;
-
-struct vreg* new_vreg(void)
-{
-	struct vreg* vreg = heap_alloc(&proc_heap, 1, sizeof *vreg);
-	vreg->id = vreg_count++;
-	return vreg;
-}
-
 struct hreg* new_hreg(const struct burm_register_data* brd)
 {
 	struct hreg* hreg = heap_alloc(&proc_heap, 1, sizeof *hreg);
diff --git a/mach/proto/mcg/reg.h b/mach/proto/mcg/reg.h
index c0cd47fa1..9a54cecfc 100644
--- a/mach/proto/mcg/reg.h
+++ b/mach/proto/mcg/reg.h
@@ -13,21 +13,6 @@ struct hreg
     ARRAYOF(struct hreg) aliases;
 };
 
-struct vreg
-{
-	int id;
-    uint32_t type;
-    struct anode* anode;
-    bool is_spillable;
-    struct hop* defined;
-    ARRAYOF(struct hop) usedhops;
-    ARRAYOF(struct basicblock) usedphis;
-};
-
-typedef PMAPOF(struct hreg, struct vreg) register_assignment_t;
-
-extern struct vreg* new_vreg(void);
-
 extern struct hreg* new_hreg(const struct burm_register_data* brd);
 extern struct hreg* new_stacked_hreg(uint32_t type);
 
diff --git a/mach/proto/mcg/treebuilder.c b/mach/proto/mcg/treebuilder.c
index 667562e8d..7184ef864 100644
--- a/mach/proto/mcg/treebuilder.c
+++ b/mach/proto/mcg/treebuilder.c
@@ -181,7 +181,8 @@ void tb_regvar(struct procedure* procedure, arith offset, int size, int type, in
     local->size = size;
     local->offset = offset;
     local->is_register = true;
-    imap_put(&procedure->locals, offset, local);
+
+    pmap_put(&procedure->locals, (void*)(intptr_t)offset, local);
 }
 
 static struct ir* address_of_external(const char* label, arith offset)
-- 
2.34.1