<[email protected]> writes: > From: Kyrylo Tkachov <[email protected]> > > A machine description often defines one attribute purely in terms of > another, so that a scheduling model can group the several hundred values > of `type' into the handful its pipeline actually distinguishes. In > arm/types.md: > > (define_attr "mul32" "no,yes" > (if_then_else > (eq_attr "type" > "smulxy,smlaxy,smulwy,smlawx,mul,muls,mla,mlas,smlawy,smuad,\ > smuadx,smlad,smladx,smusd,smusdx,smlsd,smlsdx,smmul,smmulr,\ > smmla,smlald,smlsld") > (const_string "yes") > (const_string "no"))) > > That is a total function from `type' to `mul32', and nothing else. But > genattrtab does not represent it that way. optimize_attrs substitutes > the definition of `type' into it and folds the result separately for > every insn code, so what comes out is a switch over recog_memoized: > > attr_mul32 > get_attr_mul32 (rtx_insn *insn ATTRIBUTE_UNUSED) > { > attr_type cached_type ATTRIBUTE_UNUSED; > > switch (recog_memoized (insn)) > { > case -1: > if (GET_CODE (PATTERN (insn)) != ASM_INPUT > && asm_noperands (PATTERN (insn)) < 0) > fatal_insn_not_found (insn); > /* FALLTHRU */ > if (((cached_type = get_attr_type (insn)) == TYPE_SMULXY) > || (cached_type == TYPE_SMLAXY) > ... 20 more ... > || (cached_type == TYPE_SMLSLD)) > { > return MUL32_YES; > } > else > { > return MUL32_NO; > } > > case 424: /* *mulsi_neg_uxtw */ > case 423: /* *muldi_neg */ > ... 10 more ... > case 413: /* mulsi3 */ > return MUL32_YES; > > default: > return MUL32_NO; > } > } > > Two things are worth noticing. The `case -1:' arm, reached for asm > statements, already contains the > mapping in its original form: evaluate `type' once, then decide. Every > other arm is that same decision, precomputed for one insn code and > re-emitted. So the switch is a partially evaluated copy of a function > that the file already knows how to write, keyed on the wrong thing. > > Emit the mapping directly instead: > > static const unsigned char mul32_from_type[] = { > MUL32_NO, MUL32_NO, ..., MUL32_YES, ..., MUL32_NO, > }; > > attr_mul32 > get_attr_mul32 (rtx_insn *insn ATTRIBUTE_UNUSED) > { > return (attr_mul32) mul32_from_type[get_attr_type (insn)]; > } > > The result is better in three ways. It is one array read rather than a > search over insn codes, so it does not grow when the port gains > patterns, only when `type' gains values. It has a single control-flow > path, so the host compiler has nothing to optimise. And the asm case > needs no special handling at all: get_attr_type still issues > fatal_insn_not_found, and whatever `type' it returns indexes the same > table as any other insn. > > The machine description says the attribute is a function of `type', and a > table > indexed by `type' is that function. The pass therefore only has to recognise > the shape, which it does before optimize_attrs destroys it: a cond, or > an if_then_else chain, in which every test is an eq_attr on one single > other attribute and every value including the default is constant. > Anything else, in particular match_test, match_operand, eq_attr_alt and > attr_flag, falls back to the existing expansion. An attribute that a > define_insn sets directly is not a function of anything, so that is > checked too. > > One extension is needed for the case that motivates all this. > cortex_a57_neon_type is written as a cond over `type', except that its > last arm tests is_neon_type, which is itself a function of `type'. So a > test of an attribute already known to be a function of the driver counts > as a test of the driver, and resolving it is a lookup in that > attribute's own table. get_attr_order already supplies the topological > order that guarantees the dependency is processed first. Without this, > the largest of the transformed attributes is missed. > > Supporting ior over the same attribute was measured to gain nothing: > back ends write (eq_attr "type" "a,b,c"), which check_attr_test already > normalises, so every ior in the tree spans more than one attribute. > > Across the tree 107 of 558 attributes qualify, 62 of them on s390, where > the driver is `mnemonic' with over a thousand values. On aarch64 there > are eight, and the switches they replace are far from uniform in size: > > attribute switch lines table + getter lines > mul32 39 466 > widen_mul64 37 466 > is_mve_type 75 466 > is_neon_type 4406 466 > cortex_a53_advsimd_type 4472 466 > cortex_a57_neon_type 5146 466 > exynos_m1_neon_type 4708 466 > tsv110_neon_type 4523 466 > > A table is always |type| entries, so the three attributes that only a > few patterns use get bigger in source. Emitting a table only when it is > the smaller of the two would need a heuristic, and the shape of the > generated code, not its size, is the point, so all of them are > converted. In total insn-attrtab.cc goes from 4.23MB in 91473 lines to > 3.25MB in 71967 lines. It compiles, together with insn-dfatab.cc and > insn-latencytab.cc, in 12% less time, with peak memory 313MB > against 332MB. > > Run time is unchanged. Compiling a 39-file C corpus with > -mcpu=cortex-a57 takes the same time either way. > Note that attribute values are not memoised, so a > derived attribute now runs get_attr_type's switch rather than its own > inlined copy of it. The two are close enough in size that this does not > show up. > > Verified by compiling that corpus with -mcpu=generic, cortex-a57, > cortex-a53, exynos-m1, tsv110, neoverse-v2 and neoverse-n1: they all > produce identical assembly. On the same compiler all 39 > files differ between -mcpu=generic and -mcpu=cortex-a57, so the pipeline > models these attributes feed are being exercised. > > Bootstrapped on aarch64-none-linux-gnu. > Ok for trunk? > > gcc/ChangeLog: > > * genattrtab.cc (attr_value): Add enum_index. > (attr_desc): Add num_values, derived_from and derived_table. > (get_attr_value, add_attr_value, find_attr): Maintain them. > (attr_value_index, eq_attr_value_set, sole_tested_attr) > (find_derived_attrs, write_derived_attr_get): New functions. > (write_attr_get): Use write_derived_attr_get where it applies. > (main): Call find_derived_attrs before optimize_attrs.
Thanks for doing this. It's clearly a big improvement over the status quo. I wonder how often it would be worth allowing an arbitrary "else" value for conds. For example, the table could encode num_values to say that the function should fall through to the usual handling of the else value. That probably doesn't happen often in practice though. Always using a transitively-closed derived_from means that we always use the biggest attribute, and so the biggest tables. I wonder if there are cases where it would be better to use the nearest common ancestor instead. That would potentially give smaller tables at the cost of longer chains (but no worse than the situation without the patch). Neither of those sound like big wins, if they're wins at all, and they could be follow-on patches in any case. Just thought I'd write them down since I'd thought about them... > Signed-off-by: Kyrylo Tkachov <[email protected]> > --- > gcc/genattrtab.cc | 256 ++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 256 insertions(+) > > diff --git a/gcc/genattrtab.cc b/gcc/genattrtab.cc > index a2cf08d5305..07982b74c81 100644 > --- a/gcc/genattrtab.cc > +++ b/gcc/genattrtab.cc > @@ -166,6 +166,8 @@ struct attr_value > struct insn_ent *first_insn; /* First insn with this value. */ > int num_insns; /* Number of insns with this value. */ > int has_asm_insn; /* True if this value used for `asm' insns */ > + int enum_index; /* Position in the attribute's enum, or -1 > + for a value computed by genattrtab. */ > }; > > /* Structure for each attribute. */ > @@ -183,6 +185,13 @@ public: > unsigned is_numeric : 1; /* Values of this attribute are > numeric. */ > unsigned is_const : 1; /* Attribute value constant for each run. */ > unsigned is_special : 1; /* Don't call `write_attr_set'. */ > + int num_values; /* Number of declared enum values. */ > + > + /* Set when the attribute is a function of one other attribute alone. > + DERIVED_FROM is that attribute and DERIVED_TABLE maps each of its > + enum values to one of ours. */ > + class attr_desc *derived_from; > + rtx *derived_table; > }; > > /* Structure for each DEFINE_DELAY. */ > @@ -1260,6 +1269,7 @@ get_attr_value (file_location loc, rtx value, class > attr_desc *attr, > av->first_insn = NULL; > av->num_insns = 0; > av->has_asm_insn = 0; > + av->enum_index = -1; > > return av; > } > @@ -2886,6 +2896,238 @@ get_attr_order (class attr_desc ***ret) > return num; > } > > +/* Return the position of ATTR's enum value called NAME, or -1 if ATTR has > + no such value. */ > + > +static int > +attr_value_index (class attr_desc *attr, const char *name) > +{ > + for (struct attr_value *av = attr->first_value; av; av = av->next) > + if (av->enum_index >= 0 && ! strcmp (XSTR (av->value, 0), name)) > + return av->enum_index; > + return -1; > +} > + > +/* Record in SET which of Y's enum values make the attribute test EXP true. > + SET has Y->num_values entries. Return false if EXP tests anything beyond > + Y and attributes already known to be functions of Y. */ > + > +static bool > +eq_attr_value_set (rtx exp, class attr_desc *y, bool *set) > +{ > + int i; > + > + switch (GET_CODE (exp)) > + { > + case EQ_ATTR: > + { > + const char *name = XSTR (exp, 0); > + class attr_desc *z = find_attr (&name, 0); > + > + if (z == y) > + { > + int index = attr_value_index (y, XSTR (exp, 1)); > + if (index < 0) > + return false; > + memset (set, 0, y->num_values * sizeof (bool)); > + set[index] = true; > + return true; > + } > + > + /* Testing an attribute that is itself a function of Y still selects > + a set of Y values. */ > + if (! z || z->derived_from != y) > + return false; > + for (i = 0; i < y->num_values; i++) > + set[i] = ! strcmp (XSTR (z->derived_table[i], 0), XSTR (exp, 1)); > + return true; > + } > + > + case IOR: > + case AND: > + { > + bool *other = XNEWVEC (bool, y->num_values); I know it's not existing style in these files, but I think we should use auto_vec<bool> for the temporary boolean arrays, rather than manual memory management. eq_attr_value_set would then take an array_slice. > + bool ok = (eq_attr_value_set (XEXP (exp, 0), y, set) > + && eq_attr_value_set (XEXP (exp, 1), y, other)); > + if (ok) > + for (i = 0; i < y->num_values; i++) > + set[i] = (GET_CODE (exp) == IOR > + ? set[i] || other[i] : set[i] && other[i]); > + free (other); > + return ok; > + } > + > + case NOT: > + if (! eq_attr_value_set (XEXP (exp, 0), y, set)) > + return false; > + for (i = 0; i < y->num_values; i++) > + set[i] = ! set[i]; > + return true; > + > + case CONST_INT: > + for (i = 0; i < y->num_values; i++) > + set[i] = INTVAL (exp) != 0; > + return true; > + > + default: > + return false; > + } > +} > + > +/* Return the one attribute that EXP tests, or null if it tests none or more > + than one. SOFAR is the attribute found so far, or null. An attribute > + already known to be a function of another reports that other one. */ > + > +static class attr_desc * > +sole_tested_attr (rtx exp, class attr_desc *sofar) > +{ > + const char *fmt = GET_RTX_FORMAT (GET_CODE (exp)); > + int i; > + > + if (GET_CODE (exp) == EQ_ATTR) > + { > + const char *name = XSTR (exp, 0); > + class attr_desc *attr = find_attr (&name, 0); > + > + if (! attr) > + return NULL; > + if (attr->derived_from) > + attr = attr->derived_from; > + return sofar && sofar != attr ? NULL : attr; > + } > + > + for (i = 0; i < GET_RTX_LENGTH (GET_CODE (exp)); i++) > + if (fmt[i] == 'e') > + { > + sofar = sole_tested_attr (XEXP (exp, i), sofar); > + if (! sofar) > + return NULL; > + } > + return sofar; > +} > + > +/* Note every attribute whose value is a function of one other attribute > + alone, so that write_attr_get can emit a lookup table for it rather than > + repeat the other attribute's decision tree for every insn code. > + > + Run this after fill_attr, so that a define_insn overriding the attribute > + is visible, and before optimize_attrs, which folds the cond away. */ > + > +static void > +find_derived_attrs (void) > +{ > + class attr_desc **order; > + int num = get_attr_order (&order); > + int n; > + > + for (n = 0; n < num; n++) > + { > + class attr_desc *attr = order[n]; > + rtx cond = attr->default_val->value; > + class attr_desc *y = NULL; > + bool overridden = false; > + rtx *table; > + bool *seen, *set; > + int i; > + > + if (attr->is_const || attr->is_special || attr->is_numeric > + || attr->name[0] == '*' || GET_CODE (cond) != COND) I think there's supposed to be a coding style rule about one test per line (not always followed), which I think would help with this test and the one below. It might also be worth splitting the "is this an enum?" test out into a subroutine, since it's used twice, but it's ok as-is. > + continue; > + > + /* A define_insn that sets the attribute directly overrides the cond, > + so the attribute is then not a function of anything. */ > + for (struct attr_value *av = attr->first_value; av; av = av->next) > + if (av != attr->default_val && av->num_insns != 0) > + { > + overridden = true; > + break; > + } > + if (overridden) > + continue; > + > + for (i = 0; i < XVECLEN (cond, 0); i += 2) > + { > + y = sole_tested_attr (XVECEXP (cond, 0, i), y); > + if (! y || GET_CODE (XVECEXP (cond, 0, i + 1)) != CONST_STRING) > + { > + y = NULL; > + break; > + } > + } > + > + /* Y must be a plain enum attribute whose values genattr-common.cc > + numbers from zero, so that they can index the table. */ > + if (! y || y == attr || y->num_values == 0 > + || y->is_const || y->is_special || y->is_numeric > + || y->enum_name || y->name[0] == '*' > + || GET_CODE (XEXP (cond, 1)) != CONST_STRING) > + continue; > + > + table = XCNEWVEC (rtx, y->num_values); > + seen = XCNEWVEC (bool, y->num_values); > + set = XNEWVEC (bool, y->num_values); > + > + for (i = 0; i < XVECLEN (cond, 0); i += 2) > + { > + if (! eq_attr_value_set (XVECEXP (cond, 0, i), y, set)) > + break; > + /* The cond takes the first arm that matches. */ > + for (int k = 0; k < y->num_values; k++) > + if (set[k] && ! seen[k]) > + { > + seen[k] = true; > + table[k] = XVECEXP (cond, 0, i + 1); > + } > + } > + > + if (i >= XVECLEN (cond, 0)) > + { > + for (i = 0; i < y->num_values; i++) > + if (! seen[i]) > + table[i] = XEXP (cond, 1); > + for (i = 0; i < y->num_values; i++) > + gcc_assert (attr_value_index (attr, XSTR (table[i], 0)) >= 0); Is the seen array needed? It seems like we could use XCNEWVEC for table instead. OK with those changes, thanks. (The inline changes that is, not the ramblings at the top.) Richard > + attr->derived_from = y; > + attr->derived_table = table; > + } > + else > + free (table); > + > + free (seen); > + free (set); > + } > + > + free (order); > +} > + > +/* Emit ATTR's getter as a lookup into a table indexed by the attribute it > + is derived from. */ > + > +static void > +write_derived_attr_get (FILE *outf, class attr_desc *attr) > +{ > + class attr_desc *y = attr->derived_from; > + int i; > + > + gcc_assert (attr->num_values <= USHRT_MAX + 1); > + fprintf (outf, "static const %s %s_from_%s[] = {\n", > + attr->num_values <= UCHAR_MAX + 1 > + ? "unsigned char" : "unsigned short", attr->name, y->name); > + for (i = 0; i < y->num_values; i++) > + { > + fprintf (outf, " "); > + write_attr_valueq (outf, attr, XSTR (attr->derived_table[i], 0)); > + fprintf (outf, ",\n"); > + } > + fprintf (outf, "};\n\n"); > + > + fprintf (outf, "%s\n", attr->cxx_type); > + fprintf (outf, "get_attr_%s (rtx_insn *insn ATTRIBUTE_UNUSED)\n{\n", > + attr->name); > + fprintf (outf, " return (%s) %s_from_%s[get_attr_%s (insn)];\n}\n\n", > + attr->cxx_type, attr->name, y->name, y->name); > +} > + > /* Optimize the attribute lists by seeing if we can determine conditional > values from the known values of other attributes. This will save > subroutine > calls during the compilation. NUM_INSN_CODES is the number of unique > @@ -3059,6 +3301,7 @@ add_attr_value (class attr_desc *attr, const char *name) > av->first_insn = NULL; > av->num_insns = 0; > av->has_asm_insn = 0; > + av->enum_index = attr->num_values++; > } > > /* Create table entries for DEFINE_ATTR or DEFINE_ENUM_ATTR. */ > @@ -4056,6 +4299,12 @@ write_attr_get (FILE *outf, class attr_desc *attr) > struct attr_value *av, *common_av; > int i, j; > > + if (attr->derived_from) > + { > + write_derived_attr_get (outf, attr); > + return; > + } > + > /* Find the most used attribute value. Handle that as the `default' of the > switch we will generate. */ > common_av = find_most_used (attr); > @@ -4669,6 +4918,9 @@ find_attr (const char **name_p, int create) > attr->cxx_type = nullptr; > attr->first_value = attr->default_val = NULL; > attr->is_numeric = attr->is_const = attr->is_special = 0; > + attr->num_values = 0; > + attr->derived_from = NULL; > + attr->derived_table = NULL; > attr->next = attrs[index]; > attrs[index] = attr; > > @@ -5360,6 +5612,10 @@ main (int argc, const char **argv) > /* Construct extra attributes for `length'. */ > make_length_attrs (); > > + /* Note the attributes that are functions of one other attribute alone. > + This has to happen before optimize_attrs folds their conds away. */ > + find_derived_attrs (); > + > /* Perform any possible optimizations to speed up compilation. */ > optimize_attrs (num_insn_codes);
