对C语义的for循环的基本代码生成模式

之前有同学在做龙书（第二版）题目，做到8.4的练习，跟我对答案，然后聊起C语言的for循环的代码生成有几种常见的模式。顺道跟大家分享讨论一下。

C语言的for循环大家应该都很熟悉了，C系语言大都有一样或几乎一样的语法结构：一个循环初始化，一个循环条件，一个循环再初始化，然后一个循环体。通常循环初始化在最前面，再初始化的逻辑直接黏在循环体后面，能有变化的就是循环条件的代码生成到什么位置。

举个例子，

for (int i = 0; i < 100; i++) {
  foo();
}

把它翻译为龙书第8章所用的三地址指令，可以用许多不同的模式翻译，这里举三种例子：
（注释里标出了基本块的标号、前导基本块、后继基本块，以及基本块的内容等信息。应该很直观吧？）

第一种：循环条件放前面，循环末尾用无条件跳转回到开头：

// B0 -> B1: loop initialize
(1)  i = 0

// B1 <- { B0, B2 }, -> { B2, B3 }: loop condition
(2)  if i >= 100 goto (6)  // note: inverted condition

// B2 <- B1, -> B1: loop body
(3)  call foo()
(4)  i = i + 1
(5)  goto (2)

// B3 <- B1: after loop
(6)  ...

第二种：循环条件放后面，在进入循环的地方先无条件跳转到位于循环末尾的条件：

// B0 -> B2: loop initialize
(1)  i = 0
(2)  goto (5)

// B1 <- B2, -> B2: loop body
(3)  call foo()
(4)  i = i + 1

// B2 <- { B0, B1 }, -> { B1, B3 }: loop condition
(5)  if i < 100 goto (3)

// B3 <- B2: after loop
(6)  ...

第三种：在进入循环的地方先判断是否跳过循环，然后循环条件放在末尾：

// B0 -> { B1, B3 }: loop initialize
(1)  i = 0
(2)  if i >= 100 goto (6)  // note: inverted condition

// B1 <- { B0, B2 }, -> B2: loop body
(3)  call foo()
(4)  i = i + 1

// B2 <- B1, -> { B1, B3 }: loop condition
(5)  if i < 100 goto (3)

// B3 <- { B0, B2 }: after loop
(6)  ...

顺带一提，这个具体例子中循环条件是拿循环变量与一个编译时常量比较，所以这个版本的代码的(2)可以非常轻易的通过条件常量传播消除掉，等价变换为：

// B0 -> B1: loop initialize
(1)  i = 0

// B1 <- { B0, B2 }, -> B2: loop body
(2)  call foo()
(3)  i = i + 1

// B2 <- B1, -> { B1, B3 }: loop condition
(4)  if i < 100 goto (2)

// B3 <- { B0, B2 }: after loop
(5)  ...

而前两种模式没那么容易消除其中的指令。


有兴趣的同学可以来讨论下这几种模式的异同点
注意三地址指令的条数，基本块的个数与划分，基本块之间控制流边的总个数，代码的静态与动态的情况的关系，等等。

当然这不是啥新问题，早就有很多论文讨论过了。
例如说某篇1978年的小论文⋯名字就先不说了免得剧透。有兴趣的同学自己思考喔。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

下面补充些在实际生活种能看到的例子。

1. Java虚拟机规范，Java SE 7版，3.2小节
这里举了几个Java的for循环翻译为字节码的范例，都符合上面说的“第二种”模式。
例如把这样的代码：

void spin() {
    int i;
    for (i = 0; i < 100; i++) {
        ;    // Loop body is empty
    }
}

翻译为：

0:   iconst_0       // Push int constant 0
1:   istore_1       // Store into local variable 1 (i=0)
2:   goto 8         // First time through don't increment
5:   iinc 1, 1       // Increment local variable 1 by 1 (i++)
8:   iload_1        // Push local variable 1 (i)
9:   bipush 100     // Push int constant 100
11:  if_icmplt 5    // Compare and loop if less than (i < 100)
14:  return         // Return void when done

Eclipse Compiler for Java (ecj)就采取了这种模式。但Oracle JDK6里自带的javac实际用的代码生成策略却是前面说的“第一种”，将上面的例子编译为：

0:	iconst_0
1:	istore_1
2:	iload_1
3:	bipush	100
5:	if_icmpge	14
8:	iinc	1, 1
11:	goto	2
14:	return

好玩吧呵呵厚⋯