オプティマイザ

Solidityコンパイラは、2つの異なるオプティマイザモジュールを使用しています。 オペコードレベルで動作する「旧」オプティマイザと、Yul IRコードで動作する「新」オプティマイザです。

オペコードベースのオプティマイザは、オペコードに 簡略化ルール を適用します。 また、同じコードセットを組み合わせたり、使われていないコードを削除したりします。

Yulベースのオプティマイザは、関数呼び出しをまたいで動作できるのでより強力です。 例えば、Yulでは任意のジャンプができないため、各関数の副作用を計算できます。 2つの関数呼び出しを考えてみましょう。 1つ目はストレージを変更せず、2つ目はストレージを変更します。 それらの引数と戻り値がお互いに依存しない場合、関数呼び出しを並べ替えることができます。 同様に、ある関数に副作用がなく、その実行結果にゼロをかける場合は、その関数呼び出しを完全に削除できます。

現在、パラメータ --optimize は、生成されたバイトコードにはオペコードベースのオプティマイザを、ABI coder v2などで内部的に生成されたYulコードにはYulオプティマイザを適用します。 solc --ir-optimized --optimize は、Solidityのソースに対して最適化されたYul IRを生成するために使用できます。 同様に、 solc --strict-assembly --optimize はスタンドアローンのYulモードに使用できます。

注釈

peepholeオプティマイザ はデフォルトで常に有効になっており、 Standard JSON によってのみオフにできます。

オプティマイザモジュールとその最適化ステップの詳細は以下の通りです。

Solidityコードを最適化するメリット

全体的に、オプティマイザは複雑な式を単純化しようとします。 これにより、コードサイズと実行コストの両方が削減されます。 つまり、コントラクトのデプロイやコントラクトへの外部呼び出しに必要なガスを削減できます。 また、関数の特殊化やインライン化も行います。 特に関数のインライン化は、コードサイズが大きくなる可能性がある操作ですが、より単純化できる機会があるため、よく行われます。

最適化コードと非最適化コードの違い

一般的に最も目に見える違いは、定数式がコンパイル時に評価されることです。 ASMの出力に関しても、同じあるいは重複するコードブロックが減っていることがわかります（フラグ --asm と --asm --optimize の出力を比較してみてください）。 しかし、Yul/中間表現になると大きな差が出ることがあります。 例えば、冗長性をなくすために、関数がインライン化されたり、結合されたり、書き換えられたりすることがあります（フラグ --ir と --optimize --ir-optimized の出力を比較してみてください）。

オプティマイザの実行回数パラメータ

実行回数（ --optimize-runs ）は、デプロイされたコードの各オペコードがコントラクトのライフタイム中にどのくらいの頻度で実行されるかを大まかに指定します。 つまり、コードサイズ（デプロイコスト）とコード実行コスト（デプロイ後のコスト）のトレードオフパラメータとなります。 実行回数パラメータが1の場合、コードは短いものの実行時にコストのかかるコードが生成されます。 一方、実行回数パラメータを大きくすると、コードは長いもののガス効率の良いコードが生成されます。 パラメータの最大値は 2**32-1 です。

注釈

よくこのパラメータがオプティマイザの反復回数を指定すると誤解されますが、これは違います。 オプティマイザは、コードが改善される限り、常に何度でも実行されます。

オペコードベースのオプティマイザモジュール

オペコードベースのオプティマイザモジュールは、アセンブリコード上で動作します。 このモジュールは、一連の命令を JUMPs と JUMPDESTs の基本ブロックに分割します。 これらのブロックの中で、オプティマイザは命令を解析し、スタックやメモリ、ストレージに対するすべての変更を、命令と他の式へのポインタである引数のリストからなる式として記録します。

さらに、オペコードベースのオプティマイザでは、「CommonSubexpressionEliminator」というコンポーネントを使用しています。 他のタスクの中で、（すべての入力に対して）常に等しい式を見つけ出し、それらを式クラスにまとめるというものです。 まず、既知の式のリストから新しい式を見つけようとします。 もしそのような式が見つからなければ、 constant + constant = sum_of_constants や X * 1 = X のようなルールに従って式を簡略化します。 これは再帰的なプロセスであるため、第2因子が常に1と評価されることがわかっているより複雑な式の場合、後者のルールを適用することもできます。

オプティマイザの一部のステップでは、ストレージやメモリの位置をシンボリックに追跡します。 例えば、この情報は、コンパイル時に評価できるKeccak-256ハッシュの計算に使用されます。 次のシーケンスを考えてみましょう。

PUSH 32
PUSH 0
CALLDATALOAD
PUSH 100
DUP2
MSTORE
KECCAK256

または、同等の処理をする次のYulコードを考えてみましょう。

open in Remix

let x := calldataload(0)
mstore(x, 100)
let value := keccak256(x, 32)

この場合、オプティマイザはメモリ位置 calldataload(0) の値を追跡し、コンパイル時にKeccak-256ハッシュを評価できることを認識します。 これがうまくいくのは、 mstore と keccak256 の間にメモリを変更する他の命令がない場合です。 つまり、メモリ（またはストレージ）に書き込む命令があれば、現在のメモリ（またはストレージ）の知識を消去する必要があるのです。 しかし、この消去には例外があり、その命令がある場所に書き込まれていないことが容易にわかる場合です。

例えば、次のコードです。

open in Remix

let x := calldataload(0)
mstore(x, 100)
// Current knowledge memory location x -> 100
let y := add(x, 32)
// Does not clear the knowledge that x -> 100, since y does not write to [x, x + 32)
mstore(y, 200)
// This Keccak-256 can now be evaluated
let value := keccak256(x, 32)

