From: Kyrylo Tkachov <[email protected]>
genextract already knows each operand's location as a path string, built
by walk_rtx while it descends the pattern: a digit selects an XEXP and a
letter an XVECEXP. print_path then expanded those strings back into C,
so insn_extract became one switch with an arm per insn code. Patterns
that extract alike share an arm, but the labels still cost a line each:
on aarch64, 16068 case labels selecting 649 distinct bodies, 782KB of
labels against 252KB of bodies, all inside a single 1MB function. On
riscv64 it is 45386 labels.
Emit the path strings as data and walk them instead. Three tables
replace the switch.
extract_method_of_code[] maps an insn code to an extraction method.
Method 0 means the code has no pattern to extract from, which is the
error case the old default arm handled, and method 1 means an old-style
define_peephole, whose operand count is only known at run time:
static const unsigned short extract_method_of_code[] = {
0, 650, 650, 649, 649, 648, 647, 646, 646, 646, ...
extract_methods[] gives each method its operand and dup counts and its
offsets into the path and dup-number pools:
static const struct extract_method_d extract_methods[] = {
...
{ 51, 0, 4, 0 }, /* 4 operands, no dups, paths at offset 51 */
and extract_paths[] holds the paths themselves, NUL separated, operands
first and dups second. "1c" is XVECEXP (XEXP (pat, 1), 0, 2), because
'1' selects XEXP 1 and 'c' selects XVECEXP element 2:
static const char extract_paths[] =
"1c0\0001c1\0001d\0001e\0001f\0001c\0001d\0001e\000...
So the arm that used to read
case 16029: /* aarch64_sme_fmopsvnx8hivnx16qi */
case 16028: /* aarch64_sme_fmopavnx8hivnx16qi */
... /* 34 more labels */
case 15740: /* aarch64_sme_fmopavnx4sivnx16qi */
ro[0] = *(ro_loc[0] = &XVECEXP (XEXP (pat, 1), 0, 2));
ro[1] = *(ro_loc[1] = &XVECEXP (XEXP (pat, 1), 0, 3));
ro[2] = *(ro_loc[2] = &XVECEXP (XEXP (pat, 1), 0, 4));
ro[3] = *(ro_loc[3] = &XVECEXP (XEXP (pat, 1), 0, 5));
ro[4] = *(ro_loc[4] = &XVECEXP (XEXP (pat, 1), 0, 6));
break;
is now one shared entry "1c\0001d\0001e\0001f\0001g" in extract_paths[],
one row in extract_methods[], and 36 entries in extract_method_of_code[]
that name it. insn_extract itself becomes a loop over the method's
operands, calling follow_extract_path once each.
The terminator is spelled \000 rather than \0 because the next character
is often a digit, which a shorter octal escape would absorb.
insn-extract.cc drops from 1.04MB/21139 lines to 124KB/1823 lines on
aarch64, 2.25MB to 246KB on riscv64, 750KB to 100KB on x86_64 and 170KB
to 26KB on avr. Compile time falls by 92% and peak memory
from 332MB to 166MB.
insn_extract is hot, so the I measured that there's no non-noise impact
on compile time over a bunch of input files.
A differential harness compares the operand and dup locations the old
switch and the new tables produce, for every insn code: 16116 on aarch64,
45386 on riscv64, 11335 on x86_64, 10608 on i686 and 3562 on avr. 87007
insn codes, no differences. avr covers the old-style define_peephole
path, which the other four do not have.
Bootstrapped on aarch64-none-linux-gnu.
Ok for trunk?
gcc/ChangeLog:
* genextract.cc (MISSING_OPERAND_CHAR): New macro.
(pathpool, dupnums): New variables.
(add_path, print_string_literal, print_extractions): New functions.
(print_path): Remove.
(print_header): Only emit the prologue.
(main): Call print_extractions.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/genextract.cc | 316 +++++++++++++++++++++++++++++-----------------
1 file changed, 199 insertions(+), 117 deletions(-)
diff --git a/gcc/genextract.cc b/gcc/genextract.cc
index 44094fdc281..62babeb3982 100644
--- a/gcc/genextract.cc
+++ b/gcc/genextract.cc
@@ -304,52 +304,31 @@ walk_rtx (md_rtx_info *info, rtx x, class accum_extract
*acc)
}
}
-/* Given a PATH, representing a path down the instruction's
- pattern from the root to a certain point, output code to
- evaluate to the rtx at that point. */
+/* The character that marks an operand number that a pattern does not use.
+ It cannot clash with a path step, which is always a digit or a letter. */
+#define MISSING_OPERAND_CHAR '!'
-static void
-print_path (const char *path)
-{
- int len = strlen (path);
- int i;
-
- if (len == 0)
- {
- /* Don't emit "pat", since we may try to take the address of it,
- which isn't what is intended. */
- fputs ("PATTERN (insn)", stdout);
- return;
- }
-
- /* We first write out the operations (XEXP or XVECEXP) in reverse
- order, then write "pat", then the indices in forward order. */
+/* The paths of all extraction methods, concatenated. Each path is NUL
+ terminated; the paths of one method are adjacent, operands first and
+ dups second. */
+static struct obstack pathpool;
- for (i = len - 1; i >= 0 ; i--)
- {
- if (ISLOWER (path[i]) || ISUPPER (path[i]))
- fputs ("XVECEXP (", stdout);
- else if (ISDIGIT (path[i]))
- fputs ("XEXP (", stdout);
- else
- gcc_unreachable ();
- }
+/* The dup numbers of all extraction methods, concatenated. */
+static vec<int> dupnums;
- fputs ("pat", stdout);
+/* Add PATH, which is null for an operand number that the pattern skips,
+ to the path pool. */
- for (i = 0; i < len; i++)
- {
- if (ISUPPER (path[i]))
- printf (", 0, %d)", path[i] - UPPER_OFFSET);
- else if (ISLOWER (path[i]))
- printf (", 0, %d)", path[i] - 'a');
- else if (ISDIGIT (path[i]))
- printf (", %d)", path[i] - '0');
- else
- gcc_unreachable ();
- }
+static void
+add_path (const char *path)
+{
+ if (path)
+ obstack_grow (&pathpool, path, strlen (path));
+ else
+ obstack_1grow (&pathpool, MISSING_OPERAND_CHAR);
+ obstack_1grow (&pathpool, '\0');
}
-
+
static void
print_header (void)
{
@@ -374,43 +353,203 @@ print_header (void)
/* This variable is used as the \"location\" of any missing operand\n\
whose numbers are skipped by a given pattern. */\n\
static rtx junk ATTRIBUTE_UNUSED;\n");
+}
+
+/* Print STR as a C string literal, broken into chunks so that no output
+ line gets excessively long. */
+
+static void
+print_string_literal (const char *str, unsigned int len)
+{
+ printf (" \"");
+ for (unsigned int i = 0; i < len; i++)
+ {
+ if (str[i] == '\0')
+ /* Spell the terminator with all three octal digits: the next
+ character may be a digit, which a shorter escape would absorb. */
+ printf ("\\000");
+ else
+ putchar (str[i]);
+ if ((i % 60) == 59 && i + 1 < len)
+ printf ("\"\n \"");
+ }
+ printf ("\"");
+}
+
+/* Print the tables that drive insn_extract, and insn_extract itself. */
+
+static void
+print_extractions (void)
+{
+ struct extraction *p;
+ struct code_ptr *link;
+ unsigned int i;
+
+ /* Number the methods and record, for every insn code, the method that
+ extracts its operands. Method 0 means "not an extractable insn" and
+ method 1 means "an old-style define_peephole", whose operand count is
+ only known at run time. */
+ auto_vec<unsigned int> method_of_code;
+ auto_vec<struct extraction *> methods;
+ auto_vec<unsigned int> path_start;
+ auto_vec<unsigned int> dup_start;
+
+ for (link = peepholes; link; link = link->next)
+ {
+ while (method_of_code.length () <= (unsigned int) link->insn_code)
+ method_of_code.safe_push (0);
+ method_of_code[link->insn_code] = 1;
+ }
+
+ obstack_init (&pathpool);
+ for (p = extractions; p; p = p->next)
+ {
+ unsigned int method = methods.length () + 2;
+ gcc_assert (method <= USHRT_MAX);
+ gcc_assert (p->op_count <= UCHAR_MAX && p->dup_count <= UCHAR_MAX);
+ path_start.safe_push (obstack_object_size (&pathpool));
+ dup_start.safe_push (dupnums.length ());
+ methods.safe_push (p);
+ for (i = 0; i < p->op_count; i++)
+ add_path (p->oplocs[i]);
+ for (i = 0; i < p->dup_count; i++)
+ {
+ add_path (p->duplocs[i]);
+ gcc_assert (IN_RANGE (p->dupnums[i], 0, UCHAR_MAX));
+ dupnums.safe_push (p->dupnums[i]);
+ }
+ for (link = p->insns; link; link = link->next)
+ {
+ while (method_of_code.length () <= (unsigned int) link->insn_code)
+ method_of_code.safe_push (0);
+ method_of_code[link->insn_code] = method;
+ }
+ }
+ path_start.safe_push (obstack_object_size (&pathpool));
+
+ unsigned int pool_len = obstack_object_size (&pathpool);
+ const char *pool = XOBFINISH (&pathpool, const char *);
+
+ printf ("/* The paths that locate the operands and the dups of each\n"
+ " extraction method. A path is a sequence of steps down the\n"
+ " pattern: a digit D selects XEXP (x, D - '0'), a lower-case\n"
+ " letter L selects XVECEXP (x, 0, L - 'a') and an upper-case\n"
+ " letter U selects XVECEXP (x, 0, U - %d). An empty path denotes\n"
+ " the pattern itself and '%c' an operand number that the pattern\n"
+ " does not use. */\n", UPPER_OFFSET, MISSING_OPERAND_CHAR);
+ printf ("#define UPPER_OFFSET %d\n", UPPER_OFFSET);
+ printf ("#define MISSING_OPERAND_CHAR '%c'\n\n", MISSING_OPERAND_CHAR);
+ printf ("static const char extract_paths[] =\n");
+ print_string_literal (pool, pool_len);
+ printf (";\n\n");
+
+ printf ("static const unsigned char extract_dup_num[] = {");
+ for (i = 0; i < dupnums.length (); i++)
+ printf ("%s%d,", (i % 20) == 0 ? "\n " : " ", dupnums[i]);
+ printf ("%s0\n};\n\n", dupnums.length () ? "\n " : "");
+
+ printf ("struct extract_method_d {\n"
+ " unsigned int paths;\n"
+ " unsigned int dups;\n"
+ " unsigned char n_operands;\n"
+ " unsigned char n_dups;\n"
+ "};\n\n");
+
+ printf ("static const struct extract_method_d extract_methods[] = {\n"
+ " { 0, 0, 0, 0 },\n"
+ " { 0, 0, 0, 0 },\n");
+ for (i = 0; i < methods.length (); i++)
+ printf (" { %u, %u, %u, %u },\n", path_start[i], dup_start[i],
+ methods[i]->op_count, methods[i]->dup_count);
+ printf ("};\n\n");
+
+ printf ("static const unsigned short extract_method_of_code[] = {");
+ for (i = 0; i < method_of_code.length (); i++)
+ printf ("%s%u,", (i % 20) == 0 ? "\n " : " ", method_of_code[i]);
+ printf ("\n};\n\n");
+
+ puts ("\
+/* Follow one NUL-terminated path in extract_paths from *PP, starting at\n\
+ the pattern *ROOT, and return the location it selects. *PP is left\n\
+ just after the path's terminator. */\n\
+\n\
+static inline rtx *\n\
+follow_extract_path (const char **pp, rtx *root)\n{\n\
+ const char *p = *pp;\n\
+ rtx *loc = root;\n\
+ for (; *p; p++)\n\
+ if (ISDIGIT (*p))\n\
+ loc = &XEXP (*loc, *p - '0');\n\
+ else if (ISLOWER (*p))\n\
+ loc = &XVECEXP (*loc, 0, *p - 'a');\n\
+ else\n\
+ loc = &XVECEXP (*loc, 0, *p - UPPER_OFFSET);\n\
+ *pp = p + 1;\n\
+ return loc;\n\
+}\n");
puts ("\
void\n\
insn_extract (rtx_insn *insn)\n{\n\
rtx *ro = recog_data.operand;\n\
rtx **ro_loc = recog_data.operand_loc;\n\
- rtx pat = PATTERN (insn);\n\
- int i ATTRIBUTE_UNUSED; /* only for peepholes */\n\
+ int icode = INSN_CODE (insn);\n\
\n\
if (flag_checking)\n\
{\n\
memset (ro, 0xab, sizeof (*ro) * MAX_RECOG_OPERANDS);\n\
memset (ro_loc, 0xab, sizeof (*ro_loc) * MAX_RECOG_OPERANDS);\n\
- }\n");
-
- puts ("\
- switch (INSN_CODE (insn))\n\
+ }\n\
+\n\
+ unsigned int method = (icode >= 0\n\
+ && icode < (int) ARRAY_SIZE (extract_method_of_code)\n\
+ ? extract_method_of_code[icode] : 0);\n\
+ if (method == 0)\n\
{\n\
- default:\n\
/* Control reaches here if insn_extract has been called with an\n\
- unrecognizable insn (code -1), or an insn whose INSN_CODE\n\
- corresponds to a DEFINE_EXPAND in the machine description;\n\
- either way, a bug. */\n\
- if (INSN_CODE (insn) < 0)\n\
- fatal_insn (\"unrecognizable insn:\", insn);\n\
+ unrecognizable insn (code -1), or an insn whose INSN_CODE\n\
+ corresponds to a DEFINE_EXPAND in the machine description;\n\
+ either way, a bug. */\n\
+ if (icode < 0)\n\
+ fatal_insn (\"unrecognizable insn:\", insn);\n\
else\n\
- fatal_insn (\"insn with invalid code number:\", insn);\n");
+ fatal_insn (\"insn with invalid code number:\", insn);\n\
+ }\n\
+\n\
+ if (method == 1)\n\
+ {\n\
+ /* An old-style define_peephole. The vector in the insn was created\n\
+ just for this function and contains nothing but operands. */\n\
+ for (int i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)\n\
+ ro[i] = *(ro_loc[i] = &XVECEXP (PATTERN (insn), 0, i));\n\
+ return;\n\
+ }\n\
+\n\
+ const struct extract_method_d *m = &extract_methods[method];\n\
+ const char *p = extract_paths + m->paths;\n\
+ for (unsigned int i = 0; i < m->n_operands; i++)\n\
+ if (*p == MISSING_OPERAND_CHAR)\n\
+ {\n\
+ ro[i] = const0_rtx;\n\
+ ro_loc[i] = &junk;\n\
+ p += 2;\n\
+ }\n\
+ else\n\
+ {\n\
+ rtx *loc = follow_extract_path (&p, &PATTERN (insn));\n\
+ ro_loc[i] = loc;\n\
+ ro[i] = *loc;\n\
+ }\n\
+ for (unsigned int i = 0; i < m->n_dups; i++)\n\
+ {\n\
+ recog_data.dup_loc[i] = follow_extract_path (&p, &PATTERN (insn));\n\
+ recog_data.dup_num[i] = extract_dup_num[m->dups + i];\n\
+ }\n}");
}
int
main (int argc, const char **argv)
{
- unsigned int i;
- struct extraction *p;
- struct code_ptr *link;
- const char *name;
-
progname = "genextract";
if (!init_rtx_reader_args (argc, argv))
@@ -444,64 +583,7 @@ main (int argc, const char **argv)
return FATAL_EXIT_CODE;
print_header ();
-
- /* Write out code to handle peepholes and the insn_codes that it should
- be called for. */
- if (peepholes)
- {
- for (link = peepholes; link; link = link->next)
- printf (" case %d:\n", link->insn_code);
-
- /* The vector in the insn says how many operands it has.
- And all it contains are operands. In fact, the vector was
- created just for the sake of this function. We need to set the
- location of the operands for sake of simplifications after
- extraction, like eliminating subregs. */
- puts (" for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)\n"
- " ro[i] = *(ro_loc[i] = &XVECEXP (pat, 0, i));\n"
- " break;\n");
- }
-
- /* Write out all the ways to extract insn operands. */
- for (p = extractions; p; p = p->next)
- {
- for (link = p->insns; link; link = link->next)
- {
- i = link->insn_code;
- name = get_insn_name (i);
- if (name)
- printf (" case %d: /* %s */\n", i, name);
- else
- printf (" case %d:\n", i);
- }
-
- for (i = 0; i < p->op_count; i++)
- {
- if (p->oplocs[i] == 0)
- {
- printf (" ro[%d] = const0_rtx;\n", i);
- printf (" ro_loc[%d] = &junk;\n", i);
- }
- else
- {
- printf (" ro[%d] = *(ro_loc[%d] = &", i, i);
- print_path (p->oplocs[i]);
- puts (");");
- }
- }
-
- for (i = 0; i < p->dup_count; i++)
- {
- printf (" recog_data.dup_loc[%d] = &", i);
- print_path (p->duplocs[i]);
- puts (";");
- printf (" recog_data.dup_num[%d] = %d;\n", i, p->dupnums[i]);
- }
-
- puts (" break;\n");
- }
-
- puts (" }\n}");
+ print_extractions ();
fflush (stdout);
return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
}
--
2.50.1 (Apple Git-155)
