### 9.2 バックエンドの付加機能

バックエンド部では、機能が追加しやすいように、バックエンドの各部の呼び出しかたが 工夫されている。
最初に、その呼び出しかたを説明し、その後で、機能を追加する方法を説明し、 追加された機能の例を説明する。

#### 9.2.1 バックエンドの呼び出しかた

バックエンドの呼び出しかたはcoins.driver.Driverクラスの該当する部分を 見ると分かる。それは、Driverクラスの中のcompileメソッドにある、以下の部分である。 ここでは、説明のために行に番号を付けてある。

    00    /* pass 7 -- Code generation */
    01    Root root = new Root(spec, new PrintWriter(System.out, true));
    02    String targetName
    03      = coinsOptions.getArg(CommandLine.COINS_TARGET_NAME_OPTION);
    04    String targetConvention
    05      = coinsOptions.getArg(CommandLine.COINS_TARGET_CONVENTION_OPTION);
    06    trace.trace(myName, 5000, "target name = " + targetName);
    07    Module unit = Module.loadSLir(sexp, targetName, targetConvention, root);
    08    makeCSourceFromLir("new", lirToCTimings, unit, io);
    09
    10    if(spec.getCoinsOptions().isSet("snapshot"))
    11      snap.shot(unit,"Generated LIR");
    12
    13    /* SSA optimization */
    14    if (spec.getCoinsOptions().isSet(coins.ssa.OptionName.SSA_OPT)) {
    15      unit.apply(new coins.ssa.SsaDriver(unit, io, spec));
    16      /* Simple/JumpOpt again */
    17      unit.apply(coins.backend.opt.SimpleOpt.trig);
    18      unit.apply(coins.backend.opt.JumpOpt.trig);
    19    } else {
    20      unit.basicOptimization();
    21    }
    22    if (spec.getCoinsOptions().isSet("simd")) {
    23      unit.apply(new coins.simd.SimdDriver(unit, io, spec));
    24    }
    25    makeCSourceFromLir("opt", lirToCTimings, unit, io);
    26
    27    if(spec.getCoinsOptions().isSet("snapshot"))
    28      snap.shot(unit,"Optimized LIR");
    29
    30    if(spec.getCoinsOptions().isSet("snapshot"))
    31      snap.generateXml();
    32
    33    unit.generateCode(out);
    34
    35    if (trace.shouldTrace("Sym", 1)) {
    36      trace.trace("Sym", 1, "\nSym after code generation ");
    37      symRoot.symTable.printSymTableAllDetail(symRoot.symTableRoot);
    38      symRoot.symTableConst.printSymTableDetail();
    39    }

1行目で作られるrootがバックエンドのルートとなる情報を保持する。そこにはオプション指定 の情報（spec）とアセンブリ言語で出力されるファイル（System.out）も入る。
7行目で、S式の形で表現されたLIRを読み込んで、それをクラスModuleのインスタンスの 形の内部表現に変換する。
8行目は、その時点でLIRをC言語の形で出力するかどうかチェックをしている。
１０，１１行目では、snapshotオプション指定があれば、その時点でのLIRのスナップショットをとる。スナップショットについては、９．１節を参照されたい。
14〜１８行目は、SSA最適化のオプション指定があった時の処理である。その指定がなければ 20行目が実行される。
22，23行目は、SIMD並列化のオプション指定があった時の処理である。
25行目は、その時点でLIRをC言語の形で出力するかどうかのチェック、27〜３１行目は snapshotオプション指定があった時の処理である。
３５〜３８行目は、"Sym.1"というオプション指定があった時の処理である。
結局、バックエンド部は７，２０，３３行の

    Module unit = Module.loadSLir(sexp, targetName, targetConvention, root);
    unit.basicOptimization();
    unit.generateCode(out);

によって呼び出されている。これらのメソッドの中はいくつかのステップに分けられており、 それが順次呼び出されるのであるが、それは次のように表現されている。

loadSLir

      Module unit = new Module(sexp, targetName, convention, root);
      unit.apply(new String[] {
          "IntroVirReg",
          "EarlyRewriting",
          "+AfterEarlyRewriting",
          "If2Jumpc" });
      return unit;

basicOptimization

      unit.apply(new String[] {
          "+BeforeBasicOpt",
          "SimpleOpt",
          "JumpOpt",
          "PreHeaders",
          "LoopInversion",
          "+AfterBasicOpt" });

generateCode

      unit.apply(new String[] {
          "+BeforeCodeGeneration",
          "LateRewriting",
          "+AfterLateRewriting",
          "ToMachineCode",
          "+AfterToMachineCode",
          "ConvToAsm"  });

たとえば、最初の

    unit.apply("IntroVirReg");

によって実行されるのは、coins.backend.opt.IntroVirRegクラスにあるdoItメソッドであるが、 そうなるのは、あらかじめModuleのコンストラクタの中で

    root.registerTransformer(IntroVirReg.trig);

として、そのtransformer（LIRの変換をするオブジェクト）を"IntroVirReg"と言う名前付きで rootに登録してあるからである。
なお、これを実行することによって変数のうちレジスタに割り付けても良いものには仮想レジスタ名 が付けられる。

さらに、generateCodeの中で

    unit.apply("ToMachineCode");

が実行されると、クラスFunctionのインスタンスのもつtoMachineCodeメソッドが実行 されることになるが、そのメソッドでは

        apply(LiveRange.trig);   // 変数を live-rangesに分ける
        apply(JumpOpt.trig);   // さらにJump最適化をする
        apply(JumpCanon.trig);   // JUMPC命令を標準形にする
        apply("+BeforeFirstInstSel");   // Hookを呼び出す
        apply(module.targetMachine.instSelTrig);   // 命令選択をする
        apply("+AfterFirstInstSel");  // Hookを呼び出す
        int count = 0;
        for (;;) {
          if (count++ >= REGALOLIMIT)
            throw new CantHappenException("Looks like an infinite loop during Register allocation");
          if (apply(RegisterAllocation.trig))  // レジスタ割り付け
            break;          // レジスタ割り付けに成功すればループを抜ける
          apply("+BeforeSecondInstSel");  // Hookを呼び出す
          apply(module.targetMachine.instSelTrig);   // ふたたび命令選択をする
          apply("+AfterSecondInstSel");  // Hookを呼び出す
        }
        postProcess(); // 冗長なジャンプを取り除く

が実行される。

上記のapplyの引数にある文字列の中で、"+"で始まる名前はフックと呼ばれるもので、 通常はそのapplyを実行しても何も行われないが、

     Root#addHook(String, Transformer)

と言うメソッドを呼ぶことにより、Transformerで指定されたLIR変換のクラスを Stringで指定された名前で登録することが出来る。同じ名前のフックに複数の Transformerを登録することもできる。その場合は、登録された順番に処理が 実行される。

これらの変換の具体例については バックエンド部 の実装（pdf）を見ていただきたい。

