Database changes have finished applying - please report any issues you're (still) seeing to support@shoutwiki.com.
Main Page
From reading gcc
はじめに[edit | edit source]
関根です。 gcc 0.9 のソースコードをひらメソッドで読んでいます。
概要[edit | edit source]
- ソースコードの行数の統計 (cloc http://cloc.sourceforge.net を使用)
Language | files | blank | comment | code |
---|---|---|---|---|
C | 42 | 6428 | 8240 | 28580 |
C Header | 18 | 856 | 1620 | 1880 |
yacc | 2 | 320 | 273 | 1716 |
def | 3 | 208 | 0 | 868 |
make | 1 | 53 | 30 | 135 |
SUM | 66 | 7865 | 10163 | 33179 |
- 関数のリスト List_of_functions
- GNU global で作成
- ソースコードのファイル構成
function | files |
---|---|
back end | tm-m68000.h tm-vax.h m68000.md vax.md vaxlib.c |
front end | decl.c parse.y typecheck.c |
Main compilation | emit-rtl.c explow.c expmed.c expr.c final.c global-alloc.c local-alloc.c obstack.c optabs.c stmt.c toplev.c tree.c |
Optimisations | combine.c cse.c flow.c fold-const.c jump.c loop.c recog.c regclass.c reload.c reload1.c rtl.c stor-layout.c stupid.c |
Tool chain interfacing | varasm.c |
C preprosessing | cccp.c cexp.y |
Debugging | dbxout.c print-tree.c symout.c |
The gcc driver file | gcc.c |
Generator C sources | gencodes.c genconfig.c genemit.c genextract.c genflags.c genoutput.c genrecog.c |
- 構文解析
- RTL生成
- ジャンプ最適化
- レジスタ走査
- ジャンプの一本化
- グローバル共通部分式削除
- ループ最適化
- データフロー解析
- 命令組合せ
- レジスタ移動
- 命令スケジューリング
- レジスタクラスの選択
- 大局的なレジスタ割当
- 再ロード
- 最終パス
- generator
- gencodes MDからCODE_FOR_ のマクロを生成 insn-codes.h
- genconfig MDから#define コンフィグを生成 insn-config.h
- genemit MDからemit insns を生成
- genextract MDからextract operands を生成
- genflags MDからHAVE_ のフラグを生成
- genoutput RTLからアセンブラを生成するinsnsを生成 insn-output.c
- genrecog insnからrecognized RTLを生成するemit insns を生成??? insn-recog.c
全体の流れ[edit | edit source]
- 組み込み型の宣言からTREEを生成
- ソースコードファイルを読んでTREEを生成
- 「TREEをRTLに変換してして、最適化を行い、RTLをINSNに変換してアセンブラ出力する。」 この処理は関数の終了毎に行われる。
- RTL変換は、グローバルと関数->文 -> 式-> 演算の順に、大きな構造から小さな構造へと再帰的に変換していく。
- 関数ごとのRTLが得られるので、このRTLを最適化する。
- INSNはアセンブラに1対1に対応している。単純なパターン変換でアセンブラ出力する。
データ構造[edit | edit source]
- binding_level スコープのデータ構造
- machine_mode machine mode
- obstack objectのスタック
- tree 構文木のデータ構造
- rtl RTL (Register Transfer Language)
Parse[edit | edit source]
- parse_decl_var 変数宣言のpersing
演算と式と文[edit | edit source]
演算
- 単項演算 : build_unary_op()
- 2項演算 : build_binary_op()
- 3項演算 : build_conditional_expr()
式
- 式: expand_expr()
- 代入 : MODIFY_EXPR build_modify_expr() -> expand_assignment() store_expr()
- 関数コール : build_function_call() -> expand_call() -> gen_call_1()
文
- if文 : build_if() -> do_jump() emit_jump()
- while文 : build_loop() build_compound() -> do_jump() emit_jump()
- do while文 : build_loop() build_compound() -> do_jump() emit_jump()
- for文 : build_loop() build_compound() -> do_jump() emit_jump()
- switch case文 : build_switch_stmt() finish_switch_stmt() -> expand_case_stmt() do_jump_if_equal() emit_jump()
- goto文 : build_goto() -> emit_jump() -> make_jump_insn_raw()
- break文 : build_goto() 上と同じ
- continue文 : build_goto() 上と同じ
- label文 : build_label() build_compound() -> label_rtx()
- return文 : build_return_stmt() -> RETURN insn
その他
- exit関数 : build_exit()
- インラインアセンブラ: build_asm_stmt() -> ASM_INPUT
Optimize[edit | edit source]
TREE
- constant folding : fold()
RTL RTLに変換後の最適化の順番
- JUMP jump_optimize() ジャンプ命令を減らす。
- CSE reg_scan() cse_main() 共通部分を除去
- LOOP loop_optimize()
- Flow analysis flow_analysis()
- Combining combine_instructions()
- Register allocation regclass() global_alloc() レジスタを割り当て
- 2回目のJUMP jump_optimize()
コード生成[edit | edit source]
- GCCの命令セットは、VAXの命令セットに似ている。
- 似ている箇所:バイト/ワード/ロングを区別する 命令の最後の数字がオペランドの数
- Standard Insn Names
GCCの標準命令 Mはマシンモードの2文字 最後の数字はオペランドの数 uはunsigned
movM movstrictM addM3 subM3 mulM3 umulM3 divM3 udivM3 modM3 umodM3 andM3 iorM3 xorM3 andcbM3 mulhisi3 mulqihi3 mulsidi3 umulqihi3 umulhisi3 umulsidi3 divmodM4 udivmodM4 divmodMN4 ashlM3 ashrM3 lshlM3 lshrM3 rotlM3 rotrM3 negM2 absM2 sqrtM2 one_cmplM2 cmpM tstM movstrM cmpstrM floatMN2 fixMN2 truncMN extendMN zero_extendMN extv extzv insv sCONDM bCOND call return tablejump caseM
プリプロセッサ[edit | edit source]
基本的な流れ
main 引数の解析、ファイル全体を読み、入力バッファに格納 rescan メインループ handle_directive #マクロ のパース do_なんとか 各マクロのハンドラ プリプロセッサ用のyaccファイルは #if の パラメータをCで評価して値を得るためだけに使っている
みどころ[edit | edit source]
- Init decl processing() intなどの型宣言のtreeを生成
- rest_of_compilation() tree生成後のRTL変換、最適化、アセンブリ出力までを司る関数
- expand_stmt() 文をtreeからRTLに変換
- expand_expr() 式をtreeからRTLに変換
- do_jump() 条件つきジャンプのINSNをemitする
- final() アセンブラ出力
用語[edit | edit source]
ファイル名に含まれる略語、関数名に含まれる略語の説明
BINOP: Binary Operation バイナリ演算 CONS: LISPでリストを作る関数名 CSE: Common Subexpression Elimination 最適化の手法の一つで、共通な部分を除去する。 CST: Constant DECL: declare 宣言 DBX: BSDに含まれるデバッガ EMIT: 発行する EXP: Expression 式 EXPAND: TREEからRTLを生成 EXPR: Expression 式 INC: Increment INSN: Instruction 命令 gccの仮想マシンの命令 LIM: LHS: left-hand side 式の左側(yaccの用語) MAC: Macro MD: Machine Description マシン記述 MED: OBSTACK: Stack of object REG: Register RHS: right-hand side 式の右側 (yaccの用語) RID: Reserved ID 予約語 RTL: Register Transfer Language RTX: RTL eXpresssion RTL式 STMT: Statement 文 (if文、for文、...) STOR: Store TREE: 構文木の内部表現 VEC: Vector
その他[edit | edit source]
- ソースコードを読んで気になったこと
- 関数名とカッコの間にスペースがある
- 構造体のメンバにアクセスする際には必ずマクロを使う。
メモ[edit | edit source]
わかったことなど
- build_* treeのノードを作る関数
- expand_* treeをRTLに展開する関数
- gen_* 命令のノードを作る関数
- treeで変数は、変数宣言のDECLノード 1回宣言したら、変数が出現するたびにその宣言ノードを参照する。
- マシンモードは代入先の変数の型が、演算に伝搬して決定する。 targetがその目標の型
- 演算を展開するときに、マシンモードとレジスタが割り当てる。 演算結果はレジスタに入る。
- HAVE_命令のdefineはgenflagsで生成する。insn-flags.hでdefineする。
- 各命令に応じたgen_* 関数がある。
- gen_* 関数はテーブル経由で呼ぶ。 例外は、gen_call() gen_return() gen_casesi()
- 命令を作る関数のテーブルは2階層ある。下の階層はinsn-output.cのinsn_gen_function[]は全ての命令を生成する関数が1次元の配列で並んでいる。 このテーブルをGEN_FCN(CODE)マクロで参照する。
- 上の階層は命令の種類ごとのテーブル movstrict_optab mov_optab binoptab unoptab tst_optab add_optab sub_optab などにマシンモードを配列の添字にして参照する。演算をexpandするときにこのテーブルを渡す。このテーブルはinit_optabs()で初期化する。
- 実際に使うinsnの総数は、insn-codes.hのinsn_code[]でわかる。VAXの場合は150種類。このテーブルでCODE_FOR_tstdfの数字を定義、CODE_FOR_tstdfは上のテーブルを初期化するときに使う。
- 下の階層のテーブルはmdが無いと記述できない。上の階層のテーブルはifdefを駆使することで、mdなしでも記述が可能。
- vaxlib.c は足りない命令をC言語で記述している。
- force_mem コマンドライン引数で設定、nonzeroだとexpand_binop()でオペランドのload memory addressを強制的にレジスタにする。
- 「emit」が完全に理解できない。 emitするとgen_*()で生成したRTLがinsnsに追加されていくという理解。その後最適化でRTLが変更されることは無いのか? -> expand_function()した後はinsnsしか使わない。expand_function()の終了のタイミングでTREE由来のRTLとINSNSのRTLに分かれている? または emit前のRTLとemit後のRTLという分け方もできる。emit前のRTLはtreeの木構造を維持している、emit後のRTLはコード生成する順序に並んでいる。
- gccが3番地コードを使っているのは最適化のため。3番地コードは順番を入れ替えがやり易い。2番地コードだとテンポラリレジスタの付け替えが必要。
- gccのパス TREE生成、RTL生成、INSN生成、アセンブラ出力の最低4パスでしょうか?
License[edit | edit source]
このwikiのライセンスはGFDL 1.3 です。
License of this wiki is GFDL 1.3.