GCC treeのデータ構造を読んでみました。
treeはgccのfront endで使われている木構造を表すデータ構造です。
gccはパーサでソースコードをtreeに変換します。
treeのデータ構造はtree.hで定義されています。
対象: gcc 0.9 (私がgcc 0.9 のソースコードを読んでいるので→http://gcc.shoutwiki.com/wiki/Main_Page)
tree_node
- treeはtree_nodeを連結したデータ構造です。
- tree_nodeはunionとして定義
union tree_node
{
struct tree_shared shared;
struct tree_int_cst int_cst;
struct tree_real_cst real_cst;
struct tree_string string;
struct tree_complex complex;
struct tree_identifier identifier;
struct tree_decl decl;
struct tree_type type;
struct tree_exp exp;
struct tree_stmt stmt;
struct tree_if_stmt if_stmt;
struct tree_bind_stmt bind_stmt;
struct tree_case_stmt case_stmt;
};
tree_shared
- tree_nodeのメンバは、先頭にtree_shared構造体を持つ。
struct tree_shared
{
int uid;
union tree_node *chain;
union tree_node *type;
enum tree_code code : 8; /* Give it a byte only */
/* the attributes: (special properties of node) */
-
gcc 2.xだとtree_sharedはtree_commonという名前になっているみたいです。
-
よく出てくる マクロ TREE_CODE(x)でtreeのcodeを取得する。
#define TREE_CODE(NODE) ((NODE)->shared.code)
-
codeはtree_nodeの種類を表す。 code の値は tree.defで定義。
-
整数定数ならINTEGER_CST、加算の式なら、PLUS_EXPR、if文なら、IF_STMT、変数宣言なら、VAR_DECL、などです。
-
type は型のtree_nodeを指す。
-
chain は次のtree_nodeを指す。
-
uidはtree_node毎にuniqueなidを持つ。
tree_int_cst
- 整数定数は 上位と下位をlong型で持つ。
- 枝は無い。
struct tree_int_cst
{
char shared[sizeof (struct tree_shared)];
long int_cst_low;
long int_cst_high;
};
tree_exp
- 式は枝として、operandsを持つ
- オペランドの数(枝の数)は式の種類により異なる。
struct tree_exp
{
char shared[sizeof (struct tree_shared)];
union tree_node *operands[1];
};
tree_stmt
- bodyを持つ
- loop_stmtはこの構造体を使って表す。
struct tree_stmt
{
char shared[sizeof (struct tree_shared)];
char *filename;
int linenum;
union tree_node *body;
};
tree_if_stmt
- if文は枝として、条件、then部分、else部分の３つを持つ。
- stmtはファイル名と行数の情報を持つ。
struct tree_if_stmt
{
char shared[sizeof (struct tree_shared)];
char *filename;
int linenum;
union tree_node *cond, *thenpart, *elsepart;
};
tree_case_stmt
- switch case分は、indexとcase_listを持つ。
struct tree_case_stmt
{
char shared[sizeof (struct tree_shared)];
char *filename;
int linenum;
union tree_node *index, *case_list;
};
tree_nodeのsize
- tree_nodeのサイズはcodeによって異なる。make_node()を見ると分かる。
- type が d or t なら固定長
- それ以外なら tree.defを使って定義するtree_code_length[]の値分を追加して確保する。
switch (type)
{
case 'd': /* A decl node */
length = sizeof (struct tree_decl);
break;
case 't': /* a type node */
length = sizeof (struct tree_type);
break;
case 's': /* a stmt node */
length = sizeof (struct tree_shared)
+ 2 * sizeof (int)
+ tree_code_length[(int) code] * sizeof (char *);
break;
default: /* an expression or constant. */
length = sizeof (struct tree_shared)
+ tree_code_length[(int) code] * sizeof (char *);
}