そのため、ストレージやメモリの位置（例えば位置 l ）を変更する場合、 l に等しい可能性のあるストレージやメモリの位置に関する知識を消去しなければなりません。 具体的には、ストレージについては、 l に等しい可能性のあるシンボリックロケーションの知識をすべて消去し、メモリについては、少なくとも32バイト離れていない可能性のあるシンボリックロケーションの知識をすべて消去しなければなりません。 m が任意の位置を示す場合、この消去の判断は値 sub(l, m) を計算することで行われます。 ストレージの場合、この値がゼロではないリテラルと評価されれば、 m に関する知識は維持されます。 メモリの場合、この値が 32 と 2**256 - 32 の間のリテラルと評価されるならば、 m に関する知識が保持されます。 それ以外の場合は、 m に関する知識は消去されます。

このプロセスを経て、最後にどの式がスタック上になければならないかがわかり、メモリとストレージの修正リストができました。 これらの情報は基本ブロックと一緒に保存され、ブロックの連結に使用されます。 さらに、スタック、ストレージ、メモリの構成に関する知識は、次のブロック（複数可）に転送されます。

すべての JUMP 命令と JUMPI 命令のターゲットがわかっていれば、プログラムの完全なコントロールフローグラフを作成できます。 一つだけわからないターゲットがある場合（ジャンプターゲットは原理的に入力から計算できるため、このようなことが起こりうる）、ブロックの入力状態に関する知識をすべて消去しなければなりません。 なぜなら、そのブロックは未知の JUMP のターゲットになりうるからです。 オペコードベースのオプティマイザモジュールは、条件が定数で評価される JUMPI を見つけた場合、それを無条件ジャンプに変換します。

最後のステップとして、各ブロックのコードが再生成されます。 オプティマイザは、ブロックの最後のスタック上の式から依存関係のグラフを作成し、このグラフに含まれないすべての操作を削除します。 メモリやストレージの変更を元のコードの順番通りに適用するコードを生成します（必要ないと判断された変更は削除します）。 最後に、スタック上に必要なすべての値を正しい位置に生成します。

これらのステップは各基本ブロックに適用され、新しく生成されたコードの方が小さい場合には置き換えとして使用されます。 基本ブロックが JUMPI で分割され、解析中にその条件が定数と評価された場合、 JUMPI は定数の値に基づいて置換されます。 したがって、以下のようなコードは

open in Remix

uint x = 7;
data[7] = 9;
if (data[x] != x + 2) // this condition is never true
  return 2;
else
  return 1;

は次のように簡略化されます。

open in Remix

data[7] = 9;
return 1;

単純なインライン化

Solidityのバージョン0.8.2以降、オプティマイザのステップとして、「ジャンプ」で終わる「単純な」命令を含むブロックへの特定のジャンプを、これらの命令のコピーに置き換えるものがあります。 これは、単純で小さなSolidityやYulの関数のインライン化に相当します。 特に、シーケンス PUSHTAG(tag) JUMP は、 JUMP が関数への「ジャンプ」としてマークされ、 tag の後ろに、関数からの「ジャンプ」としてマークされた別の JUMP で終わる基本ブロック（「CommonSubexpressionEliminator」で前述したように）がある場合には、置き換えられる可能性があります。

具体的には、Solidityの内部関数をコールした際に生成されるアセンブリの典型的な例を以下に示します。

  tag_return
  tag_f
  jump      // in
tag_return:
  ...opcodes after call to f...

tag_f:
  ...body of function f...
  jump      // out

関数のボディが連続した基本ブロックである限り、「Inliner」は tag_f jump を tag_f のブロックで置き換えることができ、結果として以下のようになります。

  tag_return
  ...body of function f...
  jump
tag_return:
  ...opcodes after call to f...

tag_f:
  ...body of function f...
  jump      // out

ここで理想的なのは、上述の他のオプティマイザのステップにより、リターンタグのプッシュが残りのジャンプの方に移動し、結果として、

  ...body of function f...
  tag_return
  jump
tag_return:
  ...opcodes after call to f...

tag_f:
  ...body of function f...
  jump      // out

この場合、「PeepholeOptimizer」はリターンジャンプを削除します。 理想的には、すべての tag_f への参照に対してこれを行い、未使用のまま、削除できるようにできます。

...body of function f...
...opcodes after call to f...

そのため、関数 f の呼び出しはインライン化され、 f の元の定義は削除できます。

このようなインライン化は、インライン化しないよりもインライン化した方がコントラクトのライフタイムの中で安くなるというヒューリスティックな提案がある場合に試みられます。 このヒューリスティックは、関数本体のサイズ、そのタグへの他の参照の数（関数のコール回数に近似）、コントラクトの予想実行回数（グローバルオプティマイザのパラメータ「runs」）に依存します。

Yulベースのオプティマイザモジュール

Yulベースのオプティマイザは、いくつかのステージとコンポーネントで構成されており、これらがすべて意味的に同等の方法でASTを変換します。 最終的には、コードを短くするか、少なくともわずかに長くするだけで、さらなる最適化を可能にすることが目標です。

警告

オプティマイザは現在鋭意開発中のため、ここに掲載されている情報は古いものになっている可能性があります。

特定の機能に依存している場合は、チームに直接お問い合わせください。

現在、オプティマイザは純粋に貪欲な戦略をとり、バックトラックは一切行いません。

Yulベースのオプティマイザモジュールの全構成要素を以下に説明します。 以下の変換ステップが主な構成要素です。

• SSA Transform

• Common Subexpression Eliminator

