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

    <tr>
        <th>Summary</th>
        <td>
            [C++20] Unintuitive compile times when caching the result of constexpr/consteval in modules
        </td>
    </tr>

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

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

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

<pre>
    This may or may not be related to #61425.
I have some meta-programming facilities that do the following: A templated constexpr variable calls a yet to be defined function via ADL and caches the result. In separate modules, these functions are defined for 1 concrete argument. There is a second templated argument which can change how the result is computed from previous results. These functions may depend on the result of other computations. In each module, the result for the Default Strategy is pre-computed. To illustrate this, I've substituted it with the fibonacci sequence, going from 30 to 32 to get noticable compile times.

### Cache.cppm:
```
export module Fibonacci.Cache;

export namespace Fibonacci
{
        constexpr unsigned long Recursive(unsigned long n)
        {
                if (n == 0)
                        return 0;
                if (n == 1)
                        return 1;
                return Recursive(n - 2) + Recursive(n - 1);
        }

        template<unsigned long N>
        struct Number{};

        struct DefaultStrategy
        {
                constexpr unsigned long operator()(unsigned long n, auto... other) const
                {
                        return (n + ... + other);
                }
        };

        template<unsigned long N, typename Strategy = DefaultStrategy>
        constexpr unsigned long Cache = Compute(Number<N>{}, Strategy{});
}
```
### Fib0.cppm:
```
export module Fibonacci.Fib0;

export import Fibonacci.Cache;

export namespace Fibonacci
{
        constexpr unsigned long Compute(Number<30ul>, auto strategy)
        {
                return strategy(Recursive(30ul));
        }

        template constexpr unsigned long Cache<30ul>;
}
```
### Fib1.cppm:
```
export module Fibonacci.Fib1;

export import Fibonacci.Cache;

export namespace Fibonacci
{
        constexpr unsigned long Compute(Number<31ul>, auto strategy)
        {
                return strategy(Recursive(31ul));
        }

        template constexpr unsigned long Cache<31ul>;
}
```
### Fib2.cppm:
```
export module Fibonacci.Fib2;

export import Fibonacci.Fib0;
export import Fibonacci.Fib1;

export namespace Fibonacci
{
        constexpr unsigned long Compute(Number<32ul>, auto strategy)
        {
                return strategy(Cache<30ul>, Cache<31ul>);
        }

        template constexpr unsigned long Cache<32ul>;
}
```
### Main.cpp:
```
import Fibonacci.Fib2;

int main()
{
        return Fibonacci::Cache<32ul> > (1ul << 32ul);
}
```
Compiled with the following commands on a recent Clang 17 build:
```
time clang++ -std=c++20 Cache.cppm --precompile -o Cache.pcm -ftime-trace\
&& time clang++ -std=c++20 -c Cache.pcm\
&& time clang++ -std=c++20 Fib0.cppm --precompile -o Fib0.pcm -fmodule-file=Fibonacci.Cache=Cache.pcm -fconstexpr-steps=4294967295 -ftime-trace\
&& time clang++ -std=c++20 -c Fib0.pcm\
&& time clang++ -std=c++20 Fib1.cppm --precompile -o Fib1.pcm -fmodule-file=Fibonacci.Cache=Cache.pcm -fconstexpr-steps=4294967295 -ftime-trace\
&& time clang++ -std=c++20 -c Fib1.pcm\
&& time clang++ -std=c++20 Fib2.cppm --precompile -o Fib2.pcm -fmodule-file=Fibonacci.Fib0=Fib0.pcm -fmodule-file=Fibonacci.Fib1=Fib1.pcm -fconstexpr-steps=4294967295 -ftime-trace\
&& time clang++ -std=c++20 -c Fib2.pcm\
&& time clang++ -std=c++20 -c Main.cpp -fmodule-file=Fibonacci.Fib2=Fib2.pcm -fconstexpr-steps=4294967295 -ftime-trace\
&& time clang++ -std=c++20 Main.o Cache.o Fib0.o Fib1.o Fib2.o
```