#### 9.2.2 バックエンドの機能追加の仕方

前節で説明したフックと、-coins:attachオプションを利用して、バックエンドの中身に手を加えず に、バックエンドに機能を追加する、あるいは何らかの処理を挿入する、ことが出来る。
そのためには、挿入したい処理をTransformerの規約に従って書き、そのクラスの中に

    public static void attach(CompileSpecification spec, Root root)

というメソッドを定義して、その中で、たとえば

    root.addHook("+AfterBasicOpt", myTransformer);

を実行すれば、basicOptimizationの最後の

    unit.apply("+AfterBasicOpt");

を実行した時に、myTransformerが呼び出される。
あるオプションが指定されたときだけその処理を実行したい場合は、specの中をチェックして addHookすればよい。

このような追加機能のクラスを入れるパッケージとして

    coins.backend.contrib

が用意されている。これは外部からの貢献（contribution）を入れるために設けてあるので、 そのようなお申し出があれば、入れる予定である。ただし、十分にデバッグをされた上で 提供されることを期待している。

追加機能の例を次に説明する。

#### 9.2.3 命令スケジューラ

本格的な命令スケジューラでは、対象マシンの演算器などのリソースの数、 同時に実行出来る命令の組み合わせ、 各命令のレイテンシーなどを考慮し、利用可能なリソース表をなどを使って スケジュールすることになるが、ここでは、比較的簡単な命令スケジューラで 多くのマシンに共通に使えるものとして、各命令のレイテンシーだけを考慮した 命令スケジューラを作ってみた。
ただし、SPARCマシンのような遅延分岐命令を持つマシンに対しては、 遅延スロットを埋める処理も行っている。
それでも、1. 概要 の中の「1.6 オブジェクト性能」 に見られるように効果が出ている。

##### 9.2.3.1 命令スケジューラの呼び出しかた

命令スケジューラを呼び出すには、オプション指定で

    -coins:schedule,attach=coins.backend.sched.Schedule
    または
    -coins:attach=coins.backend.sched.Schedule

とすればよい。なお、

    -coins:trace=TMD

を付け加えると、命令スケジューラでのリストスケジュールの経過が出力される。
このattach指定によって、coins.backend.sched.Scheduleのattachメソッドが 呼び出される。そのメソッドは

    public static void attach(CompileSpecification spec, Root root) {
        root.addHook("+AfterToMachineCode", after);
        if (spec.getCoinsOptions().isSet("schedule")) {
          root.addHook("+AfterFirstInstSel", before);
        }
      }

となっているので、ToMachineCodeの処理が終わった後、 すなわちレジスタ割付け後に、 afterというTransformerが呼ばれ、命令スケジューラが実行される。 さらに、scheduleオプション指定もあれば、それより前の 命令選択をした後（１回目のレジスタ割り付けをする前）に、 apply("+AfterFirstInstSel")によってbeforeというTransformerが呼ばれ、 命令スケジューラが実行される。
すなわち、scheduleオプション指定もあれば、命令スケジューラはレジスタ割付け前と後 の２回呼ばれることになり、それがなければ、命令スケジューラはレジスタ割付け後 にだけ呼ばれることになる。 その呼ばれかたは、前者が

    (new Schedule()).schedule(func, "Before");

であり、後者が

    (new Schedule()).schedule(func, "After");

であるので、ほとんど同じであるが、後者では 遅延分岐の遅延スロットを埋めるための処理が行われるところが異なる。
なお、x86のようなレジスタの少ない機種では、命令スケジューラの効果が あまり出ない場合がある。特に、浮動小数点演算に関しては、レジスタが スタック型になっているので、ほとんどスケジュールが出来ない。 したがって、後に述べるソフトウェア・パイプライニングもほとんど出来ない。

整数演算に関しても、レジスタ数が少ないので、命令スケジューラで 命令を並べ替えた結果、レジスタ割付けが出来なくなる場合がある。

COINSのTestディレクトリ以下にはコンパイラのテストプログラムが 入っており、Test/C/testdriver.shを使って、約700個のテストプログラムが 正常に実行されるかをチェックすることが出来るが、その中の１つ

    Test/C/SubpCall/tpstructFunc2.c

に対して

    -coins:schedule,attach=coins.backend.sched.Schedule,
    ssa-opt=prun/divex/cse/cstp/hli/osr/hli/cstp/cpyp/preqp/cstp/rpe/dce/srd3

というオプションを指定すると、レジスタ割付けが出来なくなって、

    coins.backend.CantHappenException: Looks like an infinite loop during Register allocation

という例外を発生する。

##### 9.2.3.2 命令スケジューラの設計

###### 設計方針

命令選択によってLIRに機械語を対応させた結果はまたLIRの形で表現されている。 この特徴を生かして、LIRに対して命令スケジュールを行えば、

1. 機械語非依存の命令スケジューラとなる。
2. 命令スケジューラを１つ作るだけで、レジスタ割り付け前にも、 レジスタ割り付け後にも適用出来る。

といった利点がある。命令選択の後でレジスタ割り付けをしても、 レジスタの表現が変わるだけで、LIRの形は変わらないからである。
ただし、１つのLIRノードが機械語の1命令に対応しているとは限らないのが問題である。 たとえば、テストして分岐するというLIRには、SPARCマシンでは機械語の3命令（比較命令、 ブランチ命令、遅延分岐のためのnop命令、の3命令）が対応している。そのために

1. １つのLIRノードに対応する複数個の命令の間ではスケジュールが出来ない
2. nopの場所に他の命令を置くこと（nopの穴埋め）が出来ない

のが問題である。
1., 2.の利点が大きいから、a.をあきらめて、b.の実現方法を考えることにして、 この方法で設計してみることにした。

2.の利点についてもう少し説明する。一般に、命令スケジュールをレジスタ割り付け前にするのが よいか、レジスタ割り付け後にするのが良いかは分からない。前にすれば、並列実行の可能性を あげることが出来るかも知れないが、多くのレジスタを必要とすることになって、 レジスタ割り付けを不利にしてしまうかも知れないし、 後にすれば、レジスタ割り付けはうまくいくかも知れないが、レジスタの依存関係によって 並列実行の可能性が減るかも知れないからである。
もう一つの方法は、両方を同時に行う方法であるが、そのアルゴリズムは複雑になることが 予想されるし、機械語非依存の形で実現するのも困難が予想されるので、 当面は考えないことにした。
ここでは、以下の理由によって、命令スケジュールをレジスタ割り付け前と後の両方で 行うことにした。
現在のレジスタ割り付け のアルゴリズムでは出来るだけ少ないレジスタを使うようにしているので、演算の途中結果などは 同じレジスタに割り付けられてしまうことが多くなり、演算間の並列実行の可能性が ほとんどなくなってしまうこと が多い。したがって命令スケジュールをレジスタ割り付け前に行う必要がある。
一方、命令スケジュールの一部として行うnopの穴埋めは、現在のLIRの形を崩すことになるので、 アセンブラ出力の直前に行う必要がある。以上のことから、命令スケジュールを レジスタ割り付け前と後の両方で行うことにした。

