ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
インストール
ブラウザよりも高速アクセス!
 

コンパイラ最適化

索引 コンパイラ最適化

ンパイラ最適化(こんぱいらさいてきか、Compiler optimization)の記事では、コンピュータ・プログラムの最適化に関する話題のうち、もっぱらコンパイラに関係するものに関して説明する。最も一般的な要求はプログラムの実行時間を最小化することであり、その次に使用するメモリ量を最小化することである。また、携帯可能なコンピュータが増えるにつれて、消費電力を最小化するという最適化も生まれてきた。 一部のコード最適化問題はNP完全問題であることが示されている。実際には、プログラマがコンパイラによる最適化の完了を待てる時間の上限なども考慮してコンパイラ最適化を実装する(最適化はCPU時間とメモリを多大に使用する)。かつては、コンピュータのメモリ実装量も実行できる最適化を制限する要因だった。 コンパイラメーカによっては、「コンパイラの最適化の能力が売り上げや評判に大きく影響する」と信じている場合があり、そういう信念に従って「最適化コンパイラ」と銘打つことがある。少なくとも、同程度にバグが無いコンパイラ同士であれば、という前提の範囲内なら、最適化の能力が高いほうが魅力的と言えるであろう。.

88 関係: 基本ブロック停止性問題参照の局所性大域値番号付け定数畳み込み並列計算中間表現中間言語マルチプロセッシングマイクロソフトポインタ (プログラミング)ラムダ計算ライブラリループ展開レッドハットレジスタ (コンピュータ)レジスタ割り付けローカル変数プログラミング言語プログラマプログラム (コンピュータ)プロシージャデバッガデバッグデータフローデータフロー解析データ構造デッドコード削除ベクトル計算機制御フローグラフ制御構造命令パイプライン命令スケジューリング命令セットアドレッシングモードアセンブリ言語インライン展開インテルインクリメントエイリアス解析キャッシュメモリコンパイラコンビネータ論理コールスタックシリコングラフィックススレッド (コンピュータ)スーパースカラーサン・マイクロシステムズ再実体化再帰...共通部分式除去副作用 (プログラム)C++C言語CISCCPU短絡評価線型計画問題疎な条件分岐を考慮した定数伝播遅延評価静的単一代入記憶装置論理積関数型言語For文FPUGNUコンパイラコレクションHaskellJavaLISPMC68000ML (プログラミング言語)MMXNAG数値計算ライブラリNP完全問題RISCStreaming SIMD ExtensionsVLIWX86抽象構文木排他的論理和機械語演算子強度低減演算装置末尾再帰最適化 (情報工学)数値解析3番地コード インデックスを展開 (38 もっと) »

基本ブロック

基本ブロック(きほんブロック、Basic block)は、コンピュータにおいて、一つの入り口(すなわち、内部のコードが他のコードの分岐先になっていない)と一つの出口を持ち、内部に分岐を含まないコードを指す。基本ブロックの開始点には、他のコードからジャンプすることができる。基本ブロックの終了点は、他のコードへのジャンプ命令(あるいは、ジャンプの一つ前の命令)である。 基本ブロックは通例コンパイラ最適化を行う最小単位であり、制御フローグラフにおけるノードや頂点である。 基本ブロックにおけるコードとは、ソースコードでもアセンブリ言語でも、またその他の命令列であっても良い。.

新しい!!: コンパイラ最適化と基本ブロック · 続きを見る »

停止性問題

計算可能性理論において停止(性)問題(ていしせいもんだい・ていしもんだい、halting problem)は、あるチューリング機械(≒コンピュータプログラム・アルゴリズム)が、そのテープのある初期状態(≒入力)に対し、有限時間で停止するか、という問題。アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。すなわち、そのようなチューリング機械の存在を仮定すると「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」ような別のチューリング機械が構成でき、矛盾となる。.

新しい!!: コンパイラ最適化と停止性問題 · 続きを見る »

参照の局所性

参照の局所性(さんしょうのきょくしょせい、locality of reference)とは、1つのリソースに複数回アクセスする処理に関する情報工学上の概念である。.

新しい!!: コンパイラ最適化と参照の局所性 · 続きを見る »

大域値番号付け

大域的値番号付け(英: Global value numbering, GVN) とは、静的単一代入中間表現に基づくコンパイラ最適化手法の一つである。 GVN は共通部分式除去 (CSE) によっても取り除くことができない冗長なコードを取り除くことができる。一方、CSE は GVN で除去できないコードを取り除くことができ、両者はいずれも現代的なコンパイラに採用されている。大域的値番号付けは、値と番号の関連付けをブロックの境界を越えて行うことができ、また関連付けのアルゴリズムを計算する方法が異なるという点で局所的値番号付けとは区別される。 大域的値番号付けは、値番号を変数や式に割り当てることで動作する。等価な変数や式には同じ値番号を割り当てる。例えば下記のコードでは、 優秀な GVN のルーチンはw 、 x と y 、z にそれぞれ 同じ値番号を割り当てる。たとえば、 の割り当てはこのブロックに関して最適な値と番号の対応関係である。この情報を用いることで、上のコードは下記のコードに安全に変換できる。 これ以降のコードしだいで、コピーの伝播によって x および z に対する割り当てを除去できる可能性がある。 GVN が CSE より強力なのは、CSE は字句的に同一な式をマッチさせるのに対して GVN はその背後の等価性を特定しようとする点である。例えば、 というコードで、CSE は f に割り当てられた再計算のコードを除去しないが、GVN はごく初歩的なアルゴリズムでもこれを発見し、冗長性を除去することができる。 GVN を実行するためには、変数名と値名の間に偽の対応関係が作られないよう、静的単一代入形式が必要である。.

新しい!!: コンパイラ最適化と大域値番号付け · 続きを見る »

定数畳み込み

定数畳み込み(ていすうたたみこみ、constant folding)および定数伝播(ていすうでんぱ、constant propagation)は、多くのコンパイラで使われている最適化技法である。定数伝播の進化したものを疎な条件分岐を考慮した定数伝播と呼び、定数伝播と同時にデッドコード削除も行って、より正確な伝播を行う。.

新しい!!: コンパイラ最適化と定数畳み込み · 続きを見る »

並列計算

並列計算(へいれつけいさん、parallel computing)は、コンピュータにおいて複数のプロセッサで1つのタスクを動作させること。並列コンピューティングや並列処理とも呼ばれる。問題を解く過程はより小さなタスクに分割できることが多い、という事実を利用して処理効率の向上を図る手法である。また、このために設計されたコンピュータを並列コンピュータという。ディープ・ブルーなどが有名。 関連する概念に並行計算(へいこうけいさん)があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクをスレッドなどをもちいて複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。 特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータやサーバ、スーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。.

新しい!!: コンパイラ最適化と並列計算 · 続きを見る »

中間表現

中間表現(ちゅうかんひょうげん、Intermediate Representation、IR)は、コンピュータがデータをクロスプラットフォームで扱うために使用するデータ構造の表現である。 中間表現を用いたデータの抽象化はコンピューティング分野では一般的な手法である。異なるプラットフォームで同等の情報を保持するデータを異なるフォーマットで扱う場合に、データを中間表現で表現することで複数フォーマットへの変換処理を効率化することを手助けする。これは自然言語の翻訳に中間言語を用いるのと同等のメリットがある。.

新しい!!: コンパイラ最適化と中間表現 · 続きを見る »

中間言語

中間言語(Pivot language)は、任意の言語を異なる任意の言語へ翻訳する際に利用する中間的な人工言語もしくは自然言語である。.

新しい!!: コンパイラ最適化と中間言語 · 続きを見る »

マルチプロセッシング

マルチプロセッシング(multi processing)とは、(本来は)ひとつのプロセスだけではなく複数の並行プロセスを同一システム内で使用することを意味する。 マルチタスクと同様ひとつのCPUを複数のプロセスが共有することも示すが、ひとつのシステム内の複数のCPUが複数のスレッドを動作させることも意味する。マルチプロセッサと言う場合は一般に後者のみを指す。.

