考研笔记

循环语句的机器级表示

机器一级同样没有 while 和 for。它只有”往回跳”这一个动作，所以三种循环最终都塌缩到同一个骨架上：

循环体

do-while 是这个骨架的直接形态，while 和 for 都要先被改写成 do-while。这一节的全部内容就是这个改写过程，以及改写留下的痕迹——那些痕迹正是读汇编题时反推源码的线索。

机制

do-while：最基本的形态

do { <body> } while (cond);
.Lbody:
      <body>
      cmp   ...
      jcc   .Lbody        ; ★ 唯一一条转移指令，而且是后向的
.Ldone:

整个循环只有一条转移指令，位于底部，方向向后。 这是最省的形态——没有一条多余的跳转。

while：两种翻译，取决于优化级别

while (cond) { <body> }

（1）跳到中间（jump-to-middle），-O0 的做法：

      jmp   .Ltest        ; ★ 先跳到判断
.Lbody:
      <body>
.Ltest:
      cmp   ...
      jcc   .Lbody

结构最直白，代价是入口处多一条无条件跳转。

（2）守卫式（guarded-do），-O1 及以上的做法：

      cmp   ...
      jncc  .Ldone        ; ★ 守卫：一次都不该执行就直接跳出
.Lbody:
      <body>
      cmp   ...
      jcc   .Lbody        ; ★ 循环内只剩这一条转移
.Ldone:

做法是”先判一次，然后整体当作 do-while”。 判断代码被复制了一份，换来循环体内只剩一条后向分支。

为什么值得复制一份代码？ 因为循环体要跑 遍，而守卫只跑一次：

循环内的转移指令执行 遍的总代价
跳到中间1 条（底部条件跳） 次
守卫式1 条 次

看起来一样——差别在别处：跳到中间的版本每次进入循环都要先执行那条 jmp .Ltest，而且判断代码在循环体之后、与循环体不连续，取指的局部性略差。真正的收益在分支预测：分支预测器对后向分支默认预测”跳转发生”（因为后向分支绝大多数是循环），守卫式的结构让这条预测在 次里都命中。这一层在 5.5 指令流水线（本地资料）兑现。

for：等价于 while，但 continue 的落点不同

for (init; cond; update) { <body> }

等价改写：

init;
while (cond) { <body>; update; }

这个等价有且只有一处例外，而它恰恰是考点：continue。

  • 在 for 里，continue 要执行 update 再回去判断
  • 在按上式改写的 while 里，continue 会跳过 update 直接判断 → 死循环

所以编译器翻译 for 时，continue 的跳转目标是 update 那一段的标号，不是 .Ltest：

.Lbody:
      <body>
      ...  jmp .Lupdate    ; ★ continue 跳到这里，不是 .Ltest
.Lupdate:
      <update>
.Ltest:
      cmp   ...
      jcc   .Lbody

读汇编时看到循环底部有两个相邻标号（一个给 continue、一个给正常流程），基本可以断定源码是 for 而不是 while。

数组遍历：为什么汇编里常常找不到 i

for (i = 0; i < n; i++) s += a[i];

直译的话，每轮都要算一次地址 ，含一次乘法。编译器不会这么干，它做归纳变量替换：

      lea   edx, [eax + ecx*4]   ; edx = &a[n]，终止地址，循环前算一次
.Lbody:
      add   esi, [eax]           ; s += *p
      add   eax, 4               ; ★ p += 4，不再有乘法
      cmp   eax, edx             ; ★ 比的是指针，不是 i
      jb    .Lbody

结果是：i 这个变量在机器码里根本不存在。 循环变量被替换成了一个指针，终止条件被替换成了指针与终止地址的比较。

这是读汇编真题的一道坎——找不到计数器不要慌，看哪个寄存器在每轮固定加一个常量（4、8），那个常量就是数组元素的字节数，那个寄存器就是 i 的化身。

层次辨析：循环给的是哪一种局部性

上面这段循环同时体现了两种局部性，而且来源完全不同，不要接反（3.5.1）：

