compiler tries to evaluate unreachable code after constexpr if

Question

I've experimenting with C++17 lately and found this:

template<size_t i>
void recurse()
{
    if constexpr(i == 0)
        return;
    return recurse<i - 1>();
}

Trying to call recurse<4>(); will lead to

fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) return recurse<i - 1>();

Adding an else fixes the error:

template<size_t i>
void recurse()
{
    if constexpr(i == 0)
        return;
    else
        return recurse<i - 1>();
}

Is this a bug? Unfortunately I don't have access to another compiler than gcc 7.3.0 right now.

Hakluyt

size_t is an "unsigned int" type, which means a negative is translated into huge number, that's why maximum 900 exceeds in that case. – Cylindrical

Answer 1

No: isn't a bug.

Both if constexpr and else are necessary.

In you first version

template<size_t i>
void recurse()
{
    if constexpr(i == 0)
        return;
    return recurse<i - 1>();
}

the recurse<i-1>() is compiled also when i == 0, so is generated recurse<-1>(), so is generated recurse<-2>(), etc.

You need the else to link the return recurse<i-1>() to if constexpr (i == 0) and avoid it's compilation when i == 0 ending the recursion.

You can try the second version removing constexpr

template<size_t i>
void recurse()
{
    if (i == 0)
        return;
    else
        return recurse<i - 1>();
}

and you should get the same "template instantiation depth exceeds maximum of 900" recursion error.

Steffin

Normally the compiler will remove unreacheable code. Since the result of if constexpr if is known at compile time the compiler also knows that the second return statement is never reached and thus should be able to remove it. On the other hand, the additional else doesn't really hurt ;) – Hakluyt

@Hakluyt - As far I know, the compiler can remove unreachable code; with if constexpr (and a corresponding else) must remove it. That else is necessary to be sure that the unnecessary code is removed. – Steffin

@Hakluyt The compiler has to determine the observable behaviour of the program, so that it can ensure that it doesn't change it. The if constexpr allows it to skip blocks during that determination – Necrosis

Answer 2

Same thing on gcc 8.1 and on some other gcc versions too. I think, static if needs else branch too, because if you haven't, compiler always generates recurse() call.

Nitrile

Answer 3

max66's answer is just fine, but as someone who has implemented various parsers and even simple compilers over the years let me offer you some more context.

Let's first get this out of the way: It would only be a bug if the standard mandated it (or GCC documented the behavior you want, as a language extension).

However, the standard cannot mandate that unreachable code be removed because detecting which code is unreachable is an undecidable problem. This can be trivially proven by reducing it to the halting problem. Assume that comp is a Turing machine computation, n is a non-negative integer value (of an unbounded type) and halts is a function that executes up to n number of iterations of comp and returns whether or not a halting state was reached. Now consider the following pseudo-code:

if ( halts(comp, n) )
    print "Halted.";

Determining whether or not the print statement is reachable therefore requires solving the halting problem for comp which is an arbitrary Turing machine calculation – not possible.

Now you might say that this is a very contrived reasoning, and has nothing to do with obviously decidable cases such as your example. However, consider that intuitive assumptions about "obviousness" and the wording of the language standard are two very different things. In other words, the committee would need to select a subset of "detectable" cases and carefully specify under which circumstances the implementation is required to detect unreachable code (and, in time, prune the evaluation tree). Compiler vendors would then be obliged to spend a possibly great deal of time implementing these rules. (Remember that software traditionally operates on "hard-coded" logical rules and does not "intuit" its required behavior. Maybe one day we'll have AI compilers that automagically do "the right thing", but we're currently not even close to that.)

Long story short – while such an approach could be taken, resources are limited, and there are simply a great many more important issues to be solved. The inconvenience of needing to be explicit about the branch structure by adding an else, in your example, is indeed minor.

Jacksonjacksonville