https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127758
Bug ID: 127758
Summary: [15 Regression] compile time hog in tree PTA with many
global variables
Product: gcc
Version: 15.1.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: christian.klein at advantest dot com
Target Milestone: ---
Created attachment 65776
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65776&action=edit
Reproducer
Compiling the attached program take ~40x as long on GCC 15.1 or later than on
GCC 14. Compile with `g++ -c -O2 shrinked.c`
(Note that the reproducer has no main(), it's basically just a lot of global
variables).
Compiling with "-ftime-report" shows that tree PTA is at 98%.
Passing "-fno-tree-pta" will bring the compile time back to normal levels.
I bisected this and could trace it to the commit
c08b0d3f7b3539b26031de31d88dea6b94474577 (Commit message at bottom of the bug).
I could reproduce this with GCC 15.x, GCC 16.x and also current master.
An observation that might be interesting is that the `X x;` in the reproducer
is necessary to see the compile time increase. If that line is removed, or if X
does not have the `int i=0` initialised member, the compile time goes back to
normal.
I also dumped the tree pass information using "-fdump-tree-alias-details"
When looking at the points-to sets, the entries for GCC 14 are pretty short:
val0.0+64 = { ESCAPED NONLOCAL }
With GCC 15 and later, each entry contains a list of all other entries, too:
val0.0+64 = { ESCAPED NONLOCAL val0.0+64 val0.64+64 val0.128+64 ...
val250.1216+64 }
So basically there is a quadratic explosion happening here.
We have several files in our code affected by this, some going from a few
seconds compile time with GCC 14 to over half an hour with GCC 15 and later.
Full message of the "problematic" commit:
commit c08b0d3f7b3539b26031de31d88dea6b94474577
Author: Richard Biener <[email protected]>
Date: Mon May 27 10:41:02 2024 +0200
tree-optimization/115236 - more points-to *ANYTHING = x fixes
The stored-to ANYTHING handling has more holes, uncovered by treating
volatile accesses as ANYTHING. We fail to properly build the
pred and succ graphs, in particular we may not elide direct nodes
from receiving from STOREDANYTHING.
PR tree-optimization/115236
* tree-ssa-structalias.cc (build_pred_graph): Properly
handle *ANYTHING = X.
(build_succ_graph): Likewise. Do not elide direct nodes
from receiving from STOREDANYTHING.
* gcc.dg/pr115236.c: New testcase.
