From 9077baa85027f2b860a28894021251ad7a617e03 Mon Sep 17 00:00:00 2001 From: David Given Date: Thu, 22 Sep 2016 23:19:29 +0200 Subject: [PATCH] Add a bodged in algorithm for converting basic block communication from stacked variables to SSA. Also add dead block removal and block splicing. IR code is much better now. --- mach/proto/mcg/array.c | 19 +++++++ mach/proto/mcg/array.h | 4 ++ mach/proto/mcg/compile.c | 93 ++++++++++++++++++++++++++++++--- mach/proto/mcg/ir.c | 61 +++++++++++++++++++--- mach/proto/mcg/ir.dat | 6 ++- mach/proto/mcg/ir.h | 9 +++- mach/proto/mcg/main.c | 4 +- mach/proto/mcg/mcg.h | 5 +- mach/proto/mcg/parse_em.c | 27 ++++++---- mach/proto/mcg/sse.c | 99 ++++++++++++++++++++++++++++++++++++ mach/proto/mcg/treebuilder.c | 13 ----- 11 files changed, 296 insertions(+), 44 deletions(-) create mode 100644 mach/proto/mcg/sse.c diff --git a/mach/proto/mcg/array.c b/mach/proto/mcg/array.c index 1b72352b0..a375bafb5 100644 --- a/mach/proto/mcg/array.c +++ b/mach/proto/mcg/array.c @@ -35,5 +35,24 @@ void array_appendu(void*** array, int* count, int* max, void* value) array_append(array, count, max, value); } +void array_remove(void** array, int* count, void* value) +{ + int i; + + for (i=0; i<*count; i++) + { + if (array[i] == value) + { + while (i < (*count-1)) + { + array[i] = array[i+1]; + i++; + } + (*count)--; + return; + } + } +} + /* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/array.h b/mach/proto/mcg/array.h index 4d9badb29..d2f56123a 100644 --- a/mach/proto/mcg/array.h +++ b/mach/proto/mcg/array.h @@ -15,9 +15,13 @@ #define APPENDU(ARRAY, VALUE) \ array_appendu((void***) &ARRAY, &ARRAY##_count, &ARRAY##_max, VALUE) +#define REMOVE(ARRAY, VALUE) \ + array_remove((void**) ARRAY, &ARRAY##_count, VALUE) + extern void array_append(void*** array, int* count, int* max, void* value); extern bool array_contains(void** array, int count, void* value); extern void array_appendu(void*** array, int* count, int* max, void* value); +extern void array_remove(void** array, int* count, void* value); #endif diff --git a/mach/proto/mcg/compile.c b/mach/proto/mcg/compile.c index d8ae7e3ea..8d147a61a 100644 --- a/mach/proto/mcg/compile.c +++ b/mach/proto/mcg/compile.c @@ -10,31 +10,110 @@ static void print_blocks(char k, struct procedure* proc) struct basicblock* bb = proc->blocks[i]; int j; - tracef(k, "%c: block %s\n", k, bb->name); + tracef(k, "%c:\n", k); + tracef(k, "%c: BLOCK: %s\n", k, bb->name); + tracef(k, "%c: from:", k); for (int j=0; jinblocks_count; j++) { struct basicblock* obb = bb->inblocks[j]; - tracef(k, "%c: %s ->\n", k, obb->name); + tracef(k, " %s", obb->name); } - - for (int j=0; jirs_count; j++) - ir_print(k, bb->irs[j]); - + tracef(k, "\n"); + tracef(k, "%c: to:", k); for (int j=0; joutblocks_count; j++) { struct basicblock* obb = bb->outblocks[j]; - tracef(k, "%c: -> %s\n", k, obb->name); + tracef(k, " %s", obb->name); } + tracef(k, "\n"); + + for (int j=0; jirs_count; j++) + ir_print(k, bb->irs[j]); } } +static void remove_dead_blocks(struct procedure* proc) +{ + int i, j; + +again: + /* Starts at 1 because we don't want to remove the root block! */ + for (i=1; iblocks_count; i++) + { + struct basicblock* bb = proc->blocks[i]; + + if (bb->inblocks_count == 0) + { + /* Nobody uses this block; disconnect it from its output + * blocks. */ + for (j=0; joutblocks_count; j++) + REMOVE(bb->outblocks[j]->inblocks, bb); + + REMOVE(proc->blocks, bb); + goto again; + } + } +} + +static void splice_adjacent_blocks(struct procedure* proc) +{ + int i, j; + +again: + for (i=0; iblocks_count; i++) + { + struct basicblock* bb = proc->blocks[i]; + if (bb->outblocks_count == 1) + { + struct basicblock* outbb = bb->outblocks[0]; + if (outbb->inblocks_count == 1) + { + struct ir* lastir = bb->irs[bb->irs_count-1]; + + if ((lastir->opcode == IR_JUMP) + && (lastir->left->opcode == IR_BLOCK) + && (lastir->left->u.bvalue == outbb)) + { + /* Remove jump instruction. */ + + bb->irs_count--; + + REMOVE(bb->outblocks, outbb); + REMOVE(outbb->inblocks, bb); + + for (j=0; jirs_count; j++) + APPEND(bb->irs, outbb->irs[j]); + for (j=0; joutblocks_count; j++) + { + APPENDU(bb->outblocks, outbb->outblocks[j]); + APPENDU(outbb->outblocks[j]->inblocks, bb); + REMOVE(outbb->outblocks[j]->inblocks, outbb); + } + + REMOVE(proc->blocks, outbb); + goto again; + } + } + } + } +} + void compile(struct procedure* proc) { int i; print_blocks('1', proc); + + remove_dead_blocks(proc); + + for (i=0; iblocks_count; i++) + sse_convert_block_parameters(proc->blocks[i]); + + splice_adjacent_blocks(proc); + + print_blocks('2', proc); } /* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/ir.c b/mach/proto/mcg/ir.c index 34fed739a..c707a6bbc 100644 --- a/mach/proto/mcg/ir.c +++ b/mach/proto/mcg/ir.c @@ -66,15 +66,30 @@ struct ir* new_localir(int offset) return ir; } -void ir_print(char k, const struct ir* ir) +struct ir* ir_find(struct ir* ir, int opcode) { + if (ir->opcode == opcode) + return ir; + if (ir->left && !ir->left->is_sequence) - ir_print(k, ir->left); + { + struct ir* irr = ir_find(ir->left, opcode); + if (irr) + return irr; + } + if (ir->right && !ir->right->is_sequence) - ir_print(k, ir->right); + { + struct ir* irr = ir_find(ir->right, opcode); + if (irr) + return irr; + } - tracef(k, "%c: %c ", k, ir->is_sequence ? 'S' : ' '); - tracef(k, "$%d = ", ir->id); + return NULL; +} + +static void print_expr(char k, const struct ir* ir) +{ tracef(k, "%s", ir_names[ir->opcode]); if (ir->size) tracef(k, "%d", ir->size); @@ -95,14 +110,44 @@ void ir_print(char k, const struct ir* ir) tracef(k, "%s", ir->u.bvalue->name); break; + case IR_PHI: + { + int i; + + for (i=0; iu.phivalue.imports_count; i++) + { + if (i > 0) + tracef(k, ", "); + tracef(k, "$%d", ir->u.phivalue.imports[i]->id); + } + } + default: if (ir->left) - tracef(k, "$%d", ir->left->id); + { + if (ir->left->is_sequence) + tracef(k, "$%d", ir->left->id); + else + print_expr(k, ir->left); + } if (ir->right) - tracef(k, ", $%d", ir->right->id); + { + tracef(k, ", "); + if (ir->right->is_sequence) + tracef(k, "$%d", ir->right->id); + else + print_expr(k, ir->right); + } } - tracef(k, ")\n"); + tracef(k, ")"); +} + +void ir_print(char k, const struct ir* ir) +{ + tracef(k, "%c: $%d = ", k, ir->id); + print_expr(k, ir); + tracef(k, "\n"); } /* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/ir.dat b/mach/proto/mcg/ir.dat index 033897384..36787525c 100644 --- a/mach/proto/mcg/ir.dat +++ b/mach/proto/mcg/ir.dat @@ -6,10 +6,12 @@ BLOCK PAIR ANY LOCAL +PHI # Magic stack operations PUSH POP +SET # Memory operations LOAD @@ -54,8 +56,10 @@ IFEQ IFLT IFLE -# Flow control +# Procedures CALL + +# Flow control --- these never return JUMP CJUMP RET diff --git a/mach/proto/mcg/ir.h b/mach/proto/mcg/ir.h index 10e171bb2..0e8e2c422 100644 --- a/mach/proto/mcg/ir.h +++ b/mach/proto/mcg/ir.h @@ -24,11 +24,16 @@ struct ir int size; struct ir* left; struct ir* right; - union { + union + { arith ivalue; int rvalue; const char* lvalue; struct basicblock* bvalue; + struct + { + ARRAY(struct ir, imports); + } phivalue; } u; bool is_sequence : 1; }; @@ -48,6 +53,8 @@ extern struct ir* new_bbir(struct basicblock* bb); extern struct ir* new_anyir(int size); extern struct ir* new_localir(int offset); +extern struct ir* ir_find(struct ir* ir, int opcode); + extern void ir_print(char k, const struct ir* ir); #include "ircodes.h" diff --git a/mach/proto/mcg/main.c b/mach/proto/mcg/main.c index 61f0bd52e..d6cc586ec 100644 --- a/mach/proto/mcg/main.c +++ b/mach/proto/mcg/main.c @@ -37,8 +37,8 @@ bool tracing(char k) { switch (k) { - case 'E': return true; - case '0': return true; + case 'E': return false; + case '0': return false; case '1': return true; case '2': return true; default: return true; diff --git a/mach/proto/mcg/mcg.h b/mach/proto/mcg/mcg.h index 5de8be0c2..bcc6ff4b6 100644 --- a/mach/proto/mcg/mcg.h +++ b/mach/proto/mcg/mcg.h @@ -77,10 +77,11 @@ struct basicblock { const char* name; ARRAY(struct insn, insns); - ARRAY(struct ir, allirs); ARRAY(struct ir, irs); ARRAY(struct basicblock, inblocks); ARRAY(struct basicblock, outblocks); + ARRAY(struct ir, inparams); + ARRAY(struct ir, outparams); bool is_root : 1; bool is_terminated : 1; }; @@ -113,6 +114,8 @@ extern void tb_fileend(void); extern void tb_procedure(struct procedure* proc); extern void tb_regvar(arith offset, int size, int type, int priority); +extern void sse_convert_block_parameters(struct basicblock* bb); + extern void compile(struct procedure* proc); #endif diff --git a/mach/proto/mcg/parse_em.c b/mach/proto/mcg/parse_em.c index e6d39f9f5..162e53915 100644 --- a/mach/proto/mcg/parse_em.c +++ b/mach/proto/mcg/parse_em.c @@ -98,6 +98,7 @@ static void queue_insn_value(int opcode, arith value) { case op_csa: case op_csb: + case op_ret: terminate_block(); break; } @@ -138,6 +139,16 @@ static void queue_insn_block(int opcode, struct basicblock* left, struct basicbl terminate_block(); } +static void change_basicblock(struct basicblock* newbb) +{ + APPENDU(current_proc->blocks, newbb); + + if (code_bb && !code_bb->is_terminated) + queue_insn_block(op_bra, newbb, NULL); + + code_bb = newbb; +} + static void queue_insn_ilabel(int opcode, int label) { const char* name = ilabel_to_str(insn.em_ilb); @@ -155,8 +166,12 @@ static void queue_insn_ilabel(int opcode, int label) case op_zle: case op_zgt: case op_zge: - queue_insn_block(insn.em_opcode, left, bb_get(NULL)); + { + struct basicblock* bb = bb_get(NULL); + queue_insn_block(insn.em_opcode, left, bb); + change_basicblock(bb); break; + } default: fatal("parse_em: unhandled conditional '%s'", @@ -164,16 +179,6 @@ static void queue_insn_ilabel(int opcode, int label) } } -static void change_basicblock(struct basicblock* newbb) -{ - APPENDU(current_proc->blocks, newbb); - - if (code_bb && !code_bb->is_terminated) - queue_insn_block(op_bra, newbb, NULL); - - code_bb = newbb; -} - static void queue_ilabel(arith label) { change_basicblock(bb_get(ilabel_to_str(label))); diff --git a/mach/proto/mcg/sse.c b/mach/proto/mcg/sse.c new file mode 100644 index 000000000..3c57a3f8b --- /dev/null +++ b/mach/proto/mcg/sse.c @@ -0,0 +1,99 @@ +#include "mcg.h" + +static struct ir* get_last_push(struct basicblock* bb) +{ + int i; + + for (i=bb->irs_count-1; i>=0; i--) + { + struct ir* ir = bb->irs[i]; + + if (ir->opcode == IR_PUSH) + return ir; + if (ir_find(ir, IR_POP)) + return NULL; + } + + return NULL; +} + +static struct ir* get_first_pop(struct basicblock* bb) +{ + int i; + + for (i=0; iirs_count; i++) + { + struct ir* irr; + struct ir* ir = bb->irs[i]; + + if (ir->opcode == IR_PUSH) + return NULL; + + irr = ir_find(ir, IR_POP); + if (irr) + return irr; + } + + return NULL; +} + +void sse_convert_block_parameters(struct basicblock* bb) +{ + int i, j; + struct ir* ir; + + for (;;) + { + struct ir* lastpush = get_last_push(bb); + if (!lastpush) + return; + + /* Abort unless *every* success block of this one starts with a pop + * of the same size... */ + + for (i=0; ioutblocks_count; i++) + { + struct basicblock* outbb = bb->outblocks[i]; + + ir = get_first_pop(outbb); + if (!ir || (ir->size != lastpush->size)) + return; + + /* Also abort unless *every* predecessor block of the one we've + * just found *also* ends in a push of the same size. */ + + for (j=0; jinblocks_count; j++) + { + struct basicblock* inbb = outbb->inblocks[i]; + + ir = get_last_push(inbb); + if (!ir || (ir->size != lastpush->size)) + return; + } + } + + /* Okay, now we can wire them all up. */ + + for (i=0; ioutblocks_count; i++) + { + struct basicblock* outbb = bb->outblocks[i]; + struct ir* phi = get_first_pop(outbb); + phi->opcode = IR_PHI; + + /* Also abort unless *every* predecessor block of the one we've + * just found *also* ends in a push of the same size. */ + + for (j=0; jinblocks_count; j++) + { + struct basicblock* inbb = outbb->inblocks[j]; + + ir = get_last_push(inbb); + *ir = *ir->left; + ir->is_sequence = true; + APPEND(phi->u.phivalue.imports, ir); + } + } + } +} + +/* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/treebuilder.c b/mach/proto/mcg/treebuilder.c index 82d7b14ec..3928dc727 100644 --- a/mach/proto/mcg/treebuilder.c +++ b/mach/proto/mcg/treebuilder.c @@ -71,18 +71,6 @@ static void print_stack(void) tracef('E', " (top)\n"); } -static void appendallirs(struct ir* ir) -{ - if (CONTAINS(current_bb->allirs, ir)) - fatal("ir reachable from more than one place"); - - APPEND(current_bb->allirs, ir); - if (ir->left && !ir->left->is_sequence) - appendallirs(ir->left); - if (ir->right && !ir->right->is_sequence) - appendallirs(ir->right); -} - static struct ir* appendir(struct ir* ir) { int i; @@ -90,7 +78,6 @@ static struct ir* appendir(struct ir* ir) assert(current_bb != NULL); ir->is_sequence = true; APPEND(current_bb->irs, ir); - appendallirs(ir); ir_print('0', ir); return ir; -- 2.34.1