Polynomial compile-time with heavily inlined templates

Polynomial compile-time growth caused by direct templated call shape, avoided by non-inlined lambda wrapper

### LLVM Version
Observed with:
- Clang 20.1.3 / Clang 20.1.8 / Clang 22.1.4
- `-O3 -std=c++20`

### Summary
Compile time grows polynomially when a recursively expanded templated function directly calls a callable object (`function[index]`), but stays nearly constant when the same call is routed through a lambda wrapper.

Marking the lambda as always_inline brings back the polynomial compile-time behavior.

The issue appears to depend strongly on inlining.

### Godbolt Reproduction
Compile times are easily measured locally, but on [Compiler Explorer](http://godbolt.org/) it's easier to observe the (closely correlated) difference in size of IR, using:

```
-O3 -std=c++20 -DMWE_REPEAT_STEPS=20 -ftime-trace
-O3 -DUSE_LAMBDA_WRAPPER -std=c++20 -DMWE_REPEAT_STEPS=20 -ftime-trace
-O3 -DUSE_LAMBDA_WRAPPER_ALWAYS_INLINE -std=c++20 -DMWE_REPEAT_STEPS=20 -ftime-trace
```
Compiler Explorer link:
[[Compiler Explorer - C++](https://godbolt.org/z/7qnocsG57) ]

`-ftime-trace` shows that:
- the direct-call version spends dramatically more time in optimization passes,
- the non-inlined lambda wrapper avoids the pathological growth almost entirely,
- forcing the lambda to inline restores the compile-time explosion.

### Reproducer

```
#ifndef NDEBUG
#include
#endif
#ifndef MWE_REPEAT_STEPS
#define MWE_REPEAT_STEPS 12
#endif
#ifndef MWE_EXPR_DEPTH
#define MWE_EXPR_DEPTH 10
#endif
namespace mwe
{
constexpr double kInitialSample = 1.0;
template
struct BinaryExpression
{
inline __attribute__((always_inline)) static double eval(double value)
{
double const left = BinaryExpression::eval(value + 0.125);
double const right = BinaryExpression::eval(value * 0.5 + 0.25);
return left * 0.625 + right * 0.375 + value * 0.03125;
}
};
template <>
struct BinaryExpression<1>
{
inline __attribute__((always_inline)) static double eval(double value)
{
return value * 0.75 + 0.125;
}
};
template <>
struct BinaryExpression<0>
{
inline __attribute__((always_inline)) static double eval(double value)
{
return value * 0.5 + 0.25;
}
};
struct ExpressionAtIndex
{
double const &value;
int index;
inline __attribute__((always_inline)) double operator()(int branch) const
{
double const seed = value * 1.011
+ static_cast(index + branch) * 1e-3;
double const left = BinaryExpression::eval(seed);
double const right = BinaryExpression::eval(seed + 0.5);
return left / (1.0 + right * right * 1e-3) + right * 0.25;
}
};
struct ScoreFunction
{
double const &value;
inline __attribute__((always_inline)) double operator[](int index) const
{
ExpressionAtIndex expression{value, index};
double const left = expression(0);
double const right = expression(1);
return left / (1.0 + right * right * 1e-3) + right * 0.25 - 1.0;
}
};
template
inline __attribute__((always_inline)) void runDirectSteps(Function const &function,
double ¤tValue,
int index,
double targetValue,
double &score)
{
currentValue += 0.25 * (targetValue - currentValue);
double const currentScore = function[index];
score = 0.5 * score + 0.5 * currentScore;
if constexpr (RemainingSteps > 1)
{
runDirectSteps(function, currentValue, index, targetValue, score);
}
}
template
inline __attribute__((always_inline)) void runLambdaSteps(GetScore const &getScore,
double ¤tValue,
int index,
double targetValue,
double &score)
{
currentValue += 0.25 * (targetValue - currentValue);
double const currentScore = getScore(currentValue);
score = 0.5 * score + 0.5 * currentScore;
if constexpr (RemainingSteps > 1)
{
runLambdaSteps(getScore, currentValue, index, targetValue, score);
}
}
template
double evaluateDirect(Function const &function, double &value, int index)
{
value = kInitialSample;
double score = 10;
runDirectSteps(function, value, index, 1.8, score);
return score;
}
template
double evaluateLambda(Function const &function, double &value, int index)
{
auto getScore = [&value, &function, &index](double nextValue) -> double {
value = nextValue;
return function[index];
};
value = kInitialSample;
double score = 10;
runLambdaSteps(getScore, value, index, 1.8, score);
return score;
}
template
double evaluateLambdaAlwaysInline(Function const &function, double &value, int index)
{
auto getScore = [&value, &function, &index](double nextValue)
__attribute__((always_inline)) -> double {
value = nextValue;
return function[index];
};
value = kInitialSample;
double score = 10;
runLambdaSteps(getScore, value, index, 1.8, score);
return score;
}
}
int main()
{
double value = 1.0;
mwe::ScoreFunction function{value};
#if defined(USE_LAMBDA_WRAPPER_ALWAYS_INLINE)
double const sum = mwe::evaluateLambdaAlwaysInline(function, value, 0);
#elif defined(USE_LAMBDA_WRAPPER)
double const sum = mwe::evaluateLambda(function, value, 0);
#else
double const sum = mwe::evaluateDirect(function, value, 0);
#endif
#ifndef NDEBUG
std::cout << sum << '\n';
#endif
return static_cast(sum);
}
```

### Commands
Direct version:
```
TIMEFORMAT='Direct %3R s'
time clang++ -O3 -std=c++20 \
-DMWE_REPEAT_STEPS=N \
DirectVsLambdaCallShapeCompileTimeMwe.cpp -o t.o
```
Lambda version:
```
TIMEFORMAT='Lambda %3R s'
time clang++ -O3 -std=c++20 \
-DUSE_LAMBDA_WRAPPER \
-DMWE_REPEAT_STEPS=N \
DirectVsLambdaCallShapeCompileTimeMwe.cpp -o t.o
```
Always-inline lambda version:
```
TIMEFORMAT='LambdaInline %3R s'
time clang++ -O3 -std=c++20 \
-DUSE_LAMBDA_WRAPPER_ALWAYS_INLINE \
-DMWE_REPEAT_STEPS=N \
DirectVsLambdaCallShapeCompileTimeMwe.cpp -o t.o
```
### Results

|Steps | Direct | Lambda|
|--------|--------|--------|
|4 | 0.380588 s | 0.264000 s|
|8 | 0.633851 s | 0.267421 s|
|12 | 0.991703 s | 0.261426 s|
|16 | 1.582494 s | 0.263983 s|
|20 | 2.533415 s | 0.266393 s|
|24 | 3.847067 s | 0.265230 s|
|40 | 13.384652 s | 0.274577 s|

Additionally:
- `evaluateLambdaAlwaysInline() `regresses back to compile times similar to the direct version.

Note:

Please check [result.csv](https://github.com/user-attachments/files/27517692/result.csv) for the full table

### Expected Behaviour

The lambda and direct versions are semantically equivalent and generate very similar runtime behavior.
Ideally, compile time should not increase polynomially.

### Actual Behaviour

The direct version exhibits polynomial compile-time growth as MWE_REPEAT_STEPS increases.
The non-inlined lambda version avoids this growth almost entirely.
Forcing lambda inlining restores the pathological behavior.

Start with DirectVsLambdaCallShapeCompileTimeMwe.cpp and run the three clang++ command variants using increasing MWE_REPEAT_STEPS values and -ftime-trace. Compare the direct, non-inlined lambda, and always-inline lambda traces to identify the optimization work responsible. Done means explaining or correcting the polynomial compile-time growth without changing the reproducer’s runtime behavior.

Written by the indexing model from the issue text.