C++ の型をハックする年末


ハッピーホリデイ！まであと 4 日ほどとなりました。
本エントリは dwango advent calendar 20th エントリとなります。

師走と書いて師が走っているので、我々はのんびりとテンプレートメタプログラミングでコンパイラに労働させましょう。

さて今回取り上げるのは、レイアウトを扱う上でどうにか楽にできないか、というところです。
我々が扱うのは CPU ばかりじゃありませんので、大体メモリレイアウトをどうにかしなきゃいけないことがあります。

が、もう少し身近な話でバイナリファイルの構造とかで考えてみます。
例えば、あるファイルの構造がこうなっていたとしましょう。

```
struct root_t {
   uint16_t length;
   entry_t slabs[ENTS_MAX];
};
```

この構造は、例えば記録メディアの団体とかでなんらかの規格で決められているものとして、好き嫌いを別にして扱わないといけなものとします。
MAX も規格で決められてることにしましょう。
さて、レイアウトとしては上記通りとしても、実は規格で「ウチの整数は BigEndian だから」というふうに決まったとします。
CPU 側が LittleEndian だとするとこれはそのまんまコピーはできない。(できないというか値の意味が壊れる)
じゃあ
`using B = uint8_t __attribute__((aligned(2))) [2] ;`
とかしてうっかりコピーを防ごうぜ, という感じになるわけですが, これで

```
struct real_root_t {
   uint16big_t length;
   entry_t slabs[ENTS_MAX];
};
```

を別の型として作ったりできますね。
うっかり非互換型をキャストすることがなくなったのはビッグなアドであるわけで。
（各メンバを Big/Little 変換するような関数は必要）
CPU で扱う型は依然として `root_t` のみ、読み書きだけが `real_root_t` というわけです。
こういうことをずーっとやってると、 `real_root_t` って `root_t` から自然に導出できませんかね、という気持ちになります。

そこで、テンプレートメタプログラミングの出番です。
variadic template parameter を使って、計算可能な型を作りましょう。

基本は `type_t < type1, type2, ... >` とやって構造体もどきを定義できればよさそうですが、構造体にはパディングがあって、これではメモリ上で互換になりません。
パディングやアラインメントを考慮した (offsetof)/alignof/sizeof がこの型にあれば、(仕様上はともかく)実装合わせで互換ということにはもっていけそうです。
(ただ仕様上実装依存になっているので原始 struct と type_t<> をまるまる同列に扱うことには問題がありまそうです)
そこでアラインメント要件を制約に加えて構造体もどきを作れるようにしましょう。
集約型 `agg_t` とし、 `type_t< T, Align >` で型自体のアラインメントを指定するようにしましょう。 `agg_t` にアラインメント要件を指定する手もありそうですが、 C++ には他に共用体もありますので、共通の外部インターフェイスとなる型は必要になりそうです。
`type_t< agg_t< type, type, ... >, 0 >` で自然な align, `type_t< agg_t< type, type, ... >, 1 >` で packed と同義になるということで `__attritbute__` や `[attribute]` とも近い使用感になります。

こうしてできた型は `get< NewType, 0, 1 >` として pair 風のアクセスをする形になり、メンバはシンボルを持ちません。
(最初の 0 は type_t が収容するただ一つの agg_t を示す)
この例では、型のメンバには既存の struct を使って名前を使ったアクセスができたほうがはるかに便利そうです。
型から型を導出するというメリットよりも、メンバ名を使えたほうが遥かに良いじゃんと。
まぁ、それはそう of そう。
役に立ちませんね。

とりあえず、そうして作られたものがここにございます。
https://github.com/roentgen/typeutils

## 少し規模の大きいメモリレイアウト

じゃあ別の状況を考えてみましょう。
メモリレイアウトがあって、型名だけが重要な状態です。
普通のアプリケーションではそれほど多くないのですが、例えば GPU など別のデバイスを叩くときです。
大容量データを扱ってると、個別のメンバにいちいちアクセスしないし、その名前なんかどうだってよいわけです。
最初は `mat4x4 perspective_cam0;` とか律儀に名前をつけるかも知れませんけど、そのうち matrix は matrix やんね、という気持ちになって、この構造体がただの mat4x4 の巨大な配列にしか見えなくなってきたとき「最初の matrix が透視変換行列でしたねぇ」くらいになってきます。
さらに、この状況では実際にデバイスとやりとりするフラットなメモリブロックとは別にコンフィギュレーションのため、そのメモリブロックがどういうレイアウトになっているのか、デスクリプタテーブルを求められることもよくあります。というか、それがないとデバイス側は困ってしまいます。ここに書いてあるデータ何なの？ってことになっちゃいますから。
そういうときに

