汇编语言乱七八糟的优化

一句话快速解释

# 分支合并 (Branch Merging)

如果有两个判断的条件是一样的，那么可以把一个分支的东西全都提到另一个分支里面去，这样可以少做一次判断。

# 子表达式合并（Common Subexpression Elimination）

譬如判断$(a+b<5\wedge a+b>3)$ 时，可以先求子表达式$c=a+b$，再判断$(c<5\wedge c>3)$。

# 分支不变外提（Branch Invariant Code Hoisting）

互斥分支中需要做同样的操作，可外提。

# 分支强度折减（Branch Strength Reduction）

用更简单的加减法去替换乘除法，用代价更低的运算去等价替代更复杂的运算。

# 寄存器变量（Register Variable）

尽量多重复利用寄存器存储临时变量。编译器比人擅长此优化，它们使用全局寄存器着色算法。

# 分支预测（Branch Predicting）

很多处理器具备分支预测器，它是一个静态硬件电路，尝试预测下次分支并提前取指。当然可能预测错误，则需要放弃和重新取值。譬如循环跳出条件往往都是不成立的次数远大于成立的次数。对于程序员，将成立概率较小的分支写成向前跳转，将成立概率较大的分支写成向后跳转或不跳转，可以增加分支预测器成功的概率。

# 死分支消除（Dead Branch Elimination）

顾名思义，不可能进入的分支不用去判断。譬如很多时候 switch 分支的 default。这方面人比机器灵活擅长得多。

# 跳转消除（Jump Elimination）

如果跳转的结果就是下一条指令，则无需跳转，自然执行。

# 谓词执行（Predicate Execution）

某些处理器的指令中，可以携带一个条件判断，该条件判断成 立时指令才执行，不成立则指令看上去就是一个 NOP。这样，简单的分支就可以直接用那个条件判断表达，不需要一条真正的跳转指令。这种指令一般出现在 DSP、GPU 等向量处理器中，在 SSE、AVX 里面有时也能找到它，这是因为上述处理器的跳转惩罚都很大，如果分支预测不正确就更糟糕了。

# 归纳变数、强度折减（Induction Invariable，Strength Reduction）

譬如

1
2
3
4
5
6
7
8
9
10

for (int i = 1;i <= 5;i++){
	cout << i * 5;
}
//==>
int a = 0;
for (int i = 1;i <= 5;i++){
	a += 5;
	cout << a;
}

# 循环旋转（Loop Rotation）

do…while 的性能要比 while 好，因为只需要在结尾处检查条件。而 while 需要在开头处检查，并在结尾处跳回开头。因此可以考虑把 while 改为 if+do while。

# 循环倒转（Loop Reversal）

很多处理器都有自己的 do…while 指令，效率较高，譬如 8086 的 LOOP 指令。但它是把某个循环变量以此递减。所以考虑把循环都变成递减循环，然后使用处理器的特殊指令。

# 循环分裂 / 合并（Loop Fission/Fusion）

将循环中无数据依赖的部分单独拆出来作为一个独立的循环， 增加程序运行时的空间局部性，提高缓存性能。

不过，必须指 出的是，此时循环相关的条件判断以及跳转消耗相当于翻倍， 因此是否需要分裂循环 —— 甚至将原本分裂的循环合并起来 —— 要视处理器微架构而定。

# 循环展开、向量化（Loop Unrolling，Vectorization）

将循环体手动重复数次后，一次性地调整循环变量，再集中起来检查一次条件，以替代每次都要进行的检查。

展开后的循环体往往对 SIMD 指令非常友好。这时，如果机器有 SIMD 指令，便可发挥其并行处理优势，在一个循环之内处理大 量数据。

# 达夫设备（Duff’s Device）

将循环体手动展开后，与 switch-case 语句联用，达到跳入循环内 直接执行而无需处理额外部分的技巧。C 的语法允许这样写，但 现代编译器可能对此优化不佳。不过，汇编语言程序中程序员 往往可以手动优化，所以可以放心地使用这种结构。

https://belaycpp.com/2021/11/18/duffs-device-in-2021/

1
2
3
4
5
6
7
8
9
10
11

int i = head & 0xFFFC;
switch (head & 3) {
	do {
        case 0: c[i] = a[i] + b[i];
        case 1: c[i + 1] = a[i + 1] + b[i + 1];
        case 2: c[i + 2] = a[i + 2] + b[i + 2];
        case 3: c[i + 3] = a[i + 3] + b[i + 3];
        i += 4;
	} while (i < 1024);
}

# 循环不变量外提（Loop Invariant Hoisting）

与分支不变量外提类似，循环不变量外提将循环中无需重新计 算的部分提到循环之前一次性完成，原本会计算多遍的值现在 只要计算一遍就可以了，大大节省了计算量。

# 循环分支外提（Loop Unswitching）

将条件不变的分支提到 循环之外，避免在循环中反复分支。并产生了数个互斥的独立循环。

# 数据补齐（Data Padding）

对于那些有缺失而又被反复使用的核心数据，可以提前一次性填补它们的缺失部分，防止在循环中每次都需要补齐。

譬如（注意：此时 b 是按列优先存储的，而 a 是按行优先存储的）

