goto die？ 那个 goto 到底能不能用啊？

写在开始之前

今年以系统程序为主题跳进 Software Development 算是一个大胆的尝试，对於一个大学时期只有写过 web 与一些简单程序的我来说，能在得奖名单上看到自己的作品真的让我又惊又喜。
在学生时期拿到铁人赛的个人奖项一直都是我的终极目标之一，我想以自己为例鼓励大家跳脱舒适圈，或许不经意间就能为你的生活加入许多惊喜！

更新文章哪里看

我预计会再补上 fork, wait, exit...等系统呼叫的文章，为多执行绪程序做一些基础的铺垫。
考虑到铁人发文按钮过一阵子就会消失，若之後有文章结构上的大调整或是有其他新文章，我都会优先更新在 AwesomeCS wiki 上，以确保大家可以按照我所期望的顺序学习系统程序，还请大家见谅 <(_ _)>

=== 废话结束 ===

是否要在 C 程序中使用 goto，一直都是工程师之间热烈讨论的话题之一。有人说使用 goto 会破坏程序结构、也有人说都有回圈了，何必使用 goto 呢？

goto 於大型软件专案的应用

因为实验室开发的关系，笔者最近阅读了一个大型的 c 语言专案，并且碰巧读到了 Computed goto for efficient dispatch tables 这篇文章，让我对 goto 有了更深入的认知。
一般来说，goto 如果出现在 C 语言专案，那它有很大的可能是被应用在：

• exception handling
• computed goto

前者可以方便开发者在 C 语言程序出错时回收动态分配的记忆体，或是进行对应的错误处理以确保程序下次进入该函式时仍可以正常工作。
试想，如果一家公司需要开发一个高效能的网路程序，并且要确保该程序可以稳定且持续的工作，这时在软件中可能发生的错误都不能被轻易放过。

以 2021 年 10 月初 Facebook 断线的例子来看，Facebook 因长达六小时的断线，连带损失估计超过 9 亿美元，由此可见商业化软件的稳定性是非常重要的。

至於後者 computed goto，才是笔者想要在本文与大家分享的重点！

computed goto

在先前的浅谈分支预测与 Hazards 议题一文中，我们可以归纳出一个重点： 如果分支预测失败，会导致流水线中已经排序的指令流被清除，这也就表示我们的处理器不止做了白工，还要把正确的指令填充回流水线上面。

再谈 branch prediction

现代处理器可能引入如上图所示的分支预测方法，处理器会以 address 为索引，检索 Pattern history table 上的历史纪录进一步的做出预测。

computed goto 的应用

computed goto 适用於取代 switch case 为基底的 dispatcher，因为 switch 仅会以一个基底作为分派任务的参考，这样子说可能会有点抽象，让我们用程序码来进一步了解这个概念：

while (1) {
        switch (code[pc++]) {
            case OP_HALT:
                return val;
            case OP_INC:
                val++;
                break;
            case OP_DEC:
                val--;
                break;
            case OP_MUL2:
                val *= 2;
                break;
            case OP_DIV2:
                val /= 2;
                break;
            case OP_ADD7:
                val += 7;
                break;
            case OP_NEG:
                val = -val;
                break;
            default:
                return val;
        }
    }

如果以现代处理器的分支预测方式来看，同一段程序码在不同的周期可能会 jump 到不同的地方，这样会导致分支预测的成功率下降，并且需要反覆的填充正确的指令到流水线上面。

那 computed goto 会怎麽做呢？让我们一起看下去：

int interp_cgoto(unsigned char* code, int initval) {

    static void* dispatch_table[] = {
        &&do_halt, &&do_inc, &&do_dec, &&do_mul2,
        &&do_div2, &&do_add7, &&do_neg};
    #define DISPATCH() goto *dispatch_table[code[pc++]]

    int pc = 0;
    int val = initval;

    DISPATCH();
    while (1) {
        do_halt:
            return val;
        do_inc:
            val++;
            DISPATCH();
        do_dec:
            val--;
            DISPATCH();
        do_mul2:
            val *= 2;
            DISPATCH();
        do_div2:
            val /= 2;
            DISPATCH();
        do_add7:
            val += 7;
            DISPATCH();
        do_neg:
            val = -val;
            DISPATCH();
    }
}

• 在 function 内宣告变数时加入 static 关键字可以使变数的生命周期延长至程序结束

在 C/C++ 中，在不同的地方使用 static 可能会带来不同的效果，使用上需要特别注意！

• unary operator && 是 gcc 提供的扩展，它可以搭配 label 使用以取得明确的跳转位址。
• 配合 goto 可以让程序访问 code[] 的结果直接跳转到它对应的操作。

这样做的好处显而易见，computed goto 把 jump 的操作分成了好几部分，只要正确的访问 dispatch table，我们的处理器就能更精准的预测到正确的分支。

真实世界的例子

Computed goto for efficient dispatch tables 一文有提到 computed goto 被应用到了哪些知名的软件上：

• Ruby 1.9 (YARV): also uses computed goto.
• Dalvik (the Android Java VM): computed goto
• Lua 5.2: uses a switch

此外，由 Jserv 老师主导开发的 rv32emu-next 同样引入了 computed goto 的实作，详细手法可参考：

• rv32emu-next PR#2
• 2020q3 专题: RISC-V 模拟器

使用前请详阅公开说明书

由於 unary operator 是 gcc 特别提供的扩展，如果你的 C 语言专案不是由 gcc 编译，或是有人下载了你的原始码且采用其他编译器进行编译就有可能会造成错误。
因此，在使用时可以考虑：

• 写好 makefile，避免有使用者做出超出预期的行为
• 针对编译器类别做侦测，如果目标编译器非 gcc，则使用一般的 switch case

最後，可以在编译时加入 -fno-gcse 与 -fno-crossjumping，让 gcc 优化你的原始码。

Reference

• Computed goto for efficient dispatch tables
• What does a && operator do when there is no left side in C?
• 你所不知道的C语言: goto 和流程控制篇