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.
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);
+ 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)
+ 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);
+ 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);
--
2.50.1 (Apple Git-155)
