compiler-construction - 興味深いコンパイラプロジェクト

Question

私は現在、今後 8 週間にわたって行われる大学院レベルのコンパイラコースのプロジェクトを選択している最中です。最適化に関連することはあまりしたことがないのでやりたいと思っていますが、この分野のことならなんでも結構です。

これまでに行った中で最も興味深いコンパイラ関連のプロジェクトは何ですか? あなたは何から最も多くを学びましたか?

編集：素晴らしい提案をありがとうございました。この度は、長らく更新を滞らせてしまい申し訳ございませんでした。

私が最終的に行ったプロジェクトは、LLVM での単純な自動ベクトル化の最適化でした。LLVM にはベクトル型がありますが、フロントエンドのサポートなしではそれらを利用する方法がないように思われました。この最適化により、通常のスカラーコードがベクトルコードに変換されました。

自動ベクトル化は実装がかなり難しい最適化であるため、可能な限りスコープを制限しました。まず、コード内の命令レベルの並列性を明らかにするために、基準に一致する 1 ブロックループを探し、それらを特定の回数展開して、簡単にベクトル化できるようにしました。次に、Larsen と Amarasinghe によるマルチメディア命令セットによるスーパーワードレベルの並列処理の活用で説明されているパッキングアルゴリズムを実装しました。

この最適化の単純化されたバージョンでさえ、かなり複雑です。多くの制約があります。たとえば、ループの外に存在する変数をベクトル化する必要はありません。これは、プログラムの残りの部分がスカラーであると想定しているためです。ここ数週間、私たちは多くの時間を費やしてきました。このプロジェクトはとても楽しかったですが、多くのことを学びました。

score 13 · Accepted Answer

8週間の期間では、「スコープクリープ」に注意する必要があります。それは、特に野心的すぎないでください。このプロジェクトにコンパイラ構築の他の側面（字句解析/解析）が含まれている場合、またはツール（デバッガ、yacc）と中間データ構造（DAG）をまだ学習している場合。

そうは言っても、私の最初の提案は、ライブ変数分析を試すことです。アルゴリズムはかなり確立されているので、データ構造などに固有にコード化する必要があります。

これにより、限定された形式のデッドコード除去を実行できます。つまり、変数が宣言されているが使用されていないことを検出した場合は、その変数にスペースを割り当てないでください。値が設定されていることを検出したが、読み取られなかった場合は、設定を生成しないでください。

生存変数分析はレジスタ割り当てにも役立つため、時間があればそれに取り組むことができるかもしれません。また、デッドコード除去のために構築したものの一部を再利用できるはずです。

score 8 · Accepted Answer

数年前、私はDSLを設計し、会社が製造した製品のコンパイラを作成しました。DSLは、宣言型ルール、イベント駆動型ロジック、および構成的継承の奇妙な組み合わせを使用していました。とても楽しいプロジェクトで、たくさんのことを学びました。

パーサーとコンパイラーに本当に興味をそそられたので、コンパイラー技術の興味深い新しい開発についていくように努めました。

最適化に関して、私が昨年読んだ楽しい記事は次のとおりです。

http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf

このホワイトペーパーでは、専門家が大量の特殊なコードを記述しなくても、のぞき穴最適化（いくつかの一般的なC ++コンパイラバックエンドのパフォーマンスを超える）を自動的に検出する手法について説明します。彼らの手法は、教師なし学習アルゴリズムを使用して、価値の高いのぞき穴の代替品を発見します。

それを読んだ後、ターゲットプロセッサアーキテクチャでサポートされているすべての命令（主な効果と副作用を含む）を一覧表示する「マシンの説明」をアルゴリズムに提供することで、彼らのアプローチを強化できることに気付きました。次に、同等の命令シーケンスを見つけるために強引なアプローチを使用するのではなく、ソルバーはそれらのシーケンスをはるかに簡単に見つけることができます。

