constexpr depth limit with clang (fconstexpr-depth doesnt seem to work)

Question

Is there anyway to configure constexpr instantiation depth? I am running with -fconstexpr-depth=4096 (using clang/XCode).

But still fail to compile this code with error: Constexpr variable fib_1 must be initialized by a constant expression. The code fails irrespective of whether option -fconstexpr-depth=4096 is set or not.

Is this a bug with clang or is expected to behave this way. Note: this works good till fib_cxpr(26), 27 is when it starts to fail.

Code:

constexpr int fib_cxpr(int idx) {
    return idx == 0 ? 0 :
           idx == 1 ? 1 :
           fib_cxpr(idx-1) + fib_cxpr(idx-2); 
}

int main() {
    constexpr auto fib_1 = fib_cxpr(27);
    return 0; 
}

Answer 1

TL;DR:

For clang you want the command line argument -fconstexpr-steps=1271242 and you do not need more than -fconstexpr-depth=27

---

The recursive method of calculating Fibonacci numbers does not require very much recursion depth. The depth required for fib(n) is in fact no more than n. This is because the longest chain of calls is through the fib(i-1) recursive call.

constexpr auto fib_1 = fib_cxpr(3); // fails with -fconstexpr-depth=2, works with -fconstexpr-depth=3
constexpr auto fib_1 = fib_cxpr(4); // fails with -fconstexpr-depth=3, works with -fconstexpr-depth=4

So we can conclude that -fconstexpr-depth is not the setting that matters.

Furthermore, the error messages also indicate a difference:

constexpr auto fib_1 = fib_cxpr(27);

Compiled with -fconstexpr-depth=26, to be sure we hit that limit, clang produces the message:

note: constexpr evaluation exceeded maximum depth of 26 calls

But compiling with -fconstexpr-depth=27, which is enough depth, produces the message:

note: constexpr evaluation hit maximum step limit; possible infinite loop?

So we know that clang is distinguishing between two failures: recursion depth and 'step limit'.

---

The top Google results for 'clang maximum step limit' lead to pages about the clang patch implementing this feature, including the implementation of the command-line option: -fconstexpr-steps. Further Googling of this option indicates that there's no user-level documentation.

So there's no documentation about what clang counts as a 'step' or how many 'steps' clang requires for fib(27). We could just set this really high, but I think that's a bad idea. Instead some experimentation shows:

n : steps
0 : 2
1 : 2
2 : 6
3 : 10
4 : 18

Which indicates that steps(fib(n)) == steps(fib(n-1)) + steps(fib(n-2)) + 2. A bit of calculation shows that, according to this, fib(27) should require 1,271,242 of clang's steps. So compiling with -fconstexpr-steps=1271242 should allow the program to compile, which indeed it does. Compiling with -fconstexpr-steps=1271241 results in an error the same as before, so we know we have an exact limit.

An alternative, less exact method involves observing from the patch that the default step limit is 1,048,576 (2²⁰), which is obviously sufficient for fib(26). Intuitively, doubling that should be plenty, and from the earlier analysis we know that two million is plenty. A tight limit would be ⌈φ · steps(fib(26))⌉ (which does happen to be exactly 1,271,242).

---

Another thing to note is that these results clearly show that clang is not doing any memoization of constexpr evaluation. GCC does, but it appears that this is not implemented in clang at all. Although memoization increases the memory requirements it can sometimes, as in this case, vastly reduce the time required for evaluation. The two conclusions I draw from this are that writing constexpr code that requires memoization for good compile times is not a good idea for portable code, and that clang could be improved with support for constexpr memoization and a command line option to enable/disable it.