Swiftコンパイラの末尾再帰最適化について

print(even(100000))の実行結果

$ swift -O TailRec.swift 
true

$ swift TailRec.swift
[1]    35214 segmentation fault  swift TailRec.swift

swiftc -emit-ir -O TailRec.swift

; ModuleID = '-'
source_filename = "-"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.9"

%Vs5Int32 = type <{ i32 }>
%Sp = type <{ i8* }>
%swift.type = type { i64 }
%swift.protocol = type { i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i32, i32, i16, i16, i32 }
%objc_object = type opaque
%swift.bridge = type opaque

@_TZvOs11CommandLine5_argcVs5Int32 = external global %Vs5Int32, align 4
@globalinit_33_FD9A49A256BEB6AF7C48013347ADC3BA_token4 = external global i64, align 8
@_TZvOs11CommandLine11_unsafeArgvGSpGSqGSpVs4Int8___ = external global %Sp, align 8
@_TMLGCs23_ContiguousArrayStorageP__ = linkonce_odr hidden global %swift.type* null, align 8
@_TMLP_ = linkonce_odr hidden global %swift.type* null, align 8
@_swift_getExistentialTypeMetadata = external global %swift.type* (i64, %swift.protocol**)*
@_TMSb = external global %swift.type, align 8
@__swift_reflection_version = linkonce_odr hidden constant i16 1
@llvm.used = appending global [1 x i8*] [i8* bitcast (i16* @__swift_reflection_version to i8*)], section "llvm.metadata"

define i32 @main(i32, i8**) #0 {
entry:
  %protocols.i.i = alloca [0 x %swift.protocol*], align 8
  store i32 %0, i32* getelementptr inbounds (%Vs5Int32, %Vs5Int32* @_TZvOs11CommandLine5_argcVs5Int32, i64 0, i32 0), align 4
  %2 = load i64, i64* @globalinit_33_FD9A49A256BEB6AF7C48013347ADC3BA_token4, align 8
  %3 = icmp eq i64 %2, -1
  br i1 %3, label %once_done, label %once_not_done

once_not_done:                                    ; preds = %entry
  tail call void @swift_once(i64* nonnull @globalinit_33_FD9A49A256BEB6AF7C48013347ADC3BA_token4, i8* nonnull bitcast (void ()* @globalinit_33_FD9A49A256BEB6AF7C48013347ADC3BA_func4 to i8*))
  br label %once_done

once_done:                                        ; preds = %once_not_done, %entry
  store i8** %1, i8*** bitcast (%Sp* @_TZvOs11CommandLine11_unsafeArgvGSpGSqGSpVs4Int8___ to i8***), align 8
  %4 = load %swift.type*, %swift.type** @_TMLGCs23_ContiguousArrayStorageP__, align 8
  %5 = icmp eq %swift.type* %4, null
  br i1 %5, label %cacheIsNull.i, label %_TMaGCs23_ContiguousArrayStorageP__.exit

cacheIsNull.i:                                    ; preds = %once_done
  %6 = load %swift.type*, %swift.type** @_TMLP_, align 8
  %7 = icmp eq %swift.type* %6, null
  br i1 %7, label %cacheIsNull.i.i, label %_TMaP_.exit.i

cacheIsNull.i.i:                                  ; preds = %cacheIsNull.i
  %8 = bitcast [0 x %swift.protocol*]* %protocols.i.i to i8*
  call void @llvm.lifetime.start(i64 0, i8* %8) #7
  %9 = getelementptr inbounds [0 x %swift.protocol*], [0 x %swift.protocol*]* %protocols.i.i, i64 0, i64 0
  %10 = call %swift.type* @rt_swift_getExistentialTypeMetadata(i64 0, %swift.protocol** %9) #7
  call void @llvm.lifetime.end(i64 0, i8* %8) #7
  store atomic %swift.type* %10, %swift.type** @_TMLP_ release, align 8
  br label %_TMaP_.exit.i

_TMaP_.exit.i:                                    ; preds = %cacheIsNull.i.i, %cacheIsNull.i
  %11 = phi %swift.type* [ %6, %cacheIsNull.i ], [ %10, %cacheIsNull.i.i ]
  %12 = call %swift.type* @_TMaCs23_ContiguousArrayStorage(%swift.type* %11) #5
  store atomic %swift.type* %12, %swift.type** @_TMLGCs23_ContiguousArrayStorageP__ release, align 8
  br label %_TMaGCs23_ContiguousArrayStorageP__.exit