その後、b.のnopの穴埋めをするために、バックエンドに新たな機能が追加された。 それは、命令スケジューラでLIR（LirNode）にdelayの印をつける（nopの穴埋めに使える命令であると言う印をつける）ことを仮定して、追加された機能であり、

1. LIRからアセンブラ命令を生成する時に、delayの印のついているLIRの命令でcallや branch命令のnop（delay-slot）を置き換える機能
2. LIR（LirNode）から情報（delay-slotをもつか、costはいくつか）をとり出すメソッド （クラスCodeGeneratorのメソッドcodeInfo）

の２つである。これらの機能を使って、nopの穴埋めを行うことにした。 実際には、レジスタ割付け後の命令スケジューラで上記のdelayの印をつけることにした。
命令スケジューリングは基本ブロック単位で、リストスケジューリングの方法で行うことにする。

###### リストスケジューリング

リストスケジューリングでは、各命令の依存関係にしたがってスケジュールする。 命令Ｂが命令Aに依存している場合は命令Aをスケジュールした後でしか命令Bをスケジュールできない。今回は以下のようなアルゴリズムでスケジュールした。

1. LIRノードを上から順に走査して、以下のようにして、スケジュール可能なリスト1と スケジュール不可能なリスト2を作る
   1. リスト1とリスト2を空リストとする
   2. とり出したLIRノードがリスト1かリスト2のどれかの命令に依存していたらリスト2に入れる。 そうでなければリスト1に入れ、スケジュール時間を0（すぐスケジュールできる）とする。
2. リスト1が空になるまで、リスト1から最もよさそうなものを選んでスケジュールする。
   リスト1から最もよさそうなものを選ぶ方法はいろいろ考えられる。最初に実現した方法は、 以下の1.である。これは簡単に実現できる。次には2.を実現した。現在は、 その2つを組み合わせた3.を採用している。
   1. リスト1の中のスケジュール時間最小のもののうち、レイテンシー最大のもの （それを命令Aとする）を選んでスケジュールする。
   2. リスト1の中のスケジュール時間最小のもののうち、それ以後のパスの一番長いもの （それを命令Aとする）を選んでスケジュールする。それ以後のパスとは、 その命令に依存する命令の列とする。パスの長さは、パス中の命令のレイテンシーの和とする。 たとえば、BがAに依存し、CがBに依存したら、A-B-Cが一つのパスになり、このパスの長さは、 A, B, Cの３つの命令のレイテンシーの和とする。
   3. 上記の、レイテンシー最大のものと、パスの一番長いものの両方を求め、 前者のレイテンシーがメモリからのロードのレイテンシー以上である時は前者を選び、 そうでなければ後者を選んでスケジュールする。
      （この方針をとった時には、ロードのレイテンシーは比較的大きく7としていた。 このように時間のかかるものは出来るだけ早くに実行しておくべきだとして、このようにした。 しかし、その後、キャッシュが効いているときはレイテンシーはもっと短いこと、 ロードのレイテンシーを長いものとしていることが、他の命令のスケジューリングを阻害 していること、などからロードのレイテンシーは4に変更した。この変更後でも上記の方針 でよいかは検討の必要があるかも知れない。）
3. リスト1の各命令のスケジュール時間が1以上であったら1を引く（これは、 命令を１つスケジュールしたらクロックが１進んだと考えることに相当する）。
4. リスト2の中で命令Aに依存しているものがあったら、その依存をないものにする。 その結果依存のなくなった命令Bがあったら、それをリスト1に移す。その際、 命令Bが命令Aにフロー依存している場合は、命令Bのスケジュール時間を命令Aの レイテンシーから1引いたものとする。そうでなければ命令Bのスケジュール時間を０とする。 ただし、分岐命令は基本ブロックの最後の命令であり、最後にスケジュールされなければ ならないからスケジュール時間はLAST_TIMEとする。

###### 分岐命令のnopの穴埋め

分岐命令のnopの除去は次のようにして行っている。 ターゲットマシンが何であるかは調べていない。クラスCodeGeneratorのメソッドcodeInfo から得られる情報（delay-slotをもつか）だけから判断している。
LIR命令Aをスケジュールするとき、Aに依存する命令がなく、今扱っている基本ブロック の最後の命令が分岐命令であり、その分岐命令がdelay-slotをもつとき、Aにdelayの印をつける。
実際にdelay-slot（nop命令）をdelayの印のついた命令で埋めるのは、 クラスCodeGeneratorのメソッドbuildcodeである。その結果、たとえば、 LIR命令AとJUMPC命令が次のようになっていたとき

    		Aに対応する命令1
    A	->	Aに対応する命令n-1
    		Aに対応する命令n
    ...		...
    JUMPC   ->	br..
    		nop

が次のようになる

    		Aに対応する命令1
    		Aに対応する命令n-1
    ...		...
    		br..
    		Aに対応する命令n

なお、ここでは、SPARCのannul命令を扱うことは考えていない。
最初はこのようにしていたが、移動した命令「Aに対応する命令n」が「Aに対応する命令n-1」 までの結果に依存していて、その依存情報がbr命令までの間に失われてしまう場合は、 この変換は不正な変換である。
そのようなことが起きないようにするためには、LIRの命令と機械語の命令が1対1に対応する ようにTMDを書き換える方法が考えられるが、その変更には時間がかかるので、とりあえずの 変更としては、機械語の複数命令に対応するLIR命令は分岐命令のnopの置き換えには使わない とする方法が考えられる。上記のcodeInfoメソッドで、対応する機械語命令の数を情報として 返すようにすれば、それが実現出来る。
CALL命令については、そのCALL命令がdelay-slotを持つとき、そのCALL命令の直前の命令 （もしあれば）にdelayの印をつけておけば良い。直前の命令であるので、そのLIRに対応 する機械語の命令が複数であっても上記のような問題は起こらない。
問題になるのは次のような場合である。CALLで呼び出す先が関数ポインタで渡されたもの である場合は、直前の命令で飛び先をレジスタにセットするかも知れない。それをcallの delay-slotに移すことは出来ない。そのような場合は、delayの印をつけないように しなければならない。

tmdファイルでのdelay-slotの設定
  上記の方法によってnopの穴埋めをするためには、tmdファイルで以下の設定をする必要がある。
  - 生成されるコードで、delay-slotに置かれるnop命令は、"nop"でなく、 "delayslot"という名前にする

    たとえば、sparc.tmdでは

        (defrule void (JUMP label)
          (code (ba $1)
        	(delayslot))
          (cost 1))

    となっている。

  - delayslotに入れるべき命令がなかった場合は、アセンブラ出力の際に"nop"に戻す

    たとえば、sparc.tmdでは

        %defemit(delayslot) { return "\tnop"; }

    となっている。

###### 各命令のレイテンシー

各命令のレイテンシーは次のように決めた。 メソッドcodeInfoから得られるLIR命令のcostをレイテンシーとする。ただし、

1. メモリからのロードを含む命令であり、costがLOAD_LATENCYより小さい場合は LOAD_LATENCYをレイテンシーとする。
2. 分岐命令は最後にスケジュールすべきものであるのでレイテンシーは０とする。
3. PROLOGUEは最初にスケジュールすべきものであるのでレイテンシーは最大とする。

###### 命令の依存関係

命令の依存関係は次のようにして求めた。 まず、各命令の入力と出力を次のようにして求める。

1. 入力は、その命令の入力となるレジスタの名前、メモリーからロードする場合はMEMのしるし、 からなるリスト
2. 出力は、その命令の出力となるレジスタの名前、メモリーにストアする場合はMEMのしるし、 からなるリスト

ただし、レジスタの名前が"%t"で始まる場合は、インテルx86のスタックレジスタであり、 レジスタの番号はpush/popで動的に変化するので、レジスタの番号で依存関係を決めること は出来ない。その場合はレジスタの名前はSTACK_REG（すべて同じ名前となるので、 すべて依存することになる）とする。
（coins-1.3ではこのようになっているが、これだけでは、レジスタ割り付け前の 命令スケジューリングに対処出来ていない。その場合にも同様の処理をするように、下記の 「9.2.3.3. 命令スケジューラの問題点と解決法」では、レジスタの個々の名前を見るのではなくて、 インテルx86の浮動小数点レジスタはすべてSTACK_REGという一つの名前にしている。）

命令AとBの依存関係は

- 命令Aの出力と命令Bの入力に共通のものがあれば、命令BはAにフロー依存
- 命令Aの入力と命令Bの出力に共通のものがあれば、命令BはAに逆依存
- 命令Aの出力と命令Bの出力に共通のものがあれば、命令BはAに出力依存

である。ただしCALL命令についてはスタックで引数を受け渡すものもあるので、 CALL命令の入力リストにMEMのしるしを入れておく。

なお、依存関係の判定に関して、 当初は同じ名前のレジスタがあれば、「共通のものがある」としていてが、 それでは32ビットのレジスタRを 2つの16ビットレジスタR1、R2として使っている場合などに正しい判定が出来ない。 そこで、「同じ名前のレジスタ」で判定するのでなく、「オーバラップしているレジスタ」 で判定するようにあらためた。

##### 9.2.3.3 命令スケジューラの問題点と解決法

当初の命令スケジューラには、以下の４つの問題点があった。

１つ目の問題点は、命令選択後のLIRの１命令が、必ずしも 機械語の１命令に対応せず、機械語の複数命令に対応する場合があることから生ずる問題である。

２つ目の問題点は、ときどきレジスタ・アロケーションに失敗してコンパイル出来なくなる 問題である。

３つ目の問題点は、浮動小数点演算を含むプログラムでターゲットマシンがx86の場合に 適用すると、異常に長い時間がかかることがある問題である。

４つ目の問題点は、CALL命令については、それがdealy-slotを持つ場合でも、 その直前の命令だけをnopの穴埋めの候補としていることから、nopの穴埋めが 出来なくなる可能性があることである。

その４つの問題点と、その解決法を以下に述べる。 現在のリリース版にはそれが入っている。

###### LIRの１命令が機械語の複数命令に対応する場合

当初のの命令スケジューラでは、 命令選択後のLIRの１命令が機械語の複数命令に対応する場合には、問題が起きる可能性があった。 たとえば、nopの穴埋めに使われる命令が、そのような複数命令の中の１命令である場合、 その１命令を移動させることが、その複数命令の中で成り立っていなければならない条件を 壊す可能性があるからである。

その問題を根本的に解決するためには、TMDの記述を改めて、命令選択後のLIRの１命令が、必ず 機械語の１命令に対応するようにする方法がある。 それが出来れば、命令選択後のピ−プホール最適化なども大変やりやすくなる。 しかし、その変更はあまり簡単ではない。

それが実現する前の応急的な処置法としては、LIR命令が機械語の複数命令からなる場合は、 それをnopの穴埋めには使わないようにすれば良い。 現在の命令スケジューラではそのようにしている。

###### レジスタ・アロケーションに失敗する場合

当初の命令スケジューラでは、x86のようなレジスタの少ないマシンや、 SPARCの古いマシン（それが、targetオプション指定のない場合のデフォールトの マシンになっている）で、レジスタ・アロケーションに失敗する場合があった。

その原因は、現在の命令スケジューラがサブルーチン・コールを超えて 命令の並べ替えをすることがあったからである。SPARCの古いマシンの場合は 乗除算がサブルーチン・コールとなるので、そのためにレジスタが占有されて レジスタの少ないマシンと同様の事情になる。

これを解決する一つの方法は、サブルーチン・コールを超えた命令移動はしないよう にすることである。

LIRではサブルーチン・コールはPARALLEL式の中に入っている。 SPARCの古いマシンの乗除算は、LIRではサブルーチン・コールの形にはなっていないが やはりPARALLEL式の中に入っている。したがって、PARALLEL式を超えた 命令移動はしないようにすれば良い。

それを実現する簡単な方法は、命令スケジュールの対象を、今まで基本ブロック単位 にしていたのを、基本ブロックをPARALLEL式で区切ったセグメント単位にする方法である。

###### x86での浮動小数点演算

３番目の問題は、x86の浮動小数点レジスタがスタック型になっていることから起こる問題である。

命令選択の前後では、ローカル変数や演算の途中結果はLIR上ではバーチャルレジスタ名になっている。 命令スケジューラでは、これらのレジスタの名前が違えば違うレジスタ として、同時に複数のレジスタが使われるようなスケジュールをしているのであるが、 レジスタがスタック型になっている場合は、実際にアクセス出来るのは スタックのトップのレジスタだけであるので、 レジスタ割付けで実レジスタを割付けるときに、非常に効率の悪いプログラムになってしまう 可能性がある。

そのようなことを避ける簡単な方法は、スタック型レジスタの場合は、命令スケジューラでは レジスタは一つしかないと見なし、すべてのレジスタは同一であるとしてスケジュール する方法である。現在の命令スケジューラではそのように変更してある。

###### CALL命令の直前の命令だけがnopの穴埋めの候補

当初は、CALLのnopの穴埋めには直前の命令を使うことだけを考えていた。 直前の命令がCALLの飛び先のアドレスをレジスタに載せる命令であるときは、 nopの穴埋めは出来なくなるが、そのような場合は少ないと思っていたからである。
しかし、ある種のマシン、たとえばSH-4、ではそのような場合が多いので、 その場合には、CALL命令の２つ前の命令でnopの穴埋めをすることを考えた方が良い。
そこで、現在の命令スケジューラでは、 直前の命令がCALLの飛び先のアドレスをレジスタに載せる命令であるときは、 ２つ前の命令をnopの穴埋めの候補としている。

