<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/123649>123649</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Poor performance for Romberg's method
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          thesamesam
      </td>
    </tr>
</table>

<pre>
    This is a companion bug of a GCC bug I've just filed (https://gcc.gnu.org/PR118570).

This was reported on IRC by `trn` who observed that with GCC, this testcase completes much quicker at -O2 than at -O3. For Clang, it always has the bad-case performance that we currently see with GCC -O3.

```c
#include <stdio.h>
#include <math.h>

#define MAX_STEPS 10
#define I_OP sin

static double
romberg(a, b, acc)
double a;
double b;
double acc;
{
  long i, j, k, ep;
  double R1[MAX_STEPS], R2[MAX_STEPS];
  double *Rp = &R1[0], *Rc = &R2[0];
  double h = b - a;
  double c, n_k;
  double *rt;
  Rp[0] = (I_OP(a) + I_OP(b)) * h * 0.5;

  for (i = 1; i < MAX_STEPS; ++i) {
      h = h / 2.0;
      c = 0;
      ep = 1 << (i - 1);

      for (j = 1; j <= ep; ++j)
        c = c + I_OP(a + (2 * j - 1) * h);

      Rc[0] = h * c + 0.5 * Rp[0];

      for (j = 1; j <= i; ++j) {
        n_k = 1;
        for (k = 0; k < j; ++k)
          n_k *= 4;
        Rc[j] = (n_k * Rc[j - 1] - Rp[j - 1]) / (n_k - 1);
      }

      if (i > 1 && fabs(Rp[i - 1] - Rc[i]) < acc)
        return Rc[i];

      rt = Rp;
      Rp = Rc;
      Rc = rt;
  }

  return Rp[MAX_STEPS - 1];
}

int
main()
{
  double a = 0.0;
  double b = 3.14159265358979323846264338327950288419716939937510;
  double c = 2.71828182845904523536028747135266249775724709369995;
  double acc = 1e-6;
  long l;
  double x = 0.001;

  for (l = 0; l <= 2500000; l++)
    x = x + romberg(a, b, acc) * romberg(a, c, acc);
  printf("%.15lf\n", x);

  return 0;
}
```

```
$ clang -O2 rom3.c -o rom3 -lm && time ./rom3
rom3.c:33:1: warning: a function definition without a prototype is deprecated in all versions of C and is not supported in C23 [-Wdeprecated-non-prototype]
   33 | romberg(a, b, acc)
      | ^
1 warning generated.
9558673.398323269560933

real    0m2.550s
user    0m2.508s
sys     0m0.014s

$ clang -O3 rom3.c -o rom3 -lm && time ./rom3
rom3.c:33:1: warning: a function definition without a prototype is deprecated in all versions of C and is not supported in C23 [-Wdeprecated-non-prototype]
   33 | romberg(a, b, acc)
      | ^
1 warning generated.
9558673.398323269560933

real    0m2.499s
user    0m2.461s
sys     0m0.015s

$ gcc -O2 rom3.c -o rom3 -lm && time ./rom3
rom3.c: In function ‘romberg’:
rom3.c:33:1: warning: old-style function definition [-Wold-style-definition]
   33 | romberg(a, b, acc)
      | ^~~~~~~
9558673.398323269560933

real    0m0.018s
user    0m0.003s
sys     0m0.014s
```
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzsV81u4zYQfhr6MrBAkaIkHnywnbjIodjAu0B7W1AUbdGRKVekks2lz16QkmzJ6baLRY8VYoWcGX4z8w3_JKzVR6PUCrENYg8L0bmqaVeuUlac_W9RNOX76kulLWgLAmRzvgijGwNFd4TmAAJ-2W5D5wmR7FXBqbMODrpWJSCSV85dLKJrRHaI7I5SRkfTRU17RGT3vI_jnGUYER4hvEZ4Hfy8CQutujStUyU0Bp72WyjeAaXYtQalGN6qBprCqvZVleAq4eBNu8rHgcgWnMdwyjoprArx1sopC-dOVvBHp-WLakE4WH4ifrDp2zSCXdPCthbm6FG0A1G_iXcLlbDgKgWFKJcB8qLaQ9OehZFq8K5Adm2rjKvfwSp1DSfg9pmhFPd_0ncI1UbWXakA0a11pW6iCtHHD6qzcNVVE5SlOmij4Nf1718_f3l8_gwxnimevn56BqtNP8A64bSEsumKWiG8bptzoTz3ufBJFv4lpESEI7zurUAgurn1ilnP24Y-yvwboG7MEbSHOfnXi3-pS28Dg1_Yx4htrhEj9uCt9uReOB-EyHp_AUQfAJE0IOBhpNfIq4aMmvnwKhgUsBzzuWqkxzBfXz76a90o218G1MFN7mntWeOAyAaGfuGZC6K190jWgCM2MORxDk3rR-sAEyO6Ad_c3srnRYhsENnogDPQ6p8-A4-6AxLhMTT_9NnPRKrnKvbw3kPwuoTYB3iLxz9DTKdbTKd-0ENfuSGeUz8pAKYu5TR5ETqI5CRkfhrc9WR89LuXU057tno8HLHQu7L-4xHrecAzAsFX-TpmIh7wXq4swkuoyukG9jLPfoAiaz8imaOFvE6TuTKYDorACnuAZZ_e2O-J2o3200r1sCh7mHKgD-NEevRFJikiKRxEYRHJA7CeOPKO9eiETpb4GHOrXNeaieGc8NaFXPaXaUDDatzLmbCfF7eVMwl7dHKZLvQx_WEXGYy1cQivz0IbRPI-1LGS487TF-u2Dsb9KchpFCcx4yRllOU845TQPElJmlCaU5JxhkmeJzHP4pRTzmnG4nugPhESZXFOcv9LGMcJI5TRFJM8S7KYMpKmJOFZxjKSZJjTlHPO7oCE7KFitUxHVdgm6zvDb2NKOP64ZdS3yVmPk50w7J8g66fprao92Lewnr6_y4d5eaeWk0NgCPDSauMOoRQEERbFrD4gtjWhu4Vv88U91BnPajoed3enXzirEpD-mA0ncNucaSRh2YQWLOvzOLmdPiuIENl5RX920UgiuqYU0XWM6BreRGu0OfqmgENnpPMXk3AS6tD0B3HTORBwaRvXuPeL8teYUl1aJYW_X2gDoq7hVbVWN8b6G80WhCm9mWkc2O4y3ES0gS2hgNhm-dsNYGkas7yC-5kd6kEpoGz7D5WYrPMtIOYP-HjMB47KqNaj-8sDZyxPMxpRnlNCScpZijmlPbGtErVHwWcSMYYtwuvOqvYqwrkX2XcLvQhHOE7seJu4FYL-X4j_rhAJ5_eFSNL4YyHYpBBHKX92PcCTuXGOHgnKMeL5mPHQ5_4O_m-1a-pyad17rf62hoHwq8nypvl5sv8Mz49z61nL59z6_ZN-b5KP286iXNGSUy4WahVnNKOcpgldVKtU5ZgVSVJQUoosyxQXGEtV5AXOD6koF3pFMGE4JjjOCE5opEjBVcpSnit-kEmBEqzOQtdRXb-e_YfNQlvbqVVMaJrwRS0KVdvweUWIUW8QtH4jZQ-LduUHLYvuaFGCa22dvcE47Wq1em6advbF4c-H_UhwZuGsXNWUi66tV3ffWtpVXRHJ5ozIzqMO__wiOSnpENmFWCwiuyHY1xX5KwAA___YRc4A">