一般化max演算子の抽出による分岐除去

• Item type: Trans(1)
• 公開日: 2020-04-27
• タイトル: 一般化max演算子の抽出による分岐除去
• タイトル / 言語: en
• タイトル: Branch Elimination by Extracting Generalized Max Operators
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要, Unrefereed Presentatin Abstract]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: 東京大学大学院総合文化研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Arts and Sciences, The University of Tokyo
• 著者名: 佐藤, 重幸; 森畑, 明昌
• 著者名(英): Shigeyuki, Sato; Akimasa, Morihata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: より大きい方を返す2項演算子maxは，プログラム記述を簡潔にし，計算機のうえで効率良く実行でき，プログラム変換を助ける代数的性質を備えている．同じ計算であるなら，if文よりも，max演算子による式として記述される方が，コンパイラ最適化にとって都合が良い．しかし，max演算子およびその一般形は，コンパイラ最適化の段階で，露に存在するものではない．たとえば，入力言語の都合によりif文で表現されたり，複雑なif文の入れ子の中に結果的に紛れ込んだりする．そこで，コンパイラ最適化においてmax演算子から恩恵を得るために，SMTソルバを用いてif文からmax式を自動的に抽出する新しい手法を開発した．提案手法は，max演算子を使うことで，入力のif文の単純化を保証する．そのうえ，コンポーネントに基づくプログラム合成技術と組み合わせることで，argmax演算子などの一般化されたmax演算子の抽出もできる．本発表では，提案手法とそのプロトタイプ実装を紹介し，提案手法のコンパイラ最適化における有用性を議論する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The max operator, a binary operator returning a larger operand, makes code brief, is efficient on real-world machines, and has algebraic properties useful for program transformations. Max expressions are more convenient to compiler optimizations than corresponding if statements. However, the max operator and its generalizations are often latent in compiler optimization phases for several reasons. For example, source languages may not have the very constructs for them; part of complicated nesting of if statements may be equivalent to them as a result. To benefit from max operators in compiler optimizations, we develop a new method of automatically extracting max expressions from if statements by using SMT solvers. Our method guarantees to simplify a given if statement with max operators, and moreover, its combination with component-based program synthesis techniques can extract the argmax operator, a generalization of the max operator. In this presentation, we give our method and its prototype implementation and discuss how our method is useful for compiler optimizations.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 13, 号 2, p. 14-14, 発行日 2020-04-27
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会