Now what I would expect is that in Fib0 the cache for 30 gets computed and in Fib1 the cache for 31 gets computed, each using the default strategy. The results get re-used in Fib2 and the result of Fib2 gets re-used in Main. What ends up happening is that in Fib2 both the cache for 30 and 31 are computed once again and in Main, the result of Fib2 gets re-computed once again.

### Case 1: All constexpr
Fib0: 4.6 sec
Fib1: 7.3 sec
Fib2: 11.8 sec
Main: 11.9 sec

However, if we substitute some `consteval` for `constexpr` it gets more unintuitive:

### Case 2: Making Recursive consteval
Fib0: 9.2 sec
Fib1: 14.7 sec
Fib2: 0.02 sec
Main: 0.02 sec

### Case 3: Making DefaultStrategy::operator() consteval:
Fib0: 4.6 sec
Fib1: 7.4 sec
Fib2: 0.02 sec
Main: 0.02 sec
(This is what I expected in every case)

### Case 4: Making Recursive and DefaultStrategy::operator() consteval
Fib0: 9.2 sec
Fib1: 14.9 sec
Fib2: 0.02 sec
Main: 0.02 sec

### Case 5: Making each Compute consteval
Fib0: 9.1 sec
Fib1: 14.5 sec
Fib2: 0.02 sec
Main: 0.02 sec

### Case 6: Making Recursive and each Compute consteval
Fib0: 9.2 sec
Fib1: 14.6 sec
Fib2: 0.02 sec
Main: 0.02 sec

### Case 7: Making DefaultStrategy::operator() and each Compute consteval
Fib0: 9.1 sec
Fib1: 14.8 sec
Fib2: 0.02 sec
Main: 0.02 sec

### Case 8: Making all consteval
Fib0: 9.0 sec
Fib1: 14.8 sec
Fib2: 0.02 sec
Main: 0.02 sec

