现代编程语言中循环是十分常见的功能，几乎任何编程语言都有类似for， while这样的循环语句，不过在计算机底层就没有那么幸福了，许多的硬件其实并没有提供硬件级别的循环。不过硬件级别的限制，似乎并没有影响到我们日常的工作，今天就主要来看看循环的本质是什么。

指令集

如今使用的编程语言，以及各类不同的软件，其实到最后都会转换成二进制的形式，用以控制底层硬件的运行。这些上层软件其实是底层功能的抽象，不管上层业务多么复杂，在底层几乎都是通过有限的寄存器，指令集，还有内存来实现相关的功能。我们所编写的应用程序，与 CPU 的指令集息息相关。其实所谓的指令集，就是 CPU 提供的一系列用于控制硬件的指令的集合。不同的硬件厂家，所生产的 CPU 指令集肯能会有所不同。目前主要分成了两大阵营，分别是 CISC-复杂指令集计算机和 RISC-精简指令集计算机。AMD 以及 Intel 这些厂家生产的 CPU（x86 指令集）基本上都属于 CISC，他们所包含的指令相当多也比较复杂，不过似乎不打算支持硬件级别的循环。而一些的手机 CPU，ARM 架构的开发版都属于 RISC 的范畴，它们的特点是指令相对较少，也比较简单，并且部分 RISC 的 CPU 甚至支持硬件级别的循环。

循环的“变态”

这里的“变态”并没有骂人的意思。根据生物学中的描述，变态其实指代了形态的变化。在某种意义上，循环也存在着变态。

在 C 语言中循环普遍有 3 中表达方式，分别是for循环，while循环以及do-while循环

// 1. for循环
for (init-expr; test-expr; update-expr) {
    ....
}

// 2. while循环
init-expr;
while (test-expr) {
    .....
    update-expr;
}

// 3. do-while循环

init-expr;
do {
    ....
    update-expr;
} while (test-expr)

不过问题是计算机底层并没有那么多表达循环的方式，为了在底层实现循环功能，必须要以另一种方式来表达循环。实际上循环在底层都会通过指令跳转配合状态更改的方式来实现。相当于用goto这类语句来实现循环模式。goto语句在业界是很让人诟病的，许多的语言都不支持goto这类语法，不过好在 C 语言还是支持的。接下来来看看要如何进行这种“变态”。

fact_while是一个用while循环实现的阶乘函数，当然我们也可以用for循环来实现等价的功能，这里不一一举例。

long fact_while(long n) {
  long result = 1;
  while (n > 1) {
    result *= n;
    n -= 1;
  }
  return result;
}

我们的任务就是不使用while，for这些循环语句，只用goto语句来实现上述循环。大体上有两种翻译方式，分别是jump to middle以及gurade-do。

1. Jump To Middle

jump to middle 直接翻译过来就是跳转到中间，它的原理其实就是把条件测试写在中间部分，在首次迭代开始之前先行跳转并执行条件测试语句。翻译过来大概就是

long fact_jump_to_middle(long n) {
  long result = 1;
  goto test;
 loop:
  result *= n;
  n --;
 test:
  if (n > 1) goto loop;
  return result;
}

这种翻译方式最为关键的是goto test;语句，在进入循环区域之前便直接跳转到条件测试语句，测试是否符合n > 1这个条件。如果符合条件则进入循环体并执行循环体中的逻辑，否则继续往下执行程序，返回结果。这种翻译方式还有个特点，当你尝试把goto test;这条语句去掉之后会发生什么事情呢？

long fact_jump_to_middle_without_first_jump(long n) {
  long result = 1;
 loop:
  result *= n;
  n --;
 test:
  if (n > 1) goto loop;
  return result;
}

从逻辑上讲它其实就是一个测试条件相同的do-while循环实现，while语句与do-while语句最大的不同就在于，while语句是先进行条件测试，当符合条件的时候才会进入到循环体中，而do-while则是执行了一次循环体中的语句之后才进行循环相关的条件测试。这么看来do-while循环本质上就是少了初始条件检测的while循环。

