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)も入る。
Module unit = Module.loadSLir(sexp, targetName, targetConvention, root); unit.basicOptimization(); unit.generateCode(out);によって呼び出されている。これらのメソッドの中はいくつかのステップに分けられており、 それが順次呼び出されるのであるが、それは次のように表現されている。
Module unit = new Module(sexp, targetName, convention, root); unit.apply(new String[] { "IntroVirReg", "EarlyRewriting", "+AfterEarlyRewriting", "If2Jumpc" }); return unit;
unit.apply(new String[] { "+BeforeBasicOpt", "SimpleOpt", "JumpOpt", "PreHeaders", "LoopInversion", "+AfterBasicOpt" });
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)を見ていただきたい。
public static void attach(CompileSpecification spec, Root root)というメソッドを定義して、その中で、たとえば
root.addHook("+AfterBasicOpt", myTransformer);を実行すれば、basicOptimizationの最後の
unit.apply("+AfterBasicOpt");を実行した時に、myTransformerが呼び出される。
このような追加機能のクラスを入れるパッケージとして
coins.backend.contribが用意されている。これは外部からの貢献(contribution)を入れるために設けてあるので、 そのようなお申し出があれば、入れる予定である。ただし、十分にデバッグをされた上で 提供されることを期待している。
追加機能の例を次に説明する。
-coins:schedule,attach=coins.backend.sched.Schedule または -coins:attach=coins.backend.sched.Scheduleとすればよい。なお、
-coins:trace=TMDを付け加えると、命令スケジューラでのリストスケジュールの経過が出力される。
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オプション指定もあれば、それより前の 命令選択をした後(1回目のレジスタ割り付けをする前)に、 apply("+AfterFirstInstSel")によってbeforeというTransformerが呼ばれ、 命令スケジューラが実行される。
(new Schedule()).schedule(func, "Before");であり、後者が
(new Schedule()).schedule(func, "After");であるので、ほとんど同じであるが、後者では 遅延分岐の遅延スロットを埋めるための処理が行われるところが異なる。
整数演算に関しても、レジスタ数が少ないので、命令スケジューラで 命令を並べ替えた結果、レジスタ割付けが出来なくなる場合がある。
COINSのTestディレクトリ以下にはコンパイラのテストプログラムが 入っており、Test/C/testdriver.shを使って、約700個のテストプログラムが 正常に実行されるかをチェックすることが出来るが、その中の1つ
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という例外を発生する。
2.の利点についてもう少し説明する。一般に、命令スケジュールをレジスタ割り付け前にするのが
よいか、レジスタ割り付け後にするのが良いかは分からない。前にすれば、並列実行の可能性を
あげることが出来るかも知れないが、多くのレジスタを必要とすることになって、
レジスタ割り付けを不利にしてしまうかも知れないし、
後にすれば、レジスタ割り付けはうまくいくかも知れないが、レジスタの依存関係によって
並列実行の可能性が減るかも知れないからである。
もう一つの方法は、両方を同時に行う方法であるが、そのアルゴリズムは複雑になることが
予想されるし、機械語非依存の形で実現するのも困難が予想されるので、
当面は考えないことにした。
ここでは、以下の理由によって、命令スケジュールをレジスタ割り付け前と後の両方で
行うことにした。
現在のレジスタ割り付け
のアルゴリズムでは出来るだけ少ないレジスタを使うようにしているので、演算の途中結果などは
同じレジスタに割り付けられてしまうことが多くなり、演算間の並列実行の可能性が
ほとんどなくなってしまうこと
が多い。したがって命令スケジュールをレジスタ割り付け前に行う必要がある。
一方、命令スケジュールの一部として行うnopの穴埋めは、現在のLIRの形を崩すことになるので、
アセンブラ出力の直前に行う必要がある。以上のことから、命令スケジュールを
レジスタ割り付け前と後の両方で行うことにした。
その後、b.のnopの穴埋めをするために、バックエンドに新たな機能が追加された。 それは、命令スケジューラでLIR(LirNode)にdelayの印をつける(nopの穴埋めに使える命令であると言う印をつける)ことを仮定して、追加された機能であり、
Aに対応する命令1 A -> Aに対応する命令n-1 Aに対応する命令n ... ... JUMPC -> br.. nopが次のようになる
Aに対応する命令1 Aに対応する命令n-1 ... ... br.. Aに対応する命令nなお、ここでは、SPARCのannul命令を扱うことは考えていない。
たとえば、sparc.tmdでは
(defrule void (JUMP label) (code (ba $1) (delayslot)) (cost 1))
となっている。
たとえば、sparc.tmdでは
%defemit(delayslot) { return "\tnop"; }
となっている。
命令AとBの依存関係は
なお、依存関係の判定に関して、 当初は同じ名前のレジスタがあれば、「共通のものがある」としていてが、 それでは32ビットのレジスタRを 2つの16ビットレジスタR1、R2として使っている場合などに正しい判定が出来ない。 そこで、「同じ名前のレジスタ」で判定するのでなく、「オーバラップしているレジスタ」 で判定するようにあらためた。
1つ目の問題点は、命令選択後のLIRの1命令が、必ずしも 機械語の1命令に対応せず、機械語の複数命令に対応する場合があることから生ずる問題である。
2つ目の問題点は、ときどきレジスタ・アロケーションに失敗してコンパイル出来なくなる 問題である。
3つ目の問題点は、浮動小数点演算を含むプログラムでターゲットマシンがx86の場合に 適用すると、異常に長い時間がかかることがある問題である。
4つ目の問題点は、CALL命令については、それがdealy-slotを持つ場合でも、 その直前の命令だけをnopの穴埋めの候補としていることから、nopの穴埋めが 出来なくなる可能性があることである。
その4つの問題点と、その解決法を以下に述べる。
現在のリリース版にはそれが入っている。
その問題を根本的に解決するためには、TMDの記述を改めて、命令選択後のLIRの1命令が、必ず 機械語の1命令に対応するようにする方法がある。 それが出来れば、命令選択後のピ−プホール最適化なども大変やりやすくなる。 しかし、その変更はあまり簡単ではない。
それが実現する前の応急的な処置法としては、LIR命令が機械語の複数命令からなる場合は、 それをnopの穴埋めには使わないようにすれば良い。 現在の命令スケジューラではそのようにしている。
その原因は、現在の命令スケジューラがサブルーチン・コールを超えて 命令の並べ替えをすることがあったからである。SPARCの古いマシンの場合は 乗除算がサブルーチン・コールとなるので、そのためにレジスタが占有されて レジスタの少ないマシンと同様の事情になる。
これを解決する一つの方法は、サブルーチン・コールを超えた命令移動はしないよう にすることである。
LIRではサブルーチン・コールはPARALLEL式の中に入っている。 SPARCの古いマシンの乗除算は、LIRではサブルーチン・コールの形にはなっていないが やはりPARALLEL式の中に入っている。したがって、PARALLEL式を超えた 命令移動はしないようにすれば良い。
それを実現する簡単な方法は、命令スケジュールの対象を、今まで基本ブロック単位 にしていたのを、基本ブロックをPARALLEL式で区切ったセグメント単位にする方法である。
命令選択の前後では、ローカル変数や演算の途中結果はLIR上ではバーチャルレジスタ名になっている。 命令スケジューラでは、これらのレジスタの名前が違えば違うレジスタ として、同時に複数のレジスタが使われるようなスケジュールをしているのであるが、 レジスタがスタック型になっている場合は、実際にアクセス出来るのは スタックのトップのレジスタだけであるので、 レジスタ割付けで実レジスタを割付けるときに、非常に効率の悪いプログラムになってしまう 可能性がある。
そのようなことを避ける簡単な方法は、スタック型レジスタの場合は、命令スケジューラでは レジスタは一つしかないと見なし、すべてのレジスタは同一であるとしてスケジュール する方法である。現在の命令スケジューラではそのように変更してある。
その方法を、行列の積のプログラムの例で説明する。 ソースプログラムは以下のようなものである。
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回分のデータに対する処理が並列して行われる。
-coins:schedule,pipelining,attach=coins.backend.sched.Scheduleとすればよい。ソフトウェア・パイプライニングはレジスタ割付け前に行われる。
ソフトウェア・パイプライニングの対象となるのは、ループの本体が 1つの基本ブロックだけからなるループであり、その中に関数呼び出しを 含まないものである。ソフトウェア・パイプライニングの対象とならない 部分については、オプション指定のscheduleによって、命令スケジューリング が行われる。
COINSのレジスタ割付けは、使用するレジスタを出来るだけ少なくする方針で割付けられており、 演算の途中結果はほとんど同じレジスタに割付けられるので、 その後でのソフトウェア・パイプライニングはあまり効果が出せない。
そこで、レジスタ割付け前にソフトウェア・パイプライニングを行うこととした。 レジスタ割付け前には、演算の途中結果はすべて異なる名前の仮想レジスタに割付けられているので、 ソフトウェア・パイプライニングの効果が期待できる。ただし、レジスタ割付けが 難しくなって、レジスタのスピルが生じた場合は、その効果が半減するかも知れない。
以下では、最初にあげた行列の積の最内側のループの例を使って、 実装したソフトウェア・パイプライニングのアルゴリズムを説明する。
ソフトウェア・パイプライニングは以下の手順で行われる。
その結果、次のものが得られる。
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
実際には、このパイプライニングの操作はレジスタ割付けの前に行うのであるが、 最終結果との対応が分かるように、ここではレジスタ割付け後の命令列を使って説明する。
その結果、
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の穴埋めに使われるのはレジスタ割付け後の命令スケジューラで行われ ることであるが、ここでも、最終結果との対応が分かるように、最終的な形で説明する。
それらは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
その最後の分岐命令の条件を反転する。その結果、次のブロックが得られる。
.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の最大値の数だけ作られる。
それらの命令の順序はカーネルにある順序の通りとする。 その最後の分岐命令の条件を反転する。その結果、次のブロックが得られる。
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に合流するところへ飛べば良い。
今の場合は最大値が2であるから、上記のようにstage 1の命令をスケジュールしたところで 終わりである。
stage数の最大値を持つ命令を並べる。今の場合は
.L6: fadds %f2,%f3,%f2 stage 2
であり、これがプロローグの最後のブロックからの飛び先である。stageの最大値が1であれば、 エピローグはこれだけで終わりである。エピローグブロックはプロローグと同じようにstageの 最大値の数だけ作られる。
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で命令のコストとして記述されているもの)だけを使うことにする。 そして、資源予約表としては、ループを構成する命令数だけの長さを持った表を使い、 その中にスケジュールした命令を埋め込んでいくことにする。 ただし、スケジュールに柔軟性を持たせるために、表の長さを途中で変更出来るようにしておく。
先に述べた手順をより詳しく説明していく。
命令スケジューラの中で、基本ブロックを1つずつ調べながら、 それがソフトウェア・パイプライニングの対象となるものであればそれに対して ソフトウェア・パイプライニングを行い、そうでなければ命令スケジュールを行う。
ソフトウェア・パイプライニングの対象となるものは、1つの基本ブロックだけから なるループ(基本ブルックの先行ブロックに自分自身が含まれるもの)であり、 そのブロックの中にPARALLEL命令がなく、かつロード命令のレイテンシー以上の レイテンシーを持つ命令を含んでいるものとする。
そのブロックの中では他の命令に依存しない命令のリストschedulableと、 他の命令に依存している命令のリストunSchedulableを作る。
(これの代わりに、カーネルのstage 1の先頭の方にスケジュールする、と言う方法も考えられる。 そのコードも作ってあるがコメントアウトしてある。どちらが有効か分かった時点でどちらかを 選ぶことにする)
まず、メソッドselectFromSchedulableで、スケジュール可能な命令リストの中から 最初にスケジュールするものを選ぶ。 ここでは、pathLength(それに依存する命令のレイテンシーの和)が長い命令から順に選んでいくのが 良いかも知れないが、より簡単に、依存する命令を持つものすべてを選ぶことにした。 そうすると、後の処理も簡単になる。
次に、メソッドscheduleNodesOfSelectedListで、選んだ命令をスケジュールしていく。 最初はカーネルの底の方だけからスケジュールするようにしていたが、 それではうまく行かないケースがあった。それは、ループ終了判定命令とそれが依存する 命令としてスケジュールした命令がtableの先頭の方にあり、ここでスケジュールした命令が tableの底の方にあり、 その2つの命令が離れすぎているので、その2つの命令に依存する命令がスケジュール出来ないという ケースである。それらの命令の依存関係をすべて調べてからもっとも適当なところにスケジュール すればいいのであるが、それは簡単ではない。そこで、ここでは、ループ終了判定命令とそれが 依存する命令のスケジュールでtableが広げられたときには、 tableの真ん中から下の方にスケジュールしていくことにしている。
なお、以上のように命令をスケジュールしたときには、その命令Aに依存していた命令Bに対して、 命令Aがどこにスケジュールされたかという情報と、依存関係が真の依存であったか偽の依存で あったかの情報を付加していく。そして、命令Bがスケジュール可能になった場合は、 Bが真に依存する命令があった場合はBをscheduleFirstリストに入れ、 そうでない場合はscheduleSecondリストに入れる。
メソッド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を1つ広げてそこにスケジュールする。tableを広げたときは、その場所以降にスケジュール されていた命令の場所が変わるから、それを設定し直す必要がある。その際、変更すべき場所が 沢山あると大変だから、変更を少なく済ませるためにPairIndexの値はスケジュールされた命令に だけ入れておくことにする(Reasonの中にPairIndexの値を直接入れるようなことはしない)。
scheduleSecondリストにある命令をスケジュールするときはメソッドtable.setWithFalseDependで スケジュールする。setWithFalseDependではsetWithReasonと同じようなスケジュールを するのであるが、 命令のレイテンシーを考える必要がない分簡単になっている。
最後にメソッドscheduleRemainingSchedulableNodesで、schedulableリストに残っているもの (スケジュール可能であったがそれに依存する命令のない命令)をスケジュールする。 この命令はtableの空いているところに入れれば良い。
プログラム名 | 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でnの値を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; }相関係数1と2は、それぞれ以下のようなループが実行の主たる部分を占めるプログラムである。
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; }相関係数2:変数の型は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回呼び出している。
p = &a;のような操作が行われていない変数aについては、それを疑似レジスタ名で置き換え、 レジスタ割り付けの結果によって、レジスタに割り付けられるようにしている。
そこで、ある条件を満足するループについて、ループ内で参照されている
グローバル変数に対してレジスタ・プロモーションを
するようにしたのが、本節のレジスタ・プロモーションである。
具体的には、そのループに入る前にそのグローバル変数の値をレジスタにロードし、
そのループを出たところで、レジスタからそのグローバル変数に代入する。
その条件は
なお、このプログラムは、東工大の佐々研究室で卒業研究の一貫として開発されたものである。 詳細はその 卒業論文を参照されたい。
バージョンcoins-1.4.5.2 からは、拡張レジスタ・プロモーション
の機能が追加されている。これは、ポインタ解析を行うことによって、
ポインタを使っている場合も、安全性が確認された変数に
対して、レジスタ・プロモーションの対象として、効率を上げようとする
ものである。
-coins:regpromote,attach=RegPromoteとすればよい。命令スケジューラの場合は
-coins:schedule, attach=coins.backend.sched.Scheduleとしていたが、RegPromoteクラスは、拡張のために用意されているcoins.backend.contribパッケージに 入れてあるので、そのパッケージ名を省略することが出来る。
拡張レジスタ・プロモーションを使うには、オプション指定で
-coins:regpromote-exとすればよい。attach= を指定する必要はない。
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; }