[Bug rtl-optimization/124165] New: [16 Regression] Many std::map -> long compilation time at -O0 (late_pro_and_epilogue pass involved)

[pheeck at gcc dot gnu.org via Gcc-bugs]

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

            Bug ID: 124165
           Summary: [16 Regression] Many std::map<string, string> -> long
                    compilation time at -O0 (late_pro_and_epilogue pass
                    involved)
           Product: gcc
           Version: 16.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog, needs-bisection
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pheeck at gcc dot gnu.org
  Target Milestone: ---
              Host: x86_64-linux
            Target: x86_64-linux

Use Python to generate the testcase:

```
TESTCASE_SIZE = 5000

print("""
#include <map>
#include <string>
using namespace std;
class C
{
  C();
""")

for i in range(TESTCASE_SIZE):
    print(f"map<string,string> A{i};")

print("""
};
C::C()
{
""")

for i in range(TESTCASE_SIZE):
    # Generate some pseudorandom strings
    str1 = str((i * 500) % 10000)
    str2 = str((i * i) % 10000)
    print(f'A{i}["{str1}"] = "{str2}";')

print("}")
```

It will generate something like this:

```
#include <map>
#include <string>
using namespace std;
class C
{
  C();

map<string,string> A0;
map<string,string> A1;
map<string,string> A2;
map<string,string> A3;
map<string,string> A4;
map<string,string> A5;
map<string,string> A6;
map<string,string> A7;
...
};

C::C()
{

A0["0"] = "0";
A1["500"] = "1";
A2["1000"] = "4";
A3["1500"] = "9";
A4["2000"] = "16";
A5["2500"] = "25";
A6["3000"] = "36";
A7["3500"] = "49";
A8["4000"] = "64";
A9["4500"] = "81";
...
}
```

Compile the testcase with trunk GCC and GCC 15.1.1 at -O0 (configured with
--enable-checking=release).  Doing -ftime-report shows that trunk takes a lot
longer to compile:

```
trunk:
 thread pro- & epilogue             :  42.13 ( 91%)   234k (  0%)
 TOTAL                              :  46.15          435M

gcc15:
 TOTAL                              :   3.77          422M
```

gcc15 doesn't even list 'thread pro- & epilogue' in the time report.  So I
assume that the late_pro_and_epilogue pass is responsible for this slowdown.


There is probably some quadratic algorithm in late_pro_and_epilogue.  When I
run the testcase with half the size (TESTCASE_SIZE = 2500), I don't get half
the compile time.  I get this:

```
 thread pro- & epilogue             :   8.64 ( 84%)   234k (  0%)
 TOTAL                              :  10.33          252M
```

I have also tried TESTCASE_SIZE = 10000 but that didn't finish in 4 minutes so
I killed the process.


I originally found the slowness by running the testcase for pr12392.