2008年11月26日水曜日

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

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)
  1. /* Describe one pass.  */  
  2. struct tree_opt_pass  
  3. {  
  4. /* Terse name of the pass used as a fragment of the dump file name.  */  
  5. const char *name;  
  6.   
  7. /* If non-null, this pass and all sub-passes are executed only if 
  8.   the function returns true.  */  
  9. bool (*gate) (void);  
  10.   
  11. /* This is the code to run.  If null, then there should be sub-passes 
  12.   otherwise this pass does nothing.  The return value contains 
  13.   TODOs to execute in addition to those in TODO_flags_finish.   */  
  14. unsigned int (*execute) (void);  
  15.   
  16. /* A list of sub-passes to run, dependent on gate predicate.  */  
  17. struct tree_opt_pass *sub;  
  18.   
  19. /* Next in the list of passes to run, independent of gate predicate.  */  
  20. struct tree_opt_pass *next;  
  21.   
  22. /* Static pass number, used as a fragment of the dump file name.  */  
  23. int static_pass_number;  
  24.   
  25. /* The timevar id associated with this pass.  */  
  26. /* ??? Ideally would be dynamically assigned.  */  
  27. unsigned int tv_id;  
  28.   
  29. /* Sets of properties input and output from this pass.  */  
  30. unsigned int properties_required;  
  31. unsigned int properties_provided;  
  32. unsigned int properties_destroyed;  
  33.   
  34. /* Flags indicating common sets things to do before and after.  */  
  35. unsigned int todo_flags_start;  
  36. unsigned int todo_flags_finish;  
  37.   
  38. /* Letter for RTL dumps.  */  
  39. char letter;  
  40. };  

によって表現され、execute_pass_list() によって実行される (passes.c)。
  1. void  
  2. execute_pass_list (struct tree_opt_pass *pass)  
  3. {  
  4. do  
  5. {  
  6.   if (execute_one_pass (pass) && pass->sub)  
  7.     execute_pass_list (pass->sub);  
  8.   pass = pass->next;  
  9. }  
  10. while (pass);  
  11. }  

バックエンドは、RTR からのコード生成。
  • バックエンドも　execute_pass_list() によって実行されるパスの一つ。
この点が　GCC でもっともわかりにくいところ。
関数ポインタを含んだ構造体が使われまくるため静的な解析が難しい。
デバッガを使わなければ、どの関数が実行されるのかを突き止めるのはほぼ不可能。

パスリストの初期化は、同ファイル内の init_optimization_passed()
  1. /* Construct the pass tree.  The sequencing of passes is driven by 
  2. the cgraph routines: 
  3.  
  4. cgraph_finalize_compilation_unit () 
  5.     for each node N in the cgraph 
  6.  cgraph_analyze_function (N) 
  7.      cgraph_lower_function (N) -> all_lowering_passes 
  8.  
  9. If we are optimizing, cgraph_optimize is then invoked: 
  10.  
  11. cgraph_optimize () 
  12.     ipa_passes ()    -> all_ipa_passes 
  13.     cgraph_expand_all_functions () 
  14.         for each node N in the cgraph 
  15.      cgraph_expand_function (N) 
  16.  tree_rest_of_compilation (DECL (N))  -> all_passes 
  17. */  
  18.   
  19. void  
  20. init_optimization_passes (void)  
  21. {  
  22. struct tree_opt_pass **p;  
  23.   
  24. #define NEXT_PASS(PASS)  (p = next_pass_1 (p, &PASS))  
  25.   
  26. /* All passes needed to lower the function into shape optimizers can 
  27.  operate on.  These passes are always run first on the function, but 
  28.  backend might produce already lowered functions that are not processed 
  29.  by these passes.  */  
  30. p = &all_lowering_passes;  
  31. NEXT_PASS (pass_remove_useless_stmts);  
  32. NEXT_PASS (pass_mudflap_1);  
  33. NEXT_PASS (pass_lower_omp);  
  34. NEXT_PASS (pass_lower_cf);  
  35. NEXT_PASS (pass_refactor_eh);  
  36. NEXT_PASS (pass_lower_eh);  
  37. NEXT_PASS (pass_build_cfg);  
  38. NEXT_PASS (pass_lower_complex_O0);  
  39. NEXT_PASS (pass_lower_vector);  
  40. NEXT_PASS (pass_warn_function_return);  
  41. NEXT_PASS (pass_build_cgraph_edges);  
  42. NEXT_PASS (pass_inline_parameters);  
  43. *p = NULL;  
  44.   
  45. ...  
  46.   
  47. NEXT_PASS (pass_final);  
  48. }  
  49.    NEXT_PASS (pass_df_finish);  
  50.  }  
  51. NEXT_PASS (pass_clean_state);  
  52. *p = NULL;  
  53.   
  54. #undef NEXT_PASS  
  55.   
  56. /* Register the passes with the tree dump code.  */  
  57. register_dump_files (all_lowering_passes, false, PROP_gimple_any);  
  58. all_lowering_passes->todo_flags_start |= TODO_set_props;  
  59. register_dump_files (all_ipa_passes, true,  
  60.       PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh  
  61.       | PROP_cfg);  
  62. register_dump_files (all_passes, false,  
  63.       PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh  
  64.       | PROP_cfg);  
  65. }  

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

pass_final は　final.c において実体が定義されている。final は必ず実行されるパスなので、gate が　NULL になる。最適化レベルによっては実行されないようなパスの場合は、gate() の中で optimize というグローバルなフラグに応じて実行するか否かを判断する。
  1. struct tree_opt_pass pass_final =  
  2. {  
  3. NULL,                                 /* name */  
  4. NULL,                                 /* gate */  
  5. rest_of_handle_final,                 /* execute */  
  6. NULL,                                 /* sub */  
  7. NULL,                                 /* next */  
  8. 0,                                    /* static_pass_number */  
  9. TV_FINAL,                             /* tv_id */  
  10. 0,                                    /* properties_required */  
  11. 0,                                    /* properties_provided */  
  12. 0,                                    /* properties_destroyed */  
  13. 0,                                    /* todo_flags_start */  
  14. TODO_ggc_collect,                     /* todo_flags_finish */  
  15. 0                                     /* letter */  
  16. };  

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

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)