Binary Hacks Rebooted ―低レイヤの世界を探検するテクニック89選

8章言語処理系HackHack #79–86

通常、コンパイラの教科書では構文解析やレジスタ割り付けといったオーソドックスなテーマが扱われています。それらのテーマも非常に重要なのですが、現実世界のコンパイラ・インタプリタ周辺には、有名ではなくても特定の状況下で役に立つテクニックが多数存在します。本章ではそれらのテクニックをまとめて紹介します。言語処理系周辺でHackをしたくなったときに本章の内容が役に立つでしょう。

HACK #79　NaNを活用して64ビット値にタグ付きの値を格納する

本Hackでは、64ビット値に倍精度浮動小数点数やポインタ等の値をタグ付きで格納するテクニックを紹介します。

動的型付き言語での値の表現

動的型付き言語の典型的な実装では、任意の種類の値を区別・表現できるように、種類を表すタグと実際の内容を組み合わせて値を表現しています。C言語の構造体として書けば次のようになります。

struct Value {
  uint8_t tag;
  union {
    Object *obj; // 固定長で表現できないデータや可変なオブジェクトを表現するためにポインタを使う
    double f64;
    int32_t i32;
  };
};

この定義では、x86-32では1個の値を表現するのに12バイト、典型的な64ビット環境では16バイト必要になります†1。ですが、Value型は至るところに現れるため、メモリ上で表現する際は1バイトでも節約したいです。もっと少ないバイト数で任意の値を表現することはできないでしょうか？ ...