ミドルエンドからバックエンドまでのフレームワーク

http://www.airs.com/dnovillo/Papers/

GCC Internals, D. Novillo, 2007 International Symposium on Code Generation and Optimization (CGO), San Jose, California, March 2007.(slides).

• GCC のミドルエンドとバックエンドはまとめて実行される。

ミドルエンドは、GIMPLE →　GIMPLE 　な最適化と　GIMPLE →　RTL の変換が混在する、最適化パスのリスト。
最適化パスは、関数ポインタ execute や実行条件 gate（-On オプションによって制御される最適化強度など）が含まれる構造体 (tree-pass.h)

/* Describe one pass.  */
struct tree_opt_pass
{
/* Terse name of the pass used as a fragment of the dump file name.  */
const char *name;

/* If non-null, this pass and all sub-passes are executed only if
  the function returns true.  */
bool (*gate) (void);

/* This is the code to run.  If null, then there should be sub-passes
  otherwise this pass does nothing.  The return value contains
  TODOs to execute in addition to those in TODO_flags_finish.   */
unsigned int (*execute) (void);

/* A list of sub-passes to run, dependent on gate predicate.  */
struct tree_opt_pass *sub;

/* Next in the list of passes to run, independent of gate predicate.  */
struct tree_opt_pass *next;

/* Static pass number, used as a fragment of the dump file name.  */
int static_pass_number;

/* The timevar id associated with this pass.  */
/* ??? Ideally would be dynamically assigned.  */
unsigned int tv_id;

/* Sets of properties input and output from this pass.  */
unsigned int properties_required;
unsigned int properties_provided;
unsigned int properties_destroyed;

/* Flags indicating common sets things to do before and after.  */
unsigned int todo_flags_start;
unsigned int todo_flags_finish;

/* Letter for RTL dumps.  */
char letter;
};

によって表現され、execute_pass_list() によって実行される (passes.c)。

void
execute_pass_list (struct tree_opt_pass *pass)
{
do
{
  if (execute_one_pass (pass) && pass->sub)
    execute_pass_list (pass->sub);
  pass = pass->next;
}
while (pass);
}

バックエンドは、RTR からのコード生成。

• バックエンドも　execute_pass_list() によって実行されるパスの一つ。

この点が　GCC でもっともわかりにくいところ。
関数ポインタを含んだ構造体が使われまくるため静的な解析が難しい。
デバッガを使わなければ、どの関数が実行されるのかを突き止めるのはほぼ不可能。

パスリストの初期化は、同ファイル内の init_optimization_passed()

/* Construct the pass tree.  The sequencing of passes is driven by
the cgraph routines:

cgraph_finalize_compilation_unit ()
    for each node N in the cgraph
 cgraph_analyze_function (N)
     cgraph_lower_function (N) -> all_lowering_passes

If we are optimizing, cgraph_optimize is then invoked:

cgraph_optimize ()
    ipa_passes ()    -> all_ipa_passes
    cgraph_expand_all_functions ()
        for each node N in the cgraph
     cgraph_expand_function (N)
 tree_rest_of_compilation (DECL (N))  -> all_passes
*/

void
init_optimization_passes (void)
{
struct tree_opt_pass **p;

#define NEXT_PASS(PASS)  (p = next_pass_1 (p, &PASS))

/* All passes needed to lower the function into shape optimizers can
 operate on.  These passes are always run first on the function, but
 backend might produce already lowered functions that are not processed
 by these passes.  */
p = &all_lowering_passes;
NEXT_PASS (pass_remove_useless_stmts);
NEXT_PASS (pass_mudflap_1);
NEXT_PASS (pass_lower_omp);
NEXT_PASS (pass_lower_cf);
NEXT_PASS (pass_refactor_eh);
NEXT_PASS (pass_lower_eh);
NEXT_PASS (pass_build_cfg);
NEXT_PASS (pass_lower_complex_O0);
NEXT_PASS (pass_lower_vector);
NEXT_PASS (pass_warn_function_return);
NEXT_PASS (pass_build_cgraph_edges);
NEXT_PASS (pass_inline_parameters);
*p = NULL;

...

NEXT_PASS (pass_final);
}
   NEXT_PASS (pass_df_finish);
 }
NEXT_PASS (pass_clean_state);
*p = NULL;

#undef NEXT_PASS

/* Register the passes with the tree dump code.  */
register_dump_files (all_lowering_passes, false, PROP_gimple_any);
all_lowering_passes->todo_flags_start |= TODO_set_props;
register_dump_files (all_ipa_passes, true,
      PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh
      | PROP_cfg);
register_dump_files (all_passes, false,
      PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh
      | PROP_cfg);
}

一番最後に、前回触れた、RTL からアセンブリを生成する　rest_of_handle_final() が含まれた構造体　pass_final が追加されていることがわかる。バックエンドも、パスの一つになっている。

pass_final は　final.c において実体が定義されている。final は必ず実行されるパスなので、gate が　NULL になる。最適化レベルによっては実行されないようなパスの場合は、gate() の中で optimize というグローバルなフラグに応じて実行するか否かを判断する。

struct tree_opt_pass pass_final =
{
NULL,                                 /* name */
NULL,                                 /* gate */
rest_of_handle_final,                 /* execute */
NULL,                                 /* sub */
NULL,                                 /* next */
0,                                    /* static_pass_number */
TV_FINAL,                             /* tv_id */
0,                                    /* properties_required */
0,                                    /* properties_provided */
0,                                    /* properties_destroyed */
0,                                    /* todo_flags_start */
TODO_ggc_collect,                     /* todo_flags_finish */
0                                     /* letter */
};

ここまでに示した、ひたすらパスを実行するフレームワークが、GCC のミドルエンド以降の肝となる。これさえ理解すれば、後はひたすら個別のパスのコードを追っていけば、いつかは　GCC をマスターできるはず。