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

不影响语义的前提下编译器可以任意重排代码顺序；

在乱序执行（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（这里正好是棵树，特例了）：

xyz48

\ / \ /

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

pdg是电子书格式。

这种格式的文件，首先要使用专业的阅读器进行打开，虽然说下载专业阅读器的方法滑歼是比较简单的，但是专业的阅读器下载之后有一系列的激活工具或者是账号登录的问题，如果不是专业的阅读用户，则不必申请相关的账号，如果是专业的用户，可以去申请一些相关的账号，这样可以保护阅读信息。打开pdg有3种方式：

1、使用超星阅读运源器直接打开文件；

2、使用专业的转化格式的转化工具；

3、使用超星信悄冲阅读器转换文件。

---