一、前言

本篇只介绍一下框架，就不具体介绍每个步骤了。

二、Pass框架

上一篇已经讲了gcc的中间语言的表现形式。gcc 对中间语言的每一步处理叫做一个pass。从一个函数的GENERIC树刚被转换为GIMPLE之后，接下来的工作就由一连串的pass来完成。这些pass环环相扣，最终完成整个程序的优化工作，为目标代码生成做最后的准备。

GCC的pass结构定义在gcc/tree-pass.h头文件中：

opt_pass的成员都很好理解，重点就在gate和execute两个函数。这两个函数都没有参数。如果该pass是用来处理函数，参数通过全局变量 current_function_decl 和 cfun 传入，前者是当前function的GENERIC树节点；后者是一个function结构体，里面包含了这个函数相关的全部信息（控制流，GENERIC，GIMPLE，等等）。

之后用继承的方式定义了四个pass的子类型：

这四种pass，只有ipa pass比较特殊，其他的除了类型不一样之外，其余都一样。当然，在初始化对应结构体时，opt_pass::type必须用对应的枚举来初始化。最后一种ipa pass区别于simple ipa pass，叫做regular ipa pass，在后面进一步介绍。

大部分常用的pass都实现在gcc目录下的某些文件中，这些文件的特点是声明了一个全局的xxx_pass结构体变量，而这些变量在tree-pass.h中用extern声明一遍，并在passes.c中的 init_optimizations() 函数中串在一起。该函数通过使用NEXT_PASS()宏，初始化了5串pass：

他们被调用的顺序和被初始化的顺序是一致的：all_lowering_passes -> all_small_ipa_passes -> all_regular_ipa_passes -> all_lto_gen_passes -> all_passes。他们所作的事情大致如下：

all_lowering_passes：降级GIMPLE，从GIMPLE生成控制流图，内联形参...

all_small_ipa_passes：内联函数(early inline)，内联形参，重建cgraph边，重建函数属性，建立SSA，复写传播(copy propagation)，清理...

all_regular_ipa_passes：内联函数(inline)，常量判定(pure const)，Escape分析，进程间Point-to分析（IPA PTA）...

all_lto_gen_passes：Link time optimization...

all_passes：exception handling，GIMPLE优化（SSA优化，dead call，别名分析，if合并，循环优化等等），GIMPLE->RTL，RTL优化（复写传播，dead call，寄存器合并，条件跳转优化等等）清理...

其中 all_regular_ipa_passes和all_lto_gen_passes都是regular ipa pass，all_small_ipa_passes就是simple ipa pass，all_lowering_passes都是gimple pass，all_passes是由gimple pass和rtl pass组成。

三、三大类Pass

3.1、GIMPLE Pass

所有的Lowering pass和前半部分优化都是gimple pass。gimple pass可以遍历当前函数的全部gimple语句。Lowering pass中的控制流生成之前，gimple pass只能从cfun里遍历全部的gimple，因为此时它们还没有被组织成控制流图的形式，之后的gimple pass就可以使用FOR_EACH_BB这样的宏逐块扫描gimple语句。

3.2、RTL Pass

RTL pass基本上是优化的后半部分。由于RTL有寄存器、字长等GIMPLE没有的底层概念，因此属于底层优化，侧重点也不同。RTL pass也可以使用FOR_EACH_BB对控制流进行遍历，但是用FOR_BB_INSNS对基本块中的insn进行处理，而gimple pass是通过gsi_start_bb来获取gimple语句列表。

3.3、IPA Pass

IPA的全称是Inter-Procedural Analysis。在gcc里它有两层意思：一个是跨函数的分析，一个是全局变量（夹在函数间的变量）的分析。IPA所使用的工具是cgraph（call graph，调用图）。调用图记录了函数之间的调用关系。进程间分析的重点就是函数间的变量传递（参数）和依赖关系（全局变量，调用关系）。

IPA pass在每次执行时也只是针对一个函数，因此它在执行时也可访问 current_function_decl 和 cfun，并通过它们获取对应的cgraph_node，由此可以得到当前函数与cgraph里的其他函数之间的关系。与此同时，gcc将全局变量存放在varpool_nodes里，这也是cgraph的一部分。

四、Pass的执行

Pass被Pass管理器执行。执行每一个pass的代码实现在gcc/passes.c里。

4.1 几个特殊的pass

在gcc/tree-optimize.c中定义了几个特殊的pass，他们的作用如下：

