Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1072588
  • 博文数量: 104
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1868
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(104)

文章存档

2013年(1)

2012年(9)

2011年(41)

2010年(3)

2009年(3)

2008年(47)

分类:

2008-07-18 17:36:21

    本文分析GCC4.3.1的源代码。如某位牛人所说,我并不打算做“参考手册”式的源码分
析,而是打算做“航海日志”式的。

* GCC中的树
    对于GCC的前端和高级的分析和及优化而言,树是其核心的数据结构。经过语法分析的
源程序都表示为树的形式。这里要说一下,GCC中,实际上有三种树:GENERIC,GIMPLE和SS
A。
    GENERIC:语言无关的一种通用表示,源程序经过前端的语法分析后,会被转化成这种
形式。其实,这种形式中是可能有与语言相关的节点的,对于这样的节点,前端要负责提供
一个将其转化成GIMPLE的函数。几乎没有什么分析和优化是在这个中间表示上进行的。
    GIMPLE:是GENERIC加了某些限制的简化版本。GENERIC表示的程序,会被转化成GIMPLE
表示的,这个是真正的语言无关的表示。有一些分析和优化是在这个表示上进行的。
    SSA:SSA是另外一种语言无关的中间表示,由GIMPLE转化来,大量的分析和优化在其上
进行。

    首先,我们看一下,gcc目录下的那些文件名中包含"tree":
%{
ChangeLog.tree-ssa  tree-nomudflap.c           tree-ssa-loop-niter.c
c-tree.h            tree-nrv.c                 tree-ssa-loop-prefetch.c
print-tree.c        tree-object-size.c         tree-ssa-loop-unswitch.c
tree-affine.c       tree-optimize.c            tree-ssa-math-opts.c
tree-affine.h       tree-outof-ssa.c           tree-ssanames.c
tree-browser.c      tree-parloops.c            tree-ssa-operands.c
tree-browser.def    tree-pass.h                tree-ssa-operands.h
tree.c              tree-phinodes.c            tree-ssa-phiopt.c
tree-cfg.c          tree-predcom.c             tree-ssa-pre.c
tree-cfgcleanup.c   tree-pretty-print.c        tree-ssa-propagate.c
tree-chrec.c        tree-profile.c             tree-ssa-propagate.h
tree-chrec.h        tree-scalar-evolution.c    tree-ssa-reassoc.c
tree-complex.c      tree-scalar-evolution.h    tree-ssa-sccvn.c
tree-data-ref.c     tree-sra.c                 tree-ssa-sccvn.h
tree-data-ref.h     tree-ssa-address.c         tree-ssa-sink.c
tree.def            tree-ssa-alias.c           tree-ssa-structalias.c
tree-dfa.c          tree-ssa-alias-warnings.c  tree-ssa-structalias.h
tree-dump.c         tree-ssa.c                 tree-ssa-ter.c
tree-dump.h         tree-ssa-ccp.c             tree-ssa-threadedge.c
tree-eh.c           tree-ssa-coalesce.c        tree-ssa-threadupdate.c
tree-flow.h         tree-ssa-copy.c            tree-ssa-uncprop.c
tree-flow-inline.h  tree-ssa-copyrename.c      tree-stdarg.c
tree-gimple.c       tree-ssa-dce.c             tree-stdarg.h
tree-gimple.h       tree-ssa-dom.c             treestruct.def
tree.h              tree-ssa-dse.c             tree-tailcall.c
tree-if-conv.c      tree-ssa-forwprop.c        tree-vect-analyze.c
tree-inline.c       tree-ssa-ifcombine.c       tree-vect-generic.c
tree-inline.h       tree-ssa-live.c            tree-vectorizer.c
tree-into-ssa.c     tree-ssa-live.h            tree-vectorizer.h
tree-iterator.c     tree-ssa-loop.c            tree-vect-patterns.c
tree-iterator.h     tree-ssa-loop-ch.c         tree-vect-transform.c
tree-loop-linear.c  tree-ssa-loop-im.c         tree-vn.c
tree-mudflap.c      tree-ssa-loop-ivcanon.c    tree-vrp.c
tree-mudflap.h      tree-ssa-loop-ivopts.c
tree-nested.c       tree-ssa-loop-manip.c
}%
    ...居然有这么多。好吧,仔细看一下,其实有很多以tree开始的文件都是优化遍。我
