言語処理系特論

Special Lecture of Language Processing System 30

996D102

63CSARO501

滝本　宗宏

Munehiro Takimoto

2026年度前期

2026年度

①First semester

水曜2限

The second class on Wednesday

創域理工学研究科　情報計算科学専攻

Department of Information Sciences, Graduate School of Science and Technology

2.00単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

プログラムを中間表現に変換する方法とその中間表現の性質を理解し，中間表現の静的解析および，解析結果を用いたプログラム変形法を学ぶ．プログラム変形の応用として，並列化法にも触れる．

The objective of this course is to understand intermediate representations in terms of transformation to it and its properties, and to learn static analyses and program transformations based on their results. Applications of the program transformations also include some parallelizing methods.

プログラムを中間表現に変換する方法とその中間表現の性質を理解し，中間表現の静的解析および，解析結果を用いたプログラム変形法を学ぶ．プログラム変形の応用として，並列化法にも触れる．
本専攻のディプロマポリシーにある「情報科学専攻の専門分野に応じた高度な専門知識、および、研究能力」を身に付けるための科目である．

Through the course, you can master intermediate representations (IR) in terms of transformation to it and its properties, and static analyses on IR and program transformations based on their results, along the diploma policy of this department.

1. 制御フローグラフの性質と構成法を理解する．
2. データフロー方程式が与えられると，そのデータフロー解析を実現し，自動的に解を得ることができる．
3. 解析解を用いて，いくつかのプログラム変形を実現できる．

1. Understand properties and construction of a control flow graph,
2. Once a dataflow equation is given, can implement a solver of the dataflow equation and obtain results from it automatically.
3. Can transform programs based on results of the solver.

-

-

-

各回の講義内容を十分復習し，講義中に示すポイントを説明できるようにしておくこと．

You have to check the contents described in this class, and become able to explain the points shown in this class.

レポートによって評価する．

evaluated by reports.

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://gomykits.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://gomykits.kinokuniya.co.jp/tokyorika/

最新コンパイラ構成技法，Andrew W. Appel 著，神林靖，滝本宗宏　訳，翔泳社

Andrew W. Appel, Modern Compiler Implementation in ML

1 制御フロー解析（１）　　　　プログラムを基本ブロックに分割する方法を理解する．
　　
2 　　制御フロー解析（２）　　　　基本ブロックに分割されたプログラムから効率のよいコード
　　　　　　　　　　　　　　　　　を生成する方法を理解する．

3 　　データフロー解析（１） 　　データフロー解析の理論と実現法について理解する。

4 　　データフロー解析（２） 　　データフロー解析の高速な解法について理解する．
　　 　　する。

5 　　データフロー解析に基づく最適化（１）
　　　　　　　　　　　　　　　　　データフロー解析の解を基に行う基本的なコード最適化を
　　　　　　　　　　　　　　　　　習得する．

6 　　データフロー解析に基づく最適化（２）
　　　　　　　　　　　　　　　　　データフロー解析の解を基に行う高度なコード最適化を学ぶ．

7 　　レジスタ割付け 　　レジスタ彩色アルゴリズムとその実現法について理解する。



8 　　ループ最適化（１） 　　ループ発見法について解説し、その際に必要な支配関係の概
　　 　　念と解析法について理解する．

9 　 ループ最適化（２） 　　ループ最適化を幾つか紹介し、その実現法について理解する．

10　　支配木　　　　　　　　　　　支配関係を表現する支配木を作成するアルゴリズムを理解する．

11　　静的単一代入形式（１） 　　静的単一代入形式について定義を与え、その変換法について
　　 　　理解する．

12　　静的単一代入形式（２） 　　静的単一代入形式に基づく高度なコード最適について理解する．

13　　命令スケジューリング（１）　大域命令スケジューリングの基本を習得する． 　　
14　　命令スケジューリング（２）　ループスケジューリングについて、ソフトウェアパイプライ
　　　 　　ニングを中心に理解する．

15　　メモリ階層 　　キャッシュの仕組みと、その有効な利用法について理解する．

1. Control flow graph (1)
Understand how to split a sequence of instructions to basic blocks.
2. Control flow graph (2)
Understand how to generate efficient target code through suitably combining basic blocks.
3. Dataflow analysis (1)
Understand theory and implementation of dataflow analyses.
4. Dataflow analysis (2)
Learn intra-procedural optimizations based on the results of dataflow analyses.
5. Code optimizations based on dataflow analyses (1)
Master basic code optimizations based on results of dataflow analyses.
6. Code optimizations based on dataflow analyses (2)
Learn sophisticated code optimizations based on results of dataflow analyses.
7. Register allocation
Understand how to implement a register coloring algorithm.
8. Loop optimizations (1)
Understand a manner for detecting a loop, and a concept and implementation of dominators needed for it.
9. Loop optimizations (2)
Understand some loop optimizations and its implementation.
10. Dominator tree
Understand how to construct a dominator tree representing dominance relation.
11. SSA form (1)
Understand the definition of SSA form and transformation to SSA form.
12. SSA form (2)
Understand sophisticated optimizations based on SSA form.
13. Instruction level scheduling (1)
Lean a basis of global instruction scheduling.
14. Instruction level scheduling (2)
Understand loop scheduling including software pipelining.
15. Memory hierarchy
Understand behaviors of a cache memory and its effective utilization.

-

-

-

-