_TMaGCs23_ContiguousArrayStorageP__.exit:         ; preds = %once_done, %_TMaP_.exit.i
  %13 = phi %swift.type* [ %4, %once_done ], [ %12, %_TMaP_.exit.i ]
  %14 = call %objc_object* @swift_bufferAllocate(%swift.type* %13, i64 64, i64 7)
  %15 = bitcast %objc_object* %14 to i8*
  %16 = getelementptr inbounds i8, i8* %15, i64 16
  %17 = bitcast i8* %16 to <2 x i64>*
  store <2 x i64> <i64 1, i64 2>, <2 x i64>* %17, align 8
  %18 = bitcast %objc_object* %14 to %swift.bridge*
  %19 = getelementptr inbounds i8, i8* %15, i64 32
  %20 = getelementptr inbounds i8, i8* %15, i64 56
  %21 = bitcast i8* %20 to %swift.type**
  store %swift.type* @_TMSb, %swift.type** %21, align 8
  br label %.lr.ph.i

.lr.ph.i:                                         ; preds = %tailrecurse.i, %_TMaGCs23_ContiguousArrayStorageP__.exit
  %.tr1.i = phi i64 [ %30, %tailrecurse.i ], [ 999999, %_TMaGCs23_ContiguousArrayStorageP__.exit ]
  %22 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %.tr1.i, i64 1) #7
  %23 = extractvalue { i64, i1 } %22, 0
  %24 = extractvalue { i64, i1 } %22, 1
  br i1 %24, label %32, label %25

; <label>:25                                      ; preds = %.lr.ph.i
  %26 = icmp eq i64 %23, 0
  br i1 %26, label %_TF7TailRec3oddFSuSb.exit, label %27

; <label>:27                                      ; preds = %25
  %28 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %23, i64 1) #7
  %29 = extractvalue { i64, i1 } %28, 1
  br i1 %29, label %33, label %tailrecurse.i

tailrecurse.i:                                    ; preds = %27
  %30 = extractvalue { i64, i1 } %28, 0
  %31 = icmp eq i64 %30, 0
  br i1 %31, label %_TF7TailRec3oddFSuSb.exit, label %.lr.ph.i

; <label>:32                                      ; preds = %.lr.ph.i
  call void asm sideeffect "", "n"(i32 0) #7
  call void @llvm.trap() #7
  unreachable

; <label>:33                                      ; preds = %27
  call void asm sideeffect "", "n"(i32 1) #7
  call void @llvm.trap() #7
  unreachable

_TF7TailRec3oddFSuSb.exit:                        ; preds = %25, %tailrecurse.i
  %34 = phi i1 [ true, %25 ], [ false, %tailrecurse.i ]
  %object._value = bitcast i8* %19 to i1*
  store i1 %34, i1* %object._value, align 8
  %35 = call { i64, i64, i64 } @_TIFs5printFTGSaP__9separatorSS10terminatorSS_T_A0_()
  %36 = extractvalue { i64, i64, i64 } %35, 0
  %37 = extractvalue { i64, i64, i64 } %35, 1
  %38 = extractvalue { i64, i64, i64 } %35, 2
  %39 = call { i64, i64, i64 } @_TIFs5printFTGSaP__9separatorSS10terminatorSS_T_A1_()
  %40 = extractvalue { i64, i64, i64 } %39, 0
  %41 = extractvalue { i64, i64, i64 } %39, 1
  %42 = extractvalue { i64, i64, i64 } %39, 2
  call void @_TFs5printFTGSaP__9separatorSS10terminatorSS_T_(%swift.bridge* %18, i64 %36, i64 %37, i64 %38, i64 %40, i64 %41, i64 %42)
  ret i32 0
}

; Function Attrs: nounwind
define hidden i1 @_TF7TailRec3oddFSuSb(i64) #1 {
entry:
  %1 = icmp eq i64 %0, 0
  br i1 %1, label %._crit_edge, label %.lr.ph.preheader

.lr.ph.preheader:                                 ; preds = %entry
  br label %.lr.ph

