A Simple Example to Show How GCC Compiler Optimizes the Operations on Scalar
1. 前言
众所周知，编译器能够对程序进行一定程度的优化，它使得程序员能够更专注地写高可读性的代码，实现快速、简便的开发。编译器对程序的优化包括但不仅限于对标量操作的优化、对函数调用的优化、对循环体的优化等。本文用一个非常简单的例子，分析编译器对标量操作的优化方式。本文假设读者都学习过计算机体系结构课程，文中的一些概念只会简单介绍，不会详细展开说明。编译器的优化可以细分成前端优化和后端优化，前端优化是机器无关的优化，后端的优化是机器相关的优化，本文将它们作为一个整体看待。
1.1 GCC与LLVM
C/C++语言的编译器中较为著名的有GCC和LLVM。GCC的全称为GNU Compiler Collection，在1987年第一次被正式released，它的特点是兼容更多的平台（尤其是旧的架构或系统）；LLVM的全称是Low Level Virtual Machine，是2000年启动的项目，在2005年正式有团队着手将它扩展到多个操作系统平台，它的特点是使用一个统一的语言（IR）作为多种高级语言的中间表示，有更好的可维护性和可扩展性。两个编译器各有优点，GCC有更好的性能优化和平台兼容性，LLVM有更好的可扩展性和可读性，还可以自己定制优化。本文使用的编译器为GCC。
1.2 机器环境
我使用机器的内核版本为：
$ uname -r
5.6.13-100.fc30.x86_64
我使用机器的GCC版本为：
$ gcc --version
gcc (GCC) 9.3.1 20200408 (Red Hat 9.3.1-2)
2. 生成汇编代码
C语言的编译可以分成四个步骤：Preprocessing、Compile、Assemble和Linking。
以下C代码（test.c）包括两个乘法和一个除法：
#include<stdint.h>
int main(){
uint32_t n = 100;
uint32_t x = n * 8;
uint32_t y = n * 31;
uint32_t z = n / 71;
return 0;
}
在分析其编译器优化过程之前，首先生成汇编代码。
Preprocessing：
gcc -E test.c -o test.i
Compile（生成汇编代码）：
gcc -S test.i -o test.s
得到test.s文件即为汇编代码。
初步观察汇编代码，对于赋值语句：
uint32_t n = 100;
其汇编代码为：
movl $100, -4(%rbp)
非常好理解，将\(100\)这个数字移动到-4(%rbp)寄存器中（这里用了立即数偏移寻址）。
而movl指令中的l表示long，\(4\) bytes（\(32\) bits），但是在现代计算机中long一般要用\(64\) bits来表示，这是为什么呢？这是一个命名的历史遗留问题，在最开始设计CPU指令时内存很小，就将\(4\) bytes用l表示，而\(8\) bytes用q（quad）表示。而代码中定义的类型为uint32_t，所以使用movl，如果类型为uint64_t，则使用movq。
3. 乘法的优化
对于第一个乘法语句：
uint32_t x = n * 8;
其汇编代码为：
movl -4(%rbp), %eax
sall $3, %eax
movl %eax, -8(%rbp)
第\(1\)行和第\(3\)行都是数值的移动，第\(2\)行为乘法运算。这里同样非常好理解，乘\(8\)相当于乘\(2^3\)，众所周知，相当于将二进制数左移\(3\)位。sal是算术左移指令，所以这个乘法运算用一个左移指令即可完成。
对于第二个乘法语句：
uint32_t y = n * 31;
其汇编代码为：
movl -4(%rbp), %edx
movl %edx, %eax
sall $5, %eax
subl %edx, %eax
movl %eax, -12(%rbp)
不难想到：\(n \times 31 = n \times 32 - n\)，编译器也是这么进行这个运算的，因为乘\(32\)的运算可以用一个算术左移完成。于是在第\(3\)行进行了乘\(32\)（左移\(5\)位）的操作，在第\(4\)行进行了一次减法操作，最终完成了乘法运算。
4. 除法的优化
前面对于乘法的优化都很简单，最后一个除法运算的优化才是真正需要思考的。
对于除法语句：
uint32_t z = n / 71;
其汇编代码为：
movl -4(%rbp), %eax
movl %eax, %edx
movl $3871519817, %eax
imulq %rdx, %rax
shrq $32, %rax
shrl $6, %eax
movl %eax, -16(%rbp)
有意思的事情来了，这一段汇编代码中没有div指令，却完成了一个除法运算。
第一步先从数学的角度思考它背后的原理，第二步再观察这段汇编代码如何利用这个原理。
对于数字\(\frac{n}{71}\)，如果将它乘上\(2^N\)再右移\(N\)位，得到的结果仍然是\(\frac{n}{71}\)。于是为了得到\(\frac{n}{71}\)，先进行一次乘法运算，再进行一次位移运算即可，乘法运算的过程表示为：
\[\frac{n}{71} \times 2^N = n \times \frac{2^N}{71} = n \times magic\_number\]当\(N=38\)时，\(magic\_number = 3871519817 = \frac{2^{38}}{71} + 1\)。
这里有两个问题：1. 为什么选择\(N=38\)？ 2. 为什么要加\(1\)？
对于问题1：为了保证精度且不会溢出。因为\(2^{38} / 71\)得到的结果恰好没有超过\(32\)位无符号整型的表示范围，如果选择再大一些会溢出；且如果\(N\)选择太小，会损失精度。
对于问题2：为了保证运算的正确性。因为\(\frac{2^N}{71}\)运算必然会向下取整，可能导致运算出错，而加\(1\)多出来的部分可以在右移操作中抹去。
思考到这里，背后的原理逐渐想明白了，编译器将一个除法运算分解为一个乘法运算和一个位移操作。
在阅读汇编代码之前，还有一个关于寄存器的知识点需要复习，即寄存器的设计：
rax是\(64\)-bit的寄存器，在2003年引入；eax是\(32\)-bit的寄存器，在1985年引入；ax是\(16\)-bit的寄存器，在1979年引入；
他们物理上的分布如下图所示：
当一个\(64\)位的数字放入rax中后，读取eax即可获得该数字的低位的\(32\)位，读取ax即可获得该数字的低位的\(16\)位。以上关系对于rdx、edx和dx同理，rdx是\(64\)-bit的寄存器，edx是\(32\)-bit的寄存器，dx是\(16\)-bit的寄存器。
接下来可以回头阅读汇编代码，看看它是如何完成这个除法运算的：
-
第\(1 \sim 2\)行代码将数字\(n\)放到
edx寄存器中。 -
第\(3\)行代码把数字\(\frac{2^{38}}{71} + 1\)放到
eax寄存器中。 -
第\(4\)行代码进行乘法运算\(n \times (\frac{2^{38}}{71} + 1)\)，这是两个\(32\)-bit值的乘法，可能会溢出到\(64\)-bit中，因此
imul指令是对两个\(64\)-bit的寄存器的值进行运算，得到的结果放到rax寄存器中。 -
第\(5\)行代码将
rax寄存器（\(64\)-bit）的值算术右移\(32\)位，那么rax寄存器的高位的\(32\)位全部为\(0\)，值全部跑到eax寄存器（\(32\)-bit）中了。 -
第\(6\)行代码将
eax寄存器的值算术右移动\(6\)位，所以两个算术右移总共移动了\(38\)位，满足背后的数学原理，最终的结果在eax寄存器中。 -
第\(7\)行代码是简单的结果拷贝工作。
以上是编译器对一个简单的除法运算的优化，对于计算机底层运算来说，除法运算的花费比乘法和加减法要更多，所以能够避免除法（包括取模）就尽量避免。当然加减乘除运算属于最基本的运算，编译器对这些运算的优化已经做得很好了，不需要程序员操心。
5. 总结
编译器对加减乘除的优化是最基本的优化，这里的展示也都是非常简单的例子，学习它们虽然对编程没有太多实质帮助，但了解汇编代码执行的过程总是没有坏处。编译器同样会对函数调用、循环体进行各种各样的优化，感兴趣的话可以阅读LLVM项目的文档。