[Bug ipa/106158] New: IPA SRA ssa_name_only_returned_p is quadratic

[rguenth at gcc dot gnu.org]

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.