グラフィックスプログラミングにおいて制御フローを構造化するために使用されるツールである`dxil-spirv`の開発者は、重大な技術的課題に直面しました。既存の構造化アルゴリズム（structurizer）が、メンテナンス不可能な9,000行の「ブラックホール」と化してしまったのです。元の実装は、現代のゲームアップデートによって生成される、ますます複雑で予測不能なシェーダーを処理しながら、人間が読めるコードを維持しようとしていました。しかし、この「人間中心」のアプローチは、特定のシェーダーがあまりにも巨大であったためにGraphvizが有限の時間内にレンダリングできなくなるという限界点に達しました。その結果、開発者は可読性の目標を放棄し、絶対的な正当性とパフォーマンスを優先する道を選びました。
この問題を解決するために、開発者はMesaグラフィックスドライバやOpenCLに近い哲学を採用しました。すべての分岐をインテリジェントに整理しようとする代わりに、新しいシステムは再帰的なアルゴリズムを使用して「シリアル化レベル」を積み上げます。このアプローチでは、ダミー変数を使用してパスを追跡し、複雑なswitchブロックを一連の条件分岐に変換することで前方制御フローを処理します。大きな簡素化の一つは、書き換えの過程でPHI SSA（静的単一代入）ノードを保持しようとする試みを断念したことです。代わりに、ツールは現在これらを単純な変数とストアに落とし込み、メモリからレジスタへの最適化はプロダクションコンパイラに任せるようにしました。これにより、構造化アルゴリズムの複雑さが大幅に軽減されました。
この画像は、開発者が複雑なシェーダーロジックを処理するために簡素化しなければならなかった特定の制御フロー構造を示しています。
この画像は、新しい再帰的アルゴリズムが処理するように設計された複雑な分岐ロジックのタイプを描写しています。
この新しい「正当性優先」のロジックを検証するために、開発者は2段階のテストプロセスを採用しました。まず、構造化アルゴリズムを完全にバイパスして、生の構造化されていない「スパゲッティ」コードを直接ドライバに送信し、世界が崩壊せず、RADVドライバにおいてパフォーマンスが同等であることを確認しました。次に、ランダム化された簡約可能な制御フローグラフ（CFG）を生成するファザーを構築し、ビット精度のフィードバックを使用して新しいアルゴリズムに対して検証を行いました。新しい手法は、旧システムでは処理できなかった「怪物」のような構造を正常に処理できる一方で、生成されるコードの人間に対する可読性への集中を犠牲にしており、NVIDIAのプロプライエタリハードウェア上でのパフォーマンスは未検証の変数として残されています。
この図は、新しいシステムが正常に処理できる制御フローグラフの特定の事例を示しています。