* 計算可能な型があれば、定数的にデスクリプタテーブルの値を生成できる！
* レイアウトの定義を変更すればデスクリプタテーブルの構造も追従される！

という世界があったら素晴らしい。
静的リフレクションがあればできそうだし、コンパイル時に確定するという希望もあるけども残念ながら今はまだないのでやってみようという話です。

### レイアウトを定義する例

さて、たとえば DirectX12 の Root Signature の Descriptor を設定するような場合を考えましょう。
DirectX12 では、 Root Signature という構造をもって GPU と CPU リソースのバインディングを明示します。
ざっくりいうと CPU と GPU で相互に見えるメモリブロック（仮想アドレスは異なる）上の、どこにどういうデータがあって、これはシェーダーからどうアクセスできる、ということを定めるものですね。

これは即ちレイアウトとデスクリプタの問題であります。
またせっかくこういう仕組みがあるんですから柔軟性も確保したい。パフォーマンスのためにこのレイアウトを並び替えたりしなければいけなくなりますので。

(デスクリプタはこの場合なんらかのパラメータを詰め込んだ便利な構造体ですが、具体的にどういう構造体をどういうパラメータに設定するのかは、煩雑になるので省きます)
(ちなみに、 DirectX12 では Root Signature を記述するための DSL と外部ツールがございます。それを使えばコード上でごりごりやらなくても Root Signature は手に入りますが、 CPU から見たメモリ上でのレイアウトとの関連は失われることになります。それでもいいやという場合はもっと楽ができそうです)

実際にはもうひとつ、描画コマンドリストにそういうデスクリプタを並べた領域の先頭を設定する必要があります。
これは GPU のアドレス空間で、 Descriptor の個数分だけオフセットを加算してゆく操作に相当しますので、 Descriptor の数が一致するように注意しないといけません。
レイアウトが型として与えられているなら、これも同種も問題として捉えることができそうです。

話を簡単にするため、制約として

* 子として集約されるひとつの type_t がひとつの Descriptor に相当する

を入れましょう。

ここでは簡単な例として 2 つのプリミティブを描画するため行列を 2 つ, テクスチャを 1 つで描画する場合を考えます。

```
using CBV = type_t< agg_t< mat4x4, mat4x4 >, 16>;
using SRV = type_t< agg_t< int >, 0 >;
using Layout = type_t< agg_t< CBV, SRV >, 0 >;
```

CBV (ConstantBufferview: GPU プログラムから見た定数データ列) には予め 2 つのワールド変換用モデル行列を置くものの、 DrawCall ごとに参照するものは常にひとつとしましょう。
シェーダープログラムとしては同じもので描画されますし、デスクリプタを一つにすることで同じ開始レジスタにマップされます。
モデル行列の切り替えには描画ごとにデスクリプタヒープというデスクリプタの集まりがオフセットされるだけです。行列の値が更新されないのなら毎回行列を送りなおしたりキャッシュを invalidate するのは無駄だからです。
SRV (テクスチャ)のほうは型が識別できればなんでもいいです（ここでは）。

この `Layout` 型を静的に精査して、デスクリプタの数、リソース（ここでは行列）の数、それらの任意の要素の開始位置、大きさが決定できれば使えそうです。

まずデスクリプタの数は、収容される各 `type_t` 型がひとつのデスクリプタに相当すると定義しましたので, `type_t` の数を数えればよいです。
これには `fold` を使います。 `fold` は入力の型 In に対して SFINAE で高度な検定ができますので、 `template template parameter` を使って:

