LLVM can't properly optimize recursive Fibonacci with a constant

[evanacox]

Test case in C++ (see Godbolt):

// $ clang++ -std=c++20 -O3 file.cc  

constexpr int fib(int n) {
  if (n < 2) {
    return n;
  }

  return fib(n - 1) + fib(n - 2);
}

int f() {
  // this doesn't get evaluated to 55
  return fib(10);
}

// this does
constinit int a = fib(10);

The Clang front-end seems capable of it, but for whatever reason LLVM isn't able to do this. The small amount of testing I did with the IR and multiple runs of opt -O3 didn't do anything to actually evaluate it

[llvmbot]

@llvm/issue-subscribers-c-20

[ChuanqiXu9]

Sorry for add the wrong labels. I thought the issue is talking about the semantics of constinit at the first sight.

[ChuanqiXu9]

This should be able to be handled by FunctionSpecialization pass (It is called ipa-cp in gcc ). This pass would try to do optimization by cloning the functions. FunctionSpecialization pass in LLVM is disabled now and there are some cases it wouldn't handle. The main concerning is about the compilation time. We need to measure the impact on compilation time and the benefit to decide whether or not should we do it.

And this is a different story in the language side. One main direction in the current C++ I see is to put computation in the compilation time as much as possible. This is required by the users. So the compiler would only assume the user knows what he/she want. This is the basic principle in C++. However, the optimizer couldn't assume the user would satisfy about the compilation time. The key difference here is about semantic.

BTW, the case you showed couldn't be handled in current implementation: I've tried many times in https://godbolt.org/z/q9cqhGn9v. The reason should be that we didn't handle as many cases as possible now. @sjoerdmeijer do you think this should be handled? It looks powerful in the small example but I think it wouldn't take a big part in actual workload.

[sjoerdmeijer]

Yes, I was also surprised that with (internal/hidden) flags to force and specialize on literal constants it wasn't doing it. I think it would be a nice case to support, and it probably should have been already.

Slightly off-topic, for these kind of cases and experiments it would be really nice to have a pragma that allows annotation of call sides and steer/force specialisation, e.g.:

int f() {
 #pragma specialize_function
  return fib(10);
}

But we probably need a bit of syntax to allow an argument list of which arguments to specialise in case the functions takes more than 1 argument. I guess that makes the Clang front-end work a bit more work than the work required in FunctionSpecialisation to support this which I think should be relatively straightforward.

[ChuanqiXu9]

Yeah, the transformation is beautiful after all.

And the syntax you mentioned is very interesting to me. I was wondering how should we add attribute at callsite for a long time. I would try to take a look.

[sjoerdmeijer]

And the syntax you mentioned is very interesting to me. I was wondering how should we add attribute at callsite for a long time. I would try to take a look.

It has been on my list too, but I would be happy to review your patches if you're going to have a look! :-)

[ChuanqiXu9]

I really wondered how could we add information at callsite to help optimization for a long time. It matters a lot for coroutines. I don't have time to look at it soon (maybe a month?) So if it is more urgent to you, I think you could take a look first. The important thing is to avoid the redundant work : )