Swiftで1+1が何故2になるのか調べてみた

TRILL開発部の石田です。

この記事は「dely #2 Advent Calendar 2020」2日目の記事です。

dely #1 Advent Calendar 2020 - Adventar

dely #2 Advent Calendar 2020 - Adventar

昨日はsacoさんの記事「ノンデザイナーでも大丈夫！見やすいプレゼン資料をつくる６つの手順」でした。デザイナーの視点から、分かりやすいプレゼンの作り方を順序立てて解説しているので是非ご覧ください。

さて、大学生のとき「1+1=2の証明」を授業で習ったのですが、小学生のとき当たり前のように教えられた自然数の足し算が大学の数学で証明され、数学の奥深さに触れた気がして今でも記憶に残っています。

そんなことを思い出して、普段書いているSwift内ではどうやって 1 + 1 が 2 であることを計算しているのか調べてみました。

Xcode上で、1 + 1 の加算演算子 + からCmd+Ctlで定義にジャンプしてみます。

f:id:trill_tech:20201106190539p:plain:w256

定義は以下のようになっています。

public protocol AdditiveArithmetic : Equatable {
  
  public static func + (lhs: Int, rhs: Int) -> Int

}

加算演算子 + は Equatable に準拠した AdditiveArithmetic というプロトコルの中で定義されています。しかしこれではインターフェースが分かっても実装が分かりません。実装を確認するため、GitHubに公開されているSwiftのソースコードを見にいきます。

上記の加算演算子コードは Integers.swift というファイルにありました。しかしこちらもインターフェースのみで実装がありません。

どうやら実際の実装はGitHub上では見ることができず、gybファイルからビルド時に生成されるようです。 gybは Generate Your Boilerplate の略で、Pythonで記述するテンプレートシステムです。該当のgybファイルは IntegerTypes.swift.gyb にあります。

このままでは実装が見られないので、ガイドに従ってSwiftのソースコードをビルドします。全部ビルドしなくても gyb.py を使って IntegerTypes.swift.gyb だけをSwiftファイルに変換することもできます。

ビルドすると IntegerTypes.swift というファイルが生成されます。加算演算子 + の実装を見てみます。

@_transparent
public static func +(lhs: Int, rhs: Int) -> Int {
  var lhs = lhs
  lhs += rhs
  return lhs
}

加算演算子 + は内部的に加算代入演算子 += を使っているようです。

加算代入演算子 += の実装を見てみます。

@_transparent
public static func +=(lhs: inout Int, rhs: Int) {
  let (result, overflow) = Builtin.sadd_with_overflow_Int64(lhs._value, rhs._value, true._value)
  Builtin.condfail_message(overflow, StaticString("arithmetic overflow").unsafeRawPointer)
  lhs = Int(result)
}

それらしいコードが出てきました。 Builtin.sadd_with_overflow_Int64() という関数が実際に加算をしているようです。

この関数を使って実際に加算ができるか試してみます。

import Swift

let a: Int = 1
let b: Int = 1
let c: Builtin.Int1 = Builtin.trunc_Int8_Int1(Int8(0)._value)

let (result, overflow) = Builtin.sadd_with_overflow_Int64(a._value, b._value, c)

print(Int(result))

実行するために多少面倒な定義をしています。 Builtin を使うため -parse-stdlib オプションを付けて実行します。

$ swift -parse-stdlib addition.swift
# 2

ちゃんと 2 が出力されました。

加算演算子 + が内部的に Builtin.sadd_with_overflow_Int64() という関数を使っていることが確認できました。しかし Builtin モジュールは組み込み関数にアクセスするものなので、これが内部で何を行っているのかが分かりません。

簡単なSwiftコードを作成し、それがLLVMの中間表現でどう書かれているかを見てみます。 LLVMはコンパイル基盤で、中間表現を経由しながら最適化を行い、最終的に機械語が生成されます。 1 + 1 だと分かりづらいので値を変えます。

let a = 1234
let b = 5678
let c = a + b

このコードを中間表現であるLLVM IRに変換します。

$ swiftc -emit-ir addition.swift

LLVM IRへの変換結果(抜粋)は以下のようになります。

...

store i64 1234, i64* getelementptr inbounds (%TSi, %TSi* @"$s8addition1aSivp", i32 0, i32 0), align 8
store i64 5678, i64* getelementptr inbounds (%TSi, %TSi* @"$s8addition1bSivp", i32 0, i32 0), align 8
%3 = load i64, i64* getelementptr inbounds (%TSi, %TSi* @"$s8addition1aSivp", i32 0, i32 0), align 8
%4 = load i64, i64* getelementptr inbounds (%TSi, %TSi* @"$s8addition1bSivp", i32 0, i32 0), align 8
%5 = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %3, i64 %4)

...

なんとなくですが、1234と5678をstoreし、loadし、加算する流れが分かります。この @llvm.sadd.with.overflow.i64 という命令がSwiftの Builtin.sadd_with_overflow_Int64() に相当するようです。

@llvm.sadd.with.overflow.i64 が加算していることは分かったのですが、実際にはどのように実行されているのでしょうか。

今度はSwiftをbitcodeに変換し、そこからアセンブリを出力します。

$ swiftc -emit-bc addition.swift > addition.bc
$ llc addition.bc

llc コマンドは brew install llvm でLLVMをインストールすることで使えるようになります。

アセンブリの抜粋は以下のようになります。

...

movq $1234, _$s8addition1aSivp(%rip) ## imm = 0x4D2
movq $5678, _$s8addition1bSivp(%rip) ## imm = 0x162E
movl $1234, %eax                     ## imm = 0x4D2
addq $5678, %rax                     ## imm = 0x162E

...