What makes this so confusing is that replacing constexpr with consteval can be EITHER an optimization OR a pessimization, and I cannot derive a good rule from this. Ideally, I would like all cases to behave like Case 3, which has by far the lowest compilation time. If for some reason, the above behaviour is working as intended, I would appreciate some guiding rules when consteval is beneficial or detrimental to compile times.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMWV2P4yoS_TXkpRTLxvnyQx4yyW3dlnZmpdlZ7TPG5ZgdDF7Anen99SuwndjdyUx3b0a6Unei4ALOqUNBFWbWiqNC3JLlJ7I8zFjrKm2235moS8PELNfF8_ZbJSzU7Bm0CV9KO8gRDErmsACngdB0lSzoMiLxgcS7R6jYE4LVNUKNjs0bo4-G1bVQRygZF1I4gRZcxRwUGlyFUGop9UmoI0l3sAOHddMNz7WyDn80Bp6YESyXCJxJaYHBMzo_e45QYCkUFlC2ijuhFTwJBrvD34CpAjjjVZjNY7atdBE8KrDYMMMcQq2LVqIldO9NLJ4HscDMaGhtIPFouEGHwMyxrVG5CL5VaBCEB2SRa1WMwA9WcKoEr4AzBbxi6ohQ6dMIke_Odd20vlNpdA2NwSehW9sb2DDPBJyXosAGVQFajcfSJWhXoelHZME8cEbGq55vT3fo49n5nwcsmf_9D-d9c3z2wBqD8wFcBN80CClbGwzAVSJ47pHQtZe8za0TLtAQDk7CVZ26IteKcS7A4n9aVDzMf9RhQXi6aeyVTKn_PKLza0zwTmxdN0IiOFGj7RdY_0nT7g_2XuGIN01N0uHhKu7_wk_80Wjjeu7wMMCJQk-SfhqP29sqVqNtGB-Z91brs3l2WZ2tCqFUgNTqCF-Rt8aKJyR0M32iCM3O3cdDkTgTJRC6UUDSA0kPEE9Mw59B1xoF8QjylY7JzY7Ji4598xiugjlQQjMg9NOrB2Hk8RDrw0SSOBsWP0n3U-JfSPrH2co603IHX9o6R-O9sD68UOFi1K_JYUnect4tKXSDhjltCN148Ff02ANrnY6iqIsbzz0MNnHhdLKL6zq_00_g-_vvYYwXnh55KrvK9ieO87H63KBfkZfI9EK_dM3Iw7fcEVZ86LzvYprQTS9Dug8adWrQ_XmqoWVE6UxmGmaXkHwQefyhiPQdrwekqMPX7w_eK45J41Z63_RrBezgmtvB3K-Pi-VmHExhQL8c3xhO8FM9RwjfJVHyUYmSv6BEyb0lSu4tUfIBiehHJaJvlGgScD8xuiH53WWkd5DxZVDQ_SsR7qcqfa-qn5lQXtVbol7z_ks1hXJQM6H6U-2Vx3ufXDRJdyTdvcAM4Z9uklYCSfck3UN48oadft-lZcUoxxsyeJ-y1UwV1uelDAxynwHvJVNHSNaQt0IWt6j7LA-4NyX0kz9N59YVJD3w7ieNR7kezOeNwSE_nOv-UcNrmJd-oLkzjCNZ7gcBVoSu4NdTzPllqPf3Pp98r_CFJx28LmDnpZBI0sOr_fIwpnJegHPrsLEkPSxotshWa5ot_3-mA6gPEU1uEk3-ikSTDxOlN4nSXxDtttfDG7Tv9tjDyHm_3SH0Yw6Z8_Me9nM-tGugv59PwDNsAX2o9Quxl0lf35XD5xd9glPFHDzCSbeyAPzRIA9lebikEGEnjcM-F64TQsGcxr5WHVXuTBW9afLSNJma-hMpVOOt9TumNy760ns4xkLFP5T_oSg2OG8tDlPQMN207g_NYaKRbXAN_MvzQL8rtw1UrGlQ-ZmnDCnkut_OJzT9TGkS7kPOZLXiCOzIhBp4fw7n0f5nmK70vlnTW_Tl6g52Ul4O4c6sC6odLKIVWOTnxmC_jtJJI_WNSRJtLq0BadeaXVq7zz_1CZ98BbcHUcJpfKnRXWmRVdzBeWKSrOLgo3Obh7iKQbiOcq0NQquEcq1wPq08n3vX6Aakn9l3Mb5BgMtkE-5ZRF9zTxbR-jX5OIrpa_LT1quA0hGgV7WmTyimxfUI6sDzF0otPgiWbsKtpLBD2HYB2y14L98zcGZxlDReYbe46m6_mN_H9U2yZHeUZTkCHnaRPo--jSm5iml5R0yrm858G8LrXlvdEeH6nYv57dive3dzR-ybEXZ23g-vQInvDyWcHDX7Hu7QhQWr_fRld3IN54fBRjLeZf9DvRRKgzPScPudI_zx-O3PP74CU6AbJ2rx33BBDX__CgwatPbcFEpAVcCj76m0gwJNWFNw1LoA4yvecHnsUUXwWCCT8jncRvenuBTfsXMXsx69hhzDq4nwoN_h6L6_na-YhfwZStZdhUt9Quv6--cOo09DIngsw5YfzgKDzOrzocdy_YTdHEK3JmxP2nSiWRDKoSq6s39AyBqfUAo2nC3HVhTe3JPzexuqkQOFhRwVloILJkEbKNAZUaNyTHpy06vyWbFNiyzN2Ay3yWqzWCSL1SabVdsFK7NssVlukmSZrLBYcM7isowxThY8zvlMbGlM03iZbBK63MRZlC-y9TLJl2se82K9ScgixpoJGUn5VEfaHGfC2ha3K7rOVjPJcpQ2vFKiVOEJwkNCKVkeZmbr-8zz9mjJIpbCOnsZxQknw7uo_ZDXkeUB_nk5PqcUe_8wXg051CXruJzG9GHkQTW87pm1Rm4r53wWuiP0gdCHo3BVm0dc14Q-eEz917wx-t_IHaEPgYkl9CEw_V8AAAD__6vBQlc">