• Expression Simplifier

• Redundant Assign Eliminator

• Full Inliner

オプティマイザのステップ

これは、Yulベースのオプティマイザの全ステップをアルファベット順に並べたリストです。 個々のステップとそのシーケンスについては、以下で詳しく説明しています。

Abbreviation	Full name
f	BlockFlattener
l	CircularReferencesPruner
c	CommonSubexpressionEliminator
C	ConditionalSimplifier
U	ConditionalUnsimplifier
n	ControlFlowSimplifier
D	DeadCodeEliminator
E	EqualStoreEliminator
v	EquivalentFunctionCombiner
e	ExpressionInliner
j	ExpressionJoiner
s	ExpressionSimplifier
x	ExpressionSplitter
I	ForLoopConditionIntoBody
O	ForLoopConditionOutOfBody
o	ForLoopInitRewriter
i	FullInliner
g	FunctionGrouper
h	FunctionHoister
F	FunctionSpecializer
T	LiteralRematerialiser
L	LoadResolver
M	LoopInvariantCodeMotion
r	RedundantAssignEliminator
m	Rematerialiser
V	SSAReverser
a	SSATransform
t	StructuralSimplifier
p	UnusedFunctionParameterPruner
S	UnusedStoreEliminator
u	UnusedPruner
d	VarDeclInitializer

いくつかのステップは BlockFlattener, FunctionGrouper, ForLoopInitRewriter によって確保されるプロパティに依存しています。 このため、Yulオプティマイザは、ユーザーが提供したステップを適用する前に、常にそれらを適用します。

最適化の選択

デフォルトでは、オプティマイザは、生成されたアセンブリに対して、事前に定義された最適化ステップのシーケンスを適用します。 --yul-optimizations オプションを使用すると、このシーケンスを上書きして、独自のシーケンスを指定できます。

solc --optimize --ir-optimized --yul-optimizations 'dhfoD[xarrscLMcCTU]uljmul:fDnTOc'

ステップの順番は重要で、アウトプットの品質に影響します。 さらに、あるステップを適用することで、すでに適用した他のステップの新たな最適化の機会が発見されることもあり、ステップを繰り返すことが有益なことも多くあります。

[...] 内のシーケンスは、Yulコードが変化しないか、最大ラウンド数（現在は12ラウンド）に達するまで、ループで複数回適用されます。 括弧（ [] ）は連続して複数回使用できますが、入れ子にすることはできません。

注意すべき重要な点は、ユーザーから提供されたシーケンス（ユーザーから提供されなかった場合はデフォルトのシーケンス）の前後に常に実行されるハードコードされたステップがいくつかあることです。

クリーンアップシーケンスの区切り文字 : はオプションで、デフォルトのクリーンアップシーケンスを置き換えるために、カスタムクリーンアップシーケンスを指定するために使用します。 省略された場合、オプティマイザはデフォルトのクリーンアップシーケンスを適用します。 また、デリミターをユーザーが指定したシーケンスの先頭に置くと、最適化シーケンスは空になり、逆にシーケンスの末尾に置くと、空のクリーンアップシーケンスとして扱われます。

前処理

前処理コンポーネントは、プログラムを作業しやすい特定の正規形に変換します。

この正規形は、最適化プロセスの残りの部分でも保たれます。

Disambiguator

DisambiguatorはASTを受け取り、すべての識別子が入力ASTの中でユニークな名前を持つようなコピーを新たに作って返します。 これは、他の全てのオプティマイザのステージの前提条件となります。 利点は、識別子の検索にスコープを考慮する必要がないため、他のステップで必要な分析が簡単になることです。

それ以降のステージでは、すべての名前が一意に保たれるという特性があります。 つまり、新しい識別子を導入する必要がある場合は、新しいユニークな名前が生成されます。

FunctionHoister

FunctionHoisterは、すべての関数定義を最上位のブロックの最後に移動させます。 これは、曖昧さを解消するステージの後に実行される限り、意味的に同等の変換です。 その理由は、定義を上位のブロックに移動しても、そのビジビリティを低下させることはできず、また、別の関数で定義された変数を参照することもできないからです。

このステージの利点は、関数の定義をより簡単に調べることができ、ASTを完全にトラバースすることなく関数を単独で最適化できることです。

FunctionGrouper

FunctionGrouperは、DisambiguatorとFunctionHoisterの後に適用しなければなりません。 その効果は、関数定義ではないすべての最上位要素が、ルートブロックの最初の文である単一のブロックに移動されることです。

このステップを経て、プログラムは次のような正規形になります。

{ I F... }

I は関数定義を（再帰的にも）含まない（空になる可能性のある）ブロックであり、 F は関数定義のリストでどの関数も関数定義を含まないようになっています。

このステージの利点は、関数のリストがどこから始まるかを常に把握できることです。

ForLoopConditionIntoBody

この変換は、forループのループ反復条件をループ本体に移動させるものです。 ExpressionSplitter は反復条件式（以下の例では C ）には適用されないため、この変換が必要です。

for { Init... } C { Post... } {
    Body...
}

上記のコードは次の処理に変換されます。

for { Init... } 1 { Post... } {
    if iszero(C) { break }
    Body...
}

ループ不変条件の不変量をループの外に出すことができるため、この変換は LoopInvariantCodeMotion と組み合わせても有効です。

ForLoopInitRewriter

この変換により、for-loopの初期化部分がループの前に移動します。

for { Init... } C { Post... } {
    Body...
}

上記のコードは次の処理に変換されます。

Init...
for {} C { Post... } {
    Body...
}

