gcc源码分析（AST抽象语法树）

三、AST相关

抽象语法树是编译系统中最常见的一种树形的中间表示形式，用来对前端语言的源代码进行规范的抽象表示。不同的高级程序设计语言通过其相应的词法/语法分析过程，会得到不同形式的抽象语法树，这些抽象语法树与编程语言的特征紧密相关，一般都包含了部分语言相关的AST节点表示。从这个角度上来讲，AST是编程语言相关的， C语言的源代码经过C语言特定的词法/语法分析过程，将生成C语言的AST。

1、AST（抽象语法树）

在gcc中GENERIC是指规范的AST，，即GENERIC形式的AST均能在gcc/tree. h中所表示的树节点表示。引入GENERIC的目的是寻找一种与前端语言无关的AST统一表示，是一种通用的处理tree_identifier而已。AST这种树形的中间表示，主要包括：树节点的种类及其语义、树节点的存储、AST操作以及AST的生成过程等。

1.1 树结点的声明

树节点声明中最基本的4个概念：

• 标识（TREE_CODE）:DEFTREECODE宏定义中的SYM参数，描述了该节点代表的是一个什么样的节点。
• 名称（NAME）:DEFTREECODE宏定义中的NAME参数，表示该树节点的名称，使用字符串来描述，主要用来进行AST中间结果的显示，方便用户直观地了解该树节点的信息。
• 类型（TREE_CODE CLASS, TCC）:DEFTREECODE宏定义中的TYPE参数，描述了该树节点的TREE_CODE所属的类型。
• 长度：DEFTREECODE宏定义中的LEN参数，用来描述该树节点所包含的操作数的数目。

用下面这种宏去定义：

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

树节点的类型主要包括了常量节点、类型节点、声明节点、比较表达式节点、单目运算表达式节点、双目运算表达式节点等。

1.2 树结点的结构

1.2.1 tree_node联合体

tree_node联合体定义了全部树结点结构体。

## gcc/tree-core.h
union GTY ((ptr_alias (union lang_tree_node),desc ("tree_node_structure (&%h)"), variable_size)) tree_node {struct tree_base GTY ((tag ("TS_BASE"))) base;struct tree_typed GTY ((tag ("TS_TYPED"))) typed;
.......
}

1.2.2 tree_base结构体

其中最关键的是tree_base结构体：该结构体定义了所有树节点最基本的属性，是构成其他树节点存储结构的基类（类似于面向对象的概念，这个思想在gcc中大量使用）。其主要包括了code字段，用来存储TREE_CODE，并标识该树节点的语义，其取值在枚举类型enum tree_code中取值。tree_base结构体中还定义了大量的标志字段，分别描述该树节点的某些语法、语义的信息，例如常量标志、无符号标志、只读标志等。

struct GTY(()) tree_base {ENUM_BITFIELD(tree_code) code : 16;unsigned side_effects_flag : 1;unsigned constant_flag : 1;unsigned addressable_flag : 1;unsigned volatile_flag : 1;unsigned readonly_flag : 1;unsigned asm_written_flag: 1;unsigned nowarning_flag : 1;unsigned visited : 1;unsigned used_flag : 1;unsigned nothrow_flag : 1;unsigned static_flag : 1;unsigned public_flag : 1;unsigned private_flag : 1;unsigned protected_flag : 1;unsigned deprecated_flag : 1;unsigned default_def_flag : 1;.......
}

1.2.3 tree_common结构体

tree chain字段可以将多个有一定关系的树节点连接成一个链表。tree type字段的值在不同的树节点中有不同的含义。例如，在所有表达式节点中，type字段指向表达式的类型节点；在指针类型节点（其TREE_CODE为POINTER_TYPE）中，此字段指向指针所指向的类型节点；在数组引用节点（其TREE_CODE为ARRAY_TYPE）中，此字段指向数组元素的类型节点；在TREE_CODE为VECTOR_TYPE的树节点中，该字段指向向量元素的类型节点。通常使用TREE_TYPE（node）宏来访问node节点的type字段。

struct GTY(()) tree_typed {struct tree_base base;tree type;
};struct GTY(()) tree_common {struct tree_typed typed;tree chain;/**将多个有一定关系的树节点连接成一个链表/
};

1.2.4 常量结构体

gcc中定义了struct tree_int_cst、struct tree_real_cst、struct tree_fixed_cst、struct tree_vector、struct tree_string、struct tree_complex等几种结构体，分别存储整型常量、实数常量、定点数常量、向量常量、字符串常量以及复数常量。

//1、整型常量
struct GTY(()) tree_int_cst {struct tree_typed typed;HOST_WIDE_INT val[1];
};  
//2、实数常量
/*结构体struct tree_real_cst用来存储实数常量*/
struct GTY(()) tree_real_cst {struct tree_typed typed;struct real_value * real_cst_ptr;
};
//3、定点数常量
struct GTY(()) tree_fixed_cst {struct tree_typed typed;struct fixed_value * fixed_cst_ptr;
};
/*
常用的宏定义：#define TREE_FIXED_CST_PTR(NODE) (FIXED_CST_CHECK (NODE)->fixed_cst.fixed_cst_ptr)#define TREE_FIXED_CST(NODE) (*TREE_FIXED_CST_PTR (NODE))
*/
//4、字符串常量
/*字符串使用struct tree_string结构体来存储*/
struct GTY(()) tree_string {struct tree_typed typed;int length;char str[1];
};
/*这部分可以分析内存信息：字符串常量节点所描述的字符串常量就存储在struct tree_string中以str成员指向的地址空间中*/
//5．复数常量
struct GTY(()) tree_complex {struct tree_typed typed;tree real;tree imag;
};
/*
下面两个宏分别用来访问该实数常量的实部（real字段）和虚部（imag字段），这两个字段均为指向树节点的指针。#define TREE_REALPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.real)#define TREE_IMAGPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.imag)
*/
//6、向量常量
struct GTY(()) tree_vector {struct tree_typed typed;tree GTY ((length ("TYPE_VECTOR_SUBPARTS (TREE_TYPE ((tree)&%h))"))) elts[1];    //用以获取节点的各个向量
};

1.2.5 标识符节点

标识符节点使用struct tree_identifier结构体存储，定义如下：

struct GTY(()) tree_identifier {struct tree_common common;/*struct tree_common common结构体字段描述了该树节点的基本属性。*/struct ht_identifier id;
};struct GTY(()) ht_identifier {const unsigned char *str;unsigned int len;unsigned int hash_value;
};

上述的struct ht_identifier在libcpp/include/symtab.h中予以定义，该结构体中的str和len字段分别描述该标识符对应的字符串名称及其长度，hash_value是该标识符名称的一个hash值，该hash值在标识符的查找、比较等操作中使用。

注：AST是源代码在GCC系统中的一种中间表示形式，该中间形式是通过GCC前端的词法/语法分析所构造的。

其他的树结点的结构不做详细介绍，有兴趣可自行查看。

2、符号绑定,作用域与block树节点

2.1 lang_identifier结构体

在前面已知gcc中通过一个tree_identifier结构体来代表一个标识符的树节点，但实际分配时会为标识符分配一个扩展的lang_identifier节点，其结构如下:

struct GTY(()) lang_identifier {struct