#### 9.2.4 ソフトウェア・パイプライニング

ループの命令レベル並列性を高める方法としてソフトウェア・パイプライニングがある。 従来のソフトウェア・パイプライニングの方法は、カウンタを使ってループの終了判定 をするループにしか使えない、ループ終了判定の命令を変更する必要がある、繰り返しの回数 が小さいループには使えない、といった問題がある。それらの問題を解決する方法として、 ループの繰り返し判定命令とその命令が依存するすべての命令を最初にスケジュールし、 その後でパイプラインのスケジュールをする方法を考案し、それをCOINSで実装した。

その方法を、行列の積のプログラムの例で説明する。 ソースプログラムは以下のようなものである。

    	for (i = 0; i < N; i++)
    		for (j = 0; j < M; j++) {
    			s = 0;
    			for (k = 0; k < L; k++)
    				s += a[i][k] * b[k][j];
    			c[i][j] = s;
    		}

ここでN=M=L=500で、各行列は500*500の配列である。

SPARCマシンに対する、この最内側のkのループのコードは

    ssa-opt=prun/divex/cse/cstp/hli/osr/hli/cstp/cpyp/preqp/cstp/rpe/dce/srd3

で以下のようになる。

    .L4:
    	ld	[%i5],%f1	 ! %f1 = a[i][k]
    	ld	[%i4],%f0	 ! %f0 = b[k][j]
    	fmuls	%f1,%f0,%f0	! %f0 = %f1*%f0 = a[i][k]*b[k][j]
    	fadds	%f2,%f0,%f2	! %f2 = s = %f2+%f0 = s + a[i][k]*b[k][j]
    	add	%i4,2000,%i4	! %i4 = &b[k][j] + 2000 = &b[k+1][j]
    	add	%i5,4,%i5	  ! %i5 = &a[i][k] + 4 = &a[i][k+1]
    	cmp	%i4,%o2      	 ! &b[k+1][j] : &b[L][j]
    	bl	.L4		  ! k+1 < L
    	nop

考案したソフトウェア・パイプライニングの方法は、ループの繰り返し判定命令と その命令が依存する すべての命令を最初にスケジュールし、その後でパイプラインのスケジュールをする方法であり、 プロローグ部にも繰り返し判定命令を入れるものである。

その方法に従って実装したパイプライニングを適用すると、以下のようなコードが得られる。

    .L4:	ld	[%i4],%f0
    	add	%i4,2000,%i4
    	cmp	%i4,%o2
    	bge	.L7
    	ld	[%i5],%f1
    	fmuls   %f1,%f0,%f3
    	add	%i5,4,%i5
    				     ld    [%i4],%f0
    				     add   %i4,2000,%i4
    				     cmp   %i4,%o2
    				     bge   .L6
    				     ld    [%i5],%f1
    ----------------------------------------------
    .L5:	fadds  %f2,%f3,%f2
    				     fmuls  %f1,%f0,%f3
    				     add    %i5,4,%i5
    							           ld	 [%i4],%f0
    							           add  %i4,2000,%i4
    							           cmp  %i4,%o2
    							           bl   .L5
    							           ld   [%i5],%f1
    ----------------------------------------------
    .L6:				     fadds %f2,%f3,%f2
    .L7:							           fmuls %f1,%f0,%f3
    							           add   %i5,4,%i5
    							           fadds %f2,%f3,%f2

最初の点線より上の部分がプロローグ部、2つの点線の間がカーネル・ループ部、 その後がエピローグ部である。実行時には、まずプロローグ部が実行され、次に カーネル・ループ部が繰り返し実行されてから、最後にエピローグ部が実行される。

各命令は並んでいる順に（上から下に）実行されるのであるが、それは以下のように解釈できる。
左端の欄の命令はループの1回目を実行するためのものである。1回で終わるときは、 左端の欄の"bge .L7"命令によって".L7:"以下の命令が実行される。
真ん中の欄の命令はループの2回目を実行するためのものである。2回で終わるときは、 真ん中の欄の"bge .L6"命令によって".L6:"と".L7:"以下の命令が実行される。
3回目以降については、まず、カーネル・ループの右端の欄の命令が実行され、次の 繰り返しで真ん中の欄の命令が実行され、その次の繰り返しで左端の欄の"fadds"命令 が実行される。
カーネル・ループを抜けた後で、エピローグが実行されるが、その右端の欄の命令は カーネル・ループの右端の欄の命令を実行したものに対応する。また、真ん中の欄の命令は カーネル・ループの真ん中の欄の命令を実行したものに対応する。

なお、カーネルループの右端の欄にあるものはstage 0、真ん中の欄にあるものはstage 1、 左端の欄にあるものはstage 2にスケジュールされているという。上記の3回目以降の説明は、 まずstage 0の命令が実行され、次の繰り返しでstage 1の命令が実行され、 その次の繰り返しでstage 2の命令が実行される、ということも出来る。

以上の説明は、もとのループの1回分のデータに対する命令がどのように実行されるかの説明であるが、 カーネル・ループの1回分の実行で行われることを中心に考えてみると、 カーネル・ループの1回の実行では、stage 1まで実行をすませたデータに対する stage 2の命令の実行と、stage 0の実行をすませたデータに対するstage 1の命令の実行と、 新しいデータに対するstage 0の実行が同時に行われることになる。すなわち、 もとのループの3回分のデータに対する処理が並列して行われる。

##### 9.2.4.1 ソフトウェア・パイプライニングの呼び出しかた

このソフトウェア・パイプライニングを使うには、オプション指定で

     -coins:schedule,pipelining,attach=coins.backend.sched.Schedule

とすればよい。ソフトウェア・パイプライニングはレジスタ割付け前に行われる。

ソフトウェア・パイプライニングの対象となるのは、ループの本体が １つの基本ブロックだけからなるループであり、その中に関数呼び出しを 含まないものである。ソフトウェア・パイプライニングの対象とならない 部分については、オプション指定のscheduleによって、命令スケジューリング が行われる。

##### 9.2.4.2 ソフトウェア・パイプライニングの設計

命令スケジューリングやソフトウェア・パイプライニングとレジスタ割付けに関しては、 どちらを先にするのが良いかは簡単には決まらない。 レジスタ割付けをした後では、レジスタによる依存が生じて並列性が生かされなくなる可能性があるし、 レジスタ割付け前では、並列性は生かされるがレジスタを多く使用するようになって レジスタ割付けが難しくなる可能性がある。

COINSのレジスタ割付けは、使用するレジスタを出来るだけ少なくする方針で割付けられており、 演算の途中結果はほとんど同じレジスタに割付けられるので、 その後でのソフトウェア・パイプライニングはあまり効果が出せない。