これにより、forループ初期化ブロックの複雑なスコープルールを無視できるため、残りの最適化プロセスが容易になります。

VarDeclInitializer

このステップでは、変数の宣言を書き換えて、すべての変数が初期化されるようにします。 let x, y のような宣言は、複数の宣言文に分割されます。

今のところ、ゼロリテラルでの初期化のみをサポートしています。

疑似SSAトランスフォーム

このコンポーネントの目的は、プログラムをより長い形式にして、他のコンポーネントがより簡単に作業できるようにすることです。 最終的な表現は、Static-Single-Assignment (SSA)形式に似ていますが、コントロールフローの異なるブランチからの値を結合する明示的な「phi」関数を使用しないという違いがあります（そのような機能はYul言語には存在しません）。 代わりに、コントロールフローがマージされる際に、いずれかのブランチで変数が再代入されると、その現在の値を保持する新しいSSA変数が宣言されるため、以下の式では依然としてSSA変数を参照するだけでよいです。

変換例は以下の通りです。

open in Remix

{
    let a := calldataload(0)
    let b := calldataload(0x20)
    if gt(a, 0) {
        b := mul(b, 0x20)
    }
    a := add(a, 1)
    sstore(a, add(b, 0x20))
}

以下の変換ステップをすべて適用すると、プログラムは以下のようになります。

open in Remix

{
    let _1 := 0
    let a_9 := calldataload(_1)
    let a := a_9
    let _2 := 0x20
    let b_10 := calldataload(_2)
    let b := b_10
    let _3 := 0
    let _4 := gt(a_9, _3)
    if _4
    {
        let _5 := 0x20
        let b_11 := mul(b_10, _5)
        b := b_11
    }
    let b_12 := b
    let _6 := 1
    let a_13 := add(a_9, _6)
    let _7 := 0x20
    let _8 := add(b_12, _7)
    sstore(a_13, _8)
}

このスニペットで再代入されている変数は b のみであることに注意してください。 b はコントロールフローに応じて異なる値を持つため、この再代入を避けることはできません。 他のすべての変数は、一度定義されるとその値が変わることはありません。 この特性の利点は、新しいコンテキストでこれらの値が有効である限り、変数を自由に移動させたり、変数への参照を初期値で交換したりできることです（その逆も同様）。

もちろん、このコードは最適化されたものとは程遠いです。 それどころかずっと長くなっています。 ここで期待することは、このコードが作業しやすくなり、さらに、これらの変更をリバートし、最後に再びコードをコンパクトにするオプティマイザのステップがあることです。

ExpressionSplitter

ExpressionSplitterは、 add(mload(0x123), mul(mload(0x456), 0x20)) のような式を、その式のサブ式に代入られた一意の変数の宣言の列に変え、各関数呼び出しが引数として変数のみを持つようにします。

上記の式は次のように変換されます。

open in Remix

{
    let _1 := 0x20
    let _2 := 0x456
    let _3 := mload(_2)
    let _4 := mul(_3, _1)
    let _5 := 0x123
    let _6 := mload(_5)
    let z := add(_6, _4)
}

なお、この変換はオペコードや関数のコールの順番を変えるものではありません。

これは、ループのコントロールフローが、すべてのケースで内部式の「アウトライン化」を許可していないため、ループの反復条件には適用されません。 ForLoopConditionIntoBody を適用して反復条件をループ本体に移動させることで、この制限を回避できます。

最終的なプログラムは、（ループ条件を除いて）関数呼び出しを式の中に入れ子にすることはできず、関数呼び出しの引数はすべて変数でなければならないという形にしなければなりません。

この形式の利点は、オペコードの順序を変更するのがかなり容易であることと、関数呼び出しのインライン化を実行するのも容易であることです。 さらに、式の個々の部分を置き換えたり、「式ツリー」を再編成したりするのも簡単です。 難点は、人間にとって読みにくいコードであることです。

SSATransform

このステージでは、既存の変数への繰り返しの代入を、新しい変数の宣言で可能な限り置き換えようとします。 再代入は残っていますが、再代入された変数へのすべての参照は、新しく宣言された変数に置き換えられます。

例:

open in Remix

{
    let a := 1
    mstore(a, 2)
    a := 3
}

は、次のコードに変換されます。

open in Remix

{
    let a_1 := 1
    let a := a_1
    mstore(a_1, 2)
    let a_3 := 3
    a := a_3
}

厳密なセマンティクス:

コードのどこかに代入されている変数 a （値が宣言されていて再代入されない変数は変更されない）について、以下の変換を行います。

• let a := v を let a_i := v   let a := a_i で置き換えます。

• a := v を let a_i := v   a := a_i に置き換えます。 ここで i は a_i にまだ使われていない数です。

さらに、 a に使われている i の現在の値を常に記録し、 a への各参照を a_i に置き換えます。 変数 a の現在値のマッピングは、それが代入された各ブロックの終了時、およびforループ本体やポストブロック内で代入された場合はforループのinitブロックの終了時にクリアされます。 上記のルールで変数の値がクリアされ、その変数がブロック外で宣言された場合、ループのポスト/ボディブロックの先頭や、If/Switch/ForLoop/Block文の直後など、コントロールフローが合流する位置に新たなSSA変数が作成されます。

このステージの後、不要な中間代入を削除するために、Redundant Assign Eliminatorを使用することをお勧めします。

このステージでは、Expression SplitterとCommon Subexpression Eliminatorが直前に実行されると、過剰な量の変数が生成されないため、最良の結果が得られます。 一方、Common Subexpression EliminatorはSSAトランスフォームの後に実行した方がより効率的です。