新しい!!: コンパイラ最適化とマルチプロセッシング · 続きを見る »

マイクロソフト

マイクロソフト()は、アメリカ合衆国ワシントン州に本社を置く、ソフトウェアを開発・販売する会社である。1975年4月4日にビル・ゲイツとポール・アレンらによって設立された。.

新しい!!: コンパイラ最適化とマイクロソフト · 続きを見る »

ポインタ (プログラミング)

ポインタ (pointer) とは、あるオブジェクトがなんらかの論理的位置情報でアクセスできるとき、それを参照する(指し示す)ものである。有名な例としては Pascal のポインタが挙げられる。 なお、C++では、さらに独立した「参照」という機能がある。.

新しい!!: コンパイラ最適化とポインタ (プログラミング) · 続きを見る »

ラムダ計算

ラムダ計算(ラムダけいさん、lambda calculus)は、計算模型のひとつで、計算の実行を関数への引数の評価(evaluation)と適用(application)としてモデル化・抽象化した計算体系である。ラムダ算法とも言う。関数を表現する式に文字ラムダ (λ) を使うという慣習からその名がある。アロンゾ・チャーチとスティーヴン・コール・クリーネによって1930年代に考案された。1936年にチャーチはラムダ計算を用いて一階述語論理の決定可能性問題を(否定的に)解いた。ラムダ計算は「計算可能な関数」とはなにかを定義するために用いられることもある。計算の意味論や型理論など、計算機科学のいろいろなところで使われており、特にLISP、ML、Haskellといった関数型プログラミング言語の理論的基盤として、その誕生に大きな役割を果たした。 ラムダ計算は1つの変換規則(変数置換)と1つの関数定義規則のみを持つ、最小の(ユニバーサルな)プログラミング言語であるということもできる。ここでいう「ユニバーサルな」とは、全ての計算可能な関数が表現でき正しく評価されるという意味である。これは、ラムダ計算がチューリングマシンと等価な数理モデルであることを意味している。チューリングマシンがハードウェア的なモデル化であるのに対し、ラムダ計算はよりソフトウェア的なアプローチをとっている。 この記事ではチャーチが提唱した元来のいわゆる「型無しラムダ計算」について述べている。その後これを元にして「型付きラムダ計算」という体系も提唱されている。.

新しい!!: コンパイラ最適化とラムダ計算 · 続きを見る »

ライブラリ

ライブラリ()は、汎用性の高い複数のプログラムを再利用可能な形でひとまとまりにしたものである。ライブラリと呼ぶ時は、それ単体ではプログラムとして作動させることはできない実行ファイルではない場合がある。ライブラリは他のプログラムに何らかの機能を提供するコードの集まりと言うことができる。ソースコードの場合と、オブジェクトコード、あるいは専用の形式を用いる場合とがある。たとえば、UNIXのライブラリはオブジェクトコードをarと呼ばれるアーカイバでひとまとめにして利用する。図書館()と同様にプログラム(算譜)の書庫であるので、索引方法が重要である。 また、ソフトウェア以外の再利用可能なものの集合について使われることもある。.

新しい!!: コンパイラ最適化とライブラリ · 続きを見る »

ループ展開

ループ展開(ループてんかい、)は、プログラムのサイズを犠牲に実行速度を最適化する(時間と空間のトレードオフ)、と呼ばれる手法の1つである。ループアンローリング()とも呼ぶ。プログラマが手動で行うこともあるし、コンパイラが行うこともある。 ループ展開の目的は、毎回の繰り返しごとに発生する「ループの終了」条件のテストを減少させる(もしくはなくす)事によって、実行速度を向上させることである。ループは、ループ自体を制御するためのオーバーヘッドがなくなるように、独立した命令ブロックの連続に書き換えることができる。.

新しい!!: コンパイラ最適化とループ展開 · 続きを見る »

レッドハット

レッドハット (Red Hat) とは、主にLinuxディストリビューションのRed Hat Enterprise Linuxを製品として販売・開発・サポートしている会社である。.

新しい!!: コンパイラ最適化とレッドハット · 続きを見る »

レジスタ (コンピュータ)

レジスタ(register)はコンピュータのプロセッサなどが内蔵する記憶回路で、制御装置や演算装置や実行ユニットに直結した、操作に要する速度が最速の、比較的少量のものを指す。.

新しい!!: コンパイラ最適化とレジスタ (コンピュータ) · 続きを見る »

レジスタ割り付け

レジスタ割り付け(レジスタわりつけ、Register allocation)は、プログラム内の多数の変数を少数のCPUレジスタに多重化するコンパイラ最適化技法のひとつである。その目標は、プログラムの実行速度を最大化すべく、なるべく多くのオペランドをレジスタに保持するようにすることである。レジスタ割り付けは基本的なブロックについて行う場合(ローカルレジスタ割り付け)と関数やプロシージャ全体について行う場合(グローバルレジスタ割り付け)がある。レジスタ割り当てとも呼ぶ。 プログラムは、多数の様々なデータを処理することが多い。しかし、CPUの多くはデータを保持するのに使えるレジスタ数は限られている。機械語のオペランドとしてメモリを指定できる場合でも、なるべくレジスタを使った方が高速化される。従って、処理に必要なデータを RAMとレジスタの間で入れ替えてやる必要がある。この操作を spill(スピル、あふれ)と呼ぶ。 レジスタの spill は、マシンが持っているレジスタ数以上の変数が同時に必要とされる場合に発生する。一般にメモリはレジスタよりも遅いため、spill にはコストがかかる。.

新しい!!: コンパイラ最適化とレジスタ割り付け · 続きを見る »

ローカル変数

ーカル変数(局所変数、local variable)とは、プログラムの一部分でしか利用できない変数のことである。一般的にグローバル変数と対比される。ローカル変数の定義はプログラミング言語によって異なるので、詳細な説明は言語別の項に譲る。.

新しい!!: コンパイラ最適化とローカル変数 · 続きを見る »

プログラミング言語

プログラミング言語(プログラミングげんご、programming language)とは、コンピュータプログラムを記述するための形式言語である。なお、コンピュータ以外にもプログラマブルなものがあることを考慮するならば、この記事で扱っている内容については、「コンピュータプログラミング言語」(computer programming language)に限定されている。.

新しい!!: コンパイラ最適化とプログラミング言語 · 続きを見る »

プログラマ

プログラマ(Programmer)とは、コンピューターのプログラムを作成する人全般を指す。プログラマーとも表記される(#プログラマに対する呼称参照)。.

新しい!!: コンパイラ最適化とプログラマ · 続きを見る »

プログラム (コンピュータ)

ンピュータプログラム(英:computer programs)とは、コンピュータに対する命令(処理)を記述したものである。コンピュータが機能を実現するためには、CPUで実行するプログラムの命令が必要である。 コンピュータが、高度な処理を人間の手によらず遂行できているように見える場合でも、コンピュータは設計者の意図であるプログラムに従い、忠実に処理を行っている。実際には、外部からの割り込み、ノイズなどにより、設計者の意図しない動作をすることがある。また設計者が、外部からの割り込みの種類を網羅的に確認していない場合もある。.

新しい!!: コンパイラ最適化とプログラム (コンピュータ) · 続きを見る »

プロシージャ

プロシージャ (procedure)とは、プログラミングにおいて複数の処理を一つにまとめたものをいう。手続きとするのが定訳である。一連の処理を意味を持った一まとまりにすることで、再利用性が高まり、プログラム中に繰り返して現れる処理を1ヶ所で記述でき、プログラムの保守、管理を容易にする。 繰り返し利用されることから、ルーチンとも言う。呼び出し関係は通常階層構造をなし、その最上位にある、プログラム全体のエントリーポイントを含むルーチンをメインルーチン、呼び出されるものをサブルーチンと言う。また、関数と呼ばれることもある(通常、数学における関数とは違ったものであるので、注意が必要である)。 プログラミング言語により、プロシージャのような構文の分類や呼称はさまざまである。詳細はサブルーチンの記事を参照のこと。 Category:プログラミング言語の構文 he:שגרה ur:دستورالعمل.

新しい!!: コンパイラ最適化とプロシージャ · 続きを見る »

デバッガ

デバッガ(Debugger)とは、デバッグを支援するプログラムのこと。対話的に利用者がプログラムを動作させたり、プログラムが使っている変数等を表示させる機能がある。近年では統合開発環境に含まれていることが多い。また、ICEなどでは、ハードウェアと連携して動作する。 インタプリタには内蔵されていることもある。たとえばperlは起動時に -d オプションを指定することで、デバッガモードになる。.

新しい!!: コンパイラ最適化とデバッガ · 続きを見る »

デバッグ

デバッグ(debug)とは、コンピュータプログラムや電気機器中のバグ・欠陥を発見および修正し、動作を仕様通りのものとするための作業である。サブシステムが密結合であると、1箇所の変更が別の箇所でのバグを作り出すので、バグの修正がより困難となる。.

新しい!!: コンパイラ最適化とデバッグ · 続きを見る »

データフロー

データフロー(dataflow)は、情報工学において使われる用語であり、様々な意味を持つ。特にメッセージパッシングと関連が深い。.

新しい!!: コンパイラ最適化とデータフロー · 続きを見る »

データフロー解析

データフロー解析(Data-flow analysis)は、プログラム内の様々な位置で、取りうる値の集合に関する情報を収集する技法である。制御フローグラフ (CFG) を使って変数の値が伝播するかどうかなどの情報を集め、利用する。このようにして集められた情報はコンパイラが最適化に利用する。データフロー解析の基本は到達定義 (reaching definition) である。 あるプログラムのデータフロー解析を行う単純な方法は、制御フローグラフの各ノードについてデータフロー方程式を設定し、全体として安定した状態、すなわち不動点に到達するまで、それらの式を繰り返し計算していく。完了することを保証するためには、不動点データフロー解析に基づくデータフロー方程式が必要である。すなわち、各式のローカルな更新は単調である。この技法の基本はゲイリー・キルドールが海軍大学院大学で教えていたころに開発したものである。.

新しい!!: コンパイラ最適化とデータフロー解析 · 続きを見る »

データ構造

データ構造(データこうぞう、data structure)は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム(アルゴリズム)の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.

新しい!!: コンパイラ最適化とデータ構造 · 続きを見る »

デッドコード削除

デッドコード削除(デッドコードさくじょ。英: dead code elimination(デッドコード取り除き))は、コンピュータ・プログラムの最適化などの目的で行われるプログラムの変形のひとつで、到達不能コードや冗長なコードなどといった「デッドコード」を削除する操作である。効果としては、最適化として見た場合、コードサイズの削減(いわゆるフットプリントの縮小)や、それに伴うキャッシュの利用効率の向上などによる高速化も期待できるかもしれない。.

新しい!!: コンパイラ最適化とデッドコード削除 · 続きを見る »

ベクトル計算機

ベクトル計算機 (ベクトルけいさんき) は、ベクトル演算(SIMDを参照)を行えるコンピュータのこと。特に(狭義では)ベクトル演算のための高性能でパイプライン化された実行ユニットを持ち、その演算能力を可能な限り発揮できるように全てが設計されたアーキテクチャを持つスーパーコンピュータを指す。広義にはSIMDによる、ベクトルを対象とした並列演算も指す。以下、主に狭義の、すなわちパイプラインによるベクトル計算機について述べる。 ベクトル計算機のプロセッサを ベクトルプロセッサ (Vector Processor) または アレイプロセッサ (Array Processor) と呼ぶ。ベクトルプロセッサは数値演算を複数のデータに対してパイプラインにより次々と実行できる。ベクトルプロセッサは科学技術計算分野でよく使われ、特に1980年代から1990年代にかけてのスーパーコンピュータでは一般的であった。、ベクトルプロセッサを名乗るプロセッサは少ないが(特にスーパコンピュータでは、パイプライン形のベクトルプロセッサはSXシリーズを残すのみである)、SIMDと呼ばれる並列ベクトル演算を行う機能を備えたマイクロプロセッサは多い。グラフィックスやマルチメディアのため、とメーカーはうたっており、実際そのように使われていることは多いが、研究発表などとしては科学技術計算への利用やコンパイラ最適化による利用なども見られる。200x年代後半頃から、GPUによる汎目的計算 (GPGPU) が行われるようになってきている。.

新しい!!: コンパイラ最適化とベクトル計算機 · 続きを見る »

制御フローグラフ

制御フローグラフ(せいぎょフローグラフ、Control Flow Graph, CFG)は、プログラムを実行したときに通る可能性のある全経路をグラフで表したものである。この場合、ノードは基本ブロック(すなわち、分岐を全く含まない逐次的コード列であって、途中に分岐先もない)を表し、ノードとノードをつなぐ有向エッジは、あるブロックから別ブロックへのジャンプを意味する。一般に、グラフ全体の入口となる入口ブロックと、出口となる出口ブロックがある。 CFGはコンパイラ最適化や静的コード解析ツールでよく使われる。 最適化において利用されるグラフの属性として、到達可能性(reachability)がある。あるブロックまたは部分グラフが、入口ブロックを含む部分グラフと連結していない場合、そのブロックは決して実行されることはなく、いわゆる到達不能コードであって、容易に削除可能である。出口ブロックが入口ブロックから到達不能な場合、無限ループとなっている(あらゆる無限ループを検出できるわけではない。停止性問題を参照のこと)。プログラマが明示的に到達できないコードや無限ループを書かなくても、そのような状況になることはある。例えば、定数伝播や定数畳み込みといった最適化を行った後に分岐スレッディングを行うと、元々は別々だった基本ブロックが1つにまとめられることがあり、エッジがCFGから除去され、グラフの一部が連結されなくなることがある。.

新しい!!: コンパイラ最適化と制御フローグラフ · 続きを見る »

制御構造

制御構造(せいぎょこうぞう)は、コンピュータ・プログラミング言語、特に手続き型プログラミングや命令型プログラミングにおいて、ループや飛び越しなどといった、手続き(プロシージャ)中の実行順を順次実行から変化させたり、サブルーチン呼出しやその戻り、などといった制御を行う「文 (プログラミング) 」などの構造(言語の構成要素)である。 制御構造の種類は言語によって様々だが、典型的には以下のようなものがある(用語「ブロック」については、ブロック (プログラミング) の記事を参照)。.

新しい!!: コンパイラ最適化と制御構造 · 続きを見る »

命令パイプライン

命令パイプライン(Instruction pipeline)は、コンピュータなどのデジタル電子機器で命令スループット(単位時間当たりに実行できる命令数)を向上させる設計技法の1つで、命令レベルの並列性を高める1技法。 命令パイプラインのあるプロセッサは、命令の処理を独立して実行できる工程(ステージ)に分割する。各工程は、前の工程の出力を自身の入力とし、自身の出力を次の工程の入力とするように相互接続されている。このような構成で各工程を並列化し、全体としての処理時間を大幅に削減する。.

新しい!!: コンパイラ最適化と命令パイプライン · 続きを見る »

命令スケジューリング

命令スケジューリング(めいれいスケジューリング、英: Instruction scheduling)は、コンパイラ最適化において考慮されるもののひとつで、具体的な内容はターゲットのマイクロアーキテクチャに依るが、より効率的にコードが実行されるよう、演算結果に影響を与えない範囲で命令の順序を入れ替え、より良い順序にするものである。例えば命令パイプラインの深いプロセッサなどで、そのプロセッサの命令レベルの並列性を可能な限り引き出すことが目標となる。 具体例としては、例えば、コードの意味を変えずに以下のようなことを実現する。.

新しい!!: コンパイラ最適化と命令スケジューリング · 続きを見る »

命令セット

命令セット(めいれいせっと、instruction set)は、コンピュータのハードウェアに対して命令を伝えるための言葉の語彙。.

新しい!!: コンパイラ最適化と命令セット · 続きを見る »

アドレッシングモード

アドレッシングモード(Addressing Mode)は、CPUの命令セットアーキテクチャ(ISA)の一部を構成する。プロセッサの命令には操作対象をオペランドで指定するものがあり、その指定方法の詳細がアドレッシングモードと呼ばれるものである。したがって、広義のアドレッシングモードにはレジスタを指定する場合も、値が命令のオペランドとして直接与えられている場合も含まれるが、狭義のアドレッシングモードはオペランドとして使用すべきメモリ領域を指定するものとみなされる。 プログラミングの観点から言えば、アドレッシングモードが重視されるのはコンパイラ開発やアセンブリ言語でプログラミングする場合である。.

新しい!!: コンパイラ最適化とアドレッシングモード · 続きを見る »

アセンブリ言語

モトローラ MC6800 のアセンブリ言語のソースコード アセンブリ言語(アセンブリげんご、英: assembly language)とは、コンピュータ、マイクロコントローラ、その他のプログラム可能な機器を動作させるための機械語を人間にわかりやすい形で記述する、代表的な低水準言語である。なお、英語の assembly とは「組立」という意味である。.

新しい!!: コンパイラ最適化とアセンブリ言語 · 続きを見る »

インライン展開

インライン展開(inline expansion または inlining)とは、コンパイラによる最適化手法の1つで、関数を呼び出す側に呼び出される関数のコードを展開し、関数への制御転送をしないようにする手法。これにより関数呼び出しに伴うオーバーヘッドを削減する。特に小さくて頻繁に呼ばれる関数では効果的であり、呼び出し側にそのコードを展開することで定数畳み込みなどのさらなる最適化を施せる可能性が生じる。問題点はバイナリコードが一般に肥大化する結果を招く点であり、参照の局所性を損なうほどだったり、リソースの限界を超えると性能がかえって悪化することになる。 関数型言語の世界では、インライン展開をβ変換とも呼び、関数型言語の理論的基盤となっているラムダ計算の用語としてよく使われる。.

新しい!!: コンパイラ最適化とインライン展開 · 続きを見る »

インテル

インテル(英:Intel Corporation)は、アメリカ合衆国カリフォルニア州に本社を置く半導体素子メーカーである。 社名の由来はIntegrated Electronics(集積されたエレクトロニクス)の意味である。.

新しい!!: コンパイラ最適化とインテル · 続きを見る »

インクリメント

インクリメント、増量 (increment) は、一般には増加という意味だが、コンピュータ用語としては、変数の値を1増やす演算のことである。逆に、1減らす演算はデクリメント (decrement) である。.

新しい!!: コンパイラ最適化とインクリメント · 続きを見る »

エイリアス解析

イリアス解析(英: Alias analysis)は、コンパイラ理論における手法の一つで、ある記憶域が複数の箇所からアクセスされるかどうかを判定する方法である。二つのポインタが同じ記憶域を参照している場合、「エイリアスしている」とみなされる。 エイリアス解析は通例制御フローとコンテキストを意識した手法である。 エイリアスする可能性があるものと、確実にエイリアスしているものを特定することができる。 エイリアス解析という用語はポインタ解析と同義で用いられることもある。.

新しい!!: コンパイラ最適化とエイリアス解析 · 続きを見る »

キャッシュメモリ

ャッシュメモリ は、CPUなど処理装置がデータや命令などの情報を取得/更新する際に主記憶装置やバスなどの遅延/低帯域を隠蔽し、処理装置と記憶装置の性能差を埋めるために用いる高速小容量メモリのことである。略してキャッシュとも呼ぶ。コンピュータは以前から記憶装置や伝送路の性能が処理装置の性能に追いつけず、この差が全体性能に対するボトルネックとされてきた(ノイマンズ・ボトルネック)。そしてムーアの法則に基づく処理装置の加速度的な高性能化により現在ではますますこの差が拡大されている。キャッシュメモリは、記憶階層の観点からこれを解消しようとするものである。 主に、主記憶装置とCPUなど処理装置との間に構成される。この場合、処理装置がアクセスしたいデータやそのアドレス、状態、設定など属性情報をコピーし保持することで、本来アクセスすべき記憶装置に代わってデータを入出力する。通常はキャッシュメモリが自動的にデータ保存や主記憶装置の代替を行うため、基本的にCPUのプログラムなど処理装置側がキャッシュメモリを意識する必要はない。 キャッシュの一般的な概念はキャッシュ (コンピュータシステム)を参照のこと。.

新しい!!: コンパイラ最適化とキャッシュメモリ · 続きを見る »

コンパイラ

ンパイラ(英:compiler)とは、コンピュータ・プログラミング言語の処理系(言語処理系)の一種で、高水準言語によるソースコードから、機械語に(あるいは、元のプログラムよりも低い水準のコードに)変換するプログラムである。.

新しい!!: コンパイラ最適化とコンパイラ · 続きを見る »

コンビネータ論理

ンビネータ論理(Combinatory Logic、組み合わせ論理)は、(Моисей Эльевич Шейнфинкель、Moses Ilyich Schönfinkel)とハスケル・カリー(Haskell Brooks Curry)によって、記号論理での変数を消去するために導入された記法である。最近では、計算機科学において計算の理論的モデルで利用されてきている。また、関数型プログラミング言語の理論(意味論など)や実装にも応用がある。 コンビネータ論理は、コンビネータまたは引数のみからなる関数適用によって結果が定義されている高階関数、コンビネータに基づいている。.

新しい!!: コンパイラ最適化とコンビネータ論理 · 続きを見る »

コールスタック

ールスタック (Call Stack)は、プログラムに実行中にサブルーチンに関する情報を格納するスタックである。実行中のサブルーチンとは、呼び出されたが処理を完了していないサブルーチンを意味する。実行スタック (Execution Stack)、制御スタック (Control Stack)、関数スタック (Function Stack)などとも呼ばれる。また、単に「スタック」と言ったときにコールスタックを指していることが多い。コールスタックを正しく保つことは多くのソフトウェアが正常動作するのに重要であるが、その詳細は高水準言語からは透過的である。.

新しい!!: コンパイラ最適化とコールスタック · 続きを見る »

シリコングラフィックス

リコングラフィックス(Silicon Graphics International Corp.、略称:SGI、NASDAQ:)は、業務用コンピュータの開発・製造・販売を行うアメリカの企業である。本拠地はカリフォルニア州マウンテンビューに置かれていたが、2009年にサンノゼが本社所在地となった。 元々は、1982年にSilicon Graphics, Inc.として設立された。 コンピュータグラフィックスに特化した最先端の製品を開発し続け、コンピュータグラフィックス全般に絶大な影響を与えた企業である。同社のCGワークステーションは、1990年代までは世界最高の性能を堅持していた。特に、大規模な商業映画におけるCG制作でデファクトスタンダードとして扱われていたことは有名である。現在も世界中のIT端末で使われているOpenGLは、同社のCGワークステーション向けに開発されたIRISGLがオープン化されたAPIである。 2000年代に入り画像処理分野にも安価で十分な性能を持つx86アーキテクチャが普及すると、高価で大して性能面の優位性もない上に互換性もない自社専用アーキテクチャの開発を停止した。x86アーキテクチャへの転換により画像処理分野における優位性が失われたため、科学技術計算用の大型計算機を中心としたビジネスに移行した。 2009年4月1日、連邦倒産法第11章の適用を申請して倒産。同日、Rackable Systems社による事業買収の合意が発表された。5月8日にRackable Systems社による買収が完了、5月18日にRackable Systems社は社名を「Silicon Graphics International Corp.(SGI)」へと変更した(NASDAQのティッカーシンボルもRACKからSGIに変更)。 2016年11月1日、ヒューレット・パッカード・エンタープライズ (HPE) による買収が完了し、公開会社としてのSGIは廃止された。買収金額は2億7500万ドルであった。 日本法人に日本SGIがある。2001年に日本SGIがNECの出資を受けてSGIより独立したが、2011年に再度、SGIの100%子会社となった。2016年にはHPEの傘下となった。.

新しい!!: コンパイラ最適化とシリコングラフィックス · 続きを見る »

スレッド (コンピュータ)

レッド(thread)とは、CPU利用の単位。プロセスに比べて、プログラムを実行するときのコンテキスト情報が最小で済むので切り替えが速くなる。スレッドは、thread of execution(実行の脈絡)という言葉を省略したものである。 プログラミングの観点からみると、アプリケーションの処理の「実行の脈絡」は1つでないことが多い。これをシングルスレッドで実現しようとするとシグナルやタイマーを駆使してコーディングすることになる。また、複数のプロセスに分割してプロセス間通信で協調動作させるという方法もある。しかし、いずれの場合もそれらの機能を使うための余分な、本来のアルゴリズムと関係ないコーディングが必要となる。スレッドを使用したプログラミングは本来のアルゴリズムに集中しやすくなり、プログラムの構造が改善されるという効果がある。.

新しい!!: コンパイラ最適化とスレッド (コンピュータ) · 続きを見る »

スーパースカラー

パイプライン概念図 Alpha プロセッサを搭載 スーパースカラー(superscalar,スーパースケーラ)とは、プロセッサのマイクロアーキテクチャにおける用語で、複数の命令を同時にフェッチし、複数の同種のあるいは異種の実行ユニットを並列に動作させ、プログラムの持つ命令レベルの並列性を利用して性能の向上を図るアーキテクチャである。.

新しい!!: コンパイラ最適化とスーパースカラー · 続きを見る »

サン・マイクロシステムズ

ン・マイクロシステムズ本社 サン・マイクロシステムズ(Sun Microsystems)は、アメリカ合衆国カリフォルニア州サンタクララに本社を置いていたコンピュータの製造・ソフトウェア開発・ITサービス企業である。2010年1月27日にオラクルにより吸収合併され、独立企業・法人としては消滅した。.

新しい!!: コンパイラ最適化とサン・マイクロシステムズ · 続きを見る »

再実体化

再実体化(英: Rematerializationあるいは remat)とは、コンパイラ最適化手法の一つで、メモリからロードせずに再計算を行うことで実行時間を節約するものである。典型的にレジスタ割り付けと統合した形で用いられ、レジスタに格納しきれずメモリにデータを書き込んでしまうことを避けるために使用される。再実体化は Preston Briggs、Keith D. Cooper、Linda Torczon によって 1992 年に提唱された。 共通部分式除去のような古典的な最適化では無駄な計算を避けることに焦点が置かれる。計算には CPU サイクルが必要であるため、通常これは望ましいことである。しかし、変数の生存時間を増大させ、また新しい変数を多数作成するため、レジスタ割り当ての際にメモリにデータを追い出す必要を生じるという大きな副作用を潜在的に抱えている。再実体化はほぼその逆であり、CPU の計算量を増加させて割り当てるレジスタを減少させる。必要以上の計算量増加を防ぐため、コンパイラが十分有益と確信できる場合、すなわちレジスタがあふれてメモリを使用するような場合のみ行われる。 再実体化は、available expression の考え方を用いて各変数を計算する式を監視することによって動作する。ある値を計算するために用いられる変数は変更されることもあり、その場合にはもはや値の再実体化に使用することができない。このとき、その式は利用可能でないと呼ばれる。もう一つの条件として、例えば値の再実体化を行う式の複雑さの最大値がある。ロードする以上に時間のかかる非常に複雑な計算を行って再実体化を行うのは望ましくない。通常は式に副作用があってはならない。.

新しい!!: コンパイラ最適化と再実体化 · 続きを見る »

再帰

再帰(さいき)は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。定義において、再帰があらわれているものを再帰的定義という。 主に英語のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳(回帰#物理学及び再帰性を参照のこと)や、reflexiveの訳として「再帰」が使われることがある。数学的帰納法との原理的な共通性から、recursionの訳として数学では「帰納」を使うことがある。.

新しい!!: コンパイラ最適化と再帰 · 続きを見る »

共通部分式除去

共通部分式除去(きょうつうぶぶんしきじょきょ、Common subexpression elimination, CSE)は、計算機科学におけるコンパイラ最適化方法の一つで、同じ式 (すべて同じ値に評価される) の出現を探し出し、計算結果を格納する一つの変数に置き換える価値があるかどうかの解析を行うものである。 下記の例では、 コードが下記のように記述されたとして解釈できるよう変更すると、 (プログラムの実行が速くなるため)利点がある。 最適化プログラムはコストと利点の解析を行い、tmpを格納するコストが複数回計算を行うコストより低いかどうかを計算する。実際には、どの値がどのレジスタに格納されるかといった要素も重要である。 上記のような単純な場合には、プログラマはコードを記述する際に重複した式を手動で除去してしまうことが多い。CSE の入力としてもっとも重要なものはコンパイラが出力する中間コードである。例えば配列のインデックス計算などで生成されるもので、開発者が介在して手動で除去することができない。また、言語の特徴によって重複した式が多数作られる場合もある。たとえばC言語のマクロでは、マクロの展開により元のコードに現れない共通部分式が生成される。 CSE を実行する利点は大きく、広く用いられる最適化手法である。 CSE ではコンパイラが値を一時的に格納する変数の数に関して十分賢いものである必要がある。膨大な一時変数を作成するとレジスタが枯渇し、メモリを使用する必要を生じる。単純な演算結果を必要に応じて再計算するより時間がかかってしまう場合もある。 コンパイラ開発者は二種類の CSE を区別している.

新しい!!: コンパイラ最適化と共通部分式除去 · 続きを見る »

副作用 (プログラム)

プログラミングにおける副作用(ふくさよう)とは、ある機能がコンピュータの(論理的な)状態を変化させ、それ以降で得られる結果に影響を与えることをいう。代表的な例は変数への値の代入である。 例えば与えられた数字を二倍して返す機能"double"があるとする。 このような機能では次のことが成立する。.

新しい!!: コンパイラ最適化と副作用 (プログラム) · 続きを見る »

C++

C++(シープラスプラス)は、汎用プログラミング言語の一つである。日本語では略してシープラプラ、シープラなどとも呼ばれる。.

新しい!!: コンパイラ最適化とC++ · 続きを見る »

C言語

C言語(シーげんご)は、1972年にAT&Tベル研究所のデニス・リッチーが主体となって開発したプログラミング言語である。英語圏では単に C と呼んでおり、日本でも文書や文脈によっては同様に C と呼ぶことがある。.

新しい!!: コンパイラ最適化とC言語 · 続きを見る »

CISC

CISC(しすく、Complex Instruction Set Computer)は、コンピュータの命令セットアーキテクチャ(ISA)の設計の方向性の一つである。単純な命令を指向したRISCが考案されたときに、対比して(レトロニム)従来のISAは複雑であるとして、"Complex" の語を用いた "CISC" と呼ばれる様になった。典型的なCISCのISAはしばしば、単一の命令で複数の処理を行う、可変長命令である、直交性がある、演算命令のオペランドにメモリを指定できる、などで特徴づけられる。 CISCを採用したプロセッサ(CPU)をCISCプロセッサと呼ぶ。CISCプロセッサに分類されるプロセッサとしては、マイクロプログラム方式を採用したSystem/360、PDP-11、VAXなどや、マイクロプロセッサの680x0、x86などがある。.

新しい!!: コンパイラ最適化とCISC · 続きを見る »

CPU

Intel Core 2 Duo E6600) CPU(シーピーユー、Central Processing Unit)、中央処理装置(ちゅうおうしょりそうち)は、コンピュータにおける中心的な処理装置(プロセッサ)。 「CPU」と「プロセッサ」と「マイクロプロセッサ」という語は、ほぼ同義語として使われる場合も多いが、厳密には以下に述べるように若干の範囲の違いがある。大規模集積回路(LSI)の発達により1個ないしごく少数のチップに全機能が集積されたマイクロプロセッサが誕生する以前は、多数の(小規模)集積回路(さらにそれ以前はディスクリート)から成る巨大な電子回路がプロセッサであり、CPUであった。大型汎用機を指す「メインフレーム」という語は、もともとは多数の架(フレーム)から成る大型汎用機システムにおいてCPUの収まる主要部(メイン)、という所から来ている。また、パーソナルコンピュータ全体をシステムとして見た時、例えば電源部が制御用に内蔵するワンチップマイコン(マイクロコントローラ)は、システム全体として見た場合には「CPU」ではない。.

新しい!!: コンパイラ最適化とCPU · 続きを見る »

短絡評価

短絡評価(たんらくひょうか、short-circuit evaluation)または最小評価(さいしょうひょうか、minimal evaluation)とは、多くのコンピュータプログラミング言語の論理演算子における左辺(第一引数)と右辺(第二引数)の式の評価法の評価法を(意味、意味論を)表す語である。.

新しい!!: コンパイラ最適化と短絡評価 · 続きを見る »

線型計画問題

線型計画問題 (せんけいけいかくもんだい、英語:linear programming problem) とは、最適化問題において、目的関数が線型関数で、なおかつ線型関数の等式と不等式で制約条件が記述できる問題である。この問題を解く手法を線型計画法という。.

新しい!!: コンパイラ最適化と線型計画問題 · 続きを見る »

疎な条件分岐を考慮した定数伝播

な条件分岐を考慮した定数伝播(英: Sparse conditional constant propagation)とは、計算機科学におけるコンパイラ最適化手法の一つで、静的単一代入(SSA)形式に変換した後に適用されることが多い。 この手法は、プログラム全体に対してある種のデッドコードの除去と、定数畳み込みを同時に実施する。重複の回数によらず、単純なデッドコード削除と定数畳み込みより強力な方法である。 アルゴリズムはSSA形式のコードに抽象解釈を実施することにより働く。抽象解釈を実施する間、典型的には、値に対応する定数の値と定数のフラットな束と、束に対する大域的な SSA 変数と値の割り当てを用いる。アルゴリズムの最重要な点は分岐命令をどのように扱うかにある。分岐命令に遭遇すると、抽象化された値を、可能な限り正確に条件の変数に割り当てるようにする。 値が完全に正確で、抽象解釈で分岐のどちらに進むかが決定できる場合もある。値が定数ではない場合、あるいは条件文における変数が未定義の場合、保守的にいずれの分岐方向も残される。 抽象解釈が完了すると、到達しない命令はデッドコードとされる。定数であることが判明した SSA 変数は使用される箇所でインライン展開(伝播)される。.

新しい!!: コンパイラ最適化と疎な条件分岐を考慮した定数伝播 · 続きを見る »

遅延評価

遅延評価(ちえんひょうか、lazy evaluation)や必要呼び(ひつようよび、call-by-need)は評価戦略の一種類であり、非正格な関数型言語で使用もされる。対義語は先行評価(eager evaluation)。.

新しい!!: コンパイラ最適化と遅延評価 · 続きを見る »

静的単一代入

静的単一代入(せいてきたんいつだいにゅう、Static Single Assignment form, SSA)形式は、コンパイラ設計における 中間表現 (IR) のひとつで、各変数が一度のみ代入されるよう定義されたものである。もともとの中間表現における変数は「バージョン」に分割され、全ての変数の定義がバージョンを表現できるよう、通例新たな変数は元の名前に添え字を付けて表現される。SSA ではuse-def 連鎖が明示的であり、連鎖は要素を一つだけ持つ。 SSA はRon Cytron、Jeanne Ferrante、Barry Rosen、Mark Wegman、Ken Zadeck および IBM の研究者たちにより1980年代に開発された。 Scheme、ML、Haskell などの関数型言語のコンパイラでは、Fortran や C などのコンパイラで SSA の利用が期待される箇所で継続渡しスタイル (CPS) を用いるのが一般的である。SSA と CPS は形式的に等価であり、最適化やコードの変換などがいずれかに施された場合、もう片方にも同様に適用することができる。.

新しい!!: コンパイラ最適化と静的単一代入 · 続きを見る »

記憶装置

GB SDRAM。一次記憶装置の例 GB ハードディスクドライブ(HDD)。コンピュータに接続すると二次記憶装置として機能する SDLT テープカートリッジ。オフライン・ストレージの例。自動テープライブラリで使う場合は、三次記憶装置に分類される 記憶装置(きおくそうち)は、コンピュータが処理すべきデジタルデータをある期間保持するのに使う、部品、装置、電子媒体の総称。「記憶」という語の一般的な意味にも対応する英語としてはメモリ(memory)である。記憶装置は「情報の記憶」を行う。他に「記憶装置」に相当する英語としてはストレージ デバイス(Storage Device)というものもある。.

新しい!!: コンパイラ最適化と記憶装置 · 続きを見る »

論理積

数理論理学において論理積(ろんりせき、logical conjunction)とは、与えられた複数の命題のいずれもが例外なく真であることを示す論理演算である。合接(ごうせつ)、連言(れんげん、れんごん)とも呼び、ANDとよく表す。 二つの命題 P, Q に対する論理積を P ∧ Q と書き、「P かつ Q」や「P そして Q」などと読む。 ベン図による論理積P \wedge Q の表.

新しい!!: コンパイラ最適化と論理積 · 続きを見る »

関数型言語

関数型言語(かんすうがたげんご、functional language)は、以下に述べる関数型プログラミングを基本スタイルとして推奨する機能を持つプログラミング言語、関数型プログラミング言語の略称である。.

新しい!!: コンパイラ最適化と関数型言語 · 続きを見る »

For文

for文(フォーぶん)はプログラミング言語において条件が真の間だけ与えられた文の実行を繰り返すというループを記述するための文である。forループは、whileループと違って、ループに入る前の初期化(通常カウンタ変数の初期化を行なう)を含む点で異なる。 また言語によってはforeach文をfor … in … のように書くことがあり、このときのfor文はイテレータの繰り返し処理をする文になる。.

新しい!!: コンパイラ最適化とFor文 · 続きを見る »

FPU

FPU(Floating Point Unit、浮動小数点(演算処理)装置)とは、浮動小数点演算を専門に行う処理装置のこと。コンピュータの周辺機器のようなアーキテクチャのものもあれば、主プロセッサと一体化したコプロセッサのようなアーキテクチャのものもある。 AMDではAm9511をAPU (Arithmetic Processing Unit) と呼んでおり(2011年以降はAPUをAccelerated Processing Unitの略称として使用)、インテルではx87をNDP(Numeric data processor, 数値演算コプロセッサ)、またその命令についてNPX(Numeric Processor eXtension)とも呼んでいる。 マイクロプロセッサにおいては、Apple IIの頃は完全に周辺機器のようなアーキテクチャだったが、8087の頃には命令の一体化など、CPUの拡張装置のようなアーキテクチャになった。 インテルのx86系CPUでは387(386用)が最後となり、486からは同一のチップ内に内蔵された(486の初期には、FPUを内蔵しない廉価版と、事実上はオーバードライブプロセッサであった487もあった)。同様に、モトローラの68000系でもMC68040以降のMPUではチップ内に内蔵している。 1990年代中盤以降の高性能プロセッサではFPUはプロセッサ内部のサブユニットとなっている。プロセッサに内蔵されたFPUは、スーパースカラーで他ユニットと並列動作させることができるなど様々なメリットがあるため、現在ではFPUを単体で用いることは珍しくなっている。.

新しい!!: コンパイラ最適化とFPU · 続きを見る »

GNUコンパイラコレクション

GNU Compiler Collection(グニューコンパイラコレクション)は、GNUのコンパイラ群である。略称は「GCC(ジーシーシー)」。GNUツールチェーンの中核コンポーネント。.

新しい!!: コンパイラ最適化とGNUコンパイラコレクション · 続きを見る »

Haskell

Haskell(ハスケル)は非正格な評価を特徴とする純粋関数型プログラミング言語である。名称は数学者であり論理学者であるハスケル・カリーに由来する。.

新しい!!: コンパイラ最適化とHaskell · 続きを見る »

Java

Java(ジャバ)は、狭義ではプログラミング言語Javaを指す。広義では言語仕様以外にも、仕様が与えられているJavaクラスライブラリやJava仮想マシン、さらにはJDKやJREなどの公式のものをはじめとする、場合によってはサードパーティのものなどを含め曖昧にJavaプラットフォームと総称されるようなものなどのエコシステムなどを指すこともある。構文についてはJavaの文法の記事を参照。.

新しい!!: コンパイラ最適化とJava · 続きを見る »

LISP

LISPは、プログラミング言語である。 によって記述される。-->前置記法などが特徴である。 1958年にはじめて設計されたLISPは、現在広範囲に使用されている高水準プログラミング言語の中でもFORTRANに次いで2番目に古い。ただし、FORTRANと同様に、現在のLISPは初期のものから非常に大きく変化している。 これまでに多数の方言が存在してきたが、今日最も広く知られるLISP方言は、Common LispとSchemeである。 元々、LISPは、アロンゾ・チャーチのラムダ計算表記法に影響を受け、コンピュータープログラムのための実用的かつ数学的な表記法として作られた。そして、すぐに人工知能研究に好まれるプログラミング言語になった。最初期のプログラミング言語として、LISPは計算機科学にて、木構造、ガベージコレクション、動的型付け、条件分岐、高階関数、再帰、セルフホスティング、コンパイラを含む多くのアイディアを切り開いた。 LISPの名前は、「list processor」に由来している。リストはLISPの主要なデータ構造であり、LISPソースコードはそれ自体がリストからできている。その結果、LISPプログラムはソースコードをデータとして操作することができ、プログラマーは、マクロ・システムで新しい構文やLISP埋め込みの新しいDSLを作成できる。 コードとデータの互換性は、LISPにそのすぐに認識できる構文を与える。すべてのプログラム・コードはS式または入れ子のリストとして書かれる。関数呼び出しまたは構文は先頭が関数または演算子の名前で、その続きが引数であるリストとして書かれる。具体的には、3つの引数を取る関数fは、(f arg1 arg2 arg3)として呼び出される。.

新しい!!: コンパイラ最適化とLISP · 続きを見る »

MC68000

MC68000(エムシーろくまんはっせん)、68000は米・モトローラ(現NXPセミコンダクターズ)が開発したMPU(MPUはマイクロプロセッサを指すのにモトローラが使った語でマイクロプロセッシングユニットの略)である。略して68K(ろくはちケー)などとも。後継MPUも含めた同一アーキテクチャのシリーズを総称するときは、680x0と呼称される。モトローラ自体は周辺LSIを含めてM68000ファミリと呼称した。MC型番は量産ロットで、量産先行品はXC型番となる。.

新しい!!: コンパイラ最適化とMC68000 · 続きを見る »

ML (プログラミング言語)

ML(えむえる、Meta-Language)は、関数型言語のひとつである。現代風の関数型言語としては歴史が古いほうで、型推論機能などを持つが、デフォルトの評価戦略は遅延評価ではなく先行評価で、書き換えが可能なレコード型を持つなど、いわゆる「純粋関数型」でない特徴や機能を持つ。.

新しい!!: コンパイラ最適化とML (プログラミング言語) · 続きを見る »

MMX

MHz) MMXは、インテルが同社のPentiumプロセッサ向けに開発したSIMD型拡張命令セットである。56個の命令を含む。MMXは、MultiMedia eXtensionsの略であるとの説があったが、インテルは、略語ではない一つの語であるとしている。.

