<bb 5>: if (a <= 11)
goto <bb 6>; else
goto <bb 7>; <bb 6>: D.1200 = a + b; a = D.1200 + c;
return a;
<bb 7>:
}
D.1201 = a;
return D.1201;
上表的过程是 GCC 以 C 源程序作为输入，从而产生了以上未经优化的 GIMPLE 中间代码。
…
a_Fra Baidu bibliotek = a_1 + 1;
<bb 4>: # a_1 = PHI <a_3(2), a_7(3)> if (a_1 <= n_6) goto <bb 3>; else goto <bb 5>;
<bb 4>: # a 1 = PHI < 1(2), a 7(3)> if (a 1 <= 6) goto <bb 3>; else goto <bb 5>;
GCC 对机器无关的中间代码所做的优化都是基于 SSA 形式来进行的。
接下来我们对 GCC 中间代码的生成及优化进行一个简单的实例分析，你可以以此作为
参考。
我们的 C 源程序命名为 sample.c。通过命令 gcc –fdump‐tree‐all –O2 sample.c 将分别产生
产生优化前后的 GIMPLE 中间代码。优化前中间代码的控制流图如图3.2所示。
GIMPLE 的产生是基于抽象语法树（AST）的，其表现形式就如同一些基本的操作一样，
较易于理解。
GIMPLE 代码根据程序流程，将自身按照基本块划分为几个部分。每个基本块内都是和
源程序对应的语句，对于如下所示的源程序，其 GIMPLE 代码如下所示：
表3.1 C 源程序与 GIMPLE 中间代码举例
（sample.c.022t.copyrename1）
<bb 2>:
a_3 = 1;
b_4 = 2;
…
c_5 = 3;
…
n_6 = c_5 * 2;
…
goto <bb 4>;
<bb 3>: a_7 = a_1 + 1;
<bb 4>: # a_1 = PHI <a_3(2), a_7(3)> if (a_1 <= n_6) goto <bb 3>; else goto <bb 5>;
实验三 中间代码生成及优化
实验目的
1、 理解和掌握生成 GCC 编译中间代码的方法 2、 理解和掌握 GCC 对中间代码进行优化的过程
实验环境
Linux 操作系统，GCC 4.x
实验内容
通过 GCC 编译 C 程序来产生 GIMPLE 中间代码，对比使用优化选项前后中间代码的不同， 并给出分析。
如果你之前的实验都是选择在 Windows 系统下用高级语言程序自行编写分析程序，那 么这里你仍然可以用高级语言程序根据你之前用高级语言程序进行的词法和语法分析来生 成中间代码。当然，关于待分析的源程序的选择和中间代码如何定义，都是任由你来决定的， 只是你需要对此进行一定的说明。
<bb 6>: D.1200 = a + b; a = D.1200 + c;
<bb 6>: D.1200_8 = a_1 + b_4; a_9 = D.1200_8 + c_5;
<bb 7>:
<bb 7>:
D.1201 = a;
# a_2 = PHI <a_1(5), a_9(6)>
return D.1201;
a = 1;
a_3 = 1;
b = 2;
b_4 = 2;
c = 3;
c_5 = 3;
n = c * 2;
n_6 = c_5 * 2;
goto <bb 4>;
goto <bb 4>;
<bb 3>: a = a + 1;
<bb 3>: a_7 = a_1 + 1;
<bb 4>: if (a <= n)
goto <bb 3>; else
备注
（sample.c.017t.ssa）
（sample.c.023t.ccp1）
<bb 2>:
<bb 2>:
a_3 = 1;
a 3 = 1;
b_4 = 2;
b 4 = 2;
c_5 = 3;
c 5 = 3;
n_6 = c_5 * 2;
n 6 = 6;
goto <bb 4>;
goto <bb 4>;
<bb 3>:
D.1201_10 = a_2;
return D.1201_10;
通过以上过程，GCC 得到了 SSA 形式的中间代码，下一步优化时将以此作为输入，首先
是变量的重命名：
表3.4 变量重命名后的中间代码对比
SSA 形式中间代码[Input]
变量重命名[Output]
备注
（sample.c.017t.ssa）
<bb 7>: # a_2 = PHI <a_1(5), a_9(6)> a_10 = a_2;
return D.1201_10;
return a_10;
接下来进行第一级常量复写传播的优化，以上一步得到的文件作为输入：
表3.5 第一级常量复写传播优化前后对比
变量重命名[Input]
第一级优化[Output]
GCC 设计中有两个重要的目标，其中一个是在构建支持不同硬件平台的编译器时，它的 代码能够最大程度的被复用，所以 GCC 必须要做到一定程度的硬件无关性；另一个是要生 成高质量的可执行代码，这就需要对代码进行集中的优化。
目前，GCC 将一种语言翻译为另一种语言的流程如下图所示：
图3.1 GCC 翻译流程
<bb 5>:
…
if (a_1 <= 11)
…
goto <bb 6>;
…
else
goto <bb 7>;
<bb 6>: D.1200_8 = a_1 + b_4; a_9 = D.1200_8 + c_5;
<bb 7>: # a_2 = PHI <a_1(5), a_9(6)> D.1201_10 = a_2;
<bb 2>: a = 1; b = 2; c = 3; n = c * 2; goto <bb 4>;
while (a <= n) {
a = a+1;
<bb 3>: a = a + 1; <bb 4>:
}
if (a <= n)
goto <bb 3>;
else
goto <bb 5>;
if (a < 12) a = a+b+c;
表3.7 删除无用代码后的结果
第二级优化[Input] （sample.c.027t.copyprop1）
删除无用代码[Output] （sample.c.029t.cddce1）
备注
<bb 2>:
<bb 2>:
a 3 = 1;
goto <bb 4>;
b 4 = 2;
c 5 = 3;
n 6 = 6;
在此之后，将其转换为 SSA 形式的 GIMPLE 代码，对比如下：
表3.3 GIMPLE 原始代码和 SSA 形式中间代码的对比
GIMPLE 中间代码[Input]
SSA 形式中间代码[Output]
备注
（sample.c.013t.cfg）
（sample.c.017t.ssa）
<bb 2>:
<bb 2>:
GCC 前端在产生基本的 GIMPLE 代码后，会将其转换一种 SSA（Simple Static Assignment）
形式的 GIMPLE 代码。
SSA 形式主要有以下两个特点：
1、 一个变量的每一次使用都对应着该变量的一个唯一版本，即不共用一个变量；
2、 当某处的变量可能在多个地方赋值，从而导致该变量在该处的值有可能有多种可能
时，使用φ函数来表示对该变量的各个版本进行一次选择。
下面给出一个基本的 GIMPLE 代码所对应的 SSA 形式的代码，以控制流图的形式给出：
图3.2 GIMPLE 代码以及其对应的 SSA 形式
注意到，对于 B4和 B7基本块里的变量 a，在 SSA 中用φ函数来从其可能的值中选择一
个。SSA 形式的构造就是期望用尽可能少的φ函数来保证我们上文所说的 SSA 的特点。
实验原理
GCC 的编译过程分为前端和后端两个部分。第一阶段，编译器的前端接受输入的源代码， 经过词法、语法和语义分析等等得到源程序的某种中间表示方式。第二阶段，编译器的后端 将前端处理生成的中间表示方式进行一些优化，并最终生成在目标机器上可运行的代码。
GCC（GNU Compiler Collection）是在 UNIX 以及类 UNIX 平台上广泛使用的编译器集合， 它能够支持多种语言前端，包括 C、C++，Objective‐C，Ada，Fortran，Java 和 treelang 等。
goto <bb 5>;
<bb 4>: # a_1 = PHI <a_3(2), a_7(3)> if (a_1 <= n_6) goto <bb 3>; else goto <bb 5>;
<bb 5>: if (a <= 11)
goto <bb 6>; else
goto <bb 7>;
<bb 5>: if (a_1 <= 11) goto <bb 6>; else goto <bb 7>;
# a_2 = PHI <a_1(5), a_9(6)>
a_10 = a_2;
…
return a_10;
接下来，以此步结果为输入，进行第二级复写传播的优化：
表3.6 第二级复写传播优化
第一级优化[Input]
第二级优化[Output]
（sample.c.023t.ccp1）
（sample.c.027t.copyprop1）
y = y ‐ D.1957;
上表已经用不同的颜色将 C 语句与其对应的 GIMPLE 代码关联了起来。
GCC 是一个驱动程序，它接受并解释命令行参数，根据对命令行参数分析的结果决定下
一步动作，GCC 提供了多种选项以达到控制 GCC 编译过程的目的，我们可以在 GCC 的手册
中查找这些编译选项的详细信息。
以上例子中，由于我们的 C 程序只有一个基本块，所以 GIMPLE 中间代码也只有一个基
本快。如果我们的程序中有跟多循环分支结构，那么将会产生多个基本块。当有多个基本块
时，在 GIMPLE 代码中，会以“<bb x>”（其中 x=1, 2, 3 …，其为基本快的编号）开头，来表
示下面的代码属于第几个基本块。
<bb 5>: if (a_1 <= 11) goto <bb 6>; else goto <bb 7>;
<bb 6>: D.1200_8 = a_1 + 2; a_9 = D.1200_8 + 3;
<bb 6>: a_9 = a_1 + 5;
<bb 7>:
<bb 7>:
# a_2 = PHI <a_1(5), a_9(6)> # a_2 = PHI <a_1(5), a_9(6)>
C 源程序
GIMPLE 中间代码
int a;
x = 10;
int main()
y = 5;
{
D.1954 = x * y;
int x = 10;
a.0 = a;
int y = 5;
x = D.1954 + a.0;
x = a + x * y;
a.1 = a;
y = y ‐ a * x;
}
D.1957 = a.1 * x;
a_10 = a_2;
return a_2;
return a_10;
到这里，我们给出经过变量重命名以及复写传播优化后，控制流图的对比：
图3.3 变量重命名以及复写传播优化前后的控制流图 这里我们可以清晰的看到，通过以上的优化，a_3、b_4、c_5和 n_6变量已经不再使用。因
此，对这些变量的赋值语句也就可以删除，接下来删除无用代码的结果如下：
表3.2 C 源程序与其 GIMPLE 中间代码
C 源程序[Input]
GIMPLE 中间代码[Output]
备注
（sample.c）
（sample.c.013t.cfg）
#include <stdio.h>
int main()
{
int a, b, c, n;
a = 1; b = 2; c = 3; n = c*2;
<bb 5>:
if (a_1 <= 11)
goto <bb 6>;
…
else
goto <bb 7>;
<bb 6>: D.1200_8 = a_1 + b_4; a_9 = D.1200_8 + c_5;
<bb 6>: D.1200_8 = a_1 + 2; a_9 = D.1200_8 + 3;
<bb 7>:
<bb 2>:
a 3 = 1;
…
b 4 = 2;
c 5 = 3;
备注
n 6 = 6; goto <bb 4>;
<bb 3>:
…
a_7 = a_1 + 1;
<bb 4>:
# a 1 = PHI < 1(2), a 7(3)>
if (a 1 <= 6)
goto <bb 3>;
…
else
goto <bb 5>;
