顺序、条件、循环语句的底层解释(机器语言级解释)

初级程序员讲究的是术,只知道如何用关键字去拼凑出领导想要的功能;高级程序员脸的是道,理解了底层的逻辑,不仅把功能做的漂漂亮亮,心法也更上一层楼。

顺序结构

数据传送指令

我们都清楚,绝大多数编译器都把汇编语言作为中间语言,把汇编语言程序变成可运行的二进制文件早就解决了,所以现在的高级语言基本上只需要把自己翻译成汇编语言就可以了。

汇编指令总共只有那么多,大多数指令都是对数据进行操作,比如常见的数据传送指令mov。不难理解,被操作数据无非有三种形式,立即数,即用来表示常数值;寄存器,此时的数据即存放在指定寄存器中的内容;内存引用,它会根据计算出来的地址访问某个内存位置。

需要注意的是,到了汇编层级,就不像高级语言那样随随便便int就能和long类型的数据相加减,他们在底层所占有的字节是不一样的,汇编指令是区分操作数据大小的,比如数据传送指令,就有下面这些品种(x86-64 对数据传送指令加了一条限制:两个操作数不能都指向内存位置)。

image.png

压栈与弹栈

对于栈,我想不必多讲,IT 行业的同学都清楚,它是一种线性数据结构,其中的数据遵循“先进后出”原则,寄存器%rsp保存着栈顶元素的地址,即栈顶指针。一个程序要运行起来,离不开栈这种数据结构。

栈使用最多的就是弹栈popq和压栈pushq操作。比如将一个四字值压入栈中,栈顶指针首先要减 8(栈向下增长),然后将值写到新的栈顶地址;而弹栈则需要先将栈顶数据读出,然后再将栈指针加 8。所以pushqpopq指令就可以表示为下面的形式。

// 压栈
subq $8, %rsp
movq %rbp, (%rsp)

// 弹栈
movq (%rsp), %rax
addq $8, %rsp

其他还有算术、逻辑、加载有效地址、移位等等指令,可以查阅相关文档了解,不作过多介绍,汇编看起来确实枯燥乏味。

条件结构

前面讲的都是顺序结构,我们的程序中不可能只有顺序结构,条件结构是必不可缺的元素,那么汇编又是如何实现条件结构的呢?

首先你需要知道,除了整数寄存器,CPU 还维护着一组条件码寄存器,我们主要是了解如何把高级语言的条件结构转换为汇编语言,不去关注这些条件码寄存器,只需要知道汇编可以通过检测这些寄存器来执行条件分支指令。

if-else 语句

下面是 C 语言中的if-else语句的通用形式。

if(test-expr){
    then-statement
}else{
    else-statement
}

汇编语言通常会将上面的 C 语言模板转换为下面的控制流形式,只要使用条件跳转和无条件跳转,这种形式的控制流就可以和汇编代码一一对应,我们以 C 语言形式给出。

    t = test-expr;
    if(!t){
        goto false;
    }
    then-statement;
    goto done;
false:
    else-statement;
done:

但是这种条件控制转移形式的代码在现代处理器上可能会很低效。原因是它无法事先确定要跳转到哪个分支,我们的处理器通过流水线来获得高性能,流水线的要求就是事先明确要执行的指令顺序,而这种形式的代码只有当条件分支求值完成后,才能决定走哪一个分支。即使处理器采用了非常精密的分支预测逻辑,但是还是有错误预测的情况,一旦预测错误,那将会浪费 15 ~ 30 个时钟周期,导致性能下降。

在流水线中,把一条指令分为多个阶段,每个阶段只执行所需操作的一小部分,比如取指令、确定指令类型、读数据、运算、写数据以及更新程序计数器。流水线通过重叠连续指令的步骤来获得高性能,比如在取一条指令的同时,执行它前面指令的算术运算。所以如果事先不知道指令执行顺序,那么事先所做的预备工作就白干了。

为了提高性能,可以改写成使用条件数据传送的代码,比如下面的例子。

v = test-expr ? then-expr : else-expr;

// 使用条件数据传送方法
v = then-expr;
ve = else-expr;
t = test-expr;
if(!t){
    v = ve;
}

这样改写,就能提高程序的性能了,但是并不是所有的条件表达式都可以使用条件传送来编译,一般只有当两个表达式都很容易计算时,编译器才会采用条件数据传送的方式,大部分都还是使用条件控制转移方式编译。

switch 语句

switch语句可以根据一个整数索引值进行多重分支,在处理具有多种可能结果的测试时,这种语句特别有用。为了让switch的实现更加高效,使用了一种叫做跳转表的数据结构(Radis 也是用的跳表)。跳转表是一个数组,表项 i 是一个代码段的地址,当开关情况数量比较多的时候,就会使用跳转表。

我们举个例子,还是采用 C 语言的形式表是控制流,要理解的是执行switch语句的关键步骤就是通过跳转表来访问代码的位置。

void switch_eg(long x, long n, long *dest){
    long val = x;
    switch(n){
        case 100:
            val *= 13;
            break;
        case 102:
            val += 10;
        case 103:
            val += 11;
            break;
        case 104:
        case 105:
            val *= val;
            break;
        default:
            val = 0;
    }
    *dest = val;
}

要注意的是,上面的代码中有的分支没有break,这种问题在笔试中会经常遇到,没有break会继续执行下面的语句,即变成了顺序执行。上面的代码会被翻译为下面这种控制流。

void switch_eg(long x, long n, long *dest){
        static void *jt[7] = {
            &&loc_A, &&loc_def, &&loc_B,
            &&loc_C, &&loc_D, &&loc_def,
            &&loc_D
        };
        unsigned long index = n - 100;
        long val;
        if(index > 6){
            goto loc_def;
        }
        goto *jt[index];
    loc_A:
        val = x * 13;
        goto done;
    loc_B:
        x = x + 10;
    loc_C:
        val = x + 11;
        goto done;
    loc_D:
        val = x * x;
        goto done;
    loc_def:
        val = 0;
    done:
        *dest = val;
}

循环结构

C 语言中有do-whilewhilefor三种循环结构,它们的通用形式一般都长下面那样。

// do-while
do
    body-statement
    while(test-expr);

// while
while(test-expr)
    body-statement

// for
for(init-expr; test-expr; update-expr)
    body-statement

do-while的特点是body-statement一定会执行一次,所以我们可以将do-while翻译成下面的控制流形式,很容易就能联想到它的汇编形式。

loop:
    body-statement;
    t = test-expr;
    if(t){
        goto loop;
    }

while循环我们给出两种形式的控制流,其中一种包含do-while形式,如下所示。

// 第一种形式
t = test-expr;
if(!t){
    goto done;
}
do
    body-statement;
    while(test-expr);
done:

// 第二种形式
    goto test;
loop:
    body-statement;
test:
    t = test-expr;
    if(t){
        goto loop;
    }

面试的时候,有的面试官会问你for循环的执行顺序,现在深入理解了三种循环的机制,再也不怕面试官啦。for循环可以转换成如下的while形式。

init-expr;
while(test-expr){
    body-statement;
    update-expr;
}

有了这种形式的for循环,我们只需要将其中的while部分再翻译一下就好了,前文给出了两种while翻译的方式,而具体采用哪种方式,取决于编译器优化的等级。

总结

计算机就是用那么几条简简单单的指令就完成了各种复杂的操作,不得不折服于计算机科学家们的魅力。现在人工智能被炒的很火热,然后人是事件、情感驱动的,而计算机是控制流驱动的,所以从架构上就决定了,冯诺依曼体系计算机实现的都是弱人工智能。

操作系统编程基础