编译器生成的汇编语句执行顺序为什么与C代码顺序不同?

来自CSAPP 3.5.4书中没有解释原因。C语言不是按顺序执行的吗?难道编译器是知道改变执行顺序不影响计算结果的情况下才这么做的?编译器有那么神吗?
关注者
403
被浏览
23652
先把题主截的图引用进来保存着上下文:


不影响语义的前提下编译器可以任意重排代码顺序;
在乱序执行(Out-of-Order)的CPU里,机器码的执行也可以不按照你在“汇编”层面上看到的顺序执行,只要不影响语义。
所以说这些中间步骤的顺序,作为底层细节平时不需要那么在意——它们多半跟原始源码的顺序是不一样的。

现代优化编译器优化的思路之一是“基于依赖的优化”(dependence-based optimization)。题主引用的CSAPP的例子:
int arith(int x, int y, int z) {
  int t1 = x + y;
  int t2 = z * 48;
  int t3 = t1 & 0xFFFF;
  int t4 = t2 * t3;
  return t4;
}
所有涉及运算的值都是局部标量变量(local scalar variable),这是最便于编译器做分析的情况,所有依赖都可以显式分析。
由于整个函数没有分支,这里也不需要讨论控制依赖(control dependence),只要讨论数据依赖(data dependence)就好。
把数据依赖图画出来是个DAG(这里正好是棵树,特例了):
 x    y    z    48
  \  /      \  /
   t1 0xFFFF t2
    \  /    /
     t3    /
       \  /
        t4
优化必须要满足的约束是:每个节点求值之前,其子节点(依赖的数据源)必须要先求了值。
显然,t1和t2之间没有依赖关系,它们的相对求值顺序怎样重排都没关系。

有本我很喜欢的书,里面讲的是各种基于依赖的优化:Optimizing Compilers for Modern Architectures - A Dependence-based Approach

以上是理论部分。

================================================================

下面来看例子。

我们可以用一个实际编译器来看看CSAPP的例子编译出来的结果:
	.text
# -- Begin  arith
	.p2align 4,,15
	.globl arith
	.type	arith, @function
arith:
	.p2align 4,,7
/*.L0:*/                          /* Block BB[54:2] preds: none, freq: 1.000 */
	movl 8(%esp), %edx               /* ia32_Load T[139:10] -:1:22 */
	addl 4(%esp), %edx               /* ia32_Add Iu[141:12] -:2:14 */
	movzwl %dx, %edx                 /* ia32_Conv_I2I Iu[142:13] -:4:15 */
	imull 12(%esp), %edx             /* ia32_IMul Iu[143:14] -:5:15 */
	leal (%edx,%edx,2), %eax         /* ia32_Lea Iu[144:15] -:5:15 */
	shll $0x4, %eax                  /* ia32_Shl Iu[146:17] -:5:15 */
	ret                              /* ia32_Return X[152:23] -:6:3 */
	.size	arith, .-arith
# -- End  arith
这里用的是libFirm。可见它跟CSAPP书里所说的汇编的顺序又有所不同。这也是完全合理的。
这个编译结果的顺序是:
edx = y;
edx += x;
edx = zeroextend dx; // edx = edx & 0xFFFF
edx *= z;
eax = edx * 3;
eax <<= 4; // eax = eax * 16
也是完全符合依赖关系的约束的一种顺序。
之所以用libFirm举例是因为它的中间表示(Intermediate Representation)是一种程序依赖图(Program Dependence Graph),可以很方便的看出控制与数据依赖。把CSAPP那里例子对应的libFirm IR画出来,是这个样子的:
(这张图跟我前面画的数据依赖图正好是左右翻转的,不过意思一样。
Arg 0、1、2分别代表x、y、z。白色方块是普通数据节点,黄色方块是常量节点,蓝色方块是内存相关节点,红色方块是控制流节点,粉红色方块是特殊的开始/结束节点。)

某版LLVM生成的代码:
; ModuleID = '/tmp/webcompile/_16355_0.bc'
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-ellcc-linux"

; Function Attrs: nounwind readnone
define i32 @arith(i32 %x, i32 %y, i32 %z) #0 {
entry:
  %add = add nsw i32 %y, %x
  %mul = mul nsw i32 %z, 48
  %and = and i32 %add, 65535
  %mul1 = mul nsw i32 %mul, %and
  ret i32 %mul1
}

attributes #0 = { nounwind readnone "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = !{!"ecc 0.1.10 based on clang version 3.7.0 (trunk) (based on LLVM 3.7.0svn)"}
最终生成的x86汇编:
	.text
	.file	"/tmp/webcompile/_15964_0.c"
	.globl	arith
	.align	16, 0x90
	.type	arith,@function
arith:                                  # @arith
# BB#0:                                 # %entry
	movl	8(%esp), %eax
	addl	4(%esp), %eax
	movzwl	%ax, %eax
	imull	12(%esp), %eax
	shll	$4, %eax
	leal	(%eax,%eax,2), %eax
	retl
.Ltmp0:
	.size	arith, .Ltmp0-arith


	.ident	"ecc 0.1.10 based on clang version 3.7.0 (trunk) (based on LLVM 3.7.0svn)"
	.section	".note.GNU-stack","",@progbits

GCC 4.9.2 x86-64:
arith(int, int, int):
	leal	(%rdx,%rdx,2), %eax
	addl	%edi, %esi
	movzwl	%si, %esi
	sall	$4, %eax
	imull	%esi, %eax
	ret

Zing VM Server Compiler x86-64:

# edi: x
# esi: y
# edx: z
movl %edx, %eax
shll $0x4, %eax
leal (%rsi, %rdi, 1), %ecx
shll $0x5, %edx
addl %edx, $eax
movzwl %ecx, %edx
imull %edx, %eax

微软Visual C++ 19.10.24629 for x64:
# ecx: x
# edx: y
# r8d: z
lea      eax, DWORD PTR [rcx+rdx]   # eax = t1 = x + y
movzx    ecx, ax                    # ecx = t3 = t1 & 0xFFFF
imul     ecx, r8d                   # ecx = t3 * z
lea      eax, DWORD PTR [rcx+rcx*2] # eax = (t3 * z) * 3
shl      eax, 4                     # eax = (t3 * z) * 3 * 16
ret      0
非常干练,赞。这组指令的构成跟GCC的做法很相似。