Почему звонки, когда jmps было бы достаточно?

Ответ 1

Первый случай (через switch()) создает для меня следующее (Linux x86_64/gcc 4.4):

  400570:       ff 24 c5 b8 06 40 00    jmpq   *0x4006b8(,%rax,8)
[ ... ]
  400580:       31 c0                   xor    %eax,%eax
  400582:       e8 e1 fe ff ff          callq  400468 <[email protected]>
  400587:       31 c0                   xor    %eax,%eax
  400589:       48 83 c4 08             add    $0x8,%rsp
  40058d:       c3                      retq
  40058e:       bf a4 06 40 00          mov    $0x4006a4,%edi
  400593:       eb eb                   jmp    400580 <main+0x30>
  400595:       bf a9 06 40 00          mov    $0x4006a9,%edi
  40059a:       eb e4                   jmp    400580 <main+0x30>
  40059c:       bf ad 06 40 00          mov    $0x4006ad,%edi
  4005a1:       eb dd                   jmp    400580 <main+0x30>
  4005a3:       bf b1 06 40 00          mov    $0x4006b1,%edi
  4005a8:       eb d6                   jmp    400580 <main+0x30>
[ ... ]
Contents of section .rodata:
[ ... ]
 4006b8 8e054000 p ... ]

Обратите внимание, что содержимое .rodata @4006b8 является печатным сетевым порядком байтов (по какой-либо причине...) значение 40058e, которое находится в пределах main выше - где блок arg-initializer/jmp начинается. Все пары mov/jmp там используют восемь байтов, следовательно, (,%rax,8) косвенное. В этом случае последовательность имеет следующий вид:

jmp <to location that sets arg for printf()>
...
jmp <back to common location for the printf() invocation>
...
call <printf>
...
retq

Это означает, что компилятор фактически оптимизировал сайты вызовов static - и вместо этого объединил их в единый встроенный вызов printf(). В этой таблице используется команда jmp ...(,%rax,8) и таблица, содержащаяся в программном коде.

Второй (с явно созданной таблицей) делает для меня следующее:

0000000000400550 <print0>:
[ ... ]
0000000000400560 <print1>:
[ ... ]
0000000000400570 <print2>:
[ ... ]
0000000000400580 <print3>:
[ ... ]
0000000000400590 <print4>:
[ ... ]
00000000004005a0 <main>:
  4005a0:       48 83 ec 08             sub    $0x8,%rsp
  4005a4:       bf d4 06 40 00          mov    $0x4006d4,%edi
  4005a9:       31 c0                   xor    %eax,%eax
  4005ab:       48 8d 74 24 04          lea    0x4(%rsp),%rsi
  4005b0:       e8 c3 fe ff ff          callq  400478 <[email protected]>
  4005b5:       8b 54 24 04             mov    0x4(%rsp),%edx
  4005b9:       31 c0                   xor    %eax,%eax
  4005bb:       ff 14 d5 60 0a 50 00    callq  *0x500a60(,%rdx,8)
  4005c2:       31 c0                   xor    %eax,%eax
  4005c4:       48 83 c4 08             add    $0x8,%rsp
  4005c8:       c3                      retq
