From b1a3d76d6fe525e0cf5c7ae741c6c78d25b0198e Mon Sep 17 00:00:00 2001 From: David Given Date: Sat, 22 Oct 2016 23:04:13 +0200 Subject: [PATCH] Re-re-add the type inference layer, now I know more about how things work. Remove that terrible float promotion code. --- mach/proto/mcg/ir.c | 4 +- mach/proto/mcg/ir.h | 1 + mach/proto/mcg/mcg.h | 2 +- mach/proto/mcg/pass_promotefloatops.c | 122 ------------ mach/proto/mcg/pass_typeinference.c | 277 ++++++++++++++++++++++++++ mach/proto/mcg/procedure.c | 2 +- util/mcgg/ir.dat | 215 ++++++++++---------- util/mcgg/ircodes.h | 3 + util/mcgg/ircodes.sh | 15 +- 9 files changed, 413 insertions(+), 228 deletions(-) delete mode 100644 mach/proto/mcg/pass_promotefloatops.c create mode 100644 mach/proto/mcg/pass_typeinference.c diff --git a/mach/proto/mcg/ir.c b/mach/proto/mcg/ir.c index 74fbac060..e30e82a2b 100644 --- a/mach/proto/mcg/ir.c +++ b/mach/proto/mcg/ir.c @@ -105,7 +105,9 @@ struct ir* ir_find(struct ir* ir, int opcode) static void print_expr(char k, const struct ir* ir) { tracef(k, "%s", ir_data[ir->opcode].name); - if (ir->size) + if (ir->type) + tracef(k, ".%c", ir->type); + else if (ir->size) tracef(k, "%d", ir->size); tracef(k, "("); diff --git a/mach/proto/mcg/ir.h b/mach/proto/mcg/ir.h index 83dd34246..10fa83a48 100644 --- a/mach/proto/mcg/ir.h +++ b/mach/proto/mcg/ir.h @@ -8,6 +8,7 @@ struct ir int id; enum ir_opcode opcode; int size; + char type; struct ir* left; struct ir* right; struct ir* root; diff --git a/mach/proto/mcg/mcg.h b/mach/proto/mcg/mcg.h index f76264813..c60dee9ce 100644 --- a/mach/proto/mcg/mcg.h +++ b/mach/proto/mcg/mcg.h @@ -109,11 +109,11 @@ extern void pass_convert_stack_ops(void); extern void pass_eliminate_trivial_blocks(void); extern void pass_find_phi_congruence_groups(void); 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_add_prologue_epilogue(void); -extern void pass_promote_float_ops(void); extern void pass_register_allocator(void); extern void pass_remove_dead_blocks(void); extern void pass_remove_dead_phis(void); diff --git a/mach/proto/mcg/pass_promotefloatops.c b/mach/proto/mcg/pass_promotefloatops.c deleted file mode 100644 index 7e5f87c19..000000000 --- a/mach/proto/mcg/pass_promotefloatops.c +++ /dev/null @@ -1,122 +0,0 @@ -#include "mcg.h" - -static ARRAYOF(struct ir) pending; -static ARRAYOF(struct ir) promotable; - -static void addall(struct ir* ir) -{ - if (array_appendu(&pending, ir)) - return; - - if (ir->left) - addall(ir->left); - if (ir->right) - addall(ir->right); -} - -static void collect_irs(void) -{ - int i; - - pending.count = 0; - promotable.count = 0; - for (i=0; iirs.count; j++) - addall(bb->irs.item[j]); - } -} - -static void promote(struct ir* ir) -{ - switch (ir->opcode) - { - case IR_CONST: - case IR_POP: - case IR_LOAD: - array_appendu(&promotable, ir); - break; - - case IR_NOP: - promote(ir->left); - break; - - case IR_PHI: - { - int i; - for (i=0; iu.phivalue.count; i++) - promote(ir->u.phivalue.item[i].right); - break; - } - } -} - -static void search_for_promotable_irs(void) -{ - int i; - - for (i=0; iopcode) - { - case IR_ADDF: - case IR_SUBF: - case IR_MULF: - case IR_DIVF: - case IR_NEGF: - case IR_COMPAREF1: - case IR_COMPAREF2: - case IR_COMPAREF4: - case IR_COMPAREF8: - case IR_CFF1: - case IR_CFF2: - case IR_CFF4: - case IR_CFF8: - if (ir->left) - promote(ir->left); - if (ir->right) - promote(ir->right); - break; - } - } -} - -static void modify_promotable_irs(void) -{ - int i; - - for (i=0; iopcode) - { - case IR_ADDF: - case IR_SUBF: - case IR_MULF: - case IR_DIVF: - case IR_NEGF: - case IR_PHI: - case IR_NOP: - break; - - default: - ir->opcode++; - break; - } - } -} - -void pass_promote_float_ops(void) -{ - collect_irs(); - search_for_promotable_irs(); - modify_promotable_irs(); -} - -/* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/pass_typeinference.c b/mach/proto/mcg/pass_typeinference.c new file mode 100644 index 000000000..d330152ef --- /dev/null +++ b/mach/proto/mcg/pass_typeinference.c @@ -0,0 +1,277 @@ +#include "mcg.h" + +static bool changed; +static ARRAYOF(struct ir) irs; + +static void addall(struct ir* ir) +{ + if (array_appendu(&irs, ir)) + return; + + if (ir->left) + addall(ir->left); + if (ir->right) + addall(ir->right); +} + +static void collect_irs(void) +{ + int i; + + irs.count = 0; + for (i=0; iirs.count; j++) + addall(bb->irs.item[j]); + } +} + +static char effective_type(struct ir* ir, char type) +{ + switch (type) + { + case 'I': + case 'F': + case 'L': + case 'D': + return type; + + case 'i': + if (ir->size == EM_wordsize) + return 'I'; + else if (ir->size == (EM_wordsize*2)) + return 'L'; + break; + + case 'f': + if (ir->size == EM_wordsize) + return 'F'; + else if (ir->size == (EM_wordsize*2)) + return 'D'; + break; + } + + return 0; +} + +static void scan_irs(void) +{ + int i; + + for (i=0; iopcode == IR_PHI) + { + int j; + + /* Phis are special. We treat them as ?=? for every import value. + * */ + + if (ir->type) + { + /* Push this type to all our children. */ + + for (j=0; ju.phivalue.count; j++) + { + struct ir* child = ir->u.phivalue.item[j].right; + if (!child->type) + { + child->type = ir->type; + changed = true; + } + } + } + else + { + /* Pull our type from the first child with a set type; we + * ignore the rest, as the next iteration will push our type to + * them. It's possible for our children to have conflicting + * types. There's not much we can do about that so we just have + * to live with it and intelligently insert casts. */ + + for (j=0; ju.phivalue.count; j++) + { + struct ir* child = ir->u.phivalue.item[j].right; + if (child->type) + { + /* Found one! */ + ir->type = child->type; + changed = true; + break; + } + } + } + } + else + { + const struct ir_data* ird = &ir_data[ir->opcode]; + + if (!ir->type) + { + char etype = effective_type(ir, ird->returntype); + if (etype) + { + ir->type = etype; + changed = true; + } + } + + if (ir->left && !ir->left->type) + { + const struct ir_data* leftird = &ir_data[ir->left->opcode]; + if (leftird->returntype == '?') + { + char etype = effective_type(ir, ird->lefttype); + if (etype) + { + ir->left->type = etype; + changed = true; + } + } + } + + if (ir->right && !ir->right->type) + { + const struct ir_data* rightird = &ir_data[ir->right->opcode]; + if (rightird->returntype == '?') + { + char etype = effective_type(ir, ird->righttype); + if (etype) + { + ir->right->type = etype; + changed = true; + } + } + } + + if (!ir->type && (ird->returntype == '?')) + { + if ((ird->lefttype == '?') && ir->left->type) + { + ir->type = ir->left->type; + changed = true; + } + + if ((ird->righttype == '?') && ir->right->type) + { + ir->type = ir->right->type; + changed = true; + } + } + + if (ir->type && (ird->lefttype == '?') && !ir->left->type) + { + ir->left->type = ir->type; + changed = true; + } + + if (ir->type && (ird->righttype == '?') && !ir->right->type) + { + ir->right->type = ir->type; + changed = true; + } + } + } +} + +static void propagate_types(void) +{ + do + { + changed = false; + + scan_irs(); + } + while (changed); +} + +static void assign_fallback_types(void) +{ + int i; + + for (i=0; iopcode]; + + if (!ir->type && (ird->returntype == '?')) + ir->type = effective_type(ir, 'i'); + } +} + +static struct ir* new_copy(char wanted, char real, struct ir* ir) +{ + struct ir* copy; + int opcode; + + if ((wanted == 'F') && (real == 'I')) + opcode = IR_COPYI; + else if ((wanted == 'D') && (real == 'L')) + opcode = IR_COPYI; + else if ((wanted == 'I') && (real == 'F')) + opcode = IR_COPYF; + else if ((wanted == 'L') && (real == 'D')) + opcode = IR_COPYF; + else + fatal("type mismatch: parent IR wanted %c, child IR provided %c", + wanted, real); + + copy = new_ir1(opcode, ir->size, ir); + copy->type = wanted; + return copy; +} + +static void insert_copies(void) +{ + int i; + + /* Insert copies for normal IR nodes. */ + + for (i=0; iopcode]; + + if (ir->left) + { + char wanted = effective_type(ir, ird->lefttype); + char real = ir->left->type; + + if (wanted && (wanted != real)) + { + struct ir* copy = new_copy(wanted, real, ir->left); + copy->root = ir->root; + ir->left = copy; + } + } + + if (ir->right) + { + char wanted = effective_type(ir, ird->righttype); + char real = ir->right->type; + + if (wanted && (wanted != real)) + { + struct ir* copy = new_copy(wanted, real, ir->right); + copy->root = ir->root; + ir->right = copy; + } + } + } +} + +void pass_infer_types(void) +{ + collect_irs(); + propagate_types(); + assign_fallback_types(); + insert_copies(); +} + +/* vim: set sw=4 ts=4 expandtab : */ + diff --git a/mach/proto/mcg/procedure.c b/mach/proto/mcg/procedure.c index 320dedf7b..a41dac459 100644 --- a/mach/proto/mcg/procedure.c +++ b/mach/proto/mcg/procedure.c @@ -184,7 +184,7 @@ void procedure_compile(struct procedure* proc) pass_convert_locals_to_ssa(); print_blocks('5'); pass_remove_dead_phis(); - pass_promote_float_ops(); + pass_infer_types(); print_blocks('6'); pass_instruction_selector(); diff --git a/util/mcgg/ir.dat b/util/mcgg/ir.dat index 5c47c6639..8f09d4204 100644 --- a/util/mcgg/ir.dat +++ b/util/mcgg/ir.dat @@ -1,123 +1,138 @@ # Flags: # S: has size (use in CONST1, CONST2, CONST4, CONST8 forms) # V: has no size (use in JUMP, CJUMP, RET forms) +# +# Types: +# +# I, F, L, D: int, float, long, double +# i, F: int, float; promoted to long, double based on size +# .: ignore this parameter +# ?: pull/push types from other ? parameters # Simple terminals -S CONST # must be followed by float form -S CONSTF -V REG -V NOP -S LABEL -S BLOCK -V PAIR -S ANY -S LOCAL -V PHI +S ?=.. CONST # must be followed by float form +S ?=.. CONSTF +V ?=.. REG +V ?=?. NOP +S I=.. LABEL +S I=.. BLOCK +V ?=.. PAIR +S ?=.. ANY +S ?=.. LOCAL +V ?=.. PHI # Magic stack operations -S PUSH -S POP # must be followed by float form -S POPF +S ?=?. PUSH +S ?=.. POP +S ?=.. POPF -#... Memory operations -S LOAD # must be followed by float form -S LOADF -S STORE -S STOREF +# Memory operations +S ?=I. LOAD # must be followed by float form +S f=I. LOADF +S ?=I? STORE +S ?=If STOREF # Arithemetic operations -S ADD -S SUB -S MUL -S DIV -S DIVU -S MOD -S MODU -S NEG - -S ADDF -S SUBF -S MULF -S DIVF -S NEGF - -S AND -S OR -S EOR -S NOT -S ASL -S ASR -S LSL -S LSR - -# Conversions -S CII1 -S CII2 -S CII4 -S CII8 - -S CIU1 -S CIU2 -S CIU4 -S CIU8 - -S CUI1 -S CUI2 -S CUI4 -S CUI8 - -S CFI1 -S CFI2 -S CFI4 -S CFI8 - -S CIF1 -S CIF2 -S CIF4 -S CIF8 - -S CFF1 -S CFF2 -S CFF4 -S CFF8 +S i=ii ADD +S i=ii SUB +S i=ii MUL +S i=ii DIV +S i=ii DIVU +S i=ii MOD +S i=ii MODU +S i=ii NEG + +S f=ff ADDF +S f=ff SUBF +S f=ff MULF +S f=ff DIVF +S f=ff NEGF + +S i=ii AND +S i=ii OR +S i=ii EOR +S i=ii NOT +S i=ii ASL +S i=ii ASR +S i=ii LSL +S i=ii LSR + +# Bitwise conversions +# (Remember, these don't change the value, merely move it) +S i=f. COPYF +S f=i. COPYI + +# Semantic conversions +S F=D. D2F +S D=F. F2D + +S I=I. CII1 +S I=I. CII2 +S I=I. CII4 +S L=L. CII8 + +S I=I. CIU1 +S I=I. CIU2 +S I=I. CIU4 +S L=L. CIU8 + +S I=I. CUI1 +S I=I. CUI2 +S I=I. CUI4 +S L=L. CUI8 + +S I=F. CFI1 +S I=F. CFI2 +S I=F. CFI4 +S L=D. CFI8 + +S I=F. CIF1 +S I=F. CIF2 +S I=F. CIF4 +S L=D. CIF8 + +S F=F. CFF1 +S F=F. CFF2 +S F=F. CFF4 +S D=D. CFF8 # Tristate comparisons -S COMPARES1 -S COMPARES2 -S COMPARES4 -S COMPARES8 +S I=II COMPARES1 +S I=II COMPARES2 +S I=II COMPARES4 +S I=LL COMPARES8 -S COMPAREU1 -S COMPAREU2 -S COMPAREU4 -S COMPAREU8 +S I=II COMPAREU1 +S I=II COMPAREU2 +S I=II COMPAREU4 +S I=LL COMPAREU8 -S COMPAREF1 -S COMPAREF2 -S COMPAREF4 -S COMPAREF8 +S I=FF COMPAREF1 +S I=FF COMPAREF2 +S I=FF COMPAREF4 +S I=DD COMPAREF8 # Tristate to boolean conversion -S IFEQ -S IFLT -S IFLE +S I=I. IFEQ +S I=I. IFLT +S I=I. IFLE # Procedures -S CALL +S i=.. CALL # Flow control --- these never return -V JUMP -V CJUMPEQ -V CJUMPLT -V CJUMPLE -V RET +V .=i. JUMP +V .=i. CJUMPEQ +V .=i. CJUMPLT +V .=i. CJUMPLE +V .=.. RET # Special -S STACKADJUST -S SETRET -S GETFP -S GETSP -S SETSP -S CHAINFP -S FPTOARGS +S ?=i. STACKADJUST +S ?=i. SETRET +S i=.. GETFP +S i=.. GETSP +S ?=i. SETSP +S i=i. CHAINFP +S i=i. FPTOARGS diff --git a/util/mcgg/ircodes.h b/util/mcgg/ircodes.h index c5bbb9f2d..7d91b27fd 100644 --- a/util/mcgg/ircodes.h +++ b/util/mcgg/ircodes.h @@ -10,6 +10,9 @@ struct ir_data { const char* name; int flags; + char returntype; + char lefttype; + char righttype; }; extern const struct ir_data ir_data[]; diff --git a/util/mcgg/ircodes.sh b/util/mcgg/ircodes.sh index 7c9917d12..ff2df4845 100755 --- a/util/mcgg/ircodes.sh +++ b/util/mcgg/ircodes.sh @@ -10,7 +10,7 @@ awk -f - $in >$header << "EOF" } /^ *[^# ]+/ { - print "\tIR_" $2 "," + print "\tIR_" $3 "," } END { @@ -30,9 +30,18 @@ awk -f - $in >$source << "EOF" return "0" } + function char_to_type(c) { + if (c ~ /[A-Za-z]/) return "'"c"'" + if (c == "?") return "'?'" + if (c == ".") return "0" + } + /^ *[^# ]+/ { - printf("\t{ \"%s\", ", $2) - printf("%s", char_to_flags(substr($1, 1, 1))) + printf("\t{ \"%s\", ", $3) + printf("%s, ", char_to_flags(substr($1, 1, 1))) + printf("%s, ", char_to_type(substr($2, 1, 1))) + printf("%s, ", char_to_type(substr($2, 3, 1))) + printf("%s, ", char_to_type(substr($2, 4, 1))) printf(" },\n") } -- 2.34.1