pass_all_optimizations ：它是进程内优化pass的第一个pass，也是他们的父pass。它只有gate函数，只做开关之用。

pass_early_local_passes：它是all_small_ipa_passes的后半部分，属于IPA优化部分。它是IPA优化的开关。

pass_all_early_optimizations：它是pass_early_local_passes的一部分，除了做开关，还负责更新cgraph_state。cgraph允许任意时刻添加函数，但是如果在pass的后段添加函数，而这个函数没有被之前的pass处理过，那就有问题，因此cgraph会根据当前的状态来决定是否要对这个函数追加执行之前的pass。

pass_cleanup_cfg，pass_cleanup_cfg_post_optimizing和pass_fixup_cfg：在不同阶段清理控制流图，它是独立的pass，没有gate（默认执行）。

pass_init_datastructures：初始化所有SSA结构，为转换SSA做准备。

4.2 Pass的执行顺序

上一篇大致讲到了Lowering在Optimization之前。在这里，我详细列出他们的调用关系：

    cgraph_finalize_compilation_unit()
        cgraph_analyze_functions()
            cgraph_analyze_function()
                gimplify_function_tree() -> gimplification。
                cgraph_lower_function() -> lowering
            cgraph_optimize()
                ipa_passes() 
                   if (!in_lto_p) execute_ipa_pass_list (all_small_ipa_passes); -> small IPA execute
                   if (!in_lto_p) execute_ipa_summary_passes(all_regular_ipa_passes) -> regular IPA summary
                   execute_ipa_summary_passes (all_lto_gen_passes); -> lto summary
                   if (!flag_ltrans) execute_ipa_pass_list (all_regular_ipa_passes); -> regular IPA (include LTO) execute
                cgraph_expand_all_functions()
                   cgraph_expand_all_function()
                      tree_rest_of_compilation()
                        execute_all_ipa_transforms() -> regular IPA transform (include LTO) transform
                        execute_pass_list (all_passes) -> 进程内优化

4.3 普通Pass的执行

普通的pass由gcc/passes.c中的execute_one_pass()函数来负责调用。该函数的代码就不贴了，具体来说，它是这么来调用每个普通pass的：

1. 检查gate：gate_status = (pass->gate == NULL) ? true : pass->gate();
2. plugin复查gate：invoke_plugin_callbacks (PLUGIN_OVERRIDE_GATE, &gate_status);
3. 如果不需要执行，就退出。
4. 通知plugin准备execute：invoke_plugin_callbacks (PLUGIN_PASS_EXECUTION, pass);
5. 执行pass预定的TODO list：execute_todo (pass->todo_flags_start);
6. 检查函数的property是否和pass的相符：do_per_function (verify_curr_properties,  (void *)(size_t)pass->properties_required);
7. 执行pass：todo_after = pass->execute ();
8. 执行pass指定的结束TODO list：execute_todo (todo_after | pass->todo_flags_finish);
9. 如果是regular IPA Pass，记录该pass到当前函数的IPA Transform列表中。

还有一些debug用的dumpfile操作就不提了。

4.3 Regular IPA Pass的执行

执行Regular IPA Pass的函数就不再作详细介绍了，他们的执行流程被分散为3轮，每一轮的步骤都差不多，而且比普通pass的执行过程简单。

每个IPA pass都有三次机会来执行。generate_summaries() -> execute() -> function_transform()。前两次机会基本都差不多，都是用来扫描和准备参数，最后一次机会就是对cgraph实施改变。比如pass_ipa_inline，在generate_summaries里面计算所有函数的大小，在execute里面根据大小和其他信息来判定哪些函数可以内联，在transform里面对所有标记为内联的函数进行内联，并更新cgraph。

尽管如此，generate_summaries() 和 execute() 还是有作用上的区别。由于前者先执行，而后者是否执行被gate()控制，并且transform是按照每个函数上挂载的ipa_pass 列表来执行，如果execute不执行的话，该pass也不会被挂载到当前函数上，因此 generate_summaries() 可以用来通过 gate() 控制后两者是否被执行。

五、之后

执行完所有Pass之后，gcc就进入了最后的阶段：目标代码生成。敬请期待下篇。

一、前言

　　又有好久没写了，的确很忙。前篇介绍了GCC的pass格局，它是GCC中间语言部分的核心架构，也是贯穿整个编译流程的核心。在完成优化处理之后，GCC必须做的最后一步就是生成最后的编译结果，通常情况下就是汇编文件（文本或者二进制并不重要）。

