脱出分析

コンパイラの最適化において、エスケープ解析はポインタの動的スコープ （プログラム内のどこからポインタにアクセスできるのか）を決定する方法です。これはポインタ解析および形状解析に関連しています。

変数 (またはオブジェクト) がサブルーチン内に割り当てられると、変数へのポインターは他の実行スレッドまたは呼び出しサブルーチンにエスケープできます。実装が末尾呼び出し最適化 (通常、関数型言語に必要) を使用する場合、オブジェクトは呼び出されたサブルーチンにエスケープすると見なされることもあります。言語がファーストクラスの継続をサポートしている場合( SchemeやStandard ML of New Jerseyなど)、呼び出しスタックの一部もエスケープされる可能性があります。

サブルーチンがオブジェクトを割り当て、それへのポインターを返す場合、そのオブジェクトはプログラム内の不特定の場所からアクセスできます。つまり、ポインターが「エスケープ」していることになります。ポインターがグローバル変数または他のデータ構造に格納されている場合にも、ポインターはエスケープされ、その結果、現在のプロシージャーからエスケープされる可能性があります。

エスケープ分析では、ポインターを格納できるすべての場所と、ポインターの有効期間が現在のプロシージャおよび/またはスレッドのみに制限されているかどうかが判断されます。

コンパイラはエスケープ解析の結果を最適化の基礎として使うことができる: ^[1]

• ヒープ割り当てをスタック割り当てに変換する。^[2]オブジェクトがサブルーチン内に割り当てられ、オブジェクトへのポインタが決して逃げない場合、そのオブジェクトはヒープ割り当てではなくスタック割り当ての候補となる可能性がある。ガベージコレクション言語では、これによりコレクターの実行頻度を減らすことができる。
• 同期の省略。オブジェクトが 1 つのスレッドからのみアクセス可能であることが判明した場合、そのオブジェクトに対する操作は同期なしで実行できます。
• オブジェクトの分割またはスカラー置換。^[3]オブジェクトは、連続したメモリ構造として存在する必要のない方法でアクセスされることがあります。これにより、オブジェクトの一部（またはすべて）をメモリではなくCPUレジスタに格納できるようになります。

オブジェクト指向プログラミング言語では、動的コンパイラはエスケープ解析を実行するのに特に適しています。従来の静的コンパイルでは、メソッドのオーバーライドによりエスケープ解析が不可能になることがあります。呼び出されたメソッドは、ポインターのエスケープを許可するバージョンによってオーバーライドされる可能性があるためです。動的コンパイラは、オーバーロードに関する利用可能な情報を使用してエスケープ解析を実行し、関連するメソッドが動的コードロードによってオーバーライドされたときに解析をやり直すことができます。^[1]

Javaプログラミング言語の人気により、エスケープ解析が関心の対象となっている。Javaのヒープのみのオブジェクト割り当て、組み込みスレッド、Sun HotSpot動的コンパイラ、OpenJ9のジャストインタイムコンパイラ（JIT）の組み合わせは、エスケープ解析関連の最適化のための候補プラットフォームを作成する（Javaのエスケープ解析を参照）。エスケープ解析はJava Standard Edition 6に実装されている。一部のJVMは、部分エスケープ解析と呼ばれるより強力なエスケープ解析の変種をサポートしており、割り当てられたオブジェクトが関数のいくつかのパスから脱出した場合でも、そのオブジェクトのスカラー置換を可能にする。^[4]

クラス Main { public static void main ( String [] args ) { example (); } public static void example () { Foo foo = new Foo (); //alloc Bar bar = new Bar (); //alloc bar . setFoo ( foo ); } } 
         
        
    
        
             
             
        
    


クラス Foo {} 

クラス Bar { private Foo foo ; public void setFoo ( Foo foo ) { this . foo = foo ; } } 
      
        
          
    

この例では、2 つのオブジェクトが作成され (alloc でコメント化)、そのうちの 1 つが別のメソッドの引数として渡されます。メソッドは、setFoo()受け取った Foo オブジェクトへの参照を格納します。Bar オブジェクトがヒープ上にある場合、Foo への参照はエスケープされます。ただし、この場合、コンパイラはエスケープ解析を使用して、Bar オブジェクト自体は の呼び出しをエスケープしないことを判断できますexample()。その結果、Foo への参照もエスケープできず、コンパイラは両方のオブジェクトをスタックに安全に割り当てることができます。

次の例では、ベクトルp はgにエスケープされないので、スタック上に割り当てておき、g を呼び出す前にスタックから削除することができます。

(定義( f x ) ( let ( ( p (ベクトル作成10000 ))) (ベクトル充填pに良いスタッフを詰め込む) ( g (ベクトル参照p 7023 ))))  
      
       
         

しかし、もし私たちが

( define ( f x ) ( let (( p ( make-vector 10000 ))) ( fill-vector-with-good-stuff p ) ( g p )))  
      
       
       

その場合、p をヒープ上に割り当てるか、( fのコンパイル時にg がコンパイラに認識されていて、正常に動作する場合) gが呼び出されたときに p がそのまま残るような方法でスタック上に割り当てる必要があります。

継続が例外のような制御構造を実装するために使用されている場合、エスケープ解析はこれを検出して、実際に継続を割り当てて呼び出しスタックをコピーする必要を回避できることが多い。たとえば、

;;ユーザーが入力したスキーム オブジェクトを読み取ります。すべてが数値の場合、
;;すべてを順番に含むリストを返します。ユーザーが
数値以外のものを入力した場合は、すぐに #f を返します。
( define ( getnumlist ) ( call/cc ( lambda ( continuation ) ( define ( get-numbers ) ( let (( next-object ( read ))) ( cond (( eof-object? next-object ) ' ()) (( number? next-object ) ( cons next-object ( get-numbers ))) ( else ( continuation #f ))))) ( get-numbers )))) 
    
     
         
          
               
                 
               
    

エスケープ解析では、 call/ccによってキャプチャされた継続がエスケープされないことが判断されるため、継続構造を割り当てる必要はなく、継続の呼び出しによる継続の呼び出しはスタックを巻き戻すことによって実装できます。

• エイリアス分析
• ポインタ解析
• 形状分析