Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

GCC treeのデータ構造

More than 3 years have passed since last update.

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部分の3つを持つ。
  • 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を持つ。
  • c 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 *);
    }

参考

eggman
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away