spa99.dvi

Size: px

Start display at page:

Download "spa99.dvi"

なおおえづか
5 years ago
Views:

1 2 SPA 99 Java Java 1 ( specialization) (partial evaluation) [6, 8] ( ) (run-time specialization 1 ) [2 5, 9, 10, 12, 13] (bytecode specialization) Java (JVM)[11] (1) (2) ( ) ( ) Just-In-Time (JIT) Java JVM ([7] ) / Stata Abadi [14] JVM 1 Run-time code generation dynamic code generation 1

2 (binding-time analysis) (specialization) 2 ( /static ) 2 ( /dynamic ) Java : class Power { static int power(int x, int n) { if (n==0) return 1; else return x*power(x,n-1); } } n x n==0 n-1 power return then 1 x*power(...) ( ) power n =3 n==0 n-1 power x * 1 ( ) x*(x*(x*1)) (a) (b) (static input) ( specialized ) ( 1 (a)) (annotated source) ( 1 (b)) (dynamic expression) (specializer) (1) (2) 2 2

3 (a) Partial Evaluation. source binding time analysis annotated source static input partial evaluation (interpretive) specialized compilation specialized static input source machine code (b) Run-Time Specialization. source binding time analysis annotated source dynamic dynamic expression expression compilation specializer compilation specializer specialized 1: 1 [3 5, 9, 10, 12] Intel x86 power (1) (2)if then (3)else (4) 2 ( ) ( ) n =3 1,1,1,1,2,4,3,4,3,4,3,4 (1) (2) then (3) else (4) pushl %ebp movl %esp,%ebp pushl %ebx movl 4(%ebp),%ebx movl $1,%eax pushl %ebx imull %ebx,%eax movl -4(%ebp),%ebx movl %ebp,%esp popl %ebp 2: ( ) 3 / power : (i) else power x (pushl %ebx) (ii) x (%ebx) 3 (7 ) 3 Strength reduction [9] 3

4 [15, 16] BCS: (BCS: bytecode specialization) Just-In-Time ([1] ) source bytecode machine code static input source compiled annotated bytecode compilation binding-time analysis dynamic instructions specializer specializer JIT compilation specialized specialized JIT compilation 3: Java (JVM) JVM JIT 3 Java (compiled ) (specializer) JIT ( ) (dynamic instructions) (specialized ) JIT 4

5 4 : JVMLi 4.1 Java (JVML ) JVMLi JVMLi JVML int (static ) (jsr ret ) JVMLi arity 0 7 : instruction ::= iconst n iadd iload x istroe x ifne L invoke mn ireturn : iconst n n iadd 2 (isub, imul, idiv) iload x x istore x x ifne L 0 L invoke m n n m 4 (1) (2) n 0,...,(n 1) (3) m 0 ireturn invoke invoke power JVMLi 4 Method int Power.power(int,int) 0 iload 1 // n 1 ifne 4 // n 0 2 iconst 1 // n =0 1 3 ireturn // 4 iload 0 // n 0 : x 5 iload 0 // x ( 1 ) 6 iload 1 // n 7 iconst 1 // 1 8 isub // n 1 ( 2 ) 9 invoke Power.power 2 // 10 imul // (x ) 11 ireturn // 4: JVMLi power JVMLi ( ) JVML (1) 4 JVML invokestatic 5

6 P [pc] =iconst n F pc F pc+1 T pc+1 = α T pc B[pc] α P [pc] =iadd F pc F pc+1 T pc = α B[pc] σ T pc+1 = β σ α B[pc] β P [pc] =iload x F pc F pc+1 T pc +1 = α T pc F pc [x] =B[pc] α P [pc] =istore x F pc [x B[pc]] F pc+1 α T pc+1 = T pc α B[pc] P [pc] =ifne L F pc F pc+1, F pc F L α T L = α T pc +1 = T pc α B[pc] P [pc] =invoke mn F pc F pc+1 T pc = A m [n 1] A m [0] σ T pc+1 = α σ R[m] α P [pc] =ireturn T pc = α ɛ α R[m] pc = m, i 5: 1 (2) / / Stata Abadi JVM [14] 5 / / / ( ) 5.2 S ( ) D( ) S D α,β,... S D ɛ σ α α σ f f[x α] : (f[x α])[y] =ifx = y then α else f[y] 5 A, R, B, F, T pc P pc m i m, i : m, i +1 m, i +1 6 A, R A[m][n] m n R[m] m A[m][n] A m [n] B,F, T / / F pc,t pc pc / 5 6 JVMLi 6

