@article{oai:ipsj.ixsq.nii.ac.jp:00016495,
 author = {勝原, 達也 and 滝本, 宗宏 and Tatsuya, KATSUHARA and Munehiro, TAKIMOTO},
 issue = {SIG12(PRO34)},
 journal = {情報処理学会論文誌プログラミング（PRO）},
 month = {Aug},
 note = {命令レベル並列性を高める有効な手法の 1 つとして、命令スケジューリングがある。特に、投機的実行を許す命令スケジューリングは、さらに並列度を高められる点で効果的であることが知られている。投機的実行は、元のプログラムに存在しなかった冗長性を導入する可能性があるので、1 つの命令をスケジュールするたびに共通部分式の削除を適用することが効果的である。本発表では、共通部分式の削除で取り除くことができない部分冗長性を扱う部分冗長除去に注目し、部分冗長除去に基づく大域命令スケジューリングを提案する。本手法は、あるプログラム点に対して、投機的命令スケジューリングを含むコードの上方移動を行うごとに、部分冗長除去のデータフロー解析を適用する。解析結果から最適化効果が認められる場合、実際にプログラムを変更することで、命令スケジューリングを実現する。部分冗長除去の性質は、プログラムの実行パスを長くしないことを保証し、大域命令スケジューリングで問題となる補償コードを最適なプログラム点に自動的に挿入する。また、本手法は、ループ構造を認識することなく、ループスケジューリング手法の 1 つである、ループシフティングを実現することができる。さらに本論文では、本手法を COINS コンパイラ・インフラストラクチャ上で実装し、最適化効果を検証する。, Instruction scheduling is one of the effective techniques to increase Instruction-level parallelism. Especially, the instruction scheduling which allows speculative execution is known as a technique which exposes more parallelism in a program. Since the speculative execution can introduce new redundant expressions as a second order effect, eliminating the redundant expressions using common sub-expression elimination (CSE) opens a way for scheduling other operations. We propose an instruction scheduling approach based on partial redundancy elimination (PRE) which eliminates more redundant expressions than CSE does. PRE can eliminate not only totally redundant expressions which CSE can eliminate but also partially redundant expressions, therefore leads to more opportunities to schedule. In addition to that, we focus on a property such that PRE eliminates redundant expressions based on code motion. This property enables determining whether scheduling to a specific idol resource is effective or not, and automatically inserting any compensation code to optimal points after scheduling. Hence, our scheduling approach guarantees that any execution paths are not lengthened. Our approach can also be applied to any program structures, and achieve a loop scheduling, i.e. loop shifting, without identifying loop structure.},
 pages = {52--65},
 title = {部分冗長除去に基づく大域命令スケジューリング},
 volume = {48},
 year = {2007}
}