https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114261
Alexander Monakov <amonakov at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |mkuvyrkov at gcc dot gnu.org --- Comment #5 from Alexander Monakov <amonakov at gcc dot gnu.org> --- It appears sched-deps is O(N*M) given N reg_pending_barriers and M distinct pseudos in a region (or even a basic block). For instance, on the following testcase #define x10(x) x x x x x x x x x x #define x100(x) x10(x10(x)) #define x10000(x) x100(x100(x)) void f(int); void g(int *p) { #if 1 x10000(f(*p++);) #else x10000(asm("" :: "r"(*p++));) #endif } gcc -O -fschedule-insns invokes add_dependence 20000 times for each asm/call after the first. There is a loop for (i = 0; i < (unsigned)deps->max_reg; i++) { struct deps_reg *reg_last = &deps->reg_last[i]; reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); SET_REGNO_REG_SET (&deps->reg_last_in_use, i); } that registers the insn with reg_pending_barrier != 0 in reg_last->sets of each pseudo, and then all those reg_last->sets will be inspected on the next reg_pending_barrier insn.