[ ... ]
 500a60 50054000 00000000 60054000 00000000  [email protected]`[email protected]
 500a70 70054000 00000000 80054000 00000000  [email protected]@.....
 500a80 90054000 00000000                    [email protected]

Снова обратите внимание на инвертированный порядок байтов, так как objdump печатает секцию данных - если вы обернете их вокруг, вы получите адрес функции для print[0-4]().

Компилятор вызывает цель через косвенный call - то есть использование таблицы непосредственно в команде call, и таблица явно создается как данные.

Edit:
Если вы измените источник следующим образом:

#include <stdio.h>

static inline void print0() { printf("Zero"); }
static inline void print1() { printf("One"); }
static inline void print2() { printf("Two"); }
static inline void print3() { printf("Three"); }
static inline void print4() { printf("Four"); }

void main(int argc, char **argv)
{
    static void (*jt[])() = { print0, print1, print2, print3, print4 };
    return jt[argc]();
}

созданная сборка для main() становится:

0000000000400550 <main>:
  400550:       48 63 ff                movslq %edi,%rdi
  400553:       31 c0                   xor    %eax,%eax
  400555:       4c 8b 1c fd e0 09 50    mov    0x5009e0(,%rdi,8),%r11
  40055c:       00
  40055d:       41 ff e3                jmpq   *%r11d

который больше похож на то, что вы хотели?

Причиной этого является то, что для этого вам понадобятся "стековые" функции: хвостовая рекурсия (возврат из функции через jmp вместо ret) возможна только в том случае, если вы либо сделали весь стек очистить уже или не нужно делать, потому что вам нечего убирать в стеке. Компилятор может (но не обязательно) выбирать для очистки до последнего вызова функции (в этом случае последний вызов может быть сделан jmp), но это возможно только в том случае, если вы возвращаете либо значение, которое вы получили от этой функции, либо если вы "вернетесь void". И, как сказано, если вы на самом деле используете стек (как ваш пример для переменной input), то ничего, что может заставить силу компилятора отменить это, таким образом, что результаты хвостовой рекурсии.

Edit2:

Разбор для первого примера с теми же изменениями (argc вместо input и форсированием void main - комментариев по стандартному соответствию, пожалуйста, это демонстрация), приводит к следующей сборке:

0000000000400500 <main>:
  400500:       83 ff 04                cmp    $0x4,%edi
  400503:       77 0b                   ja     400510 <main+0x10>
  400505:       89 f8                   mov    %edi,%eax
  400507:       ff 24 c5 58 06 40 00    jmpq   *0x400658(,%rax,8)
  40050e:       66                      data16
  40050f:       90                      nop
  400510:       f3 c3                   repz retq
  400512:       bf 3c 06 40 00          mov    $0x40063c,%edi
  400517:       31 c0                   xor    %eax,%eax
  400519:       e9 0a ff ff ff          jmpq   400428 <[email protected]>
  40051e:       bf 41 06 40 00          mov    $0x400641,%edi
  400523:       31 c0                   xor    %eax,%eax
  400525:       e9 fe fe ff ff          jmpq   400428 <[email protected]>
  40052a:       bf 46 06 40 00          mov    $0x400646,%edi
  40052f:       31 c0                   xor    %eax,%eax
  400531:       e9 f2 fe ff ff          jmpq   400428 <[email protected]>
  400536:       bf 4a 06 40 00          mov    $0x40064a,%edi
  40053b:       31 c0                   xor    %eax,%eax
  40053d:       e9 e6 fe ff ff          jmpq   400428 <[email protected]>
  400542:       bf 4e 06 40 00          mov    $0x40064e,%edi
  400547:       31 c0                   xor    %eax,%eax
  400549:       e9 da fe ff ff          jmpq   400428 <[email protected]>
  40054e:       90                      nop
  40054f:       90                      nop

Это хуже одним способом (вместо двух jmp вместо одного), но лучше в другом (потому что он исключает функции static и строит код). Оптимизация, компилятор в значительной степени сделал то же самое.

Ответ 2

У писателей-компиляторов есть много работы. Очевидно, они уделяют приоритетное внимание работе, которая имеет самый большой и быстрый результат.

Операторы Switch являются обычными для всех видов кода, поэтому любые выполненные на них оптимизации будут влиять на множество программ.

Этот код

jt[input](); 

намного реже, и, следовательно, намного больше времени на TODO-список дизайнеров компиляторов. Возможно, они еще не решили, что стоит попытаться его оптимизировать? Будет ли это выигрывать у них какие-либо известные тесты? Или улучшить некоторую широко используемую кодовую базу?

Ответ 3

Потому что массив указателей функций изменчив. Компилятор решил, что не может предположить, что указатели не будут изменены. Вы можете найти сборку, отличающуюся для С++, и/или сделать jt const.

Ответ 4

Моя догадка заключается в том, что эта оптимизация связана с тем фактом, что после switch: у вас есть оператор return: оптимизатор понимает, что он может комбинировать возвраты, встроенные в ваш print0.. print4 функции и уменьшает call до jmp; ret CPU, попадающий внутрь выбранного printN, служит в качестве возврата из main.

Попробуйте вставить код после переключения, чтобы увидеть, заменит ли компилятор jmp на call.

#include <stdio.h>

static inline void print0() { printf("Zero"); }
static inline void print1() { printf("One"); }
static inline void print2() { printf("Two"); }
static inline void print3() { printf("Three"); }
static inline void print4() { printf("Four"); }

int main()
{
    unsigned int input;
    scanf("%u", &input);

    switch (input)
    {
        case 0: print0(); break;
        case 1: print1(); break;
        case 2: print2(); break;
        case 3: print3(); break;
        case 4: print4(); break;
    }
    /* Inserting this line should force the compiler to use call */
    printf("\nDone");
    return 0;
}

РЕДАКТИРОВАТЬ: Ваш код ideone имеет jmp по другой причине: это эквивалент этого:

static const char* LC0 ="Zero";
static const char* LC1 ="One";
static const char* LC2 ="Two";
static const char* LC3 ="Three";
static const char* LC4 ="Four";

int main()
{
    unsigned int input;
    scanf("%u", &input);

    switch (input)
    {
        case 0: printf(LC0); break;
        case 1: printf(LC1); break;
        case 2: printf(LC2); break;
        case 3: printf(LC3); break;
        case 4: printf(LC4); break;
    }
    printf("\nDone");
    return 0;
}

Ответ 5

Профилировали ли вы другой код? Я думаю, что можно аргументировать, что косвенный вызов оптимизирован. Следующий анализ был проведен с использованием GCC 4.6.1 для платформы x64 (MinGW).

Если вы посмотрите, что произойдет, когда используется jt[input](), вызов приведет к следующей последовательности выполняемого кода:

• косвенный вызов одной из функций printX()
• Функция printX() устанавливает аргумент для printf(), затем
• переходит в printf()
• вызов printf() будет возвращаться непосредственно на сайт косвенного вызова.

В общей сложности три ветки.

При использовании оператора switch происходит следующее:

• косвенный переход на бит пользовательского кода для каждого случая (вложенные printX() вызовы)
• "обработчик case" загружает соответствующий аргумент для вызова printf()
• вызывает printf()
• вызов printf() вернется к обработчику case, который
• переходит к точке выхода коммутатора (за исключением одного обработчика случая, в котором код выхода вложен - другие скачки туда)

В общей сложности 4 ветки (в общем случае).

В обеих ситуациях у вас есть: - косвенная ветвь (для одного это вызов, а в другом - прыжок) - ветвь к printf() (для одного это прыжок, в другом - вызов) - ответвление назад на сайт вызова

Однако, когда оператор switch используется там, есть дополнительная ветка, чтобы добраться до "конца" коммутатора (в большинстве случаев).

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

Для тех, кого это интересует, здесь ассемблер, сгенерированный с использованием jk[input](); (оба примера, скомпилированные с использованием GCC MinGW 4.6.1 с таргетингом на x64, были -Wall -Winline -O3 -S -masm=intel):

print0:
    .seh_endprologue
    lea rcx, .LC4[rip]
    jmp printf
    .seh_endproc

// similar code is generated for each printX() function
// ...

main:
    sub rsp, 56
    .seh_stackalloc 56
    .seh_endprologue
    call    __main
    lea rdx, 44[rsp]
    lea rcx, .LC5[rip]
    call    scanf
    mov edx, DWORD PTR 44[rsp]
    lea rax, jt.2423[rip]
    call    [QWORD PTR [rax+rdx*8]]
    xor eax, eax
    add rsp, 56
    ret

И вот код, созданный для реализации на основе коммутатора:

main:
    sub rsp, 56
    .seh_stackalloc 56
    .seh_endprologue
    call    __main
    lea rdx, 44[rsp]
    lea rcx, .LC0[rip]
    call    scanf
    cmp DWORD PTR 44[rsp], 4
    ja  .L2
    mov edx, DWORD PTR 44[rsp]
    lea rax, .L8[rip]
    movsx   rdx, DWORD PTR [rax+rdx*4]
    add rax, rdx
    jmp rax
    .section .rdata,"dr"
    .align 4
.L8:
    .long   .L3-.L8
    .long   .L4-.L8
    .long   .L5-.L8
    .long   .L6-.L8
    .long   .L7-.L8
    .section    .text.startup,"x"
.L7:
    lea rcx, .LC5[rip]
    call    printf
    .p2align 4,,10


.L2:
    xor eax, eax
    add rsp, 56
    ret

.L6:
    lea rcx, .LC4[rip]
    call    printf
    jmp .L2

     // all the other cases are essentially the same as the one above (.L6)
     // where they jump to .L2 to exit instead of simply falling through to it
     // like .L7 does

Ответ 6

Не работает ли код для последней функции между косвенным call и последующим ret? Я не удивлюсь, если в адресном вычислении для косвенного вызова используется регистр, значение которого требуется последней функции (это означает, что он должен сохранить значение перед вычислением и восстановить его через некоторое время после). Хотя может быть возможно переместить код регистрации-восстановления перед косвенным вызовом, компилятор может выполнять только такое движение кода в тех случаях, когда он был запрограммирован на признание в качестве законных возможностей.

Кроме того, хотя я не думаю, что это имеет значение, я бы предположил, что подпрограммы не должны быть inline, так как компилятор не сможет их выполнить таким образом.