RedundantAssignEliminator

SSAトランスフォームでは、次の例のように多くのケースで不要な場合があっても、常に a := a_i 形式の割り当てが生成されます。

open in Remix

{
    let a := 1
    a := mload(a)
    a := sload(a)
    sstore(a, 1)
}

SSAトランスフォームでは、このスニペットを次のように変換します。

open in Remix

{
    let a_1 := 1
    let a := a_1
    let a_2 := mload(a_1)
    a := a_2
    let a_3 := sload(a_2)
    a := a_3
    sstore(a_3, 1)
}

Redundant Assign Eliminatorは、 a の値が使用されていないため、 a への3つの割り当てをすべて削除し、このスニペットを厳密なSSAフォームにします。

open in Remix

{
    let a_1 := 1
    let a_2 := mload(a_1)
    let a_3 := sload(a_2)
    sstore(a_3, 1)
}

もちろん、代入が冗長であるかどうかを判断する複雑な部分は、コントロールフローの結合につながっています。

このコンポーネントは、詳しくは以下のように動作します。

ASTは、情報収集のステップと実際の削除のステップの2回にわたって走査されます。 情報収集のステップでは、代入文から「unused」「undecided」「used」の3つの状態へのマッピングを保持しています。 これは、代入された値が後でその変数への参照によって使われるかどうかを示すものです。

代入が訪問されると、「undecided」状態のマッピングに追加され（後述のforループに関する記述を参照）、「undecided」状態のままの同じ変数への他のすべての代入は「unused」に変更されます。 ある変数が参照されると、「undecided」状態にあるその変数へのすべての割り当ての状態は "used"に変更されます。

コントロールフローが分岐するポイントでは、マッピングのコピーが各ブランチに引き渡されます。 コントロールフローが合流するポイントでは、2つのブランチから送られてきた2つのマッピングが次のようにして結合されます。 1つのマッピングにしかない文や同じ状態の文は、変更されずに使用されます。 相反する値は次のようにして解決されます。

• 「unused」「undecided」 -> 「undecided」

• 「unused」「used」 -> 「used」

• 「undecided」「used」 -> 「used」

for-loopでは、condition、body、post-partを2回訪れ、conditionでのコントロールフローの結合を考慮します。 つまり、3つのコントロールフローの経路を作ります。 つまり、0回のループ、1回のループ、2回のループの3つのコントロールフローを作成し、最後にそれらを結合します。

3回目以降のシミュレーションは不要であることは、次のように考えられます。

反復開始時の割り当ての状態は、反復終了時のその割り当ての状態を決定論的にもたらします。 この状態マッピング関数を f とします。 上記で説明した3つの異なる状態 unused 、 undecided 、 used の組み合わせは、 unused = 0 、 undecided = 1 、 used = 2 の max 演算です。

適切な方法は、次のように計算します。

max(s, f(s), f(f(s)), f(f(f(s))), ...)

をループ後の状態とします。 f は3つの異なる値の範囲を持っているだけなので、これを反復すると、最大で3回の反復後にサイクルに到達しなければならず、したがって f(f(f(s))) は s 、 f(s) 、 f(f(s)) のいずれかと等しくなければならず、したがって

max(s, f(s), f(f(s))) = max(s, f(s), f(f(s)), f(f(f(s))), ...).

要するに、3つの異なる状態があるだけなので、ループを最大2回実行すれば十分です。

defaultのケースを持つswitch文では、スイッチをスキップするコントロールフローの部分はありません。

変数がスコープ外に出ると、まだ「undecided」の状態にあるすべての文が「unused」に変更されます。 ただし、その変数が関数のリターンパラメータである場合は、「used」に変更されます。

2回目のトラバーサルでは、「unused」の状態にあるすべての代入が削除されます。

このステップは通常、SSAトランスフォームの直後に実行され、疑似SSAの生成を完了します。

ツール

Movability

movabilityは、式の特性の一つです。 大まかに言うと、その式は副作用がなく、その評価は変数の値と環境のコールコンスタントな状態にのみ依存するということです。 ほとんどの式はmovableです。 以下の部分が式をnon-movableにしています。

• 関数の呼び出し（関数内のすべての文がmovableであれば、将来緩和される可能性あり）

• 副作用のある（可能性のある）オペコード（ call や selfdestruct など）

• メモリ、ストレージ、外部の状態情報を読み書きするオペコード

• 現在のPC、メモリサイズ、リターンデータのサイズに依存するオペコード

DataflowAnalyzer

Dataflow Analyzerは、それ自体はオプティマイザではありませんが、他のコンポーネントのツールとして使用されます。 ASTをトラバースしながら、各変数の現在の値を追跡します（その値がmovableな式である限り）。 各変数に現在割り当てられている式の一部である変数を記録します。 変数 a に代入されるたびに、 a の現在の格納値が更新され、 a が b の現在格納されている式の一部であるときは、すべての変数 b のすべての格納値がクリアされます。

コントロールフローの分岐点では、コントロールフローのいずれかの経路で代入された、または代入される可能性のある変数についての知識がクリアされます。 たとえば、forループに入ると、bodyまたはpostブロックで代入される予定のすべての変数がクリアされます。

式スケールの単純化

これらの簡略化パスは、表現を変更し、同等の、できればより単純な表現に置き換えます。

CommonSubexpressionEliminator

このステップでは、Dataflow Analyzer を使用して、構文的に変数の現在の値と一致する部分式を、その変数への参照に置き換えます。 このような部分式はmovableでなければならないため、これは等価変換です。

識別子であるすべての部分式は、その値が識別子である場合、現在の値で置き換えられます。

