brainrot - 極限の速度を追い求めて

注意: このページにおけるbrainrotは個人が名付けた言語処理系の名前であり、イタリアンブレインロットやBrain rotとは異なります

4ヶ月以上の歳月を経て極限を追求したBrainfuck最適化処理系brainrotをあなたはご存知ですか？

今回は、そんな処理系brainrot不定期レポート(?)第一弾を書いていこうと思います。

1. 高密度バイトコード

このbrainrotで最も特徴的なのは、恐らくこの高密度なインタプリタバイトコードでしょう。
以下がそのバイトコード定義の一部です:

pub enum Bytecode {
    Breakpoint { delta: i16 },

    SingleAdd { delta: i16, val: u8 },
    SingleSet { delta: i16, val: u8 },
    AddAdd { delta1: i16, val1: u8, delta2: i16, val2: u8 },
    AddSet { delta1: i16, val1: u8, delta2: i16, val2: u8 },
    SetAdd { delta1: i16, val1: u8, delta2: i16, val2: u8 },
    SetSet { delta1: i16, val1: u8, delta2: i16, val2: u8 },

    BothRangeCheck { range: Range<u16> },
    Shift  { delta: i16, step: i16 },
    ShiftN { delta: i16, step: i16, range: RangeFrom<u16> },
    ShiftP { delta: i16, step: i16, range: RangeTo<u16> },
    ShiftAdd  { delta1: i16, step: i8, delta2: i8, val: u8 },
    ShiftAddN { delta1: i16, step: i8, delta2: i8, val: u8, range: RangeFrom<u16> },
    ShiftAddP { delta1: i16, step: i8, delta2: i8, val: u8, range: RangeTo<u16> },
    ShiftSet  { delta1: i16, step: i8, delta2: i8, val: u8 },
    ShiftSetN { delta1: i16, step: i8, delta2: i8, val: u8, range: RangeFrom<u16> },
    ShiftSetP { delta1: i16, step: i8, delta2: i8, val: u8, range: RangeTo<u16> }

実に高密度でしょう？一つのバイトコードに3個にもなる命令が詰まった高密度命令が大量にあるのです。
このように一コードで行う命令を増やすことでメインループの反復を減らし、より速い実行を実現しています。

安全性

どうせ速くても、broptのように境界チェックを省略してしまったら危険なのでは？

と思う方もいるでしょう。
しかし、brainrotではこの課題を解決し、境界チェックを削減しつつ範囲外アクセスに対応できる構造となっております。

その秘訣はRangeです。前述のコードを見れば分かる通り、バイトコードに範囲データが埋め込まれており、ここから必要な部分でのみ境界チェックが可能な設計となっております。
このようなことが可能である理由は、高度なBrainfuckコード解析にあります。

brainrotでは、基底ポインタ+オフセット形式によるコード解析を行っています。
ポインタ移動命令を記録し、固定可能なメモリアドレスとループでのポインタ移動差分をIRに埋め込むことによって、ポインタ移動差分の地点からどのようなメモリアクセスがあるか、どのような範囲であれば安全かを解析し、最小限の範囲チェックで動作可能となっております。

次世代のbrainrot

我々は、次世代のbrainrotを企画・設計しております。
次世代のbrainrotでは、制御フローグラフ・静的単一代入などによるより高度な最適化をする予定です。

将来の進展について、ぜひご期待ください。