GCC不能尾调用优化递归函数。

Question

我为我的uint128结构编写了一个十六进制解析函数，它在内部仅由两个uint64_t - hi和lo组成。以下是相关的函数：

uint128_t parse_from_hex(const char *string, uint128_t previous_value, const size_t num_digits) {
    if (string == NULL || string[0] == '\0')
        return previous_value;

    if (num_digits + 1 > 2 * SIZEOF_INT128) { // SIZEOF_INT128 is 16 - meaning 16 bytes
        return UINT128_MAX; // the maximum value of 128bit uint, if we overflow
    }

    int64_t current_digit = parse_hex_digit(string[0]);
    if (current_digit < 0)
        return UINT128_ZERO; // a global variable which I use multiple times which represents a 0
    return parse_from_hex(string + 1,
                          uint128_or_uint64(uint128_shift_left(previous_value, 4), (uint64_t)current_digit),
                          num_digits + 1);
}

由于某种原因，即使递归调用明显仅在函数末尾执行一次，gcc也不会对该函数进行优化。在解析函数中使用的其他函数没有任何副作用并返回新值，因此我认为问题不在它们身上。我已经尝试将uint128_t结构成员设置为非const（最初它们是非const的），以及将函数参数设置为非const，但这也没有帮助。最初使用Ofast编译，但也尝试了O3和O2 - 没有好运。请了解得更多的人可以帮忙吗？我觉得我理解得很好，但显然我错过了什么。

- renbou

---

你为什么要用递归来做这个？这是循环的工作。 - tadman

这里是一个godbolt链接，展示了原始代码不是尾递归的：https://godbolt.org/z/Ws4YTz - Bill Lynch

GCC 10.2会在此处执行尾递归，Clang则不会。 - Bill Lynch

GCC在优化和展开循环方面比处理尾递归更容易，后者更多地是一种函数式编程模式。优化器处理人们最常使用的模式。即使经过优化，这段代码看起来也比基于循环的同等版本要复杂得多。 - tadman

为了好玩，采用非递归方法 uint128_t parse_from_hex(const char *string) { uint128_t sum = 0; if (string) { while (*string) { int current_digit = parse_hex_digit(*string); if (current_digit < 0) { return 0; } if (sum > UINT128_MAX / 16) { return UINT128_MAX; } sum = sum * 16 + (current_digit & 15); string++; } } return sum; }` - chux - Reinstate Monica

Answer 1

正如评论中@BillLynch所指出的那样 - 是clang由于某种原因没有对该函数进行优化，而不是GCC。在我的PC上，GCC 10.2.0可以正确地优化该函数，因此这里没有问题。

- renbou