　　前面也讲到了，GCC中间语言的核心数据结构是GENERIC、GIMPLE和RTL。其中的RTL就是和指令紧密相关的一种结构，它是指令生成的起点。

二、RTL和INSN

2.1 什么是RTL，什么是INSN

　　RTL叫做寄存器转移语言（Register Transfering Language）。说是寄存器，其实也包含内存操作。RTL被设计成一种函数式语言，由表达式和对象构成。其中对象指的是寄存器、内存和值（常数或者表达式的值），表达式就是对对象和子表达式的操作。这些在gcc internal里面都有介绍。

　　RTL对象和操作组成RTL表达式，子表达式加上操作组成复合RTL表达式。当一个RTL表达式表示一条中间语言指令时，这个RTL表达式叫做INSN。RTL表达式（RTL Expression）在gcc代码中缩写为RTX，代码中的rtx类型就是指向RTL表达式的指针。所以insn就是rtx，但是rtx不一定是insn。

2.2 INSN的生成

　　RTL是由gimple生成的，从gimple到RTL的转换叫做“expand”。在整个优化的pass链中，这一步由pass_expand完成。该pass实现在gcc/cfgexpand.c中。它的execute函数gimple_expand_cfg很长，但是核心工作是对每个basic block进行转换：

expand_gimple_basic_block会调用expan_gimple_stmt来展开每一个gimple语句，并将展开后的rtx连接在一起。首先就有一个问题：insn是怎么生成的？

　　此外，每个expand_xxx函数只负责一部分工作，有些函数有rtx类型的返回值，有些函数没有返回值。那些有返回值的函数通常也不会有变量来保存它们返回的insn。那么就有另外一个问题：那些展开的insn到哪里去了？

　　为了弄清楚这两个问题，首先要找到生成insn的地方。这是一项工程浩大的体力活，不妨从某个点来研究这个问题，比如就从函数调用的语句来入手吧。我们可以从expand_gimple_basic_block开始顺藤摸瓜，来看看一个GIMPLE_CALL是如何翻译成insn的。

　　首先，expand_gimple_basic_block里有一个对basic block里的gimple statement的遍历循环，在这个循环里面，首先判断了一些特殊的情况，比如debug之类的，忽略之。直到循环最后一部分才进入正题：

　　进入到expand_gimple_stmt里面，这个函数不长，一眼可以看出来，核心是expand_gimple_stmt_1 (stmt);，这个函数分情况展开了stmt。其中GIMPLE_CALL对应的是expand_call_stmt。这个函数也不长，关键在最后。

　　gimple call语句形如 lhs = func ( args ); 。其中，lhs是可以没有的。所以如果存在lhs的话，就按赋值语句展开。否则的话就按表达式展开。赋值语句的右边也是表达式，因此按赋值语句展开最终也会将“func(args)”部分按表达式展开。

　　expand_gimple_expr_1函数很长，因为要处理的表达式类型比较多。其中我们关注的是case CALL_EXPR:分支：

　　内置函数有内置函数的展开方法，这个以后有机会再讲。这里还是分析一下普通函数。前面的那个if 是用来检查的，展开是由expand_call函数来完成。这个函数相当长，因为函数的参数、堆栈等等事务很繁琐。但是至少可以确定的是，一句普通的函数调用绝对不是一个简单的insn能实现的，它应该对应了一串insn，而且至少包括压栈、调用、退栈这三部分。那么这一串insn在哪里？

　　为了弄清楚这一串insn在代码中的哪个地方，就必须提到start_sequence ()、get_insns()、end_sequence()这三个没有参数的函数。第一个函数开启了一个新的insn sequence，第二个函数获取这个sequence的第一个insn，因为sequence是双链表，所以由第一个insn就可以访问到后面的所有insn。最后一个函数关闭这个sequence，之后就不能再通过emit_xxx往这个sequence里面插入insn了。原因现在还说不清楚，因为这个跟第二个问题相关，就是insn去哪里了？

　　那么insn到哪里去了？在expand_call这个函数最后就有答案：

　　所谓尾调用就相当于 return tail_call(...);。这个是有专门优化的。但不管怎么优化，最后的insn被发射（emit）了：

其中first_insn和last_insn是宏定义：

　　原来，生成的insns被插入了当前函数的insn链表中。这个链表包含了当前函数的所有insn，而且是按存储顺序存放的。如果有跳转的话，会有对应的jump insn和label insn。如果把insn就看作是汇编的话，这个链表其实就是“汇编”序列了。