上記の2つのルールの組み合わせにより、ローカルな値のナンバリングを計算できます。 これは、2つの変数が同じ値を持つ場合、そのうちの1つは常に使用されないことを意味します。 Unused PrunerやRedundant Assign Eliminatorは、このような変数を完全に排除できます。

このステップは、式分割機が前に実行されている場合、特に効率的です。 コードが疑似SSA形式であれば、変数の値はより長い時間利用可能であるため、式が置換可能になる可能性が高くなります。

式単純化装置は、その直前に共通部分式除去装置が実行されていれば、より良い置換を行うことができます。

ExpressionSimplifier

Expression Simplifierは、Dataflow Analyzerを使用し、 X + 0 -> X のような式に対する等価変換のリストを利用してコードを単純化します。

X + 0 のようなパターンを各部分式でマッチさせようとします。 また、コードが疑似SSA形式であっても、より深い入れ子のパターンにマッチできるように、マッチング処理中に変数を現在割り当てられている式に解決します。

X - X -> 0 のようないくつかのパターンは、式 X がmovableである限り適用できます。 そうでなければ、その潜在的な副作用を取り除くことになるからです。 変数参照は、現在の値がそうでないかもしれないとしても、常にmovableであるため、式の簡略化は、分割または疑似SSAの形で再び強力になります。

LiteralRematerialiser

ドキュメント化予定。

LoadResolver

sload(x) 型と mload(x) 型の式を、現在ストレージやメモリに格納されている値で置き換える最適化ステージ。

コードがSSA形式の場合に最適です。

前提条件: Disambiguator、ForLoopInitRewriter。

文スケールの単純化

CircularReferencesPruner

このステージでは、相互に呼び出しているが、外部から参照されておらず、一番外側のコンテキストからも参照されていない関数を削除します。

ConditionalSimplifier

条件付きシンプリファイアは、コントロールフローから値が決定できる場合、条件変数への割り当てを挿入します。

SSAフォームを破棄します。

現在のところ、このツールは非常に限定されています。 主な理由は、ブーリアン型をまだサポートしていないからです。 条件は式がゼロでないことをチェックするだけなので、特定の値を割り当てることはできません。

現在の機能:

• スイッチケースで「<condition> := <caseLabel>」を挿入します。

• 終了コントロールフローのif文の後に、「<条件> := 0」を挿入します。

今後の機能:

• 「1」による置き換えを可能にします。

• ユーザー定義関数の終了を考慮に入れます。

SSA形式で、かつデッドコード除去を実行したことがある場合に最適です。

前提条件: Disambiguator。

ConditionalUnsimplifier

Conditional Simplifierの逆です。

ControlFlowSimplifier

いくつかのコントロールフロー構造を簡素化をします:

• pop(condition)でifを空のボディに置き換える

• 空のデフォルトのスイッチケースを削除する

• デフォルトのケースが存在しない場合、空のスイッチケースを削除する

• ケースのないswitchをpop(expression)で置き換える

• シングルケースのスイッチをifに変える

• pop(expression)とbodyでデフォルトケースのみのswitchに変更する

• スイッチを、ケースボディが一致するconst exprに置き換える

• for を終端コントロールフローに置き換える、 if による他のブレーク/コンティニューなしで

• 関数の最後にある leave を削除する

これらの操作はいずれもデータフローには依存しません。 StructuralSimplifierは、データフローに依存する同様のタスクを実行します。

ControlFlowSimplifierは、トラバーサル中に break 文と continue 文の有無を記録します。

前提条件: Disambiguator、FunctionHoister、ForLoopInitRewriter。

重要: EVMオペコードを導入しているため、現在はEVMコードにのみ使用可能です。

DeadCodeEliminator

この最適化ステージでは、到達できないコードを削除します。

到達不可能なコードとは、ブロック内のコードのうち、leave、return、invalid、break、continue、selfdestruct、revert、または無限に再帰するユーザー定義関数の呼び出しが先行するものを指します。

関数定義は、以前のコードから呼び出される可能性があるため、到達可能とみなされて保持されます。

forループのinitブロックで宣言された変数は、そのスコープがループ本体にまで及ぶため、このステップの前にForLoopInitRewriterを実行する必要があります。

前提条件: ForLoopInitRewriter、Function Hoister、Function Grouper。

EqualStoreEliminator

このステップは、 mstore(k, v) / sstore(k, v) の呼び出しが過去にあり、その間に他のストアがなく、 k と v の値が変更されていない場合に、 mstore(k, v) と sstore(k, v) の呼び出しを削除します。

この単純なステップは、SSA変換とCommon Subexpression Eliminatorの後に実行すると効果的です。 SSAは変数が変更されないことを確認し、Common Subexpression Eliminatorは値が同じであることが分かっている場合、まったく同じ変数を再利用するからです。

前提条件: Disambiguator、ForLoopInitRewriter。

UnusedPruner

このステップでは、参照されることのないすべての関数の定義を削除します。

また、決して参照されない変数の宣言も削除されます。 宣言が移動不可能な値を割り当てている場合、式は保持されますが、その値は破棄されます。

movableな式の文（割り当てられていない式）はすべて削除されます。

StructuralSimplifier

これは、構造的なレベルで様々な種類の単純化を行う一般的なステップです。

• if文を pop(condition) による空のボディに置き換える

• 真の条件を持つif文をそのボディで置き換える

• 偽の条件を持つif文は削除する

• シングルケースのスイッチをifに変える

• スイッチを pop(expression) とボディのデフォルトケースのみに置き換える

• 大文字小文字を一致させてスイッチをリテラル表現に置き換える

