https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96388
--- Comment #17 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Maxim Kuvyrkov <mkuvyr...@gcc.gnu.org>: https://gcc.gnu.org/g:0c42d1782e48d8ad578ace2065cce9b3615f97c0 commit r14-8174-g0c42d1782e48d8ad578ace2065cce9b3615f97c0 Author: Maxim Kuvyrkov <maxim.kuvyr...@linaro.org> Date: Sun Nov 19 08:43:05 2023 +0000 sched-deps.cc (find_modifiable_mems): Avoid exponential behavior [PR96388] 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) ... === sp=sp-4 // sp_insnA mem_insnA1[sp+A1] ... mem_insnAN[sp+AN] sp=sp-4 // sp_insnB mem_insnB1[sp+B1] ... mem_insnBM[sp+BM] === [For simplicity, let's assume find_inc(backwards==true)]. 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.