　　ok，回到前面提到的start_sequence/get_insns/end_sequence这一组函数。由于emit_xxx函数都是向first_insn/last_insn插入，而新的sequence也要借助于emit_xxx来插入，也就是说在start_sequence和end_sequence这两个调用中间，所有的emit_xxx必须向这个sequence发射insn。方法只有一个：那就是让first_insn/last_insn指向当前正在构建的sequence，当这个sequence构建完成之后，再把它还原。（相当笨拙而无奈的设计，因为emit_xxx数量众多，不容得罪）

　　至此，insn去哪里的问题解决了，但是第一个问题还在：insn如何被构建出来的？继续顺藤摸瓜。在expand_call函数中，有一句特别显眼：

　　看不懂代码，看注释也明白了，这不就是生成一个call insn吗？进入看看：

　　这只是emit_call_1的一小部分。gen_rtx_MEM就是创建一个内存地址对应的rtx，这里用来获取被调用的函数地址（注意，这里的地址使用符号表示，因为函数到底会被安排在哪里目前还不知道，给它安排个符号，让汇编器和连接器去翻译成真实的地址）。那么这个GEN_CALL是什么？至少在gcc 被 built 之前是不知道的。但是可以告诉你的是，它由一个叫做Machine Description的东西来决定。这里的GEN_CALL调用的是gen_call函数，这个函数定义在insn-emit.c中，而这个文件实在build的时候由Machine Description生成的。在i386平台的Machine Description中，gen_call函数转而去调用ix86_expand_call，因此真正的call insn是由这个函数来完成的。而这个函数又调用了一堆 gen_rtx_XXX来组装insn，这一堆gen_rtx_XXX是从gcc/rtl.def文件自动生成的。

　　rtl.def 文件是由一串宏组成的，这个宏形如DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)。ENUM是枚举名，gen_rtx_XXX中的XXX部分就是这个枚举名；NAME是识别名，用在其他地方识别rtl；FORMAT是参数格式，代表这个rtx有多少个参数，每个参数是什么类型。比如0代表常数0，e代表表达式等等。CLASS是类型。

　　在gcc目录下有个叫做gengenrtl.c的文件，他有自己的main函数，所以是一个独立的程序。该程序就是将rtl.def翻译成genrtl.h和genrtl.c两个文件，前者声明了gen_rtx_XXX到gen_rtx_fmt_FFF_stat的对应关系，其中FFF就是宏里面的FORMAT参数，gen_rtx_CALL对应的就是gen_rtx_fmt_ee_stat；后者定义了gen_rtx_fmt_FFF_stat的实现。

　　所以总的说来，一个insn自底向上的构建的话，先由rtl.def构建原子的rtx，然后由Machine Description组装insn或者insn 序列。

2.3 Basic Block中的insn

　　前面提到过，basic block中有两套指令系统：gimple和RTL。那么basic block中的RTL是从哪里来的呢？还是回到expand_gimple_basic_block函数：

　　对应的，在函数体中间也有对BB_HEAD(bb)的赋值，是设置basic block的insn序列的起始。BB_HEAD 排除了基本块开头的LABEL，BB_END排除了基本块最后的跳转表。所以每个基本块的insn序列就是函数insn序列的子序列。不同基本块的insn序列不会相交，甚至可能不会连着，因为中间还隔着LABEL和跳转表。

　　pass_expand之后的pass基本上都是RTL Pass了。这些pass要么通过get_first_insn()/get_last_insn()来遍历整个函数的insn列表（包含Label和跳转），要么用FOREACH_BB、BB_HEAD、BB_END来遍历每个基本块内部的insn（不包含Label和跳转）。

三、Machine Description

　　针对每个CPU平台，gcc有对应的Machine Description用指导指令生成。这些代码放在gcc/config/<平台名称>的目录下，比如intel平台的在gcc/config/i386/。一个Machine Description文件是对应平台的核心，比如gcc/config/i386/i386.md文件。

　　一个md文件中可以定义很多东西，比如constant、attr、insn、expand等等。constant是给一个名字起一个编号，其他地方如果要用到这个编号，可以用名字代替。比如i386.md中每个寄存器有一个编号；attr是目标平台的属性，比如有些什么扩展指令集、有些什么功能、或者被禁用了那些功能等等；insn和expand是md文件的主体，用来定义insn，不同的是前者的输出是asm，用于指令生成；后者的输出是insn sequence；用于GIMPLE转RTL。

