[WIP] rustcが生成するコードの調査

本記事では，rustcが生成するコードについての調査を行っています．

記事は随時更新されます．

最初の記事を書いた時点で，Rust Playgroundで使用されていたrustcのバージョンは以下の通りです．

* Stable: 1.29.2
* Beta: 1.30.0-beta.15 (590121930fc942315c84)
* Nightly: 1.31.0-nightly (14f42a732ff9562fb5f0)

# String::from()

[Rust Playground](https://play.rust-lang.org/?version=stable&mode=release&edition=2015&code=fn%20main()%20%7B%0A%20%20%20%20let%20s%20%3D%20String%3A%3Afrom(%22world!%22)%3B%0A%20%20%20%20println!(%22Hello%2C%20%7B%7D%22%2C%20s)%3B%0A%7D%0A)

```rust:rust
fn main() {
    let s = String::from("world!");
    println!("Hello, {}", s);
}
```

`String`オブジェクトは，ヒープではなくスタック上に確保されます．文字列を格納するための領域は，ヒープから割り当てられます．

```llvm:llvm-ir
  %s = alloca %"alloc::string::String", align 8
  ...
  call void @"_ZN87_$LT$alloc..string..String$u20$as$u20$core..convert..From$LT$$RF$$u27$a$u20$str$GT$$GT$4from17h0e73539cabf31215E"(%"alloc::string::String"* noalias nocapture nonnull sret dereferenceable(24) %s, [0 x i8]* noalias nonnull readonly bitcast (<{ [6 x i8] }>* @byte_str.1 to [0 x i8]*), i64 6)
```
## Mutability

記事の趣旨からは外れてしまいますが，変数のミュータビリティについて言及しておきます．

一般に，ある変数についてimmutableであると言った場合，以下の２つのどちらか，または両方を意味する可能性があります．

1. 変数には１度しかオブジェクトをバインドできない（C/C++の`char* const`に相当）
2. 変数にバインドされたオブジェクトを書き換えることができない（C/C++の`const char*`に相当）

例えば先程の例で考えると，以下の文は

```rust
let s = String::from("world!");
```

* `s`には一度しかオブジェクトをバインドできない
* `s`にバインドされる`String`オブジェクトを書き換えることができない

ということを意味します．そのため，後者の制約のみが必要な場合は，`let`で`s`を再定義する必要があります（別の型のオブジェクトを使用している場合は，再定義が不要な場合があるかもしれません）．

```rust
let s = String::from("foo");
// s("foo")に対する処理を実行

let s = String::from("bar");  // sを再定義（ループ内の処理などでこのように書くことが多いと思います）
```

ただ，Rustの変数のmutabilityを，スタック上に確保されたオブジェクト（メモリ領域）に関するものだと解釈すべきではないと考えます．そのように解釈することでも

```rust
let s = String::from("world");  // スタック上に`String`オブジェクトを配置し，それはimmutable
s.push('!');  // 長さに関するフィールドがスタック上に存在するが，その領域は書き換えられない
```

がコンパイルエラーとなることを理解することが可能です．しかし，例えば`String::from()`が「`String`オブジェクトをヒープ上に配置し，そのアドレスをスタック上に確保されたバインド先変数のためのメモリ領域に書き込む」という実装になっていたとすると，上記のように解釈することができなくなります．

そのため，`push()`が以下のように定義されているためコンパイルエラーになると解釈すべきです．

```rust
pub fn push(&mut self, ch: char) {}  // selfの型は&mut String
```

型に対する制約は，その型のオブジェクトがどのように実装されているのか（今の例だと，`String`オブジェクトがスタック上に確保されるのか，ヒープ上に確保されそのアドレスのみがスタック上の変数に保存されるのか，など）などの詳細に関わらない抽象的な概念であり，Rustにおけるmutabilityとは型に対する制約を意味していると考えるべきです．

ちなみに，[TRPL First Edition](https://doc.rust-lang.org/book/first-edition/mutability.html#interior-vs-exterior-mutability)には上記に関連する記述が３章で出てきますが，新しいTRPLでは「exterior mutability」に関する記述はなくなっています（「interior mutability」は１５章で出てきます）．削除した理由は不明ですが（GitHubの履歴を見れば確認できそうですが），重要な概念なので３章で説明しておいたほうが良いような気がします．

# `String`オブジェクトの所有権の移動

[Rust Playground](https://play.rust-lang.org/?version=stable&mode=release&edition=2015&code=fn%20main()%20%7B%0A%20%20%20%20let%20s1%20%3D%20String%3A%3Afrom(%22world!%22)%3B%0A%20%20%20%20hello(s1)%3B%0A%7D%0A%0Afn%20hello(s%3A%20String)%20%7B%0A%20%20%20%20println!(%22Hello%2C%20%7B%7D%22%2C%20s)%3B%0A%7D)

```rust:rust
fn main() {
    let s1 = String::from("world!");
    hello(s1);
}

fn hello(s: String) {
    println!("hello, {}", s);
}
```

所有権が移動し，`hello(s1)`以降に`s1`を使用するとコンパイルエラーとなります．そのため，`s`と`s1`はスタック上の同一`String`オブジェクトを使用するような最適化が行われることを期待していたのですが，実際は`hello()`呼び出し前にコピーが発生します．

```llvm:llvm-ir
  %_3 = alloca %"alloc::string::String", align 8
  %s1 = alloca %"alloc::string::String", align 8
  %0 = bitcast %"alloc::string::String"* %s1 to i8*
  ...
  %1 = bitcast %"alloc::string::String"* %_3 to i8*
  call void @llvm.lifetime.start.p0i8(i64 24, i8* nonnull %1)
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 %1, i8* nonnull align 8 %0, i64 24, i1 false)
```

アセンブリコードでもコピーが確認できます．

```:asm
playground::main:
	pushq	%rbx
	subq	$112, %rsp
	leaq	.Lbyte_str.1(%rip), %rsi
	leaq	88(%rsp), %rdi
	movl	$6, %edx
	callq	<alloc::string::String as core::convert::From<&'a str>>::from@PLT
	movq	104(%rsp), %rax
	movq	%rax, 16(%rsp)
	movups	88(%rsp), %xmm0
	movaps	%xmm0, (%rsp)
```

Nightly Versionでコンパイルすると，`String`オブジェクトをコピーするコードがなくなるので，改善されたのかもしれません．

# `String`オブジェクの借用

[Rust Playground](https://play.rust-lang.org/?version=stable&mode=release&edition=2015&code=fn%20main()%20%7B%0A%20%20%20%20let%20s1%20%3D%20String%3A%3Afrom(%22world!%22)%3B%0A%20%20%20%20hello(%26s1)%3B%0A%7D%0A%0Afn%20hello(s%3A%20%26String)%20%7B%0A%20%20%20%20println!(%22Hello%2C%20%7B%7D%22%2C%20s)%3B%0A%7D)

```rust:rust
fn main() {
    let s1 = String::from("world!");
    hello(&s1);
}

fn hello(s: &String) {
    println!("Hello, {}", s);
}
```

`String`オブジェクトを借用するように変更すると，コピーしなくなります．

```llvm:llvm-ir
  %s1 = alloca %"alloc::string::String", align 8
  %0 = bitcast %"alloc::string::String"* %s1 to i8*
  ...
```

所有権が移動する場合に存在した`%_3`や`llvm.memcpy`はなくなっています．

`fmt()`の引数の型が`%"alloc::string::String"**`になっている点が気になります．所有権が移動する場合は`%"alloc::string::String"*`でした．

`%"alloc::string::String"**`となっているため，所有権が移動する場合のコードと比べて，アドレス参照が１回増えます．

```:asm
<&'a T as core::fmt::Display>::fmt:
	movq	%rsi, %rax
	movq	(%rdi), %rcx
	movq	(%rcx), %rdi
	movq	16(%rcx), %rsi
	movq	%rax, %rdx
	jmp	<str as core::fmt::Display>::fmt@PLT
```

LLVM IRのデバッグビルドの`hello()`を確認しましたが，引数の型は予想通り`%"alloc::string::String"*`となっていました．しかし，直接引数を使用するのではなく，スタック上に`%"alloc::string::String"*`を格納するための領域を確保し値をコピーしています．

```llvm:llvm-ir-debug
; playground::hello
; Function Attrs: uwtable
define internal void @_ZN10playground5hello17hb8df0bc2cde9eedcE(%"alloc::string::String"* noalias readonly dereferenceable(24)) unnamed_addr #0 !dbg !749 {
start:
  %arg0 = alloca %"alloc::string::String"**, align 8
  %_11 = alloca i64*, align 8
  %_10 = alloca [1 x { i8*, i8* }], align 8
  %_3 = alloca %"core::fmt::Arguments", align 8
  %s = alloca %"alloc::string::String"*, align 8
  store %"alloc::string::String"* %0, %"alloc::string::String"** %s, align 8
```

~~わざわざこのようにする理由が私には思いつきません．もし理由が分かる人がいたら教えてください．~~ @lo48576さんに教えていただきました．`println!()`は出力対象オブジェクトを借用するため，`&&String`となるためです．

# `Array` and `Vec`

Rustでプログラムを書いている方は知っていることだと思われますが，`Array`はスタック上に（もしくはtextまたはdataセクション），`Vec`はヒープ上に要素を配置します．

C++の`std::vector`は，要素をスタック上に配置するようにコンパイルされる場合があるようですが，`Vec`は必ずヒープ上に要素を配置します．

[Rust Playground](https://play.rust-lang.org/?version=stable&mode=release&edition=2015&code=fn%20main()%20%7B%0A%20%20%20%20let%20v%20%3D%20vec!%5B1%2C%202%2C%203%2C%204%5D%3B%0A%20%20%20%20for%20i%20in%20v%20%7B%0A%20%20%20%20%20%20%20%20println!(%22%7B%7D%22%2C%20i)%3B%0A%20%20%20%20%7D%0A%7D%0A)

```rust:rust
fn main() {
    let v = vec![1, 2, 3, 4];
    for i in v {
        println!("{}", i);
    }
}
```

```:asm
playground::main:
        ...
        callq __rust_alloc@PLT
        ...
```

rustc内には明確な基準が存在するのだと思いますが，ブロック内の文（または式）が少なく，要素数も小さい場合は，ループを展開するようです．定数テーブルも作成されているようなので，もうここまでやったら`__rust_alloc`も消せるんじゃないかと思ってしまうのですが，多分私が気付いていないだけで消せない理由があるのでしょう．

余談ですが，`String`は`Vec<i8>`で実装されているので，文字列は必ずヒープ上に配置されます．C++の`std::string`は`std::vector`と同様に小さい文字列はスタック上に配置しますが，`String`ではそのようなことは起こりません．ヒープに配置したくない場合は，スライスを使う必要があります．

# `Box`とトレイトオブジェクト

あるトレイトを実装する型のオブジェクトを`Box::new()`でヒープ上に確保し，`Box<型>`の変数に束縛することを考えます．

```rust:rust
trait Shape {}
struct Rectangle { width: u32, height: u32 }
impl Shape for Rectangle {}

let rect = Box::new(Rectangle::new(10, 10));
```

変数`rect`は`Box<Rectangle>`型で，コンパイル後はポインターとなります．

```llvm:llvm-ir
; 簡単なコードだと最適化で消えてしまうので，デバッグビルドで確認してください
  %rect = alloca { i32, i32 }*, align 8
```

では，以下のように`Box<トレイト>`の変数に束縛した場合はどうなると思いますか？

```rust:rust
trait Shape {}
struct Rectangle { width: u32, height: u32 }
impl Shape for Rectangle {}

let shape: Box<Shape> = Box::new(Rectangle::new(10, 10));
```

素直に考えるとトレイトオブジェクトへのポインターになりそうですが，トレイトオブジェクトそのものになります．

```llvm:llvm-ir
  %shape = alloca { {}*, [3 x i64]* }, align 8
```

リリースビルドでも同じ結果になります．Nightlyでも同じでした．

１つのポインターにコンパイルされることを期待して`Box<トレイト>`型を使っている場合，以下の点に注意が必要です．

* データサイズが予想よりポインター１つ分だけ大きくなっている
* アドレス参照回数が予想より１回少なくなっている

どうせサイズが増えるなら，`enum`を使ったタグ付きポインターにしてしまったほうが良いケースはあるでしょう．

```rust:rust
enum Geometry {
    Triangle(Box<Triangle>),
    Rectangle(Box<Rectangle>),
    ...
}

let geom = Geometry::Rectangle(Box::new(Rectangle::new(10, 10)));
```

```llvm:llvm-ir
  %geom = alloca { i64, i8* }, align 8
```

インターフェースを綺麗に抽出可能な場合は`Box<トレイト>`で，ダウンキャストを多用するケース（このような場合はそもそも妥当なトレイトは存在しないでしょうが）はタグ付きポインターを使うのがよいでしょう．

# オブジェクトのコピー

Rustでは，一見最適化で除去できそうなオブジェクトのコピーが行われるケースがいくつか存在するようです．

## `Box::new()`とオブジェクトの初期化

関連サイト

* [cargo asmでRustのメモリ周り最適化をチェック | κeenのHappy Hacκing Blog](https://keens.github.io/blog/2018/04/04/cargo_asmderustnomemorimawarisaitekikawochekku/)

以下のようなオブジェクトを`Box::new()`でヒープ上に確保した場合，

```rust:rust
struct X {
    x: i32,
}

fn main() {
    let data = Box::new(X { x: 112 });
    println!("{}", data.x);
}
```

`__rust_alloc`後にオブジェクトの初期化が行われます．

```llvm:llvm-ir
  %0 = tail call i8* @__rust_alloc(i64 4, i64 4) #7
  ...
  %2 = bitcast i8* %0 to i32*
  store i32 112, i32* %2, align 4
```

タプルも同様の結果になります．

しかし，配列は違います．配列の場合，配列のサイズがが９バイト以上になると

* スタック上に配列を確保し，これを初期化
* `__rust_alloc`でヒープ上に配列のメモリを確保
* スタック上の配列をヒープにコピー

という動作になります．

```rust:rust
fn main() {
    let data = Box::new([112u8; 9]);
    println!("{}", data[0]);
}
```

```llvm:llvm-ir
  %_2 = alloca [9 x i8], align 1
  %data = alloca [9 x i8]*, align 8
  ...
  %_2.0.sroa_idx6 = getelementptr inbounds [9 x i8], [9 x i8]* %_2, i64 0, i64 0
  ...
  call void @llvm.memset.p0i8.i64(i8* nonnull align 1 %_2.0.sroa_idx6, i8 112, i64 9, i1 false)
  %1 = tail call i8* @__rust_alloc(i64 9, i64 1) #7, !noalias !5
  ...
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 %1, i8* nonnull align 1 %_2.0.sroa_idx6, i64 9, i1 false) #7
```

この動作に関連するIssueが登録済みです．

* [Boxed array initialisation with Box::new does not seem to optimise properly #41831](https://github.com/rust-lang/rust/issues/41831)

類似の問題として，`Box<[T; N]>`の`clone`のコンパイル結果が登録されてます．

`Box::new()`について説明しましたが，同様の問題は`Rc::new()`などでも発生します．

### 関数呼び出し順序の一貫性

`Box::new(X::new())`がどのようなコードにコンパイルされるのかは確認が必要です．

普通に考えると，他の関数の呼び出し順との一貫性から

1. X::new()
2. Box::new()

の順番で呼び出しが行われるべきです．

RustにはC++の継承のような機能が存在せず，その代替として

```rust:rust
// C++での`class T: public Base {};`に相当
struct Base<T> {
  data: T,
}
```

のような書き方をすることがよくあります．そのため，アグレッシブな最適化のために，上記の呼び出し順序の一貫性を犠牲にすることになりそうです．

実際，`X::new()`を実装して確認してみると，`Box::new(X { .. })`の場合と同様に，`__rust_alloc`後にヒープ上のオブジェクトを初期化するコードが生成されることが分かります．

~~未検証ですが，（インライン展開できないくらい）もっと複雑な`new()`を実装すると，`X::new()`の結果をスタック上に一度保存するかもしれません（検証が必要だと考えています）．~~

### 検証してみました

`X::new()`に`#[inline(never)]`をつけて検証してみました．

[Rust Playground](https://play.rust-lang.org/?version=stable&mode=release&edition=2015&gist=b0a379774a73f7497ddf80250b56f7cc)

```rust:rust
struct X {
    x1: i64,
    x2: i64,
    x3: i64,
}

impl X {
    #[inline(never)]
    fn new(x: i64) -> X {
        X { x1: x, x2: x, x3: x, }
    }
}

fn main() {
    let data = Box::new(X::new(112));
    println!("{}", data.x1);
}
```

構造体のサイズが小さいと`#[inline(never)]`をつけても`X::new()`がなくなるので，サイズを大きくしてあります．

```llvm:llvm-ir
  %_2 = alloca %X, align 8
  ...
  %1 = bitcast %X* %_2 to i8*
  ...
; call playground::X::new
  call fastcc void @_ZN10playground1X3new17hd1b418a35221643aE(%X* noalias nocapture nonnull dereferenceable(24) %_2)
  %2 = tail call i8* @__rust_alloc(i64 24, i64 8) #8, !noalias !5
  ...
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 %2, i8* nonnull align 8 %1, i64 24, i1 false) #8
```

スタック上のオブジェクトに対して`X::new()`を呼び出し，それを`Box::new()`で確保してヒープ上のオブジェクトにコピーしています．

このことから，大きな構造体を使うようなプロジェクトでは，オブジェクト生成コストがC/C++に比べて大きくなります．何より，スタックの消費を避けるためヒープから確保しようとして`Box::new()`に置き換えたとしても，改善されないという点が一番大きな問題です．

### `box`構文

`box`を使えば`Box::new()`に関しては改善可能です．

```rust:rust
#![feature(box_syntax)]  // added

struct X {
    x1: i64,
    x2: i64,
    x3: i64,
}

impl X {
    #[inline(never)]
    fn new(x: i64) -> X {
        X { x1: x, x2: x, x3: x, }
    }
}

fn main() {
    let data = box X::new(112);  // modified
    println!("{}", data.x1);
}
```

上記のように書き換え，Nightlyでビルドすると

```llvm:llvm-ir
  %data = alloca %X*, align 8
  ...
  %1 = tail call i8* @__rust_alloc(i64 24, i64 8) #8
  ...
  %3 = bitcast i8* %1 to %X*
; call playground::X::new
  tail call fastcc void @_ZN10playground1X3new17h0ce0962a98843dbaE(%X* noalias nocapture dereferenceable(24) %3)
  %4 = bitcast %X** %data to i8**
  store i8* %1, i8** %4, align 8
 
```

スタック上にオブジェクトを確保せず，ヒープ上のオブジェクトに対して`X::new()`が呼び出されます．また，関数呼び出し順序の一貫性も保たれます．

### 配置構文

`Box::new()`の問題は`box`を使うことで解決できますが，`Rc::new()`など他にもヒープからメモリを割り当てる関数は存在します．これらについては当然`box`では問題を解決できません．

一連のコピーコストの問題を解決するため配置構文が提案されていました．

* [Tracking issue for placement new · Issue #27779 · rust-lang/rust](https://github.com/rust-lang/rust/issues/27779)
* [Rustの配置構文とbox構文 - 簡潔なQ](https://qnighy.hatenablog.com/entry/2017/06/06/220000)

しかし，最終的にはunstableからも削除されたようです．

* [Remove all unstable placement features by aidanhs · Pull Request #48333 · rust-lang/rust](https://github.com/rust-lang/rust/pull/48333)

ちなみに，`Rc::new()`は，[ヒープからメモリを割り当てるために`box`構文を使用していますが](https://github.com/rust-lang/rust/blob/1.30.0/src/liballoc/rc.rs#L315)，インライン展開されないためスタック上に一時オブジェクトが作成されます．多分，インライン展開すれば改善されると思われます．

## 戻り値の代入

関数の戻り値を代入する場合，余計なスタックからのコピーが発生する場合があります．

```rust:rust
struct X {
    x1: i64,
    x2: i64,
    x3: i64,  // これを消すとレジスタだけでコピーできるようになり，スタックからのコピー回数が減る
}

impl X {
    #[inline(never)]
    fn new(x: i64) -> X {
        X { x1: x, x2: x, x3: x, }
    }
}

#[inline(never)]
fn p(x: &X) {
    println!("{}", x.x1);
}

fn main() {
    let mut data = X::new(112);
    p(&data);
    data = X::new(123);
    p(&data);
}
```

```llvm:llvm-ir
  %_5 = alloca %X, align 8
  %data = alloca %X, align 8
  ...
; call playground::X::new
  call fastcc void @_ZN10playground1X3new17h4bea4d29da321a4dE(%X* noalias nocapture nonnull dereferenceable(24) %data, i64 112)
; call playground::p
  call fastcc void @_ZN10playground1p17hdbe1cc8eb37ada0dE(%X* noalias nonnull readonly dereferenceable(24) %data)
  %1 = bitcast %X* %_5 to i8*
  call void @llvm.lifetime.start.p0i8(i64 24, i8* nonnull %1)
; call playground::X::new
  call fastcc void @_ZN10playground1X3new17h4bea4d29da321a4dE(%X* noalias nocapture nonnull dereferenceable(24) %_5, i64 123)
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 %0, i8* nonnull align 8 %1, i64 24, i1 false)
  call void @llvm.lifetime.end.p0i8(i64 24, i8* nonnull %1)
```

C++には`operator=`があるので理解できるのですが，Rustには該当するものがないので最適化でスタックからのコピーをなくすことが可能なように思われます．それとも，`Copy`や`Clone`を考慮するとスタックからのコピーが必要なのでしょうか？

# 借用と最適化

所有権の維持のため，関数呼び出し時に参照を渡すことは多々あると思います．しかし，これが原因でC/C++に比べて最適化が進まないことがあるようです．

例えば以下のようなコードは

```rust:rust
#[inline(never)]
fn p(x: &i32) {
    println!("{}", x);
}

fn main() {
    let d = 1;
    p(&d);
}
```

```:asm
playground::main:
	pushq	%rax
	movl	$1, 4(%rsp)
	leaq	4(%rsp), %rdi
	callq	playground::p
	popq	%rax
	retq
```

のように一度スタックに値を書き込み，書き込み先アドレスを引数として関数を呼び出すようにコンパイルされます．素直な結果です．

ところが，C/C++で同じようなコードを書くと（以下はCの例ですが，C++でも基本的には同じです），

```c:C
#include <stdio.h>

static void __attribute__ ((noinline)) p(int* x) {
  printf("%d\n", *x);
}

int main(int argc, char** argv) {
  int a = 1;
  p(&a);
  return 0;
}
```

```:asm（macOSのclangでコンパイル）
_main:                                  ## @main
	.cfi_startproc
## %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register %rbp
	movl	$1, %edi
	callq	_p
	xorl	%eax, %eax
	popq	%rbp
	retq
	.cfi_endproc
```

即値で関数を呼び出すように書き換えられます（呼び出される関数のコードも含めて）．かなりアグレッシブです．

しかし，以下のように変更すると

```c:C
#include <stdio.h>

static void __attribute__ ((noinline)) p(int* x) {
  if (x != NULL)  // 追加
    printf("%d\n", *x);
}

int main(int argc, char** argv) {
  int a = 1;
  p(&a);
  return 0;
}
```

```:asm（macOSのclangでコンパイル）
_main:                                  ## @main
	.cfi_startproc
## %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register %rbp
	subq	$16, %rsp
	movl	$1, -4(%rbp)
	leaq	-4(%rbp), %rdi
	callq	_p
	xorl	%eax, %eax
	addq	$16, %rsp
	popq	%rbp
	retq
	.cfi_endproc
```

Rustの例と同じようにスタック上のアドレスを渡すようになります．推測にすぎませんが，Rustの例は，内部的にはNULLチェックを伴うようなプログラムに展開されていると考えられます．Rustでは借用がNULLになることはありえないのですが．