Подтвердить что ты не робот

Почему оптимизация tailcall не выполняется для типов класса MEMORY?

Я пытаюсь понять значение System V AMD64 - ABI для возврата по значению из функции.

Для следующего типа данных

struct Vec3{
    double x, y, z;
};

тип Vec3 относится к классу MEMORY, и, таким образом, ABI указывает следующее: "Возвращение значений":

  1. Если тип имеет класс MEMORY, то вызывающая сторона предоставляет пространство для возвращаемого значения и передает адрес этого хранилища в% rdi, как если бы это был первый аргумент функции. По сути, этот адрес становится "скрытым" первым аргументом. Это хранилище не должно перекрывать какие-либо данные, видимые вызываемому абоненту через другие имена, кроме этого аргумента.

    На return% rax будет содержать адрес, который был передан вызывающая сторона в% rdi.

Имея это в виду, следующая (глупая) функция:

struct Vec3 create(void);

struct Vec3 use(){
    return create();
}

может быть скомпилировано как:

use_v2:
        jmp     create

По моему мнению, оптимизация tailcall может быть выполнена, поскольку мы уверены в ABI, что create поместит переданное значение %rdi в регистр %rax.

Однако ни один из компиляторов (gcc, clang, icc), по-видимому, не выполняет эту оптимизацию (здесь на Godbolt). Полученный код сборки сохраняет %rdi в стеке только для возможности перемещения его значения в %rax, например, gcc:

use:
        pushq   %r12
        movq    %rdi, %r12
        call    create
        movq    %r12, %rax
        popq    %r12
        ret

Ни для этой минимальной, глупой функции, ни для более сложных из реальной жизни не выполняется оптимизация tailcall. Что заставляет меня верить, что я что-то упускаю, что запрещает это.


Само собой разумеется, что для типов класса SSE (например, только 2, а не 3 двойных) выполняется оптимизация tailcall (по крайней мере, gcc и clang, live на godbolt):

struct Vec2{
    double x, y;
};

struct Vec2 create(void);

struct Vec2 use(){
    return create();
}

приводит к

use:
        jmp     create
4b9b3361

Ответ 1

Похоже на пропущенную ошибку оптимизации, о которой следует сообщить, если еще нет открытых дубликатов для gcc и clang.

(Нередко и в gcc, и в clang бывает одинаковая пропущенная оптимизация в подобных случаях; не предполагайте, что что-то незаконно, только потому, что компиляторы этого не делают. Единственные полезные данные - это когда компиляторы делают это. выполнить оптимизацию: либо ошибка компилятора, либо, по крайней мере, некоторые разработчики компилятора решили, что это безопасно в соответствии с их интерпретацией любых стандартов.)


Мы можем видеть, что GCC возвращает свой собственный входящий аргумент вместо того, чтобы возвращать его копию, которую create() вернет в RAX. Это пропущенная оптимизация, блокирующая оптимизацию tailcall.

Для ABI требуется функция с возвращаемым значением типа MEMORY для возврата "скрытого" указателя в RAX 1.

GCC/clang уже понимают, что они могут исключить фактическое копирование, передавая собственное пространство возвращаемых значений вместо выделения нового пространства. Но для оптимизации хвостового вызова им нужно понять, что они могут оставить значение RAX вызываемого в RAX вместо сохранения входящего RDI в регистре с сохранением вызова.

Если бы ABI не требовал возврата скрытого указателя в RAX, я ожидаю, что у gcc/clang не было бы проблем с передачей входящего RDI как части оптимизированного хвостового вызова.

Обычно компиляторы любят сокращать цепочки зависимостей; это, вероятно, то, что здесь происходит. Компилятор не знает, что задержка от rdi arg до rax результата create(), вероятно, является всего лишь одной инструкцией mov. По иронии судьбы, это может быть пессимизацией, если вызываемый объект сохраняет/восстанавливает некоторые регистры, сохраняющие вызовы (например, r12), представляя сохранение/перезагрузку указателя обратного адреса. (Но это, в основном, имеет значение, только если что-то и использует. Я получил некоторый лязгательный код, см. ниже.)


Сноска 1: Возвращение указателя звучит как хорошая идея, но почти всегда вызывающая сторона уже знает, куда она помещает аргумент в свой собственный кадр стека, и будет просто использовать режим адресации, такой как 8(%rsp), вместо того, чтобы фактически использовать RAX. По крайней мере, в сгенерированном компилятором коде возвращаемое значение RAX обычно не используется. (И при необходимости звонящий всегда может сохранить его где-нибудь самостоятельно.)

Как обсуждалось в Что мешает использовать аргумент функции в качестве скрытого указателя? Существуют серьезные препятствия для использования чего-либо, кроме пробела в кадре стека вызывающих, для получения ответа.

Наличие указателя в регистре просто сохраняет LEA в вызывающей стороне, если вызывающая сторона хочет где-то сохранить адрес, если это статический адрес или адрес стека.

Однако этот случай близок к тому, в котором он был бы полезен. Если мы передаем наше собственное пространство для поиска дочерней функции, мы можем захотеть изменить это пространство после вызова. Тогда это полезно для легкого доступа к этому пространству, например, изменить возвращаемое значение, прежде чем мы вернемся.

#define T struct Vec3

T use2(){
    T tmp = create();
    tmp.y = 0.0;
    return tmp;
}

Эффективный рукописный ассемблер:

use2:
        callq   create
        movq    $0, 8(%rax)
        retq

Фактический clang asm по крайней мере все еще использует оптимизацию возвращаемого значения, а не копирование GCC9.1. (Godbolt)

# clang -O3
use2:                                   # @use2
        pushq   %rbx
        movq    %rdi, %rbx
        callq   create
        movq    $0, 8(%rbx)
        movq    %rbx, %rax
        popq    %rbx
        retq

Это правило ABI, возможно, существует специально для этого случая, или, может быть, разработчики ABI представляли, что пространство поиска может быть вновь выделенным динамическим хранилищем (на которое вызывающий абонент должен будет сохранить указатель, если ABI его не предоставил) в RAX). Я не пробовал этот случай.

Ответ 2

Система V AMD64 - ABI будет возвращать данные из функции в регистрах RDX и RAX или XMM0 и XMM1. Глядя на Godbolt, кажется, что оптимизация основана на размере. Компилятор возвращает только 2 double или 4 float в регистрах.


Компиляторы все время пропускают оптимизации. Язык C не имеет оптимизации хвостового вызова, в отличие от Scheme. GCC и Clang заявили, что не планируют пытаться гарантировать оптимизацию хвостовой связи. Похоже, что OP может попытаться спросить разработчиков компилятора или открыть ошибку с указанными компиляторами.