[Bug tree-optimization/108653] New: SRA compile-time hog with large copy chain

[Bug tree-optimization/108653] New: SRA compile-time hog with large copy chain

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108653

            Bug ID: 108653
           Summary: SRA compile-time hog with large copy chain
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
  Target Milestone: ---

PR108500 shows that propagate_all_subaccesses is quadratic in the length of a
copy chain.  A simplified testcase looks like the following where adding
'THOUSAND's will increase the number of items worked on in its processing loop
quadratically.

struct s2 {
   int id;
   char a[20];
};
static inline  __attribute__((always_inline)) struct s2
f(struct s2 s)
{
  return s;
}

volatile struct s2 x;
int main(void)
{
  struct s2 s2 = {0};
#define TEN \
  s2 = f(s2); \
  s2 = f(s2); \
  s2 = f(s2); \
  s2 = f(s2); \
  s2 = f(s2); \
  s2 = f(s2); \
  s2 = f(s2); \
  s2 = f(s2); \
  s2 = f(s2); \
  s2 = f(s2);
#define HUNDRED TEN TEN TEN TEN TEN TEN TEN TEN TEN TEN
#define THOUSAND HUNDRED HUNDRED HUNDRED HUNDRED HUNDRED HUNDRED HUNDRED
HUNDRED HUNDRED HUNDRED
  THOUSAND THOUSAND
  return 0;
}

with a dev build this shows

 tree SRA                           :   0.52 ( 66%)   0.00 (  0%)   0.53 ( 66%)
    0  (  0%)