> On 15 Sep 2026, at 13:23, Richard Sandiford <[email protected]> > wrote: > > <[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.) >
Thanks Richard. I think this version should address these comments.
I’ll commit this shortly.
Kyrill
> 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);
0009-genattrtab-table-drive-attributes-that-are-functions.patch
Description: 0009-genattrtab-table-drive-attributes-that-are-functions.patch
