Передача по ссылке препятствует gcc от устранения хвостового вызова

Увидеть 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');
}
};

в

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? Семантически они оба выглядят одинаково для меня в этом случае.

7

Решение

Как отмечает @jxh актерский состав static_cast<int>() создает временный, чья ссылка передается print функция. Без такого броска рекурсия хвоста оптимизирована правильно.

Вопрос очень похож на старый случай Почему g ++ не оптимизирует хвостовой вызов, пока gcc? и обходной путь может быть похож на https://stackoverflow.com/a/31793391/4023446.

Все еще можно использовать System с аргументами, передаваемыми по ссылке, если вызов System::print будет перемещен в отдельную частную вспомогательную функцию SystemPrint:

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;
}
}

// ...

}

Теперь работает оптимизация хвостового вызова (g ++ (Ubuntu / Linaro 4.7.2-2ubuntu1) 4.7.2 с опцией оптимизации -O2) и print не вызывает переполнение стека.

Обновить

Я проверил это с другими компиляторами:

  • исходный код без каких-либо изменений прекрасно оптимизирован с помощью clang ++ Apple LLVM версии 5.1 (clang-503.0.40) (на основе LLVM 3.4svn) с оптимизацией -O1
  • g ++ (Ubuntu 4.8.4-2ubuntu1 ~ 14.04) 4.8.4 не может выполнить TCO даже без приведения или с функцией обтекания SystemPrint обходной путь; здесь только обходной путь с System::print аргументы по значениям работает.

Таким образом, проблема очень специфична для версий компилятора.

1

Другие решения


По вопросам рекламы [email protected]