Scheme Compiler の勉強(24) - 比較
※適当な粒度で書いていたら 24 回にもなってしまった。元の文書だと全部で２４ステップなのに。
コンパイラ自体は単純だけど、それが吐き出す結果は十分ややこしい。procedure の定義までできるようになったので、結果をよく眺めてみることにする。また、いまの直接命令を出力する単純なプログラムを、すこし奇麗にしたい。このあとは Iteration via Proper Tail Calls と Heap Allocation で、ちょっと立ち止まって準備しないとできる気がしない。
fib
まずフィボナッチ数列で。
(letrec ((fib (lambda (n) (if (fx< n 2) 1 (fx+ (fib (fx- n 2)) (fib (fx- n 1))))))) (fib 9)) => 55
これをそのままコンパイルして LLVM IR にする。一行ずつ追って見よう、と思ったけどあまりに面倒なので、 compiler の方で適当にコメントを出力することにした。何の最適化もしていないのでとても冗長。
; emit-letrec: (letrec ((fib (lambda (n) (if (fx< n 2) 1 (fx+ (fib (fx- n 2)) (fib (fx- n 1))))))) (fib 9))
define i32 @Label_1(i32 %arg1) nounwind {
entry:
%ret = alloca i32
%sta1 = alloca i32
store i32 %arg1, i32* %sta1
; emit-if (if (fx< n 2) 1 (fx+ (fib (fx- n 2)) (fib (fx- n 1))))
; emit-if-test
; fx<:
; eval and store arg1
%var9 = load i32* %sta1
store i32 %var9, i32* %ret
%sta2 = alloca i32
%var3 = load i32* %ret
store i32 %var3, i32* %sta2
; eval and store arg2
store i32 8, i32* %ret
%sta3 = alloca i32
%var4 = load i32* %ret
store i32 %var4, i32* %sta3
%var5 = load i32* %sta2
%var6 = load i32* %sta3
; icmp with 'slt
%var7 = icmp slt i32 %var5, %var6
%var8 = select i1 %var7, i32 111, i32 47
store i32 %var8, i32* %ret
%var1 = load i32* %ret
; compare %ret to #f
%var2 = icmp eq i32 %var1, 47
br i1 %var2, label %Label_3, label %Label_2
Label_2:
store i32 4, i32* %ret
br label %Label_4
Label_3:
; fx+
; eval and store arg1
; fx-
; eval and store arg1
%var22 = load i32* %sta1
store i32 %var22, i32* %ret
%sta6 = alloca i32
%var17 = load i32* %ret
store i32 %var17, i32* %sta6
; eval and store arg2
store i32 8, i32* %ret
%sta7 = alloca i32
%var18 = load i32* %ret
store i32 %var18, i32* %sta7
%var19 = load i32* %sta6
%var20 = load i32* %sta7
; sub arg1 arg2
%var21 = sub i32 %var19, %var20
store i32 %var21, i32* %ret
%var16 = load i32* %ret
%var15 = call i32 @Label_1(i32 %var16)
store i32 %var15, i32* %ret
%sta4 = alloca i32
%var10 = load i32* %ret
store i32 %var10, i32* %sta4
; eval and store arg1
; fx-
; eval and store arg1
%var30 = load i32* %sta1
store i32 %var30, i32* %ret
%sta8 = alloca i32
%var25 = load i32* %ret
store i32 %var25, i32* %sta8
; eval and store arg2
store i32 4, i32* %ret
%sta9 = alloca i32
%var26 = load i32* %ret
store i32 %var26, i32* %sta9
%var27 = load i32* %sta8
%var28 = load i32* %sta9
; sub arg1 arg2
%var29 = sub i32 %var27, %var28
store i32 %var29, i32* %ret
%var24 = load i32* %ret
%var23 = call i32 @Label_1(i32 %var24)
store i32 %var23, i32* %ret
%sta5 = alloca i32
%var11 = load i32* %ret
store i32 %var11, i32* %sta5
%var12 = load i32* %sta4
%var13 = load i32* %sta5
; add arg1 arg2
%var14 = add i32 %var12, %var13
store i32 %var14, i32* %ret
br label %Label_4
Label_4:
%retval = load i32* %ret
ret i32 %retval
}
define i32 @scheme_entry() nounwind {
entry:
%ret = alloca i32
store i32 36, i32* %ret
%var32 = load i32* %ret
%var31 = call i32 @Label_1(i32 %var32)
store i32 %var31, i32* %ret
%retval = load i32* %ret
ret i32 %retval
}LLVM の opt コマンドで最適化すると、以下のようになる。最適化するとコメントが消されるので、再度手で付加した。
; ModuleID = 'stst.opt.bc'
define i32 @Label_1(i32 %arg1) nounwind { ;; fib 本体
entry:
%var7 = icmp slt i32 %arg1, 8 ;; (if (< n 2)
br i1 %var7, label %UnifiedReturnBlock, label %Label_3 ;; jump
Label_3: ;
%var21 = add i32 %arg1, -8 ; var21 = n - 2
%var15 = call i32 @Label_1( i32 %var21 ) ; var15 = (fib var21) = (fib (- n 2))
%var29 = add i32 %arg1, -4 ; var29 = n - 1
%var23 = call i32 @Label_1( i32 %var29 ) ; var23 = (fib var29) = (fib (- n 1))
%var14 = add i32 %var23, %var15 ; <i32> [#uses=1] ; var14 = (+ var23 var15)
ret i32 %var14
UnifiedReturnBlock: ;
ret i32 4 ; return 1
}
define i32 @scheme_entry() nounwind {
entry:
%var15.i = tail call i32 @Label_1( i32 28 ) nounwind ; var15.i = (fib 7)
%var23.i = tail call i32 @Label_1( i32 32 ) nounwind ; var23.i = (fib 8)
%var14.i = add i32 %var23.i, %var15.i ; var14.i = (+ (fib 7) (fib 8))
ret i32 %var14.i
}
- fib の本体はほとんど scheme での関数の定義そのものになった。
- 呼び出し側(scheme_entry) では (fib 9) が (+ (fib 7) (fib 8)) になった。比較演算を減らすため？また call が tail call になった(あとで調べる)。
PowerPC 用にはこうなる。うーん、"32ビットPowerPCアーキテクチャ プログラミング環境"を一行一行しらべないと。
.machine ppc7400 .section __TEXT,__textcoal_nt,coalesced,pure_instructions .section __TEXT,__symbol_stub1,symbol_stubs,pure_instructions,16 .text .globl _Label_1 .align 4 _Label_1: mflr r0 stw r0, 8(r1) stwu r1, -64(r1) stw r29, 60(r1) stw r30, 56(r1) cmpwi cr0, r3, 8 mr r30, r3 blt cr0, LBB1_2 ; UnifiedReturnBlock LBB1_1: ; Label_3 addi r3, r30, -8 bl _Label_1 mr r29, r3 addi r3, r30, -4 bl _Label_1 add r3, r3, r29 lwz r30, 56(r1) lwz r29, 60(r1) addi r1, r1, 64 lwz r0, 8(r1) mtlr r0 blr LBB1_2: ; UnifiedReturnBlock li r3, 4 lwz r30, 56(r1) lwz r29, 60(r1) addi r1, r1, 64 lwz r0, 8(r1) mtlr r0 blr .globl _scheme_entry .align 4 _scheme_entry: mflr r0 stw r0, 8(r1) stwu r1, -64(r1) stw r30, 60(r1) li r3, 28 bl _Label_1 mr r30, r3 li r3, 32 bl _Label_1 add r3, r3, r30 lwz r30, 60(r1) addi r1, r1, 64 lwz r0, 8(r1) mtlr r0 blr .subsections_via_symbols
llc コマンドに -march=x86 を与えるとこうなる。少しだけみやすい？
※現在 www.intel.com にアクセスできないのでインストラクションセットが入手できない‥
.text .align 4,0x90 .globl _Label_1 _Label_1: pushl %edi pushl %esi subl $4, %esp movl 16(%esp), %esi cmpl $8, %esi jge LBB1_3 ## Label_3 LBB1_1: ## UnifiedReturnBlock movl $4, %eax LBB1_2: ## UnifiedReturnBlock addl $4, %esp popl %esi popl %edi ret LBB1_3: ## Label_3 leal -8(%esi), %eax movl %eax, (%esp) call _Label_1 movl %eax, %edi addl $4294967292, %esi movl %esi, (%esp) call _Label_1 addl %edi, %eax jmp LBB1_2 ## UnifiedReturnBlock .align 4,0x90 .globl _scheme_entry _scheme_entry: pushl %esi subl $8, %esp movl $28, (%esp) call _Label_1 movl %eax, %esi movl $32, (%esp) call _Label_1 addl %esi, %eax addl $8, %esp popl %esi ret .subsections_via_symbols
