跳至內容

逃逸分析

維基百科,自由的百科全書

在編譯程序優化理論中,逃逸分析是一種確定指針動態範圍的方法——分析在程序的哪些地方可以訪問到指針。它涉及到指針分析和形狀分析。

當一個變量(或對象)在子程序中被分配時,一個指向變量的指針可能逃逸到其它執行線程中,或是返回到調用者子程序。如果使用尾遞歸優化(通常在函數編程語言中是需要的),對象也可以看作逃逸到被調用的子程序中。如果一種語言支持第一類型的續體Scheme新澤西Standard ML中同樣如此),部分調用棧也可能發生逃逸。

如果一個子程序分配一個對象並返回一個該對象的指針,該對象可能在程序中被訪問到的地方無法確定——這樣指針就成功「逃逸」了。如果指針存儲在全局變量或者其它數據結構中,因為全局變量是可以在當前子程序之外訪問的,此時指針也發生了逃逸。

逃逸分析確定某個指針可以存儲的所有地方,以及確定能否保證指針的生命周期只在當前進程或線程中。

優化

編譯器可以使用逃逸分析的結果作為優化的基礎:[1]

  • 將堆分配轉化為棧分配。如果某個對象在子程序中被分配,並且指向該對象的指針永遠不會逃逸,該對象就可以在分配在棧上,而不是在堆上。在有垃圾收集的語言中,這種優化可以降低垃圾收集器運行的頻率。
  • 同步消除。如果發現某個對象只能從一個線程可訪問,那麼在這個對象上的操作可以不需要同步。
  • 分離對象或標量替換。如果某個對象的訪問方式不要求該對象是一個連續的內存結構,那麼對象的部分(或全部)可以不存儲在內存,而是存儲在CPU寄存器中。

實際問題

在面向對象的編程語言中,動態編譯器特別適合使用逃逸分析。在傳統的靜態編譯中,方法重寫使逃逸分析變得不可能,任何調用方法可能被一個允許指針逃逸的版本重寫。動態編譯器可以使用重載信息來執行逃逸分析,並且當相關方法被動態代碼加載重寫時,會重新執行分析。[1]

Java編程語言的流行使得逃逸分析成為一個研究熱點。Java的堆分配、內置線程和Sun HotSpot動態編譯器的結合創建了一個關於逃逸分析優化的候選平台。逃逸分析最早是在Java標準版6中實現的。

例子 (Java)

class 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);   
  }
}  
class Foo {}  
class Bar {   
  private Foo foo;   
  public void setFoo(Foo foo) {     
    this.foo = foo;   
  }
}

在這個示例中,創建了兩個對象(用alloc注釋),其中一個作為方法的參數。方法setFoo()接收到foo參數後,保存Foo對象的引用。如果Bar對象保存在堆中,那麼Foo的引用將逃逸。但在這種情況下,編譯器可以使用逃逸分析確定Bar對象本身並沒有逃逸example()的調用。這意味着Foo引用無法逃逸。因此,編譯器可以安全地在棧上分配兩個對象。

例子(Scheme)

在接下來的例子中,向量p不逃入g,所以它可以分配在棧上,然後在調用g之前從棧中刪除。

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

然而,如果有

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

然後p需要分配在堆上或(如果當f被編譯時,編譯器知道g )分配在棧上,如此需要做出改變,即在g被調用時,可以保持g。 如果計算續體(continuations)用於實現異常控制結構,逃逸分析通常可以發現以避免必須分配一個計算續體(continuation)並複製調用棧。例如,在

;;读取用户输入的scheme对象。如果所有的数字,
;;返回一个列表,有序包含所有。如果用户输入一个
;;不是一个数字,立即返回#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捕獲的continuation不會逃逸,所以沒有continuation結構需要被分配,喚醒continuation可以通過刪除棧來實現。

參考資料

  1. ^ 1.0 1.1 T. Kotzmann and H. Mössenböck, 「Escape analysis in the context of dynamic compilation and deoptimization,」 in Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, New York, NY, USA, 2005, pp. 111–120.