理解C语言-2:指令执行 English Version

简介

上一篇主要描述了C语言如何将待处理的数据建模成变量。有了变量，接下来需要拆解的就是如何使用他们。

指令式编程

一步步告诉机器如何去做，这是指令式编程的精髓。人们特别喜欢将程序比喻成菜谱：

将西红柿洗净后去皮、去蒂，切片待用
把鸡蛋打入碗中，加盐，待用
炒锅放油3汤匙烧热，将鸡蛋放入锅中炒熟
下西红柿片煸炒，放盐、糖炒片刻，出锅

和以下main函数中的语句某种意义上是相通的。

int main() {
    int tomato = 1;
    int egg = 2;
    int dish = a + b;
    return dish;
}

在这个思想的指导下，我们从设计最简单的元素入手来表达这些操作。

操作符和表达式

假设你接到的第一个任务是让计算机帮你计算”1+2”，你该如何表达它？
估摸着你会白我一眼：”这还用想吗？当然直接写作1+2咯。”

Bingo，这种表达已经不能再简化了。让我们尝试对”1+2”进行抽象建模：
显然，1和2是同一种元素，”+”是另一种元素。姑且就把它们称做操作数和操作符吧。”1+2”把这两种元素组合到了一起，称作表达式。

操作符的本质

根据操作符的实际功能，我们大体可以把它们分成算术/关系/逻辑/赋值/取地址等几大类。操作符描述了机器具体的操作，因此往往能够在汇编指令中直接找到对应的指令，例如：

汇编指令	C运算符
add	+（加法）
sub	- (减法)
and	&&（逻辑与）
mov	=（传送赋值）
lea	&（取地址）

再强调一下，每个操作符建模的是特定的操作。

表达式的本质

表达式建模的是求值过程：它将操作数通过操作符（也可以没有）组合在一起，并按照一定顺序求值。

最简表达式
一个字面量或者变量即是一个最简单的表达式，它的值就是自己（例如12或者变量a）。
支持嵌套
操作数代表运算需要的值，因而可以是表达式。表达式通过嵌套可以变得相当复杂。
求值顺序
如何求值一个复杂表达式的依据是操作符的优先级和结合性（当遇到相同优先级的操作符时），如果需要根据实际情况改变运算顺序，就需要括号的帮忙。

举个例子：
表达式1+2*3描述的操作是先乘法后加法。如果想先做加法，在这种中缀表达法里，不得不加入括号：(1+2)*3。如果想简化表达式，去掉括号带来的复杂度，则可以引入逆波兰式（后缀表达法）：

中缀表达	后缀表达
1+2*3	1 2 3 * +
(1+2)*3	1 2 + 3 *

由于从左到右扫描逆波兰式时借助堆栈可以方便的进行求值运算，逆波兰式常被解释器内部使用。中缀表达式则因为便于人类书写阅读而作为程序语法存在。

二叉树可以作为一种中转数据结构将中缀表达法转换成后缀表达法（单目操作符/多操作数的运算符都可以转化为双目运算符）。

语句

上文提到的菜谱由多个步骤构成，步骤之间可能存在特定的执行顺序。程序也有相同的需求，我们引入语句来建模这种控制流程。

为了方便语法上区分语句，C语言要求语句间用’;’分隔。

控制流

最常见的有以下四种控制流：

顺序
把多条语句用”{}”包裹起来就自然声明了语句间的顺序执行。这样的一组语句也叫复合语句。
条件
根据表达式的真假决定一组语句是否执行。
循环
根据表达式的真假决定是否重复执行一组语句。
跳转
无条件将控制流转向特定语句（例如goto/continue/break/return）。
需要注意goto语句的目标label必须和变量一样处于该语句的引用环境中（引用环境的说明具体见下一节）。

在汇编语言中，控制程序执行流的基石是rip的自动增长（即默认顺序执行）和跳转：

1	jmp addr // change ip to addr

上述除顺序执行之外的所有控制流都可以转换成类似jmp一族指令（条件和循环通过条件跳转实现）。

引用环境（referencing environment）

语句中的表达式可以引用已经声明的变量，因此，每一条语句都对应一个可见变量的集合叫做引用环境。

我更喜欢把引用环境称为引用上下文，因为和自然语言一样：

你和我是好朋友。

这句话中的”你”需要一个语境才能确定指的是谁。

引用上下文和上一篇中提到的变量作用域实际是相同的概念：只不过变量作用域是从变量角度提及，而引用上下文是从引用变量的语句角度提及。

那么C语言如何确定语句对应的引用上下文呢？答案是文本作用域（静态作用域）。

在C语言中，每一个复合语句（用”{}”括起来）就对应一个作用域。因此函数/循环/选择语句等都具有自己的作用域。
作用域可以嵌套，语句由内而外依次搜索每个作用域中声明的变量。内层作用域声明的变量会覆盖外层作用域的同名变量。

同样举一个例子：

int main() {
    int a = 1;
    int b = 2;

    if (a == 1) {
        int a = 2;
        a == b;
    }
}

对应的汇编代码：

push   %rbp
mov    %rsp,%rbp
movl   $0x1,-0x4(%rbp)  ; set a = 1
movl   $0x2,-0x8(%rbp)  ; set b = 2
cmpl   $0x1,-0x4(%rbp)  ; a == 1?
jne    40050c <main+0x1f>  
movl   $0x2,-0xc(%rbp)  ; inner a = 2
pop    %rbp
retq

这里的重点是静态作用域在编译阶段即可确定语句的引用环境，从而检查出潜在的错误引用。
相对的，还有一些语言使用与静态作用域相对的动态作用域，语句不再通过静态代码决定作用域嵌套关系，而是在运行时通过追踪调用链决定。

引入函数

此刻，你手上已有了指挥计算机所必需的所有基础工具，利用语句操作变量，你就可以命令计算机完成任何你想得到的计算。
美中不足的是，代码中总有一些语句重复出现，它们做的事情大致相同，只是每次处理的数据不同。反复输入相同的语句换谁感到恼火。程序员是世界上最懒的人，嗯，是时候该考虑效率了。

为了解决这个问题，C语言引入函数（正式的称谓是子程序，函数是子程序的一种实现）：把相同的代码片段定义成函数体，把变化的数据定义成参数。每次调用函数时传入不同的参数值即可得到相应结果。

调用约定

嵌套调用函数的过程（A调用B，B调用C）具有先进后出的特征，因此使用堆栈来保存调用函数相关的数据（称为活动记录Active Record）便水到渠成。
为了规范不同的编译器在特定架构上布局和使用栈帧的的细节，平台制定了调用约定来描述调用函数和被调用函数之间的交互细节。调用约定的关注点包括：

如何传递实参以及传递的顺序
如何传递被调用函数的返回值
被调用函数需要为调用者保存哪些寄存器的值
调用完成后由谁来清理堆栈，恢复调用者的执行

根据GNU gcc的官方文档，gcc在x86架构的Linux机器上遵循名为sysv_abi的调用约定，相关的内存布局如图1所示：

图1 堆栈内存布局

可见在一个栈帧中，内存地址由高到低增长，依次进栈的元素有：

调用函数的返回地址（rip）
调用函数的栈底地址（bsp）
函数的本地变量预留空间
形式参数的预留空间

让我们举例具体说明：

int callee(int a, int b) {
    int c = 1;
    return c;
}

int main() {
    int a = 1;
    int b = 2;

    return callee(a, b);
}

在amd64平台上按照64位汇编得到代码如下：

// callee
push   %rbp  ; save frame base (8bytes)
mov    %rsp,%rbp ; create new frame base
mov    %edi,-0x14(%rbp) ; get argument a (4 bytes)
mov    %esi,-0x18(%rbp) ; get argument b (4 bytes)
movl   $0x1,-0x4(%rbp) ; set local var c = 1 (4 bytess)
mov    -0x4(%rbp),%eax ; set return value
pop    %rbp
retq

// main
push   %rbp ; save old frame base (8 bytes)
mov    %rsp,%rbp  ; create new frame base
sub    $0x10,%rsp  ; allocate space for local vars (16 bytes)
movl   $0x1,-0x4(%rbp)  ; set local var a = 1 (4 bytes)
movl   $0x2,-0x8(%rbp)  ; set local var b = 2 (4 bytes)
mov    -0x8(%rbp),%edx  
mov    -0x4(%rbp),%eax
mov    %edx,%esi  ; pass argument b
mov    %eax,%edi  ; pass argumnet a
callq  4004ed <callee> ; call will push rip (8 bytes) to stack
leaveq ; set rsp = rbp then pop rbp (clean up) 
retq

由此解释一些细节：

实参按照从右到左（RTL）按照预设的优先级分配寄存器传递（按照实际情况也可以通过堆栈传递，细节可以查阅手册）
返回值通过eax寄存器传递（观察callee设置返回值）
被调用函数为本地变量预留的空间需要按16bytes对齐（观察callee中本地变量分配位置）
在返回前由调用者负责清理自身的堆栈空间（观察main的leaveq）

最后要说明的是：

通过在每个栈帧中保存上一个栈帧基址（bp），实际上构成了一个运行时函数调用的链表，在支持动态作用域的语言中即通过该链表搜索引用环境
在支持嵌套定义函数的语言（C语言不支持）中，需要在栈帧中额外记录静态代码中的父函数，以搜索引用环境

函数声明

ANSI C要求在调用函数前需要像变量一样声明函数原型（提供必要的参数和返回值类型信息）。
如果编译下述代码：

int func(int a);

int main() {
    int d[5];
    d = func(1);
    return 1;
}

会产生错误：

extern_func_decl.c: In function ‘main’:
extern_func_decl.c:5:7: error: incompatible types when assigning to type ‘int5’ from type ‘int’

函数原型提高了程序的健壮性，方便编译器检查潜在的错误。

内存布局

函数作为可执行代码，其包含的代码片段布局在text段中。
对应的函数名会在符号表中拥有一个条目，具体可以参看理解C语言-3:编译链接。

结论

本文讨论了构成C语言控制流的各种元素：操作符，表达式，语句以及函数，并介绍了如何通过调用栈是实现函数的嵌套调用。
这里再做两点补充：

堆栈

由于堆栈保存了调用链，并发执行代码需要多个堆栈的支持（同一个进程的每个线程都有自己的执行堆栈）。
即使不是为了并发，Linux也区分了用户程序的用户态堆栈和内核态堆栈（具有不同的执行权限）。

协程

普通函数只有一个入口，如果一个函数的控制流有多个入口（可以暂停和恢复其执行），就衍生出了协程（多个这样的协程可以显式地相互跳转）。协程间的切换发生在用户态，由用户指令显式触发；对应的，线程间的切换发生在内核态，由内核调度器控制。
实现协程有很多种方法，主要原理都是在堆上保存某个栈帧（即保存函数某个时间点的执行状态），未来在栈上恢复执行。

参考文献

系列推荐

发布于 2018-03-24

tags:

{ 编码 }

{ 沉思 }

{ C语言 }

{ 指令执行 }

{ 指令式编程 }

{ 操作符 }

{ 操作数 }

{ 表达式 }

{ 语句 }

{ 控制流 }

{ 函数 }

{ 调用约定 }

{ 活动记录 }