```
#include <stdio.h>
#include <aggregate.hpp>
#include <type_traits>
#include <typeinfo>
#include <stdint.h>
#if defined(HAS_CXXABI_H)
#include <cxxabi.h>
#endif

using namespace typu;

struct mat4x4 { float m[16]; };

using CBV = type_t< agg_t< mat4x4, mat4x4 >, 16>;
using SRV = type_t< agg_t< int >, 0 >;
using Layout = type_t< agg_t< CBV, SRV >, 0 >;

const char* demangle(const char* nm)
{
#if defined(HAS_CXXABI_H)
	int status;
	return abi::__cxa_demangle(nm, 0, 0, &status);
#else
	return nm;
#endif
}

template < template <typename, alignment_t> typename T, typename Ts, alignment_t A >
constexpr bool is_type_t(T<Ts, A>&&) { return std::is_same< T< Ts, A >, type_t<Ts, A > >::value; };

template < typename Acc, Acc Acc0, typename In, typename En = void >
struct fold_type_t_fun { static const Acc value = Acc0; };
template < typename Acc, Acc Acc0, typename In>
struct fold_type_t_fun< Acc, Acc0, In, std::enable_if_t< is_type_t(In{}) > >  { static const Acc value = Acc0 + 1; };

int main()
{
	printf("%s -> %d(descriptors)\n", demangle(typeid(Layout).name()), fold< Layout, int, 0, fold_type_t_fun >::value);
	return 0;
}

```

でよさそうです。
次に行列の数は mat4x4 に一致するものを調べればよさそうです。
これには mat4x4 が配列になっているか(mat4x4 mat[4] とか)どうかによってバリエーションがあるのですが、今は配列じゃないので素直に書きます。

fold に与える述語:

```
template < typename Acc, Acc Acc0, typename In >
struct fold_mat_fun { static const Acc value = Acc0; };
template <typename Acc, Acc Acc0 >
struct fold_mat_fun< Acc, Acc0, mat4x4 > { static const Acc value = Acc0 + 1; };
```

fold を適用する:

```
	printf("%s -> %d(matricies)\n", demangle(typeid(Layout).name()), fold< get< Layout, 0, 0 >::type, int, 0, fold_mat_fun >::value);
```

うまくいきました。
あれ？ `fold< Layout, int, 0, fold_mat_fun >::value` じゃダメなの……？　と思ったあなたは鋭い。
……すいませんバグってました。`type_t` がネストすると `fold` の走査が入っていきません。
うあああ面倒くさ！！
この年の瀬に何やってんだよもう！
行列渡すのなんて CBV (ConstantBufferView) くらいだよね？とかでいったん勘弁してください。

次に CPU から見てちゃんとメモリマップになっていることを確認しましょう。
メモリブロック p に対してキャストなしのアクセスができています。
下の例では無邪気に malloc してますので、アラインメント用件は満たしてません。

```
	void* p = malloc(get< Layout, 0 >::size);
	printf("size:%ld %p\n", get< Layout, 0 >::size, p);
	memset(p, 0xcc, get< Layout, 0 >::size);
	using CBV = get<Layout, 0, 0>::type;
	
	*get<Layout, 0, 0, 0, 0>::addr(p) = mat4x4{};
	*get<Layout, 0, 0, 0, 1>::addr(p) = mat4x4{};
```

```
size:132 0x8415fa0

Program received signal SIGTRAP, Trace/breakpoint trap.
0x0000000008001022 in main ()
(gdb) x /132bx 0x8415fa0
0x8415fa0:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415fa8:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415fb0:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415fb8:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415fc0:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415fc8:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415fd0:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415fd8:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415fe0:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415fe8:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415ff0:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8415ff8:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8416000:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8416008:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8416010:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8416018:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x8416020:      0xcc    0xcc    0xcc    0xcc
```

おっけーそうです。
struct との互換性はいまいちですが、なんとかもう少し揉めば目的に合いそうです。

ちなみにこれを粗方作ってから boost hana というのがあるのを知りました。
*へーいいじゃん*。
良いお年を。


## 課題

### 同じ型をまとめたい
 
例えば本格的に使おうとすると、ある `mat4x4[2]` と `mat4x4[2]` は、 CPU からアクセスするときはそれぞれ別の配列でいいけど GPU からアクセスする場合はひとつのデスクリプタでいいじゃん、ということがあります。
そこを編集するために `morph` のついでに mat4x4[NA] と mat4x4[NB] を mat4x4[NA+NB] にしたいなと思うことがあります。
これはよほど作為的な使い方で、なかなか汎用的な方法が見つかりません。
これは前節で上げた "agg_t がひとつの Descriptor に相当する" というような制約を緩和させる、という話です。

### 実メモリ操作も fold でやりたい

fold のテンプレート引数でわたす関数オブジェクトに実アドレスを渡して副作用のある操作もやらせたいけど、 C++14 までの範囲では厳しそう。