1
2
3
4
5
6
7
8
9

for (int s = 0; s < 4; s++) {
    for (int i = 0; i < 64; i++) {
        for (int j = 0; j < 32; j++) 
            c[s][j][i] = a[s][j][i] + b[i][j];
        for (int j = 32; j < 64; j++) 
            c[s][j][i] = a[s][j][i] + vdef;
    }
}

一次性补齐为：

1
2
3
4
5
6
7
8
9
10
11
12

for (int i = 0; i < 64; i++) {
	for (j = 0; j < 32; j++)
		d[i][j] = b[i][j];
	for (j = 32; j < 64; j++)
		d[i][j] = vdef;
}
for (int s = 0; s < 4; s++) {
		for (int i = 0; i < 64; i++)
			for (int j = 0; j < 64; j++)
				c[s][j][i] = a[s][j][i] + d[i][j];
}

# 数据转置（Data Transposition）

当被反复使用的核心数据与其它数据的行列存储方式不一致时， 可以提前一次性将其转置，这样在循环中就可以使用与其它数 据同样的归纳变数来访问它了。当然，这会消耗额外的处理时 间。幸运的是，这个操作往往可以和数据补齐一起进行。

接上例，此时 b 是按列优先存储的，而 a 是按行优先存储的，则我们在数据补齐时就可以完成数据转置：

1
2
3
4
5
6
7
8
9
10
11
12

for (int i = 0; i < 64; i++) {
	for (j = 0; j < 32; j++)
		d[i][j] = b[j][i];
	for (j = 32; j < 64; j++)
		d[i][j] = vdef;
}
for (int s = 0; s < 4; s++) {
		for (int i = 0; i < 64; i++)
			for (int j = 0; j < 64; j++)
				c[s][j][i] = a[s][j][i] + d[j][i];
}

# 循环交换（Loop Interchanging）

如果嵌套循环中不含有任何数据依赖（最典型的是一对一的矩 阵数据处理），那么可以将外循环和内循环的位置颠倒过来。

接上例：

1
2
3
4
5
6

for (int s = 0; s < 4; s++) {
		for (int j = 0; j < 64; j++)
			for (int i = 0; i < 64; i++)
				c[s][j][i] = a[s][j][i] + d[j][i];
}

# 循环坍缩（Loop Collapsing）

如果在嵌套的循环中，两个相邻的内循环所处理的数据恰好在 存储地址上是相邻的（最常见的是二维数组的相邻行或者列、 以及三维数组的相邻平面，依此类推），那么外循环和内循环 就可以合并成同一个。

# 循环分块（Loop Blocking）

在一个数据量较大、超出缓存容量的循环中，热点数据无法整 个放入缓存，那么可以将热点数据分成几份，每个循环调用一 份热点数据并处理与这一部分热点数据有关联的部分数据，再 把各自的部分结果输出到合适的位置。所有循环运行完后，各 循环产生的部分结果拼合起来得到最终结果。

# 循环倾斜（Loop Skewing）

在不破坏数据依赖的前提下，调整循环的方向，使尽量多的数 据可以复用，并使尽量多的操作可以同时执行。这通常是将一 个按照行或列进行水平和垂直迭代的循环改为按照斜对角线 （数据依赖的平行向和法向）进行迭代。

# 过程合并（Procedure Merging）

当两个过程处理同样性质的数据或完成同样性质的操作，并总 是按照相同先后顺序被调用时，可以将两个过程合并成一个过 程，节约一次调用开销。

# 过程内联（Procedure Inlining）

当被调用者相对较短小、调用开销相对较大时，可以考虑将过 程直接嵌入调用者的指令序列，从而节约过程调用开销、提升 程序执行效率。

# 过程克隆（Procedure Cloning）

将一个处理不同范围 / 种类数据的过程分成两个，并且分别在两 个地方调用，这样在过程中就不需要做判断来决定进入哪个分 支来处理数据了。这可以节约潜在的判断分支。

# 循环嵌入（Loop Embedding）

当多数对过程的调用都是单体循环调用时，可以创建一个新过 程专用于循环调用：将循环移动到过程内部，并将循环次数当 成一个参数传递进去，以省去反复执行序言和尾声的开销。

# 包装收缩（Shrink Wrapping）

将过程的序言和尾声中的某些部分（通常是对寄存器的保护） 从过程头部和过程尾部移动到真正必要的地方去，从而仅在那 些需要它们的分支上执行它们，而在那些不需要它们的分支上 就不必执行它们了。这可以节约开销，尤其是当那些不需要它 们的分支被频繁执行时。

# 部分内联（Partial Inlining）

当一个过程本身较为复杂而不方便整体内联，但其中又有一部 分内容较简单的分支被频繁进入时，可以将这部分较简单的分 支内联，而较复杂的部分仍保持为一个独立的过程。此优化比 包装收缩更加极端，它使得部分分支连调用和返回的开销都避 免了。

# 尾递归优化（Tail Recursion Optimization）

当过程返回前的最后一个操作是调用它自己时，由于其栈框中 没有任何有效信息，因此可以在对自己的下一次调用中复用。循环的实质就是尾 递归。