　　每个insn和expand有这么几个要素：名字、RTL模板、条件、输出模板。名字是insn的识别名，比如rtl.def中CALL的识别名是call，所以对应的insn就是md文件里的define_expand call；RTL模板是RTX的规格，它有两个作用：1.判断是否匹配某个insn，2.指出每个操作数的属性（大小、使用情况，前置后置条件）；条件被用来检查该insn的前置条件，如果不符合，那就有问题；输出模板是该insn的汇编输出格式，用于最后的指令发射。

　　要注意的是md文件定义的是insn pattern，具体的insn是由expand_xxx、emit_xxx、gen_rtx_xxx、gen_xxx那一堆函数生成的。所以md文件里的insn只有两个作用：1.检查insn；2.输出asm

　　那么md文件是如何融入到gcc中的呢？还是靠build！和前面讲的rtl.def生成genrtl.h、genrtl.c类似，md文件被一系列工具翻译成不同作用的代码：

　　这里只说三个文件：insn-recog.c包含了RTL模板匹配的代码，用来检查rtx的合法性；insn-emit.c包含了insn的构建代码；insn-output.c包含了insn对应的asm输出。这三个文件分别由gcc/genrecog.c、gcc/genemit.c 和 gcc/genoutput.c编译出来的三个程序来生成，不妨还是那上面的call来举例子：

　　这个call insn要求第一个操作数是一个整数（QI），第二个和第三个参数自便，但是第三个参数是程序要使用的。从expand_call可以看出，第一个操作数是调用函数的地址，第二个操作数是参数堆栈大小，第三个操作数是参数列表（所有参数都在这第三个操作数里）。这个expand被用于gimple_call到insn的转换。

　　这条md定义被genemit工具转换成了一个叫做gen_call的函数，函数体中除了准备参数之外，最核心的就是调用ix86_expand_call。这是转换之后的结果：

这是一个expand，用来生成insn，所以没有对应的output。再看一个insn的例子：

转换成gen_xxx之后变成：

asm模板不会出现在gen_xxx中，因为这个函数pass_expand是用来构建insn的。asm模板会转换到insn-output.c中：

四、指令生成

　　在优化的pass序列的最后，有一个叫做pass_final的RTL Pass，这个pass负责将RTL翻译为ASM。它的execute函数最核心的三行：

　　第一行输出函数的头，包括函数的汇编说明、stack frame的建立。第二行输出指令序列；第三行结束函数，包括stack frame的销毁、结束说明等。

final函数遍历整个函数的insn序列，调用final_scan_insn输出每一个insn。这个函数太长，要处理note、debug、frame等等乱七八糟的东西。但是中间最关键的一段是调用Machine Description来输出ASM：

　　指令生成的最关键一步是这段代码的第一个工作：识别insn。这一个工作很令人费解：既然insn是由md来生成的，那么生成的时候就应该知道这个insn该由md里面的哪一条定义提供asm输出，为什么还要识别呢？因为有的insn并不是全靠RTL来生成。就比如上面说的call，虽然他提供了expand的方法，但是真实的工作是由定义在gcc/config/i386/i386.c文件中的ix86_expand_call函数来完成。这个函数手工生成了一系列insn来完成函数调用的工作，那么这些insn如何来输出？

　　所以gcc提供了genrecog生成recog函数来完成insn的识别。识别的方法就是将md文件中的所有RTL表达式当作模式串集合，看真实的insn复合哪一个RTL表达式，那么这个insn就有对应的定义输出。recog函数返回对应insn的编号，然后按这个编号去找md的定义，并找到asm输出模板，于是有了上面这段输出代码。

　　recog函数的核心就是一棵硬编码的决策树。genrecog首先会扫描全部的md定义，抽取所有的RTL模式串，分解为一串predicates，然后将这些predicates插入到决策树中。recog函数就是一边输入未知insn的predicates，一边从树根开始做决策（其实就是跳转），直到遇到树叶完成决策。

　　在此之后的两个pass只是清理一下数据结构。由此整个pass链调用完毕，gcc完成了从GENERIC到GIMPLE，再到RTL，最后到ASM的转换。

五、总结

　　这个系列对gcc从输入到输出的流程进行了粗略的分析。一个编译器最核心的是优化部分。具体的优化步骤在本系列中没有提到，因为太多、太繁琐、也太理论。以后可以考虑把教科书中提到的优化挑出来分析一下，但最近是没有时间了，就此告一段落。

原内容来自http://blog.csdn.net/sonicling/article/details/6706152