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 745BC384CBB3; Wed, 17 Jan 2024 07:48:21 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 745BC384CBB3
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1705477701;
	bh=Fpgf/is6KD3a+6o0SlubMXzfmHshmcPkEhAz84NrE/g=;
	h=From:To:Subject:Date:In-Reply-To:References:From;
	b=U1mKm3rkf4C3hPnthMBzBYDrkySm9d675GWLmtp+ytAvhorIlGkV3l15YdLGKB3X3
	 mWColL38EyNnVuY7wJ3z8NxUsGUOqzCOUX5D076srZdQYaWr9GW4PgWQp9s8thKi4Y
	 rVuDFstuscDAIcZRmWznuL757SsCl6jkL7tz5wX4=
From: "cvs-commit at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/96388] scheduling takes forever with -fPIC
Date: Wed, 17 Jan 2024 07:48:20 +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: 11.0
X-Bugzilla-Keywords: compile-time-hog, memory-hog, needs-reduction
X-Bugzilla-Severity: normal
X-Bugzilla-Who: cvs-commit at gcc dot gnu.org
X-Bugzilla-Status: ASSIGNED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: mkuvyrkov at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: 
Message-ID: <bug-96388-4-eVhit01FSl@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-96388-4@http.gcc.gnu.org/bugzilla/>
References: <bug-96388-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=3D96388

--- Comment #17 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Maxim Kuvyrkov <mkuvyrkov@gcc.gnu.org=
>:

https://gcc.gnu.org/g:0c42d1782e48d8ad578ace2065cce9b3615f97c0

commit r14-8174-g0c42d1782e48d8ad578ace2065cce9b3615f97c0
Author: Maxim Kuvyrkov <maxim.kuvyrkov@linaro.org>
Date:   Sun Nov 19 08:43:05 2023 +0000

    sched-deps.cc (find_modifiable_mems): Avoid exponential behavior [PR963=
88]

    This patch avoids sched-deps.cc:find_inc() creating exponential number
    of dependencies, which become memory and compilation time hogs.
    Consider example (simplified from PR96388) ...
    =3D=3D=3D
    sp=3Dsp-4 // sp_insnA
    mem_insnA1[sp+A1]
    ...
    mem_insnAN[sp+AN]
    sp=3Dsp-4 // sp_insnB
    mem_insnB1[sp+B1]
    ...
    mem_insnBM[sp+BM]
    =3D=3D=3D

    [For simplicity, let's assume find_inc(backwards=3D=3Dtrue)].
    In this example find_modifiable_mems() will arrange for mem_insnA*
    to be able to pass sp_insnA, and, while doing this, will create
    dependencies between all mem_insnA*s and sp_insnB -- because sp_insnB
    is a consumer of sp_insnA.  After this sp_insnB will have N new
    backward dependencies.
    Then find_modifiable_mems() gets to mem_insnB*s and starts to create
    N new dependencies for _every_ mem_insnB*.  This gets us N*M new
    dependencies.

    In PR96833's testcase N and M are 10k-15k, which causes RAM usage of
    30GB and compilation time of 30 minutes, with sched2 accounting for
    95% of both metrics.  After this patch the RAM usage is down to 1GB
    and compilation time is down to 3-4 minutes, with sched2 no longer
    standing out on -ftime-report or memory usage.

    gcc/ChangeLog:

            PR rtl-optimization/96388
            PR rtl-optimization/111554
            * sched-deps.cc (find_inc): Avoid exponential behavior.=