传递引用会阻碍gcc进行尾调用优化。

Question

传递引用会阻碍gcc进行尾调用优化。

c++gccrecursionfunctional-programmingtail-call-optimization

7

请查看BlendingTable::create和BlendingTable::print。两者都具有相同形式的尾递归，但是create将被优化为循环，而print不会，从而导致堆栈溢出。

向下滚动以查看解决方法，我从其中一位gcc开发人员的提示中获得了这个问题的修复方法。

#include <cstdlib>
#include <iostream>
#include <memory>
#include <array>
#include <limits>

class System {
public:
    template<typename T, typename... Ts>
    static void print(const T& t, const Ts&... ts) {
        std::cout << t << std::flush;
        print(ts...);
    }

    static void print() {}

    template<typename... Ts>
    static void printLine(const Ts&... ts) {
        print(ts..., '\n');
    }
};

template<typename T, int dimension = 1>
class Array {
private:
    std::unique_ptr<T[]> pointer;
    std::array<int, dimension> sizes;
    int realSize;

public:
    Array() {}

    template<typename... Ns>
    Array(Ns... ns):
    realSize(1) {
        checkArguments(ns...);
        create(1, ns...);
    }

private:
    template<typename... Ns>
    static void checkArguments(Ns...) {
        static_assert(sizeof...(Ns) == dimension, "dimension mismatch");
    }

    template<typename... Ns>
    void create(int d, int n, Ns... ns) {
        realSize *= n;
        sizes[d - 1] = n;
        create(d + 1, ns...);
    }

    void create(int) {
        pointer = std::unique_ptr<T[]>(new T[realSize]);
    }

    int computeSubSize(int d) const {
        if (d == dimension) {
            return 1;
        }
        return sizes[d] * computeSubSize(d + 1);
    }

    template<typename... Ns>
    int getIndex(int d, int n, Ns... ns) const {
        return n * computeSubSize(d) + getIndex(d + 1, ns...);
    }

    int getIndex(int) const {
        return 0;
    }

public:
    template<typename... Ns>
    T& operator()(Ns... ns) const {
        checkArguments(ns...);
        return pointer[getIndex(1, ns...)];
    }

    int getSize(int d = 1) const {
        return sizes[d - 1];
    }
};

class BlendingTable : public Array<unsigned char, 3> {
private:
    enum {
        SIZE = 0x100,
        FF = SIZE - 1,
    };

public:
    BlendingTable():
    Array<unsigned char, 3>(SIZE, SIZE, SIZE) {
        static_assert(std::numeric_limits<unsigned char>::max() == FF, "unsupported byte format");
        create(FF, FF, FF);
    }

private:
    void create(int dst, int src, int a) {
        (*this)(dst, src, a) = (src * a + dst * (FF - a)) / FF;
        if (a > 0) {
            create(dst, src, a - 1);
        } else if (src > 0) {
            create(dst, src - 1, FF);
        } else if (dst > 0) {
            create(dst - 1, FF, FF);
        } else {
            return;
        }
    }

    void print(int dst, int src, int a) const {
        System::print(static_cast<int>((*this)(FF - dst, FF - src, FF - a)), ' ');
        if (a > 0) {
            print(dst, src, a - 1);
        } else if (src > 0) {
            print(dst, src - 1, FF);
        } else if (dst > 0) {
            print(dst - 1, FF, FF);
        } else {
            System::printLine();
            return;
        }
    }

public:
    void print() const {
        print(FF, FF, FF);
    }
};

int main() {
    BlendingTable().print();
    return EXIT_SUCCESS;
}

将 System 的类定义从

class System {
public:
    template<typename T, typename... Ts>
    static void print(const T& t, const Ts&... ts) {
        std::cout << t << std::flush;
        print(ts...);
    }

    static void print() {}

    template<typename... Ts>
    static void printLine(const Ts&... ts) {
        print(ts..., '\n');
    }
};

to

class System {
public:
    template<typename T, typename... Ts>
    static void print(T t, Ts... ts) {
        std::cout << t << std::flush;
        print(ts...);
    }

    static void print() {}

    template<typename... Ts>
    static void printLine(Ts... ts) {
        print(ts..., '\n');
    }
};

神奇地允许gcc消除尾调用。

为什么'是否通过引用传递函数参数'会对gcc的行为产生如此大的影响？在这种情况下，它们在语义上看起来都一样。

- user3810155

1

我真的很好奇是否使用完美转发会出现同样的问题。 - WhozCraig

一般来说，按引用传递会使编译器的程序分析更加困难，因此更难确定哪些转换是合法的。无论这是否是实际问题，或者是否存在其他原因（例如标准中的怪异之处，使得此优化不合法），我无法确定。 - MikeMB

2

一种假设是，强制类型转换创建一个临时对象，其引用被传递给 print 函数，现在编译器可能感到需要保留该临时对象，直到 print 函数返回。 - jxh

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Orest Hera · Answer 1

正如 @jxh 所指出的那样，强制类型转换 static_cast<int>() 会创建一个临时对象，其引用被传递给 print 函数。如果没有这样的强制类型转换，则尾递归将被正确优化。

这个问题非常类似于旧案例为什么 g++ 没有尾调用优化而 gcc 有？，解决方法可能类似于 https://dev59.com/KWsz5IYBdhLWcg3w8Mcb#31793391。

如果将对 System::print 的调用移动到一个单独的私有辅助函数 SystemPrint 中，则仍然可以使用传递的参数引用来使用 System：

class BlendingTable : public Array<unsigned char, 3> {

//...

private:
    void SystemPrint(int dst, int src, int a) const
    {
        System::print(static_cast<int>((*this)(FF - dst, FF - src, FF - a)), ' ');
    }

    void print(int dst, int src, int a) const {
        SystemPrint(dst, src, a);
        if (a > 0) {
            print(dst, src, a - 1);
        } else if (src > 0) {
            print(dst, src - 1, FF);
        } else if (dst > 0) {
            print(dst - 1, FF, FF);
        } else {
            System::printLine();
            return;
        }
    }

// ...

}

现在尾调用优化已经生效（使用优化选项-O2的g++（Ubuntu/Linaro 4.7.2-2ubuntu1）4.7.2），print不会导致堆栈溢出。

更新

我已经通过其他编译器进行了验证：

原始代码没有任何更改，使用clang++ Apple LLVM版本5.1（基于LLVM 3.4svn）进行-O1优化，完全优化。
即使没有强制转换或使用包装函数SystemPrint解决方法，g++（Ubuntu 4.8.4-2ubuntu1~14.04）4.8.4仍无法执行TCO；这里只有使用值传递的System::print参数的解决方法有效。

因此，该问题非常特定于编译器版本。