そこで、レジスタ割付け前にソフトウェア・パイプライニングを行うこととした。 レジスタ割付け前には、演算の途中結果はすべて異なる名前の仮想レジスタに割付けられているので、 ソフトウェア・パイプライニングの効果が期待できる。ただし、レジスタ割付けが 難しくなって、レジスタのスピルが生じた場合は、その効果が半減するかも知れない。

以下では、最初にあげた行列の積の最内側のループの例を使って、 実装したソフトウェア・パイプライニングのアルゴリズムを説明する。

ソフトウェア・パイプライニングは以下の手順で行われる。

カーネルループを作る
  1. ループ終了判定命令とそれが依存する命令をstage 0にスケジュールする

     その結果、次のものが得られる。

         0
         1
         2
         3	ld	[%i4],%f0	stage 0
         4	add	%i4,2000,%i4	stage 0
         5	cmp	%i4,%o2		stage 0
         6	bl	.L5		stage 0
         7	nop			stage 0

     実際には、このパイプライニングの操作はレジスタ割付けの前に行うのであるが、 最終結果との対応が分かるように、ここではレジスタ割付け後の命令列を使って説明する。

  2. スケジュール可能な命令でそれに依存する命令を持っているものをカーネルの底の方 （ループ終了判定命令に近いところ）にスケジュールする。

     その結果、

         	ld	[%i5],%f1

     がスケジュールされて、次のものが得られる。

         0
         1
         2
         3	ld	[%i4],%f0	stage 0
         4	add	%i4,2000,%i4	stage 0
         5	cmp	%i4,%o2		stage 0
         6	bl	.L5		stage 0
         7	ld	[%i5],%f1	stage 0

     実際には、ld命令がnopの穴埋めに使われるのはレジスタ割付け後の命令スケジューラで行われ ることであるが、ここでも、最終結果との対応が分かるように、最終的な形で説明する。

  3. スケジュール可能な命令で今までにスケジュールした命令に真に依存していた命令から はじめて、パイプライニングのスケジュールをしていく。

     それらはstage 1以降にスケジュールされることが期待出来る。真に依存していた命令を すべてスケジュールしてから、偽の依存をしていた命令をスケジュールする。 真に依存していた命令をスケジュールする場合は、依存もとの命令からその命令のレイテンシー だけ離れたところに置く必要がある。偽の依存をしていた命令をスケジュールする場合は、 依存もとの命令の後であれば良い。

     今の例では、真に依存していた命令としては。fmulsがあり（2つのld命令に真に依存している）、 さらにそれに真に依存している命令としてfaddsがあるので、それらが順次スケジュールされて 次のようになる。

         0	fadds	%f2,%f3,%f2	stage 2
         1	fmuls	%f1,%f0,%f3	stage 1
         2
         3	ld	[%i4],%f0	stage 0
         4	add	%i4,2000,%i4	stage 0
         5	cmp	%i4,%o2		stage 0
         6	bl	.L5		stage 0
         7	ld	[%i5],%f1	stage 0

     最後に、偽の依存をしていた命令をスケジュールしてカーネルが以下のように完成する。

         0	fadds	%f2,%f3,%f2	stage 2
         1	fmuls	%f1,%f0,%f3	stage 1
         2	add	%i5,4,%i5	stage 1
         3	ld	[%i4],%f0	stage 0
         4	add	%i4,2000,%i4	stage 0
         5	cmp	%i4,%o2		stage 0
         6	bl	.L5		stage 0
         7	ld	[%i5],%f1	stage 0

プロローグを作る
  1. stage 0の命令だけからなるブロックを作る。

     その最後の分岐命令の条件を反転する。その結果、次のブロックが得られる。

         .L4:	ld	[%i4],%f0	stage 0
         	add	%i4,2000,%i4	stage 0
         	cmp	%i4,%o2		stage 0
         	bge	.L7		stage 0
         	ld	[%i5],%f1	stage 0

     もとの分岐命令がblであったから、ここではそれを反転したbgeになっている。 この分岐命令の飛び先は、stage 1と2の命令をstageの番号順に実行して終わるところである。 stageの最大値が1であれば、プロローグはこれ一つで終わりである。1より大きければ、 以下のようにして、プロローグブロックはstageの最大値の数だけ作られる。

  2. stage 0, 1の命令だけからなるブロックを作る。

     それらの命令の順序はカーネルにある順序の通りとする。 その最後の分岐命令の条件を反転する。その結果、次のブロックが得られる。

         	fmuls	%f1,%f0,%f3	stage 1
         	add	%i5,4,%i5	stage 1
         	ld	[%i4],%f0	stage 0
         	add	%i4,2000,%i4	stage 0
         	cmp	%i4,%o2		stage 0
         	bge	.L6		stage 0
         	ld	[%i5],%f1	stage 0

     この分岐命令の飛び先は、stage 2と1と2の命令をこの順に実行して終わるところである。 したがってstage 2の命令を実行して、前記の.L7に合流するところへ飛べば良い。

  3. 同様の操作をstageの最大値-1のstageの命令がでてくるまで繰り返す

     今の場合は最大値が2であるから、上記のようにstage 1の命令をスケジュールしたところで 終わりである。

エピローグを作る
  1. エピローグの最初のブロックを作る

     stage数の最大値を持つ命令を並べる。今の場合は

         .L6:	fadds	%f2,%f3,%f2	stage 2

     であり、これがプロローグの最後のブロックからの飛び先である。stageの最大値が１であれば、 エピローグはこれだけで終わりである。エピローグブロックはプロローグと同じようにstageの 最大値の数だけ作られる。

  2. エピローグの2番目のブロックを作る

     stage数の最大値-1を持つ命令を並べ、その次にtage数の最大値を持つ命令を並べる。 今の場合は、

         .L7:	fmuls	%f1,%f0,%f3	stage 1
         	add	%i5,4,%i5	stage 1
         	fadds	%f2,%f3,%f2	stage 2

     であり、これでパイプライニングが完成する。

以下では、以上のアルゴリズムをより詳しく説明する。

通常のソフトウェアパイプライニングでは、モジュール資源予約表と呼ばれるものを使い、 その表に命令を埋めていくことでスケジュールする。資源としては、整数演算ユニット、 浮動小数点演算ユニット、ロード・ストアユニットなどが考えられる。 命令記述（TMD）ファイルで、それらの資源の数や各命令が使う資源の記述がされていれば、 それらの資源予約表を作ってスケジュールすることが出来る。 しかし、現在のCOINSのTMDにはそのような記述は入っていない。

ここでは、資源としては、レジスタとメモリだけを考え、 各命令がどのレジスタを使っているか（書き込んでいるか読んでいるかの区別はする）、 あるいはメモリを使っているかという情報と、命令のレイテンシー （COINSのTMDで命令のコストとして記述されているもの）だけを使うことにする。 そして、資源予約表としては、ループを構成する命令数だけの長さを持った表を使い、 その中にスケジュールした命令を埋め込んでいくことにする。 ただし、スケジュールに柔軟性を持たせるために、表の長さを途中で変更出来るようにしておく。

先に述べた手順をより詳しく説明していく。

対象とするブロックを見つける

  命令スケジューラの中で、基本ブロックを１つずつ調べながら、 それがソフトウェア・パイプライニングの対象となるものであればそれに対して ソフトウェア・パイプライニングを行い、そうでなければ命令スケジュールを行う。

  ソフトウェア・パイプライニングの対象となるものは、１つの基本ブロックだけから なるループ（基本ブルックの先行ブロックに自分自身が含まれるもの）であり、 そのブロックの中にPARALLEL命令がなく、かつロード命令のレイテンシー以上の レイテンシーを持つ命令を含んでいるものとする。

対象とするブロックに対して、その中の命令の依存グラフを作る

  そのブロックの中では他の命令に依存しない命令のリストschedulableと、 他の命令に依存している命令のリストunSchedulableを作る。

カーネルループを作る
  1. ループ終了判定命令とそれが依存する命令をstage 0にスケジュールする
     これはメソッドscheduleBranchAndDependで行う。このメソッドでは以下のことを行う。
     資源予約表の長さlistLengthはループ内の命令数とする。
     最後のブランチ命令とそれが依存するすべての命令のリストを作り、 それをもとの命令の順序でソートした配列sortedArrayを作る。
     それらの命令をスケジュールしたときにレイテンシーが全部でいくつになるか （latencyArray[0]の値）を計算する。 それがlistLength以上であれば、listLength = latencyArray[0] + 1 とする。
     長さlistLengthの資源予約表tableを作る。
     資源予約表tableにループ終了判定命令とそれが依存する命令をすべてスケジュールする。
  2. リストschedulableに入っている命令で、それに依存する命令を持っているものをカーネルの底の方（ループ終了判定命令に近いところ）にスケジュールする

     （これの代わりに、カーネルのstage 1の先頭の方にスケジュールする、と言う方法も考えられる。 そのコードも作ってあるがコメントアウトしてある。どちらが有効か分かった時点でどちらかを 選ぶことにする）

     まず、メソッドselectFromSchedulableで、スケジュール可能な命令リストの中から 最初にスケジュールするものを選ぶ。 ここでは、pathLength（それに依存する命令のレイテンシーの和）が長い命令から順に選んでいくのが 良いかも知れないが、より簡単に、依存する命令を持つものすべてを選ぶことにした。 そうすると、後の処理も簡単になる。

     次に、メソッドscheduleNodesOfSelectedListで、選んだ命令をスケジュールしていく。 最初はカーネルの底の方だけからスケジュールするようにしていたが、 それではうまく行かないケースがあった。それは、ループ終了判定命令とそれが依存する 命令としてスケジュールした命令がtableの先頭の方にあり、ここでスケジュールした命令が tableの底の方にあり、 その2つの命令が離れすぎているので、その2つの命令に依存する命令がスケジュール出来ないという ケースである。それらの命令の依存関係をすべて調べてからもっとも適当なところにスケジュール すればいいのであるが、それは簡単ではない。そこで、ここでは、ループ終了判定命令とそれが 依存する命令のスケジュールでtableが広げられたときには、 tableの真ん中から下の方にスケジュールしていくことにしている。

     なお、以上のように命令をスケジュールしたときには、その命令Aに依存していた命令Bに対して、 命令Aがどこにスケジュールされたかという情報と、依存関係が真の依存であったか偽の依存で あったかの情報を付加していく。そして、命令Bがスケジュール可能になった場合は、 Bが真に依存する命令があった場合はBをscheduleFirstリストに入れ、 そうでない場合はscheduleSecondリストに入れる。

  3. スケジュール可能な命令で今までにスケジュールした命令に真に依存していた命令からはじめて、パイプライニングのスケジュールをしていく

     メソッドscheduleDependentNodeによってスケジュールしていく。そのメソッドでは、 最初にscheduleFirstリストにある命令をスケジュールし、scheduleFirstリストが空になったら scheduleSecondリストが空になるまでscheduleSecondリストにある命令をスケジュールする。 ただし、スケジュールの結果でまたscheduleFirstリストに加えられる場合もあるので、 それのチェックもする。

     scheduleFirstリストにある命令をスケジュールするときはメソッドtable.setWithReasonで スケジュールする。 setWithReasonで命令Aをスケジュールする場合は、Aがスケジュール出来るようになった理由（Reason） を調べ、最適なスケジュール場所を選ぶようにする。それは以下のようにして決める。

     Aがスケジュール出来るようになった理由は、Aが依存している命令ですでにスケジュールされて いる命令のリストからなるが、そこにはその命令がスケジュールされた場所、Aがその命令に真に 依存していたかの情報も入っている。

     スケジュールされた場所は、stage番号とtableのインデックス の組からなる（クラスPairIndexのオブジェクト）。場所の順序は辞書式順序である。 (stage s, index i)に対して、その次の場所は(stage s, index i+1)であり、このiを増やして いってtableの長さlistLengthに達したときに(stage s+1, index 0)となる。

     このリストの中で一番最初の場所にスケジュールされたものの場所を baseMin = (stage s1, index i1)、 最後の場所にスケジュールされたものの場所をbaseMax = (stage s2, index i2)とすると、 Aをスケジュールする場所は (stage s2, index i2+1)から(stage s1+1, index i1-1)までの間である。 即ち、最後の場所の次から最初の場所の1周り後までである。 レジスタの生存区間は1周りを超えてはならないからこのようになる。

     なお、最初の場所から最後の場所までが1周り以上ある場合は、ソフトウェア・パイプライニング はあきらめる。

     命令Aを置く場所はAが真に依存している命令の場所からその命令のレイテンシー以上後であれば 良い（そのような命令が複数個あればそのそのような場所の最後（maxPairの値）以後とする）。 そのような場所で空いている場所があれば、そこにスケジュールする。空いている場所がなければ、 tableを１つ広げてそこにスケジュールする。tableを広げたときは、その場所以降にスケジュール されていた命令の場所が変わるから、それを設定し直す必要がある。その際、変更すべき場所が 沢山あると大変だから、変更を少なく済ませるためにPairIndexの値はスケジュールされた命令に だけ入れておくことにする（Reasonの中にPairIndexの値を直接入れるようなことはしない）。

     scheduleSecondリストにある命令をスケジュールするときはメソッドtable.setWithFalseDependで スケジュールする。setWithFalseDependではsetWithReasonと同じようなスケジュールを するのであるが、 命令のレイテンシーを考える必要がない分簡単になっている。

     最後にメソッドscheduleRemainingSchedulableNodesで、schedulableリストに残っているもの （スケジュール可能であったがそれに依存する命令のない命令）をスケジュールする。 この命令はtableの空いているところに入れれば良い。