• 偽条件のforループを初期化部分で置き換える

このコンポーネントは、Dataflow Analyzerを使用します。

BlockFlattener

このステージでは、内側のブロックの文を外側のブロックの適切な場所に挿入することで、入れ子になったブロックを解消します。 このステージはFunctionGrouperに依存しており、FunctionGrouperによって生成されたフォームを維持するために、一番外側のブロックをフラットにしません。

open in Remix

{
    {
        let x := 2
        {
            let y := 3
            mstore(x, y)
        }
    }
}

は、次の処理に変換されます。

open in Remix

{
    {
        let x := 2
        let y := 3
        mstore(x, y)
    }
}

曖昧さを排除したコードであれば、変数のスコープは大きくなる一方なので、問題はありません。

LoopInvariantCodeMotion

この最適化により、移動可能なSSA変数の宣言はループの外側に移動します。

考慮されるのは、ループの本体またはポストブロック内のトップレベルの文のみです。 つまり、条件分岐内の変数宣言はループの外に移動されません。

要件:

• Disambiguator、ForLoopInitRewriter、FunctionHoisterは前もって実行する必要があります。

• より良い結果を得るためには、ExpressionSplitterとSSAトランスフォームを前もって実行する必要があります。

関数レベルの最適化

FunctionSpecializer

このステップでは、関数をリテラルの引数で特殊化します。

例えば function f(a, b) { sstore (a, b) } という関数が、例えば f(x, 5) というリテラルの引数で呼ばれ、 x が識別子である場合、1つの引数しか取らない f_1 という新しい関数を作ることで、特化できます。

open in Remix

function f_1(a_1) {
    let b_1 := 5
    sstore(a_1, b_1)
}

他の最適化ステップでは、関数をより単純化できます。 最適化ステップは、主にインライン化されないような関数に有効です。

前提条件: Disambiguator、FunctionHoister。

LiteralRematerialiserは、正しさのために必要ではないにもかかわらず、前提条件として推奨されています。

UnusedFunctionParameterPruner

このステップでは、関数内の未使用のパラメータを削除します。

c と y が function f(a,b,c) -> x, y { x := div(a,b) } になっているように、パラメータが使われていない場合は、パラメータを削除して、次のように新しい「リンク」関数を作成します。

open in Remix

function f(a,b) -> x { x := div(a,b) }
function f2(a,b,c) -> x, y { x := f(a,b) }

そして、 f へのすべての参照を f2 に置き換えます。 インライナーは、その後に実行して、 f2 へのすべての参照が f に置き換えられていることを確認する必要があります。

前提条件: Disambiguator、FunctionHoister、LiteralRematerialiser。

LiteralRematerialiserというステップは正しさのために必要ではありません。 以下のようなケースに対処するのに役立ちます。 function f(x) -> y { revert(y, y} } はリテラル y がその値 0 に置き換えられるので、関数を書き換えることができます。

UnusedStoreEliminator

冗長な sstore ステートメントやメモリストアステートメントを削除するオプティマイザコンポーネントです。 ストア sstore の場合、（明示的な revert() 、 invalid() 、または無限再帰によって）すべての出力コードパスがリバートするか、オプティマイザが最初のストアを上書きすると判断できる別の sstore につながる場合、ステートメントは削除されます。 しかし、最初の sstore とリバート、または上書きされる sstore の間に読み取り操作がある場合、ステートメントは削除されません。 このような読み取り操作には、外部呼び出し、ストレージにアクセスするユーザー定義関数、最初の sstore が書き込んだスロットと異なることを証明できないスロットの sload が含まれます。

例えば、次のコードは、

open in Remix

{
    let c := calldataload(0)
    sstore(c, 1)
    if c {
        sstore(c, 2)
    }
    sstore(c, 3)
}

Unused Store Eliminatorステップが実行されると、以下のコードに変換されます。

open in Remix

{
    let c := calldataload(0)
    if c { }
    sstore(c, 3)
}

メモリストア操作の場合、一般的には、少なくとも一番外側のYulブロックでは、そのようなステートメントは、どのコードパスでも読み込まれることがなければ、すべて削除されるので単純です。 しかし、関数解析レベルでは、関数のスコープを離れるとメモリロケーションが読み込まれるかどうかわからないので、ステートメントはすべてのコードパスがメモリの上書きにつながる場合にのみ削除されます。

SSA形式で最も効果があります。

前提条件: Disambiguator、ForLoopInitRewriter。

EquivalentFunctionCombiner

2つの関数が構文的に同等で、変数名の変更は可能だが順序変更はできない場合、一方の関数への参照は他方の関数で置き換えられます。

実際に関数を取り除くのは、Unused Prunerが行います。

関数のインライン化

ExpressionInliner

オプティマイザのこのコンポーネントは、関数式の中にあるインライン化できる関数、つまり以下のような関数をインライン化することで、制限付きの関数のインライン化を行います。

• 単一の値を返す

• r := <functional expression> のようなボディを持つ

• 自分自身も r も右辺で参照しない

さらに、すべてのパラメータについて、以下のすべてが真である必要があります。

• 引数がmovableである

• パラメータの参照回数が関数ボディ内で2回以下であるか、または引数のコストがかなり低い（"コスト"は最大でも1で、0xffまでの定数のようなもの）

例: インライン化される関数は function f(...) -> r { r := E } という形式で、 E は r を参照していない式で、関数呼び出しのすべての引数はmovableな式です。

このインライン化の結果は、常に単一の式となります。

このコンポーネントは、固有の名前を持つソースにのみ使用できます。

FullInliner

