From 68f98cbad7e10d642bc7557276474c7987a9e98c Mon Sep 17 00:00:00 2001 From: David Given Date: Mon, 3 Oct 2016 20:52:36 +0200 Subject: [PATCH] Instruction selection now happens on a shadow tree, rather than on the IR tree itself. Currently it's semantically the same but the implementation is cleaner. --- mach/proto/mcg/ir.h | 3 - mach/proto/mcg/mcgg_generated_header.h | 17 +---- mach/proto/mcg/pass_instructionselection.c | 80 +++++++++++++--------- mach/proto/mcg/pass_ssa.c | 2 + mach/proto/mcg/table | 4 +- util/mcgg/ir.dat | 6 +- util/mcgg/mcgg.h | 31 ++++++--- 7 files changed, 78 insertions(+), 65 deletions(-) diff --git a/mach/proto/mcg/ir.h b/mach/proto/mcg/ir.h index ce90fcbde..52c5dc7d2 100644 --- a/mach/proto/mcg/ir.h +++ b/mach/proto/mcg/ir.h @@ -20,9 +20,6 @@ struct ir ARRAYOF(struct ir) phivalue; } u; - void* state_label; /* used by the iburg instruction selector */ - int insn_no; /* the table rule number for this instruction */ - int goal_no; /* the semantic type of this instruction; not stmt */ IMAPOF(struct hop) hops; /* only for root IRs; by goal */ }; diff --git a/mach/proto/mcg/mcgg_generated_header.h b/mach/proto/mcg/mcgg_generated_header.h index eead127f1..f190a9867 100644 --- a/mach/proto/mcg/mcgg_generated_header.h +++ b/mach/proto/mcg/mcgg_generated_header.h @@ -4,22 +4,7 @@ #define PANIC printf -#define OP_LABEL(p) burm_calculate_label(p) -#define LEFT_CHILD(p) ((p)->left) -#define RIGHT_CHILD(p) ((p)->right) - #define burm_assert(b, s) assert(b) -extern int burm_calculate_label(struct ir* ir); -extern void burm_panic_cannot_match(struct ir* ir); - -static bool burm_predicate_int(struct ir* ir) -{ - return ir->goal_no == 3; -} - -static bool burm_predicate_float(struct ir* ir) -{ - return ir->goal_no == 5; -} +extern void burm_panic_cannot_match(NODEPTR_TYPE node); diff --git a/mach/proto/mcg/pass_instructionselection.c b/mach/proto/mcg/pass_instructionselection.c index a1f80a855..5c92aae02 100644 --- a/mach/proto/mcg/pass_instructionselection.c +++ b/mach/proto/mcg/pass_instructionselection.c @@ -6,28 +6,21 @@ static struct ir* current_ir; static const struct burm_emitter_data emitter_data; -void burm_trace(struct ir* p, int ruleno, int cost, int bestcost) { +void burm_trace(struct burm_node* p, int ruleno, int cost, int bestcost) { const struct burm_instruction_data* insndata = &burm_instruction_data[ruleno]; //tracef('I', "I: 0x%p matched %s with cost %d vs. %d\n", p, // insndata->name, cost, bestcost); } -void burm_panic_cannot_match(struct ir* ir) +void burm_panic_cannot_match(struct burm_node* node) { fprintf(stderr, "could not find any patterns to match:\n"); - ir_print(0, ir); + ir_print(0, node->ir); fprintf(stderr, "aborting!\n"); exit(1); } -int burm_calculate_label(struct ir* ir) -{ - if (ir->root != current_ir) - return ir_to_esn(IR_REG, ir->size); - return ir_to_esn(ir->opcode, ir->size); -} - -static void emit_reg(struct ir* ir, int goal) +static void emit_reg(struct burm_node* node, int goal) { struct hop* hop = imap_get(¤t_ir->hops, goal); @@ -39,17 +32,17 @@ static void emit_string(const char* data) hop_add_string_insel(current_hop, data); } -static void emit_fragment(struct ir* ir, int goal) +static void emit_fragment(struct burm_node* node, int goal) { - int insn_no = burm_rule(ir->state_label, goal); + int insn_no = burm_rule(node->state_label, goal); const struct burm_instruction_data* insndata = &burm_instruction_data[insn_no]; if (insndata->emitter) - insndata->emitter(ir, &emitter_data); + insndata->emitter(node, &emitter_data); } -static void emit_value(struct ir* ir) +static void emit_value(struct burm_node* node) { - hop_add_value_insel(current_hop, ir); + hop_add_value_insel(current_hop, node->ir); } static void emit_eoi(void) @@ -57,15 +50,17 @@ static void emit_eoi(void) hop_add_eoi_insel(current_hop); } -static void emit_constraint_equals(struct ir* ir, int goal) +static void emit_constraint_equals(struct burm_node* node, int goal) { +#if 0 struct hop* hop; if (!goal) - goal = 2; + goal = ir->goal_no; hop = imap_get(¤t_ir->hops, goal); current_hop->output = hop->output; +#endif } static const struct burm_emitter_data emitter_data = @@ -79,13 +74,14 @@ static const struct burm_emitter_data emitter_data = }; -static void walk_instructions(struct ir* ir, int goal) +static void walk_instructions(struct burm_node* node, int goal) { - struct ir* children[10]; - int insn_no = burm_rule(ir->state_label, goal); + struct burm_node* children[10]; + int insn_no = burm_rule(node->state_label, goal); const struct burm_instruction_data* insndata = &burm_instruction_data[insn_no]; const short* nts = burm_nts[insn_no]; struct hop* parent_hop = NULL; + struct ir* ir = node->ir; int i; if (!insndata->is_fragment) @@ -99,17 +95,13 @@ static void walk_instructions(struct ir* ir, int goal) } } - burm_kids(ir, insn_no, children); + burm_kids(node, insn_no, children); for (i=0; nts[i]; i++) walk_instructions(children[i], nts[i]); - ir->insn_no = insn_no; - if (goal != 1) - ir->goal_no = goal; - tracef('I', "I: $%d goal %d selected %s %d: %s\n", ir->id, - ir->goal_no, + goal, insndata->is_fragment ? "fragment" : "instruction", insn_no, insndata->name); @@ -119,7 +111,7 @@ static void walk_instructions(struct ir* ir, int goal) /* This may cause the vregs to be reassigned for this instruction (and * fragments contained within it). */ - insndata->emitter(ir, &emitter_data); + insndata->emitter(node, &emitter_data); hop_print('I', current_hop); array_append(&ir->hops, current_hop); @@ -127,6 +119,27 @@ static void walk_instructions(struct ir* ir, int goal) } } +static struct burm_node* build_shadow_tree(struct ir* root, struct ir* ir) +{ + struct burm_node* node = calloc(1, sizeof(*node)); + node->ir = ir; + + if (ir->root == root) + { + node->label = ir_to_esn(ir->opcode, ir->size); + + if (ir->left) + node->left = build_shadow_tree(root, ir->left); + + if (ir->right) + node->right = build_shadow_tree(root, ir->right); + } + else + node->label = ir_to_esn(IR_REG, 0); + + return node; +} + static void select_instructions(void) { int i; @@ -135,16 +148,19 @@ static void select_instructions(void) for (i=0; iirs.count; i++) { + struct burm_node* shadow; int insnno; + current_ir = current_bb->irs.item[i]; - burm_label(current_ir); + shadow = build_shadow_tree(current_ir, current_ir); + burm_label(shadow); - insnno = burm_rule(current_ir->state_label, 1); + insnno = burm_rule(shadow->state_label, 1); if (!insnno) - burm_panic_cannot_match(current_ir); + burm_panic_cannot_match(shadow); ir_print('I', current_ir); - walk_instructions(current_ir, 1); + walk_instructions(shadow, 1); } } diff --git a/mach/proto/mcg/pass_ssa.c b/mach/proto/mcg/pass_ssa.c index 87a0b973e..265ade1f5 100644 --- a/mach/proto/mcg/pass_ssa.c +++ b/mach/proto/mcg/pass_ssa.c @@ -174,6 +174,7 @@ static bool rewrite_loads_cb(struct ir* ir, void* user) if (is_local(ir)) { ir->opcode = IR_NOP; + ir->size = 0; ir->left = definition; ir->right = NULL; } @@ -214,6 +215,7 @@ static void recursively_rewrite_tree(struct basicblock* bb) if (ir->opcode == IR_STORE) { ir->opcode = IR_NOP; + ir->size = 0; ir->left = ir->right; ir->right = NULL; } diff --git a/mach/proto/mcg/table b/mach/proto/mcg/table index 0db5f6a99..5f589d122 100644 --- a/mach/proto/mcg/table +++ b/mach/proto/mcg/table @@ -67,12 +67,12 @@ PATTERNS emit "add sp, sp, %delta" cost 4; - reg = in:REG4 + reg = in:REG with (reg == in) emit "reg %reg" cost 1; - reg = NOP4(in:reg) + reg = NOP(in:reg) with (reg == in) cost 1; diff --git a/util/mcgg/ir.dat b/util/mcgg/ir.dat index baa4617a6..50c2e44ed 100644 --- a/util/mcgg/ir.dat +++ b/util/mcgg/ir.dat @@ -5,14 +5,14 @@ # Simple terminals S CONST # must be followed by float form S CONSTF -S REG -S NOP +V REG +V NOP S LABEL S BLOCK V PAIR S ANY S LOCAL -S PHI +V PHI # Magic stack operations S PUSH diff --git a/util/mcgg/mcgg.h b/util/mcgg/mcgg.h index 1d806852b..9180113a7 100644 --- a/util/mcgg/mcgg.h +++ b/util/mcgg/mcgg.h @@ -13,27 +13,40 @@ (size-1))) #define STATE_TYPE void* -typedef struct ir* NODEPTR_TYPE; #define STATE_LABEL(p) ((p)->state_label) +#define OP_LABEL(p) ((p)->label) +#define LEFT_CHILD(p) ((p)->left) +#define RIGHT_CHILD(p) ((p)->right) -extern void* burm_label(struct ir* ir); +struct burm_node +{ + int label; + void* state_label; + struct burm_node* left; + struct burm_node* right; + struct ir* ir; +}; + +typedef struct burm_node* NODEPTR_TYPE; + +extern void* burm_label(NODEPTR_TYPE node); extern int burm_rule(void* state, int goalnt); extern const short *burm_nts[]; -extern struct ir** burm_kids(struct ir* p, int eruleno, struct ir* kids[]); -extern void burm_trace(struct ir* p, int ruleno, int cost, int bestcost); +extern NODEPTR_TYPE* burm_kids(NODEPTR_TYPE p, int eruleno, NODEPTR_TYPE kids[]); +extern void burm_trace(NODEPTR_TYPE p, int ruleno, int cost, int bestcost); struct burm_emitter_data { void (*emit_string)(const char* data); - void (*emit_fragment)(struct ir* ir, int goal); - void (*emit_reg)(struct ir* ir, int goal); - void (*emit_value)(struct ir* ir); + void (*emit_fragment)(NODEPTR_TYPE node, int goal); + void (*emit_reg)(NODEPTR_TYPE node, int goal); + void (*emit_value)(NODEPTR_TYPE node); void (*emit_eoi)(void); - void (*emit_constraint_equals)(struct ir* rightir, int rightgoal); + void (*emit_constraint_equals)(NODEPTR_TYPE node, int goal); }; -typedef void burm_emitter_t(struct ir* ir, const struct burm_emitter_data* data); +typedef void burm_emitter_t(NODEPTR_TYPE node, const struct burm_emitter_data* data); struct burm_instruction_data { -- 2.34.1