以上でカーネルループが完成する。これ以後はメソッドconstructPipelinedBlocksを使って、 プロローグ、カーネル、エピローグのブロックとそのブロック内の命令の列を作る。 それらの詳細な説明は省略する。

##### 9.2.4.3 ソフトウェア・パイプライニングの評価

表9.2-1に、いくつかの例題について、COINSでソフトウェア・パイプライニングを行った場合 と行わなかった場合の実行時間と、参考のためにgcc（バージョン3.4.2）で-O2と-O3のオプション を指定した場合の実行時間を載せる。単位は秒である。

表9.2-1 いくつかの例題の実行時間

プログラム名 | no-opt | ssa | ssa+pipe | gcc -O2 | gcc -O3
--- | --- | --- | --- | --- | ---
prod | 17.83 | 13.31 | 7.70 | 13.27 | 13.28
行列積 | 4.26 | 1.95 | 1.24 | 1.94 | 1.94
相関係数1 | 34.76 | 27.27 | 23.77 | 27.26 | 26.28
相関係数2 | 35.28 | 19.63 | 15.07 | 18.65 | 20.09

no-opt、ssa、ssa+pipeがCOINSでの結果である。no-optは最適化オプションを何も指定しない場合、 ssaは

    ssa-opt=prun/divex/cse/cstp/hli/osr/hli/cstp/cpyp/preqp/cstp/rpe/dce/srd3

というオプション指定をした場合、ssa+pipeはさらにソフトウェア・パイプライニングを行った 場合である。これらの例題ではソフトウェア・パイプライニングが大きな効果を上げている。

マシンはSun Blade 1000で、UltraSPARC-III（750MHz）のデュアル構成、メモリは1 GBである。
プログラム名の行列積は500×500のfloat型の行列の積、 prodは次の関数prodでｎの値を1000000としたものを1000回呼び出したもの、

    float prod(float a[], int n){
    	int i; float s = 0;
    	for (i = 0; i < n; i++)
    		s += a[i]*a[i];
    	return s;
    }

相関係数１と２は、それぞれ以下のようなループが実行の主たる部分を占めるプログラムである。
相関係数１：変数の型はdouble

    	for (i = 0; i < n; i++) {
    		sx += x[i];  sy += y[i];
    	}
    	sx /= n;  sy /= n;
    	for (i = 0; i < n; i++) {
    		dx = x[i] - sx;  dy = y[i] - sy;
    		sxx += dx * dx;  syy += dy * dy;  sxy += dx * dy;
    	}

相関係数２：変数の型はdouble

    	for (i = 0; i < n; i++) {
    		sx += x[i];  sy += y[i];
    		sxx += x[i] * x[i];
    		syy += y[i] * y[i];
    		sxy += x[i] * y[i];
    	}

いずれも、nの値は200000で、このループを含んだ関数を500回呼び出している。

#### 9.2.5 レジスタ・プロモーション

通常は、メモリ上に割り付けられる変数に対して、それをレジスタに割り付けるようにするのが レジスタ・プロモーションであり、ループの中で頻繁にアクセスされる変数に適用すると 効果が大きい。
COINSのバックエンドでは、ローカル変数のうち、アドレスがとられていない変数、 すなわち、

     p = &a;

のような操作が行われていない変数aについては、それを疑似レジスタ名で置き換え、 レジスタ割り付けの結果によって、レジスタに割り付けられるようにしている。
しかし、グローバル変数については、レジスタに割り付けるようなことはしていない。

そこで、ある条件を満足するループについて、ループ内で参照されている グローバル変数に対してレジスタ・プロモーションを するようにしたのが、本節のレジスタ・プロモーションである。
具体的には、そのループに入る前にそのグローバル変数の値をレジスタにロードし、 そのループを出たところで、レジスタからそのグローバル変数に代入する。
その条件は

- ループ内に関数呼び出しがない
- ループ内にポインターによるメモリへの間接参照がない

である。この条件を満足するループの中で一番外側のループを対象とする。
この条件は、外部の関数の解析をいっさいせずにレジスタ・プロモーションの適用可能性を 判定するために採用したものである。

なお、このプログラムは、東工大の佐々研究室で卒業研究の一貫として開発されたものである。 詳細はその 卒業論文を参照されたい。

バージョンcoins-1.4.5.2 からは、拡張レジスタ・プロモーション の機能が追加されている。これは、ポインタ解析を行うことによって、 ポインタを使っている場合も、安全性が確認された変数に 対して、レジスタ・プロモーションの対象として、効率を上げようとする ものである。

##### 9.2.5.1 レジスタ・プロモーションの使い方

このレジスタ・プロモーションを使うには、オプション指定で

     -coins:regpromote,attach=RegPromote

とすればよい。命令スケジューラの場合は

     -coins:schedule, attach=coins.backend.sched.Schedule

としていたが、RegPromoteクラスは、拡張のために用意されているcoins.backend.contribパッケージに 入れてあるので、そのパッケージ名を省略することが出来る。

拡張レジスタ・プロモーションを使うには、オプション指定で

     -coins:regpromote-ex

とすればよい。attach= を指定する必要はない。

##### 9.2.5.2 レジスタ・プロモーションの評価

レジスタ・プロモーションだけの効果は、大きなプログラムに対してはあまり現れない。 しかし、小さなプログラムに対しては、その効果が顕著に見える場合もある。
1. 概要 の中の「1.6 オブジェクト性能」の図1-3の primeの例がそれである。その主要部は、以下のようなプログラムであり、 グローバル変数がループの中で頻繁に使われている。この例題では、 他の最適化なしで、レジスタプロモーションだけで、gcc -O2より良い性能を出している。
他の最適化なしでとはいっても、バックエンドでの基本的な最適化は行っており、 それだけでもgcc -O2に近い性能を出していることは、 「1.6 オブジェクト性能」の図1-２にも示されている。

    int candidat, quotient, remaindr, index, nth, primenum, loopend ;
    int primeNumbers[SIZE] ;

    void getPrime(int primevec[SIZE], int count)
    {
     primevec[0] = 2 ;
     nth = 1 ;
     candidat = 3 ;
     while (nth<count) {
       remaindr = 1 ;
       index = 0 ;
       loopend = 0 ;
       while(loopend==0) {
         primenum = primevec[index] ;
         quotient = candidat / primenum ;
         remaindr = candidat - quotient*primenum ;
         if (remaindr==0)
           loopend = 1 ;
         if (quotient*quotient<candidat)
           loopend = 1 ;
         index = index + 1 ;
         if (index >= nth)
           loopend = 1 ;
       }
       if (remaindr != 0) {
         primevec[nth] = candidat ;
         nth = nth + 1 ;
       }
       candidat = candidat + 2 ;
     }
     nth   = 0 ;
     while (nth<count) {
    /*   print(primevec[nth]) ;
    */
       nth   = nth + 1 ;
     }
     return;
    }

#### 9.2.6 参考ドキュメント

1. バックエンド部の実装（pdf）