浅谈循环之硬件级实现

现代编程语言中循环是十分常见的功能，几乎任何编程语言都有类似 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 语句模拟了底层的循环实现。最后还提供了一个优化等级较低的汇编语言版本，能进一步体现出底层硬件的工作方式。