(509)1    Java            !

"$# %'&(*) +-,

0. /210324257628092:2;=<?>A@B.0/210324AC0;2@0DBE
F @2G=HJIA10KBLM@ONAP FAQARTS 5VU0W2XZY\[2]?^V_B`
a2b0c 57d2e2f0gB>7hZij@Tk?l2KnmToB^7p2qB`7;2<0r2stvuxwzy|{z}x~T|Z X  @ c 5|Ji=>Vv 5VrvT
m2o?Ap0Z 7B 5 b2? @THB FM0Z 50B7K2E
 I720BA7 u  A .0/212304257;2<2s?5 u0w > K0 20Bb > HB F2Z ^7z2`7G   68290:B7¡2¢  @ c 5A;2<=r0sB5 u0w ?2£Ar0sB57¤2¥
A¦?§ 7
.0/2¨ª10©¬32«®4A6T­ 8092:0;2<B>7@  \¯B237°2±0²B5VHZI
2³?   A}0´ b KBiµ@z.2/2103247C2;2@?.2/0123
4nG=H¶In1¸·¹[=]=º2K»L¼@ c 5Ad=e=f=gx>¾½ ~  À¿¼{xabAu0wBy7{B} 0`A608292:=;0<2r2s?>A@0Á2Â2m0oB5?N E =OÄÃ Å0Æ =Z Ap=  n}0~Ç Èa2 .=/12304257½2É2Ê0²ÌËÎÍ2Ï2²x^?  K0A@ON  E0.2/0123
427p2OMqB`7Ð2Ñ062829=:0;2< b >AÒ0ÓBKA;0<2Ô0ÕBÖB` ¿  tB×AØ ^2K  @  `VÙ2¡B57Ú2Û?^AB0`2.0/21
Java

13[1]

A Method of Data Dependence Analysis of Java
Bytecode.
Kenji KONDA,, Graduate
School of Engineering Science, Osaka University.
Fumiaki OHATA,, Graduate School of Engineering Science, Osaka University.
Katsuro INOUE,/, Graduate Schoolof Engineering Science, Osaka University / Graduate School of Information Science, Nara Institute ofScience and Technology.

30425A¤0¦2ñ0òBAp0 MqB`7ó2Ñ0628290:2;0<B5Aô0õ t
Á a § } 0` O¿ 52B7KAó=Ñ260829=:2;0<B.T/01T3T42^Vp V} ±0eTqB`Vö?^T>V@ ÷¬øAù?úAû
@¾ÿ=@ºü?ýÇþ ·|5  t  õ   bT ` Z X  @t ÷ Tø ·@ ÿ T@=Hz F
=  º >n@ÈE  In=2x  b 5A¤=¦ t  u nK0§}   @ 2r0sB7±2e 7T´ b >2E  I72  AG   608290:B =qB` ¿ A> b2~ K0 ?a2 @0HB
F\2Z ^A?2`A608T92:?^A92q?` Z 7} >t? ` t @2608292:?5n¡2¢ t  Y {B} 2` ´ b @2¤
ö?5 !#"7r2s?^ $B } > %ZY {B} 2K2   b >7@2HB F¼2Z ^A?2`&'B)E (2I + * 5G   608290:BA¡0¢  @ c 5 !)"Ar2s? u0w qB` Ba
 @ u2w r2s?^ ,- ~ @2HB FM0Z 7Ú2ÛOMqB`7G 
 6282;0#< .  / 1 032  @ S /)4#56 427¤2öB^7ó 2
1y 7B} 80Aÿ 92@ b HB F\2O B0£ c?¿ ^78 :0qB`AG  608292:?^ $x 1} ;< qB`  b G   6280;2<2r0sB5u0w x2£ c 57¤2¥?=^ $? >}  `  ° ?B^ b2a  @+ A?B15 BC?^ $B >}  ` Java [2]Java

Java Virtual Machine

JavaVM[3]

JavaVM

Java BytecodeJava[3][6] [5]

2.

3.

4.

ÜÞÝßÜáàßÜáàßâßãáäßåáàßæßçáèDFEHGIKJML NKOPJRQTSVURWPXÜÞÝßÜáàßÜáàßâßãáäßåáàßæßçáè÷Y+2øZì è¾à¾í¾î¾Ü¾à¾â¾Ü¾Üáà¾Ý¾ï¾Ü¾ð¾àßè¾Ü¾à¾à¾æ¾âáç¾ã¾èäßå¾à¾æßç¾è é¾êßë 032^2 b [ 0X 32{zE2 P)N \A  /ET.T^1]/v^ 1TyA3v{ 4T` >V @ 032E2P)\A¯ p cTq `Tv3TEv^V9  / >Tx3T_E & `¬^ ab y|{ @2 G   ?T£VHz FTJ 5 d eTòz fRg BczV} @t 23=E0hP \n / > i 81jh8 @ HB F¼2Z 
2

