コード例

たとえば次のような計算を考えてみましょう。

    lw a4, 0(a0)    # レジスタa0の指すメモリの値をレジスタa4へロードする
    addi a4, a4, 1  # レジスタa4に1加える
    sw a4, 0(a1)    # レジスタa4の値をレジスタa1の指すメモリにストアする

この3つの命令の順番を入れ替えると結果が変わってしまう可能性があります。なぜならば，次のような依存関係があるからです。

lw a4, 0(a0) によってレジスタa4の値が決まります。その値を使ってaddi a4, a4, 1 という計算が行われます。
addi a4, a4, 1 によってレジスタa4の値が決まります。その値がsw a4, 0(a1) によってメモリにストアされます。

このような依存関係は，前のデータを利用して後の命令を実行することから，データ依存関係と言います。ある2つの命令にデータ依存関係がある場合には，それらの命令を入れ替えて実行すると結果が変わってしまう可能性があります。

さて，次のような計算を考えてみましょう。

# 前半
    lw a4, 0(a0)    # レジスタa0の指すメモリの値をレジスタa4へロードする
    addi a4, a4, 1  # レジスタa4に1加える
    sw a4, 0(a1)    # レジスタa4の値をレジスタa1の指すメモリにストアする

# 後半
    lw a5, 4(a0)    # レジスタa0に4加えた値の指すメモリの値をレジスタa5へロードする
    addi a5, a5,-1  # レジスタa5から1減ずる
    sw a5, 4(a1)    # レジスタa5の値をレジスタa1に4加えた値の指すメモリにストアする

先に説明したように，前半の中の3つの命令はそれぞれデータ依存関係があるので，それらの命令は順番を入れ替えることはできません。同様に後半の中の3つの命令にもそれぞれデータ依存関係があるので，それらの命令は順番を入れ替えると結果が変わってしまいます。

しかし，前半の計算と後半の計算にはデータ依存関係がありません。これらの計算の前にレジスタa0とa1の値は決まっていて変化がないことと，前半の計算と後半の計算で使うメモリ領域が重なっていません。したがって，これらにデータ依存関係がないのです。

例えば，次のように順番を入れ替えたとしましょう。

    lw a4, 0(a0)    # レジスタa0の指すメモリの値をレジスタa4へロードする
    lw a5, 4(a0)    # レジスタa0に4加えた値の指すメモリの値をレジスタa5へロードする
    addi a4, a4, 1  # レジスタa4に1加える
    addi a5, a5,-1  # レジスタa5から1減ずる
    sw a4, 0(a1)    # レジスタa4の値をレジスタa1の指すメモリにストアする
    sw a5, 4(a1)    # レジスタa5の値をレジスタa1に4加えた値の指すメモリにストアする

このように入れ替えても，全体として計算結果は変わらないでしょう。

    lw a4, 0(a0)    # レジスタa0の指すメモリの値をレジスタa4へロードする
    addi a4, a4, 1  # レジスタa4に1加える
    lw a5, 4(a0)    # レジスタa0に4加えた値の指すメモリの値をレジスタa5へロードする
    addi a5, a5,-1  # レジスタa5から1減ずる
    sw a4, 0(a1)    # レジスタa4の値をレジスタa1の指すメモリにストアする
    sw a5, 4(a1)    # レジスタa5の値をレジスタa1に4加えた値の指すメモリにストアする

このように入れ替えても，全体として計算結果は変わらないでしょう。

一般化すると，次のようになります。

機械語命令にデータ依存関係があるならば，順番を入れ替えると結果が変わってしまう可能性がある
機械語命令にデータ依存関係がないならば，どんな順番で実行しても結果は変わらない

原則・原理(1)の利用例

先のコード例を再度見てみましょう。

    lw a4, 0(a0)    # レジスタa0の指すメモリの値をレジスタa4へロードする
    addi a4, a4, 1  # レジスタa4に1加える
    sw a4, 0(a1)    # レジスタa4の値をレジスタa1の指すメモリにストアする
    lw a5, 4(a0)    # レジスタa0に4加えた値の指すメモリの値をレジスタa5へロードする
    addi a5, a5,-1  # レジスタa5から1減ずる
    sw a5, 4(a1)    # レジスタa5の値をレジスタa1に4加えた値の指すメモリにストアする

