From 88fb231d6e9c227a2a98fb54ec5ad021281498ff Mon Sep 17 00:00:00 2001 From: David Given Date: Wed, 5 Oct 2016 22:56:25 +0200 Subject: [PATCH] Better constraint syntax; mcgg now passes register usage information up to mcg; mcg can track individual hop inputs and outputs (needed for live range analysis!); the register allocator now puts the basic blocks into the right order in preparation for live range analysis. --- mach/proto/mcg/hop.c | 11 +- mach/proto/mcg/hop.h | 3 + mach/proto/mcg/mcg.h | 2 + mach/proto/mcg/pass_instructionselection.c | 31 ++++- mach/proto/mcg/procedure.c | 3 +- mach/proto/mcg/registerallocator.c | 32 +++++ mach/proto/mcg/table | 144 ++++++++------------- util/mcgg/gram.y | 19 +-- util/mcgg/iburg.c | 105 +++++++++++++-- util/mcgg/iburg.h | 9 +- util/mcgg/mcgg.h | 8 +- 11 files changed, 240 insertions(+), 127 deletions(-) diff --git a/mach/proto/mcg/hop.c b/mach/proto/mcg/hop.c index a11b99792..352ad9b2b 100644 --- a/mach/proto/mcg/hop.c +++ b/mach/proto/mcg/hop.c @@ -50,7 +50,7 @@ void hop_add_eoi_insel(struct hop* hop) void hop_print(char k, struct hop* hop) { - int i; + int i, j; bool soi = true; i = 0; @@ -60,7 +60,14 @@ void hop_print(char k, struct hop* hop) if (soi) { - tracef(k, "%c: %d from $%d: ", k, hop->id, hop->ir->id); + tracef(k, "%c: %d from $%d:", k, hop->id, hop->ir->id); + + for (j=0; jins.count; j++) + tracef(k, " <%%%d", hop->ins.item[j]->id); + for (j=0; jouts.count; j++) + tracef(k, " >%%%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 d802ed01a..66903cbfe 100644 --- a/mach/proto/mcg/hop.h +++ b/mach/proto/mcg/hop.h @@ -28,6 +28,9 @@ struct hop struct ir* ir; ARRAYOF(struct insel) insels; struct vreg* output; + + ARRAYOF(struct vreg) ins; + ARRAYOF(struct vreg) outs; PMAPOF(struct vreg, struct hreg) registers; }; diff --git a/mach/proto/mcg/mcg.h b/mach/proto/mcg/mcg.h index 07da36467..601249f07 100644 --- a/mach/proto/mcg/mcg.h +++ b/mach/proto/mcg/mcg.h @@ -109,6 +109,8 @@ extern void pass_promote_float_ops(struct procedure* proc); extern void pass_remove_dead_blocks(struct procedure* proc); extern void pass_split_critical_edges(struct procedure* proc); +extern void register_allocator(struct procedure* proc); + #endif /* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/pass_instructionselection.c b/mach/proto/mcg/pass_instructionselection.c index 5f965c9bc..ca7589e86 100644 --- a/mach/proto/mcg/pass_instructionselection.c +++ b/mach/proto/mcg/pass_instructionselection.c @@ -37,15 +37,19 @@ static void emit_return_reg(void) hop_add_vreg_insel(current_hop, current_hop->output); } -static void emit_reg(int child) +static struct vreg* find_vreg_of_child(int child) { struct insn* insn = current_insn->children[child]; - struct vreg* vreg; if (insn->hop) - vreg = insn->hop->output; + return insn->hop->output; else - vreg = insn->ir->result; + return insn->ir->result; +} + +static void emit_reg(int child) +{ + struct vreg* vreg = find_vreg_of_child(child); if (vreg) hop_add_vreg_insel(current_hop, vreg); @@ -71,6 +75,18 @@ static void emit_eoi(void) hop_add_eoi_insel(current_hop); } +static void constrain_input_reg(int child, int attr) +{ + struct vreg* vreg = find_vreg_of_child(child); + + if (vreg) + array_appendu(¤t_hop->ins, vreg); +} + +static void constrain_output_reg(int attr) +{ +} + static const struct burm_emitter_data emitter_data = { &emit_string, @@ -79,6 +95,8 @@ static const struct burm_emitter_data emitter_data = &emit_reg, &emit_value, &emit_eoi, + &constrain_input_reg, + &constrain_output_reg }; static void emit(struct insn* insn) @@ -142,11 +160,16 @@ static struct insn* walk_instructions(struct burm_node* node, int goal) break; default: + /* FIXME: some instructions don't emit anything, so + * allocating a register for them is a waste of time. */ vreg = new_vreg(); } insn->hop = current_hop = new_hop(0, insn->ir); insn->hop->output = vreg; + if (vreg) + array_appendu(¤t_hop->outs, vreg); + emit(insn); hop_print('I', current_hop); diff --git a/mach/proto/mcg/procedure.c b/mach/proto/mcg/procedure.c index 8fbccd5d6..8d0f83953 100644 --- a/mach/proto/mcg/procedure.c +++ b/mach/proto/mcg/procedure.c @@ -61,8 +61,9 @@ void procedure_compile(struct procedure* proc) pass_promote_float_ops(proc); print_blocks('6', proc); - pass_instruction_selector(proc); + + register_allocator(proc); } static bool collect_outputs_cb(struct ir* ir, void* user) diff --git a/mach/proto/mcg/registerallocator.c b/mach/proto/mcg/registerallocator.c index 84db0ea7d..eae72fac6 100644 --- a/mach/proto/mcg/registerallocator.c +++ b/mach/proto/mcg/registerallocator.c @@ -1,2 +1,34 @@ +#include "mcg.h" + +static ARRAYOF(struct basicblock) blocks; + +static void recursively_walk_blocks(struct basicblock* bb) +{ + int i; + + if (array_appendu(&blocks, bb)) + return; + tracef('R', "R: considering block %s\n", bb->name); + + for (i=0; inexts.count; i++) + recursively_walk_blocks(bb->nexts.item[i]); +} + +static void order_blocks(struct procedure* proc) +{ + /* Put them into preorder; this ensures that when we do the allocation, + * we do all of a block's predecessors before the block (except for + * backward edges). */ + + blocks.count = 0; + recursively_walk_blocks(proc->blocks.item[0]); + assert(blocks.count == proc->blocks.count); +} + +void register_allocator(struct procedure* proc) +{ + order_blocks(proc); +} + /* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/table b/mach/proto/mcg/table index 8ab4a4d51..f3f359f4b 100644 --- a/mach/proto/mcg/table +++ b/mach/proto/mcg/table @@ -29,7 +29,6 @@ REGISTERS DECLARATIONS - reg; cc; address fragment; @@ -40,28 +39,24 @@ PATTERNS /* Special */ - reg; - PAIR(BLOCK4, BLOCK4); /* Miscellaneous special things */ - PUSH4(in:reg) + PUSH4(in:(int)reg) emit "push %in" cost 4; - reg = POP4 - with int reg - emit "pop %reg" + out:(int)reg = POP4 + emit "pop %out" cost 4; RET emit "ret" cost 4; - SETRET4(in:reg) - with ret reg + SETRET4(in:(ret)reg) emit "mov r0, %in" cost 4; @@ -69,51 +64,38 @@ PATTERNS emit "add sp, sp, %delta" cost 4; - reg = in:REG - cost 1; - - reg = NOP(in:reg) - cost 1; - /* Memory operations */ - STORE4(addr:address, value:reg) - with int value + STORE4(addr:address, value:(int)reg) emit "str %value, %addr" cost 4; - STORE1(addr:address, value:reg) - with int value + STORE1(addr:address, value:(int)reg) emit "strb %value, %addr" cost 4; - reg = LOAD4(addr:address) - with int reg - emit "ldr %reg, %addr" + out:(int)reg = LOAD4(addr:address) + emit "ldr %out, %addr" cost 4; - reg = LOAD1(addr:address) - with int reg - emit "ldrb %reg, %addr" + out:(int)reg = LOAD1(addr:address) + emit "ldrb %out, %addr" cost 4; - reg = CIU14(LOAD1(addr:address)) - with int reg - emit "ldrb %reg, %addr" + out:(int)reg = CIU14(LOAD1(addr:address)) + emit "ldrb %out, %addr" cost 4; - reg = CII14(CIU41(CIU14(LOAD1(addr:address)))) - with int reg - emit "ldrsb %reg, %addr" + out:(int)reg = CII14(CIU41(CIU14(LOAD1(addr:address)))) + emit "ldrsb %out, %addr" cost 4; /* Locals */ - reg = in:LOCAL4 - with int reg - emit "add %reg, fp, #$in" + out:(int)reg = in:LOCAL4 + emit "add %out, fp, #$in" cost 4; address = in:LOCAL4 @@ -122,16 +104,13 @@ PATTERNS /* Memory addressing modes */ - address = ADD4(addr:reg, offset:CONST4) - with int addr + address = ADD4(addr:(int)reg, offset:CONST4) emit "[%addr, #$offset]"; - address = ADD4(addr1:reg, addr2:reg) - with int addr1, int addr2 + address = ADD4(addr1:(int)reg, addr2:(int)reg) emit "[%addr1, %addr2]"; - address = addr:reg - with int addr + address = addr:(int)reg emit "[%addr]"; @@ -142,17 +121,17 @@ PATTERNS emit "b $addr" cost 4; - CJUMPEQ(value:cc, PAIR(true:BLOCK4, false:BLOCK4)) + CJUMPEQ(value:(cc)cc, PAIR(true:BLOCK4, false:BLOCK4)) emit "beq $true" emit "b $false" cost 8; - CJUMPLE(value:cc, PAIR(true:BLOCK4, false:BLOCK4)) + CJUMPLE(value:(cc)cc, PAIR(true:BLOCK4, false:BLOCK4)) emit "ble $true" emit "b $false" cost 8; - CJUMPLT(value:cc, PAIR(true:BLOCK4, false:BLOCK4)) + CJUMPLT(value:(cc)cc, PAIR(true:BLOCK4, false:BLOCK4)) emit "blt $true" emit "b $false" cost 8; @@ -164,96 +143,81 @@ PATTERNS /* Comparisons */ - cc = COMPARES4(left:reg, right:aluparam) - with cc cc + (cc)cc = COMPARES4(left:(int)reg, right:aluparam) emit "cmp %left, %right" cost 4; - cc = COMPARES4(COMPARES4(left:reg, right:aluparam), CONST4) - with cc cc + (cc)cc = COMPARES4(COMPARES4(left:(int)reg, right:aluparam), CONST4) emit "cmp %left, %right" cost 4; - reg = cc - with int reg - emit "mov %reg, #0" - emit "movlt %reg, #-1" - emit "movgt %reg, #1" + out:(int)reg = (cc)cc + emit "mov %out, #0" + emit "movlt %out, #-1" + emit "movgt %out, #1" cost 12; /* Conversions */ - reg = CII14(CIU41(value:reg)) - with int reg - emit "sxtb %reg, %value" + out:(int)reg = CII14(CIU41(value:(int)reg)) + emit "sxtb %out, %value" cost 4; - reg = CIU41(in:reg) - with int reg - emit "and %reg, %in, #0xff" + out:(int)reg = CIU41(in:(int)reg) + emit "and %out, %in, #0xff" cost 4; /* ALU operations */ - reg = ADD4(left:reg, right:aluparam) - with int reg - emit "add %reg, %left, %right" + out:(int)reg = ADD4(left:(int)reg, right:aluparam) + emit "add %out, %left, %right" cost 4; - reg = ADD4(left:aluparam, right:reg) - with int reg - emit "add %reg, %right, %left" + out:(int)reg = ADD4(left:aluparam, right:(int)reg) + emit "add %out, %right, %left" cost 4; - reg = MOD4(left:reg, right:reg) - with int reg - emit "udiv %reg, %left, %right" - emit "mls %reg, %reg, %right, %left" + out:(int)reg = MOD4(left:(int)reg, right:(int)reg) + emit "udiv %out, %left, %right" + emit "mls %out, %out, %right, %left" cost 8; - reg = DIV4(left:reg, right:aluparam) - with int reg - emit "div %reg, %left, %right" + out:(int)reg = DIV4(left:(int)reg, right:aluparam) + emit "div %out, %left, %right" cost 4; aluparam = value:CONST4 emit "#$value"; - aluparam = value:reg + aluparam = value:(int)reg emit "%value"; - reg = value:aluparam - with int reg - emit "mov %reg, %value" + out:(int)reg = value:aluparam + emit "mov %out, %value" cost 4; - reg = value:LABEL4 - with int reg - emit "adr %reg, $value" + out:(int)reg = value:LABEL4 + emit "adr %out, $value" cost 4; - reg = value:BLOCK4 - with int reg - emit "adr %reg, $value" + out:(int)reg = value:BLOCK4 + emit "adr %out, $value" cost 4; - reg = value:CONST4 - with int reg - emit "ldr %reg, address-containing-$value" + out:(int)reg = value:CONST4 + emit "ldr %out, address-containing-$value" cost 8; - reg = value:CONSTF4 - with int reg - emit "vldr %reg, address-containing-$value" + out:(int)reg = value:CONSTF4 + emit "vldr %out, address-containing-$value" cost 8; /* FPU operations */ - reg = ADDF4(left:reg, right:reg) - with int reg - emit "fadds %reg, %left, %right" + out:(float)reg = ADDF4(left:(float)reg, right:(float)reg) + emit "fadds %out, %left, %right" cost 4; /* vim: set sw=4 ts=4 expandtab : */ diff --git a/util/mcgg/gram.y b/util/mcgg/gram.y index a7ba08d70..fbd191052 100644 --- a/util/mcgg/gram.y +++ b/util/mcgg/gram.y @@ -11,8 +11,6 @@ extern int yylex(void); -static int nextern = 1; - %} %union { int n; @@ -86,17 +84,6 @@ declarations declaration : ID { $$ = nonterm($1, true); } | declaration FRAGMENT { $$ = $1; $$->is_fragment = true; } - | allocates { $$ = $1; } - ; - -allocates - : declaration ALLOCATES '(' ID ')' - { - $$ = $1; - if ($$->allocate) - yyerror("pattern type is defined to already allocate a register"); - $$->allocate = getregattr($4); - } ; patterns @@ -106,8 +93,8 @@ patterns ; pattern - : ID '=' rhs { nonterm($1, false); $$ = rule($1, $3, nextern++); } - | rhs { $$ = rule("stmt", $1, nextern++); } + : terminfo '=' rhs { nonterm($1.name, false); $$ = rule(&$1, $3); } + | rhs { $$ = rule(NULL, $1); } | pattern PREFERS predicate { $$ = $1; array_append(&$$->prefers, $3); } | pattern WHEN predicate { $$ = $1; array_append(&$$->requires, $3); } | pattern COST INT { $$ = $1; $$->cost = $3; } @@ -123,7 +110,9 @@ rhs terminfo : ID { $$.name = $1; } + | '(' ID ')' ID { $$.attr = $2; $$.name = $4; } | ID ':' ID { $$.label = $1; $$.name = $3; } + | ID ':' '(' ID ')' ID { $$.label = $1; $$.attr = $4; $$.name = $6; } ; pattern_emit diff --git a/util/mcgg/iburg.c b/util/mcgg/iburg.c index b9ecd2cd2..5683b6cc4 100644 --- a/util/mcgg/iburg.c +++ b/util/mcgg/iburg.c @@ -14,6 +14,7 @@ #include "ircodes.h" #include "astring.h" #include "smap.h" +#include "mcgg.h" static char rcsid[] = "$Id$"; @@ -131,6 +132,20 @@ int main(int argc, char* argv[]) makeregattr("bytes4"); makeregattr("bytes8"); + /* Define some standard terms. */ + + { + const static struct terminfo reg = { "reg", NULL, "" }; + const static struct terminfo REG = { "REG", NULL, NULL }; + const static struct terminfo NOP = { "NOP", NULL, NULL }; + + nonterm("reg", true); + + rule(NULL, tree(®, NULL, NULL))->cost = 1; + rule(®, tree(®, NULL, NULL))->cost = 1; + rule(®, tree(&NOP, tree(®, NULL, NULL), NULL))->cost = 1; + } + yyin = infp; yyparse(); @@ -336,7 +351,7 @@ Term term(const char* id, int esn) } /* tree - create & initialize a tree node with the given fields */ -Tree tree(struct terminfo* ti, Tree left, Tree right) +Tree tree(const struct terminfo* ti, Tree left, Tree right) { Tree t = calloc(1, sizeof *t); Term p = lookup(ti->name); @@ -363,31 +378,57 @@ Tree tree(struct terminfo* ti, Tree left, Tree right) if (p->kind == TERM && arity != p->arity) yyerror("inconsistent arity for terminal `%s'\n", ti->name); t->op = p; - t->label = ti->label; t->nterms = p->kind == TERM; if (t->left = left) t->nterms += left->nterms; if (t->right = right) t->nterms += right->nterms; + + /* Special rules that have no output register attribute use "" as the + * attribute name; these can't be made by the grammar. */ + + t->label = ti->label; + if ((p->kind == TERM) && (ti->attr)) + yyerror("can't specify an input register attribute for terminal '%s'", ti->name); + if (p->kind == NONTERM) + { + Nonterm nt = (Nonterm)p; + if (nt->is_fragment && ti->attr) + yyerror("can't specify an input register attribute for fragment '%s'", ti->name); + if (!nt->is_fragment && !ti->attr) + yyerror("must specify an input register attribute for non-fragment '%s'", ti->name); + + if (ti->attr && ti->attr[0]) + { + nt->attr = smap_get(®isterattrs, ti->attr); + if (!nt->attr) + yyerror("'%s' doesn't seem to be a known register attribute", ti->attr); + } + } return t; } /* rule - create & initialize a rule with the given fields */ -Rule rule(char* id, Tree pattern, int ern) +Rule rule(const struct terminfo* ti, Tree pattern) { + static int number = 1; + static const struct terminfo stmt = { "stmt", NULL, NULL }; Rule r = calloc(1, sizeof *r); Rule *q; Term p = pattern->op; + if (!ti) + ti = &stmt; + nrules++; r->lineno = yylineno; - r->lhs = nonterm(id, false); + r->lhs = nonterm(ti->name, false); r->packed = ++r->lhs->lhscount; for (q = &r->lhs->rules; *q; q = &(*q)->decode) ; *q = r; r->pattern = pattern; - r->ern = ern; + r->ern = number++; if (p->kind == TERM) { r->next = p->rules; @@ -405,6 +446,23 @@ Rule rule(char* id, Tree pattern, int ern) yyerror("duplicate external rule number `%d'\n", r->ern); r->link = *q; *q = r; + + r->label = ti->label; + if (r->lhs->is_fragment && ti->attr) + yyerror("can't specify an output register attribute for a fragment"); + if (!r->lhs->is_fragment && !ti->attr && (r->lhs->number != NONTERM_STMT)) + yyerror("must specify an output register attribute for non-fragments"); + + /* Special rules that have no output register attribute use "" as the + * attribute name; these can't be made by the grammar. */ + + if (ti->attr && ti->attr[0]) + { + r->attr = smap_get(®isterattrs, ti->attr); + if (!r->attr) + yyerror("'%s' doesn't seem to be a known register attribute", ti->attr); + } + return r; } @@ -986,6 +1044,28 @@ static void emitpredicatedefinitions(Rule r) } } +static void emit_input_regs(Tree node, int* index) +{ + /* This must return the same ordering as the burm_kids() function uses. */ + + Nonterm nt = node->op; + if ((nt->kind == NONTERM) && !nt->is_fragment && !node->left && !node->right) + { + uint32_t attr = 0; + if (nt->attr->number) + attr = 1<attr->number; + print("%1data->constrain_input_reg(%d, 0x%x);\n", *index, attr); + } + + if (!node->left && !node->right) + (*index)++; + + if (node->left) + emit_input_regs(node->left, index); + if (node->right) + emit_input_regs(node->right, index); +} + /* emitinsndata - emit the code generation data */ static void emitinsndata(Rule rules) { @@ -1011,6 +1091,14 @@ static void emitinsndata(Rule rules) print("/* %R */\n", r); print("static void %Pemitter_%d(const struct %Pemitter_data* data) {\n", r->ern); + if (r->attr) + print("%1data->constrain_output_reg(0x%x);\n", 1<attr->number); + + { + int index = 0; + emit_input_regs(r->pattern, &index); + } + while (f) { switch (f->data[0]) @@ -1019,7 +1107,7 @@ static void emitinsndata(Rule rules) { const char* label = f->data + 1; - if (strcmp(label, r->lhs->name) == 0) + if (r->label && (strcmp(label, r->label) == 0)) print("%1data->emit_return_reg();\n", label); else { @@ -1086,11 +1174,6 @@ static void emitinsndata(Rule rules) print("%2&%Pemitter_%d,\n", r->ern); - if (r->lhs->allocate) - print("%2%d,\n", r->lhs->allocate->number); - else - print("%20,\n"); - print("%2%s,\n", r->lhs->is_fragment ? "true" : "false"); print("%1},\n"); diff --git a/util/mcgg/iburg.h b/util/mcgg/iburg.h index 60e51d7b4..48981722b 100644 --- a/util/mcgg/iburg.h +++ b/util/mcgg/iburg.h @@ -41,6 +41,7 @@ struct terminfo { const char* name; const char* label; + const char* attr; }; struct reg @@ -82,7 +83,7 @@ struct nonterm Rule chain; /* chain rules w/non-terminal on rhs */ Nonterm link; /* next terminal in number order */ bool is_fragment; /* these instructions are all fragments */ - struct regattr* allocate; /* allocate this kind of register */ + struct regattr* attr; /* input register attribute */ }; extern void* lookup(const char* name); extern Nonterm nonterm(const char* id, bool allocate); @@ -96,7 +97,7 @@ struct tree Tree left, right; /* operands */ int nterms; /* number of terminal nodes in this tree */ }; -extern Tree tree(struct terminfo* ti, Tree left, Tree right); +extern Tree tree(const struct terminfo* ti, Tree left, Tree right); struct rule { /* rules: */ @@ -106,6 +107,8 @@ struct rule int ern; /* external rule number */ int packed; /* packed external rule number */ int cost; /* associated cost */ + const char* label; /* label for LHS */ + struct regattr* attr; /* register attribute of result */ Rule link; /* next rule in ern order */ Rule next; /* next rule with same pattern root */ Rule chain; /* next chain rule with same rhs */ @@ -116,7 +119,7 @@ struct rule ARRAYOF(struct constraint) constraints; /* register constraints */ struct stringlist code; /* compiler output code strings */ }; -extern Rule rule(char* id, Tree pattern, int ern); +extern Rule rule(const struct terminfo* ti, Tree pattern); extern int maxcost; /* maximum cost */ /* gram.y: */ diff --git a/util/mcgg/mcgg.h b/util/mcgg/mcgg.h index 65dc26f54..14353c0e3 100644 --- a/util/mcgg/mcgg.h +++ b/util/mcgg/mcgg.h @@ -44,6 +44,8 @@ struct burm_emitter_data void (*emit_reg)(int child); void (*emit_value)(int child); void (*emit_eoi)(void); + void (*constrain_input_reg)(int child, int attr); + void (*constrain_output_reg)(int attr); }; typedef void burm_emitter_t(const struct burm_emitter_data* data); @@ -52,7 +54,6 @@ struct burm_instruction_data { const char* name; burm_emitter_t* emitter; - int allocate; bool is_fragment; }; @@ -75,6 +76,11 @@ enum REGATTR_BYTES8 }; +enum +{ + NONTERM_STMT = 1 +}; + #endif /* vim: set sw=4 ts=4 expandtab : */ -- 2.34.1