2.1

JavaJavaVM

Java kl   NAP FAQAR0S

2....

monqpsronut
vxwyoronutz 1 {|~}xuPTsuu

istore 1s

....
....
................
....

t1

x

iload 1

1

iload 1

1t

stack

3
stack
30
1
3
memoryistore_12v

y01memoryiconst_3

Data

istore 1

field_xz 3 øuùusì~qîsïuðTñsò uósôõuïu÷2.2

Dependence Relation

stack

memory3v

yygetfield Point/x I

1tfield_x
memory200sstackyputfield Point/x I

samplevxz 2 ê uëìuuíTîsïðTñsòTuóôöõuï÷;Í0@2¤0¦2qB` >  ¯zv3ÎRÏ Ð_Ñ 5Tz=^V@)ÒzNTI ^2  N  E 0Z XZYMHx FM2O ^1]^ y7{ `  H
 FnT  >V¬ c Ó)Ô 5 devXJ>Y Õb y={¬}  @ Ö ^ × ÖTÑ?K deJ c 5Aó 2z ØRÙ0` xaT HB
FM0Z ^2>AG    ÚÛ3ÜBK ]ÝZ A} @?P Þ  /
 @B/  ß1/ ]Ý0@BE  IA05 ÓÔ t? ` à0ø á1âãäå
