From ed67d427c9cceaa8c77d9fbc838651d8fee3aa59 Mon Sep 17 00:00:00 2001 From: David Given Date: Fri, 23 Sep 2016 23:59:15 +0200 Subject: [PATCH] Replaced the block splicer with a trivial block eliminator (which rewrites jumps to blocks which contain only a jump). Don't bother storing the bb graph in the ir nodes; we can find it on demand by walking the tree instead --- slower, but much easier to understand and more robust. Added a terrible map library. --- mach/proto/mcg/array.h | 5 + mach/proto/mcg/compile.c | 18 +--- mach/proto/mcg/ir.c | 33 +++---- mach/proto/mcg/ir.h | 12 +-- mach/proto/mcg/ircodes.sh | 2 +- mach/proto/mcg/main.c | 2 +- mach/proto/mcg/map.c | 58 ++++++++++++ mach/proto/mcg/map.h | 26 ++++++ mach/proto/mcg/mcg.h | 8 +- mach/proto/mcg/parse_em.c | 16 ++-- mach/proto/mcg/pass_convertstackops.c | 98 ++++++++++++++------ mach/proto/mcg/pass_deadblocks.c | 27 ------ mach/proto/mcg/pass_eliminatetrivialblocks.c | 41 ++++++++ mach/proto/mcg/pass_removedeadblocks.c | 40 ++++++++ mach/proto/mcg/pass_spliceadjacentblocks.c | 47 ---------- mach/proto/mcg/treebuilder.c | 14 +-- 16 files changed, 276 insertions(+), 171 deletions(-) create mode 100644 mach/proto/mcg/map.c create mode 100644 mach/proto/mcg/map.h delete mode 100644 mach/proto/mcg/pass_deadblocks.c create mode 100644 mach/proto/mcg/pass_eliminatetrivialblocks.c create mode 100644 mach/proto/mcg/pass_removedeadblocks.c delete mode 100644 mach/proto/mcg/pass_spliceadjacentblocks.c diff --git a/mach/proto/mcg/array.h b/mach/proto/mcg/array.h index d2f56123a..b3c9a03e5 100644 --- a/mach/proto/mcg/array.h +++ b/mach/proto/mcg/array.h @@ -6,6 +6,11 @@ int NAME##_count; \ int NAME##_max +#define STATICARRAY(TYPE, NAME) \ + static TYPE** NAME; \ + static int NAME##_count; \ + static int NAME##_max + #define APPEND(ARRAY, VALUE) \ array_append((void***) &ARRAY, &ARRAY##_count, &ARRAY##_max, VALUE) diff --git a/mach/proto/mcg/compile.c b/mach/proto/mcg/compile.c index e9fb86be2..c6fea43d6 100644 --- a/mach/proto/mcg/compile.c +++ b/mach/proto/mcg/compile.c @@ -13,24 +13,8 @@ static void print_blocks(char k, struct procedure* proc) 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, " %s", obb->name); - } - tracef(k, "\n"); - tracef(k, "%c: to:", k); - for (int j=0; joutblocks_count; j++) - { - struct basicblock* obb = bb->outblocks[j]; - tracef(k, " %s", obb->name); - } - tracef(k, "\n"); - for (int j=0; jirs_count; j++) ir_print(k, bb->irs[j]); - } } @@ -40,9 +24,9 @@ void compile(struct procedure* proc) print_blocks('1', proc); + pass_eliminate_trivial_blocks(proc); pass_remove_dead_blocks(proc); pass_convert_stack_ops(proc); - pass_splice_adjacent_blocks(proc); print_blocks('2', proc); } diff --git a/mach/proto/mcg/ir.c b/mach/proto/mcg/ir.c index c707a6bbc..f0c495f7e 100644 --- a/mach/proto/mcg/ir.c +++ b/mach/proto/mcg/ir.c @@ -66,21 +66,21 @@ struct ir* new_localir(int offset) return ir; } -struct ir* ir_find(struct ir* ir, int opcode) +struct ir* ir_walk(struct ir* ir, ir_walker_t* cb, void* user) { - if (ir->opcode == opcode) + if (cb(ir, user)) return ir; if (ir->left && !ir->left->is_sequence) { - struct ir* irr = ir_find(ir->left, opcode); + struct ir* irr = ir_walk(ir->left, cb, user); if (irr) return irr; } if (ir->right && !ir->right->is_sequence) { - struct ir* irr = ir_find(ir->right, opcode); + struct ir* irr = ir_walk(ir->right, cb, user); if (irr) return irr; } @@ -88,6 +88,19 @@ struct ir* ir_find(struct ir* ir, int opcode) return NULL; } +static bool finder_cb(struct ir* ir, void* user) +{ + int opcode = *(int*)user; + if (ir->opcode == opcode) + return true; + return false; +} + +struct ir* ir_find(struct ir* ir, int opcode) +{ + return ir_walk(ir, finder_cb, &opcode); +} + static void print_expr(char k, const struct ir* ir) { tracef(k, "%s", ir_names[ir->opcode]); @@ -110,18 +123,6 @@ static void print_expr(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) { diff --git a/mach/proto/mcg/ir.h b/mach/proto/mcg/ir.h index 0e8e2c422..795b6dd6d 100644 --- a/mach/proto/mcg/ir.h +++ b/mach/proto/mcg/ir.h @@ -1,6 +1,8 @@ #ifndef IR_H #define IR_H +#include "ircodes.h" + enum { IRR_LB = -1, @@ -20,7 +22,7 @@ enum struct ir { int id; - int opcode; + enum ir_opcode opcode; int size; struct ir* left; struct ir* right; @@ -30,10 +32,6 @@ struct ir int rvalue; const char* lvalue; struct basicblock* bvalue; - struct - { - ARRAY(struct ir, imports); - } phivalue; } u; bool is_sequence : 1; }; @@ -53,11 +51,11 @@ extern struct ir* new_bbir(struct basicblock* bb); extern struct ir* new_anyir(int size); extern struct ir* new_localir(int offset); +typedef bool ir_walker_t(struct ir* node, void* user); +extern struct ir* ir_walk(struct ir* ir, ir_walker_t* callback, void* user); extern struct ir* ir_find(struct ir* ir, int opcode); extern void ir_print(char k, const struct ir* ir); -#include "ircodes.h" - #endif diff --git a/mach/proto/mcg/ircodes.sh b/mach/proto/mcg/ircodes.sh index f1219c50e..3fdf1982d 100755 --- a/mach/proto/mcg/ircodes.sh +++ b/mach/proto/mcg/ircodes.sh @@ -6,7 +6,7 @@ source=$3 awk -f - $in >$header << "EOF" BEGIN { - print "enum {" + print "enum ir_opcode {" } /^[^#]+/ { diff --git a/mach/proto/mcg/main.c b/mach/proto/mcg/main.c index d6cc586ec..6c9a28006 100644 --- a/mach/proto/mcg/main.c +++ b/mach/proto/mcg/main.c @@ -39,7 +39,7 @@ bool tracing(char k) { case 'E': return false; case '0': return false; - case '1': return true; + case '1': return false; case '2': return true; default: return true; } diff --git a/mach/proto/mcg/map.c b/mach/proto/mcg/map.c new file mode 100644 index 000000000..228cf8bcc --- /dev/null +++ b/mach/proto/mcg/map.c @@ -0,0 +1,58 @@ +#include "mcg.h" + +static void extend(struct map_node** map, int* count, int* max) +{ + if (*count == *max) + { + int newmax = (*max == 0) ? 8 : (*max * 2); + struct map_node* newmap = realloc(*map, newmax * sizeof(struct map_node)); + if (!newmap) + fatal("memory allocation failure"); + + *max = newmax; + *map = newmap; + } +} + +void map_set(struct map_node** map, int* count, int* max, void* left, void* right) +{ + int i; + struct map_node* node; + + for (i=0; i<*count; i++) + { + node = &(*map)[i]; + if (node->left == left) + { + node->right = right; + return; + } + } + + extend(map, count, max); + node = &(*map)[*count]; + node->left = left; + node->right = right; + (*count)++; +} + +void map_add(struct map_node** map, int* count, int* max, void* left, void* right) +{ + int i; + struct map_node* node; + + for (i=0; i<*count; i++) + { + node = &(*map)[i]; + if ((node->left == left) && (node->right == right)) + return; + } + + extend(map, count, max); + node = &(*map)[*count]; + node->left = left; + node->right = right; + (*count)++; +} + +/* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/map.h b/mach/proto/mcg/map.h new file mode 100644 index 000000000..bf9d9e8e3 --- /dev/null +++ b/mach/proto/mcg/map.h @@ -0,0 +1,26 @@ +#ifndef MAP_H +#define MAP_H + +struct map_node +{ + void* left; + void* right; +}; + +#define _MAP(MODIFIER, NAME) \ + MODIFIER struct map_node* NAME; \ + MODIFIER int NAME##_count; \ + MODIFIER int NAME##_max + +#define MAP(NAME) _MAP(, NAME) +#define STATICMAP(NAME) _MAP(static, NAME) + +#define MAP_SET(MAP, LEFT, RIGHT) \ + map_set(&MAP, &MAP##_count, &MAP##_max, LEFT, RIGHT) + +extern void map_set(struct map_node** map, int* count, int* max, void* left, void* right); +extern void map_add(struct map_node** map, int* count, int* max, void* left, void* right); + +#endif + + diff --git a/mach/proto/mcg/mcg.h b/mach/proto/mcg/mcg.h index 1f66ef249..a7b8d6835 100644 --- a/mach/proto/mcg/mcg.h +++ b/mach/proto/mcg/mcg.h @@ -17,6 +17,7 @@ #include "em_flag.h" #include "em_ptyp.h" #include "array.h" +#include "map.h" #include "ir.h" extern char em_pseu[][4]; @@ -78,10 +79,7 @@ struct basicblock const char* name; ARRAY(struct insn, insns); ARRAY(struct ir, irs); - ARRAY(struct basicblock, inblocks); - ARRAY(struct basicblock, outblocks); - ARRAY(struct ir, inparams); - ARRAY(struct ir, outparams); + bool is_fake : 1; bool is_root : 1; bool is_terminated : 1; }; @@ -116,7 +114,7 @@ extern void tb_regvar(arith offset, int size, int type, int priority); extern void pass_convert_stack_ops(struct procedure* proc); extern void pass_remove_dead_blocks(struct procedure* proc); -extern void pass_splice_adjacent_blocks(struct procedure* proc); +extern void pass_eliminate_trivial_blocks(struct procedure* proc); extern void compile(struct procedure* proc); diff --git a/mach/proto/mcg/parse_em.c b/mach/proto/mcg/parse_em.c index 162e53915..7daecfecd 100644 --- a/mach/proto/mcg/parse_em.c +++ b/mach/proto/mcg/parse_em.c @@ -128,14 +128,6 @@ static void queue_insn_block(int opcode, struct basicblock* left, struct basicbl insn->u.bvalue.right = right; APPEND(code_bb->insns, insn); - APPENDU(code_bb->outblocks, left); - APPENDU(left->inblocks, code_bb); - if (right) - { - APPENDU(code_bb->outblocks, right); - APPENDU(right->inblocks, code_bb); - } - terminate_block(); } @@ -256,7 +248,12 @@ static void parse_pseu(void) */ if (data_bb) - APPENDU(data_bb->outblocks, bb_get(label)); + { + struct insn* insn = new_insn(op_bra); + insn->paramtype = PARAM_BVALUE; + insn->u.bvalue.left = bb_get(label); + APPEND(data_bb->insns, insn); + } data_offset(label, 0, ro); break; @@ -361,6 +358,7 @@ void parse_em(void) const char* label = dlabel_to_str(insn.em_dlb); data_label(label); data_bb = bb_get(label); + data_bb->is_fake = true; break; } diff --git a/mach/proto/mcg/pass_convertstackops.c b/mach/proto/mcg/pass_convertstackops.c index 6ee90bda9..77cdf39d9 100644 --- a/mach/proto/mcg/pass_convertstackops.c +++ b/mach/proto/mcg/pass_convertstackops.c @@ -1,5 +1,9 @@ #include "mcg.h" +STATICMAP(graph); +STATICARRAY(struct ir, pops); +STATICARRAY(struct ir, pushes); + static struct ir* get_last_push(struct basicblock* bb) { int i; @@ -37,61 +41,93 @@ static struct ir* get_first_pop(struct basicblock* bb) return NULL; } -static void convert_block(struct basicblock* bb) +static bool collect_outputs_cb(struct ir* ir, void* user) +{ + struct basicblock* caller = user; + + if (ir->opcode == IR_BLOCK) + MAP_SET(graph, caller, ir->u.bvalue); + return false; +} + +static void make_bb_graph(struct procedure* proc) +{ + int i, j; + + graph_count = 0; + for (i=0; iblocks_count; i++) + { + struct basicblock* bb = proc->blocks[i]; + for (j=0; jirs_count; j++) + ir_walk(bb->irs[j], collect_outputs_cb, bb); + } +} + +static void convert_block(struct procedure* proc, struct basicblock* bb) { int i, j; struct ir* ir; + pushes_count = pops_count = 0; for (;;) { struct ir* lastpush = get_last_push(bb); if (!lastpush) return; - /* Abort unless *every* success block of this one starts with a pop + /* Abort unless *every* successor block of this one starts with a pop * of the same size... */ - for (i=0; ioutblocks_count; i++) + for (i=0; ioutblocks[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++) + if (graph[i].left == bb) { - struct basicblock* inbb = outbb->inblocks[i]; + struct basicblock* outbb = graph[i].right; - ir = get_last_push(inbb); + ir = get_first_pop(outbb); if (!ir || (ir->size != lastpush->size)) return; + APPENDU(pops, ir); + + /* 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; jsize != lastpush->size)) + return; + APPENDU(pushes, ir); + } + } } } /* Okay, now we can wire them all up. */ - for (i=0; ioutblocks_count; i++) + for (i=0; ioutblocks[i]; - struct ir* phi = get_first_pop(outbb); - phi->opcode = IR_PHI; + struct ir* ir = pushes[i]; + assert(ir->is_sequence); + *ir = *ir->left; + ir->is_sequence = true; + } - /* Also abort unless *every* predecessor block of the one we've - * just found *also* ends in a push of the same size. */ + for (i=0; isize, pushir); - for (j=0; jinblocks_count; j++) - { - struct basicblock* inbb = outbb->inblocks[j]; + for (j=1; jsize, phi, pushes[j]); - ir = get_last_push(inbb); - *ir = *ir->left; - ir->is_sequence = true; - APPEND(phi->u.phivalue.imports, ir); - } + phi->is_sequence = ir->is_sequence; + *ir = *phi; } } } @@ -100,8 +136,10 @@ void pass_convert_stack_ops(struct procedure* proc) { int i; + make_bb_graph(proc); + for (i=0; iblocks_count; i++) - convert_block(proc->blocks[i]); + convert_block(proc, proc->blocks[i]); } /* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/pass_deadblocks.c b/mach/proto/mcg/pass_deadblocks.c deleted file mode 100644 index 94c8735cc..000000000 --- a/mach/proto/mcg/pass_deadblocks.c +++ /dev/null @@ -1,27 +0,0 @@ -#include "mcg.h" - -void pass_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; - } - } -} - -/* vim: set sw=4 ts=4 expandtab : */ - diff --git a/mach/proto/mcg/pass_eliminatetrivialblocks.c b/mach/proto/mcg/pass_eliminatetrivialblocks.c new file mode 100644 index 000000000..96c8e080d --- /dev/null +++ b/mach/proto/mcg/pass_eliminatetrivialblocks.c @@ -0,0 +1,41 @@ +#include "mcg.h" + +static bool rewrite_jumps_cb(struct ir* ir, void* user) +{ + if (ir->opcode == IR_BLOCK) + { + struct basicblock* bb = ir->u.bvalue; + if ((bb->irs_count > 0) + && (bb->irs[0]->opcode == IR_JUMP) + && (bb->irs[0]->left->opcode == IR_BLOCK)) + { + ir->u.bvalue = bb->irs[0]->left->u.bvalue; + } + } + + return false; +} + +static void rewrite_jumps(struct basicblock* bb) +{ + int i; + + for (i=0; iirs_count; i++) + { + struct ir* ir = bb->irs[i]; + ir_walk(ir, rewrite_jumps_cb, NULL); + } +} + +void pass_eliminate_trivial_blocks(struct procedure* proc) +{ + int i; + + for (i=0; iblocks_count; i++) + { + struct basicblock* bb = proc->blocks[i]; + rewrite_jumps(bb); + } +} + +/* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/pass_removedeadblocks.c b/mach/proto/mcg/pass_removedeadblocks.c new file mode 100644 index 000000000..af2d54d70 --- /dev/null +++ b/mach/proto/mcg/pass_removedeadblocks.c @@ -0,0 +1,40 @@ +#include "mcg.h" + +STATICARRAY(struct basicblock, used); + +static void walk_blocks(struct basicblock* bb); + +static bool walk_blocks_cb(struct ir* ir, void* user) +{ + if (ir->opcode == IR_BLOCK) + walk_blocks(ir->u.bvalue); + return false; +} + +static void walk_blocks(struct basicblock* bb) +{ + int i; + + if (!CONTAINS(used, bb)) + { + APPENDU(used, bb); + + for (i=0; iirs_count; i++) + ir_walk(bb->irs[i], walk_blocks_cb, NULL); + } +} + +void pass_remove_dead_blocks(struct procedure* proc) +{ + int i, j; + + used_count = 0; + walk_blocks(proc->blocks[0]); + + proc->blocks_count = 0; + for (i=0; iblocks, used[i]); +} + +/* vim: set sw=4 ts=4 expandtab : */ + diff --git a/mach/proto/mcg/pass_spliceadjacentblocks.c b/mach/proto/mcg/pass_spliceadjacentblocks.c deleted file mode 100644 index 7f6a69b98..000000000 --- a/mach/proto/mcg/pass_spliceadjacentblocks.c +++ /dev/null @@ -1,47 +0,0 @@ -#include "mcg.h" - -void pass_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; - } - } - } - } -} - -/* vim: set sw=4 ts=4 expandtab : */ - diff --git a/mach/proto/mcg/treebuilder.c b/mach/proto/mcg/treebuilder.c index 3928dc727..39d529f3d 100644 --- a/mach/proto/mcg/treebuilder.c +++ b/mach/proto/mcg/treebuilder.c @@ -531,8 +531,6 @@ static void insn_ivalue(int opcode, arith value) case op_csa: case op_csb: { - struct basicblock* data_bb; - int i; const char* helper = aprintf(".%s%d", (opcode == op_csa) ? "csa" : "csb", value); @@ -542,16 +540,10 @@ static void insn_ivalue(int opcode, arith value) fatal("csa/csb are only supported if they refer " "directly to a descriptor block"); - /* Splice the outgoing bbs in the data block into our own. */ + /* Turn the label reference into a block. */ - data_bb = bb_get(descriptor->u.lvalue); - for (i=0; ioutblocks_count; i++) - { - struct basicblock* bb = data_bb->outblocks[i]; - printf("\t; may jump to %s\n", bb->name); - APPENDU(current_bb->outblocks, bb); - APPENDU(bb->inblocks, current_bb); - } + descriptor->opcode = IR_BLOCK; + descriptor->u.bvalue = bb_get(descriptor->u.lvalue); push(descriptor); materialise_stack(); -- 2.34.1