.lr.ph:                                           ; preds = %.lr.ph.preheader, %tailrecurse
  %.tr1 = phi i64 [ %10, %tailrecurse ], [ %0, %.lr.ph.preheader ]
  %2 = tail call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %.tr1, i64 1)
  %3 = extractvalue { i64, i1 } %2, 0
  %4 = extractvalue { i64, i1 } %2, 1
  br i1 %4, label %13, label %5

; <label>:5                                       ; preds = %.lr.ph
  %6 = icmp eq i64 %3, 0
  br i1 %6, label %._crit_edge.loopexit, label %7

; <label>:7                                       ; preds = %5
  %8 = tail call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %3, i64 1)
  %9 = extractvalue { i64, i1 } %8, 1
  br i1 %9, label %14, label %tailrecurse

tailrecurse:                                      ; preds = %7
  %10 = extractvalue { i64, i1 } %8, 0
  %11 = icmp eq i64 %10, 0
  br i1 %11, label %._crit_edge.loopexit, label %.lr.ph

._crit_edge.loopexit:                             ; preds = %5, %tailrecurse
  %.ph = phi i1 [ true, %5 ], [ false, %tailrecurse ]
  br label %._crit_edge

._crit_edge:                                      ; preds = %._crit_edge.loopexit, %entry
  %12 = phi i1 [ false, %entry ], [ %.ph, %._crit_edge.loopexit ]
  ret i1 %12

; <label>:13                                      ; preds = %.lr.ph
  tail call void asm sideeffect "", "n"(i32 0) #7
  tail call void @llvm.trap()
  unreachable

; <label>:14                                      ; preds = %7
  tail call void asm sideeffect "", "n"(i32 1) #7
  tail call void @llvm.trap()
  unreachable
}

; Function Attrs: nounwind
define hidden i1 @_TF7TailRec4evenFSuSb(i64) #1 {
entry:
  %1 = icmp eq i64 %0, 0
  br i1 %1, label %_TF7TailRec3oddFSuSb.exit, label %2

; <label>:2                                       ; preds = %entry
  %3 = tail call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %0, i64 1)
  %4 = extractvalue { i64, i1 } %3, 1
  br i1 %4, label %21, label %5

; <label>:5                                       ; preds = %2
  %6 = extractvalue { i64, i1 } %3, 0
  %7 = icmp eq i64 %6, 0
  br i1 %7, label %_TF7TailRec3oddFSuSb.exit, label %.lr.ph.i.preheader

.lr.ph.i.preheader:                               ; preds = %5
  br label %.lr.ph.i

.lr.ph.i:                                         ; preds = %.lr.ph.i.preheader, %tailrecurse.i
  %.tr1.i = phi i64 [ %16, %tailrecurse.i ], [ %6, %.lr.ph.i.preheader ]
  %8 = tail call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %.tr1.i, i64 1) #7
  %9 = extractvalue { i64, i1 } %8, 0
  %10 = extractvalue { i64, i1 } %8, 1
  br i1 %10, label %18, label %11

; <label>:11                                      ; preds = %.lr.ph.i
  %12 = icmp eq i64 %9, 0
  br i1 %12, label %_TF7TailRec3oddFSuSb.exit.loopexit, label %13

; <label>:13                                      ; preds = %11
  %14 = tail call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %9, i64 1) #7
  %15 = extractvalue { i64, i1 } %14, 1
  br i1 %15, label %19, label %tailrecurse.i

tailrecurse.i:                                    ; preds = %13
  %16 = extractvalue { i64, i1 } %14, 0
  %17 = icmp eq i64 %16, 0
  br i1 %17, label %_TF7TailRec3oddFSuSb.exit.loopexit, label %.lr.ph.i

; <label>:18                                      ; preds = %.lr.ph.i
  tail call void asm sideeffect "", "n"(i32 0) #7
  tail call void @llvm.trap() #7
  unreachable

; <label>:19                                      ; preds = %13
  tail call void asm sideeffect "", "n"(i32 1) #7
  tail call void @llvm.trap() #7
  unreachable

_TF7TailRec3oddFSuSb.exit.loopexit:               ; preds = %11, %tailrecurse.i
  %.ph = phi i1 [ false, %tailrecurse.i ], [ true, %11 ]
  br label %_TF7TailRec3oddFSuSb.exit

