Help us understand the problem. What is going on with this article?

最適化コンパイラへのいざない (2) マルチパスコンパイラ

記事一覧

  1. はじめに
  2. マルチパスコンパイラ (この記事)
  3. 定数に関する最適化
  4. プログラムの構造

対象読者

  • コンパイラの内部構造について興味がある方
  • コンパイラに関して精通している方(批評お待ちしております)

ワンパスコンパイラ

突然ですが,初めてコンパイラを作るのであれば,大抵次のような構造になると思います.

ワンパスコンパイラ

図中の赤い部分は,どんなにシンプルなコンパイラでも含まれているだろうという意味を込めたものです.字句解析や中間言語生成はそれぞれ構文解析やコード生成と区別化がつかなくなっている場合もあるかと思います.

ここで図中に,一つのパスと書かれているのが気になった方もいるかと思います.

パス

プログラムのとある表現(ソースコードや中間言語)は,ある操作を施されて別の表現へと移っていきます.この時,ある操作やそれを行うためのルーチン群のことをパスと呼びます.

この説明だと,ASTが中間言語へ変換されるのも一つのパスだと数えられないのか?という疑問が浮かびます.
しかし,おそらくシンプルなコンパイラならば,字句解析からコード生成までが逐次行われていて,「構文解析が完全に済んだから,ASTに対してコード生成を始めよう」,というような構造にはなっていないかと思います.そういう意味で,シンプルなコンパイラはワンパスと言われています.逆にそのような構造ではなくて,段階ごとにしっかり分離された設計になっているのならば,次に説明するマルチパスコンパイラであると言えます.

マルチパスコンパイラ

マルチパスコンパイラは以下のような構造をしています.

multi pass compiler.png

マルチという言葉の通りパスが複数ありますね.何が増えたのかというと,最適化パスが増えています.
ワンパスコンパイラのような逐次処理では困難だったコンパイル単位での処理が,マルチパスコンパイラでは可能になります.最適化が実装しやすくなるので,マルチパスコンパイラは最適化コンパイラとも呼ばれます.

実例

世の中で使われているコンパイラはマルチパスのものが多いですが,実際どのような構造なのでしょうか.
具体例を見たほうが分かりやすい方も多いと思うので紹介します.

GCC

gcc internal
GNU C Compiler Internals/GNU C Compiler Architecture

画像はgccの内部構造です.一目見るだけでマルチパスだとわかります.GIMPLERTLなど見慣れない言葉もあるかと思いますが,とりあえず今は気にしなくて大丈夫でしょう.

LLVM

llvm internal

Design and Implementation of a TriCore Backendfor the LLVM Compiler Framework (p.10)

画像はLLVMの構造です.(LLVMはコンパイラ基盤なので,中間言語以降を対象にしていると思えばよいです.)
とにかくたくさんの工程を経てアセンブリが出力されていることが分かります.この画像では中間言語(LLVM-IR)に対する最適化が描かれていないので,実際にはもっと長くなります.

一つ一つのパスは広大で,小さなコンパイラほどの規模を持ちます.私は高校3年生の時の通学時間をスマホでLLVMのソースコードリーディングをすることに割きましたが,どのパスも最後まで読むことはできませんでした.もっとコードリーディングが上手くなりたいですね.

次の記事

coming soon

いよいよ具体的な最適化手法の説明に入ります.まずは身近で簡単なものからです.

uint256_t
大学生になりました.
http://github.com/maekawatoshiki
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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした