changeset 29:d80535a49459

modify tex
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 21 Nov 2011 06:28:32 +0900
parents 9ca3eb4921d6
children 998df5441c3b
files Paper/figure/code-id.eps Paper/figure/ir.eps Paper/figure/ir.graffle Paper/figure/rid-goto.eps Paper/nobu-prosym.tex
diffstat 5 files changed, 280 insertions(+), 367 deletions(-) [+]
line wrap: on
line diff
--- a/Paper/figure/code-id.eps	Mon Nov 21 04:53:45 2011 +0900
+++ b/Paper/figure/code-id.eps	Mon Nov 21 06:28:32 2011 +0900
@@ -1,5 +1,5 @@
 %!PS-Adobe-3.0 EPSF-3.0
-%%HiResBoundingBox: 0.000000 0.000000 299.000000 142.000000
+%%HiResBoundingBox: 0.000000 0.000000 319.000000 142.000000
 %APL_DSC_Encoding: UTF8
 %APLProducer: (Version 10.7.2 (Build 11C74) Quartz PS Context)
 %%Title: (Unknown)
@@ -9,7 +9,7 @@
 %%DocumentData: Clean7Bit
 %%LanguageLevel: 2
 %%Pages: 1
-%%BoundingBox: 0 0 449 213
+%%BoundingBox: 0 0 479 213
 %%EndComments
 %%BeginProlog
 %%BeginFile: cg-pdf.ps
@@ -641,7 +641,7 @@
 %%BeginSetup
 %%EndSetup
 %%Page: 1 1
-%%PageBoundingBox: 0 0 449 213
+%%PageBoundingBox: 0 0 479 213
 %%BeginPageSetup
 cg_md begin
 bp
@@ -763,7 +763,7 @@
 /Cs1 SC
 1 1 1 sc
 q
-0 0 448.5 213 rc
+0 0 478.5 213 rc
 -77.499855 445.50681 m
 761.00012 445.50681 l
 761.00012 -728.99316 l
@@ -772,10 +772,10 @@
 -77.499855 445.50681 m
 f
 31.5 195 m
-417 195 l
-424.45581 195 430.5 188.95584 430.5 181.5 c
-430.5 31.5 l
-430.5 24.044174 424.45581 18 417 18 c
+447 195 l
+454.45581 195 460.5 188.95584 460.5 181.5 c
+460.5 31.5 l
+460.5 24.044174 454.45581 18 447 18 c
 31.5 18 l
 24.044151 18 18 24.044174 18 31.5 c
 18 31.5 18 31.5 18 31.5 c
@@ -790,10 +790,10 @@
 0 0 0 sc
 1.5 0 0 -1.5 -76.5 445.5 cm
 72 167 m
-329 167 l
-333.97055 167 338 171.02943 338 176 c
-338 276 l
-338 280.97055 333.97055 285 329 285 c
+349 167 l
+353.97055 167 358 171.02943 358 176 c
+358 276 l
+358 280.97055 353.97055 285 349 285 c
 72 285 l
 67.029434 285 63 280.97055 63 276 c
 63 276 63 276 63 276 c
@@ -805,10 +805,10 @@
 2 w
 1 1 1 sc
 72 167 m
-329 167 l
-333.97055 167 338 171.02943 338 176 c
-338 276 l
-338 280.97055 333.97055 285 329 285 c
+349 167 l
+353.97055 167 358 171.02943 358 176 c
+358 276 l
+358 280.97055 353.97055 285 349 285 c
 72 285 l
 67.029434 285 63 280.97055 63 276 c
 63 276 63 276 63 276 c
@@ -820,19 +820,19 @@
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 224.25 106.5 cm
+1.5 0 0 -1.5 239.25 106.5 cm
 /F1.1[ 12 0 0 -12 0 0]sf
--132.5 -34 m
+-142.5 -34 m
 (!"#$%&'\(\)*!+*!&',!\)-./0%1)[ 6.673828 6.673828 6.673828 9.996094 3.333984 6.000000 6.673828 3.333984 6.000000 6.673828 6.673828 6.000000 6.673828 6.673828 6.000000 6.673828 6.000000 6.673828 6.000000 8.666016 6.673828 3.996094 6.673828 3.333984 0.000000 ] xS
--132.5 -20 m
+-142.5 -20 m
 (%%&\(+'"."!2)[ 3.333984 3.333984 6.000000 3.333984 6.000000 6.673828 6.673828 6.673828 6.673828 6.673828 0.000000 ] xS
--132.5 -6 m
+-142.5 -6 m
 (%%&\(+'3.402)[ 3.333984 3.333984 6.000000 3.333984 6.000000 6.673828 6.000000 6.673828 2.666016 6.673828 0.000000 ] xS
--132.5 8 m
+-142.5 8 m
 (%%%%%5)[ 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
--132.5 22 m
+-142.5 22 m
 (%%&\(+'676'&.0!2)[ 3.333984 3.333984 6.000000 3.333984 6.000000 6.673828 8.666016 6.673828 8.666016 6.673828 6.000000 6.673828 6.673828 6.673828 0.000000 ] xS
--132.5 36 m
+-142.5 36 m
 (%%%%%5)[ 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
 ep
 end
--- a/Paper/figure/ir.eps	Mon Nov 21 04:53:45 2011 +0900
+++ b/Paper/figure/ir.eps	Mon Nov 21 06:28:32 2011 +0900
@@ -1,5 +1,5 @@
 %!PS-Adobe-3.0 EPSF-3.0
-%%HiResBoundingBox: 0.000000 0.000000 425.000000 219.000000
+%%HiResBoundingBox: 0.000000 0.000000 419.000000 219.000000
 %APL_DSC_Encoding: UTF8
 %APLProducer: (Version 10.7.2 (Build 11C74) Quartz PS Context)
 %%Title: (Unknown)
@@ -9,7 +9,7 @@
 %%DocumentData: Clean7Bit
 %%LanguageLevel: 2
 %%Pages: 1
-%%BoundingBox: 0 0 638 329
+%%BoundingBox: 0 0 629 329
 %%EndComments
 %%BeginProlog
 %%BeginFile: cg-pdf.ps
@@ -641,7 +641,7 @@
 %%BeginSetup
 %%EndSetup
 %%Page: 1 1
-%%PageBoundingBox: 0 0 638 329
+%%PageBoundingBox: 0 0 629 329
 %%BeginPageSetup
 cg_md begin
 bp
@@ -657,7 +657,7 @@
 
dup 36 /r put
 
dup 37 /i put
 
dup 38 /c put
-
dup 39 /t put
+
dup 39 /T put
 
dup 40 /C put
 
dup 41 /o put
 
dup 42 /d put
@@ -678,9 +678,9 @@
 
dup 57 /f put
 
dup 58 /y put
 
dup 59 /O put
-
dup 60 /z put
-
dup 61 /R put
-
dup 62 /T put
+
dup 60 /t put
+
dup 61 /z put
+
dup 62 /R put
 
dup 63 /space put
 
readonly def
 
42/FontType resourcestatus{pop pop false}{true}ifelse
@@ -782,25 +782,25 @@
 /Cs1 SC
 1 1 1 sc
 q
-0 0 637.5 328.5 rc
--71.49987 441.50671 m
-767.00012 441.50671 l
-767.00012 -732.99329 l
--71.49987 -732.99329 l
+0 0 628.5 328.5 rc
+-80.499847 441.50671 m
+758.00012 441.50671 l
+758.00012 -732.99329 l
+-80.499847 -732.99329 l
 h
--71.49987 441.50671 m
+-80.499847 441.50671 m
 f
-369 311.99994 m
-487.80002 311.99994 l
-487.80002 239.99995 l
-369 239.99995 l
+360 311.99994 m
+478.80002 311.99994 l
+478.80002 239.99995 l
+360 239.99995 l
 h
-369 311.99994 m
+360 311.99994 m
 f
 1 J
 1 j
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 293 86.000038 m
 372.20001 86.000038 l
 372.20001 134.00003 l
@@ -811,51 +811,51 @@
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 428.40002 275.99994 cm
+1.5 0 0 -1.5 419.40002 275.99994 cm
 /F1.1[ 12 0 0 -12 0 0]sf
 -21.008789 -3 m
 (!"#"$%&)[ 9.333984 6.673828 6.673828 6.673828 3.996094 2.666016 0.000000 ] xS
--10.338867 11 m
-('$"")[ 3.333984 3.996094 6.673828 0.000000 ] xS
+-12.117188 11 m
+('$"")[ 6.890625 3.996094 6.673828 0.000000 ] xS
 0.60000002 i
 /Cs1 SC
 1 1 1 sc
 CM
-41.999886 311.99994 m
-160.7999 311.99994 l
-160.7999 239.99995 l
-41.999886 239.99995 l
+17.999886 311.99994 m
+136.7999 311.99994 l
+136.7999 239.99995 l
+17.999886 239.99995 l
 h
-41.999886 311.99994 m
+17.999886 311.99994 m
 f
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
-74.999924 86.000038 m
-154.19994 86.000038 l
-154.19994 134.00003 l
-74.999924 134.00003 l
+1.5 0 0 -1.5 -79.5 441 cm
+64.999924 86.000038 m
+144.19994 86.000038 l
+144.19994 134.00003 l
+64.999924 134.00003 l
 h
-74.999924 86.000038 m
+64.999924 86.000038 m
 S
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 101.39989 275.99994 cm
+1.5 0 0 -1.5 77.399895 275.99994 cm
 -14.34375 4 m
 (\(\)*")[ 8.666016 6.673828 6.673828 0.000000 ] xS
 0.60000002 i
 /Cs1 SC
 1 1 1 sc
 CM
-26.999886 200.70007 m
-145.7999 200.70007 l
-145.7999 128.70007 l
-26.999886 128.70007 l
+17.999886 200.70007 m
+136.7999 200.70007 l
+136.7999 128.70007 l
+17.999886 128.70007 l
 h
-26.999886 200.70007 m
+17.999886 200.70007 m
 f
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 64.999924 160.19995 m
 144.19994 160.19995 l
 144.19994 208.19995 l
@@ -866,26 +866,28 @@
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 86.399895 164.70007 cm
--22.672852 4 m
+1.5 0 0 -1.5 77.399895 164.70007 cm
+-22.672852 -3 m
 (!+,-./)[ 9.333984 3.333984 9.996094 8.003906 6.673828 0.000000 ] xS
+-12.117188 11 m
+('$"")[ 6.890625 3.996094 6.673828 0.000000 ] xS
 0.60000002 i
 /Cs1 SC
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
-154.19994 110.00004 m
-283.10004 110.00004 l
+1.5 0 0 -1.5 -79.5 441 cm
+144.19994 110.00004 m
+283.09998 110.00004 l
 S
 CM
-366.15002 275.99994 m
-354.15002 280.49994 l
-354.15002 271.49994 l
+357.15002 275.99994 m
+345.15002 280.49994 l
+345.15002 271.49994 l
 h
-366.15002 275.99994 m
+357.15002 275.99994 m
 f
 0 J
 0 j
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 291.10004 110.00004 m
 283.10004 107.00004 l
 283.10004 113.00004 l
@@ -894,34 +896,34 @@
 S
 1 1 1 sc
 CM
-215.55457 306.50665 m
-293.49771 306.50665 l
-293.49771 246.50667 l
-215.55457 246.50667 l
+198.37924 306.50665 m
+276.32239 306.50665 l
+276.32239 246.50667 l
+198.37924 246.50667 l
 h
-215.55457 306.50665 m
+198.37924 306.50665 m
 f
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 255.52602 275.99994 cm
+1.5 0 0 -1.5 238.35065 275.99994 cm
 -15.673828 4 m
 (-0$1")[ 8.003906 6.673828 3.996094 6.000000 0.000000 ] xS
 0.60000002 i
 /Cs1 SC
 1 1 1 sc
 CM
-489.59998 90 m
-620.99994 90 l
-620.99994 18 l
-489.59998 18 l
+480.59998 90 m
+611.99994 90 l
+611.99994 18 l
+480.59998 18 l
 h
-489.59998 90 m
+480.59998 90 m
 f
 1 J
 1 j
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 373.39999 234 m
 460.99997 234 l
 460.99997 282 l
@@ -932,7 +934,7 @@
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 555.29999 54 cm
+1.5 0 0 -1.5 546.29999 54 cm
 -28.341797 -3 m
 (211"345"$)[ 8.003906 6.000000 6.000000 6.673828 9.996094 6.673828 2.666016 6.673828 0.000000 ] xS
 -26.695312 11 m
@@ -940,7 +942,7 @@
 0.60000002 i
 /Cs1 SC
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 372.20001 110.00004 m
 385.7999 110.00005 l
 385.7999 145.00006 l
@@ -949,15 +951,15 @@
 116.55188 153.24435 l
 S
 CM
-89.511368 202.51083 m
-107.56133 205.5773 l
-101.09434 216.68964 l
+80.511368 202.51083 m
+98.561325 205.5773 l
+92.094337 216.68964 l
 h
-89.511368 202.51083 m
+80.511368 202.51083 m
 f
 0 J
 0 j
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 106.67425 158.99277 m
 118.70755 156.94846 l
 114.39622 149.54024 l
@@ -966,175 +968,130 @@
 S
 1 1 1 sc
 CM
-215.55457 243.20673 m
-305.59998 243.20673 l
-305.59998 205.70663 l
-215.55457 205.70663 l
+206.5546 243.20673 m
+296.60001 243.20673 l
+296.60001 205.70663 l
+206.5546 205.70663 l
 h
-215.55457 243.20673 m
+206.5546 243.20673 m
 f
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 261.57715 223.94995 cm
+1.5 0 0 -1.5 252.57715 223.94995 cm
 -21.667969 4 m
 (!%385%9:)[ 9.333984 2.666016 9.996094 6.673828 2.666016 2.666016 3.333984 0.000000 ] xS
-0.60000002 i
-/Cs1 SC
-1 1 1 sc
-CM
-369 200.70007 m
-487.80002 200.70007 l
-487.80002 128.70007 l
-369 128.70007 l
-h
-369 200.70007 m
-f
 1 J
 1 j
-0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
-293 160.19995 m
-372.20001 160.19995 l
-372.20001 208.19995 l
-293 208.19995 l
-h
-293 160.19995 m
-S
-/Cs2 SC
-0 sc
-0 i
-1.5 0 0 -1.5 428.40002 164.70007 cm
--21.008789 -3 m
-(!"#"$%&)[ 9.333984 6.673828 6.673828 6.673828 3.996094 2.666016 0.000000 ] xS
--10.338867 11 m
-('$"")[ 3.333984 3.996094 6.673828 0.000000 ] xS
 0.60000002 i
 /Cs1 SC
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
-144.19992 184.19995 m
-279.67145 184.19995 l
+1.5 0 0 -1.5 -79.5 441 cm
+144.69992 184.20277 m
+272.67163 184.9248 l
 S
 CM
-366.15002 164.70007 m
-349.00717 171.12866 l
-349.00717 158.27151 l
+346.65005 163.51607 m
+329.54376 170.04123 l
+329.47119 157.1843 l
 h
-366.15002 164.70007 m
+346.65005 163.51607 m
 f
 0 J
 0 j
-1.5 0 0 -1.5 -70.5 441 cm
-291.10004 184.19995 m
-279.67145 179.91422 l
-279.67145 188.48566 l
+1.5 0 0 -1.5 -79.5 441 cm
+284.10004 184.98929 m
+272.69586 180.63918 l
+272.64746 189.21046 l
 h
-291.10004 184.19995 m
+284.10004 184.98929 m
 S
 1 1 1 sc
 CM
-210.20868 189.50662 m
-300.25409 189.50662 l
-300.25409 142.7067 l
-210.20868 142.7067 l
+201.20869 189.50662 m
+291.25409 189.50662 l
+291.25409 142.7067 l
+201.20869 142.7067 l
 h
-210.20868 189.50662 m
+201.20869 189.50662 m
 f
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 256.23126 165.59995 cm
+1.5 0 0 -1.5 247.23125 165.59995 cm
 -23.671875 4 m
-(;8'%3%<")[ 9.333984 6.673828 3.333984 2.666016 9.996094 2.666016 6.000000 0.000000 ] xS
+(;8<%3%=")[ 9.333984 6.673828 3.333984 2.666016 9.996094 2.666016 6.000000 0.000000 ] xS
 1 J
 1 j
 0.60000002 i
 /Cs1 SC
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
-372.20004 184.19995 m
+1.5 0 0 -1.5 -79.5 441 cm
+378 184 m
 387.59985 183.99995 l
 388.20001 225 l
 119.19994 225.39995 l
-110.85696 228.96394 l
+116.01524 227.31952 l
 S
 CM
-80.020775 90.819672 m
-98.31086 91.642342 l
-93.26004 103.46585 l
+79.84079 91.171165 m
+97.841431 94.514946 l
+91.204269 105.52647 l
 h
-80.020775 90.819672 m
+79.84079 91.171165 m
 f
 0 J
 0 j
-1.5 0 0 -1.5 -70.5 441 cm
-100.34718 233.45355 m
-112.54057 232.90511 l
-109.17336 225.02277 l
+1.5 0 0 -1.5 -79.5 441 cm
+106.2272 233.21922 m
+118.22762 230.99004 l
+113.80285 223.64902 l
 h
-100.34718 233.45355 m
+106.2272 233.21922 m
 S
 1 1 1 sc
 CM
-194.91721 128.00671 m
-326.31717 128.00671 l
-326.31717 81.206787 l
-194.91721 81.206787 l
+17.999886 89.699936 m
+136.7999 89.699936 l
+136.7999 17.699936 l
+17.999886 17.699936 l
 h
-194.91721 128.00671 m
-f
-/Cs2 SC
-0 sc
-0 i
-1.5 0 0 -1.5 261.61707 104.10004 cm
--37.693359 4 m
-(=>.?!"#"$0'")[ 8.455078 7.330078 6.234375 3.333984 9.333984 6.673828 6.673828 6.673828 3.996094 6.673828 3.333984 0.000000 ] xS
-0.60000002 i
-/Cs1 SC
-1 1 1 sc
-CM
-17.999886 89.700073 m
-136.7999 89.700073 l
-136.7999 17.700073 l
-17.999886 17.700073 l
-h
-17.999886 89.700073 m
+17.999886 89.699936 m
 f
 1 J
 1 j
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
-58.999924 234.19995 m
-138.19994 234.19995 l
-138.19994 282.19995 l
-58.999924 282.19995 l
+1.5 0 0 -1.5 -79.5 441 cm
+64.999924 234.20004 m
+144.19994 234.20004 l
+144.19994 282.20004 l
+64.999924 282.20004 l
 h
-58.999924 234.19995 m
+64.999924 234.20004 m
 S
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 77.399895 53.700073 cm
+1.5 0 0 -1.5 77.399895 53.699936 cm
 -11.229492 4 m
-(=>.)[ 8.455078 7.330078 0.000000 ] xS
+(>'.)[ 8.455078 7.330078 0.000000 ] xS
 0.60000002 i
 /Cs1 SC
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 138.19998 257.00006 m
 259.67181 257.90112 l
 S
 CM
-336.15009 54.021149 m
-319.05542 60.576714 l
-318.96002 47.71994 l
+327.15009 54.021149 m
+310.05542 60.576714 l
+309.96002 47.71994 l
 h
-336.15009 54.021149 m
+327.15009 54.021149 m
 f
 0 J
 0 j
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 271.10007 257.9859 m
 259.70361 253.61552 l
 259.64001 262.18671 l
@@ -1143,65 +1100,80 @@
 S
 1 1 1 sc
 CM
-173.00012 79.406631 m
-270.49994 79.406631 l
-270.49994 18.20665 l
-173.00012 18.20665 l
+164.00015 79.406631 m
+261.49997 79.406631 l
+261.49997 18.20665 l
+164.00015 18.20665 l
 h
-173.00012 79.406631 m
+164.00015 79.406631 m
 f
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 222.74991 48.299927 cm
+1.5 0 0 -1.5 213.74991 48.299927 cm
 -11.229492 -3 m
-(=>.)[ 8.455078 7.330078 0.000000 ] xS
+(>'.)[ 8.455078 7.330078 0.000000 ] xS
 -23.671875 11 m
-(;8'%3%<")[ 9.333984 6.673828 3.333984 2.666016 9.996094 2.666016 6.000000 0.000000 ] xS
+(;8<%3%=")[ 9.333984 6.673828 3.333984 2.666016 9.996094 2.666016 6.000000 0.000000 ] xS
 0.60000002 i
 /Cs1 SC
 1 1 1 sc
 CM
-338.00012 85.106705 m
-435.49994 85.106705 l
-435.49994 23.906723 l
-338.00012 23.906723 l
+329.00015 85.106705 m
+426.49997 85.106705 l
+426.49997 23.906723 l
+329.00015 23.906723 l
 h
-338.00012 85.106705 m
+329.00015 85.106705 m
 f
 /Cs2 SC
 0 sc
 0 i
-1.5 0 0 -1.5 387.74991 54 cm
+1.5 0 0 -1.5 378.74991 54 cm
 -14.34375 -3 m
 (\(\)*")[ 8.666016 6.673828 6.673828 0.000000 ] xS
 -25.016602 11 m
-(!"#"$0'")[ 9.333984 6.673828 6.673828 6.673828 3.996094 6.673828 3.333984 0.000000 ] xS
+(!"#"$0<")[ 9.333984 6.673828 6.673828 6.673828 3.996094 6.673828 3.333984 0.000000 ] xS
 1 J
 1 j
 0.60000002 i
 /Cs1 SC
 0 0 0 sc
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 337.99988 258 m
 360.07141 258 l
 S
 CM
-486.74994 54 m
-469.60712 60.428581 l
-469.60712 47.571442 l
+477.74994 54 m
+460.60712 60.428581 l
+460.60712 47.571442 l
 h
-486.74994 54 m
+477.74994 54 m
 f
 0 J
 0 j
-1.5 0 0 -1.5 -70.5 441 cm
+1.5 0 0 -1.5 -79.5 441 cm
 371.49997 258 m
 360.07141 253.71428 l
 360.07141 262.28571 l
 h
 371.49997 258 m
 S
+1 1 1 sc
+CM
+346.40021 189.50662 m
+477.80017 189.50662 l
+477.80017 142.7067 l
+346.40021 142.7067 l
+h
+346.40021 189.50662 m
+f
+/Cs2 SC
+0 sc
+0 i
+1.5 0 0 -1.5 413.10004 165.59995 cm
+-37.693359 4 m
+(>'.?!"#"$0<")[ 8.455078 7.330078 6.234375 3.333984 9.333984 6.673828 6.673828 6.673828 3.996094 6.673828 3.333984 0.000000 ] xS
 ep
 end
 %%Trailer
--- a/Paper/figure/ir.graffle	Mon Nov 21 04:53:45 2011 +0900
+++ b/Paper/figure/ir.graffle	Mon Nov 21 06:28:32 2011 +0900
@@ -50,6 +50,60 @@
 	<key>GraphicsList</key>
 	<array>
 		<dict>
+			<key>Bounds</key>
+			<string>{{284.60004, 168.00006}, {87.599983, 31.199951}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>37</integer>
+			<key>Magnets</key>
+			<array>
+				<string>{1, 1}</string>
+				<string>{1, -1}</string>
+				<string>{-1, -1}</string>
+				<string>{-1, 1}</string>
+				<string>{0, 1}</string>
+				<string>{0, -1}</string>
+				<string>{1, 0}</string>
+				<string>{-1, 0}</string>
+				<string>{-0.5, -0.233518}</string>
+				<string>{-0.49144199, 0.26006299}</string>
+				<string>{0.50711799, -0.224086}</string>
+				<string>{0.50711799, 0.26717901}</string>
+				<string>{-0.27430999, -0.47402799}</string>
+				<string>{0.27978, -0.47847801}</string>
+				<string>{0.29393801, 0.54304397}</string>
+				<string>{-0.28623199, 0.55380398}</string>
+			</array>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230
+{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
+
+\f0\fs24 \cf0 RTL Generate}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+		</dict>
+		<dict>
 			<key>AllowLabelDrop</key>
 			<false/>
 			<key>Class</key>
@@ -234,7 +288,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{58.999924, 234.19995}, {79.200012, 47.999989}}</string>
+			<string>{{64.999924, 234.20004}, {79.200012, 47.999989}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -282,60 +336,6 @@
 			</dict>
 		</dict>
 		<dict>
-			<key>Bounds</key>
-			<string>{{177.61139, 209}, {87.599983, 31.199951}}</string>
-			<key>Class</key>
-			<string>ShapedGraphic</string>
-			<key>ID</key>
-			<integer>29</integer>
-			<key>Magnets</key>
-			<array>
-				<string>{1, 1}</string>
-				<string>{1, -1}</string>
-				<string>{-1, -1}</string>
-				<string>{-1, 1}</string>
-				<string>{0, 1}</string>
-				<string>{0, -1}</string>
-				<string>{1, 0}</string>
-				<string>{-1, 0}</string>
-				<string>{-0.5, -0.233518}</string>
-				<string>{-0.49144199, 0.26006299}</string>
-				<string>{0.50711799, -0.224086}</string>
-				<string>{0.50711799, 0.26717901}</string>
-				<string>{-0.27430999, -0.47402799}</string>
-				<string>{0.27978, -0.47847801}</string>
-				<string>{0.29393801, 0.54304397}</string>
-				<string>{-0.28623199, 0.55380398}</string>
-			</array>
-			<key>Shape</key>
-			<string>Rectangle</string>
-			<key>Style</key>
-			<dict>
-				<key>shadow</key>
-				<dict>
-					<key>Draws</key>
-					<string>NO</string>
-				</dict>
-				<key>stroke</key>
-				<dict>
-					<key>Draws</key>
-					<string>NO</string>
-				</dict>
-			</dict>
-			<key>Text</key>
-			<dict>
-				<key>Text</key>
-				<string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230
-{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
-{\colortbl;\red255\green255\blue255;}
-\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
-
-\f0\fs24 \cf0 RTL Generate}</string>
-				<key>VerticalPad</key>
-				<integer>0</integer>
-			</dict>
-		</dict>
-		<dict>
 			<key>AllowLabelDrop</key>
 			<false/>
 			<key>Class</key>
@@ -348,14 +348,14 @@
 				<integer>6</integer>
 			</dict>
 			<key>ID</key>
-			<integer>28</integer>
+			<integer>40</integer>
 			<key>Points</key>
 			<array>
-				<string>{372.20004, 184.19995}</string>
+				<string>{378, 184}</string>
 				<string>{387.59985, 183.99995}</string>
 				<string>{388.20001, 225}</string>
 				<string>{119.19994, 225.39995}</string>
-				<string>{98.59993, 234.19995}</string>
+				<string>{104.59993, 234.20004}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -371,11 +371,6 @@
 					<real>0.5</real>
 				</dict>
 			</dict>
-			<key>Tail</key>
-			<dict>
-				<key>ID</key>
-				<integer>24</integer>
-			</dict>
 		</dict>
 		<dict>
 			<key>Bounds</key>
@@ -436,17 +431,12 @@
 			<false/>
 			<key>Class</key>
 			<string>LineGraphic</string>
-			<key>Head</key>
-			<dict>
-				<key>ID</key>
-				<integer>24</integer>
-			</dict>
 			<key>ID</key>
-			<integer>25</integer>
+			<integer>39</integer>
 			<key>Points</key>
 			<array>
-				<string>{144.19992, 184.19995}</string>
-				<string>{293, 184.19995}</string>
+				<string>{144.69992, 184.20277}</string>
+				<string>{286, 185}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -472,56 +462,6 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{293, 160.19995}, {79.200012, 47.999989}}</string>
-			<key>Class</key>
-			<string>ShapedGraphic</string>
-			<key>ID</key>
-			<integer>24</integer>
-			<key>Magnets</key>
-			<array>
-				<string>{1, 1}</string>
-				<string>{1, -1}</string>
-				<string>{-1, -1}</string>
-				<string>{-1, 1}</string>
-				<string>{0, 1}</string>
-				<string>{0, -1}</string>
-				<string>{1, 0}</string>
-				<string>{-1, 0}</string>
-				<string>{-0.5, -0.233518}</string>
-				<string>{-0.49144199, 0.26006299}</string>
-				<string>{0.50711799, -0.224086}</string>
-				<string>{0.50711799, 0.26717901}</string>
-				<string>{-0.27430999, -0.47402799}</string>
-				<string>{0.27978, -0.47847801}</string>
-				<string>{0.29393801, 0.54304397}</string>
-				<string>{-0.28623199, 0.55380398}</string>
-			</array>
-			<key>Shape</key>
-			<string>Rectangle</string>
-			<key>Style</key>
-			<dict>
-				<key>shadow</key>
-				<dict>
-					<key>Draws</key>
-					<string>NO</string>
-				</dict>
-			</dict>
-			<key>Text</key>
-			<dict>
-				<key>Text</key>
-				<string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230
-{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
-{\colortbl;\red255\green255\blue255;}
-\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
-
-\f0\fs24 \cf0 Generic\
-tree}</string>
-				<key>VerticalPad</key>
-				<integer>0</integer>
-			</dict>
-		</dict>
-		<dict>
-			<key>Bounds</key>
 			<string>{{191.36963, 132.2}, {60.030289, 25.000061}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
@@ -671,7 +611,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{191.36963, 90.000031}, {51.962097, 40}}</string>
+			<string>{{185.91939, 90.000031}, {51.962097, 40}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -744,7 +684,7 @@
 			<integer>11</integer>
 			<key>Points</key>
 			<array>
-				<string>{154.19994, 110.00003}</string>
+				<string>{144.19994, 110.00003}</string>
 				<string>{293, 110.00003}</string>
 			</array>
 			<key>Style</key>
@@ -811,14 +751,15 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
 
-\f0\fs24 \cf0 GIMPLE}</string>
+\f0\fs24 \cf0 GIMPLE\
+Tree}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
 			</dict>
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{74.999924, 86.000038}, {79.200012, 47.999989}}</string>
+			<string>{{64.999924, 86.000038}, {79.200012, 47.999989}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -910,7 +851,7 @@
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
 
 \f0\fs24 \cf0 Generic\
-tree}</string>
+Tree}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
 			</dict>
@@ -963,7 +904,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2011-11-18 00:23:12 +0000</string>
+	<string>2011-11-20 21:01:25 +0000</string>
 	<key>Modifier</key>
 	<string>Nobuyasu Oshiro</string>
 	<key>NotesVisible</key>
@@ -1044,7 +985,7 @@
 			</dict>
 		</array>
 		<key>Frame</key>
-		<string>{{6, 4}, {693, 938}}</string>
+		<string>{{50, 4}, {693, 938}}</string>
 		<key>ListView</key>
 		<true/>
 		<key>OutlineWidth</key>
--- a/Paper/figure/rid-goto.eps	Mon Nov 21 04:53:45 2011 +0900
+++ b/Paper/figure/rid-goto.eps	Mon Nov 21 06:28:32 2011 +0900
@@ -696,15 +696,15 @@
 
dup 75 /L put
 
dup 76 /braceleft put
 
dup 77 /l put
-
dup 78 /slash put
-
dup 79 /g put
+
dup 78 /v put
+
dup 79 /b put
 
dup 80 /period put
-
dup 81 /v put
-
dup 82 /b put
-
dup 83 /braceright put
-
dup 84 /U put
-
dup 85 /X put
-
dup 86 /Y put
+
dup 81 /g put
+
dup 82 /braceright put
+
dup 83 /U put
+
dup 84 /X put
+
dup 85 /Y put
+
dup 86 /slash put
 
dup 87 /asterisk put
 
dup 88 /one put
 
dup 89 /fi put
@@ -928,7 +928,7 @@
 -198.5 -136.5 m
 (%%%%%%%%%%%%%%%%%-)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
 -198.5 -122.5 m
-(%%%%%%$M#$%NN%':%=>>\)?@AB%9#%!0E$%#$O3$14P)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.673828 2.666016 6.000000 6.673828 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 8.666016 8.003906 8.003906 6.673828 8.666016 8.003906 9.996094 8.003906 3.333984 2.666016 6.000000 3.333984 6.000000 6.673828 6.673828 6.673828 3.333984 6.000000 6.673828 6.673828 9.996094 6.673828 6.673828 3.333984 0.000000 ] xS
+(%%%%%%$M#$)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.673828 2.666016 6.000000 0.000000 ] xS
 -198.5 -108.5 m
 (%%%%%%L)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
 -198.5 -94.5 m
@@ -936,43 +936,43 @@
 -198.5 -80.5 m
 (%%%%%%%%%%L)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
 -198.5 -66.5 m
-(%%%%%%%%%%%%4/$$%9E%I%!\)."/#$/\).$$5\)405$1%6."/#$/7FGQ"M2$8)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.996094 6.673828 6.673828 3.333984 2.666016 6.673828 3.333984 7.007812 3.333984 6.000000 6.673828 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 6.673828 6.673828 6.673828 6.673828 6.000000 6.673828 3.333984 6.673828 6.000000 6.673828 6.673828 3.333984 3.996094 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 3.996094 3.996094 7.007812 6.000000 6.673828 2.666016 6.673828 6.673828 0.000000 ] xS
+(%%%%%%%%%%%%4/$$%9E%I%!\)."/#$/\).$$5\)405$1%6."/#$/7FGN"M2$8)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.996094 6.673828 6.673828 3.333984 2.666016 6.673828 3.333984 7.007812 3.333984 6.000000 6.673828 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 6.673828 6.673828 6.673828 6.673828 6.000000 6.673828 3.333984 6.673828 6.000000 6.673828 6.673828 3.333984 3.996094 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 3.996094 3.996094 7.007812 6.000000 6.673828 2.666016 6.673828 6.673828 0.000000 ] xS
 -198.5 -52.5 m
 (%%%%%%%%%%%%M0!"4901\)4%M0!%I%!\)."/#$/\).$$5\)405$1%6."/#$/7FGM0!"49018)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 2.666016 6.673828 6.000000 6.673828 3.333984 2.666016 6.673828 6.673828 6.673828 3.333984 3.333984 2.666016 6.673828 6.000000 3.333984 7.007812 3.333984 6.000000 6.673828 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 6.673828 6.673828 6.673828 6.673828 6.000000 6.673828 3.333984 6.673828 6.000000 6.673828 6.673828 3.333984 3.996094 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 3.996094 3.996094 7.007812 2.666016 6.673828 6.000000 6.673828 3.333984 2.666016 6.673828 6.673828 0.000000 ] xS
 -198.5 -38.5 m
-(%%%%%%%%%%%%R29ME\)$;4$/1"M\)/$:%6M0!<%9E<%&'\(\)=R=\)=+\(B<%C$;./P0/9O91"M\)4H.$78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.673828 6.673828 2.666016 2.666016 6.673828 6.673828 6.673828 6.000000 3.333984 6.673828 3.996094 6.673828 6.673828 2.666016 6.673828 3.996094 6.673828 3.333984 3.333984 3.996094 2.666016 6.673828 6.000000 3.333984 3.333984 2.666016 6.673828 3.333984 3.333984 8.666016 3.333984 8.666016 6.673828 8.666016 6.673828 8.666016 6.673828 8.666016 9.333984 8.666016 8.003906 3.333984 3.333984 8.003906 6.673828 6.000000 6.673828 3.339844 3.333984 6.673828 3.996094 2.666016 6.673828 2.666016 6.673828 6.673828 2.666016 6.673828 3.333984 6.000000 6.673828 6.673828 3.996094 0.000000 ] xS
+(%%%%%%%%%%%%O29ME\)$;4$/1"M\)/$:%6M0!<%9E<%&'\(\)=O=\)=+\(B<%C$;./P0/9Q91"M\)4H.$78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.673828 6.673828 2.666016 2.666016 6.673828 6.673828 6.673828 6.000000 3.333984 6.673828 3.996094 6.673828 6.673828 2.666016 6.673828 3.996094 6.673828 3.333984 3.333984 3.996094 2.666016 6.673828 6.000000 3.333984 3.333984 2.666016 6.673828 3.333984 3.333984 8.666016 3.333984 8.666016 6.673828 8.666016 6.673828 8.666016 6.673828 8.666016 9.333984 8.666016 8.003906 3.333984 3.333984 8.003906 6.673828 6.000000 6.673828 3.339844 3.333984 6.673828 3.996094 2.666016 6.673828 2.666016 6.673828 6.673828 2.666016 6.673828 3.333984 6.000000 6.673828 6.673828 3.996094 0.000000 ] xS
 -198.5 -24.5 m
-(%%%%%%%%%%S)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
+(%%%%%%%%%%R)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
 -198.5 -10.5 m
-(%%%%%%%%$;./%I%!\)."/#$/\)$;./\)10\)!033"#%6."/#$/<%?TKK78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.673828 6.000000 6.673828 3.996094 3.333984 7.007812 3.333984 6.000000 6.673828 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 6.673828 6.673828 6.000000 6.673828 3.996094 6.673828 6.673828 6.673828 6.673828 6.000000 6.673828 9.996094 9.996094 6.673828 6.000000 3.333984 3.996094 6.673828 6.673828 3.996094 6.000000 6.673828 3.339844 3.333984 3.333984 8.666016 8.666016 6.673828 6.673828 3.996094 0.000000 ] xS
+(%%%%%%%%$;./%I%!\)."/#$/\)$;./\)10\)!033"#%6."/#$/<%?SKK78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.673828 6.000000 6.673828 3.996094 3.333984 7.007812 3.333984 6.000000 6.673828 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 6.673828 6.673828 6.000000 6.673828 3.996094 6.673828 6.673828 6.673828 6.673828 6.000000 6.673828 9.996094 9.996094 6.673828 6.000000 3.333984 3.996094 6.673828 6.673828 3.996094 6.000000 6.673828 3.339844 3.333984 3.333984 8.666016 8.666016 6.673828 6.673828 3.996094 0.000000 ] xS
 -198.5 3.5 m
-(%%%%%%%%9:%6,&BB\)=+\(B6$;./PQ"M2$7%II%=@KK\)BU>&%7)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 2.666016 3.333984 3.333984 3.996094 7.330078 8.666016 8.003906 8.003906 6.673828 8.666016 9.333984 8.666016 8.003906 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 3.333984 7.007812 7.007812 3.333984 8.666016 8.003906 6.673828 6.673828 6.673828 8.003906 8.003906 8.003906 8.666016 3.333984 0.000000 ] xS
+(%%%%%%%%9:%6,&BB\)=+\(B6$;./PN"M2$7%II%=@KK\)BT>&%7)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 2.666016 3.333984 3.333984 3.996094 7.330078 8.666016 8.003906 8.003906 6.673828 8.666016 9.333984 8.666016 8.003906 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 3.333984 7.007812 7.007812 3.333984 8.666016 8.003906 6.673828 6.673828 6.673828 8.003906 8.003906 8.003906 8.666016 3.333984 0.000000 ] xS
 -198.5 17.5 m
 (%%%%%%%%%%L)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
 -198.5 31.5 m
 (%%%%%%%%%%%%M0!"4901\)4%M0!%I%!\)."/#$/\).$$5\)405$1%6."/#$/7FGM0!"49018)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 2.666016 6.673828 6.000000 6.673828 3.333984 2.666016 6.673828 6.673828 6.673828 3.333984 3.333984 2.666016 6.673828 6.000000 3.333984 7.007812 3.333984 6.000000 6.673828 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 6.673828 6.673828 6.673828 6.673828 6.000000 6.673828 3.333984 6.673828 6.000000 6.673828 6.673828 3.333984 3.996094 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 3.996094 3.996094 7.007812 2.666016 6.673828 6.000000 6.673828 3.333984 2.666016 6.673828 6.673828 0.000000 ] xS
 -198.5 45.5 m
-(%%%%%%%%%%%%!R!\)/$.M"!$\)"/O23$14#%6M0!<%$;./PQ"M2$78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.000000 6.673828 6.000000 6.673828 3.996094 6.673828 6.673828 2.666016 6.673828 6.000000 6.673828 6.673828 6.673828 3.996094 6.673828 6.673828 9.996094 6.673828 6.673828 3.333984 6.000000 3.333984 3.996094 2.666016 6.673828 6.000000 3.333984 3.333984 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 0.000000 ] xS
+(%%%%%%%%%%%%!O!\)/$.M"!$\)"/Q23$14#%6M0!<%$;./PN"M2$78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.000000 6.673828 6.000000 6.673828 3.996094 6.673828 6.673828 2.666016 6.673828 6.000000 6.673828 6.673828 6.673828 3.996094 6.673828 6.673828 9.996094 6.673828 6.673828 3.333984 6.000000 3.333984 3.996094 2.666016 6.673828 6.000000 3.333984 3.333984 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 0.000000 ] xS
 -198.5 73.5 m
-(%%%%%%%%%%%%,&BB\),V>B6$;./PQ"M2$7%I%Q09E\)4H.$\)10E$8)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.123047 7.330078 8.666016 8.003906 8.003906 6.673828 7.330078 8.003906 8.003906 8.003906 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 3.333984 7.007812 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.333984 6.000000 6.673828 6.673828 6.673828 6.673828 6.673828 6.673828 6.673828 0.000000 ] xS
+(%%%%%%%%%%%%,&BB\),U>B6$;./PN"M2$7%I%N09E\)4H.$\)10E$8)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.123047 7.330078 8.666016 8.003906 8.003906 6.673828 7.330078 8.003906 8.003906 8.003906 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 3.333984 7.007812 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.333984 6.000000 6.673828 6.673828 6.673828 6.673828 6.673828 6.673828 6.673828 0.000000 ] xS
 -198.5 87.5 m
-(%%%%%%%%%%%%NW4/$$%$1Q%I%?TKK\),&BB8WWN)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 4.669922 3.333984 3.996094 6.673828 6.673828 3.333984 6.673828 6.673828 6.000000 3.333984 7.007812 3.333984 8.666016 8.666016 6.673828 6.673828 6.673828 7.330078 8.666016 8.003906 8.003906 3.333984 4.669922 4.669922 0.000000 ] xS
+(%%%%%%%%%%%%VW4/$$%$1N%I%?SKK\),&BB8WWV)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 4.669922 3.333984 3.996094 6.673828 6.673828 3.333984 6.673828 6.673828 6.000000 3.333984 7.007812 3.333984 8.666016 8.666016 6.673828 6.673828 6.673828 7.330078 8.666016 8.003906 8.003906 3.333984 4.669922 4.669922 0.000000 ] xS
 -198.5 101.5 m
-(%%%%%%%%%%%%=R=\)'J\)=R=\)*+,+%6$;./PQ"M2$7%I%X8)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 8.666016 6.673828 8.666016 6.673828 3.333984 8.003906 6.673828 8.666016 6.673828 8.666016 6.673828 9.333984 9.333984 7.119141 9.333984 3.333984 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 3.333984 7.007812 3.333984 6.673828 0.000000 ] xS
+(%%%%%%%%%%%%=O=\)'J\)=O=\)*+,+%6$;./PN"M2$7%I%X8)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 8.666016 6.673828 8.666016 6.673828 3.333984 8.003906 6.673828 8.666016 6.673828 8.666016 6.673828 9.333984 9.333984 7.119141 9.333984 3.333984 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 3.333984 7.007812 3.333984 6.673828 0.000000 ] xS
 -198.5 115.5 m
-(%%%%%%%%%%%%=@KK\)BU>&\),@'K=@KK%6$;./PQ"M2$7%I%X8)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 8.666016 8.003906 6.673828 6.673828 6.673828 8.003906 8.003906 8.003906 8.666016 6.673828 6.445312 8.003906 3.333984 6.673828 8.666016 8.003906 6.673828 6.234375 3.333984 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 3.333984 7.007812 3.333984 6.673828 0.000000 ] xS
+(%%%%%%%%%%%%=@KK\)BT>&\),@'K=@KK%6$;./PN"M2$7%I%X8)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 8.666016 8.003906 6.673828 6.673828 6.673828 8.003906 8.003906 8.003906 8.666016 6.673828 6.445312 8.003906 3.333984 6.673828 8.666016 8.003906 6.673828 6.234375 3.333984 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 3.333984 7.007812 3.333984 6.673828 0.000000 ] xS
 -198.5 129.5 m
-(%%%%%%%%%%%%"EE\)#4346$;./PQ"M2$78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.673828 6.673828 6.673828 6.673828 6.000000 3.333984 9.996094 3.333984 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 0.000000 ] xS
+(%%%%%%%%%%%%"EE\)#4346$;./PN"M2$78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.673828 6.673828 6.673828 6.673828 6.000000 3.333984 9.996094 3.333984 3.996094 6.673828 6.000000 6.673828 3.339844 3.333984 6.000000 6.673828 2.666016 6.673828 6.673828 3.996094 0.000000 ] xS
 -198.5 143.5 m
-(%%%%%%%%%%%%#434%I%!\)Y19#Z\)/$42/16M0!<%?TKK\),&BB<%?TKK\),&BB78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.000000 3.333984 9.996094 3.333984 3.333984 7.007812 3.333984 6.000000 6.673828 6.000000 6.673828 2.666016 6.000000 6.673828 6.673828 3.996094 6.673828 3.333984 6.673828 3.996094 6.673828 3.996094 2.666016 6.673828 6.000000 3.333984 3.333984 8.666016 8.666016 6.673828 6.673828 6.673828 7.330078 8.666016 8.003906 8.003906 3.333984 3.333984 8.666016 8.666016 6.673828 6.673828 6.673828 7.330078 8.666016 8.003906 8.003906 3.996094 0.000000 ] xS
+(%%%%%%%%%%%%#434%I%!\)Y19#Z\)/$42/16M0!<%?SKK\),&BB<%?SKK\),&BB78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.000000 3.333984 9.996094 3.333984 3.333984 7.007812 3.333984 6.000000 6.673828 6.000000 6.673828 2.666016 6.000000 6.673828 6.673828 3.996094 6.673828 3.333984 6.673828 3.996094 6.673828 3.996094 2.666016 6.673828 6.000000 3.333984 3.333984 8.666016 8.666016 6.673828 6.673828 6.673828 7.330078 8.666016 8.003906 8.003906 3.333984 3.333984 8.666016 8.666016 6.673828 6.673828 6.673828 7.330078 8.666016 8.003906 8.003906 3.996094 0.000000 ] xS
 -198.5 157.5 m
-(%%%%%%%%%%S)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
+(%%%%%%%%%%R)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
 -198.5 171.5 m
 (%%%%%%%%$M#$)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.673828 2.666016 6.000000 0.000000 ] xS
 -198.5 185.5 m
-(%%%%%%%%%%!\)."/#$/\)$//0/%6."/#$/<%[$;.$!4$E%!0E$%#$O3$14%\\23.%0/%]^W]G[78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.000000 6.673828 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 6.673828 6.673828 3.996094 3.996094 6.673828 3.996094 3.333984 3.996094 6.673828 6.673828 3.996094 6.000000 6.673828 3.339844 3.333984 3.333984 4.259766 6.673828 6.000000 6.673828 6.673828 6.000000 3.333984 6.673828 6.673828 3.333984 6.000000 6.673828 6.673828 6.673828 3.333984 6.000000 6.673828 6.673828 9.996094 6.673828 6.673828 3.333984 3.333984 2.666016 6.673828 9.996094 6.673828 3.333984 6.673828 3.996094 3.333984 10.669922 7.007812 4.669922 10.669922 7.007812 4.259766 3.996094 0.000000 ] xS
+(%%%%%%%%%%!\)."/#$/\)$//0/%6."/#$/<%[$;.$!4$E%!0E$%#$Q3$14%\\23.%0/%]^W]G[78)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 6.000000 6.673828 6.673828 6.673828 3.996094 6.000000 6.673828 3.996094 6.673828 6.673828 3.996094 3.996094 6.673828 3.996094 3.333984 3.996094 6.673828 6.673828 3.996094 6.000000 6.673828 3.339844 3.333984 3.333984 4.259766 6.673828 6.000000 6.673828 6.673828 6.000000 3.333984 6.673828 6.673828 3.333984 6.000000 6.673828 6.673828 6.673828 3.333984 6.000000 6.673828 6.673828 9.996094 6.673828 6.673828 3.333984 3.333984 2.666016 6.673828 9.996094 6.673828 3.333984 6.673828 3.996094 3.333984 10.669922 7.007812 4.669922 10.669922 7.007812 4.259766 3.996094 0.000000 ] xS
 -198.5 199.5 m
-(%%%%%%S)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
+(%%%%%%R)[ 3.333984 3.333984 3.333984 3.333984 3.333984 3.333984 0.000000 ] xS
 ep
 end
 %%Trailer
--- a/Paper/nobu-prosym.tex	Mon Nov 21 04:53:45 2011 +0900
+++ b/Paper/nobu-prosym.tex	Mon Nov 21 06:28:32 2011 +0900
@@ -1,1 +1,1 @@
-\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}
\usepackage{jtygm}


% 巻数,号数などの設定
%\setcounter{巻数}{41}
%\setcounter{号数}{6}
%\setcounter{volpageoffset}{1234}
%\受付{12}{2}{4}
%\採録{12}{5}{11}

\pagestyle{empty}

% ユーザが定義したマクロなど.
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
%\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[Continuation based C の GCC 4.6 上の実装について]%
	{Continuation based C の GCC 4.6 上の実装について}
% 英文表題
\etitle{The implementation of Continuation based C Compiler on GCC 4.6}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{大城 信康\affiref{URYUKYU}\nomember\and
	河野 真治\affiref{URYUKYU}\member{19841765}}
	

% 英文著者名
\eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and
	Shinji Kono\affiref{URYUKYU}}

% 連絡先(投稿時に必要.製版用では無視される.)
\contact{大城 信康\\
	〒903-0213 沖縄県中頭郡西原町字千原1番地\\
	琉球大学 情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
	email: dimolto@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
GCC-4.6 をベースとした CbC コンパイラの実装を行った.
CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており,
以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた.
本論文では GCC-4.6 への CbC の具体的な実装について述べる。


%当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している.
%また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている.
%お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった.


\end{abstract}


% 英文概要
\begin{eabstract}
We implemented Continuation based C Compiler on GCC-4.6.
CbC Compiler on GCC-4.2 was developed on 2008.
Since then we kept to update it.
In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6.

%Continuation based C is programming language. It is developing our laboratory.

\end{eabstract}

% 表題などの出力
\maketitle
\thispagestyle{empty} 

%}{

% 本文はここから始まる
\section{歴史的経緯}
%当研究室では, 継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している.
%CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる.
当研究室ではコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している.
コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより,
 Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている.

CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが,
2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され,
2010年には GCC-4.4 へとアップデートが行われた.
GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.
%以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている.
%今回,CbC コンパイラを GCC-4.6 へとアップデートを行った.
%本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる.
だが, GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.


%}{

\section{Continuation based C (CbC)}
CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る.
構文は C と同じであるが, ループ制御や関数コールが取り除かれる.

%Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である.
%構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている.
%また,コードセグメント単位で処理を記述するという特徴がある.
%図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している.


\subsection{継続(goto)}
コードセグメントの記述は C の関数の構文と同じで, 型に ``\verb+__code+'' を使うことで宣言できる.
コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える.
図\ref{fig:cs}はコードセグメント間の処理の流れを表している.

%コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない.
%コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る.
%この goto によるコードセグメント間の移動を継続と言う.
%継続の実態は jmp による関数の移動となる.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/codesegment.eps}}
  \end{center}
  \caption{コードセグメント間の継続(goto)}
  \label{fig:cs}
\end{figure}

\subsection{コードセグメント(code segment)}
コードセグメントは C の関数と違って返り値を持たず, 処理が終われば次のコードセグメントへと処理を移る.
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
だが, 返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない.

軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.

図\ref{fig:factorial}は CbC で書いたプログラムの例である.
与えられた数 x の階上を計算して出力するプログラムとなっている.

\begin{figure}
\lstinputlisting[language=c]{source/factorial.cbc}
\caption{階上を計算する CbC プログラムの例}
\label{fig:factorial}
\end{figure}

%CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
%コードセグメントの記述の仕方は C の関数と同じだが, 型に ``\_\_code''を使って宣言を行うところだけが違う.
%関数と同じように引数を持たせて継続させることもできる.
%しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.

%コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
%コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.
\section{GCCの3つの内部表現}
GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.

GCC は内部で Generic Tree, GIMPLE, RTL という3つの内部表現を扱う.
それぞれが
読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき,
最後にアセンブラ言語へと出力される.
図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/ir.eps}}
  \end{center}
  \caption{GCC によるコンパイルの一連の流れ}
  \label{fig:ir}
\end{figure}


\subsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の戻値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.

CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


\subsection{GIMPLE}
Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される.
GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる.
制約は「1つの枝に4つ以上の子を持たせない」等といったもので,
GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
CbC の実装では特に修正は加えていない.


\subsection{Register Transfer Language (RTL)}
構文木 GIMPLE は解析が行われた後 RTL へと変換される.
RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
プログラム内部では RTL も木構造で表される.

CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる.


\section{GCC-4.6 への実装}
前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した.
ここからは GCC-4.6 への実装について述べていく.


\subsection{``\_\_code'' のパース}
C の予約後は \verb+gcc/c-family/c-common.c+ の \verb+c_common_reswords+ 構造体で定義されている.
ここに,図\ref{fig:code-parse}のように \verb+code+ の登録を行う.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/code-parse.eps}}
  \end{center}
  \caption{\_\_code のパース}
  \label{fig:code-parse}
\end{figure}


これで \verb+__code+ は \verb+RID_CbC_CODE+ として判定されるようになる.
次に, id を用意する.
 Genric Tree が生成されるデータは一度 \verb+c_declspecs+ 構造体に保存される.
そこに登録するコードセグメント判定用 id  ``\verb+cts_CbC_code+'' を用意する.
これは gcc/c-tree.h で定義される(図\ref{fig:code-id}).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/code-id.eps}}
  \end{center}
  \caption{cts\_CbC\_code の定義}
  \label{fig:code-id}
\end{figure}

後は\verb+c_declspecs+ 構造体にこの id を登録する.
 id の登録は \verb+declspecs_add_type+ 関数の中で行われる(図\ref{fig:regi-id}).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/regi-id.eps}}
  \end{center}
  \caption{id の登録(declspecs\_add\_type 関数)}
  \label{fig:regi-id}
\end{figure}

図\ref{fig:regi-id} のプログラムは void 型の id 登録を元に作られている.
違うところは \verb+cts_CbC_code+ を登録するところだけである.

最後に, \verb+finish_declspecs+ 関数にて id 毎に tree タイプの決定をする.
コードセグメントは void 型として扱ってもらうために \verb+void_type_node+ をタイプと
して登録している(図\ref{fig:regi-node}).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/regi-node.eps}}
  \end{center}
  \caption{declspecs\_add\_type 関数}
  \label{fig:regi-node}
\end{figure}


\subsection{goto シンタックスの追加}
通常 goto のシンタックスは ``goto ラベル名;'' となっている.
CbC では通常の goto に加え ``goto cs();'' の形でコードセグメントを呼び出すシンタックスを追加する必要がある.
図\ref{fig:rid-goto}は, 追加した goto のシンタックスである
(通常のシンタックスは省いてある).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/rid-goto.eps}}
  \end{center}
  \caption{goto へのシンタックスの追加}
  \label{fig:rid-goto}
\end{figure}

%具体的には, 読み込んだ CPP_NAME が関数の場合の処理を追加した.
具体的には
void 型の tree を元にコードセグメントと判定するフラグ と Tail Call のフラグ
を付けた関数として tree の作成を行なっている.

\verb+cbc_replace_argments+ 関数と \verb+c_finish_return+ 関数の動作については
 CbC においても重要になるので後に詳しく説明する.

\subsection{Tail Call Elimination}
CbC の継続の実装には GCC の最適化の1つ, Tail Call Elimination (末尾除去) を強制することで実装する.
これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する.
%Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
%call ではなく jmp を用いることができるという最適化である.
図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.30}{\includegraphics{figure/continuation.eps}}
  \end{center}
  \caption{Tail Call Elimination}
  \label{fig:continue}
\end{figure}
funcB は jmp 命令で funcC を呼び出す.
funcC は, 戻値を funcB ではなく funcA へと返すことになる.

\subsubsection{expand\_call}
ある関数が Tail Call Elimination を行えるかどうかは \verb+expand_call+ 関数で判断される.
\verb+expand_call+ 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.

%\begin{itemize}
\begin{enumerate}
  \item caller 側と callee 側の戻値の型が一致している.
  \item 関数呼び出しがリターンの直前に行われている.
  \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
  \item 引数の並びのコピーに上書きがない.
\end{enumerate}
%\end{itemize}

CbC の実装では上記の条件を,以下の様にして解決させている.

\begin{enumerate}
%\begin{itemize}
%  \item コードセグメントは void 型で統一する. Cの関数からコードセグメントに goto する場合は返す値の型チェックを行わない.
  \item コードセグメントは void 型で統一する. 最適化(-O2)の強制付与.
  \item goto の直後に retrun を置く.
  \item スタックサイズは関数宣言時に決まったサイズにする.
  \item 引数は一旦, 一時変数にコピーして重なりがないようにする.
%\end{itemize}
\end{enumerate}

%1 については自明だろう.コードセグメントは戻値を持たない為 void 型の扱いになる.
%2, 3 と 4 については以下で詳しく説明を行う.
戻値を持たない為, コードセグメントを void 型で統一するのは自明だろう.
最適化の強制付与及び 2, 3 と 4 については以下で詳しく説明を行う.

\subsubsection{末尾最適化の強制付与}
Tail Call Elimination は C のプログラムにおいて末尾最適化を有効にすることで行われる.
以前の GCC の初期の実装では \verb+expand_call+ 関数を元にした \verb+expand_cbc_call+ 関数を作成して,
 条件をクリアするようにしていた.
しかし, その方法では \verb+expand_call+ 関数が改良される度に \verb+expand_cbc_call+ 関数にも
変更を加える必要があり, 手間となっていた.
そこで, 最適化フラグを強制的に付与させることで \verb+expand_cbc_call+ 関数を取り除くことに成功した.

\verb+expand_call+ 関数内では, Tail Call Eliminatino に書けるためのフラグ, \verb+try_tail_call+
 変数があり, コードセグメントはこのフラグには初め 1 がセットされている.
コードセグメントの時はこの \verb+try_tail_call+ 変数に 0 を代入させないように実装を行った.
また, 万が一 \verb+try_tail_call+ 変数に 0 を代入された時の為にフラグに 1 を代入するコードの挿入も行った.
これにより末尾最適化の強制付与がなされた.


\subsubsection{goto の直後に return の配置}
図\ref{fig:factorial}のコードセグメント factorial0 をlisting\ref{code:return}の様に, goto の直後に return を
置く必要がある.だがそれをプログラマが記述することは実用的でない.

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=goto の直後に return を置く,label=code:return]
__code factorial0(int prod, int x)
{
  if ( x >= 1) {
    goto factorial0(prod*x, x-1);
    return;
  }else{
    goto print_factorial(prod);
    return;
  }
}
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}
CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している.
図\ref{fig:rid-goto}の\verb+c_finish_return+ 関数がそれにあたる.

%goto でコードセグメントの継続を行うプログラムの直後に return を表す情報を Generic Tree に追加を行う.

\subsubsection{スタックサイズの固定化}
CbC では継続によりスタックに値が積まれていくということはない為サイズを固定することができる.
また, サイズが固定な為, スタックポインタを変えずにスタックを扱うことができる.
これも CbC の1つの特徴である.
図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/cs_stack.eps}}
  \end{center}
  \caption{継続による引数のスタック格納の様子}
  \label{fig:cs_stack}
\end{figure}

%GCCでは, この他にもTCEを禁止するルールがあり, GCC-4.5, 4.6 でも
%Tail Call Elimination にかからないコードセグメントがある.
%この点を改善する必要がある.

%\subsection{引数の一時変数への避難}
%\subsection{スタック書き換えの問題}
\subsubsection{引数の並びの上書きコピー}
CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる.
例えばlistlising\ref{code:cs_prog}のような継続である.
\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=スタックの上書きが起こる継続の例,label=code:cs_prog]
__code cs_a(int a, int b) {
        goto cs_b(b, a)
}
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}


\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/cs_prog.eps}}
  \end{center}
  \caption{スタック書き換えの問題}
  \label{fig:cs_prog}
\end{figure}
この時のスタックの様子を表したのが図\ref{fig:cs_prog}となる.
数字の 1 と 2 は \verb+cs_b+ の引数をスタックに乗せる順を表している.
CbC ではこの問題を一時変数に引数の値を代入することで問題を解決している.

\subsubsection{一時変数へのコピー}
一時変数へのコピーは, goto が行われた時の, コードセグメントの Generic Tree 生成時に行われる.

図\ref{fig:cbc_replace}に示す \verb+cbc_replace_arguments+ 関数が実際のコードとなる.
%\begin{figure}
%\lstinputlisting[language=c]{source/cbc_replace_arguments.c}
%\caption{引数の一時変数へのコピー}
%\label{fig:cbc_replace}
%\end{figure}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/cbc_replace.eps}}
  \end{center}
  \caption{引数の一時変数へのコピー}
  \label{fig:cbc_replace}
\end{figure}


具体的には, 内部で以下の事が行われている.
\begin{itemize}
\item 引数と同じ型の一時変数を作成
\item 一時変数に引数の値を代入
\item 関数に渡す引数のポインタを一時変数に変更
\end{itemize}

tree call は継続を行うコードセグメントを指す.
コードセグメントに渡された引数の情報を抜き出す部分が \verb+FOR_EACH_CALL_EXPR_ARG+ である.
 \verb+tmp_decl+ という一時変数を作り,最後に \verb+CALL_EXPR_ARG+ を使って引数の情報が入っていた
ところへ一時変数を入れている.

\subsection{環境付き継続}
CbC には通常の C の関数からコードセグメントに継続する際,
 その関数から値を戻す処理への継続を得ることができる.
これを環境付き継続という.
これらは, 以下の二種類の CbC で定義した特殊変数である.
\verb+__environment+ は, 環境を表す情報である.
\verb+__return+ は,  これを環境付き継続の行き先であり, 関数の戻値と \verb+__environment+ の二つの引数を持つ
コードセグメントである. 例えば, 以下のように使うと, \verb+main()+ は 1 を返す.

\begin{verbatim}
__code c1(__code ret(int,void *),void *env) {
    goto ret(1,env);
}

int main() {
    goto c1(__return, __environment);
}
\end{verbatim}

GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す.
戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(Listing\ref{code:_ret_val}).

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val]
__label__ _cbc_exit0;
static int retval;
   void _cbc_internal_return(int retval_,
                            void *_envp){
  retval = retval_;
  goto _cbc_exit0;
}
if (0) {
 _cbc_exit0:
  return retval;
 }
_cbc_internal_return;
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

\subsubsection{環境付き継続の問題}
現在環境付き継続は
このコードを GCC 内部で生成することで実現している. これは正しく動作しているが,
 \verb+retval+に static を指定してしまうと,
 スレッドセーフな実装でなくなる.
これを通常の変数にすると, 関数内の関数は closure として実装される. しかし, GCC 4.6 と Lion の
組合せでは closure は正しく動作してないことがわかった. 
Thread local 変数を用いると, やはり closure が出力されてしまう.
本来は, 戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず,
浮動小数点や構造体自体である可能性があり複雑である. 
一つの解決策はレジスタ渡しと考えているが, 他の方法もありえる. 少し重いが setjmp を用いた実装方法もある.


\subsection{引数渡し}
通常コードセグメントの継続において, 引数は C の関数と同じスタックを用いて渡される.
 GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある.
 fastcall を用いてコードセグメント間を継続することで, 速度の向上を図る.

\subsubsection{fastcall}
C において fastcall を用いる場合は関数にキーワード ``\verb+__attribute__ ((fastcall))+'' をつけて行う.
だが, コードセグメントを全てこのキーワードをつけて宣言することは実用的ではない.
そこで, コードセグメントで宣言された場合, fastcall が自動で付くように実装を行う.
図\ref{fig:fastcall}はコードセグメントの生成を行なっているコードである.

%\lstinputlisting[language=c]{source/fastcall.c}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/fastcall.eps}}
  \end{center}
  \caption{コードセグメントへのfastcall属性付与}
  \label{fig:fastcall}
\end{figure}

13,14 行目が fastcall 属性を付与している部分になる.
if 文で条件を決めているのは, 64 bit の場合 fastcall が標準で行われていて,
 warning を出すからである.


\subsection{typedefrecの実装の構想}
C では関数や構造体の宣言の時に自分自身を引数にすることができない。
そこで ``typedefrec'' という構文を作り、図\ref{code:typedefrec}のような宣言を行えるようにしたい。

%C を基本としている CbC には型推論がない.

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=typedefrecの例,label=code:typedefrec]
typedefrec void *funcA(int, funcA);

typedefrec struct {
  NODE left;
  NODE right;
} *NODE;
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

typedefrec によりコードセグメントは自分自身に戻る構成ができるようになる.
より柔軟なプログラミングが行えるように typdefrec の実装を行う予定である.

\section{評価}
今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース,
Micro-C コンパイラとそれぞれ比較を行った.
比較を行うのはクイックソートのプログラムである.
%クイックソートは再帰的にプログラムされる為 CbC に向いている
%プログラムだと言える.
クイックソートは再帰的なプログラムな為スタック操作が行われる.
比較を行うのは以下のアーキテクチャと OS になる.

%\begin{description}
\begin{itemize}
  \item x86/Linux
  \item x86/OS X
\end{itemize}
%\end{description}

また,比較を行うプログラムは最適化(-O0 オプション)を行わないものと,
速度最適化(-O2 -fomit-frame-pointer)を行うものの2つ,
それと -m32 オプションと -m64 オプションをつけたものそれぞれで行う.

表\ref{tab:speed-mc-vs-gcc-nonopt}が最適化無し,
表\ref{tab:speed-mc-vs-gcc-opt}が速度最適化有りとなる.


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 7.378 & 0.833 & 2.923 \\ \hline
 x86\_64/OS X(-m32)& 5.951 & 0.507 &  2.871\\ \hline
 x86\_64/OS X      & 6.420 & 0.621 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較(単位: 秒)(最適化無し)}
  \label{tab:speed-mc-vs-gcc-nonopt}
\end{table}


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 3.253 & 2.906 & 2.71 \\ \hline
 x86\_64/OS X(-m32)& 2.726 & 2.418 &  2.857\\ \hline
 x86\_64/OS X      & 1.390 &  1.509 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較(単位: 秒)(速度最適化)}
  \label{tab:speed-mc-vs-gcc-opt}
\end{table}


\section{CbC のアップデート手法}
最後に, CbC のアップデート手法について述べる.

現在 GCC は年に数回アップデートが行われている.
GCC に合わせて CbC のアップデートを行うのが好ましいが,
 その度新しいソースコードに合わせていくのは負担が大きい.
GCC の正式な機能として CbC を組み込んで貰うことが最良の方法だが
現時点ではまだそこまで至っていない.

そこで Mercurial を使ってアップデート方法を行なっている.

\subsection{Mercurial によるアップデート}
Mercurial はバージョン管理システムである.
当研究室では CbC のソースコードは Mercurial によって管理されている.
Mercurial では本家 GCC のソースコードも管理されており,
これら 2 つのリポジトリを使って CbC のアップデートは行われる(図\ref{fig:mercurial}).
具体的な方法は以下になる.

\begin{itemize}
\item GCC リポジトリ
\begin{enumerate}
\item GCC リポジトリの中身を削除 (バージョン管理情報以外)
\item 新しい GCC のソース入れる
\item hg status で追加ファイルと削除ファイルを確認
\item 追加, 削除するファイルに対して hg add, hg remove を行う
\item コミット
\item gcc version タグを追加
\end{enumerate}

\item CbC リポジトリ
\begin{enumerate}
\item GCC リポジトリから hg pull を行う
\item hg merge でマージを行う
\item 衝突が発生したファイルのマージを行う
\item ビルドを行い動作確認
\item コミット
\item gcc version タグを追加
\end{enumerate}
\end{itemize}


\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/mercurial_update.eps}}
  \end{center}
  \caption{CbConGCC リポジトリの管理(左:本家GCC 中央:独自のGCCリポジトリ 右:CbConGCC リポジトリ)}
  \label{fig:mercurial}
\end{figure}


\subsection{リポジトリ管理方法の評価}
上記のリポジトリ管理方法を用いて GCC-4.5.0 から GCC-4.6.0 へのアップデートを行った.
この手法を用いらない場合は手動で diff を行い差分を探すことになる.
%この手法を用いらない場合は手動で diff をとり差分を適用するという方法を,
% ファイル全てに行う必要があった.
だが, 上記の手法ではほとんどの差分を Mercurial 自身がおこなってくれた.
手動で差分を直したのは CbC の実装を行ったファイルだけで済んだ.
若干ファイルの移動や追加があり戸惑ったが, アップデートは楽に行えた.




\section{まとめと今後の課題}
今回 CbC コンパイラを GCC-4.6 へとアップデートを行った.
アップデートに伴い不具合の修正と Intel64 ビットへの対応を行った.
だが, 環境付き継続等未だ幾つかの問題を残している.
また, typedefrec の様に新たに実装を行いたい機能もでてきている.



\nocite{kono:2002a, kono:2000a, kono:2008a, yogi:2008a, yogi:2008b, yan:2002a,gcc_internals}
\bibliographystyle{junsrt}
\bibliography{cbc.bib}

\end{document}
\ No newline at end of file
+\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}
\usepackage{jtygm}


% 巻数,号数などの設定
%\setcounter{巻数}{41}
%\setcounter{号数}{6}
%\setcounter{volpageoffset}{1234}
%\受付{12}{2}{4}
%\採録{12}{5}{11}

\pagestyle{empty}

% ユーザが定義したマクロなど.
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
%\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[Continuation based C の GCC 4.6 上の実装について]%
	{Continuation based C の GCC 4.6 上の実装について}
% 英文表題
\etitle{The implementation of Continuation based C Compiler on GCC 4.6}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{大城 信康\affiref{URYUKYU}\nomember\and
	河野 真治\affiref{URYUKYU}\member{19841765}}
	

% 英文著者名
\eauthor{Nobuyasu Oshiro\affiref{URYUKYU}\and
	Shinji Kono\affiref{URYUKYU}}

% 連絡先(投稿時に必要.製版用では無視される.)
\contact{大城 信康\\
	〒903-0213 沖縄県中頭郡西原町字千原1番地\\
	琉球大学 情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
	email: dimolto@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
GCC-4.6 をベースとした CbC コンパイラの実装を行った.
CbC のコンパイラは GCC-4.2 ベースのコンパイラが2008年に開発されており,
以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた.
本論文では GCC-4.6 への CbC の具体的な実装について述べる。


%当研究室では継続を基本としたプログラミング言語 Continuation basede C (以下CbC) を開発している.
%また,CbC 自体の開発と共に CbC のコンパイラの開発も行っている.
%お陰で GCC の最適化やデバッグの機能を CbC のプログラミングで扱うことができるようになった.


\end{abstract}


% 英文概要
\begin{eabstract}
We implemented Continuation based C Compiler on GCC-4.6.
CbC Compiler on GCC-4.2 was developed on 2008.
Since then we kept to update it.
In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6.

%Continuation based C is programming language. It is developing our laboratory.

\end{eabstract}

% 表題などの出力
\maketitle
\thispagestyle{empty} 

%}{

% 本文はここから始まる
\section{歴史的経緯}
%当研究室では, 継続により処理を行うプログラミング言語 Continuation based C (以下CbC) を開発している.
%CbC の構文は C と同じであるが,継続によりループ制御や関数コールが取り除かれる.
当研究室ではコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している.
コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより,
 Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている.

CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが,
2008年の研究において GCC-4.2 ベースの CbC コンパイラが開発され,
2010年には GCC-4.4 へとアップデートが行われた.
GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.
%以来,GCC のアップデートに合わせて GCC ベースの CbC コンパイラのアップデートを行って来ている.
%今回,CbC コンパイラを GCC-4.6 へとアップデートを行った.
%本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる.
だが, GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
本研究では, GCC-4.5.0 をベースとしていた CbC-GCC を GCC-4.6.0 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.


%}{

\section{Continuation based C (CbC)}
CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る.
構文は C と同じであるが, ループ制御や関数コールが取り除かれる.

%Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である.
%構文は C と同じであるが,ループ制御や関数コールを取り除き継続(goto)を用いている.
%また,コードセグメント単位で処理を記述するという特徴がある.
%図\ref{fig:cs}は CbC におけるプログラムの処理の流れを表している.


\subsection{継続(goto)}
コードセグメントの記述は C の関数の構文と同じで, 型に ``\verb+__code+'' を使うことで宣言できる.
コードセグメントへの移動は ``goto'' の後にコードセグメント名と引数を並べて記述することで行える.
図\ref{fig:cs}はコードセグメント間の処理の流れを表している.

%コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない.
%コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る.
%この goto によるコードセグメント間の移動を継続と言う.
%継続の実態は jmp による関数の移動となる.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/codesegment.eps}}
  \end{center}
  \caption{コードセグメント間の継続(goto)}
  \label{fig:cs}
\end{figure}

\subsection{コードセグメント(code segment)}
コードセグメントは C の関数と違って返り値を持たず, 処理が終われば次のコードセグメントへと処理を移る.
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
だが, 返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない.

軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.

図\ref{fig:factorial}は CbC で書いたプログラムの例である.
与えられた数 x の階上を計算して出力するプログラムとなっている.

\begin{figure}
\begin{footnotesize}
\lstinputlisting[language=c]{source/factorial.cbc}
\caption{階上を計算する CbC プログラムの例}
\label{fig:factorial}
\end{footnotesize}
\end{figure}


\section{GCCの3つの内部表現}
GCC-4.6 への実装の前に,GCC で扱われる3つの内部表現について触れておく.

GCC は内部で Generic Tree, GIMPLE Tree, RTL という3つの内部表現を扱う.
それぞれが
読み込んだソースコードは Generic Tree, GIMPLE Tree, RTL の順に変換されていき,
最後にアセンブラ言語へと出力される.
図\ref{fig:ir}は GCC がソースコードを読み込みアセンブラ言語出力までの流れを表した図である.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/ir.eps}}
  \end{center}
  \caption{GCC によるコンパイルの一連の流れ}
  \label{fig:ir}
\end{figure}


\subsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の戻値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.

CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


\subsection{GIMPLE Tree}
Generic Tree で表現されたデータは GIMPLE Tree に変換される.
GIMPLE Tree は Generic Tree より制約がかかった状態で作成された構文木となる.
制約は「1つの枝に4つ以上の子を持たせない」等といったもので,
GIMPLE Tree へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる.
CbC の実装では特に修正は加えていない.


\subsection{Register Transfer Language (RTL)}
GIMPLE Tree は解析が行われた後 RTL へと変換される.
RTL はレジスタの割り当てといった低レベルの表現で,アセンブラとほぼ同じ表現を行うことができる.
プログラム内部では RTL も木構造で表される.

CbC における継続は,この RTL への変換で行われる最適化の1つ Tail Call Elimination が重要となってくる.


\section{GCC-4.6 への実装}
前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した.
ここからは GCC-4.6 への実装について述べていく.


\subsection{``\_\_code'' のパース}
C の予約後は \verb+gcc/c-family/c-common.c+ の \verb+c_common_reswords+ 構造体で定義されている.
ここに,図\ref{fig:code-parse}のように \verb+__code+ 型の登録を行う.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/code-parse.eps}}
  \end{center}
  \caption{\_\_code のパース}
  \label{fig:code-parse}
\end{figure}


これで \verb+__code+ は \verb+RID_CbC_CODE+ として判定されるようになる.
次に, id を用意する.
 Genric Tree が生成されるデータは一度 \verb+c_declspecs+ 構造体に保存される.
そこに登録するコードセグメント判定用 id  ``\verb+cts_CbC_code+'' を用意する.
これは gcc/c-Tree.h で定義される(図\ref{fig:code-id}).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/code-id.eps}}
  \end{center}
  \caption{cts\_CbC\_code の定義}
  \label{fig:code-id}
\end{figure}

後は\verb+c_declspecs+ 構造体にこの id を登録する.
 id の登録は \verb+declspecs_add_type+ 関数の中で行われる(図\ref{fig:regi-id}).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/regi-id.eps}}
  \end{center}
  \caption{id の登録(declspecs\_add\_type 関数)}
  \label{fig:regi-id}
\end{figure}

図\ref{fig:regi-id} のプログラムは void 型の id 登録を元に作られている.
違うところは \verb+cts_CbC_code+ を登録するところだけである.

最後に, \verb+finish_declspecs+ 関数にて id 毎に Tree タイプの決定をする.
コードセグメントは void 型として扱ってもらうために \verb+void_type_node+ を Tree のタイプと
して登録している(図\ref{fig:regi-node}).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/regi-node.eps}}
  \end{center}
  \caption{declspecs\_add\_type 関数}
  \label{fig:regi-node}
\end{figure}


\subsection{goto シンタックスの追加}
通常 goto のシンタックスは ``goto ラベル名;'' となっている.
CbC では通常の goto に加え ``goto cs();'' の形でコードセグメントを呼び出すシンタックスを追加する必要がある.
図\ref{fig:rid-goto}は, 追加した goto のシンタックスである
(通常のシンタックスは省いてある).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/rid-goto.eps}}
  \end{center}
  \caption{goto へのシンタックスの追加}
  \label{fig:rid-goto}
\end{figure}

%具体的には, 読み込んだ CPP_NAME が関数の場合の処理を追加した.
具体的には
void 型の Tree を作成している.加えてコードセグメントと判定するフラグ と Tail Call のフラグ
を付けた関数とした Tree となる.
%の作成を行なっている.

\verb+cbc_replace_argments+ 関数と \verb+c_finish_return+ 関数の動作については
 CbC においても重要になるので後に詳しく説明する.

\subsection{Tail Call Elimination}
CbC の継続の実装には GCC の最適化の1つ, Tail Call Elimination (末尾除去) を強制することで実装する.
これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する.
%Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
%call ではなく jmp を用いることができるという最適化である.
図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.30}{\includegraphics{figure/continuation.eps}}
  \end{center}
  \caption{Tail Call Elimination}
  \label{fig:continue}
\end{figure}
funcB は jmp 命令で funcC を呼び出す.
funcC は, 戻値を funcB ではなく funcA へと返すことになる.

\subsubsection{expand\_call}
\verb+expand_call+ 関数は, 関数を表す Tree から RTL を生成する関数である.
 Tail Call Elimination を行えるかどうかもこの関数で判断される.
内部でチェックされる Tail Call Elimination の条件は以下になる.
%\verb+expand_call+ 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.

%\begin{itemize}
\begin{enumerate}
  \item caller 側と callee 側の戻値の型が一致している.
  \item 関数呼び出しがリターンの直前に行われている.
  \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
  \item 引数の並びのコピーに上書きがない.
\end{enumerate}
%\end{itemize}

CbC の実装では上記の条件を,以下の様にして解決させている.

\begin{enumerate}
%\begin{itemize}
%  \item コードセグメントは void 型で統一する. Cの関数からコードセグメントに goto する場合は返す値の型チェックを行わない.
  \item コードセグメントは void 型で統一する. 最適化(-O2)の強制付与.
  \item goto の直後に retrun を置く.
  \item スタックサイズは関数宣言時に決まったサイズにする.
  \item 引数は一旦, 一時変数にコピーして重なりがないようにする.
%\end{itemize}
\end{enumerate}

%1 については自明だろう.コードセグメントは戻値を持たない為 void 型の扱いになる.
%2, 3 と 4 については以下で詳しく説明を行う.
戻値を持たない為, コードセグメントを void 型で統一するのは自明だろう.
最適化の強制付与及び 2, 3 と 4 については以下で詳しく説明を行う.

\subsubsection{末尾最適化の強制付与}
Tail Call Elimination は C のプログラムにおいて末尾最適化を有効にすることで行われる.
以前の CbC-GCC の実装では \verb+expand_call+ 関数を元にした \verb+expand_cbc_call+ 関数を作成して,
 条件をクリアするようにしていた.
しかし, その方法では \verb+expand_call+ 関数が改良される度に \verb+expand_cbc_call+ 関数にも
変更を加える必要があり, 手間となっていた.
そこで, 最適化フラグを強制的に付与させることで \verb+expand_cbc_call+ 関数を取り除くことに
成功した(図\ref{fig:tail_call}:2行目).

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/tail_call_flag.eps}}
  \end{center}
  \caption{コードセグメントの末尾最適化の付与}
  \label{fig:tail_call}
\end{figure}


\verb+expand_call+ 関数内では, Tail Call Eliminatino にかけるためのフラグ, \verb+try_tail_call+
 変数があり, コードセグメントはこのフラグには初め 1 がセットされている.
コードセグメントの時はこの \verb+try_tail_call+ 変数に 0 を代入させないように実装を行った.
また, 万が一 \verb+try_tail_call+ 変数に 0 を代入された時の為にフラグに 1 を代入するコードの挿入も行った.
これにより末尾最適化の強制付与がなされた.


\subsubsection{goto の直後に return の配置}
図\ref{fig:factorial}のコードセグメント factorial0 をlisting\ref{code:return}の様に, goto の直後に return を
置く必要がある.だがそれをプログラマが記述することは実用的でない.

\begin{figure}[h]
\begin{footnotesize}
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=goto の直後に return を置く,label=code:return]
__code factorial0(int prod, int x)
{
  if ( x >= 1) {
    goto factorial0(prod*x, x-1);
    return;
  }else{
    goto print_factorial(prod);
    return;
  }
}
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{footnotesize}
\end{figure}
CbC では Generic Tree の生成時に継続の直後に return を自動で組み込むことで解決している.
図\ref{fig:rid-goto}の\verb+c_finish_return+ 関数がそれにあたる.

%goto でコードセグメントの継続を行うプログラムの直後に return を表す情報を Generic Tree に追加を行う.

\subsubsection{スタックサイズの固定化}
CbC では継続によりスタックに値が積まれていくということはない為サイズを固定することができる.
また, サイズが固定な為, スタックポインタを変えずにスタックを扱うことができる.
これも CbC の1つの特徴である.
図\ref{fig:cs_stack}はコードセグメントの継続の際にスタックに積まれる引数を表している.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.30}{\includegraphics{figure/cs_stack.eps}}
  \end{center}
  \caption{継続による引数のスタック格納の様子}
  \label{fig:cs_stack}
\end{figure}

%GCCでは, この他にもTCEを禁止するルールがあり, GCC-4.5, 4.6 でも
%Tail Call Elimination にかからないコードセグメントがある.
%この点を改善する必要がある.

%\subsection{引数の一時変数への避難}
%\subsection{スタック書き換えの問題}
\subsubsection{引数の並びの上書きコピー}
CbC の継続では, 引数渡しでスタックを入れ替える為値が書き換えられる可能性がでてくる.
例えばlistlising\ref{code:cs_prog}のような継続である.
\begin{figure}[h]
\begin{footnotesize}
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=スタックの上書きが起こる継続の例,label=code:cs_prog]
__code cs_a(int a, int b) {
        goto cs_b(b, a)
}
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{footnotesize}
\end{figure}


\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/cs_prog.eps}}
  \end{center}
  \caption{スタック書き換えの問題}
  \label{fig:cs_prog}
\end{figure}
この時のスタックの様子を表したのが図\ref{fig:cs_prog}となる.
数字の 1 と 2 は \verb+cs_b+ の引数をスタックに乗せる順を表している.
CbC ではこの問題を一時変数に引数の値を代入することで問題を解決している.

\subsubsection{一時変数へのコピー}
一時変数へのコピーは, goto が行われた時の, コードセグメントの Generic Tree 生成時に行われる.

図\ref{fig:cbc_replace}に示す \verb+cbc_replace_arguments+ 関数が実際のコードとなる.
%\begin{figure}
%\lstinputlisting[language=c]{source/cbc_replace_arguments.c}
%\caption{引数の一時変数へのコピー}
%\label{fig:cbc_replace}
%\end{figure}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/cbc_replace.eps}}
  \end{center}
  \caption{引数の一時変数へのコピー}
  \label{fig:cbc_replace}
\end{figure}


具体的には, 内部で以下の事が行われている.
\begin{itemize}
\item 引数と同じ型の一時変数を作成
\item 一時変数に引数の値を代入
\item 関数に渡す引数のポインタを一時変数に変更
\end{itemize}

Tree call は継続を行うコードセグメントを指す.
コードセグメントに渡された引数の情報を抜き出す部分が \verb+FOR_EACH_CALL_EXPR_ARG+ である.
 \verb+tmp_decl+ という一時変数を作り,最後に \verb+CALL_EXPR_ARG+ を使って引数の情報が入っていた
ところへ一時変数を入れている.

\subsection{環境付き継続}
CbC には通常の C の関数からコードセグメントに継続する際,
 その関数から値を戻す処理への継続を得ることができる.
これを環境付き継続という.
これらは, 以下の二種類の CbC で定義した特殊変数である.
\verb+__environment+ は, 環境を表す情報である.
\verb+__return+ は,  これを環境付き継続の行き先であり, 関数の戻値と \verb+__environment+ の二つの引数を持つ
コードセグメントである. 例えば, 以下のように使うと, \verb+main()+ は 1 を返す.

\begin{verbatim}
__code c1(__code ret(int,void *),void *env) {
    goto ret(1,env);
}

int main() {
    goto c1(__return, __environment);
}
\end{verbatim}

GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す.
戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(Listing\ref{code:_ret_val}).

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val]
__label__ _cbc_exit0;
static int retval;
   void _cbc_internal_return(int retval_,
                            void *_envp){
  retval = retval_;
  goto _cbc_exit0;
}
if (0) {
 _cbc_exit0:
  return retval;
 }
_cbc_internal_return;
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

\subsubsection{環境付き継続の問題}
現在環境付き継続は
このコードを GCC 内部で生成することで実現している. これは正しく動作しているが,
 \verb+retval+に static を指定してしまうと,
 スレッドセーフな実装でなくなる.
これを通常の変数にすると, 関数内の関数は closure として実装される. しかし, GCC 4.6 と Lion の
組合せでは closure は正しく動作してないことがわかった. 
Thread local 変数を用いると, やはり closure が出力されてしまう.
本来は, 戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず,
浮動小数点や構造体自体である可能性があり複雑である. 
一つの解決策はレジスタ渡しと考えているが, 他の方法もありえる. 少し重いが setjmp を用いた実装方法もある.


\subsection{引数渡し}
通常コードセグメントの継続において, 引数は C の関数と同じスタックを用いて渡される.
 GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある.
 fastcall を用いてコードセグメント間を継続することで, 速度の向上を図る.

\subsubsection{fastcall}
C において fastcall を用いる場合は関数にキーワード ``\verb+__attribute__ ((fastcall))+'' をつけて行う.
だが, コードセグメントを全てこのキーワードをつけて宣言することは実用的ではない.
そこで, コードセグメントで宣言された場合, fastcall が自動で付くように実装を行う.
図\ref{fig:fastcall}はコードセグメントの生成を行なっているコードである.

%\lstinputlisting[language=c]{source/fastcall.c}

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/fastcall.eps}}
  \end{center}
  \caption{コードセグメントへのfastcall属性付与}
  \label{fig:fastcall}
\end{figure}

13,14 行目が fastcall 属性を付与している部分になる.
if 文で条件を決めているのは, 64 bit の場合 fastcall が標準で行われていて,
 warning を出すからである.


\subsection{typedefrecの実装の構想}
C では関数や構造体の宣言の時に自分自身を引数にすることができない。
そこで ``typedefrec'' という構文を作り、図\ref{code:typedefrec}のような宣言を行えるようにしたい。

%C を基本としている CbC には型推論がない.

\begin{figure}[h]
  \begin{minipage}[b]{.45\textwidth}
    \begin{lstlisting}[caption=typedefrecの例,label=code:typedefrec]
typedefrec void *funcA(int, funcA);

typedefrec struct {
  NODE left;
  NODE right;
} *NODE;
    \end{lstlisting}
  \end{minipage}
  \hfill
\end{figure}

typedefrec によりコードセグメントは自分自身に戻る構成ができるようになる.
より柔軟なプログラミングが行えるように typdefrec の実装を行う予定である.

\section{評価}
今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース,
Micro-C コンパイラとそれぞれ比較を行った.
比較を行うのはクイックソートのプログラムである.
%クイックソートは再帰的にプログラムされる為 CbC に向いている
%プログラムだと言える.
クイックソートは再帰的なプログラムな為スタック操作が行われる.
比較を行うのは以下のアーキテクチャと OS になる.

%\begin{description}
\begin{itemize}
  \item x86/Linux
  \item x86/OS X
\end{itemize}
%\end{description}

また,比較を行うプログラムは最適化(-O0 オプション)を行わないものと,
速度最適化(-O2 -fomit-frame-pointer)を行うものの2つ,
それと -m32 オプションと -m64 オプションをつけたものそれぞれで行う.

表\ref{tab:speed-mc-vs-gcc-nonopt}が最適化無し,
表\ref{tab:speed-mc-vs-gcc-opt}が速度最適化有りとなる.


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 7.378 & 0.833 & 2.923 \\ \hline
 x86\_64/OS X(-m32)& 5.951 & 0.507 &  2.871\\ \hline
 x86\_64/OS X      & 6.420 & 0.621 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較(単位: 秒)(最適化無し)}
  \label{tab:speed-mc-vs-gcc-nonopt}
\end{table}


\begin{table}[htpb]
  \centering
  \small
  \begin{tabular}{|c|c|c|c|} \hline
      CPU/OS      &GCC-4.4& GCC-4.6 &Micro-C  \\ \hline
    x86/Linux     & 3.253 & 2.906 & 2.71 \\ \hline
 x86\_64/OS X(-m32)& 2.726 & 2.418 &  2.857\\ \hline
 x86\_64/OS X      & 1.390 &  1.509 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較(単位: 秒)(速度最適化)}
  \label{tab:speed-mc-vs-gcc-opt}
\end{table}


\section{CbC のアップデート手法}
最後に, CbC のアップデート手法について述べる.

現在 GCC は年に数回アップデートが行われている.
GCC に合わせて CbC のアップデートを行うのが好ましいが,
 その度新しいソースコードに合わせていくのは負担が大きい.
GCC の正式な機能として CbC を組み込んで貰うことが最良の方法だが
現時点ではまだそこまで至っていない.

そこで Mercurial を使ってアップデート方法を行なっている.

\subsection{Mercurial によるアップデート}
Mercurial はバージョン管理システムである.
当研究室では CbC のソースコードは Mercurial によって管理されている.
Mercurial では本家 GCC のソースコードも管理されており,
これら 2 つのリポジトリを使って CbC のアップデートは行われる(図\ref{fig:mercurial}).
具体的な方法は以下になる.

\begin{itemize}
\item GCC リポジトリ
\begin{enumerate}
\item GCC リポジトリの中身を削除 (バージョン管理情報以外)
\item 新しい GCC のソース入れる
\item hg status で追加ファイルと削除ファイルを確認
\item 追加, 削除するファイルに対して hg add, hg remove を行う
\item コミット
\item gcc version タグを追加
\end{enumerate}

\item CbC リポジトリ
\begin{enumerate}
\item GCC リポジトリから hg pull を行う
\item hg merge でマージを行う
\item 衝突が発生したファイルのマージを行う
\item ビルドを行い動作確認
\item コミット
\item gcc version タグを追加
\end{enumerate}
\end{itemize}


\begin{figure}[htpb]
  \begin{center}
\scalebox{0.33}{\includegraphics{figure/mercurial_update.eps}}
  \end{center}
  \caption{CbConGCC リポジトリの管理(左:本家GCC 中央:独自のGCCリポジトリ 右:CbConGCC リポジトリ)}
  \label{fig:mercurial}
\end{figure}


\subsection{リポジトリ管理方法の評価}
上記のリポジトリ管理方法を用いて GCC-4.5.0 から GCC-4.6.0 へのアップデートを行った.
この手法を用いらない場合は手動で diff を行い差分を探すことになる.
%この手法を用いらない場合は手動で diff をとり差分を適用するという方法を,
% ファイル全てに行う必要があった.
だが, 上記の手法ではほとんどの差分を Mercurial 自身がおこなってくれた.
手動で差分を直したのは CbC の実装を行ったファイルだけで済んだ.
若干ファイルの移動や追加があり戸惑ったが, アップデートは楽に行えた.




\section{まとめと今後の課題}
今回 CbC コンパイラを GCC-4.6 へとアップデートを行った.
アップデートに伴い不具合の修正と Intel64 ビットへの対応を行った.
だが, 環境付き継続等未だ幾つかの問題を残している.
また, typedefrec の様に新たに実装を行いたい機能もでてきている.



\nocite{kono:2002a, kono:2000a, kono:2008a, yogi:2008a, yogi:2008b, yan:2002a,gcc_internals}
\bibliographystyle{junsrt}
\bibliography{cbc.bib}

\end{document}
\ No newline at end of file