https://gcc.gnu.org/g:f4d579b7a2ace16c9b0b7912940ff6809f8ddf9c
commit r17-4260-gf4d579b7a2ace16c9b0b7912940ff6809f8ddf9c Author: Kyrylo Tkachov <[email protected]> Date: Fri Aug 7 11:23:20 2026 +0200 genattrtab: table-drive attributes that are functions of one other attribute 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 whose `type' is only known at run time, 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. This is correct by construction rather than by testing. 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 selects a set of values of one single other attribute and every value including the default is constant. check_attr_test has already rewritten (eq_attr "type" "a,b,c") into an ior chain over single values, so a test is matched as a boolean combination of eq_attr. 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. 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.26MB in 92424 lines to 3.28MB in 72584 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, within a run-to-run spread of about 1.5%. 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: 273 compilations, and the assembly does not change. 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. 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, simple_enum_attr_p) (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. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/genattrtab.cc | 265 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 265 insertions(+) diff --git a/gcc/genattrtab.cc b/gcc/genattrtab.cc index a2cf08d53058..503c50637aa0 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,247 @@ 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, array_slice<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; + for (i = 0; i < y->num_values; i++) + set[i] = false; + 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: + { + auto_vec<bool, 64> other; + other.safe_grow (y->num_values); + 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]); + 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 true if ATTR's values are a plain enumeration, rather than numbers + or something genattrtab computes for itself. */ + +static bool +simple_enum_attr_p (class attr_desc *attr) +{ + return (!attr->is_const + && !attr->is_special + && !attr->is_numeric + && attr->name[0] != '*'); +} + +/* 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; + int i; + + if (!simple_enum_attr_p (attr) + || GET_CODE (cond) != COND) + 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 + || !simple_enum_attr_p (y) + || y->enum_name + || GET_CODE (XEXP (cond, 1)) != CONST_STRING) + continue; + + table = XCNEWVEC (rtx, y->num_values); + auto_vec<bool, 64> set; + set.safe_grow (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, so an entry that is + already filled in stays as it is. */ + for (int k = 0; k < y->num_values; k++) + if (set[k] && !table[k]) + table[k] = XVECEXP (cond, 0, i + 1); + } + + if (i >= XVECLEN (cond, 0)) + { + for (i = 0; i < y->num_values; i++) + if (!table[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); + attr->derived_from = y; + attr->derived_table = table; + } + else + free (table); + } + + 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 +3310,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 +4308,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 +4927,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 +5621,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);
