GCC GENERIC tree

Generic 是GCC使用的三种中间语言(IL)的一种,另外两种是Gimple和RTL。

"The purpose of GENERIC is simply to provide a language-independent way of representing 

an entire function in trees"

从字面上翻译，GENERIC为的就是提供一个语言无关的方法来表示一个函数，它的表现形式是trees。

如果你把trees理解为数据结构中的树结构(二叉树等等)，那么你估计要迷惑一段时间。

我们应该把trees理解为 - “一个叫做tree的C structure”。

也就是说GENERIC是把函数(当然也包含类，表达式，namespace等)的信息存储在一个叫tree的C structure中。

1. struct tree

那么这个叫做tree的struct是什么样子的？没有仔细分析GCC代码，但从GCC internal文档中我们可知，

C类型的tree是有很多变种的，但它们都包含两个相同的field - chain，type。chain是一个可用作单向

链表的指针，它指向另外的trees。type顾名思义就是tree structure的类型。 我们用宏TREE_CHAIN来访问

tree的chain，TREE_TYPE来访问tree的type

有了chain这个指针，我们就可以遍历所有的tree结构了，示例如下

tree decl = ....

for( ; decl != 0; decl = TREE_CHAIN(decl) )

{

    //do something

}

我们从一个tree结构开始(声明为tree的变量其实是个指向结构体的指针)，如果它的chain不等于0就意味着还有下一个tree，使用TREE_CHAIN得到其下一个tree struct。

接下来是如何在tree struct上dosomething的问题。

既然类型为tree的变量是个指针，并且它指向的struct还有很多变体，那么除了common的chain和type外，我们很难直接访问其fields（不知道具体类型啊）。

怎么办？我们可以通过GCC提供的宏来访问。例如

2. TREE_CODE

可以使用TREE_CODE宏来判别一个特定的tree structure的类型，其返回是一个int值，其实是一个enum值，因为tree的code定义如下

enum tree_code {

#include "all-tree.def"

MAX_TREE_CODES

};

而文件all-tree.def内容如下，可见它集合了base code(定义在tree.def中)，各个语言的扩展code，例如c-common.def，

java-tree.def等

#include "tree.def"

END_OF_BASE_TREE_CODES

#include "c-family/c-common.def"

#include "ada/gcc-interface/ada-tree.def"

#include "cp/cp-tree.def"

#include "java/java-tree.def"

#include "objc/objc-tree.def"

我们看一下tree.def的内容，有个直观的概念

DEFTREECODE (ERROR_MARK, "error_mark", tcc_exceptional, 0)

DEFTREECODE (IDENTIFIER_NODE, "identifier_node", tcc_exceptional, 0)

DEFTREECODE (TREE_LIST, "tree_list", tcc_exceptional, 0)

DEFTREECODE (TREE_VEC, "tree_vec", tcc_exceptional, 0)

DEFTREECODE (BLOCK, "block", tcc_exceptional, 0)

DEFTREECODE (OFFSET_TYPE, "offset_type", tcc_type, 0)

DEFTREECODE (ENUMERAL_TYPE, "enumeral_type", tcc_type, 0)

DEFTREECODE (BOOLEAN_TYPE, "boolean_type", tcc_type, 0)

DEFTREECODE (INTEGER_TYPE, "integer_type", tcc_type, 0)

DEFTREECODE (REAL_TYPE, "real_type", tcc_type, 0)

DEFTREECODE (POINTER_TYPE, "pointer_type", tcc_type, 0)

DEFTREECODE (REFERENCE_TYPE, "reference_type", tcc_type, 0)

DEFTREECODE (NULLPTR_TYPE, "nullptr_type", tcc_type, 0)

DEFTREECODE (FIXED_POINT_TYPE, "fixed_point_type", tcc_type, 0)

DEFTREECODE (COMPLEX_TYPE, "complex_type", tcc_type, 0)

DEFTREECODE (VECTOR_TYPE, "vector_type", tcc_type, 0)

DEFTREECODE (ARRAY_TYPE, "array_type", tcc_type, 0)

DEFTREECODE (RECORD_TYPE, "record_type", tcc_type, 0)

DEFTREECODE (UNION_TYPE, "union_type", tcc_type, 0) /* C union type */

DEFTREECODE (QUAL_UNION_TYPE, "qual_union_type", tcc_type, 0)

DEFTREECODE (VOID_TYPE, "void_type", tcc_type, 0)

DEFTREECODE (FUNCTION_TYPE, "function_type", tcc_type, 0)

DEFTREECODE (METHOD_TYPE, "method_type", tcc_type, 0)

DEFTREECODE (LANG_TYPE, "lang_type", tcc_type, 0)

DEFTREECODE (INTEGER_CST, "integer_cst", tcc_constant, 0)

DEFTREECODE (REAL_CST, "real_cst", tcc_constant, 0)

DEFTREECODE (FIXED_CST, "fixed_cst", tcc_constant, 0)

DEFTREECODE (COMPLEX_CST, "complex_cst", tcc_constant, 0)

DEFTREECODE (VECTOR_CST, "vector_cst", tcc_constant, 0)

DEFTREECODE (STRING_CST, "string_cst", tcc_constant, 0)

DEFTREECODE (FUNCTION_DECL, "function_decl", tcc_declaration, 0)

因为tree.def排在all-tree.def的第一位，而enum的值是从0开始的，那么我们可以知道

FUNCTION_DECL的值其实是30。

只有了这个int的code，我们可以和enum tree_code的比较来知道tree struct是什么类型的。

另外，我们可以通过数组tree_code_name[tree_code]来得到一个可读的字符串，例如

tree_code_name[FUNCTION_DECL] = "function_decl"

3. TREE TYPE

我们可以通过TREE_TYPE来访问一个tree的type(是用另一个tree struct来表示的)。

例如对一个 "int a;"来说，tree的type就是integer_type(也是tree_code定义的)

 if (tree t = TREE_TYPE (decl))

    cout << "type " << tree_code_name[TREE_CODE(t)] << endl;

4. IDENTIFIER_NODE

我们知道可以用TREE_CODE来得到一个tree struct的类型（是integer_type，boolean_type

还是function_decl等）。

那么这个tree struct所表示的function的名字怎么得到呢？

（例如一个表达式 "int a"的的tree code是var_decl，tree type是integer_type,那么标示符a是怎么得到呢？）

我们需要IDENTIFIER_NODE， 它表示一个标示符 (indentifier)

"标识符是用户编程时使用的名字。我们指定某个东西、人，都要用到它，他或她的名字；在数学中解方程时，我们也常常用到这样或那

样的变量名或函数名。同样的道理，在电脑语言中，对于变量，常量，函数，语句块也有名字，我们统统称之为标识符。"

可以看到它正是我们想要的 - int a中的a就是变量个标示符。

如何取得一个变量声明的标示符呢？使用宏DECL_NAME，例如

tree id = DECL_NAME(decl)

其中id就是IDENTIFIER_NODE，它也表示为一个tree struct. 

接下来，我们可以用IDENTIFIER_POINTER来得到可读的标示符名字 - “a”

IDENTIFIER_POINTER(id)

5. 常见的TREE，及其相互转换

到目前为止，常见的tree有

decl tree(用来表示声明，函数声明，变量声明，类声明，namespace声明等等)，

type tree(被decl tree包含为一个common field，表示decl的类型，如interger，bool，real，function decl，record等)

identifier tree(用来表示标示符，如变量的名字，函数的名字，类的名字等)

这几个tree互相关联，共同描述了C/C++的声明语句。它们之间可以通过宏互相转换

例如一个函数声明：  int foo(); 

在GENERIC中表现为一个decl tree。

有了这个decl tree想知道它是否是一个函数声明，则取其type tree，看看是否是function decl。

想得到其名字foo，则需要得到indentifier tree。

6. C++ GENERIC的根

我们讨论了这么半天，我们可以用TREE_CHAIN得到下一个tree，那么第一个tree哪来的？

对于C++来说，我们用"根变量global_namespace".

7. C++遍历不能用cp_namespace_decls

cp_namespace_decls将返回包含在命名空间中的声明，包括类型，重载函数，其它命名空间等等。

但它不包含嵌套的namespace。

那么对于一个C++文件

int a;

namespace tt

{

};

int main(int argc, char* argv[])

{

  return 0;

}

是不能通过“cp_namespace_decls(global_namespace)”来得到“namespace tt”的。

对于C++，应该参看GCC对C++的特殊处理(相对于tree.def, tree.h来说) cp/cp-tree.def cp/name-lookup.h, 其中

      typedef struct cp_binding_level cxx_scope;  

这个结构除了被用于名字空间及类的作用域外，还被用于C++概念中的其他作用域。

例如：函数（被视为与{}块等价）、try/catch块、函数参数、for初始化值、模板参数、特化模板的参数.

(抄自 《GCC-3.4.6源代码学习笔记》)

所以应该用cp_binding_level来遍历。具体代码参见

  ~boris/blog/2010/05/10/parsing-cxx-with-gcc-plugin-part-2/