旧石器時代のポインタをご利用の皆様へ ～provenance入門～

現代のプログラミング言語ではポインタは単なるアドレスではなく，provenanceを伴った参照として扱われています．
世界は既に変わっています．

# 概要

* ポインタは単なるアドレスではありません．
* ポインタにはprovenanceという，どのオブジェクト由来かの情報が含まれています．
* Provenanceを使うことで，最適化が効きやすくなったり，堅牢なプログラムを書きやすくなったりします．

追記: 次の英語記事を読むとprovenanceが必要な理由についてもっとよく知ることができます．クリックしよう！！！！(2020-12-15)
https://www.ralfj.de/blog/2020/12/14/provenance.html

# ポインタはアドレスではない

次のCプログラムを見てみましょう．

```c
#include <stdio.h>
#include <string.h>

int main() {
    int a = 100;
    int b = 200;
    
    int *p = &a + 1;
    int *q = &b;
    printf("p = %p, q = %p, (p == q) = %d\n", p, q, p == q);
    if (p == q) {
        printf("p == q!\n");
    }
    
    printf("a = %d, b = %d", a, b);
}
```

このコードを[GCC 10.1.0で実行する](https://wandbox.org/permlink/UJBXWGE4mqSMCb7h)と次の結果が得られます．

```
p = 0x7ffd5d140d1c, q = 0x7ffd5d140d1c, (p == q) = 0
a = 100, b = 200
```

注目すべき点は，ポインタ`p`と`q`がそれぞれ`0x7ffd5d140d1c`という同じアドレス値[^1]をとっているのにも関わらず，`p == q`という比較が偽を返している(`p`と`q`とが異なるポインタである)ということです．
つまり，**ポインタの等しさにはアドレス以外の何者かが関わってくるのです！**

[^1]: アドレス値自体は実行ごとに変わります．

それはポインタのprovenance(由来)と呼ばれるものです．provenanceはポインタがどのオブジェクトから由来するものかを表します．さきほどのプログラムの場合はポインタ`p`のprovenanceは変数`a`，ポインタ`q`は変数`b`となっています．ポインタのprovenanceが異なっているため，`p`と`q`は(たとえアドレスが同じでも)異なるポインタと**判定しても良い**のです．

**注: 変更前のバージョンでは上の段落は「provenanceが異なるポインタは『必ず』異なると判定される」と読める文章でした，これは意図(provenanceが異なるポインタは異なると判定『しても良い』)とは異なるので訂正します．例えば，プロセッサ上では通常アドレス数値のみを用いてポインタを扱うので，provenanceが異なっていてもアドレスが等しいポインタが`==`の意味で等しいと判定しても良いです．(2020-09-08)**

注意しなければならないのは，このようなprovenanceを用いた推論は**既に行われている**という点です．文書としての初出は[2004年](http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm)です．これはC20の提案などではなく，**10年以上続いている現状**なのです[^2]．

[^2]: [C2xへのprovenance提案](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2362.pdf)は現状を明文化するものと捉えるのが良いでしょう．

# Provenanceの何が嬉しいのか

## 最適化能力の向上

コンパイラはprovenance情報をポインタのエイリアス解析に活用しています．
つまり，provenanceを解析することでポインタを経由した読み込み/書き込みの影響範囲を計算でき，この情報によって最適化が可能かどうかより正確に判定できるようになります．
例えば，次の関数

```c
int func(int *p) {
    int x = 100;
    *p = 300;
    return x;
}
```

は直観的には

```c
int func2(int *p) {
    *p = 300;
    return 100; // xの値を伝播させた
}
```

と最適化することができそうです．
この最適化を正当化するためには「ポインタ`p`が変数`x`を指すことは無い」ということを証明する必要があります．

ここで，ポインタを単なるアドレスと同一視した場合，

```c
func((int*)rand()); // たまたまxのアドレスが出てしまった！
```

というケースが存在するので`func → func2`の最適化が不正なものとなってしまいます．

一方で，provenanceを使った場合は`(int*)rand()`が`x`のprovenanceを持つことはありません(まだ`x`が登場していないため)．ですから，`func → func2`という最適化が正当化できます．

## サニタイザの強化

ポインタのprovenanceは「オブジェクトを指すもの」としてのポインタを捉えた概念です．
これを活用することでプログラムの堅牢性を向上させることもできるかもしれません．

Cプログラミングではサニタイザを使ってプログラムが不正な動作を起こしていないかどうかテストし，プログラムの堅牢性を高めることがよく行われています．
例えば，AddressSanitizerやValgrindといったサニタイザを利用することで，バッファオーバーフローやメモリリークといったバグを検出することが可能です．

ですが，サニタイザは全てのバグを検出できるわけではありません．
この記事の最初に取り上げたプログラムの場合，ポインタ`p`は大元の変数`a`の範囲からははみ出ていますから，ある意味でバッファオーバーフローが起きていると言えます[^3]．
しかし，ポインタ`p`のアドレス値は変数`b`のアドレスであり，アドレスだけを見た場合はこのバッファオーバーフローは検出できません．

[^3]: 厳密には1個先のアドレスはアクセスしない限り大丈夫なはずですが，ここでは問題があるということにします．

しかし，ポインタのprovenanceも考慮した場合，ポインタ`p`は変数`a`の範囲内に収まっていなければならないということがサニタイザからも分かるので，バッファオーバーフローの検出が可能です．

**Provenance的な推論を行うサニタイザは既に登場しつつあります．**
例えば，RustのMIRIインタプリタにはサニタイザが標準搭載されており，未初期化メモリやダングリングポインタといった典型的な未定義動作だけではなくprovenance的な未定義動作の検出[^4]も可能です．
MIRIインタプリタはRust Playgroundからも簡単に実行でき，unsafe Rustを書く人々に重用されています．C言語にも同様のサニタイザが導入される未来は想像に難くありません．

[^4]: Rustの場合はprovenanceではなくStacked Borrowsと呼ばれる定式化を用いて参照の由来を表現しています．

# 更に詳しく

https://stefansf.de/post/pointers-are-more-abstract-than-you-might-expect/ ではほとんど同じ例(似ているのはたまたまです)について詳しく考察をしています．
残念ながらこのブログ記事の結論に自分は同意しない(aggregateは1つのオブジェクトをなすと自分は考えています)のですが，よく書かれています．

ポインタのprovenanceの取り扱いは確定したとは言い難く，プログラミング言語研究における最先端の一つと言えるでしょう．
例えば，次のような問題に答えていく必要があります．

* ポインタを`memcpy`したときのprovenanceはどうなる？
* ポインタ↔整数キャストの場合は？
* MMIO等特殊なポインタの取り扱いは？
* `__attribute__((malloc))`

気になる方は次の文献をチェックしてみるのはいかがでしょうか．

* Ralf Jung (Rust研究者)のブログ．分かりやすいのでオススメ
  * [Pointers Are Complicated, or: What's in a Byte?](https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html)
  * ["What The Hardware Does" is not What Your Program Does: Uninitialized Memory](https://www.ralfj.de/blog/2019/07/14/uninit.html)
* [Cのprovenance解説文書](http://www.open-std.org/JTC1/SC22/WG14/www/docs/n2012.htm#clarifying-the-c-memory-object-model-pointer-provenance)
* [C2xへのprovenance提案](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2362.pdf)
* [自分もいくつかprovenance関連の論文メモを残しています](https://gist.github.com/pandaman64/40c18e7ec3eb337bfb23ea3ddbf56411#%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9llvm%E3%81%AE%E3%83%A1%E3%83%A2%E3%83%AA%E3%83%A2%E3%83%87%E3%83%AB)

# 謝辞

素晴らしいタイトルを提供してくれた親友に感謝します．