们先来找到对树的定义。其中有三个文件最为可疑:tree.[h def c]。首先看看tree.h。
这个文件,从感觉上应该定义了树的接口。该文件的第一行注释是
%{
/* Front-end tree definitions for GNU compiler.
}%
看来是感觉对了。其他的注释都是废话。文件中的第一个比较重要的数据结构如下,它定义
了树中可以出现的节点的编码。
%{
/* Codes of tree nodes */

#define DEFTREECODE(SYM, STRING, TYPE, NARGS)   SYM,

enum tree_code {
#include "tree.def"

  LAST_AND_UNUSED_TREE_CODE /* A convenient way to get a value for
                   NUM_TREE_CODES.  */
};

#undef DEFTREECODE
}%
可以看到,这时用到了tree.def文件。这个文件原来是定义和树的节点相关的信息的,使用
了通常的编程技巧,tree_code中仅仅使用了DEFTREECODE的第一个域,定义了表示这个节点
的常量编码。我们看一下tree.def这个文件。第一行的注释说的很清楚。
%{
/* This file contains the definitions and documentation for the
   tree codes used in GCC.
}%
根据名字,DEFTREECODE中四个域大概表示节点的枚举常量名、字符串名、类型、参数(子节
点)的数目。在tree.def文件中,有更为详细的说明。对于类型为 tcc_references,
tcc_expression, tcc_comparison, tcc_unary, tcc_binary, tcc_statement类型的节点,
(它们都用struct tree_exp来表示),第四个参数是要为它们分配的参数的位置的个数。这
个同时也确定了树节点的大小。其他类型的节点使用不同的结构体表示,其大小由一个
tree_union的成员结构体确定,第四个参数应该为0。语言前端自己定义的节点类型如果是
tcc_exceptional 或 tcc_constant,此时,前端必须定义tree_size这个langhook来指出自
己定义的节点的大小。
在这里,这些树节点的定义顺序是被仔细安排的,这样,很多判断可以变成范围判断。
tree.def里面,详细地给出了每一个树节点的定义和文档说明。这个文件完全可以当作树的
参考手册。这里面的节点的定义,应该给出了GENERIC的定义,同时,由于GIMPLE是GENERIC
的一个受限制的子集,所以也给出了GIMPLE的定义。我们先继续看tree.h,回头再给出所有
节点的详细说明(其实大部分也就是翻译一下他们的注释)。
%{
/* 这个是编译器中最大可用的树节点的种类的数目 */
#define MAX_TREE_CODES 512  
/* 这个定义在tree.c中,并在init_ttree()中进行了初始化。
 * 掩码,用于表示一个树节点(union tree_node)包含什么。和下面的枚举配合使用 */
extern unsigned char tree_contains_struct[MAX_TREE_CODES][64];
#define CODE_CONTAINS_STRUCT(CODE, STRUCT) (tree_contains_struct[(CODE)][(STRUCT)])

/* 下面文件中定义的每一个枚举值都要对应union tree_node中的唯一一个成员。这些枚举值用于区分
 * 联合体的成员,用于垃圾收集以及用于在数组tree_contains_struct中指定每一类树节点包含什么
 * 结构 */
#define DEFTREESTRUCT(ENUM, NAME) ENUM,
enum tree_node_structure_enum {
#include "treestruct.def"
  LAST_TS_ENUM
};

/* 可见,在tree.def中定义的节点都是语言无关的*/
/* Number of language-independent tree codes.  */
#define NUM_TREE_CODES ((int) LAST_AND_UNUSED_TREE_CODE)
}%
刚才说了,每一个树节点都有一个类型,这里就定义了可用的类型。
%{
/* Tree code classes.  */

/* Each tree_code has an associated code class represented by a
   TREE_CODE_CLASS.  */

enum tree_code_class {
  tcc_exceptional, /* 用于不能归于其他类型的类型 */
  tcc_constant,    /* 常量类型 */
  /* 一下两者的定义顺序很重要 */
  tcc_type,        /* 用于表示“类型”的类型 */
  tcc_declaration, /* 声明,同时也可以表示变量引用 */
  tcc_reference,   /* 对主存的引用,类似于指针 */
  tcc_comparison,  /* 比较表达式 */
  tcc_unary,       /* 一元算数表达式 */
  tcc_binary,      /* 二元算数表达式 */
  tcc_statement,   /* 语句表达式,它一般有副作用,并且我们不关心它自己的值 */
  tcc_vl_exp,      /* 有变长操作数向量的函数调用或是其它表达式 */
  tcc_expression,  /* 不能归类于以上表达式的其他表达式 */
  tcc_gimple_stmt  /* 一个GIMPLE的语句,只有一个赋值节点是这个类型 */
};
}%
上面定义的每一种类型,都有一个对应的字符串表示,大概是用于打印输出,便于阅读。该
字符串表示在tree.h中声明,在tree.c中定义。枚举常量和字符串必须对应。
%{
const char *const tree_code_class_strings[] =
{
  "exceptional",
  "constant",
  "type",
  "declaration",
  "reference",
  "comparison",
  "unary",
  "binary",
  "statement",
  "vl_exp",
  "expression",
  "gimple_stmt"
};
/* 该宏用于返回参数对应的字符串 */
#define TREE_CODE_CLASS_STRING(CLASS)\
        tree_code_class_strings[(int) (CLASS)]
}%
既然每一个节点都有类型,就必然可以从节点的编码查到它的类型,这个正是下面这个数组
完成的功能。
%{
extern const enum tree_code_class tree_code_type[];
#define TREE_CODE_CLASS(CODE)   tree_code_type[(int) (CODE)]
}%
这里,只是声明了这个数组,并给出了用于查询的宏。对于不同的前端,这个数组有不同的
定义。这是由于,这个数组应该包含前端定义的所有的节点类型,不同的前端,可能有不同
的自定义节点。例如,在c的前端中,是这样定义的(c-lang.c)。
%{
#define DEFTREECODE(SYM, NAME, TYPE, LENGTH) TYPE,

const enum tree_code_class tree_code_type[] = {
#include "tree.def"
  tcc_exceptional,
#include "c-common.def"
};
#undef DEFTREECODE
}%
同时,我们也发现,c前端自定义的树节点在文件c-common.def中。在这之后,是用于节点
类型判断的一系列的宏。
下面这个数组用于记录查找每一种树节点的“长度”,及参数个数,就是DEFTREECODE中最
后一个参数。基于同样的原因,该数组在这里也只有声明,每个前端独立定义自己的数组
%{
/* Number of argument-words in each kind of tree-node.  */

extern const unsigned char tree_code_length[];
#define TREE_CODE_LENGTH(CODE)  tree_code_length[(int) (CODE)]
}%
c的前端的定义如下(c-lang.c)
%{
#define DEFTREECODE(SYM, NAME, TYPE, LENGTH) LENGTH,

const unsigned char tree_code_length[] = {
#include "tree.def"
  0,
#include "c-common.def"
};
#undef DEFTREECODE
}%
下面的数组定义了每一种树节点的字符串名,定义方法同上。
%{
extern const char *const tree_code_name[];
}%
在c-lang.c中
%{
/* Names of tree components.
   Used for printing out the tree and error messages.  */
#define DEFTREECODE(SYM, NAME, TYPE, LEN) NAME,

const char *const tree_code_name[] = {
#include "tree.def"
  "@@dummy",
#include "c-common.def"
};
#undef DEFTREECODE
}%
下面三行代码定义了一个tree构成的vector。vec.h定义了一个vector模板,支持操作
vector。这里就是用了这些接口。
%{
/* A vectors of trees.  */
DEF_VEC_P(tree); /* tree 是指向tree_node的指针类型,指出了vector的成员类型 */
DEF_VEC_ALLOC_P(tree,gc);
DEF_VEC_ALLOC_P(tree,heap);
}%
在接下来,tree.h中有一大段关于buildin函数的声明。Note:暂时跳过。
分析从这里继续
%{
/* The definition of tree nodes fills the next several pages.  */
}%
一个树节点可以代表一种数据类型,一个变量,一个表达式或一个语句。每一个节点都有一
个TREE_CODE表示它代表的对象。常见的包括INTEGER_TYPE表示整形,ARRAY_TYPE表示指针
类型(这个没有错吗?),VAR_DECL表示一个声明的变量,INTEGER_CST表示整型常量,
PLUS_EXPR表示一个加法表达式等。在不同的树节点之间,有很多内容是一样的,但是,每
一类树节点也有自己独有的一些内容。这些内容从不被直接访问,都是通过某些宏进行的。
每一种树节点都是以下面这个结构开始的
%{
/* In the following comments, expressions including decls*/
struct tree_base GTY(())
{
  /* 指出了该节点的节点编码 */
  ENUM_BITFIELD(tree_code) code : 16;

  unsigned side_effects_flag : 1;
  unsigned constant_flag : 1;
/* 在VAR_CECL节点中,非0表示该节点需要地址,所以,不能只把它放在寄存器中。在
 * FUNCTION_DECL中,非0表示需要地址,所以该函数必须有独立实体,尽管它可能是
 * inline函数。在FIELD_DECL中,非0表示允许程序员取该域的地址。在CONSTRUCTOR节点
 * 中,非0表示对象必须被构造在主存中。Note:在LABEL_DECL中的含义没有看明白。在
 * xxx_TYPE节点中,非0表示该类型的对象必须是完整可寻址的。在INDENTFIER_NODE中
 * 非0表示该名字的某个外部声明会取它的地址。在CALL_EXPR中,非0表示该调用是尾调用
 * 。在CASE_LABEL_EXPR中,非0表示CASE_LOW操作数已经被处理了。*/
  unsigned addressable_flag : 1;
  unsigned volatile_flag : 1;
  unsigned readonly_flag : 1;
  unsigned unsigned_flag : 1;
  unsigned asm_written_flag: 1;
  unsigned nowarning_flag : 1;

  unsigned used_flag : 1;
  unsigned nothrow_flag : 1;
/* 在VAR_DECL中,非0表示分配静态存储区。在FUNCTION_DECL中,非0表示函数已经被定义
 * 了。在CONSTRUCTOR中,非0表示分配静态存储区。在TARGET_EXPR和WITH_CLEANUP_EXPR
 * 中,非0表示相关的cleanup只在出现异常的时候执行,正常退出作用域时不执行。在
 * TRY_CATCH_EXPR中,非0表示应该将异常处理代码看作honor_protect_cleanup_actions
 * 中独立的cleanup函数。Note:
 * honor_protect_cleanup_actions是什么?在CASE_LABEL_EXPR中表示CASE_HIGH操作数
 * 已经被处理了。在CALL_EXPR中表示该函数不适于inline....


 * Note:
 * 从这两个标志看出来,每一个标志都被不同的节点用于不同的目的,对应于每一个目的
 * 都有一个宏来判断(尽管它们检查相同的标志)。有些宏里面还加入了check类的宏,来确
 * 保正确的访问。鉴于太多了,就不一一写出来了。注释写得挺好的。
 */
  unsigned static_flag : 1;
  unsigned public_flag : 1;
  unsigned private_flag : 1;
  unsigned protected_flag : 1;
  unsigned deprecated_flag : 1;
  unsigned invariant_flag : 1;
  unsigned saturating_flag : 1;

  unsigned lang_flag_0 : 1;
  unsigned lang_flag_1 : 1;
  unsigned lang_flag_2 : 1;
  unsigned lang_flag_3 : 1;
  unsigned lang_flag_4 : 1;
  unsigned lang_flag_5 : 1;
  unsigned lang_flag_6 : 1;
  unsigned visited : 1;

  unsigned spare : 23;

  /* FIXME tuples: Eventually, we need to move this somewhere external to
     the trees.  */
  union tree_ann_d *ann;
};
}%
一下的两个树定义是基于上面定义的特殊化的两类树节点。
%{
struct tree_common GTY(())
{
  struct tree_base base;
  tree chain;
  tree type;
};

/* GIMPLE_MODIFY_STMT */
struct gimple_stmt GTY(())
{
  struct tree_base base;
  source_locus locus;
  tree block;
  /* FIXME tuples: Eventually this should be of type ``struct gimple_expr''.  */
  tree GTY ((length ("TREE_CODE_LENGTH (TREE_CODE (&%h))"))) operands[1];
};
}%
接下来,有一大段在说明tree_base中的标志对于哪些节点是有意义的。个人觉得,更后面
的访问域的宏的定义看起来更清楚。tree_base中的注释,是根据这些来的。
文件中定义了一大堆用于检查树节点属性的宏,这些宏发现对树节点的非法访问的时候,就
会报告错误,并停止编译。其中有一些注释还是值得一看的。例如“将树节点用链表穿起来
有很多用处。类型节点穿起来,用于记录它们并输出给调试器;同一个作用域中的声明穿起来,用与记录该作用域的内容;顺序的语句节点会被穿起来;一般而言,链表使用
TREE_LIST节点来表示,而这种节点也是被穿起来的。”再之后,又是大量的宏,用于操作
树节点。
下面是一些更加具体的树节点的定义。
%{
/* 该节点表示整形常量,可以表示2字的常量 */
struct tree_int_cst GTY(())
{
  struct tree_common common;
  double_int int_cst; /* double_int 分为high和low两个部分,每部分都是机器字*/
};
/* 浮点常量,struct real_value定义在real.h中,表示一个浮点数*/
struct tree_real_cst GTY(())
{
  struct tree_common common;
  struct real_value * real_cst_ptr;
};
/* 定点常量,fixed_value中包含一个double_int和一个mode,在fixed-value中定义*/
struct tree_fixed_cst GTY(())
{
  struct tree_common common;
  struct fixed_value * fixed_cst_ptr;
};
/* 字符串常量 */
struct tree_string GTY(())
{
  struct tree_common common;
  int length;
  char str[1];
};
/* 复数常量*/
struct tree_complex GTY(())
{
  struct tree_common common;
  tree real;
  tree imag;
};
/* Vector常量*/
struct tree_vector GTY(())
{
  struct tree_common common;
  tree elements;
};
}%
另外还有一些特殊的树节点也是类似定义的。另外一个比较重要的树节点是表示表达式的树
节点,定义如下。
%{
struct tree_exp GTY(())
{
  struct tree_common common;
  source_locus locus; /* 源文件中的位置 */
  tree block;         /* 所属的块 */
  tree GTY ((special ("tree_exp"),
         desc ("TREE_CODE ((tree) &%0)")))
    operands[1];      /* 操作数 */
};
}%
下面开始的一部分是用于操作SSA的宏。Note:关于SSA_NAME节点的定义没有找到,但是这
种节点的确在tree.def中进行了声明。在后面有一个结构体的声明
%{
#ifndef _TREE_FLOW_H
struct ptr_info_def;
#endif
}%
这个结构定义在tree-flow.h中,用于记录一些SSA结点的属性,用于别名分析。遇到后再仔
细看它。
下面这个结构用于维护一个双向链表,记录了一个SSA_NAME的使用者。
%{
typedef struct ssa_use_operand_d GTY(())
{
  struct ssa_use_operand_d* GTY((skip(""))) prev;
  struct ssa_use_operand_d* GTY((skip(""))) next;
  /* Note:这两个成员具体包含什么信息?*/
  tree GTY((skip(""))) stmt;
  tree *GTY((skip(""))) use;
} ssa_use_operand_t;
}%
下面这个结构体很像是SSA_NAME的定义,但是却没有ssa_name这个域。根据上面的宏来看,
似乎应该有一个类型的树节点,包含一个ssa_name的域,这个域的类型是struct
tree_ssa_name
%{
struct tree_ssa_name GTY(())
{
  struct tree_common common;

  /* 该SSA包装(代表)的_DECL的对象(变量) */
  tree var;

  /* SSA 的版本号 */
  unsigned int version;

  /* 用于别名分析的属性 */
  struct ptr_info_def *ptr_info;

  /* 多遍使用到的一个关于SSA的值,目前,只有不变量允许保存在这里面跨越不同的遍*/
  tree value_handle;

  /* 该SSA名字的使用者构成的链表 */
  struct ssa_use_operand_d imm_uses;
};
}%
下面的一部分是phi节点的东西。phi节点是ssa中的一种特殊的节点。一个基本块的所有的
phi节点被穿成一个单链表。
%{
struct phi_arg_d GTY(())
{
  /* imm_use必须是第一个域,我们会用它做一些指针运算 */
  /* Note:这两个域是什么意思?*/
  struct ssa_use_operand_d imm_use;
  tree def;
};

struct tree_phi_node GTY(())
{
  struct tree_base common;
  tree chain;
  tree result;
  int num_args;
  int capacity;

  /* 包含这个phi节点的基本块 */
  struct basic_block_def *bb;

  /* phi节点的参数,它们的顺序和对应的基本块的前驱的顺序一致 */
  struct phi_arg_d GTY ((length ("((tree)&%h)->phi.num_args"))) a[1];
};
}%
下面是表示BLOCK的树节点的定义
%{
struct tree_block GTY(())
{
  struct tree_common common;

  /* 非0表示该块已经准备好处理列在vars中的例外 */
  unsigned handler_block_flag : 1;
  unsigned abstract_flag : 1;
  /* Block的下标号,这些号并不保证在函数之间的唯一性,是否唯一依赖于输出的调试格
   * 式*/
  unsigned block_num : 30;

  /* 对于一个内联的函数,该成员记录了它被定义的地方。这个只有在顶层块中有效,顶
   * 层块代表了被inline的函数的函数体。这个一般用于调试输出*/
  location_t locus;

  tree vars;
  tree subblocks;
  tree supercontext;
  tree abstract_origin;
  /* 在块重排的时候,一个词法上的块可能被分到若干不连续的地址范围,此时,我们会做一份原
   * 块的拷贝。这与abstract_origin是不同的,在abstract_origin中,我们有唯一一个
   * 原块,它被复制若干份(inlining, unrolling),
   * 每一份是一个逻辑块,并且,这些逻辑块有不同的物理变量。
   * 而在这里的情况中,我们只有一个逻辑块,它被分割到不连续的地址范围中。大部分
   * 调试格式都不支持表达这种情况,所以,我们创建多个逻辑块,但它们共享相同的物
   * 理变量,来骗过它们。对于支持这种请况的,这将允许它们将逻辑块重构出来。
   * 逻辑块中的一个片段被选为ORIGINAL,其他的通过fragment_origin指向它,它自己
   * 的这个域是空。所有的片段会从ORIGINAL开始,通过fragment_chain穿成链表*/
  tree fragment_origin;
  tree fragment_chain;
};
}%
下面的结构定义了类型节点。
%{
struct tree_type GTY(())
{
  struct tree_common common;
  tree values;
  tree size;
  tree size_unit;
  tree attributes;
  unsigned int uid;

  unsigned int precision : 9;
  ENUM_BITFIELD(machine_mode) mode : 7;

  unsigned string_flag : 1;
  unsigned no_force_blk_flag : 1;
  unsigned needs_constructing_flag : 1;
  unsigned transparent_union_flag : 1;
  unsigned packed_flag : 1;
  unsigned restrict_flag : 1;
  unsigned contains_placeholder_bits : 2;

  unsigned lang_flag_0 : 1;
  unsigned lang_flag_1 : 1;
  unsigned lang_flag_2 : 1;
  unsigned lang_flag_3 : 1;
  unsigned lang_flag_4 : 1;
  unsigned lang_flag_5 : 1;
  unsigned lang_flag_6 : 1;
  unsigned user_align : 1;

  unsigned int align;
  tree pointer_to;
  tree reference_to;
  union tree_type_symtab {
    int GTY ((tag ("0"))) address;
    const char * GTY ((tag ("1"))) pointer;
    struct die_struct * GTY ((tag ("2"))) die;
  } GTY ((desc ("debug_hooks == &sdb_debug_hooks ? 1 : debug_hooks == &dwarf2_debug_hooks ? 2 : 0"),
      descbits ("2"))) symtab;
  tree name;
  tree minval;
  tree maxval;
  tree next_variant;
  tree main_variant;
  tree binfo;
  tree context;
  /* 一个类型的规范形式,用于比较类型相等。如果其内容为NULL_TREE,表示该类型不能
   * 与其它类型直接比较。此时,在比较相等的时候,需要逐项比较该类型的组成成分,
   * 而不是比较规范形式*/
  tree canonical;
  alias_set_type alias_set;
  /* Points to a structure whose details depend on the language in use.  */
  struct lang_type *lang_specific;
};
}%
注意,values,minval,maxval这些域常常是被重载的,对于不同的类型用不同的宏访问。
瓷碗,前端也可能重载这些域。
看了这么多节点的定义了,这个文件还没有看到一半。大概翻了一下,后面的定义都是类似
的:定义一个结构体表示一种节点,这个结构体的第一项很可能是一个更一般的结构体,然
后定义一大堆宏来操作和判断这个结构的属性。
最后,给出最一般的一个结构,也是在其它文件中最常用的。它给出了一个树节点能表示的
所有信息,它可以代表本文件(tree.h)中声明的任何一种树节点。
%{
union tree_node GTY ((ptr_alias (union lang_tree_node),
              desc ("tree_node_structure (&%h)")))
{
  struct tree_base GTY ((tag ("TS_BASE"))) base;
  struct tree_common GTY ((tag ("TS_COMMON"))) common;
  struct tree_int_cst GTY ((tag ("TS_INT_CST"))) int_cst;
  struct tree_real_cst GTY ((tag ("TS_REAL_CST"))) real_cst;
  struct tree_fixed_cst GTY ((tag ("TS_FIXED_CST"))) fixed_cst;
  struct tree_vector GTY ((tag ("TS_VECTOR"))) vector;
  struct tree_string GTY ((tag ("TS_STRING"))) string;
  struct tree_complex GTY ((tag ("TS_COMPLEX"))) complex;
  struct tree_identifier GTY ((tag ("TS_IDENTIFIER"))) identifier;
  struct tree_decl_minimal GTY((tag ("TS_DECL_MINIMAL"))) decl_minimal;
  struct tree_decl_common GTY ((tag ("TS_DECL_COMMON"))) decl_common;
  struct tree_decl_with_rtl GTY ((tag ("TS_DECL_WRTL"))) decl_with_rtl;
  struct tree_decl_non_common  GTY ((tag ("TS_DECL_NON_COMMON"))) decl_non_common;
  struct tree_parm_decl  GTY  ((tag ("TS_PARM_DECL"))) parm_decl;
  struct tree_decl_with_vis GTY ((tag ("TS_DECL_WITH_VIS"))) decl_with_vis;
  struct tree_var_decl GTY ((tag ("TS_VAR_DECL"))) var_decl;
  struct tree_field_decl GTY ((tag ("TS_FIELD_DECL"))) field_decl;
  struct tree_label_decl GTY ((tag ("TS_LABEL_DECL"))) label_decl;
  struct tree_result_decl GTY ((tag ("TS_RESULT_DECL"))) result_decl;
  struct tree_const_decl GTY ((tag ("TS_CONST_DECL"))) const_decl;
  struct tree_type_decl GTY ((tag ("TS_TYPE_DECL"))) type_decl;
  struct tree_function_decl GTY ((tag ("TS_FUNCTION_DECL"))) function_decl;
  struct tree_type GTY ((tag ("TS_TYPE"))) type;
  struct tree_list GTY ((tag ("TS_LIST"))) list;
  struct tree_vec GTY ((tag ("TS_VEC"))) vec;
  struct tree_exp GTY ((tag ("TS_EXP"))) exp;
  struct tree_ssa_name GTY ((tag ("TS_SSA_NAME"))) ssa_name;
  struct tree_phi_node GTY ((tag ("TS_PHI_NODE"))) phi;
  struct tree_block GTY ((tag ("TS_BLOCK"))) block;
  struct tree_binfo GTY ((tag ("TS_BINFO"))) binfo;
  struct tree_statement_list GTY ((tag ("TS_STATEMENT_LIST"))) stmt_list;
  struct gimple_stmt GTY ((tag ("TS_GIMPLE_STATEMENT"))) gstmt;
  struct tree_value_handle GTY ((tag ("TS_VALUE_HANDLE"))) value_handle;
  struct tree_constructor GTY ((tag ("TS_CONSTRUCTOR"))) constructor;
  struct tree_memory_tag GTY ((tag ("TS_MEMORY_TAG"))) mtag;
  struct tree_struct_field_tag GTY ((tag ("TS_STRUCT_FIELD_TAG"))) sft;
  struct tree_omp_clause GTY ((tag ("TS_OMP_CLAUSE"))) omp_clause;
  struct tree_memory_partition_tag GTY ((tag ("TS_MEMORY_PARTITION_TAG"))) mpt;
};
}%
可以看出,这里使用了C语言中支持“多态性”的一个很常见的技巧。同时,我们也弄明白
了那个ssa_name的出处。在文件coretypes.h中,我们看到,"tree"被定义为指向tree_node
的指针类型。
在tree.h中,还使用一个枚举类型定义了C编译器用到的所有数据类型的编码,包括标准命
名的和无名的。并且,声明了一个用于保存指向这些类型对应的树节点的指针的数组。
%{
enum tree_index
{
  TI_ERROR_MARK,
  TI_INTQI_TYPE,
  TI_INTHI_TYPE,
  TI_INTSI_TYPE,
  TI_INTDI_TYPE,
  TI_INTTI_TYPE,

  TI_UINTQI_TYPE,
  TI_UINTHI_TYPE,
  TI_UINTSI_TYPE,
  TI_UINTDI_TYPE,
  TI_UINTTI_TYPE,

  TI_UINT32_TYPE,
  TI_UINT64_TYPE,

  TI_INTEGER_ZERO,
  TI_INTEGER_ONE,
  TI_INTEGER_MINUS_ONE,
  ...


  TI_SAT_UHA_TYPE,
  TI_SAT_USA_TYPE,
  TI_SAT_UDA_TYPE,
  TI_SAT_UTA_TYPE,

  TI_MAX
};

extern GTY(()) tree global_trees[TI_MAX];
}%
下面这个枚举定义给出了C的标准的整形类型。这些类型的顺序必须是,短的在前,有符号
的在前。在c-lex.c文件中的interpret_integer()会用到。
%{
enum integer_type_kind
{
  itk_char,
  itk_signed_char,
  itk_unsigned_char,
  itk_short,
  itk_unsigned_short,
  itk_int,
  itk_unsigned_int,
  itk_long,
  itk_unsigned_long,
  itk_long_long,
  itk_unsigned_long_long,
  itk_none
};

typedef enum integer_type_kind integer_type_kind;

/* 标准c整数类型,使用上面定义的枚举类型索引该数组 */
extern GTY(()) tree integer_types[itk_none];
}%
好吧,关于树的定义就先看到这里了。其实,该文件中还有很多东西没有提到。例如,对于
OpenMP的支持等(tree.c中,就是对这个文件中声明的函数的实现,另外,还有树结构的初
始化部分代码)。这里是纯粹从代码出发来分析的,如果想要了解关于树的更加高级的概念
,参考“GENERIC and GIMPLE”一文。

阅读(7961) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~