2. guarded-do

另一种翻译方式被称为 guarded-do，它的原理是在迭代之前设置一个“门卫”条件。如果不符合条件的话，则直接跳到循环逻辑之后，否则就进入循环逻辑中，此处的循环逻辑依旧用do-while循环来实现。按照这种翻译方式所翻译的goto版本如下

long fact_guarded_do(long n) {
  long result = 1;
  if (n <= 1) goto done;
 loop:
  result *= n;
  n --;
  if (n > 1) goto loop;
 done:
  return result;
}

可见最关键的地方是设置的“门卫”条件，该条件应该设置成循环条件的补集。只要满足这个“门卫”条件则跳过整个循环逻辑，否则就进入循环区域中。有些书还会把上面的过程写成

long fact_guarded_do(long n) {
  long result = 1;
  if (n <= 1) goto done;
 loop:
  result *= n;
  n --;
  if (n != 1) goto loop;
 done:
  return result;
}

其实两种方式是等价的。只要符合条件n > 1便能够进入到循环区域中，在循环中每次迭代都会进行减一操作，那么只要满足条件n != 1便可持续进行迭代。

真实场景

前面部分简单地介绍了循环，以及如何对循环进行变形，用goto语句来取代while， for， do-while这类循环语句。然而正常情况下我们并不会去把一个 C 语言的循环版本，转换成与之等价的 C 语言的goto版本，这么做其实只是为了方便原理的解释。真实场景下，在语言进行编译的时候，其实会先转换成汇编代码。

通过命令

gcc -Og -S while.c

把最开始的fact_while阶乘函数编译成汇编语言版本，生成的汇编程序会存储在文件while.s中，丢掉一些杂七杂八的东西之后大概结果如下

    movl    $1, %eax
    cmpq    $2, %rdi
    jl  LBB0_2
LBB0_1:
    imulq   %rdi, %rax
    cmpq    $2, %rdi
    leaq    -1(%rdi), %rdi
    jg  LBB0_1
LBB0_2:
    retq

简单起见，我把一些方法调用相关的寄存器行为给去掉了，只保留了循环逻辑的部分。阅读汇编代码的关键点在于了解不同寄存器的作用，其中寄存器%rax用于存放返回值，寄存器%rdi用于存放函数第一个参数的值。把上面的汇编程序转换成更加亲民的版本，并加上注释可得

    movl    $1, %eax                 ## 把数值1放进寄存器%eax中
    cmpq    $2, %rdi                 ## 把参数n的值与数值2进行比较
    jl  done                         ## 如果n < 2则跳到标签done处
loop:                                ## 标识着即将进入循环区域
    imulq   %rdi, %rax               ## 把%rax (就是%eax中的数值0扩展到64位)的数值与%rdi(数值n)相乘，并把结果存储到%rax中
    cmpq    $2, %rdi                 ## 把n的值与数值2进行比较，比较结果会记录在其他地方 (1)
    leaq    -1(%rdi), %rdi           ## 改变n的值，n = n - 1
    jg  loop                         ## 获取(1)处的比较结果，如果在递减之前n是大于2的则跳转到循环区域开始的地方
done:                                ## 标识着已经离开循环区域
    retq                             ## 函数返回，返回值存放在寄存器%rax中

总体上看来这里是采用了guarded-do的翻译方式。不过它的具体逻辑看起来跟我们前面用 C 语言的goto语句描述的过程稍微有些不同，但是只要仔细琢磨，其实它们所做的东西是等价的，为了少执行一些指令，编译器会进行了一些优化，不过在本例中所采用的优化等级还算是比较低的了。

结尾

这篇文章主要简单地总结了一下在计算机底层循环的实现方式，即便是现代最流行的 x86 指令集都没有硬件级循环的支持，常见的做法是利用硬件的条件跳转指令来实现循环的相关逻辑。为了更直观地看到这个过程，我们利用 C 语言的goto语句模拟了底层的循环实现。最后还提供了一个优化等级较低的汇编语言版本，能进一步体现出底层硬件的工作方式。