From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
	id 5C37B385843B; Mon, 11 Mar 2024 16:30:31 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5C37B385843B
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1710174631;
	bh=4Wte6lei8SkSbB36FEEDtsQJfTsTc5rQsmCNHqQHAUo=;
	h=From:To:Subject:Date:In-Reply-To:References:From;
	b=ilInYhcnKudOdex8nYYFr5S7ZdOFrEGKNItTubVj7gH0pcZbibTIF4moOvGuHQxvf
	 AMQUc1ti1FHNoK4djQL62G+IY4koDj5YQtkW5RTc6llrZFfWeEBh06pavbz61skR6x
	 Pzc0LY+HFHXW0hYjEup3wWU6EBp0x4QH/ejQh9+g=
From: "amonakov at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/114261] [13/14 Regression] Scheduling takes
 excessive time (97%)
Date: Mon, 11 Mar 2024 16:30:29 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: rtl-optimization
X-Bugzilla-Version: 14.0
X-Bugzilla-Keywords: compile-time-hog
X-Bugzilla-Severity: normal
X-Bugzilla-Who: amonakov at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 13.3
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: cc
Message-ID: <bug-114261-4-N60NZfuxAO@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-114261-4@http.gcc.gnu.org/bugzilla/>
References: <bug-114261-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
List-Id: <gcc-bugs.sourceware.org>

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D114261

Alexander Monakov <amonakov at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mkuvyrkov at gcc dot gnu.o=
rg

--- 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 =3D 0; i < (unsigned)deps->max_reg; i++)
        {
          struct deps_reg *reg_last =3D &deps->reg_last[i];
          reg_last->sets =3D 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 !=3D 0 in reg_last->sets o=
f each
pseudo, and then all those reg_last->sets will be inspected on the next
reg_pending_barrier insn.=