機械学習アルゴリズムは、経験的観測を使用して最も効率的な命令シーケンスを決定します（キャッシュ効果、マイクロオペレーション、パイプライン化はほとんど経験的タイミングデータを必要とするため）が、結果の同等性は代数的定理証明器を使用して予測できます。マシンの説明を操作します。

この論文では、オプティマイザーが2つまたは3つの命令ののぞき穴置換シーケンスしか検出できない方法について説明しています（そうしないと、力ずくの検索に時間がかかり、メモリを大量に消費するためです）。スマートソルバーをアルゴリズムの適切な場所に配置すると、より長い置換シーケンスで機能するようになる可能性があります。

とにかく...あなたがそのプロジェクトを終えたら私に知らせてください！そして、あなたの「謝辞」セクションで私に言及することを忘れないでください！;-)

score 7 · Accepted Answer

独自の単純な組み込みスクリプト言語を作成することは、これまでに行ったコンパイラ関連のプロジェクトの中で最も興味深いものの 1 つだったと思います。設計からコンセプトまでのプロセスのあらゆる側面を教えてくれました。ゼロから作っていたので、必要に応じて単純にも複雑にもすることができたので、多くのノイズなしでコンセプトを理解できました。プロジェクトが持っている可能性があります。

score 7 · Accepted Answer

最適化に興味がある場合は、SSE および MMX 命令セットを使用したループのベクトル化が興味深いかもしれません。

score 5 · Accepted Answer

PythonをC++にコンパイルするShedSkinプロジェクトの支援を検討してください。夏の間、助けを求める声が上がったと思います。C ++へのコンパイルを改善する方法を決定すると、Pythonプログラムに驚異的な最適化が提供されます。

http://code.google.com/p/shedskin/

score 5 · Accepted Answer

コンパイラを学習するには、エンドツーエンドで学習するのが最善の方法です。x86 ではなく単純なバックエンドマシンを使用するのではなく、必要最小限の MIPS のような単純なマシンを選択します。私は、PDP-11 シミュレーターを対象とした学部生のコンパイラプロジェクトを行いました。これは、物事を非常にシンプルに保つための優れたターゲットでした。いくつかのサンプルコードのおかげで、単純な命令型言語コンパイラを約 4 週間で作成できました。Cで！

今日では、ML のような強力な言語により、コンパイラーの作成がはるかに簡単になるはずです。

何をするかは、何に関心があるかによって異なります。最適化が目的の場合は、それだけに関心を持つ必要がある単純なフレームワークを見つけてください。

今日最も実りの多い分野は、スレッド化されたターゲット向けのコンパイルまたはジャストインタイムコンパイルであると思います。

score 4 · Accepted Answer

「DragonBook」の提案に加えて、中間表現、コード生成、および最適化手法に焦点を当てたSteven S.Muchnickによる「AdvancedCompilerDesign＆Implementation」も強くお勧めします。

score 4 · Accepted Answer

私はかつて、プログラミング言語とそれを実行するための仮想マシンを作成しました。この言語は、16 ビット Windows の DLL (これは OLE オートメーションの前) に含まれている専用に作成された関数にインターフェイスできました。

最初から最後まですべてを行うことで、言語を両端から深く理解することができました。当時、私はさまざまなコンパイラの本 (悪名高いドラゴンの本など) を読んでいましたが、何か具体的なものを書くまでは、実際に没頭することはありませんでした。何年も経った今、私が行った作業により、Java VM や CLR の機能などについて、より深い評価と理解が得られました。

score 4 · Accepted Answer

学部生のコンパイラのクラスでは、最初に Pascal に似た言語用の再帰降下 (トップダウン) パーサーをゼロから作成しました: レキシカルアナライザー、パーサー、すべて。

学期の途中で、lex/yacc や flex/bison などのパーサー/スキャナージェネレーターに切り替えました。Pascal サブセットを取得し、それをコンパイルして、与えられたスタックマシン用にアセンブリするコンパイラを構築しました (スタックマシンは非常に単純ですが、原則は同じです)。

コンパイラに興味があるなら、Dragon Bookはあまりお勧めできません。これは、1 学期の学部課程で使用することを目的としており、後半は大学院レベルの課程として使用することを目的としており、必要な理論と最適化のあらゆる部分を網羅しています。ジョエルも気に入っている。=)

乾杯

score 4 · Accepted Answer

4

既存の動的型付け言語の型推論を検討してください。

于 2008-10-08T18:08:47.363 に答える

score 3 · Accepted Answer

ここに別のアイデアがあります...まだ少し漠然としています:

ほとんどの最適化はコンパイル時に行われます (実行時に最適化する JIT コンパイラを除く)。しかし、リンク時とインストール時に最適化する機会もたくさんあります。

私は特に、インストール時までリンクを気にしないプラットフォームのアイデアに興味があります。しかし、そのインストール時のリンクプロセスでは、積極的な最適化戦略を採用します。これは、マシンアーキテクチャに関する多くの詳細な情報を知っており、より微妙で十分な情報に基づいた最適化の決定を行うことができるためです。

score 2 · Accepted Answer

自分の言語を書くことは楽しくて伝統的な学術活動ですが、実装が不十分なコンパイラ関連のプロジェクトはすでにたくさんあります。また、完全な言語実装で良い仕事をするのに8週間では十分ではありません。

「最適化に関連するもの」に関心がある場合は、既存の言語またはVMを選択し、パフォーマンス、サイズ、またはその両方について最適化します。これにより、言語の実装全体を再発明する必要がなくなり、最適化問題に集中できるようになり、他の学業だけでなく他の人にも役立つ製品が作成され、就職にも役立ちます。

Parrotバイトコードインタープリターとさまざまな.NetIron言語パーサーは、単純な最適化でも恩恵を受けることができると思います。

score 2 · Accepted Answer

IronScheme のオプティマイザーを作成することもできます。これは、いくつかの「組み込み」関数を除いて、現在はすべてうまく機能するためです。 :)

score 2 · Accepted Answer

その他の興味深いプロジェクトには次のものがあります。

オープンソースの Sun JVM に末尾呼び出しの最適化を追加します。
名前付き戻り値の最適化 (NRVO) を Python または Ruby VM に追加します。
お気に入りのターゲットに対して、ジャストインタイムの正規表現からバイトコードへのコンパイルを追加します (.Net には既にありますが、Java にはないと確信しています)。

score 2 · Accepted Answer

私は自分自身の教えの中でこれを「ずっと前に」行ってきました。型推論、JIT、バイトコーディング、オブジェクトフォーマット / デバッグサポートなど、他のことほど最適化を強調するつもりはありません。

人々が考えているよりもはるかに重要性が低いことを伝えている限り、最適化に集中しても害はありません。次のコードでのみ重要です。

呼び出しスタックの一番下でタイトなループで実行されます (つまり、関数を明示的または暗黙的に呼び出すことなく)
実際には、アプリの時間のかなりの割合を占めています (つまり、コードがほとんど実行されない場合、コードを最適化してもあまり役に立ちません)。

これは、コンパイラが認識するすべてのコードのごく一部です。

編集: 残念ながら、コードを容赦なくスクランブルし、パフォーマンスにイプシロン効果を与えながらデバッグを非常に困難にする Fortran コンパイラでの作業から逃れることはできません。

score 2 · Accepted Answer

ループ検出とパラメータ化されたアンローリングは、興味深いものにするのに十分難しいはずです。あまりセクシーではありませんが、8週間でセクシーになりすぎると沈みます.

score 1 · Accepted Answer

サイズ/速度のトレードオフのためのヒューリスティックテストを使用した自動インラインコード生成。

score 0 · Accepted Answer

B :: CC perlコンパイラは、型を追加して分析することで恩恵を受けるでしょう。まだ十分な時間がありません。

最近十分な時間がありました。http://blogs.perl.org/users/rurban/2011/02/use-types.html

compiler-construction - 興味深いコンパイラ プロジェクト

18 に答える 18

Related

Reference

compiler-construction - 興味深いコンパイラプロジェクト