7 iconst, iadd, iload, invoke lift iadd, istore, ifne lift : F F x Dom(F ).F [x]=f [x]. (Dom(F ) F ) lift invoke monovariant ireturn : 0 : pc Dom(P ).pc = m, i, A,R,B,F,T,pc P T m,0 = ɛ F m,0 =[j A m [j],... j Dom(Am) ] A, R, B, F, T, m P. : x y if (x==0) { z = f(y); } else { z = g(y); } f(y) g(y) if z x ( ) P [pc] =if L then/else M pc pc M pc then/else istore l pc =[x 1,x 2,...] pc then/else n pc : {}}{ pc M pc.b[pc] β pc, T pc = β pc β pc σ, x l pc.f pc [x] =β pc. n pc 5.3 power x n A[Power.power] =[0 D, 1 S] 6 n( 1) 7

8 P B T iload 1 S ɛ ifne L2 S S ɛ L1 : iconst 1 D ɛ goto L0 S D ɛ L2 : iload 0 D ɛ iload 0 D D ɛ iload 1 S D D ɛ P B T iconst 1 S S D D ɛ isub S S S D D ɛ invoke Power.power 2 S S D D ɛ imul D D D ɛ goto L0 S D ɛ L0 : ireturn S D ɛ R[Power.power] = D pc Dom(F ).F [pc] =[0 D,1 S] 6: power 6 JVML Java JVMLi 6 : instruction g ::= instruction GEN instruction LIFT LABEL L SAVE n [x 0,...] RESTORE INVOKEGEN m [x 0,...] : i i i GEN i GEN i i i LIFT (1) P [pc] B[pc] =S T [pc +1]=D σ (2) P [pc] B[pc] =D T [pc] =S σ LIFT (1) (2) LIFT n iconst n 2 int mult(int, int) 1 2 7(a) P B T 0 iload 0 S ɛ 1 iload 1 D D ɛ 2 imul D D D ɛ 3 ireturn S D ɛ F pc =[0 S, 1 D] mult gen(int) 0 iload 0 1 LIFT 2 GEN iload 1 3 GEN imul 4 ireturn (a) int mult(int,int) (b) 7: LIFT 0 S 0 iload S (imul ) D 7(b) LIFT 8

9 mult_gen(3) LIFT ( 3) iconst iconst 3; iload 1; imul invoke m INVOKEGEN m [x 0,x 1,...] x 0,x 1,... INVOKEGEN (1)x 0,x 1,... m (2) m (3) x 0,x 1,... ifne L (1) GEN ifne L; SAVE n [x 0,x 1,...] (2) L LABEL L; RESTORE n [x 0,x 1,...] then SAVE n x 0,x 1,... RESTORE SAVE power power_gen 8 Method Power.power_gen(int) iload_1 ifne L5 L2:GEN iconst_1 L4:ireturn L5:GEN iload_0 GEN iload_0 iload_1 iconst_1 isub INVOKEGEN Power.power_gen 2 [0] GEN imul L13:ireturn 8: (1) byte[] code (2)code int i (3) 7 ConstantPool cp 3 code[i] i power A n =2 power 9 JIT Method int power(int) 0 iload_0 1 iload_0 2 istore_1 3 iload_0 4 iload_1 5 istore_0 6 iload_0 7 iload_0 8 istore_1 9 iload_0 10 iload_1 11 istore_0 12 iconst_1 13 istore_1 14 istore_0 15 iload_1 16 imul 17 istore_1 18 istore_0 19 iload_1 20 imul 21 ireturn 9: power 7 JVML JVMLi Java Java 7 JVM constant pool 9

10 power(x,30) (1) (2)BCS (3) C 2 PC (PentiumII 300MHz 256MB MS-Windows NT) Sun JDK (+ Symantec JIT ) Cygnus GCC BCS JIT JIT (C) JIT JIT a b c : power(x,30) (µ ) 1( ) JIT BCS 3 JIT BCS (C ) / 1( ) BCS (a) (b) (c) JIT JIT (c) JIT 8 Wickline CAM [17] Fabius [9, 10] icode [12] Sperber Thiemann [13] 9 (1) (2) JVML 10

11 / Stata Abadi [14] JVML JVML monovariant polyvariant [1] A.-R. Adl-Tabatabai, M. Cierniak, G.-Y. Lueh, V. M. Parikh, and J. M. Stichnoth. Fast, effective code generation in a just-in-time Java compiler. In PLDI 98, pp , [2] C. Consel and F. Noël. A general approach for run-time specialization and its application to C. In POPL 96, pp , [3] D. R. Engler. VCODE: a retargetable, extensible, very fast dynamic code generation system. In PLDI 96, pp , [4] D. R. Engler and T. A. Proebsting. DCG: An efficient, retargetable dynamic code generation system. In ASPLOS 94, pp , [5].., 15(5):25 37, Sept [6] Y. Futamura. Partial evaluation of computation process an approach to a compiler-compiler. Systems, Computers, Controls, 2(5):45 50, [7] J. C. Hardwick and J. Sipelstein. Java as an intermediate language. Technical Report CMU-CS , School of Computer Science, Carnegie Mellon University, [8] N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, [9] P. Lee and M. Leone. Optimizing ML with run-time code generation. In PLDI 96, pp , [10] M. Leone and P. Lee. Lightweight run-time code generation. In PEPM 94, pp , [11] T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley, [12] M. Poletto, D. R. Engler, and M. F. Kaashoek. tcc: A system for fast, flexible, and high-level dynamic code generation. In PLDI 97, pp , [13] M. Sperber and P. Thiemann. Two for the price of one: Composing partial evaluation and compilation. In PLDI 97, pp , [14] R. Stata and M. Abadi. A type system for Java bytecode subroutines. In POPL 98, pp , [15],,.. (SPA 98), [16] Y. Sugita, H. Masuhara, K. Harada, and A. Yonezawa. On-the-fly specialization of reflective s using dynamic code generation techniques. In Workshop on Reflective Programming in C++ and Java, pp , [17] P. Wickline, P. Lee, and F. Pfenning. Run-time code generation and Modal-ML. In PLDI 98, pp , A 8 JVM power_gen 1 power constant pool 11

12 JVM method int[] Power.power gen(int, byte[], int, ConstantPool) // set stack depth iconst_2 istore 4 L0: iload_0 L1: ifne L5 // GEN iconst_1 L2: iconst_4 // return index & depth L3: iconst_2 newarray int dup iconst_0 iastore dup iconst_1 iload 4 iastore areturn // GEN iload_0 L5: bipush 27 // GEN iload_0 L6: bipush 27 L7: iload_0 L8: iconst_1 L9: isub // INVOKEGEN Power. // power_gen 2 [0] // GEN istore_2 L10: bipush 61 // GEN iload_1 bipush 27 // GEN bipush 28 // GEN istore_1 bipush 60 // extra arguments aload_3 invoke Power.power_gen // extract index dup iconst_0 iaload istore_2 // extract&update depth iconst_1 iaload iconst_2 iadd dup iload 4 if_icmpgt L14 pop iload 4 L14:istore 4 // GEN istore_2 bipush 61 // GEN istore_1 bipush 60 // GEN bipush 28 // GEN imul L11: bipush 104 // return index & depth L12:iconst_2 newarray int dup iconst_0 iastore dup iconst_1 iload 4 iastore areturn 12

Java

Java JAIST Reposi https://dspace.j Title 軽いハードウェアによる Java 高速化手法に関する研究 Author(s) 吉兼, 寛 Citation Issue Date 2004-03 Type Thesis or Dissertation Text version author URL http://hdl.handle.net/10119/1775 Rights