Full Inlinerでは、特定の関数の特定の呼び出しを関数の本体に置き換えます。 これはコードサイズが大きくなるだけで、ほとんどの場合あまり役に立ちません。 コードは通常非常に高価なものであり、効率の良いコードよりも短いコードの方が良い場合が多いのです。 しかし、いくつかのケースでは、関数のインライン化が後続のオプティマイザのステップにプラスの効果をもたらすことがあります。 例えば、関数の引数の1つが定数の場合です。

インライン化の際には、関数呼び出しをインライン化すべきかどうかを判断するヒューリスティックな手法が用いられます。 現在のヒューリスティックでは、呼び出される関数が小さなものでない限り、「大きな」関数にはインライン化されません。 一度しか使用されない関数はインライン化され、中規模の関数もインライン化されますが、定数の引数を持つ関数呼び出しでは少し大きな関数が使用できます。

将来は、関数をすぐにインライン化するのではなく、関数を特殊化するバックトラックコンポーネントを組み込むことも考えています。 その後、この特殊化された関数に対してオプティマイザを実行します。 その結果、大きな利益が得られた場合は、特化された関数を残し、そうでない場合は元の関数を代わりに使用します。

クリーンアップ

クリーンアップは、オプティマイザの実行の最後に行われます。 分割された式を再び深く入れ子にして結合しようとしたり、変数を極力排除してスタックマシンでの「コンパイル性」を向上させたりします。

ExpressionJoiner

これは、式分割器とは逆の動作です。 正確に1つの参照を持つ変数宣言のシーケンスを複雑な式に変えます。 このステージでは、関数の呼び出しとオペコードの実行の順序が完全に保持されます。 オペコードの可換性に関する情報は利用しません。 変数の値を使用する場所に移動することで、関数呼び出しやオペコードの実行順序が変わる場合は、変換を行いません。

ただし、変数の代入や複数回参照されている変数の代入値は、コンポーネントでは移動しません。

スニペット let x := add(0, 2) let y := mul(x, mload(2)) は変換されません。 オペコード add と mload の呼び出し順序が入れ替わってしまうからです。 ただし、 add はmovableなので違いはありません。

このようにオペコードを並び替える場合、変数参照やリテラルは無視されます。 そのため、リテラル 3 の評価後に add のオペコードが実行されるにもかかわらず、スニペット let x := add(0, 2) let y := mul(x, 3) は let y := mul(add(0, 2), 3) に変換されてしまいます。

SSAReverser

これは、Common Subexpression EliminatorやUnused Prunerと組み合わせることで、SSAトランスフォームの効果を元に戻すのに役立つ小さな一歩です。

私たちが生成するSSAフォームは、多くのローカル変数を生成するため、コード生成に悪影響を及ぼします。 新しい変数を宣言する代わりに、既存の変数を代入して再利用する方が良いでしょう。

SSAトランスフォームは、

open in Remix

let a := calldataload(0)
mstore(a, 1)

を、次の処理に書き換えます。

open in Remix

let a_1 := calldataload(0)
let a := a_1
mstore(a_1, 1)
let a_2 := calldataload(0x20)
a := a_2

問題は、 a が参照されるたびに、 a の代わりに a_1 という変数が使われることです。 SSAトランスフォームでは、このような形式の文を、宣言と代入を入れ替えるだけで変更します。 上のスニペットは次のように変わります。

open in Remix

let a := calldataload(0)
let a_1 := a
mstore(a_1, 1)
a := calldataload(0x20)
let a_2 := a

これは非常に単純な同値変換ですが、次にCommon Subexpression Eliminatorを実行すると、 a_1 のすべての出現箇所が a に置き換えられます（ a が再割り当てされるまで）。 その後、Unused Prunerが変数 a_1 を完全に除去し、SSAトランスフォームを完全に逆にします。

StackCompressor

Ethereum Virtual Machineのコード生成を難しくしている問題の1つは、式スタックを下にたどり着くためのスロットが16個という厳しい制限があることです。 これは多かれ少なかれ、16個のローカル変数に制限があることに通じます。 スタックコンプレッサは、YulのコードをEVMバイトコードにコンパイルします。 スタックの差が大きくなると、この現象がどの関数で起きたかを記録します。

このような問題を起こした関数ごとに、Rematerialiserに特別な依頼をして、値のコスト順にソートされた特定の変数を積極的に排除してもらいます。

失敗した場合は、この手続きを複数回繰り返します。

Rematerialiser

再物質化ステージでは、変数の参照を、その変数に最後に割り当てられた式で置き換えようとします。 これはもちろん、この式が比較的安価に評価できる場合にのみ有益です。 さらに、代入時点と使用時点の間で式の値が変化していない場合にのみ、意味的に等価となります。 このステージの主な利点は、変数を完全に排除することにつながる場合、スタックスロットを節約できることですが（後述）、式が非常に安価な場合、EVM上のDUPオペコードを節約することもできます。

Rematerialiserは、Dataflow Analyzerを使用して、常にmovableな変数の現在の値を追跡します。 値が非常に安い場合や、変数の削除が明示的に要求された場合、変数の参照はその現在の値で置き換えられます。

ForLoopConditionOutOfBody

ForLoopConditionIntoBodyの変換の逆です。

どのようなmovableな c に対しても、

for { ... } 1 { ... } {
if iszero(c) { break }
...
}

を、

for { ... } c { ... } {
...
}

にし、また、

for { ... } 1 { ... } {
if c { break }
...
}

を、

for { ... } iszero(c) { ... } {
...
}

にします。

LiteralRematerialiserは、このステップの前に実行する必要があります。