C++ constexpr このブログ投稿では、文字列リテラルとして与えられた Brainfuck プログラムを解析し、実行時に実行できる最適化されたアセンブリ命令を生成できるコンパイラを作成します。最も良い点:実際にアセンブリを生成する必要はありません。自分たちで何も最適化することもありません!代わりに、コンパイラをだましてすべての難しい作業を行わせます。
ある種の「プログラム」を別の方法で指定し、実行時に変換したい場合はいつでも、同じ手法を使用できます:正規表現、ルーティング テーブルなど。
ブレインファック
Brainfuck は、「単純な」チューリング完全プログラミング言語です。実行すると、Brainfuck プログラムは、6 つのコマンドのいずれかによって制御されるデータ ポインターを介してバイト配列を変更します。
>、<データポインタをインクリメント/デクリメントします (ptr++、ptr--)+、-データポインタが指す値をインクリメント/デクリメントします ((*ptr)++、(*ptr)--).、,データポインタが指す値の書き込み/読み取り (putchar(*ptr)、*ptr = getchar())[、]データポインターが指す値がゼロである限り、内部コマンドを実行するループを形成します (while (*ptr == 0) { …})
他のすべての文字はコメントと見なされ、無視されます。
詳細 (具体的には、実際に何か役に立つことを行うにはどうすればよいでしょうか?!) については、ウィキペディアの記事を参照してください。
ステップ 1:従来の Brainfuck VM
最初に、Brainfuck を実行するための従来の VM を構築します。VM のプログラムは命令の配列です:
enum class op
{
ptr_inc, // >
ptr_dec, // <
data_inc, // +
data_dec, // -
write, // .
read, // ,
jmp_ifz, // [, jump if zero
jmp, // ], unconditional jump
};
template <std::size_t InstructionCapacity>
struct program
{
std::size_t inst_count;
op inst[InstructionCapacity];
std::size_t inst_jmp[InstructionCapacity];
};
最初の 6 つのオペランドはコマンドに直接対応します。ループ コマンドはジャンプに下げられています。これは、対応する [ の入力文字列をスキャンする必要がないことを意味します。 または ] 命令 inst[i] のジャンプ先 inst_jmp]i]で指定;これは宛先のインデックスです。非ジャンプ命令の配列の値は無視されます。
最終的には、コンパイル時に既知の Brainfuck プログラムを実行したいので、単純な固定サイズの配列を使用して命令を格納しています。サイズの上限は常にわかっています。
execute() を記述できるようになりました プログラムと data_ptr を取る関数 ループと switch を使用して ステートメント:
template <std::size_t InstructionCapacity>
void execute(const program<InstructionCapacity>& program,
unsigned char* data_ptr)
{
auto inst_ptr = std::size_t(0);
while (inst_ptr < program.inst_count)
{
switch (program.inst[inst_ptr])
{
case op::ptr_inc:
++data_ptr;
++inst_ptr;
break;
case op::ptr_dec:
--data_ptr;
++inst_ptr;
break;
case op::data_inc:
++*data_ptr;
++inst_ptr;
break;
case op::data_dec:
--*data_ptr;
++inst_ptr;
break;
case op::write:
std::putchar(*data_ptr);
++inst_ptr;
break;
case op::read:
*data_ptr = static_cast<unsigned char>(std::getchar());
++inst_ptr;
break;
case op::jmp_ifz:
if (*data_ptr == 0)
inst_ptr = program.inst_jmp[inst_ptr];
else
++inst_ptr;
break;
case op::jmp:
inst_ptr = program.inst_jmp[inst_ptr];
break;
}
}
}
残っているのは、文字列リテラルを解析してプログラムにすることです。コンパイル時の定数である文字列リテラルの長さを InstructionCapacity として使用できることに注意してください。 (最悪の場合、文字列の各文字は 1 つの命令です)。ループを実装するには、最後に開いた [ の位置を記憶するスタックを使用できます。 .
template <std::size_t N>
constexpr auto parse(const char (&str)[N])
{
program<N> result{};
std::size_t jump_stack[N] = {};
std::size_t jump_stack_top = 0;
for (auto ptr = str; *ptr; ++ptr)
{
if (*ptr == '>')
result.inst[result.inst_count++] = op::ptr_inc;
else if (*ptr == '<')
result.inst[result.inst_count++] = op::ptr_dec;
else if (*ptr == '+')
result.inst[result.inst_count++] = op::data_inc;
else if (*ptr == '-')
result.inst[result.inst_count++] = op::data_dec;
else if (*ptr == '.')
result.inst[result.inst_count++] = op::write;
else if (*ptr == ',')
result.inst[result.inst_count++] = op::read;
else if (*ptr == '[')
{
jump_stack[jump_stack_top++] = result.inst_count;
result.inst[result.inst_count++] = op::jmp_ifz;
}
else if (*ptr == ']')
{
auto open = jump_stack[--jump_stack_top];
auto close = result.inst_count++;
result.inst[close] = op::jmp;
result.inst_jmp[close] = open;
result.inst_jmp[open] = close + 1;
}
}
return result;
}
まとめると、文字列リテラルとして与えられた Brainfuck プログラムを解析して実行できるようになりました:
// `x = std::getchar(); y = x + 3; std::putchar(y);`
static constexpr auto add3 = parse(",>+++<[->+<]>.");
// Use this array for our data_ptr.
unsigned char memory[1024] = {};
execute(add3, memory);
解析は完全にコンパイル時に行われますが、実行は実行時に行われることに注意してください。それができることはすでに素晴らしいことです!
生成されたアセンブリは簡単です。clang は、スイッチをルックアップ テーブルに変換することを決定しました。各命令のコードは、2 つのアセンブリ命令のみです。
メタ命令の追加による最適化や JIT コンパイルなど、そのルートをさらにたどりたい場合は、Eli Bendersky によるこのシリーズを強くお勧めします。
ただし、私たちは何か違うことをしています。
ステップ 2:末尾再帰
プログラムの書き方を変更して、実際には何も変更しませんが、次のステップへの動機付けを容易にします:execute() の反復バージョンを回す これは、ループ中に変更されたすべての引数、つまり inst_ptr を渡すことによって行われます。 、追加の引数として。その後、ループを削除し、++inst_ptr; break; を回します。 return execute(program, memory, inst_ptr + 1) に .
通常、再帰はスタック オーバーフローを引き起こす可能性があるため、反復よりも悪いことになります。ただし、ここでは、再帰呼び出しが実際に新しいスタック フレームをプッシュする必要はなく、引数を更新するだけで済む末尾再帰があります。もちろん、コンパイラはその最適化を行う必要があります。そうしないと、ループによってすぐにスタック オーバーフローが発生します。clang 属性 [[clang::musttail]] これは、clang の手を強制するために使用できます。これは、読みやすくするために以下のスニペットでは省略されています。
新しい execute() 関数は次のようになります:
template <std::size_t InstructionCapacity>
void execute(const program<InstructionCapacity>& program,
unsigned char* data_ptr,
std::size_t inst_ptr = 0)
{
if (inst_ptr >= program.inst_count)
return; // Execution is finished.
switch (program.inst[inst_ptr])
{
case op::ptr_inc:
++data_ptr;
return execute(program, data_ptr, inst_ptr + 1);
case op::ptr_dec:
--data_ptr;
return execute(program, data_ptr, inst_ptr + 1);
case op::data_inc:
++*data_ptr;
return execute(program, data_ptr, inst_ptr + 1);
case op::data_dec:
--*data_ptr;
return execute(program, data_ptr, inst_ptr + 1);
case op::write:
std::putchar(*data_ptr);
return execute(program, data_ptr, inst_ptr + 1);
case op::read:
*data_ptr = static_cast<unsigned char>(std::getchar());
return execute(program, data_ptr, inst_ptr + 1);
case op::jmp_ifz:
if (*data_ptr == 0)
return execute(program, data_ptr, program.inst_jmp[inst_ptr]);
else
return execute(program, data_ptr, inst_ptr + 1);
case op::jmp:
return execute(program, data_ptr, program.inst_jmp[inst_ptr]);
}
}
ここでは、生成されたアセンブリが少し長く見えますが、それ以外は同じように見えます。これは驚くべきことではありません。コンパイラについては実際には何も変更していないからです!
生成されたアセンブリを実際に変更してみましょう。
ステップ 3:テンプレートにする
末尾再帰バージョンを注意深く見ると、次のことがわかります。各再帰呼び出しで、inst_ptr の新しい値 コンパイル時の定数 (1 )、または inst_jmp から値を読み取ることによって これもコンパイル時に計算されます。つまり、inst_ptr の値がわかっている場合 コンパイル時に命令を実行する前に、コンパイル時に次の値も知っています。jmp_ifz の場合 、ランタイム値に分岐がありますが、各分岐の宛先は固定です。
さらに、inst_ptr の値がわかれば コンパイル時に、ランタイム switch を実行する必要もありません inst の対応する命令として 配列もコンパイル時に計算されます。
これは、execute(const program&, unsigned char* data_ptr, std::size_t inst_ptr) を回すことができることを意味します program のテンプレートに と inst_ptr はテンプレート パラメータとして与えられます!コンパイル時に計算されるため、プログラムをテンプレート パラメータとして渡すことができます。ただし、inst_ptr を渡すこともできます。 テンプレートパラメータとして、最初は 0 です 、後で他の定数によってのみ変更されます。その後、 switch を置き換えることができます if constexpr で 、末尾再帰の代わりに、テンプレートの別のインスタンス化への末尾呼び出しがあります。
template <const auto& Program, std::size_t InstPtr = 0>
constexpr void execute(unsigned char* data_ptr)
{
if constexpr (InstPtr >= Program.inst_count)
{
// Execution is finished.
return;
}
else if constexpr (Program.inst[InstPtr] == op::ptr_inc)
{
++data_ptr;
return execute<Program, InstPtr + 1>(data_ptr);
}
else if constexpr (Program.inst[InstPtr] == op::ptr_dec)
{
--data_ptr;
return execute<Program, InstPtr + 1>(data_ptr);
}
else if constexpr (Program.inst[InstPtr] == op::data_inc)
{
++*data_ptr;
return execute<Program, InstPtr + 1>(data_ptr);
}
else if constexpr (Program.inst[InstPtr] == op::data_dec)
{
--*data_ptr;
return execute<Program, InstPtr + 1>(data_ptr);
}
else if constexpr (Program.inst[InstPtr] == op::write)
{
std::putchar(*data_ptr);
return execute<Program, InstPtr + 1>(data_ptr);
}
else if constexpr (Program.inst[InstPtr] == op::read)
{
*data_ptr = static_cast<char>(std::getchar());
return execute<Program, InstPtr + 1>(data_ptr);
}
else if constexpr (Program.inst[InstPtr] == op::jmp_ifz)
{
if (*data_ptr == 0)
return execute<Program, Program.inst_jmp[InstPtr]>(data_ptr);
else
return execute<Program, InstPtr + 1>(data_ptr);
}
else if constexpr (Program.inst[InstPtr] == op::jmp)
{
return execute<Program, Program.inst_jmp[InstPtr]>(data_ptr);
}
}
アセンブリを見てみましょう。すべてのディスパッチが消え、「call std::getchar()」に置き換えられています。 、3 を追加、std::putchar() を呼び出す !これは可能です。コンパイル時に完全にディスパッチを行っているため、コンパイラは一連のテール コールを認識します。これらは簡単に融合して最適化できます。
さらに、Program へのすべてのアクセスとして の配列はコンパイル時の定数なので、Program は必要ありません これは、命令を保存する追加のメモリがないことを意味します。
結論
素晴らしいことですが、これが実際にどのように役立つのでしょうか?Brainfuck プログラムを解析する手間をかけずに、同等の動作を C++ で直接記述できます。
ただし、コンパイル時に別の言語で何かを指定し、コンパイル時に実行させたい場合があります。 、そしてこのテクニックを活用して、ランタイム実行のための効率的なコード生成を取得します.これは基本的にHanaのCTREライブラリが機能する方法です.同様に、私は現在lexyでそれを使用して、一連の文字列リテラルと照合するための効率的なコードを生成しています.
コンパイル時に DSL で何かを指定し、それを動的入力で効率的に実行したいときはいつでも、if constexpr を使用して、静的プログラム状態と動的データを分離するこのハイブリッド アプローチを使用します。 末尾再帰 (ループがない場合はインライン展開のみ) が機能します。