d3e b ¡=¢ yA{x / ß>/ ]Ý 5>æ t d3e b>ç3èyn{ `» ~ @ X Y ^ ^92qx` àÇ3ø á>â3ã3äå ·º t )8 :xq¬`O|   Ñ b >|@^=  E  In F IA.0=5 æ t /  ß=/ ]3Ý
^ ×0Ú · ¡2¢Tº y7{ @^2  /  ß1/ ]Ý 5
æ t E  I7 F I7.2^0.BIA l¸· çè º yA{?} T` Z¿
5z ~ @15 éz^T/  ß/ ] Ý ^92q?`AG   608290: t 38 :0qB` d e b ¡T¢ yV{z P Þ  /  5 æ t d e b çèsstack01xmemory

iload_1

 1 {u|}xuPx uuu
=
=
pop
uT_=s¡¢£¤¥¦s§ n ¡u=¨©sªiconst n« =¬­=®§ n ¯° ¡x_=¨©sªiload n
istore nu±x²³´ T_=s¡¢£¤¡ « =¬x­=®§ n ¨µ¶=·u¸¹sº=­h» ¯° ¡x_x=¨©ªgetfield
u±x²³´ T_=s¡¢£¤putfield¡¹=ºs­h»¨µs¶=·_¸
u±x²³´ T_=s¡ 2 ¼ ¢T£¤iadd ¯½=¾s¿=À ¡u=¨©=ªu±x²³´ T_=s¡ 2 ¼ ¢T£¤idiv ¯ ¤ ¾s¿=À ¡u=¨©=ªu±x²³´ T_=´us¡Ç 2 ¼ ¢T£¤if icmpne LnÈxÉ ­ LnÂ¨Á=Ê=ÃË=ÄuÌ ¥ Å·uÆ ¸
1

x0
1
x
memoryistore_1................

int sample(int a,int b){if(a == b) a = 3;
else a = 4;
return(a);}iload_1
iload_2
if_icmpne L10
iconst_3
istore_1
goto L12
JavaCompiler L10: iconst_4
istore_1
L12: iload_1
ireturn(510)stackz 4 úTóûuüuîsïuð ñsòTuósôõöïu÷

Vy { `¬ ~ @ XZY ^ ^V9Tq `VG   6T8v9T: t 8:0q»`?nB  Ñ b >A@^2 E  IV F IA.T51æ t PÞ /  ^×TÚ · ¡T¢0º y^T  P Þ _ /Ì _5 æ t{@E  IA F IA.v^?.BI7 l¸· çhè º y0{ } ?` Z¿ 5~@
15 é»^03P Þ 1 /  ^V9=qB`7G   62829=: t 8 :2qx` aT @ d e b E  IA z^ ý aV{z æ t d e b çè?y¾{ `x ~ @ XZY ^0E  In0^A9=qB`nG   628=9: t 38 :2q?`BnB  Ñ b >7@^=  E  I
T^T.?IA l¸· ¡T¢Tº yV{z æ t^T0§ } ç
>5 éx^2E  I¾=^èxyn{ `  @n@90qB`AG   628290: t 8 :0qB` stv

3

putfield Point/x I
xyx

getfield Point/x I

putfield Point/x I

getfield Point/x Ix

stst

4

iconst 3

istore 1

iconst 3

istore 12 BOVb7JVu2wQqBSV`AUPH?þR ÿFM2O ^7p2qB`7G   6280;2<r0sB>A@0ÿ?5 $?52E7DZIA. b Õb yA{ ` 32b Õ V 5!?  LV` ¿ V^T  @2G  628T92:z51!R"A?T£ g 5VG   6T8B5!hiV¦J ;T<z>V¤T¦ Üjz5  `!k } 5!lm^7p A} ¦B7@ -  KnG   628092: t !#" yA{ K?iAK` a2b ?2`  ÿ 0@nBP RT3 6  o p?^  ` >V@ ?5Vr2 ~ ?.T/21T3T42^Vp0qz`Vr2s V±2eqz` ¿  t Ü bT? @ Ñ ^ S/#4R516 425!"z# G   6v8vq9xr:z5_sn!ø t"vu|¦ v |^ v¬ @  Ò N0I q ?aT @ ¿ 5 S1/R4#56 40 Ñ V5 Hz FMTO ^A± * 5xP Þ  / ¼Ã /  ß_/ ]Ýv@BE  I73 z<5 æ te 7$%  Ñ ^#2q L|5 de b ¡T¢ yV{  X¬Vx[ wTq¬` Ö · qrys=øtºO] z{=º?=}e |vq `  ;v<OP ( ·4v>V@ ]Ý~xzv£ c 5 æ V° ?z^=¡T¢ V d e 5V¦>(@0^Aà0@2øG á â ã62ä82å;=&<?^A' eB0`A;0<BP#(  40) Å 5VpB!5  b2 `  Ñ >A@TH? F2J z2£ c*Tqz`
+ V^ @2;T<zPR(  4T!,-  K t Y 5 ¦ V5 d ezV;T<   Ï !  zb 5V;T<zRP ( 40 # V} 2`  P Þ  /  > 0¡2¢T@?/  ß1/ ] Ý. ì0/214365> ¦ A5b @ > ¦ V57!8:9<; >==_»
b @ > ¦ A5 ^==§ } ¡2¢ yA{?B¿ A?8Ö^@!A 9<; >==_»¨>BÄ ¡DCFE=·_¸V} v`  ^V9 V} >V@ ¦ |5G u ¡FHIuÄ ²!
L  æ t ¡2¢ yA{ ` t @ ¦ n5 ^V  æ nt Zb J6KT¡
M6J6K ¯
NFO
X { `  @A@ 2¡2¢OnK2` W
NOT´
V!5 Tkz^T  @0ÙT¡z5VÓ TXJ]Y  a V ÓJK ¯¡QX6I¯QP ¨>RTS<U ¸l m t  0qB` Æ  b 52E  I7 B 6 > l mB^7628
# ¨Y ¡FZ¥7nnZ  TaÇ @6ÒxN2I  5T=C?^  õxK2/ 3ß
/ ]ÝB5 Ý Ã °2½?E  IV] B 6 >  M¯?232^0 z . ì/01>365
 YMX (1@ yA{?} 2`  @A@0;2<B)P (  425A½ ~2y>7Ð2ÑB^ 2¡0qB` ¿  tBb2~ ` []\]^`_ba`cbdbebf
G   6T82à09Tø :zá51â3!Rã"Tä>Aå@ &' b e| 7 ;T<BP(  4A?2£7@B.2/01=324257U  B7Ú2ÛO A} @ Ñ!^ #Tq S /#4R56 41^ B§ } ¦{`¿ 5 S /)4#516 42> n2ÑB^7±2e yA{ ` (511)Vol. 8 No. 6 Nov. 1991 0ø ·    :@ ÿ ¶@ºZ0¬øControl Flow Graph>0@0HO F7»  ^0p Ç} P?/  ;?<CFGA¦?A@ de?2 @d3eéB5  52 óB bÖT¥ V? 5 bT `  Hz F\TZ ^7p2qz` CFG Õ
Step1

3

Step1

CFG

CFG

(Phase2)

Phase1[1]

51

6Analysis Frame

Step2

:

7(Phase1)

1 80ConstructCFG

08(N :)
foreach n in N beginnCFG
foreach n0 in N 0nn0 CFG
end78N05

iload 0idiv

stack 0

CFG
CFG

(1)

stack 2

istore 0

stack 1

CFG

(2)
(3)
(4)
(5)
(6)

4

iload 0idiv

JavaVM[3]

ConstructCFG

5

iload_1

Phase2

iload_2

Phase1

if_icmpne L10

8

iconst_3

AnalyzeDD

L10 iconst_4

istore_1
istore_1
goto L12

L12

iload_1

ireturnz 6 z 1  CFG

1: iload_0
2: iconst_9
3: iadd
4: istore_0
5: iload_0
6: iconst_27: iload_0
8: idiv
9: imul
10: istore_0

field_0

undef

local_0

4

stack_0
stack_1
stack_2

undef
85z 7 6Tø0s 5 kl   NAP FAQAR0S

(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)

return
else
fn
endif
endif
fCFGn
CFG
foreach n0 in N 0 beginf0
fAnalyzeDD(n0 , f 0 )
end

(i)

local_0

undef

stack_0
stack_1

undef2

iload_1

iload_2

iconst_3

(8)

xxts

CFGsxxx(iii) iconst ns

iload n1sp(iv) iaddidiv1

sp9

istore 0

iconst 60

CFG0istore 03

....
....
local_03

stack_0
stack_1

undefundef×ÃØÚÙÍÛÝÜßÞáàáâäãåçæäèêéÍëäìÚíêîäï Üáð æòñçóáôõ ñòöÍ÷ÍíÍîáø Üáð æùñÝóáôL10 iconst_4

istore_1
istore_1
goto L12(iv)

(ii)

t

ÉQÊËÌÍ¿ÀÎQÆÀÏÀÐ

if_icmpne L10(iii)s2: iconst_6
3: istore_00z 8 . ì0/1>365 AnalyzeDD4¾À¿ÁÃÂQÄÀÅÀÆÀÇÀÈ

3: istore_0¡>³T´_ÄQµ´W=V >¤T¥ Y ¡¨¶¦ ½
J²K ¯ NTO N ¡>X¢I¯QP >¨ RTS<U ¸Q¯ ·F¸ ¡ W LAnalyzeDD(ii)2: iconst_6z 9 6Tø0F5TFÑ6ÒÓsòTuósôõ²ÔT Õ6Ö¯ W ¹6¡©£T®W¯¨ ¡©¦ ½

5 b >n@=d3ex5 Ó3Ô ^S>/45>6 4c( } ÿ ?5 $?5!2C¹A¦J ?2´B x2£>A@ Ã 52CO2  ^A¦ { ` de b ]Ý t çèByA{ `? ~;T<BRP (  4T5 ^7p cTqB`T³z F5 t d e bT`z ~ @ de XJY d e ^VG   6T829T: t 8 :qz` ¿  t Ó2X  @Tp c0qz`  éz^ ^V9qBde`7G b  ] Ý 628 t ¡0¹¢ hnyAi0{ qB`?`  ~;2<?RP (  4T5 ^Ap c0qB`T³? F 5 ¹de 5V¦Å  ^ ] ,0Ã qB`  KzLn@?E  IA g 5x.?IAl¹ºO de?5B ~E  I7 F I7. ¹]» ¼=q?¢` ½0B  5 æx¹ $Ù2`
Ã KxLM@xE  IA7X Y75 ½?IA. ¹]ºO deB5? ~;2<?#P (  4250E  I7 F IV.=5 ]ÝB52³? 1F 5 ¹
2¡0¢B^Aq?`B0  ^ 5 æ¹ $#Ù0` >Ñ ^0® } @b ¡?¢ y0{®G   ¹TE  IA7XZY ½zIA.  @B/  ß/ ]Ý ¹A¡T¢A} 2` Bc 5  @7@ ¿M{ Y75 deéB>7G   628092:t 8 :  @2p c0qz`  éB!^  t hi yA{ `  i
P (  4250/  ß/ ]Ý ^Vp c0qB`0³z FÏ } @2;0<BR5V¦ Å  bT ` ^|@BE  IA F IA.T^
5 t(i)....

. ì0/214365 AnalyzeDD
7!8 JWK n²TT ¹¢¡ Q£ f?8´<§È@!A _W =>¹6¤T¡ ¥ ©£Y ÁF¡>ª¢¦ ½ «©=¬ U _=Ês>¤TË¥ ¹ Y « T¨¡Q¦ ½ ·_¹ ¸OT­ K then begin(1) if n Á CFG ¯D(2)if f Á n ¯¹!¡ >£ ®F¯ö¨©°²± ´ ¬²«¸ then(512)....

4L12iload_1ireturnú 10 û6ü6ý6þ ÿ     CFG !#"$&%'(*)+,*-*.
984:AnalyzeDD / (1) (7) 0*1 CFG 2436587
G C '*( @2**;. < => 2?@ (6'AB /C*DE #FLM,-6N
CFG /HI#JK01 AnalyzeDD2O%/G JKP/;<Q6R5SCT[U\&%'] '*(VW*.&[ X/ TU2YZ/Q6R5S@^C_`1\-a O/*;<QR45S2b  ;<C*cd .e 2fhg `i  ;<QR*5#S0j  kl 3m2O/n G,o "pq P 9r 1 A iO/  /s0tuv/*wnsPxyz - i{*1 AnalyzeDD 0*|}cd .
~ 10 21 ~ 1 /* l j5 2 6 ;8<#C4 .
~ 6 / CFG 2 '4( 16#5#43#1#64#2 6 5 [ C # 5* [,*-( @ .
3.1JP01 3.P*  ' i  5 [ ;<¡/¢£2¤ @ ( g ` *.
~ 11 26¥¦5§3/¨¦©ªC#  .  l« j¦5¬­0§®6¯ 2

(513)

Vol. 8 No. 6 Nov. 1991°²±³µ´µ¶·01010
00000010100111111111

CFG

Jasmintranslator°h±³µ´µ¶8·ÎhÏ(Jasmin½ ¶*¾µ¿²Á ºh»hÌ ¶²Í½Çh¶ÄÈ8¾µÉË¿hÊ ÁhÅ*Æ¸²¹hºh¸h» ¼½ ¶*¾Àºh¿h» ÁÂ²ÃCFG,CFG)ú 11 Ð ÑÓÒ ÔÕ¦ÖØ× /  5Ø#ÙÚP 9Ø iØ{#1 9 z4^ÜÛ§{ÓÝÞÓß  @Ö× [7] 2#à '*(Äáâã.# ¥#53041ä0Û{#2JasminÖ× /Ä l& j5åC¨æ#;< ' 1 CFG C¨#ç
Jasmin*. O/è153#12  5
 584 [ C #64.X
- [ 6rhC4éäê ' 1 [CFG
22b 5* #,- i CFG ë z -.
¢ : 2  ¥5*3C M Ø@ ìÜ( 'Ø â l&íØ îjÚ5&ÚhXØ/ %  5 ' [ ; .
<ÚCÓtÚ@Ó1ØØ¡CÓïØð i ¥53P01ñòôó6õê ' ö÷9ø H1ù2ñòµóõê 'ú Cû#üýþÿ1 r sCì ï 0ñÚòýþÿ  %Ø'( &Bø i{1Ør;#<Ø/. i  ' 1éê  /G* ;<C[t i  Hb
` 5  6,*-X% 0 ] @ .A i*1
A i  # ß "$ 0*;</ R
2
 %'( @ ] @ .

45 "!$#%"&('() PØ0Ó1 lÜ jØ5Ü 2 Ü'Ó( 1 JavaVM /+*, P 9Ø ØC+-(. ' i  5ØÓ [ ØÚC "Ø$' 1O/éê*¡C ' i ., z2*1¡/7  l 7¢/Ct@031  2 S/ íî Cïð ' i .
3 èÚ+/ 4(5 %'Ó( 0Ó1Ø ' iÓ;Ø<ØØ¡Ú+/ 6(7(8ßØ1á :¦Ó 56Ó [ 6Ú/§éªê = <;>¦ÚR9 Ú2 ;z -Ó.A i§1ñªò#9/  5¦# [ 6ª/§éÚê6Ct B6X¦% =P ?@BABC=DFE=GHA=CB' IKJ Program Dependence Graph L PDGMäCÓ¨Øç
1 ?(@(A(CD+N;C+O(N]RPQ
J Program SliceM [4] éê/STC-y ( @ .
ûVUXWVY[ 1 ] Aho, A.V., Sethi, R. and Ullman, J.D.: “Compilers Principles, Techniques, and Tools,” AddisonWesley, (1986).
[ 2 ] Gosling, J., Joy, B. and Steele, G.: “The Java
Language Specification,” Addison-Wesley, (1996).
[ 3 ] Meyer, J., Downing, T.: “Java Virtual Machine,” O’Reilly & Associates, (1997).
[ 4 ] Weiser, M.: “Program Slicing,” IEEE Transaction on Software Engineering, 10(4), pp.352–357(1984).
[ 5 ] Zhao, J.: “Analyzing Control Flow in Java Bytecode,”16, pp.313–316(1999).
[ 6 ] Zhao, J.: “Dependence Analysis of Java Bytecode,”16, pp.317–
320(1999).
[ 7 ] “Jasmin Home Page,”
http://www.cat.nyu.edu/meyer/jasmin/

Z\[=]_^H`badc+egf_h_i_jkl_iZ\[=]_^H`badc+egf_h_i_jkl_i