メモリから2つのロード命令によりレジスタへ値をロードしていきます。一般にCPUよりメモリの方がかなり低速なので，ロード命令があってしばらくしないとレジスタに値が格納されず，そのあとデータ依存関係のある命令列を実行することができません。

すなわち，1クロックに1命令実行する素朴なCPUだった場合，例えば1つのロード命令で10クロック待たされるとした場合，次のように実行されます。

lw a4, 0(a0) を実行する
addi a4, a4, 1 でレジスタa4を使用するので，10クロック待たされたあと，この命令を実行する
sw a4, 0(a1) を実行する
lw a5, 4(a0) を実行する
addi a5, a5,-1 でレジスタa5を使用するので，10クロック待たされたあと，この命令を実行する
sw a5, 4(a1)を実行する

このように10クロック待つことを2回もする必要があります。

しかし，もし次のようにコードを配置したとしましょう。

    lw a4, 0(a0)    # レジスタa0の指すメモリの値をレジスタa4へロードする
    lw a5, 4(a0)    # レジスタa0に4加えた値の指すメモリの値をレジスタa5へロードする
    addi a4, a4, 1  # レジスタa4に1加える
    addi a5, a5,-1  # レジスタa5から1減ずる
    sw a4, 0(a1)    # レジスタa4の値をレジスタa1の指すメモリにストアする
    sw a5, 4(a1)    # レジスタa5の値をレジスタa1に4加えた値の指すメモリにストアする

この場合は，次のように実行することが期待されます。

lw a4, 0(a0) を実行する
lw a5, 4(a0) を実行する
addi a4, a4, 1 でレジスタa4を使用するので，10-1クロック待たされたあと，この命令を実行する。しかしこの間に，10-1クロック経過している点に注意。
addi a5, a5,-1 でレジスタa5を使用するが，この時には2を実行してから10クロック経過しているので，待たなくて良い
sw a4, 0(a1) を実行する
sw a5, 4(a1)を実行する

このように10クロック待つことは1回で済みます！

データ依存関係を保ったまま命令の実行順番を入れ替えることによって，より高速化できる余地があることがわかりました。このようなコード最適化のことをインストラクション・スケジューリングまたは命令スケジューリングと言います。

コンピュータ・アーキテクチャへの応用: アウト・オブ・オーダー実行

データ依存関係に注目して適宜命令を入れ替えることを，CPUが積極的に行うような機能を持たせることが，現代的なCPUではされています。このような方式を，アウト・オブ・オーダー実行方式と言います。

このような機能を備えたCPUでは，次のようなコードが与えられた場合でも，

    lw a4, 0(a0)    # レジスタa0の指すメモリの値をレジスタa4へロードする
    addi a4, a4, 1  # レジスタa4に1加える
    sw a4, 0(a1)    # レジスタa4の値をレジスタa1の指すメモリにストアする
    lw a5, 4(a0)    # レジスタa0に4加えた値の指すメモリの値をレジスタa5へロードする
    addi a5, a5,-1  # レジスタa5から1減ずる
    sw a5, 4(a1)    # レジスタa5の値をレジスタa1に4加えた値の指すメモリにストアする

適宜順番を入れ替えて，次のように実行します。

lw a4, 0(a0) を実行する。実行結果は10クロック後に出来上がる。
addi a4, a4, 1 は1とデータ依存関係があるので，保留されたまま，次の命令へ読み進む。
sw a4, 0(a1) は2とデータ依存関係があるので，保留されたまま，次の命令へ読み進む。
lw a5, 4(a0) を実行する。実行結果は10クロック後に出来上がる。
addi a5, a5,-1 は4とデータ依存関係があるので，保留されたまま，次の命令へ読み進む。
sw a5, 4(a1)は5とデータ依存関係があるので，保留されたまま，次の命令へ読み進む。
そのうち1の実行結果が得られるので，2を実行する。
2の実行が終わるので，3を実行する。
そのうち4の実行結果が得られるので，5を実行する。
5の実行が終わるので，6を実行する。