为什么要使用调用而不是跳转？

Question

我有两个文件：

#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;
    }
    return 0;
}

并且

#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);

    static void (*jt[])() = { print0, print1, print2, print3, print4 };
    jt[input]();
    return 0;
}

我原本期望它们会编译成几乎相同的汇编代码。两种情况下都生成了跳转表，但是在第一个文件中的调用由jmp表示，而在第二个文件中的调用由call表示。为什么编译器不优化call？是否可能向gcc提示我想看到jmp而不是call？

使用gcc -Wall -Winline -O3 -S -masm=intel编译，GCC版本为4.6.2。 GCC 4.8.0生成的代码略少，但问题仍然存在。

UPD：将jt定义为const void(* const jt[])() = { print0，print1，print2，print3，print4 };并使函数static const inline没有帮助：http://ideone.com/97SU0

- skink

---

也许因为在后一种情况下函数是通过间接调用的方式被调用的？如果将jt[]声明为一个由5个指向const函数指针的const数组，会发生什么？ - Alexey Frunze

你能否尝试在第二个例子中将它声明为const吗？ 编译器必须假设它可能会更改为需要调用的内容。@Alex更快... - elmo

@Joulukuusi 是的，这正是我所想的。在第二种情况下，调用没有内联。(我不认为它们可以内联而不退化到第一种情况)。因此，你可能想要更改那个句子的措辞。 - Mysticial

@Alex，@Martin James，@elmo，没有帮助，还是有一个call。我马上会更新我的问题。 - skink

说实话，这是一款6502 8位处理器，具有一个字节的操作码，所以为什么不直接用汇编语言来实现模拟器呢？一个256字节的跳转表很容易实现。 - Martin James

Answer 1

编译器的作者们有很多工作要做。显然，他们会优先处理具有最大和最快收益的工作。

switch语句在各种代码中都很常见，因此对它们进行的任何优化都将对许多程序产生影响。

这段代码

jt[input](); 

这种优化在编译器设计者的TODO清单上并不常见，因此可能需要更长的时间才能得到实现。也许他们还没有找到值得努力进行优化的理由？这样做是否会获得任何已知基准测试的胜利？或者能否改进一些广泛使用的代码库？

- Bo Persson

Answer 2

由于函数指针数组是可变的。编译器决定不能假设指针不会被更改。你可能会发现C++的汇编代码不同，或者让jt保持不变。

- Matt Joiner

---

我并不完全认同这个观点。证明数组永远不会改变是微不足道的。它在main中被声明为局部变量，并且在main()内部从未被修改 - 它的地址也从未被获取。编译器是否会进行数据依赖分析则是另一回事。 - Mysticial

那样做并将jt声明为const不会改变任何东西。 - Michael Burr

谢谢！不幸的是，将jt的声明更改为const void (* const jt[])()也没有帮助。 - skink

Answer 3

我的猜测是，这种优化与您在switch之后立即使用return语句有关：优化器意识到它可以利用嵌入在print0..print4函数中的返回来减少call到jmp；所选printN内部CPU触发的ret作为main的返回。尝试在switch之后插入一些代码，看看编译器是否会用call替换jmp。

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

- Sergey Kalinichenko

---

谢谢！不过，即使在这种情况下编译器也会输出 jmp：http://ideone.com/FBHuZ - skink

哦，没错。我稍微修改了第一个文件：http://ideone.com/GJPQi 不过输出中仍然有“jmp”：http://ideone.com/F9AMo - skink

@Joulukuusi 但是所有的跳转都会导致共同的继续（尽管它出现在汇编输出的较早位置）。 - Sergey Kalinichenko

请提供一个最小的测试，如果可以的话？我似乎想不到一个有不同结尾的测试 - 如果我去掉 printf，编译器就会抛出其他部分。 - skink

@Joulukuusi 请尝试将一个 printf 替换为 puts，另一个替换为 fputs("...", stdout)，再将另一个替换为 fprintf(stdout, "...")，以避免共享调用的优化。 - Sergey Kalinichenko

Answer 4

第一个案例（通过 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 <printf@plt>
  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对都使用了8个字节，因此使用了(,%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 <scanf@plt>
  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  P.@.....`.@.....
 500a70 70054000 00000000 80054000 00000000  p.@.......@.....
 500a80 90054000 00000000                    ..@.....

请注意，当objdump打印数据段时，字节顺序是倒置的——如果您将它们翻转，您将得到print[0-4]()函数的地址。

编译器通过间接call调用目标——即表的使用直接在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"); }

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变量），那么没有任何东西可以强制编译器以使尾递归结果撤消此操作。

编辑2：

对于第一个示例，进行相同的更改（将input替换为argc并强制使用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 <printf@plt>
  40051e:       bf 41 06 40 00          mov    $0x400641,%edi
  400523:       31 c0                   xor    %eax,%eax
  400525:       e9 fe fe ff ff          jmpq   400428 <printf@plt>
  40052a:       bf 46 06 40 00          mov    $0x400646,%edi
  40052f:       31 c0                   xor    %eax,%eax
  400531:       e9 f2 fe ff ff          jmpq   400428 <printf@plt>
  400536:       bf 4a 06 40 00          mov    $0x40064a,%edi
  40053b:       31 c0                   xor    %eax,%eax
  40053d:       e9 e6 fe ff ff          jmpq   400428 <printf@plt>
  400542:       bf 4e 06 40 00          mov    $0x40064e,%edi
  400547:       31 c0                   xor    %eax,%eax
  400549:       e9 da fe ff ff          jmpq   400428 <printf@plt>
  40054e:       90                      nop
  40054f:       90                      nop

这种方法在某些方面略逊（执行两个jmp而不是一个），但在另一方面更好（因为它消除了static函数并内联了代码）。就优化而言，编译器基本上做了同样的事情。

- FrankH.

---

谢谢！我得到了非常接近的结果 - 汇编输出的链接在原始帖子中。然而，问题是 - 为什么编译器不会像第一种情况那样将第二种情况中的call优化为两个jmp？这将消除堆栈操作，这可能比两个jmp慢。 - skink

我不完全理解你的意思; 在这两种情况下，你都是通过call调用实际函数。也就是说，此处创建的main（）不是_tail recursive_（如果它使用jmp print ...而不是call print ...; retq，则是tail-recursive）。但其原因是main（）执行了return 0 - 因此它_不能是尾递归_。 - FrankH.

抱歉我的措辞很糟糕！在第一种情况下，编译器通过jmp [DWORD PTR L8[0+eax*4]]调用任何一个printX函数。在第二种情况下，这是通过call [DWORD PTR _jt.1677[0+eax*4]]完成的，并且每个printX函数都执行sub esp, 28和add esp, 28。我认为sub和add是多余的，如果编译器将call更改为两个jmp - 一个在printX标签内，一个回到call后的位置。 - skink

你期望的那个部分（“...一次返回到调用位置之后<调用的地方>”）如果你声明了一个跳转表变量是不可能发生的；这是因为在这种情况下编译器无法确定print[0-4]函数只有一个调用者。只有在switch()语句中才能确定这一点，这就是为什么编译器在这种情况下消除/内联static函数的原因。 - FrankH.

我认为我理解了一切，但是这里有一个问题 - “在这种情况下编译器无法确定print[0-4]函数只有一个调用者”。跳转表变量是main()中的局部变量，怎么可能会有多个调用者？ - skink

Answer 5

在间接call和随后的ret之间，后一个函数的代码是否什么都没做？如果间接调用的地址计算使用了一个寄存器，而该寄存器的值是后一个函数需要保留的（这意味着它必须在计算之前保存该值，并在一段时间后恢复该值），那么我不会感到惊讶。虽然可能将寄存器恢复代码移动到间接调用之前，但编译器只能在已经被编程为识别为合法机会的情况下执行这样的代码移动。

此外，虽然我认为这并不重要，但我建议例程不应该是inline，因为编译器无法以这种方式执行它们。

- supercat

---

谢谢！是的，它使用 eax 进行地址计算 - call [DWORD PTR _jt.1677[0+eax*4]]。紧接着这个操作（即在调用函数返回之后），出现了 xor eax,eax, leave 和 ret 操作指令。我不知道为什么必须保留 eax。顺带一提，我在问题中附上了汇编输出的链接。关于 inline 的建议 - 你能解释一下吗？ - skink

@Joulukuusi：返回值在eax中。由于编译器无法推断调用的函数返回时eax中会有什么值，因此它必须将eax加载为零。如果您从“void”函数中进行间接调用，或者调用返回值为“int”的函数并返回该函数返回的值，则可以消除“xor”，从而可能允许使用间接“jmp”而不是“call”。 - supercat

Answer 6

你对不同的代码进行了分析吗？我认为可以提出一个论点，即间接调用已经被优化了。以下分析是使用GCC 4.6.1针对x64平台（MinGW）完成的。

如果你看一下当使用jt[input]()时会发生什么，一个调用将导致执行以下代码序列：

• 间接调用其中一个printX()函数
• printX()函数设置printf()的参数，然后
• 跳转到printf()
• printf()调用将直接返回到“间接调用”的位置。

总共有3个分支。

当你使用switch语句时会发生什么：

• 每种情况都有一个指向自定义代码位的间接跳转（内联printX()调用）
• 'case handler' 加载适当的参数给 printf() 调用
• 调用 printf()
• printf() 调用将返回到 'case handler'，然后
• 跳转到 switch 的退出点（除了一个 case 处理程序外，其中退出代码是内联的 - 其他 case 跳转到那里）

总共有 4 个分支（在一般情况下）。

在两种情况下，你都有： - 一个间接分支（对于其中之一而言，它是一个调用，在另一个中是跳转） - 分支到 printf()（对于其中之一而言，它是一个跳转，在另一个中是调用） - 分支回调用站点

但是，当使用 switch 语句时，还有一个额外的分支来到达 switch 的“结尾”（在大多数情况下）。

现在，如果您实际上分析了这些内容，处理器可能会比间接调用更快地处理间接跳转，但我猜即使是这种情况，在基于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

这是基于 switch 实现生成的代码：

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

- Michael Burr

---

谢谢！我想对纯指令进行分析，但我找不到方法。我的汇编输出与你的略有不同——使用 jt[input]() 时会生成 call _printf（而不是你的 jmp printf）。此外，在调用 printf 之前和之后，还进行了一些堆栈对齐。这会有影响吗？ - skink

@Joulukuusi：我认为你正在生成32位x86代码，而我正在生成64位x64代码。似乎对于间接调用情况，x86代码生成略逊于x64代码生成。然而，我仍然不确定它最终是否比switch语句显着不优化（但也许是）。我认为栈调整是由于调用争用要求而进行的。这些调整可以在switch中被优化掉，因为它能够通过特定的指针进行单独的间接调用。 - Michael Burr

我认为原则上，编译器可以将jt[input]()调用“展开”为五个单独的直接调用，并最终得到与switch语句相同的代码，但正如Bo Persson所提到的那样，这种情况可能不常见，没有引起编译器维护者的注意。请注意，调用执行堆栈对齐的函数的x86代码仍具有与switch语句生成的“优化”代码类似的分支数（按我的计算，每种方式都有4个分支）。因此，在x86上它仍然可能与switch执行得几乎相同。 - Michael Burr

我在我的电脑上尝试对两种情况进行分析。以下是使用的源链接：http://ideone.com/WE5N4 http://ideone.com/OQJa8 我确保两个汇编输出都包含跳转表。sample.bin是一个随机的250MB zip档案。根据gprof，第一个程序运行了3.80秒，第二个程序运行了4.69秒。你认为我可以相信这个结果吗？ - skink

@Joulukuusi：20%的差异相当令人信服；这么大的差距也很令人惊讶。但是，这种情况通常会产生出人意料的结果。你是否运行了两种情况多次（交替运行），以查看结果是否一致？ - Michael Burr