Microsoft PowerPoint - PLDI11

Size: px

Start display at page:

Download "Microsoft PowerPoint - PLDI11"

止冯
4 years ago
Views:

1 プログラミング言語処理系論 (11) Design and Implementation of Programming Language Processors 佐藤周行 ( 情報基盤センター / 電気系専攻融合情報学コース ) 1

2 最適化 (2 回目 ) 今回は Template call に関係する最適化次回は Xpath expressions の評価に関係する最適化実はアーキテクチャ独立の最適化の多くを包含する 2

3 Template Instantiation Template instantiation の最適化には 1 回あたりのオーバーヘッドを減らす回数を減らす実行を高速化する Evaluation of <xsl:apply-templates/> For each (target node) 1. select matching template (query required) 2. make frame 3. jump to the template 3

4 Procedure Call Optimization( 一般論 ) Interprocedural Optimization Dataflow across Calls Inlining (Inline Expansion, Procedure Integration) Save Call Overhead Tail Call Elimination Save Frame Overhead 4

5 NOTE: Template instantiation の場合実行されるテンプレートの検索のコストが大きい一般の言語ではこのコストはコンパイル時に解決されているならば以下が考えられる ( 後述するかも ) コンパイルして検索のコストを削減する検索そのものを高速化する 5

6 Inlining void a() { b(2); } Void a() { printf( %d n, 2+1); } void b(int x) { printf( %d n, x+1); } Void b(int x) { printf( %d n, x+1); } 6

7 Effect of Inlining Call Overhead Reduction Execution of Call: Arguments Stack Return address Stack Heavy Address of subroutine Program Counter Make frame Save registers Execute Destroy frame (stack unreel) Return address Program Counter Destroy arguments 7

8 Effect of Inlining(2) 発想じゃコールしないことにしよう展開されたコードは全体の中で最適化ができる Very Effective for small functions Methods Inline prefix in C++ Similar to macros 8

9 Effect of Inlining(3) Further Optimization across Calls Most optimizations are done within a procedure. Code Size Increase (Drawback) Harder Program Analysis (Drawback) 9

10 Effect of Inlining(4) Alias 問題とは何か? 変数に割り当てられているメモリ位置が他の変数によって参照されているかどうかを決定する問題 Alias problem in Fortran Fortran does not assume aliases among arguments (exists in reality, though) If inlined, Compiler must check if there is not any alias among arguments (often fails) Then, poor code may be generated. 10

