间接分支

在汇编过程中,所有标签(labels)都将转换为(绝对或相对)地址,然后编码到跳转指令中。

你还可以通过存储在寄存器中的变量值进行跳转,称为计算跳转(computed jump):

jmp rax

这里有一些与动态语言和实现更复杂的控制流有关的有趣例子。

多路分支

如果你已经忘记了switch语句的用法,这里有一个美国评分系统中计算GPA的小程序:

switch (grade) {
case 'A':
return 4.0;
break;
case 'B':
return 3.0;
break;
case 'C':
return 2.0;
break;
case 'D':
return 1.0;
break;
case 'E':
case 'F':
return 0.0;
break;
default:
return NAN;
}

我个人不记得上一次在非教育场景下使用switch是什么时候了。一般来说,switch语句等价于if, else-if, else if, elsen-if ...的序列,因此许多语言甚至没有switch。尽管如此,这种控制流结构对于实现解析器、解释器和其他状态机非常重要,这些状态机通常由单个while (true)循环和内嵌的switch(state)语句组成。

当变量可以取值的范围有限时,我们可以利用计算跳转技巧。我们可以创建一个分支表(branch table)代替n个条件分支,其中包含指向可能的跳转位置的指针或偏移量,然后使用[0,n)[0,n)范围内state变量作为索引对其进行取值。

编译器会在数值密集地排列在一起时使用这种技术(不一定是严格顺序排列,但在必要时会在表中留有空白字段)。它也可以通过computed goto显式实现:

void weather_in_russia(int season) {
static const void* table[] = {&&winter, &&spring, &&summer, &&fall};
goto *table[season];

winter:
printf("Freezing\n");
return;
spring:
printf("Dirty\n");
return;
summer:
printf("Dry\n");
return;
fall:
printf("Windy\n");
return;
}

对于编译器来说,基于switch的代码并不总是能直接进行优化,因此在状态机的上下文中,通常直接使用goto语句。glibc中与I/O相关的部分充满了这样的例子。

动态调用

间接分支也有助于实现运行时多态性。

考虑一个经典的例子,我们有一个Animal的抽象类,含有一个虚拟的.speak() 方法,以及两个具体的实现:Dog会汪汪叫,Cat会喵喵叫:

struct Animal {
virtual void speak() { printf("<abstract animal sound>\n");}
};

struct Dog {
void speak() override { printf("Bark\n"); }
};

struct Cat {
void speak() override { printf("Meow\n"); }
};

我们想创建一个动物,在不事先知道它的类型的前提下,调用它的.speak()方法,该方法应该以某种方式调用正确的实现:

Dog sparkles;
Cat mittens;

Animal *catdog = (rand() & 1) ? &sparkles : &mittens;
catdog->speak();

有很多方法可以实现这种行为,C++使用虚方法表(virtual method table)来实现。

对于Animal的所有具体实现,编译器会填充它们所有的方法(即它们的指令序列),以便所有类都具有相同的长度(通过在ret后面插入一些填充指令),然后将它们按顺序写入指令内存段中的某个位置。然后,在结构/类中(即所有实例中)添加运行时类型信息(run-time type information)字段,其本质上只是指向类的虚拟方法的正确实现的内存区域的偏移量。

通过虚方法调用,从结构/类的实例中提取偏移字段,并使用它进行正常的函数调用,因为每个派生类的所有方法和其他字段都具有完全相同的偏移。

当然,这会引入一些代价:

  • 由于和分支预测失败相同的流水线刷新(pipeline flush),你可能需要多花费约15个时钟周期。
  • 编译器很可能无法内联函数调用本身。
  • 类大小会增加了若干字节(取决于具体实现)。
  • 二进制大小本身会增加一点。

由于这些原因,在性能关键型应用程序中通常避免使用运行时多态。