_TF7TailRec3oddFSuSb.exit:                        ; preds = %_TF7TailRec3oddFSuSb.exit.loopexit, %5, %entry
  %20 = phi i1 [ true, %entry ], [ false, %5 ], [ %.ph, %_TF7TailRec3oddFSuSb.exit.loopexit ]
  ret i1 %20

; <label>:21                                      ; preds = %2
  tail call void asm sideeffect "", "n"(i32 0) #7
  tail call void @llvm.trap()
  unreachable
}

declare void @globalinit_33_FD9A49A256BEB6AF7C48013347ADC3BA_func4() #0

declare void @swift_once(i64*, i8*)

; Function Attrs: argmemonly nounwind
declare void @llvm.lifetime.start(i64, i8* nocapture) #2

; Function Attrs: noinline nounwind
define linkonce_odr hidden %swift.type* @rt_swift_getExistentialTypeMetadata(i64, %swift.protocol**) #3 {
entry:
  %load = load %swift.type* (i64, %swift.protocol**)*, %swift.type* (i64, %swift.protocol**)** @_swift_getExistentialTypeMetadata, align 8
  %2 = tail call %swift.type* %load(i64 %0, %swift.protocol** %1) #7
  ret %swift.type* %2
}

; Function Attrs: argmemonly nounwind
declare void @llvm.lifetime.end(i64, i8* nocapture) #2

declare %swift.type* @_TMaCs23_ContiguousArrayStorage(%swift.type*) #0

; Function Attrs: noreturn nounwind
declare void @llvm.trap() #4

; Function Attrs: nounwind readnone
declare { i64, i1 } @llvm.usub.with.overflow.i64(i64, i64) #5

; Function Attrs: noinline
declare void @_TFs5printFTGSaP__9separatorSS10terminatorSS_T_(%swift.bridge*, i64, i64, i64, i64, i64, i64) #6

declare %objc_object* @swift_bufferAllocate(%swift.type*, i64, i64) #0

; Function Attrs: noinline
declare { i64, i64, i64 } @_TIFs5printFTGSaP__9separatorSS10terminatorSS_T_A0_() #6

; Function Attrs: noinline
declare { i64, i64, i64 } @_TIFs5printFTGSaP__9separatorSS10terminatorSS_T_A1_() #6

attributes #0 = { "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "target-cpu"="core2" "target-features"="+ssse3,+cx16,+fxsr,+mmx,+sse,+sse2,+sse3" }
attributes #1 = { nounwind "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "target-cpu"="core2" "target-features"="+ssse3,+cx16,+fxsr,+mmx,+sse,+sse2,+sse3" }
attributes #2 = { argmemonly nounwind }
attributes #3 = { noinline nounwind }
attributes #4 = { noreturn nounwind }
attributes #5 = { nounwind readnone }
attributes #6 = { noinline "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "target-cpu"="core2" "target-features"="+ssse3,+cx16,+fxsr,+mmx,+sse,+sse2,+sse3" }
attributes #7 = { nounwind }

!llvm.module.flags = !{!0, !1, !2, !3, !4, !5, !9, !10}

!0 = !{i32 1, !"Objective-C Version", i32 2}
!1 = !{i32 1, !"Objective-C Image Info Version", i32 0}
!2 = !{i32 1, !"Objective-C Image Info Section", !"__DATA, __objc_imageinfo, regular, no_dead_strip"}
!3 = !{i32 4, !"Objective-C Garbage Collection", i32 1024}
!4 = !{i32 1, !"Objective-C Class Properties", i32 64}
!5 = !{i32 6, !"Linker Options", !6}
!6 = !{!7, !8}
!7 = !{!"-lswiftCore"}
!8 = !{!"-lobjc"}
!9 = !{i32 1, !"PIC Level", i32 2}
!10 = !{i32 1, !"Swift Version", i32 4}

TailRec.swift

func odd(_ n: UInt) -> Bool {
    if n == 0 {
        return false
    }
    else {
        return even(n - 1)
    }
}

func even(_ n: UInt) -> Bool {
    if n == 0 {
        return true
    }
    else {
        return odd(n - 1)
    }
}