局部性来源在这段代码里
时间局部性循环回跳——同一批指令被反复执行循环体那四条指令、变量 s 和指针 p
空间局部性顺序访问——地址连续往下走a[0], a[1], a[2], … 依次访问

循环回跳给时间局部性，顺序访问给空间局部性。 一个常见的说法是”循环体时间局部性好是因为里面没有跳转”——这是反的：正因为有那条回跳，同一段代码才会被反复执行；真要一路直线执行下去，时间局部性反而为零。

loop 指令：一条”看起来该赢”的 CISC 指令

x86 提供了一条专用循环指令：

      mov   ecx, n
.Lbody:
      <body>
      loop  .Lbody         ; ecx--; if (ecx != 0) jump

一条指令干了三件事：减 1、判零、条件跳转。代码密度明显更好。

但现代编译器几乎从不生成它。 原因是它在多数微架构上被实现得比等价的 dec ecx; jnz .Lbody 更慢（微码实现、且隐式改 ECX 妨碍寄存器分配），而后者虽然多一条指令，却能和别的指令并行发射。

这是 CISC 的一个负面例证，正好和 4.3.1 里 lea 那个正面例证配成一对：复杂指令不是必然赢，也不是必然输——判据是”它有没有被硬件真正优待”。这条会在 4.4.3用性能公式重新表述一遍。

边界

三种循环在机器级没有本质区别，全部是”条件后向跳转”。 判断题若说”for 循环在机器级有专门的指令支持”，错——loop 指令存在，但它不是 for 的翻译，编译器也基本不用。

do-while 至少执行一次，while 可能一次都不执行——这个差别在机器级体现为”有没有那个守卫”。 反推源码时，循环体前面有一条条件跳出，就是 while/for；没有，就是 do-while。

循环展开会让循环体里出现多份相同结构的代码。 编译器把 4 轮合成 1 轮以减少分支和判断，读汇编时看到”同一组操作重复了几次、指针一次加 16”，不要以为源码写了四遍。

continue 在 for 和 while 里的落点不同，这是 for 不能被机械改写成 while 的唯一原因。 反过来，break 在两者里没有区别，都是跳到 .Ldone。

归纳变量替换之后，循环次数的边界条件容易被看错。 cmp eax, edx; jb .Lbody 里 edx 是 &a[n]（越界的那一个），所以用的是 jb（严格小于）——若看成 &a[n-1] 就会把循环次数少算一次。

统考的循环题常常和数组、指针一起出，考的是”这段汇编对应的 C 代码循环了多少次、访问了哪些元素”。先找那个每轮固定增量的寄存器，再看终止比较的对象，两步就能定位。

对照速查

源码机器级骨架循环内转移指令特征
do-while体 → 判 → 后向跳1 条入口无守卫
while（-O0）jmp 到判断 → 体 → 判 → 跳1 条入口有一条无条件 jmp
while（-O1+）守卫 → 体 → 判 → 跳1 条入口有一条条件跳出
for同 while，但多一个 update 标号1 条底部两个相邻标号
判断对错
循环回跳提供时间局部性✅
循环体时间局部性好是因为没有跳转❌（反了）
数组顺序遍历提供空间局部性✅
for 和 while 可以机械互换❌（continue 的落点不同）
break 在 for 和 while 里翻译不同❌（相同）
汇编里找不到循环变量说明代码错了❌（归纳变量替换）
loop 指令比 dec+jnz 快❌（多数微架构上更慢）
do-while 在机器级最省✅（唯一一条转移指令）

考点

  • 三种循环统一到 “循环体 → 比较 → 条件后向跳转”；do-while 是基本形态
  • while 两种翻译：跳到中间（-O0）与守卫式（-O1+）；守卫的有无是反推 do-while / while 的判据
  • for 与 while 的唯一实质差别是 continue 的落点（跳 update 而非 test）
  • 归纳变量替换：i 被替换成指针，终止条件变成指针比较；每轮固定增量 = 元素字节数
  • 循环回跳给时间局部性，顺序访问给空间局部性——不要接反
  • loop 指令存在但编译器不用，是 CISC 的负面例证

链接

反向链接