https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106158
Bug ID: 106158
Summary: IPA SRA ssa_name_only_returned_p is quadratic
Product: gcc
Version: 13.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: ipa
Assignee: unassigned at gcc dot gnu.org
Reporter: rguenth at gcc dot gnu.org
CC: marxin at gcc dot gnu.org
Target Milestone: ---
If you take a function like
unsigned bar (int);
unsigned foo (int flag)
{
unsigned val = 0;
#define DOIT \
for (int i = 0; i < 2048; ++i) \
if (flag) \
val ^= bar (i);
#define DOIT10 DOIT DOIT DOIT DOIT DOIT DOIT DOIT DOIT DOIT DOIT
#define DOIT100 DOIT10 DOIT10 DOIT10 DOIT10 DOIT10 DOIT10 DOIT10 DOIT10 DOIT10
DOIT10
#define DOIT1000 DOIT100 DOIT100 DOIT100 DOIT100 DOIT100 DOIT100 DOIT100
DOIT100 DOIT100 DOIT100
#define DOIT10000 DOIT1000 DOIT1000 DOIT1000 DOIT1000 DOIT1000 DOIT1000
DOIT1000 DOIT1000 DOIT1000 DOIT1000
DOIT1000
DOIT1000
DOIT1000
DOIT1000
return val;
}
then you'll see that ssa_name_only_returned_p is eventually called for each
return value of bar () but they are chained together via the ^= stmts.
While there's a bitmap to avoid exponential behavior the actual result
is not cached nor used across different SSA name def chain analyses.
It might be cheaper to walk use->def links from all return stmts somehow
but caching would also fix this particular case.