11 Alias 問題は非常に特殊なacceleratorを持っているときに問題になる以下のプログラムでデータ依存性が発生するかもしれない int xx(int a[], int b[]) { int k; for (k = 0; k < 1000; k++) a[k+1] = b[k]; 11

12 C の場合 restrict 修飾子の追加 (C99) int xx(restrict int a[],restrict int b[]) Fortran と同等のコード生成がすでに可能 12

13 Inline 展開を行なうことによって関数コールでは最適化できなかった部分で最適化ができるかもしれない NOTE:Inline 展開は手で行なってはいけないマクロ inline 修飾子その他必ず言語 ( 処理系 ) の手助けを借りること 13

14 Inlining in XSLT <xsl:call-template name= a /> <xsl:with-param name= prefix select=.. /> <xsl:template name= a > <xsl:param name= prefix /> <path> <xsl:value-of select= $prefix /> / <xsl:value-of select=. /> <path> <xsl:value-of select=.. /> / <xsl:value-of select=. /> </path> 14

15 <call-template> に有効 <apply-templates> についても applyされるテンプレートが一意に定まれば特に有効 ( テンプレートを探すコストが削減できる ) DTDなどによってXML 文書の形式が定まっているとき一意に定まる機会が特に多くなる 15

16 実行する template の検索通常のプログラミング言語では生じないがたとえば <xsl:apply-templates select= MATCH /> <xsl:template match= MATCH /> が一致しているときわざわざ検索することはない 16

17 検索の最適化 foreach (xsl:apply-templatesのselect) { stylesheet 内のテンプレートのmatchと照合 if ( マッチするものが1つだけある ) { apply-templatesをcall-templateに置換する } } ( 実は部分評価と呼ばれるより一般的な評価手法の一つの例になっている ) 17

18 Tail Call Elimination まず観察してみる <xsl:template name= x > <xsl:param name= n /> <xsl:choose> <xsl:when test= > <xsl:call-template name= a /> <xsl:with-param name= $n /> </xsl:when> <xsl:otherwise> <xsl:call-template name= x /> <xsl:with-param name= $n 1 /> </xsl:otherwise> </xsl:choose> </xsl:template> 18

19 Tail Call Elimination(2) Return from template a immediate return Tail Call Return from template x immediate return Tail Recursion Used as LOOP. In this case, caller s frame can be destroyed at calls of a or x. However, Call is done, and a new frame is allocated for a and x. 19

20 Tail Call Elimination(3) 忠実な実行方法 destroy frame of x call of a jump to a make frame of a make frame of a execute execute destroy frame of a destroy frame of a return to x return from a destroy frame of x = return from x. return from x. 20

21 Tail Call Elimination(4) Before Elimination After Elimination frame Ret address call frame Ret address jump frame Ret address 21

22 Tail Call Elimination(5) This Optimization Requires a Jump to a procedure Low Level Stack Manipulation such as Frame Destruction Return Address Identification Are Required. 22

23 実装この最適化はGCCでも観察することができる ( 課題 15) 以下のコードからどのようなアセンブリコードが出てくるか観察しこの授業での説明がどのように実現されているかをあわせて観察せよ h(int x) { if (x ==0) return 0; else return g(x)+1; } g(int y) { return a(y+1); } 23

24 Tail Recursion Elimination Tail Recursion Tail Call Tail Call to Self. 実はこちらのほうはソース変換が可能 Most Programming Languages have goto construct Can do Source-to-source conversion Frame creation/destruction = rewrite local variables 24

25 Tail Recursion Elimination(2) Observation: int f(int n) int ff(int n) { {top: Jump if (n==0) return 0; if (n==0) return 0; else f(n-1); else {n=n-1; } goto top; } } Frame destruction/ creation 25

26 Tail Recursion Elimination(3) Before Optimization After Optimization n= Ret address call n= Ret address call n=n-1 Ret address 26

27 課題 16 以上のことはGCCにおいてでも実現されている課題 15にならって具体的にアセンブリコードを生成しそれを観察することによってこの最適化が実際にどう行なわれているかを解説せよ 27

28 Effect of Tail Call Elimination Save Frame Creation/Destruction Cost Save Space for Frame Creation Significant when LOOP is implemented as Tail Recursion (XSLT, most Functional Languages). 28

29 Tail Call Elimination in XSLT No GOTO Construct Source-to-source conversion Optimization of XSLT Engine Recognition of Tail Call/Recursion. Frame Adjustment, and Jump. 29

30 Tail Recursion Elimination in General int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } Not Tail Recursion 30

31 Tail Recursion Elimination in General(2) int fact2(int n, int res) { if (n==0) return res; else return fact2(n-1, n * res); } Tail Recursion 31

32 Tail Recursion Elimination in General(3) int fact2(int n, int res) { if (n==0) return res; else return fact2(n-1, n*res); } int fact(int n) { return fact2(n, 1);} int fact2(int n, int res) {top: if (n==0) return res; else { n = n-1; res = n * res; goto top; } int fact(int n) { return fact2(n,1);} 32

33 Tail Recursion Elimination in General(4) How to Rewrite non tail-recursion to tail-recursion. Commutative, associative operations Some Linearity in Call Introduction of Intermediate Variables. 33

Microsoft PowerPoint - PLDI7

Microsoft PowerPoint - PLDI7 プログラミング言語処理系論 (7) Design and Implementation of Programming Language Processors 佐藤周行 ( 情報基盤センター / 電気系専攻融合情報学コース ) 1 Why XSLT? この時間 ( と次の時間 ) は Formal な言語仕様を読めるようになるための直感的な理解を助けるために割かれます Formal な定義はここ