Common subexpression eliminationとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Common subexpression eliminationの意味・解説 

共通部分式除去

(Common subexpression elimination から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/10/23 06:42 UTC 版)

Jump to navigation Jump to search

共通部分式除去(きょうつうぶぶんしきじょきょ、: Common subexpression elimination, CSE)は、計算機科学におけるコンパイラ最適化方法の一つで、同じ (すべて同じ値に評価される) の出現を探し出し、計算結果を格納する一つの変数に置き換える価値があるかどうかの解析を行うものである。

下記の例では、

a = b * c + g;
d = b * c * d;

コードが下記のように記述されたとして解釈できるよう変更すると、 (プログラムの実行が速くなるため)利点がある。

tmp = b * c;
a = tmp + g;
d = tmp * d;

最適化プログラムはコストと利点の解析を行い、tmpを格納するコストが複数回計算を行うコストより低いかどうかを計算する。実際には、どの値がどのレジスタに格納されるかといった要素も重要である。

上記のような単純な場合には、プログラマはコードを記述する際に重複した式を手動で除去してしまうことが多い。CSE の入力としてもっとも重要なものはコンパイラが出力する中間コードである。例えば配列のインデックス計算などで生成されるもので、開発者が介在して手動で除去することができない。また、言語の特徴によって重複した式が多数作られる場合もある。たとえばC言語マクロでは、マクロの展開により元のコードに現れない共通部分式が生成される。

CSE を実行する利点は大きく、広く用いられる最適化手法である。

CSE ではコンパイラが値を一時的に格納する変数の数に関して十分賢いものである必要がある。膨大な一時変数を作成するとレジスタが枯渇し、メモリを使用する必要を生じる。単純な演算結果を必要に応じて再計算するより時間がかかってしまう場合もある。

コンパイラ開発者は二種類の CSE を区別している:

  • 局所共通部分式除去 は一つのブロック内で動作するため実装が簡単な最適化方法である。
  • 大域共通部分式除去 は手続きの全体で動作し、式が手続きのどこで利用可能になるかを解析するデータフロー解析の結果に依存する。

関連項目

参考文献

  • Steven S. Muchnick, Advanced Compiler Design and Implementation (Morgan Kaufmann, 1997) pp. 378-396
  • John Cocke. "Global Common Subexpression Elimination." Proceedings of a Symposium on Compiler Construction, ACM SIGPLAN Notices 5(7), July 1970, pages 850-856.
  • Briggs, Preston, Cooper, Keith D., and Simpson, L. Taylor. "Value Numbering." Software-Practice and Experience, 27(6), June 1997, pages 701-724.

「Common subexpression elimination」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Common subexpression elimination」の関連用語

Common subexpression eliminationのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Common subexpression eliminationのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの共通部分式除去 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS