2003f用のLLVMバックエンド llvm-2003f での処理の流れを、具体例とともに順番に追っていきます。
コミットID edb02bの時点での動作です。LLVM 5.0.0を使用しています。
コード中の色は筆者が勝手に付けたものです。
define i32 @pom(i32 %n) nounwind {
fasal:
%0 = icmp sge i32 %n, 2
br i1 %0, label %xeu, label %halt
xeu:
%1 = sub nsw i32 %n, 1
%2 = call i32 @pom(i32 %1)
%3 = sub nsw i32 %1, 1
%4 = call i32 @pom(i32 %3)
%5 = add nsw i32 %2, %4
br label %halt
halt:
%6 = phi i32 [ %5, %xeu ], [ %n, %fasal ]
ret i32 %6
}
fib_recursiveをほぼそのままLLVM IRで書いたものです。これがバックエンドの入力になります。
pom という関数で、 i32 の値を一つ受け取り i32 の値を返します。フィボナッチ数列の計算をする関数です。
fasal, xeu, halt と3つのBasicBlock(出口と入口がそれぞれ1つしかないコード塊)で構成されます。
式は全てSSA(単一静的代入)型式で、φノードを含みます。
%6 の行は、xeu から halt に入った場合は %5 の値を、fasal から halt に入った場合は %n の値を使うという意味です。
SelectionDAGは有向非巡回グラフの型式です。
llcコマンドで-debugを指定するとテキストで表示される他、graphviz等で画像として表示するオプションもあります。(どちらもデバッグビルドのllcでのみ有効)
ひとつのノードがひとつの命令に対応し、それぞれが入力値と出力値を持っていて、依存関係のグラフを作ります。ひとつのノードに出力値が複数あることもあります。
型の名前にある ch(chain) や glue は副作用の依存関係などを表します。
ノード名: 出力値の型 = ノードの種類 入力値, 入力値, ...
BasicBlock単位で、それぞれ独立して処理します。
LLVM IRからSelectionDAGを経由して最初のMI層に至るまで、SelectionDAGISelパスで処理されます。
DAGの画像を全部貼るとかさばるので貼りませんが、イメージしやすいように次にある、 fasal の分だけ貼っておきます。
Initial selection DAG: BB#0 'pom:fasal' SelectionDAG has 15 nodes: t0: ch = EntryToken t3: i32,ch = load<LD4[FixedStack-1]> t0, FrameIndex:i32<-1>, undef:i32 t5: ch = CopyToReg t0, Register:i32 %vreg2, t3 t8: i1 = setcc t3, Constant:i32<2>, setge:ch t10: i1 = xor t8, Constant:i1<-1> t12: ch = brcond t5, t10, BasicBlock:ch<halt 0x3748d98> t14: ch = br t12, BasicBlock:ch<xeu 0x3748ce8> Initial selection DAG: BB#1 'pom:xeu' SelectionDAG has 33 nodes: t0: ch = EntryToken t2: i32,ch = CopyFromReg t0, Register:i32 %vreg2 t4: i32 = sub t2, Constant:i32<1> t5: i32 = GlobalAddress<i32 (i32)* @pom> 0 t8: ch,glue = callseq_start t0, TargetConstant:i32<8>, TargetConstant:i32<0> t10: i32,ch = CopyFromReg t8, Register:i32 %F5 t12: i32 = add t10, Constant:i32<4> t14: ch = store<ST4[<unknown>]> t8, t4, t12, undef:i32 t17: ch,glue = F2003fISD::FENXEO t14, TargetGlobalAddress:i32<i32 (i32)* @pom> 0, RegisterMask:Untyped t18: ch,glue = callseq_end t17, TargetConstant:i32<8>, TargetConstant:i32<0>, t17:1 t20: i32,ch,glue = CopyFromReg t18, Register:i32 %F0, t18:1 t22: ch,glue = callseq_start t20:1, TargetConstant:i32<8>, TargetConstant:i32<0> t21: i32 = sub t4, Constant:i32<1> t23: i32,ch = CopyFromReg t22, Register:i32 %F5 t24: i32 = add t23, Constant:i32<4> t25: ch = store<ST4[<unknown>]> t22, t21, t24, undef:i32 t26: ch,glue = F2003fISD::FENXEO t25, TargetGlobalAddress:i32<i32 (i32)* @pom> 0, RegisterMask:Untyped t27: ch,glue = callseq_end t26, TargetConstant:i32<8>, TargetConstant:i32<0>, t26:1 t28: i32,ch,glue = CopyFromReg t27, Register:i32 %F0, t27:1 t29: i32 = add t20, t28 t31: ch = CopyToReg t0, Register:i32 %vreg0, t29 t32: ch = TokenFactor t31, t28:1 Initial selection DAG: BB#2 'pom:halt' SelectionDAG has 6 nodes: t0: ch = EntryToken t2: i32,ch = CopyFromReg t0, Register:i32 %vreg1 t4: ch,glue = CopyToReg t0, Register:i32 %F0, t2 t5: ch = F2003fISD::DOSNUD t4, Register:i32 %F0, t4:1
最初にDAGに変換された状態です。この時点で関数呼出、引数の取得、返り値などは2003f固有の処理がされています。
FrameIndex は関数のスタックフレーム内の場所を表します。負の数はフレーム内での位置が固定されているもの(主に関数に渡された引数)を表します。
setcc は値を比較して結果を i1 型の 0 か 1 で返すノード、 setge は符号付き整数の >= です。
callseq_start と callseq_end の 8 は、関数 pom を呼び出すために用意・片付けするスタックのバイト数です。
-view-dag-combine1-dags オプションでこの段階のDAGが画像で表示できます。
Optimized lowered selection DAG: BB#0 'pom:fasal' SelectionDAG has 12 nodes: t0: ch = EntryToken t3: i32,ch = load<LD4[FixedStack-1]> t0, FrameIndex:i32<-1>, undef:i32 t5: ch = CopyToReg t0, Register:i32 %vreg2, t3 t17: ch = br_cc t5, setlt:ch, t3, Constant:i32<2>, BasicBlock:ch<halt 0x3748d98> t14: ch = br t17, BasicBlock:ch<xeu 0x3748ce8> Optimized lowered selection DAG: BB#1 'pom:xeu' SelectionDAG has 33 nodes: t0: ch = EntryToken t2: i32,ch = CopyFromReg t0, Register:i32 %vreg2 t8: ch,glue = callseq_start t0, TargetConstant:i32<8>, TargetConstant:i32<0> t35: i32 = add t2, Constant:i32<-1> t10: i32,ch = CopyFromReg t8, Register:i32 %F5 t12: i32 = add t10, Constant:i32<4> t14: ch = store<ST4[<unknown>]> t8, t35, t12, undef:i32 t17: ch,glue = F2003fISD::FENXEO t14, TargetGlobalAddress:i32<i32 (i32)* @pom> 0, RegisterMask:Untyped t18: ch,glue = callseq_end t17, TargetConstant:i32<8>, TargetConstant:i32<0>, t17:1 t20: i32,ch,glue = CopyFromReg t18, Register:i32 %F0, t18:1 t22: ch,glue = callseq_start t20:1, TargetConstant:i32<8>, TargetConstant:i32<0> t37: i32 = add t2, Constant:i32<-2> t23: i32,ch = CopyFromReg t22, Register:i32 %F5 t24: i32 = add t23, Constant:i32<4> t25: ch = store<ST4[<unknown>]> t22, t37, t24, undef:i32 t26: ch,glue = F2003fISD::FENXEO t25, TargetGlobalAddress:i32<i32 (i32)* @pom> 0, RegisterMask:Untyped t27: ch,glue = callseq_end t26, TargetConstant:i32<8>, TargetConstant:i32<0>, t26:1 t28: i32,ch,glue = CopyFromReg t27, Register:i32 %F0, t27:1 t29: i32 = add t20, t28 t31: ch = CopyToReg t0, Register:i32 %vreg0, t29 t32: ch = TokenFactor t31, t28:1 Optimized lowered selection DAG: BB#2 'pom:halt' (変化なし)
いくつかの処理が最適化されました。
fasal では setcc + xor + brcond が br_cc にまとめられました。setlt は < です。
xeuでは t2 - 1 が t2 + (-1) に、 t2 - 1 - 1 が t2 + (-2) になりました。減算よりも加算の方が計算回路が簡単になるので置き換えたのでしょう。
-view-legalize-types-dags オプションでこの段階のDAGが画像で表示できます。
Type-legalized selection DAG (変化なし)
2003fで扱えない型を、扱える型に置き換えます。
例えば、16ビット整数を32ビットとして扱ったり、64ビットの演算を32ビットの演算を組合せて表現したりなどです。
-view-legalize-dags オプションでこの段階のDAGが画像で表示できます。
Legalized selection DAG: BB#0 'pom:fasal'
SelectionDAG has 12 nodes:
t0: ch = EntryToken
t3: i32,ch = load<LD4[FixedStack-1]> t0, FrameIndex:i32<-1>, undef:i32
t5: ch = CopyToReg t0, Register:i32 %vreg2, t3
t19: ch = F2003fISD::BR_CC t5, BasicBlock:ch<halt 0x3748d98>, t3, Constant:i32<2>, TargetConstant:i8<11>
t14: ch = br t19, BasicBlock:ch<xeu 0x3748ce8>
Legalized selection DAG: BB#1 'pom:xeu'
(変化なし)
Legalized selection DAG: BB#2 'pom:halt'
(変化なし)
2003fで扱えない命令を、扱える命令に置き換えます。
例えば、ビットのローテートを、ビットシフトとビット論理和で表現したりなどです。
LLVM用の条件コード setlt を、2003f用の条件コード 11(xolo) に置き換え、引数の順番も変えました。
fi と malkrz は必ず隣り合っていないといけないため、かなり後半の処理に至るまではまとめて1つの疑似命令として扱います。
-view-dag-combine2-dags オプションでこの段階のDAGが画像で表示できます。
Optimized legalized selection DAG (変化なし)
もう一度最適化します。
-view-isel-dags オプションでこの段階のDAGが画像で表示できます。
Selected selection DAG: BB#0 'pom:fasal' SelectionDAG has 13 nodes: t0: ch = EntryToken t3: i32,ch = KRZrm<Mem:LD4[FixedStack-1]> TargetFrameIndex:i32<-1>, Register:i32 %noreg, TargetConstant:i32<0>, t0 t5: ch = CopyToReg t0, Register:i32 %vreg2, t3 t19: ch = FIri_MALKRZx BasicBlock:ch<halt 0x3748d98>, t3, TargetConstant:i32<2>, TargetConstant:i8<11>, t5 t14: ch = KRZx BasicBlock:ch<xeu 0x3748ce8>, t19 Selected selection DAG: BB#1 'pom:xeu' SelectionDAG has 31 nodes: t0: ch = EntryToken t2: i32,ch = CopyFromReg t0, Register:i32 %vreg2 t8: i32,ch,glue = ADJCALLSTACKDOWN TargetConstant:i32<8>, TargetConstant:i32<0>, t0 t10: i32,ch = CopyFromReg t8:1, Register:i32 %F5 t35: i32 = ATAri t2, TargetConstant:i32<-1> t14: ch = KRZmr<Mem:ST4[<unknown>]> t10, Register:i32 %noreg, TargetConstant:i32<4>, t35, t8:1 t17: ch,glue = INJ_FENXEOr TargetGlobalAddress:i32<i32 (i32)* @pom> 0, RegisterMask:Untyped, t14 t18: i32,ch,glue = ADJCALLSTACKUP TargetConstant:i32<8>, TargetConstant:i32<0>, t17, t17:1 t20: i32,ch,glue = CopyFromReg t18:1, Register:i32 %F0, t18:2 t22: i32,ch,glue = ADJCALLSTACKDOWN TargetConstant:i32<8>, TargetConstant:i32<0>, t20:1 t23: i32,ch = CopyFromReg t22:1, Register:i32 %F5 t37: i32 = ATAri t2, TargetConstant:i32<-2> t25: ch = KRZmr<Mem:ST4[<unknown>]> t23, Register:i32 %noreg, TargetConstant:i32<4>, t37, t22:1 t26: ch,glue = INJ_FENXEOr TargetGlobalAddress:i32<i32 (i32)* @pom> 0, RegisterMask:Untyped, t25 t27: i32,ch,glue = ADJCALLSTACKUP TargetConstant:i32<8>, TargetConstant:i32<0>, t26, t26:1 t28: i32,ch,glue = CopyFromReg t27:1, Register:i32 %F0, t27:2 t29: i32 = ATArr t20, t28 t31: ch = CopyToReg t0, Register:i32 %vreg0, t29 t32: ch = TokenFactor t31, t28:1 SelectionDAG has 6 nodes: t0: ch = EntryToken t2: i32,ch = CopyFromReg t0, Register:i32 %vreg1 t4: ch,glue = CopyToReg t0, Register:i32 %F0, t2 t5: ch = KRZ_DOSNUD Register:i32 %F0, t4, t4:1
それぞれのノードを2003f固有の命令に置き換えます。
メモリを表すオペランド(f5+4@ など)は、RegisterまたはTargetFrameIndex, Register, TargetConstant の3つのオペランドを並べて表現しています。
callseq_start と callseq_end はそれぞれ ADJCALLSTACKDOWN と ADJCALLSTACKUP 疑似命令になりました。スタックの操作を表します。
レジスタ間のコピーはまだ krz になりません。
-view-sched-dags オプションでこの段階のDAGが画像で表示できます。
MI層は MachineInstr, MachineOperand, MachineBasickBlock, MachineFunction などのオブジェクトで表される状態です。
MI層では多数の最適化パスが処理されますが、今回のプログラムで変化があるものだけを取り上げます。
llc の -print-machineinstrs オプションで表示できます。
# After Instruction Selection: # Machine code for function pom: IsSSA, TracksLiveness Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] BB#0: derived from LLVM BB %fasal %vreg2<def> = KRZrm <fi#-1>, %noreg, 0; mem:LD4[FixedStack-1] Reg:%vreg2 FIri_MALKRZx <BB#2>, %vreg2, 2, 11; Reg:%vreg2 KRZx <BB#1> Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#2(0x40000000 / 0x80000000 = 50.00%) BB#1: derived from LLVM BB %xeu Predecessors according to CFG: BB#0 ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg3<def> = COPY %F5; Reg:%vreg3 %vreg4<def,tied1> = ATAri %vreg2<tied0>, -1; Reg:%vreg4,%vreg2 KRZmr %vreg3, %noreg, 4, %vreg4<kill>; mem:ST4[<unknown>] Reg:%vreg3,%vreg4 INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg5<def> = COPY %F0; Reg:%vreg5 ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg6<def,tied1> = ATAri %vreg2<tied0>, -2; Reg:%vreg6,%vreg2 %vreg7<def> = COPY %F5; Reg:%vreg7 KRZmr %vreg7, %noreg, 4, %vreg6<kill>; mem:ST4[<unknown>] Reg:%vreg7,%vreg6 INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg8<def> = COPY %F0; Reg:%vreg8 %vreg0<def,tied1> = ATArr %vreg5<tied0>, %vreg8; Reg:%vreg0,%vreg5,%vreg8 Successors according to CFG: BB#2(?%) BB#2: derived from LLVM BB %halt Predecessors according to CFG: BB#0 BB#1 %vreg1<def> = PHI %vreg2, <BB#0>, %vreg0, <BB#1>; Reg:%vreg1,%vreg2,%vreg0 %F0<def> = COPY %vreg1; Reg:%vreg1 KRZ_DOSNUD %F0<imp-use> # End machine code for function pom.
命令の実行順が決定されました。まだ仮想レジスタで、SSA型式です。
%vreg4<def,tied1> = ATAri %vreg2<tied0>, -1
は、%vreg4 = %vreg2 + -1 ということですが、%vreg4 と %vreg2 は同じ物理レジスタになることを表します。
def はレジスタの定義。killは レジスタを使用し、今後そのレジスタを使うことはないこと。
imp-def, imp-use は命令のオペランドとして明示的に指定しないが、そのレジスタを使用することを表します。
Frame Objectsの欄では、<fi#-1> で表されるものが4バイトであり、[SP+4](f5+4@) にあることが分かります。関数に渡された引数ですね。
# After Live Variable Analysis: # Machine code for function pom: IsSSA, TracksLiveness Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] BB#0: derived from LLVM BB %fasal %vreg2<def> = KRZrm <fi#-1>, %noreg, 0; mem:LD4[FixedStack-1] Reg:%vreg2 FIri_MALKRZx <BB#2>, %vreg2, 2, 11; Reg:%vreg2 KRZx <BB#1> Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#2(0x40000000 / 0x80000000 = 50.00%) BB#1: derived from LLVM BB %xeu Predecessors according to CFG: BB#0 ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg3<def> = COPY %F5; Reg:%vreg3 %vreg4<def,tied1> = ATAri %vreg2<tied0>, -1; Reg:%vreg4,%vreg2 KRZmr %vreg3<kill>, %noreg, 4, %vreg4<kill>; mem:ST4[<unknown>] Reg:%vreg3,%vreg4 INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg5<def> = COPY %F0<kill>; Reg:%vreg5 ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg6<def,tied1> = ATAri %vreg2<kill,tied0>, -2; Reg:%vreg6,%vreg2 %vreg7<def> = COPY %F5; Reg:%vreg7 KRZmr %vreg7<kill>, %noreg, 4, %vreg6<kill>; mem:ST4[<unknown>] Reg:%vreg7,%vreg6 INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg8<def> = COPY %F0<kill>; Reg:%vreg8 %vreg0<def,tied1> = ATArr %vreg5<kill,tied0>, %vreg8<kill>; Reg:%vreg0,%vreg5,%vreg8 Successors according to CFG: BB#2(?%) BB#2: derived from LLVM BB %halt Predecessors according to CFG: BB#0 BB#1 %vreg1<def> = PHI %vreg2, <BB#0>, %vreg0, <BB#1>; Reg:%vreg1,%vreg2,%vreg0 %F0<def> = COPY %vreg1<kill>; Reg:%vreg1 KRZ_DOSNUD %F0<imp-use,kill> # End machine code for function pom.
レジスタの生存期間が解析されてkillが増えました。
# After Eliminate PHI nodes for register allocation: # Machine code for function pom: NoPHIs, TracksLiveness Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] BB#0: derived from LLVM BB %fasal %vreg2<def> = KRZrm <fi#-1>, %noreg, 0; mem:LD4[FixedStack-1] Reg:%vreg2 FIri_MALKRZx <BB#1>, %vreg2, 2, 10; Reg:%vreg2 Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#3(0x40000000 / 0x80000000 = 50.00%) BB#3: Predecessors according to CFG: BB#0 %vreg9<def> = COPY %vreg2<kill>; Reg:%vreg9,%vreg2 KRZx <BB#2> Successors according to CFG: BB#2(?%) BB#1: derived from LLVM BB %xeu Predecessors according to CFG: BB#0 ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg3<def> = COPY %F5; Reg:%vreg3 %vreg4<def,tied1> = ATAri %vreg2<tied0>, -1; Reg:%vreg4,%vreg2 KRZmr %vreg3<kill>, %noreg, 4, %vreg4<kill>; mem:ST4[<unknown>] Reg:%vreg3,%vreg4 INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg5<def> = COPY %F0<kill>; Reg:%vreg5 ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg6<def,tied1> = ATAri %vreg2<kill,tied0>, -2; Reg:%vreg6,%vreg2 %vreg7<def> = COPY %F5; Reg:%vreg7 KRZmr %vreg7<kill>, %noreg, 4, %vreg6<kill>; mem:ST4[<unknown>] Reg:%vreg7,%vreg6 INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg8<def> = COPY %F0<kill>; Reg:%vreg8 %vreg0<def,tied1> = ATArr %vreg5<kill,tied0>, %vreg8<kill>; Reg:%vreg0,%vreg5,%vreg8 %vreg9<def> = COPY %vreg0<kill>; Reg:%vreg9,%vreg0 Successors according to CFG: BB#2(?%) BB#2: derived from LLVM BB %halt Predecessors according to CFG: BB#1 BB#3 %vreg1<def> = COPY %vreg9<kill>; Reg:%vreg1,%vreg9 %F0<def> = COPY %vreg1<kill>; Reg:%vreg1 KRZ_DOSNUD %F0<imp-use,kill> # End machine code for function pom.
φノードを消すために、fasal と xeu の末尾で、%vreg9 に結果を格納するコードが増えました。
また、fasal の中にある fi malkrz の条件が 11(xylo) から 10(xolo) に反転しました。
# After Two-Address instruction pass: # Machine code for function pom: NoPHIs, TracksLiveness Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] BB#0: derived from LLVM BB %fasal %vreg2<def> = KRZrm <fi#-1>, %noreg, 0; mem:LD4[FixedStack-1] Reg:%vreg2 FIri_MALKRZx <BB#1>, %vreg2, 2, 10; Reg:%vreg2 Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#3(0x40000000 / 0x80000000 = 50.00%) BB#3: Predecessors according to CFG: BB#0 %vreg9<def> = COPY %vreg2<kill>; Reg:%vreg9,%vreg2 KRZx <BB#2> Successors according to CFG: BB#2(?%) BB#1: derived from LLVM BB %xeu Predecessors according to CFG: BB#0 ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg3<def> = COPY %F5; Reg:%vreg3 %vreg4<def> = COPY %vreg2; Reg:%vreg4,%vreg2 %vreg4<def,tied1> = ATAri %vreg4<tied0>, -1; Reg:%vreg4 KRZmr %vreg3<kill>, %noreg, 4, %vreg4<kill>; mem:ST4[<unknown>] Reg:%vreg3,%vreg4 INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg5<def> = COPY %F0<kill>; Reg:%vreg5 ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg6<def> = COPY %vreg2<kill>; Reg:%vreg6,%vreg2 %vreg6<def,tied1> = ATAri %vreg6<tied0>, -2; Reg:%vreg6 %vreg7<def> = COPY %F5; Reg:%vreg7 KRZmr %vreg7<kill>, %noreg, 4, %vreg6<kill>; mem:ST4[<unknown>] Reg:%vreg7,%vreg6 INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> %vreg8<def> = COPY %F0<kill>; Reg:%vreg8 %vreg0<def> = COPY %vreg8<kill>; Reg:%vreg0,%vreg8 %vreg0<def,tied1> = ATArr %vreg0<tied0>, %vreg5<kill>; Reg:%vreg0,%vreg5 %vreg9<def> = COPY %vreg0<kill>; Reg:%vreg9,%vreg0 Successors according to CFG: BB#2(?%) BB#2: derived from LLVM BB %halt Predecessors according to CFG: BB#1 BB#3 %vreg1<def> = COPY %vreg9<kill>; Reg:%vreg1,%vreg9 %F0<def> = COPY %vreg1<kill>; Reg:%vreg1 KRZ_DOSNUD %F0<imp-use,kill> # End machine code for function pom.
A = B + C
のようになっていた命令が
A = B
A = A + C
に書き換えられました。
%vreg0 の部分では、
%vreg0 = %vreg5 + %vreg8
だったものが
%vreg0 = %vreg8
%vreg0 = %vreg0 + %vreg5
とオペランドの順番が入れ替わりました。
%vreg8 は直近で f0 からコピーしているため、最終的にコピー命令が不要になり
f0 = f0 + %vreg5
となることを期待したヒューリスティックな最適化のようです。
# After Simple Register Coalescing: # Machine code for function pom: NoPHIs, TracksLiveness Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] 0B BB#0: derived from LLVM BB %fasal 16B %vreg9<def> = KRZrm <fi#-1>, %noreg, 0; mem:LD4[FixedStack-1] Reg:%vreg9 32B FIri_MALKRZx <BB#1>, %vreg9, 2, 10; Reg:%vreg9 Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#3(0x40000000 / 0x80000000 = 50.00%) 48B BB#3: Predecessors according to CFG: BB#0 80B KRZx <BB#2> Successors according to CFG: BB#2(?%) 96B BB#1: derived from LLVM BB %xeu Predecessors according to CFG: BB#0 112B ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> 144B %vreg4<def> = COPY %vreg9; Reg:%vreg4,%vreg9 160B %vreg4<def,tied1> = ATAri %vreg4<tied0>, -1; Reg:%vreg4 176B KRZmr %F5, %noreg, 4, %vreg4; mem:ST4[<unknown>] Reg:%vreg4 192B INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> 208B ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> 224B %vreg5<def> = COPY %F0<kill>; Reg:%vreg5 240B ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> 272B %vreg9<def,tied1> = ATAri %vreg9<tied0>, -2; Reg:%vreg9 304B KRZmr %F5, %noreg, 4, %vreg9; mem:ST4[<unknown>] Reg:%vreg9 320B INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> 336B ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> 352B %vreg9<def> = COPY %F0<kill>; Reg:%vreg9 384B %vreg9<def,tied1> = ATArr %vreg9<tied0>, %vreg5; Reg:%vreg9,%vreg5 Successors according to CFG: BB#2(?%) 416B BB#2: derived from LLVM BB %halt Predecessors according to CFG: BB#1 BB#3 448B %F0<def> = COPY %vreg9; Reg:%vreg9 464B KRZ_DOSNUD %F0<imp-use,kill> # End machine code for function pom.
不要な仮想レジスタやレジスタ間コピー命令が削減されました。
以下のようにレジスタが融合されました。
%vreg3 -> %F5
%vreg7 -> %F5
%vreg2, %vreg6, %vreg8, %vreg0, %vreg1 -> %vreg9
# After Greedy Register Allocator: # Machine code for function pom: NoPHIs, TracksLiveness Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] fi#0: size=4, align=4, at location [SP] 0B BB#0: derived from LLVM BB %fasal 16B %vreg11<def> = KRZrm <fi#-1>, %noreg, 0; mem:LD4[FixedStack-1] Reg:%vreg11 32B FIri_MALKRZx <BB#1>, %vreg11, 2, 10; Reg:%vreg11 Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#3(0x40000000 / 0x80000000 = 50.00%) 48B BB#3: Predecessors according to CFG: BB#0 80B KRZx <BB#2> Successors according to CFG: BB#2(?%) 96B BB#1: derived from LLVM BB %xeu Predecessors according to CFG: BB#0 112B ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> 136B %vreg14<def> = COPY %vreg11; Reg:%vreg14,%vreg11 144B %vreg4<def> = COPY %vreg14; Reg:%vreg4,%vreg14 160B %vreg4<def,tied1> = ATAri %vreg4<tied0>, -1; Reg:%vreg4 176B KRZmr %F5, %noreg, 4, %vreg4; mem:ST4[<unknown>] Reg:%vreg4 192B INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> 208B ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> 224B KRZmr <fi#0>, %noreg, 0, %F0; mem:ST4[FixedStack0] 240B ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> 248B %vreg18<def> = KRZrm <fi#-1>, %noreg, 0; mem:LD4[FixedStack-1] Reg:%vreg18 264B %vreg17<def> = COPY %vreg18; Reg:%vreg17,%vreg18 272B %vreg17<def,tied1> = ATAri %vreg17<tied0>, -2; Reg:%vreg17 304B KRZmr %F5, %noreg, 4, %vreg17; mem:ST4[<unknown>] Reg:%vreg17 320B INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> 336B ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> 352B %vreg11<def> = COPY %F0; Reg:%vreg11 360B %vreg15<def> = KRZrm <fi#0>, %noreg, 0; mem:LD4[FixedStack0] Reg:%vreg15 384B %vreg11<def,tied1> = ATArr %vreg11<tied0>, %vreg15; Reg:%vreg11,%vreg15 Successors according to CFG: BB#2(?%) 416B BB#2: derived from LLVM BB %halt Predecessors according to CFG: BB#1 BB#3 448B %F0<def> = COPY %vreg11; Reg:%vreg11 464B KRZ_DOSNUD %F0<imp-use> # End machine code for function pom.
仮想レジスタに物理レジスタを割り当てます。表示されていませんが、割り当てるレジスタはもう決まっています。
%vreg5 は2度目の pom の関数呼出をまたいで使用されますが、関数を呼ぶとレジスタは保証されないのでスタックフレームに退避させます。
%vreg15 でスタックフレームから読み出します。
これに伴いスタックフレームに fi#0 が増えました。フレーム内での位置はだ決まっていません。
%vreg9 も同様に1度目の pom の関数呼出をまたいで使用されますが、%vreg9 はもともとメモリからのロードなので、%vreg18 で再実体化され、同じ場所からロードしなおします。
# After Virtual Register Rewriter: # Machine code for function pom: NoPHIs, TracksLiveness, NoVRegs Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] fi#0: size=4, align=4, at location [SP] 0B BB#0: derived from LLVM BB %fasal 16B %F0<def> = KRZrm <fi#-1>, %noreg, 0; mem:LD4[FixedStack-1] 32B FIri_MALKRZx <BB#1>, %F0, 2, 10 Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#3(0x40000000 / 0x80000000 = 50.00%) 48B BB#3: Live Ins: %F0 Predecessors according to CFG: BB#0 80B KRZx <BB#2> Successors according to CFG: BB#2(?%) 96B BB#1: derived from LLVM BB %xeu Live Ins: %F0 Predecessors according to CFG: BB#0 112B ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> 160B %F0<def,tied1> = ATAri %F0<kill,tied0>, -1 176B KRZmr %F5, %noreg, 4, %F0<kill>; mem:ST4[<unknown>] 192B INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> 208B ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> 224B KRZmr <fi#0>, %noreg, 0, %F0; mem:ST4[FixedStack0] 240B ADJCALLSTACKDOWN 8, 0, %F5<imp-def,dead>, %F5<imp-use> 248B %F0<def> = KRZrm <fi#-1>, %noreg, 0; mem:LD4[FixedStack-1] 272B %F0<def,tied1> = ATAri %F0<kill,tied0>, -2 304B KRZmr %F5, %noreg, 4, %F0<kill>; mem:ST4[<unknown>] 320B INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> 336B ADJCALLSTACKUP 8, 0, %F5<imp-def,dead>, %F5<imp-use> 360B %F1<def> = KRZrm <fi#0>, %noreg, 0; mem:LD4[FixedStack0] 384B %F0<def,tied1> = ATArr %F0<kill,tied0>, %F1<kill> Successors according to CFG: BB#2(?%) 416B BB#2: derived from LLVM BB %halt Live Ins: %F0 Predecessors according to CFG: BB#1 BB#3 464B KRZ_DOSNUD %F0<imp-use> # End machine code for function pom.
仮想レジスタを物理レジスタに置き換えます。不要なレジスタ間コピーの命令も削除されました。
# After Prologue/Epilogue Insertion & Frame Finalization: # Machine code for function pom: NoPHIs, TracksLiveness, NoVRegs Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] fi#0: size=4, align=4, at location [SP-4] BB#0: derived from LLVM BB %fasal %F5<def,tied1> = NTAri %F5<tied0>, 4 %F0<def> = KRZrm %F5, %noreg, 8; mem:LD4[FixedStack-1] FIri_MALKRZx <BB#1>, %F0, 2, 10 Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#3(0x40000000 / 0x80000000 = 50.00%) BB#3: Live Ins: %F0 Predecessors according to CFG: BB#0 KRZx <BB#2> Successors according to CFG: BB#2(?%) BB#1: derived from LLVM BB %xeu Live Ins: %F0 Predecessors according to CFG: BB#0 %F5<def,tied1> = NTAri %F5<tied0>, 8 %F0<def,tied1> = ATAri %F0<kill,tied0>, -1 KRZmr %F5, %noreg, 4, %F0<kill>; mem:ST4[<unknown>] INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> %F5<def,tied1> = ATAri %F5<tied0>, 8 KRZmr %F5, %noreg, 0, %F0; mem:ST4[FixedStack0] %F5<def,tied1> = NTAri %F5<tied0>, 8 %F0<def> = KRZrm %F5, %noreg, 16; mem:LD4[FixedStack-1] %F0<def,tied1> = ATAri %F0<kill,tied0>, -2 KRZmr %F5, %noreg, 4, %F0<kill>; mem:ST4[<unknown>] INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> %F5<def,tied1> = ATAri %F5<tied0>, 8 %F1<def> = KRZrm %F5, %noreg, 0; mem:LD4[FixedStack0] %F0<def,tied1> = ATArr %F0<kill,tied0>, %F1<kill> Successors according to CFG: BB#2(?%) BB#2: derived from LLVM BB %halt Live Ins: %F0 Predecessors according to CFG: BB#1 BB#3 %F5<def,tied1> = ATAri %F5<tied0>, 4 KRZ_DOSNUD %F0<imp-use> # End machine code for function pom.
スタックフレームのレイアウトを確定し、関数の始めと終わりでスタックの用意と片付けをするコードを増やします。
また、スタックフレームへのアクセスを実際のレジスタとオフセット(f5+4@など)に書き換えます。
ADJCALLSTACKDOWN と ADJCALLSTACKUP も、実際のスタック操作命令に書き換えます。
ADJCALLSTACKDOWN と ADJCALLSTACKUP の間では、スタックフレームへのアクセスでオフセットがずれることも考慮しています。
今回はありませんでしたが、スタックフレームへのアクセスは場合によっては ata 命令などを増やすことになります。
# After Control Flow Optimizer: # Machine code for function pom: NoPHIs, NoVRegs Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] fi#0: size=4, align=4, at location [SP-4] BB#0: derived from LLVM BB %fasal %F5<def,tied1> = NTAri %F5<tied0>, 4 %F0<def> = KRZrm %F5, %noreg, 8; mem:LD4[FixedStack-1] FIri_MALKRZx <BB#2>, %F0, 2, 11 Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#2(0x40000000 / 0x80000000 = 50.00%) BB#1: derived from LLVM BB %xeu Live Ins: %F0 Predecessors according to CFG: BB#0 %F5<def,tied1> = NTAri %F5<tied0>, 8 %F0<def,tied1> = ATAri %F0<kill,tied0>, -1 KRZmr %F5, %noreg, 4, %F0<kill>; mem:ST4[<unknown>] INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> %F5<def,tied1> = ATAri %F5<tied0>, 8 KRZmr %F5, %noreg, 0, %F0; mem:ST4[FixedStack0] %F5<def,tied1> = NTAri %F5<tied0>, 8 %F0<def> = KRZrm %F5, %noreg, 16; mem:LD4[FixedStack-1] %F0<def,tied1> = ATAri %F0<kill,tied0>, -2 KRZmr %F5, %noreg, 4, %F0<kill>; mem:ST4[<unknown>] INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> %F5<def,tied1> = ATAri %F5<tied0>, 8 %F1<def> = KRZrm %F5, %noreg, 0; mem:LD4[FixedStack0] %F0<def,tied1> = ATArr %F0<kill,tied0>, %F1<kill> Successors according to CFG: BB#2(?%) BB#2: derived from LLVM BB %halt Live Ins: %F0 Predecessors according to CFG: BB#1 BB#0 %F5<def,tied1> = ATAri %F5<tied0>, 4 KRZ_DOSNUD %F0<imp-use> # End machine code for function pom.
不要な制御フロー命令やBasicBlockを削減します。
fasal の中にある fi malkrz の条件が 10(xolo) から 11(xylo) に反転し、不要な BB#3 が消えました。
# After 2003f Eliminate Pseudo Instr FI_MALKRZ: # Machine code for function pom: NoPHIs, NoVRegs Frame Objects: fi#-1: size=4, align=4, fixed, at location [SP+4] fi#0: size=4, align=4, at location [SP-4] BB#0: derived from LLVM BB %fasal %F5<def,tied1> = NTAri %F5<tied0>, 4 %F0<def> = KRZrm %F5, %noreg, 8; mem:LD4[FixedStack-1] FIri %F0, 2, 11 * MALKRZx <BB#2> Successors according to CFG: BB#1(0x40000000 / 0x80000000 = 50.00%) BB#2(0x40000000 / 0x80000000 = 50.00%) BB#1: derived from LLVM BB %xeu Live Ins: %F0 Predecessors according to CFG: BB#0 %F5<def,tied1> = NTAri %F5<tied0>, 8 %F0<def,tied1> = ATAri %F0<kill,tied0>, -1 KRZmr %F5, %noreg, 4, %F0<kill>; mem:ST4[<unknown>] INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> %F5<def,tied1> = ATAri %F5<tied0>, 8 KRZmr %F5, %noreg, 0, %F0; mem:ST4[FixedStack0] %F5<def,tied1> = NTAri %F5<tied0>, 8 %F0<def> = KRZrm %F5, %noreg, 16; mem:LD4[FixedStack-1] %F0<def,tied1> = ATAri %F0<kill,tied0>, -2 KRZmr %F5, %noreg, 4, %F0<kill>; mem:ST4[<unknown>] INJ_FENXEOr <ga:@pom>, <regmask>, %F5<imp-use>, %F5<imp-def>, %F0<imp-def> %F5<def,tied1> = ATAri %F5<tied0>, 8 %F1<def> = KRZrm %F5, %noreg, 0; mem:LD4[FixedStack0] %F0<def,tied1> = ATArr %F0<kill,tied0>, %F1<kill> Successors according to CFG: BB#2(?%) BB#2: derived from LLVM BB %halt Live Ins: %F0 Predecessors according to CFG: BB#1 BB#0 %F5<def,tied1> = ATAri %F5<tied0>, 4 KRZ_DOSNUD %F0<imp-use> # End machine code for function pom.
2003f独自のパスです。まとめていた FI_MALRKZ 疑似命令を fi と malkrz に分割します。
MC層は MCInst, MCOperand などのオブジェクトで表される状態です。
llcの-asm-show-instオプションで、アセンブリ中にコメントとしてMC層の内容が表示されます。
AsmPrinterパスで、MC層を経由してアセンブリを生成します。
オブジェクトファイルを生成する場合も、同様にMC層を経由してバイナリデータを生成します。
'c'i
kue pom ; -- Begin function pom
; BB#0: ; @pom
; %fasal
nta f5 4 l' pom ; <MCInst #270 NTAri
; <MCOperand Reg:6>
; <MCOperand Reg:6>
; <MCOperand Imm:4>>
krz f0 f5+8@ ; <MCInst #213 KRZrm
; <MCOperand Reg:2>
; <MCOperand Reg:6>
; <MCOperand Reg:0>
; <MCOperand Imm:8>>
fi f0 2 xylo ; <MCInst #178 FIri
; <MCOperand Reg:2>
; <MCOperand Imm:2>
; <MCOperand Imm:11>>
malkrz xx BB0_2 ; <MCInst #261 MALKRZx
; <MCOperand Expr:(BB0_2)>>
; BB#1: ; %xeu
nta f5 8 ; <MCInst #270 NTAri
; <MCOperand Reg:6>
; <MCOperand Reg:6>
; <MCOperand Imm:8>>
ata f0 4294967295 ; <MCInst #114 ATAri
; <MCOperand Reg:2>
; <MCOperand Reg:2>
; <MCOperand Imm:-1>>
krz f5+4@ f0 ; <MCInst #211 KRZmr
; <MCOperand Reg:6>
; <MCOperand Reg:0>
; <MCOperand Imm:4>
; <MCOperand Reg:2>>
inj f5@ xx pom ; <MCInst #195 INJ_FENXEOr
; <MCOperand Expr:(pom)>>
ata f5 8 ; <MCInst #114 ATAri
; <MCOperand Reg:6>
; <MCOperand Reg:6>
; <MCOperand Imm:8>>
krz f5@ f0 ; 4-byte Folded Spill
; <MCInst #211 KRZmr
; <MCOperand Reg:6>
; <MCOperand Reg:0>
; <MCOperand Imm:0>
; <MCOperand Reg:2>>
nta f5 8 ; <MCInst #270 NTAri
; <MCOperand Reg:6>
; <MCOperand Reg:6>
; <MCOperand Imm:8>>
krz f0 f5+16@ ; <MCInst #213 KRZrm
; <MCOperand Reg:2>
; <MCOperand Reg:6>
; <MCOperand Reg:0>
; <MCOperand Imm:16>>
ata f0 4294967294 ; <MCInst #114 ATAri
; <MCOperand Reg:2>
; <MCOperand Reg:2>
; <MCOperand Imm:-2>>
krz f5+4@ f0 ; <MCInst #211 KRZmr
; <MCOperand Reg:6>
; <MCOperand Reg:0>
; <MCOperand Imm:4>
; <MCOperand Reg:2>>
inj f5@ xx pom ; <MCInst #195 INJ_FENXEOr
; <MCOperand Expr:(pom)>>
ata f5 8 ; <MCInst #114 ATAri
; <MCOperand Reg:6>
; <MCOperand Reg:6>
; <MCOperand Imm:8>>
krz f1 f5@ ; 4-byte Folded Reload
; <MCInst #213 KRZrm
; <MCOperand Reg:3>
; <MCOperand Reg:6>
; <MCOperand Reg:0>
; <MCOperand Imm:0>>
ata f0 f1 ; <MCInst #116 ATArr
; <MCOperand Reg:2>
; <MCOperand Reg:2>
; <MCOperand Reg:3>>
ata f5 4 l' BB0_2 ; %halt
; <MCInst #114 ATAri
; <MCOperand Reg:6>
; <MCOperand Reg:6>
; <MCOperand Imm:4>>
krz xx f5@ ; <MCInst #208 KRZ_DOSNUD>
; -- End function