新しい!!: コンパイラ最適化とMMX · 続きを見る »

NAG数値計算ライブラリ

NAG ライブラリは、Numerical Algorithms Group(NAG社)により販売されているFortran、C言語、Java、などで使用可能な数値計算、統計解析用ライブラリである。線型方程式、固有値問題、補間、微積分、非線型方程式、微分方程式などの数学関数のほかに、相関係数、共分散、多変量解析、乱数発生などの統計計算や金融工学に必要な関数を多く取り揃えている。Windows、Linux、Solaris、HP-UX、IBM AIX、SGI IRIX, その他NECや富士通のスーパーコンピュータなどのプラットフォームで動作する。英国 The Numerical Algorithms Group Ltd. が開発、日本国内では日本ニューメリカルアルゴリズムズグループ株式会社が販売、サポートを行なっている。 NAG数値計算ライブラリでは利用言語や環境などにより以下の5種類のライブラリが用意されている。.

新しい!!: コンパイラ最適化とNAG数値計算ライブラリ · 続きを見る »

NP完全問題

NP完全(な)問題(エヌピーかんぜん(な)もんだい、NP-complete problem)とは、(1) クラスNP(Non-deterministic Polynomial)に属する決定問題(言語)で、かつ (2) 任意のクラスNPに属する問題から多項式時間還元(帰着)可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クック(Stephen Cook (1971).

新しい!!: コンパイラ最適化とNP完全問題 · 続きを見る »

RISC

RISC(りすく、Reduced Instruction Set Computer、縮小命令セットコンピュータ)は、コンピュータの命令セットアーキテクチャ(ISA)の設計手法の一つで、命令の種類を減らし、回路を単純化して演算速度の向上を図るものである。なお、RISCが提唱されたときに、従来の設計手法に基づくアーキテクチャは対義語としてCISCと呼ばれるようになった。 RISCを採用したプロセッサ (CPU) をRISCプロセッサと呼ぶ。RISCプロセッサの例として、ARM、MIPS、POWER、SPARCなどが知られる。.

新しい!!: コンパイラ最適化とRISC · 続きを見る »

Streaming SIMD Extensions

トリーミングSIMD拡張命令 (Streaming SIMD Extensions, SSE) は、インテルが開発したCPUのSIMD拡張命令セット、およびその拡張版の総称である。.

新しい!!: コンパイラ最適化とStreaming SIMD Extensions · 続きを見る »

VLIW

VLIWとはVery Long Instruction Word(超長命令語)の略で、プロセッサの命令セットアーキテクチャ(ISA)の一種類である。 VLIWプロセッサは、その実行ユニットが並列的に一度に実行できる、ロード・ストア・演算・分岐などの命令の複数個から成る、かなり長い命令語によってー単位の命令が構成されており、それをそのまま実行ユニットに投入する(各命令をatom、まとまったものをmoleculeなどと呼ぶこともある)。実行に複数クロック掛かるような命令もあるかもしれないが、そういったものも含めて、タイミング的に全て差し支えなく実行できるようにVLIWの機械語プログラムは書かれていなければならず、依存や順序を解決するような機構をハードウェアでは持たない。一般に、そのようなコードを生成するのはコンパイラの仕事となる。また、どうしても埋められないスロットはNOP(No Operation・何もしない)で埋め、命令語の長さは常に固定長となる。一般にVLIWプロセッサ自身はRISCのコンセプトをより押し進めたような設計であるが、以上のような「複数の機能が詰め込まれた長い固定長の命令」はマイクロプログラム方式における、いわゆる水平型マイクロプログラムを直接外に出したようなもの、といったような感じに近い。なお、「超長命令」の由来は命令語が最低でも(たとえば)128ビットといったように長いものであることからである。 スーパースカラやアウトオブオーダーなどと異なり、命令列はフェッチされたそのまま実行ユニットに投入され、投入された後も並列性の分析などといった必要がない為、ハードウェアコストの低下や動作の高速化が期待される。反面、VLIWの性能を引き出すにはコンパイラが重要である。その意味でRISCよりもさらにソフトウェアに依存する側に寄ったアーキテクチャといえる。 命令セットアーキテクチャではなく、マイクロアーキテクチャを指してVLIWの語が使われることもある。 VLIWの採用例として、サーバ向けとして商品化されたマイクロプロセッサとしては、インテルがHPと開発したIA-64(Itanium)のEPICアーキテクチャがあるが(EPICは修正VLIWアーキテクチャである、などとされることもある)、IA-64については(当初もくろんだようにx86の代替としては)普及はしていない。後述するが、組込み用プロセッサではVLIW風の設計の、複数メーカの複数の製品ファミリが継続している。.

新しい!!: コンパイラ最適化とVLIW · 続きを見る »

X86

x86(エックスはちろく)は、Intel 8086、およびその後方互換性を持つマイクロプロセッサの命令セットアーキテクチャの総称。16ビットの8086で登場し、32ビット拡張の80386(後にIA-32と命名)、64ビット拡張のx64、広義には更にAMDなどの互換プロセッサを含む。 なおインテルのIA-64は全く異なる。.

新しい!!: コンパイラ最適化とX86 · 続きを見る »

抽象構文木

抽象構文木(abstract syntax tree、AST)とは、通常の構文木(具象構文木あるいは解析木とも言う)から、言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した(抽象した)木構造のデータ構造である。 理論的には、有限なラベル付き有向木であり、分岐点に演算子、葉にそのオペランドを対応させたものである。つまり、葉は変数や定数に対応する。 抽象構文木は構文解析で構文木とデータ構造の中間的なものとして使用される。さらにコンパイラやインタプリタなど(プログラミング言語処理系)でのプログラムの中間表現として使われ、コンパイラ最適化やコード生成はその上で行われる。抽象構文木のとりうる構造は抽象構文で記述されている。 抽象構文木は(具象)構文木とは異なり、プログラムの意味に関係ない部分を省略する。そのような省略の例としては括弧の省略があげられる。抽象構文木では、オペランドのグループ化が自明な木構造とするのが普通であり、グループ化のための括弧などは意味的に不要である。 大多数のプログラミング言語のような文脈自由言語の構文解析で抽象構文木を作るのは簡単である。構文規則ごとに新たな節点を作成し、葉はその規則における記号に対応する。グループ化規則のような抽象構文木に関わらない規則は無視される。そのようにいきなり抽象構文木を生成することもあるし、完全な具象構文木を作り、その後そこから冗長な部分(プログラムの意味に関係しない部分)を除いて抽象構文木に変換することもある。 理論的な観点からは、たとえばソースコード上の位置(何行目の何カラム目など)といった具象の情報は言語処理系には不要であり、抽象構文木には無くてもよいのだが、実践的には、エラーを見つけた時にプログラマに親切なエラーメッセージを出力するためなど、重要な情報であり、時には処理系のフロントエンドではなくバックエンドでも必要なこともある。.

新しい!!: コンパイラ最適化と抽象構文木 · 続きを見る »

排他的論理和

ベン図による排他的論理和P \veebar Q 排他的論理和(はいたてきろんりわ、)とは、ブール論理や古典論理、ビット演算などにおいて、2つの入力のどちらか片方が真でもう片方が偽の時には結果が真となり、両方とも真あるいは両方とも偽の時は偽となる演算(論理演算)である。XOR、EOR、EX-OR(エクスオア、エックスオア、エクソア)などと略称される。.

新しい!!: コンパイラ最適化と排他的論理和 · 続きを見る »

機械語

機械語(きかいご)またはマシン語(Machine code、machine language)とは、コンピュータのプロセッサが直接解釈実行可能な一連の命令群のデータそのもの(を、コンピュータ・プログラミング言語とみなしたもの)である。.

新しい!!: コンパイラ最適化と機械語 · 続きを見る »

演算子強度低減

演算子強度低減(英: Strength reduction)とはコンパイラ最適化手法の一つで、コストの高い演算式を等価でコストの低い演算式に置き換えるものである。 演算子強度低減では、数学的な同一性を用いて低速な演算式を高速な演算式で置換する。置換したことによるコストと利点は対象の CPU や、時には周辺のコード(CPU 内の機能ユニットが利用できるかどうか)に大きく依存する。.

新しい!!: コンパイラ最適化と演算子強度低減 · 続きを見る »

演算装置

演算装置(えんざんそうち)は、コンピュータ(プロセッサ)の構成要素のひとつで、論理演算や四則演算などの演算をおこなう装置である。.

新しい!!: コンパイラ最適化と演算装置 · 続きを見る »

末尾再帰

末尾再帰(まつびさいき)とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出し (:en:Tail call)という。呼び出しではなく、戻り先を保存しないジャンプに最適化できるという特徴がある(#末尾呼出し最適化)。.

新しい!!: コンパイラ最適化と末尾再帰 · 続きを見る »

最適化 (情報工学)

ンピュータ関連において最適化(Optimization)という語は、最適化問題のそれを指すことも多いが、ここでは、コンパイラ最適化などに似た話題について説明する(「情報工学」と記事名には付いているが、全く information engineering の話題ではない)。コンピュータシステムは、主としてコストパフォーマンス上の理由から、効率的に(efficiently)動作することが望ましいことが多い。例えば、コンパイラ最適化は、高速化のためだったり、メモリの使用量を削減するためだったり、電力消費を抑えるためだったりする。最適化の対象となるシステムは、1つのプログラムの場合もあるし、複数のコンピュータの場合もあるし、インターネットのようなネットワーク全体の場合もある。 "optimization" という単語の語源は "optimal"(最適な、最善な)と同じだが、最適化によって真に最適なシステムとなることは稀である。最適化されたシステムは一般にある面でのみ最適となる。プログラムの実行時間を削減するためにメモリ使用量を増やしてでも実行時間を最適化したり、逆にメモリが少ないシステムで実行時間が長くなることを覚悟してメモリ使用量が少ないアルゴリズムを選んだりする。あらゆる場合に最適な方法や設計は存在しないので、技術者は最も重要と思われる観点での最適化のために妥協点を探る。さらに、ソフトウェアを完全に最適にする(それ以上どうやっても最適化できない状態にする)のに要する労力は、その最適化されたシステムを利用することで得られる利益よりも大きい。従って、最適化の工程は完全な最適解に到達する以前に終了させられるのが普通である。幸いなことに、効果の大きい改善は最適化工程の初期に現れることが多い。 最適化は様々なレベルで行われる。最も高いレベルの最適化は設計段階に行われる。設計が最適化されていれば、実装でも効率的なアルゴリズムを利用でき、品質のよいコードになるという利点がある。コンパイラ最適化を使えば、実行ファイルがさらに最適化される。最も低いレベルでは、コンパイラを使わずに人間がアセンブリ言語で最適なコードを書く。コンパイラ最適化の技術の進歩と最近のCPUの複雑さのため、コンパイラよりも最適なコードを人間が書くには大変な技能を要する。そのため、このような最適化を行うプロジェクトは滅多にない。最適化は例外的なケースを考慮しつつ、複雑な妥協点を探ることが多い。従って最適化されたプログラムはプログラマが理解できないほど難解になることも多い。可能であれば等価であることが保証されながらプログラムを変形させるなどの手法でバグの可能性をゼロにすべきだが、できない場合、できてないコードではバグを多く含む危険性がある。.

新しい!!: コンパイラ最適化と最適化 (情報工学) · 続きを見る »

数値解析

バビロニアの粘土板 YBC 7289 (紀元前1800-1600年頃) 2の平方根の近似値は60進法で4桁、10進法では約6桁に相当する。1 + 24/60 + 51/602 + 10/603.

新しい!!: コンパイラ最適化と数値解析 · 続きを見る »

3番地コード

3アドレスコード(英: three-address code)とは、コンピュータ・プログラミング言語処理系などにおける中間表現などにおける形式の1パターンである。処理系においては、コンパイラ最適化などの処理を掛けるのに適している。2つの入力と1つの出力のアドレス(メモリまたはレジスタ)を指定する形式であるため、3アドレスコードと呼ばれる。命令セットアーキテクチャにおける「3オペランド」形式の類推とも言える。.

新しい!!: コンパイラ最適化と3番地コード · 続きを見る »

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »