[Bug rtl-optimization/114261] [13/14 Regression] Scheduling takes excessive time (97%)

["amonakov at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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.