https://gcc.gnu.org/g:789de024dc88bf0d2870de680d63cd333b5ba67e
commit r17-5253-g789de024dc88bf0d2870de680d63cd333b5ba67e Author: Kyrylo Tkachov <[email protected]> Date: Tue Oct 13 17:59:16 2026 +0200 genattrtab: remove insn entries in constant time remove_insn_ent searches the list of insns of an attribute value for the predecessor of the entry that it removes. The default values of attributes such as the DFA attributes have most insns in their lists, and optimize_attrs removes one entry for each insn whose value it makes more specific, so the total cost is quadratic in the number of insns. After the previous patch this search is the largest part of the genattrtab run for aarch64 and riscv64. Add a link to the previous entry, so that removal does not search. The order of each list does not change. The generated files do not change for 52 target configurations. genattrtab instructions, with genattrtab built at -O2, relative to the previous patch: riscv64 -21.2%, aarch64 -12.8%, x86_64 -4.0%. Built at -g without optimization, aarch64 -10.3%. Over the four patches, genattrtab built as in stage 1 executes 94.5% fewer instructions for aarch64, and at -O2 between 65.5% (x86_64) and 94.4% (s390x) fewer. gcc/ChangeLog: * genattrtab.cc (struct insn_ent): Add prev. (remove_insn_ent): Use it instead of a search of the list. (insert_insn_ent): Set it. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/genattrtab.cc | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) diff --git a/gcc/genattrtab.cc b/gcc/genattrtab.cc index e1afe09c9ebb..67a72e8f4e61 100644 --- a/gcc/genattrtab.cc +++ b/gcc/genattrtab.cc @@ -152,6 +152,7 @@ public: struct insn_ent { struct insn_ent *next; /* Next in chain. */ + struct insn_ent *prev; /* Previous in chain, or null if first. */ class insn_def *def; /* Instruction definition. */ }; @@ -1794,16 +1795,16 @@ simplify_cond (rtx exp, int insn_code, int insn_index) static void remove_insn_ent (struct attr_value *av, struct insn_ent *ie) { - struct insn_ent *previe; - - if (av->first_insn == ie) - av->first_insn = ie->next; + gcc_checking_assert (!ie->prev || ie->prev->next == ie); + if (ie->prev) + ie->prev->next = ie->next; else { - for (previe = av->first_insn; previe->next != ie; previe = previe->next) - ; - previe->next = ie->next; + gcc_checking_assert (av->first_insn == ie); + av->first_insn = ie->next; } + if (ie->next) + ie->next->prev = ie->prev; av->num_insns--; if (ie->def->insn_code == -1) @@ -1817,7 +1818,10 @@ remove_insn_ent (struct attr_value *av, struct insn_ent *ie) static void insert_insn_ent (struct attr_value *av, struct insn_ent *ie) { + ie->prev = NULL; ie->next = av->first_insn; + if (ie->next) + ie->next->prev = ie; av->first_insn = ie; av->num_insns++; if (ie->def->insn_code == -1)
