`
weimou66
  • 浏览: 1236585 次
文章分类
社区版块
存档分类
最新评论

gcc编译流程及中间表示层RTL的探索

 
阅读更多
gcc编译流程及中间表示层RTL的探索收藏

新一篇:解读VC++编程中的文件操作API和CFile类|旧一篇:Effective Item21 尽可能使用const

内容摘要 本文将以 C 语言为例,介绍 gcc 在接受一个 .c文件的输入之后,其前端是如何进行处理并得到一个中间表示并转交给后端处理。然后,在了解了 gcc[1] 的工作流程后,介绍一下作者尝试在 gcc内部的 RTL 表示层中 hack gcc 的过程,与大家分享一些经验,希望能给对有兴趣研究和开发 gcc 的读者有所帮助。

1. GCC 简介
编译器的工作是将源代码(通常使用高级语言编写)翻译成目标代码(通常是低级的目标代码或者机器语言),在现代编译器的实现中,这个工作一般是分为两个阶段来实现的:

第一阶段,编译器的前端接受输入的源代码,经过词法、语法和语义分析等等得到源程序的某种中间表示方式。

第二阶段,编译器的后端将前端处理生成的中间表示方式进行一些优化,并最终生成在目标机器上可运行的代码。

GCC(GNU Compiler Collection) 是在 UNIX 以及类 UNIX 平台上广泛使用的编译器集合,它能够支持多种语言前端,包括 C, C++, Objective-C, Ada, Fortran, Java 和 treelang 等。

GCC 设计中有两个重要的目标,其中一个是在构建支持不同硬件平台的编译器时,它的代码能够最大程度的被复用,所以 GCC必须要做到一定程度的硬件无关性;另一个是要生成高质量的可执行代码,这就需要对代码进行集中的优化。为了实现这两个目标,GCC内部使用了一种硬件平台无关的语言,它能对实际的体系结构做一种抽象,这个中间语言就是 RTL(Register TransferLanguage)。

虽然关于 GCC 的研究和开发工作侧重于 GCC 后端代码优化方面,但本文中我们关注的目标是在 GCC 的编译过程中前端是如何工作的。

把 GCC 的前端独立出来研究目的在于,在设计新的编译器的时候,我们仅仅需要关注如何设计新编译器的前端,而将代码优化和目标代码的生成留给 GCC 后端去完成,避免了后端设计的重复性劳动。

本文将以 C 语言为例,介绍 gcc[2]在接受一个 .c 文件的输入之后,其前端是如何进行处理并得到一个中间表示并转交给后端处理。然后,在了解了 gcc的工作流程后,介绍一下作者尝试在 gcc 内部的RTL表示层中 hack gcc 的过程,与大家分享一些经验,希望能给对有兴趣研究和开发gcc 的读者有所帮助。


[1] 如无特别说明,下文中 gcc 均指GNU C Compiler,即GCC编译器集合中的C语言编译器。

2. gcc 的工作流程
gcc 是一个驱动程序,它接受并解释命令行参数,根据对命令行参数分析的结果决定下一步动作,gcc 提供了多种选项以达到控制 gcc 编译过程的目的,我们可以在 GCC 的手册中查找这些编译选项的详细信息。

gcc 的使用是比较简单的,但是要深入到其内部去了解编译流程,情况就比较复杂了。面对庞大的[3] gcc,我们只能选择感兴趣的部分来分析。但我们无法获得关于 gcc 编译流程的详尽文档[4],这主要是由于 gcc 本身过于繁杂,而且它处于不断的变化当中,所以我们只有通过其它途径来了解 gcc。有两个比较好的方法:一是阅读source,对感兴趣的函数可以跟踪过去看一看,阅读代码看起来可怕,但其实代码中会有很多注释说明它的功能,使得我们的阅读变得更简单一些,这种方法便于从整体上把握 gcc;另外一个是 debug gcc,就是使用调试器来跟踪 gcc 的编译过程,这样可以看清 gcc编译的实际流程,也可以追踪我们感兴趣的细节部分。我们先从大处着眼,从 source 中看看 gcc一些比较重要的函数以及它们之间的调用关系,然后在 hack gcc 的时候,对 gcc 进行 debug来追踪我们关心的细节,并且可以通过调试来发现和修改 patch 中的错误。


[3] 完整的gcc 3.4.0解压缩后占用超过150M的空间,有超过13000个代码和文档文件。

在开始阅读 gcc 的代码之前,推荐您阅读一下 GCC internals 中 passes and files of the compiler 一章——如果您以前没有看过的话,这段内容会帮助您对 gcc 的结构建立一个大概的映像。

好了,我们以 gcc 中的函数为单位,希望能够尽量详细地描述 gcc 中自顶向下的函数调用关系。在 gcc源码目录中,很容易就发现了一个文件 main.c,应该是 gcc 的入口了,这个main.c 文件中只有一个函数 main,而这个 main函数中也只有一条语句,调用了一下toplev_main 函数。之所以单独用一个 main 函数来调用toplev_main,是为了让不同的语言前端可以方便设计不同的 main 函数。


[4] 作者认为关于GCC学习比较好的文档列在本文后面的参考文档一节中,但本文不准备重复这些文档中已有的内容。

toplev_main 函数是在 toplev.c 文件中定义的,从名字中就可以看出这个文件应该是用来控制 gcc 最顶层的编译流程的,在程序开始的注释中也说明了它是用来处理命令行参数、打开文件、以合适的顺序调用各个分析程序[5]并记录它们各自所用的处理时间。toplev_main 首先对 gcc做了一下初始化,主要是设置环境变量和诊断信息等等,然后就开始解析命令行参数,我们对这些并不感兴趣,重要的是接下来调用了 do_compile函数,这个函数看从名字看就是做编译工作的,而在此之后 toplev_main 函数就返回了。

do_compile 函数也是在 tolev.c中定义的,它调用了一些函数来做进一步的初始化,比如对编译过程中计时器的初始化、针对特定程序设计语言的初始化以及对后端的初始化等等,同时它还对toplev_main 函数中解析的命令行参数做了进一步处理。在完成了上述工作后,调用了 compile_file()函数,这个函数应该是用来进行真正的编译工作了。


[5] 分析程序对应的英文是pass,即多趟扫描编译器中某一趟扫描所使用的扫描程序。

compile_file 函数还是在 toplev.c 中定义的,这里提一下 compile_file 函数和上面的do_compile函数,它们是参数和返回类型都为 void 的函数,在编译的时候需要的各种参数包括编译的文件名、编译参数以及 gcc内部使用的一些钩子函数等等都是采用全局变量来表示的,当然,这些全局变量在前面各种初始化函数中都已经被适当地初始化了。接着说compile_file 函数,它又做了一些我们并不太关心的初始化工作,之后,它终于调用了一个钩子函数来分析(parse)整个输入文件了:


(*lang_hooks.parse_file)(set_yydebug);

这里的 lang_hooks 是一个全局变量,不同语言的前端对此赋以不同的值,以便调用各自特有的分析程序,关于 lang_hooks结构的定义和初始化等等可以参见源码中的 langhooks.h、langhooks.c 和 langhooks-def.h等文件,这里就不详细追究了。对于 C 语言来说,这条语句相当于调用了 c-opts.c 中的 c_common_parse_file 函数。

c_common_parse_file中调用了c-parse.c中的c_parse_file函数,在此函数中又调用了同样位于c-parse.c中的yyparse函数。有必要介绍一下c-parse.c文件,它是由GNU bison[6] 从c-parse.y中得到的一个语法解析器。c-parse.y则是一个YACC文件,它使用BNF(Backus Naur Form)来描述了某种程序设计语言的语法。[7]


[6] GNU bison是一个通用的生成语法解析器的工具,它可以把LALR(1)上下文无关的语法描述转换成C语言程序,以便对使用该语法描述的语言进行语法分析。

至此,我们对gcc中主要的函数调用关系还是相当清楚的,从main函数层层深入,进入了c-parse.c中的yyparse函数。前面提到过c-parse.c文件是由GNUbison对c-parse.y这个YACC文件作用后自动生成的,这导致这段代码阅读起来比较困难,因为bison生成的c-parse.c文件中有很多条goto语句以及超过500个case的switch语句,如此多的选择和跳转语句无疑给追踪gcc的函数调用带来了极大的困难,我们不可能再继续下去了。

再回过头去看看前面那些代码和注释以及一些文档,注意到多次提到过一个函数――rest_of_compilation,这似乎是一个很重要的函数,我们可以过去看看。


[7] 关于词法解析器和语法解析器的生成,本文不作详细讨论,有兴趣的读者可以参考GNU bison和flex的手册。

在toplev.c中我们找到了这个函数,注释中说明它的作用是:在对程序中顶层的函数定义或者变量的定义处理以后,接着对这些函数或者变量进行编译并输出相应的汇编代码,在此函数返回后,gcc内部使用的tree结构就消亡了。看来这个函数的功能比较复杂,它已经把源程序对应的汇编代码生成了,并且把对应的tree结构占用的空间已经释放了,而我们所感兴趣的部分是gcc编译过程中内部使用RTL表示的情况,这部分处理应该是在rest_of_compilation这个函数返回之前做的。

前面我们从main函数跟踪到了yyparse函数,这里又发现了一个很重要的rest_of_compilation函数,但中间这段过程gcc做了些什么我们还不清楚,也许我们所关心的有关RTL的处理就在其中。

现在我们只有对gcc进行调试才能确切的看清进入yyparse后函数调用的情况了,这里介绍一下调试gcc的方法:

对gcc进行调试,其实是对编译gcc源代码所得到的cc1程序调试,进入到cc1所在的目录,运行命令:


$ gdb cc1
$ break main
$ run -dr /PATH/test.c

这样就是以-dr为编译参数运行gcc来编译test.c文件了,并且在main函数的入口处设置了一个断点,-dr作为编译参数就是要求在RTL表示生成以后将其dump到一个以.rtl结尾的文件中去。接下来在rest_of_compilation之前再设置一个断点,并用continue命令运行到该断点,用backtrace命令查看此时函数栈帧的情况:


$ break rest_of_compilation
$ continue
$ backtrace

下表1给出了使用gdb调试时显示出的从main到rest_of_compilation的函数调用情况:

调用顺序 函数名字 所在文件名
#1

#2

#3

#4

#5

#6

#7

#8

#9

#10

#11

#12

#13

#14

#15

main

toplev_main

do_compile

compile_file

c_common_parse_file

c_parse_file

yyparse

finish_function

cgraph_finalize_function

cgraph_assemble_pending_functions

cgraph_expand_function

c_expand_body

c_expand_body_1

tree_rest_of_compilation

rest_of_compilation

main.c

toplev.c

toplev.c

toplev.c

c-opts.c

c-parse.y

c-parse.y

c-decl.c

cgraphunit.c

cgraphunit.c

cgraphunit.c

c-decl.c

c-decl.c

tree-optimize.c

toplev.c

表1. 部分函数调用栈帧列表

调试的结果证实我们前面的分析是正确的,从main函数到yyparse函数的调用顺序与我们阅读代码时所分析得到的结果是吻合的。现在我们得到了gcc编译时从yypare到rest_of_compilation之间的一系列函数调用,这些都是值得关注的目标,让我们返回到源码中去看看这些函数的功能。

时刻记得我们的目标:对于gcc如何生成tree结构我们并不关心,也不关心gcc是如何由中间表示层RTL生成汇编代码的,我们感兴趣的是RTL表示是如何生成的,并希望在RTL表示层做一些修改,以达到我们的目的。为了省去一些篇幅,本文中略去了对那些我们不太关心的函数的分析,直接跳转到RTL生成和处理相关的部分。

终于,在tree-optimize.c中的tree_rest_of_compilation中,我们发现了一系列看起来是与RTL生成有关的函数调用,特别引起我们注意的又是一个钩子函数:

(*lang_hooks.rtl_expand.stmt) (DECL_SAVED_TREE (fndecl));

这行代码的注释说这个钩子函数用来生成一个被编译函数的RTL表示,接下来还调用了几个函数来进行RTL生成阶段的最后处理(包括调用gcc编译时内部使用的垃圾收集函数),然后就调用了rest_of_compilation了。前面已经提到了,rest_of_compilation的作用是对RTL表示做优化并且生成汇编代码输出,至此我们可以做出这样的推断:在tree_rest_of_compilation调用了一系列生成RTL表示的函数之后,到调用rest_of_compilation之前,gcc的内部保存了一个原始的、未优化的RTL中间表示。如果我们希望对函数的RTL表示做一些修改,在这里插入代码做改动应该是一个不错的选择。

到这里,我们所关心的gcc编译流程基本已经结束了,也搞清了RTL表示在什么地方生成的,我们应该有一定的信心在RTL表示层上对gcc进行hack了。

3. RTL简介
我们的目标是在RTL表示层上hack gcc,所以有必要对RTL做一些介绍。在gcc internals中有专门的一章描述RTL,如果对RTL没有任何了解,那么它很值得您一看;同时,在理解和插入RTL语句的时候,这份文档也可以作为比较详尽的手册来参照。

在gcc的编译过程中,有三次比较重要的转换:

  1. 待编译的源代码―<gcc抽象语法树表示。
  2. gcc抽象语法树―<RTL表示。
  3. RTL表示-<汇编代码输出。

RTL是gcc内部使用的中间表示语言,为了对其有一个直观点的印象,我们可以把它dump出来看一看。使用

$ gcc -dr test.c

就可以得到test.c的RTL表示,文件名一般为test.c.00.rtl。

RTL的设计据说是从LISP语言得到了灵感,所以我们dump出来的.rtl文件看起来也像是一个LISP程序,每条RTL语句都是用来描述需要输出的指令的,可以对照我们dump出的.rtl文件以及上面提到的文档来深入学习RTL。但我们的要求不仅如此,我们需要插入自己的RTL语句来hackcc,必须阅读gcc源代码提供的RTL操作的接口,这个过程比较繁琐而且没有文档可以参考,唯一有帮助的就是已有的在RTL表示层上对gcc做的补丁,以吸取其他gcc hackers的经验,作者在尝试自己的补丁时曾经参考过StackGuard[8] 的代码,另外可以在gcc的maillist上看到有些hacker提供的patch,这些已有的工作对于gcc hacker newbie来说是很有裨益的。


[8] StackGuard实际上是一个做过补丁的GCC,可以做为在RTL表示层上hack GCC的一个例子来参考。

仅仅这么多文字来介绍RTL还远远不够,但是如果希望把RTL描述得十分清楚,那应该由另外一篇文章来完成了,本文就不再详述了。

4. Let's hack gcc!
下面进入hackgcc的实战阶段了,先说一下我的目的:我希望使用修改过的gcc编译程序的时候,能够在每个函数的开始和结束的地方插入一个函数调用语句,也就是说,在每个函数的第一条指令之前,由编译器强制插入一个函数调用,在函数最后一条指令结束之后,也要插入一个函数调用。下面用两段C语言代码来表达这个补丁的效果:

int foo()
{
first statement;



last statement;
}
int foo()
{
my_function_begin;
first statement;

last statement;
my_function_end;
}

左边一列是程序员正常编写的普通函数,我希望使用修改过的gcc编译该函数后,能够得到相当于编译右边这段函数的结果,就是对程序员透明地在每个函数的第一条语句之前和最后一条语句之后自动插入两个函数调用:my_function_begin和my_function_end。当然,这两个函数具体实现什么功能可以由程序员来编写,最简单的实现可以仅仅在标准输出上分别打印一句话表示该函数确实被调用了即可。

gcc中生成抽象语法树表示和RTL表示都是以一个完整的函数定义或者toplevel的声明为单位的,这也就意味着在tree_rest_of_compilation这个函数调用了一系列用于生成RTL表示的函数之后,我们所得到的只是当前正在被编译的函数的RTL表示,而并不是整个源程序的RTL表示,这正好方便我们以函数为单位来进行修改。

我们在tree_rest_of_compilation函数中调用rest_of_compilation之前插入一条语句,调用一个新函数modify_rtl来对gcc生成的RTL表示做一些处理。函数modify_rtl的定义放在function.c文件中,这是因为gcc在生成RTL表示时需要的相关函数大部分都定义在这个文件中,我们的补丁也可以看作是gcc生成RTL表示的一部分工作,所以把modify_rtl放到这个文件中定义是最合适的。

接下来工作的关键就集中到如何定义modify_rtl函数了。现在我们得到了当前编译函数的RTL表示,我们可以对这个RTL单元进行扫描,找到合适的位置分别调用my_function_begin和my_function_end函数即可。函数的RTL表示是一个双向连接的链表结构,其中每个节点称为一个insn[9] ,有的insn可能表示一条真实的汇编指令,有的则表示jump指令跳转的标签或者其它各种声明信息。为了简便起见,这里直接给出一个常用的gcc所提供的访问insn的宏和函数列表,并给出它们的功能:


[9] StackGuard实际上是一个做过补丁的GCC,可以做为在RTL表示层上hack GCC的一个例子来参考。

宏(函数)名 功能
INSN_UID(insn) 获取该insn的id
PREV_INSN(insn) 获取insn链表中该insn的前一个insn
NEXT_INSN(insn) 获取insn链表中该insn的后一个insn
GET_CODE(insn) 获取该insn的code
NOTE_LINE_NUMBER(insn) 如果insn的code是NOTE,则返回该insn对应源代码的行号,否则返回一个负数
Get_insns() 获取当前函数RTL表示的第一个insn
Get_last_insn() 返回当前函数RTL表示的最后一个insn

表2. 部分gcc提供的insn操作接口列表

一个函数完整的、未被优化的RTL表示中会有两个noteinsn表示函数的开始和结束,gcc定义了两个全局变量NOTE_INSN_FUNCTION_BEGIN和NOTE_INSN_FUNCTION_END来表示这两个note insn的行数。这样我们就可以扫描当前RTL单元,当碰到这两个noteinsn的时候,就可以插入相应的函数调用语句了。

gcc提供了emit_library_call函数来插入一个函数调用,这个函数返回的是一个表示函数调用的RTL表达式,并默认地把这个RTL表达式插入到当前RTL单元的最后一个insn之后。所以如果直接调用emit_library_call,就会把函数调用语句插入到RTL单元最后一个insn之后,而不是我们所希望的函数开始和结束的地方,我们可以使用start_sequence和end_sequence函数,它们产生一个相对独立的sequence并把函数调用语句保存到一个RTL表达式中以备后用。

我们已经找到插入函数调用的点,并且也生成了表示函数调用的RTL语句,现在就可以使用gcc提供的emit_insn_before和emit_insn_after函数来插入RTL语句了。

到这里,modify_rtl函数的实现基本已经成型了,下面这段示例代码就可以完成在每个函数的开始处插入RTL语句的功能:


int modify_rtl()
{
	rtx insn;
	rtx seq;

	//emit my_function_begin at the beginnig of each function
	start_sequence();
	emit_libarary_call(gen_rtx(SYMBOL_REF, Pmode, my_function_begin),
									0, VOIDmode, 0);
	seq = get_insns();
	end_sequence();

	for(insn = get_insns(); ; insn = NEXT_INSN(insn))
		if((GET_CODE(insn) == NOTE)
			&& (NOTE_LINE_NUMBER(insn) ==
				NOTE_INSN_FUNCTION_BEGIN))
		break;

	emit_insn_after(seq, insn);

	…
}

这段代码中所使用数据结构、函数的具体功能和用法,属于十分细节的内容,无须在这里描述清楚,请读者参考gcc源代码。

对于在函数结束的地方插入my_function_end函数同样如此,我们可以用get_last_insn得到RTL单元的最后一个insn,然后使用PREV_INSN(insn)开始向前扫描,遇到行号为NOTE_INSN_FUNCTION_END的noteinsn时,用emit_insn_before把相应的函数调用RTL表达式插入到这个insn之前即可。

现在这个patch的基本功能已经完成了,我们还可以再做一些工作使得它功能更强大和实用一些,比如加入一个编译选项(比如-finsert-function)来指定是否启用这个patch的,当编译的命令行参数中没有提供这个编译选项时,我们所作的补丁就不起作用。关于如何增加编译选项,我们可以参考opts.c中的decode-options函数,在此就不详细分析了。

在modify_rtl中调用current_function_name函数可以得到当前正在被编译的函数名,我们可以把这些函数名写到一个文件中去,这样可以记录我们对哪些函数做了修改;还可以实现一个过滤器,在启用了patch的情况下,对于指定的函数,我们还可以将其过滤掉,不对其做处理,这些功能也是很容易实现的。

我们还可以再实现一些功能,比如在扫描RTL的时候,如果发现一条call_insn,可以把这条call指令所调用的函数名记录下来,这样我们甚至可以得到一个程序运行时刻的动态的函数调用关系图,这就可以描绘程序的实际运行轨迹。

最后,还需要把my_function_begin和my_function_end两个函数实现一下,可以把它们的功能扩展一下,不是仅仅输出一条语句到标准输出,而是记录一些信息到文件中,这样就可以得到一个以函数为粒度的运行时刻日志,甚至可以使这两个函数与linux内核联系起来,做一些特殊的检查工作等等,这样就使得我们的patch有一些实用性了。这两个函数我们可以在mylib.c中实现,编译成一个sharedobject,使用如下命令编译:


$ gcc mylib.c -c -fPIC
$ gcc mylib.o -shared -o libmylib.so

把libmylib.so放到/usr/lib目录下,那么在编译的时候只需加上-lmylib参数就可以使用这个shared object中的函数了。

剩下的工作就是进行调试和测试了,当我们解决了各种问题,使这个修改过的编译器能够完美的运行起来的时候,也许我们就能体会到gcc hacker的那种成就感和喜悦之情了。

5. 经验总结
先说一下我自己尝试的结果,我是基于gcc version3.4.0工作的,给gcc加入了一个编译选项以选择是否启用添加的补丁,可以在每个函数的开始和结束的时候插入函数调用,也可以在函数调用之前和返回之后插入函数调用,实现了一个过滤器,可以忽略一些函数不对其做处理,并且可以在运行时将一些信息记录到文件中去留待分析。这个补丁的功能基本上就是这些了,实现方法可能和本文中的方法有所不同,文中描述的方法是较早的时候我采用的方法,现在则进行了一些改动,这里就不详加介绍了。我已经成功的使用“我的”gcc编译了emacs和lynx等实用软件,运行正常,补丁功能也正常,可以说是取得了一个小小的成功。但是我没有空间可以上载我的补丁,有兴趣的读者可以通过e-mail向我索取。

最后谈谈我的经验:

在理解gcc的编译流程以及试图找到做补丁的思路的时候,需要多阅读文档,包括学习已有的工作是怎么做的。不要贸然尝试,不要奢望可以凭运气达成目的,尽量找到最合适的实现方法,在确立了一个基本思路之后,可以在gcc的maillist上咨询一下,看看有没有人提供更好的思路,在确信自己思路的可行性之后再开始具体的工作。

在做具体实现的时候,肯定会遇到各种各样的问题,比如在编译自己修改过的gcc时会出错,或者用patch过的gcc编译程序时出错,或者是编译通过运行时刻出错等等,这时候需要耐心地检查代码和进行debug,尽量自己解决问题,不要把一些特别细节地问题拿到maillist上讨论。我记得在maillist上曾经有人严厉地告诫我:“you won't go very far if you ask a question eachtime you get anerror”,自己debug才是解决问题的最好方法,当然如果实在不明白的问题必须拿到maillist上去讨论,这时候要尽量详细的描述自己的目的和问题,才能够得到有效的帮助。

好了,这就是我自己学习和尝试hack gcc的工作过程,希望我的一些经验能够给您帮助,如果对本文中的观点有疑问或者在学习gcc的时候碰到困难,欢迎与我探讨。

参考资料

  1. GCC internals.http://gcc.gnu.org/onlinedocs/gccint/,这是得到公认的除了gcc源码以外,学习gcc最好的材料,虽然比较难读,但它的权威性和全面性是毋庸置疑的,GCC的手册和info也是很好的参考资料。
  2. GCC Front end HOWTO, 通过自己设计一个GCC前端来帮助GCC hacker newbie来学习和了解GCC,http://www.icewalkers.com/Linux/Howto/GCC-Frontend-HOWTO.html#toc1,适合新手阅读,作者还提供了相关程序的软件包。
  3. StackGuard,http://www.immunix.org/stackguard.html,可以作为一个在RTL表示层hack gcc的实例来学习。
关于作者
王逸,2002年秋季入学的南京大学计算机科学与技术系硕士研究生,在分布式系统国家重点实验室学习。对于软件安全、linux系统和无线网络有兴趣,目前工作主要集中在缓冲区溢出攻击的防范上。您可以通过cnnjuwy@hotmail.com与我联系,也可以在南京大学小百合bbs上(http://bbs.nju.edu.cn/或者http://lilybbs.net/)与LinuxLover账号联系。
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics