CODEWITHSUNDEEP
c++clangtail-recursion
oblitum
oblitum

Reputation: 11998

Why the following function doesn't generate tail recursion with Clang?

Under clang the following function generates object code for a tail recursive function:

template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
    return counter >= limit
        ? number % limit != 0
        : number % counter
            ? is_prime(number, number / counter, counter + 2)
            : false;
}

template<typename T>
constexpr bool is_prime(T n)
{
    return n == 2 || n == 3 || n == 5
        ? true
        : n <= 1 || n % 2 == 0
            ? false
            : is_prime(n, n / 3, T{3});
}

but changing one line (letting a boolean result "non-normalized"), it ceases to generate tail recursive object code:

template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
    return counter >= limit
        ? number % limit    // changed here
        : number % counter
            ? is_prime(number, number / counter, counter + 2)
            : false;
}

template<typename T>
constexpr bool is_prime(T n)
{
    return n == 2 || n == 3 || n == 5
        ? true
        : n <= 1 || n % 2 == 0
            ? false
            : is_prime(n, n / 3, T{3});
}

Is it clang failing to optimize it correctly or there's a logical reason for so?

To force runtime evaluation, x is a runtime integral prime ≥ 13 (one recursion) or a large enough constexpr prime that would prevent compile-time evaluation because of large recursion depth:

is_prime(x);

Upvotes: 2

Views: 288

Answers (1)

krsteeve
krsteeve

Reputation: 1804

If you have exp1 ? exp2 : exp3, to determine the type of the ?: statement the type of exp3 is converted into the type of exp2 (if possible). This means your nice bool result is converted into type T and has to be converted back to bool for return.

This means that the recursive call is not the last statement. I believe if you reverse the order in the ternary operator you will get the tail recursive result.

template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
    return counter < limit
        ? (number % counter
            ? is_prime(number, number / counter, counter + 2)
            : false)
        : number % limit;
}

Upvotes: 2

Related Questions