changeset 9:de1193768ef9

modify
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 19 Nov 2011 18:03:15 +0900
parents 3d1135b3519c
children 3d1f778dc358
files Paper/figure/continuation.eps Paper/figure/continuation.graffle Paper/nobu-prosym.aux Paper/nobu-prosym.dvi Paper/nobu-prosym.log Paper/nobu-prosym.pdf Paper/nobu-prosym.tex Paper/nobu-prosym.tex~
diffstat 8 files changed, 495 insertions(+), 163 deletions(-) [+]
line wrap: on
line diff
--- a/Paper/figure/continuation.eps	Fri Nov 18 18:11:00 2011 +0900
+++ b/Paper/figure/continuation.eps	Sat Nov 19 18:03:15 2011 +0900
@@ -1,5 +1,5 @@
 %!PS-Adobe-3.0 EPSF-3.0
-%%HiResBoundingBox: 0.000000 0.000000 267.000000 271.000000
+%%HiResBoundingBox: 0.000000 0.000000 281.000000 290.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 267 271
+%%BoundingBox: 0 0 422 435
 %%EndComments
 %%BeginProlog
 %%BeginFile: cg-pdf.ps
@@ -641,7 +641,7 @@
 %%BeginSetup
 %%EndSetup
 %%Page: 1 1
-%%PageBoundingBox: 0 0 267 271
+%%PageBoundingBox: 0 0 422 435
 %%BeginPageSetup
 cg_md begin
 bp
@@ -708,6 +708,78 @@
 
%RBIEndFontSubset
 /Helvetica cguidfix
 /F1.1/Helvetica renmfont
+%RBIBeginFontSubset: Helvetica
+%!FontType1-1.0: Helvetica 1.0000.0.0000
+
14 dict begin/FontName /Helvetica def
+
/PaintType 0 def
+
/Encoding 256 array 0 1 255{1 index exch/.notdef put}for
+
dup 33 /c put
+
dup 34 /a put
+
dup 35 /l put
+
dup 36 /j put
+
dup 37 /m put
+
dup 38 /p put
+
dup 39 /r put
+
dup 40 /e put
+
dup 41 /t put
+
dup 42 /u put
+
dup 43 /n put
+
readonly def
+
42/FontType resourcestatus{pop pop false}{true}ifelse
+
%APLsfntBegin
+
{currentfile 0(%APLsfntEnd\n)/SubFileDecode filter flushfile}if
+
/FontType 42 def
+
/FontMatrix matrix def
+
/FontBBox[2048 -1947 1 index div -985 2 index div 2961 3 index div 2297 5 -1 roll div]cvx def
+
/sfnts [<
+
74727565000900000000000063767420000000000000009C0000036C6670676D000000000000040800000A1D676C79660000000000000E28000009C06865616400000000000017E80000003668686561000000000000182000000024686D74780000000000001844000000306C6F636100000000000018740000001A6D6178700000000000001890000000207072657000000000000018B0000003CF05C0001005BD00280580001A042F001F0000FFD90000FFDA0000FFD9FE55FFE605C70010FE6DFFF1033B000000B9000000B902FE3F3C00C0008D009B00AF000600A800C00028005E009800C9016A00B9015C00B400D6011E002E0080000400B8004C00CC01FFFFD1006600A400AF007400C2009500B1000C0028006D0015004C008E0125FF7A000C0040004C00620084FFA200240038008600BD0039005E008E00EDFFA9FFB300400052005500AA00AB00C200CB012302B10413FFAEFFE4000800510074008400AA00D1FF4CFFAF0012002C004200500051008400BE012503DAFF680018003B0098009C009F00A100C100EC018201B4FF68FF76FFD0FFE100020018001C00530053007D01B401E103AF0486FF9CFFEAFFFE001F0028002A00520060009300A300AA00AF00AF00C001000145016B0174019301950240028202B404850517FEFD00060029004700470048006F008800B400B900C400F200F901EF02180310037403C5FF35FFF3000B004B004C0052005500650076007600870087008E00AB00BB0106013001430150017D0194019501D3022A025502580277027802E6034E035C037903D3047304B2058C0598060BFEF5FFBBFFC7FFD50017001D005B0072007E009C00C200D000F400FA01030106011C0125013B0142015E015E0180019B02B901A101B9025001C001D002AA01DF01E301EF01FB0205020C0215022B0274029302AB02C202CE03690395039903DF03F5043E050205A105E5062507DBFE62FE89FECEFF3BFFE1FFF800030008002100390042004E005F0061006F00700034007F008E00AD00AD00AF00BD00C400C500C900C900C900E3011C00ED00F800F901000112011A0132014D014D014E014F01660169019E01BA01BA01BE01E301EF01F602000200020902110217021C02530262026D028002D50280031B032A034A035A03AF03AF03C803D603FB03FB04050413041504470449008C046D049A049A04A604A804B204CF0539053E054E055605800589058C036305D105D6067E068E06B206EF06F00728074C076F078C00B400C900C000C10000000000000000000000000004012400AF0032006E0063014401620096014301A10161008A00740064018801EF01700028FF5D037E0347023000AA00BE007B0062009A007D0089035C00A1FFD803AA00D70093006C0000008000A70442001D0597001D00820030002A
+
002A002A002A002A40292A292827262524232221201F1E1D1C1B1A191817161514131211100D0C0B0A090807060504030201002C4523466020B02660B004262348482D2C452346236120B02661B004262348482D2C45234660B0206120B04660B004262348482D2C4523462361B0206020B02661B02061B004262348482D2C45234660B0406120B06660B004262348482D2C4523462361B0406020B02661B04061B004262348482D2C0110203C003C2D2C20452320B0CD442320B8015A51582320B08D44235920B0ED51582320B04D44235920B09051582320B00D44235921212D2C20204518684420B001602045B04676688A4560442D2C01B9400000000A2D2C00B9000040000B2D2C2045B00043617D6818B0004360442D2C45B01A234445B01923442D2C2045B00325456164B050515845441B2121592D2C20B0032552582359212D2C69B04061B0008B0C6423648BB8400062600C642364615C58B0036159B002602D2C45B0112BB0172344B0177AE5182D2C45B0112BB01723442D2C45B0112BB017458CB0172344B0177AE5182D2CB002254661658A46B040608B482D2CB0022546608A46B040618C482D2C4B53205C58B002855958B00185592D2C20B0032545B019236A4445B01A23444565234520B00325606A20B009234223688A6A606120B0005258B21A401A4523614459B0005058B219401945236144592D2CB9187E3B210B2D2CB92D412D410B2D2CB93B21187E0B2D2CB93B21E7830B2D2CB92D41D2C00B2D2CB9187EC4E00B2D2C4B525845441B2121592D2C0120B003252349B04060B0206320B000525823B002253823B002256538008A63381B212121212159012D2C456920B00943B0022660B00325B005254961B0805358B21940194523616844B21A401A4523606A44B209191A45652345604259B00943608A103A2D2C01B005251023208AF500B0016023EDEC2D2C01B005251023208AF500B0016123EDEC2D2C01B0062510F500EDEC2D2C20B001600110203C003C2D2C20B001610110203C003C2D2C764520B003254523616818236860442D2C7645B00325452361682318456860442D2C7645B0032545616823452361442D2C4569B014B0324B505821B0205961442DB8002B2C4BB800095058B101018E59B801FF85B800441DB9000900035F5E2DB8002C2C2020456944B001602DB8002D2CB8002C2A212DB8002E2C2046B003254652582359208A208A49648A204620686164B004254620686164525823658A592F20B00053586920B000545821B040591B6920B000545821B0406559593A2DB8002F2C2046B00425465258238A592046206A6164B0042546206A61645258238A592FFD2DB800302C4B20B0032650585158B080441BB04044591B21212045B0C05058B0C0441B2159592DB800312C2020456944B0016020
+
20457D691844B001602DB800322CB800312A2DB800332C4B20B003265358B0801BB040598A8A20B0032653582321B0C08A8A1B8A235920B0032653582321B801008A8A1B8A235920B0032653582321B801408A8A1B8A235920B80003265358B0032545B8018050582321B8018023211BB003254523212321591B2159442DB800342C4B535845441B2121592DB800352C4BB800095058B101018E59B801FF85B800441DB9000900035F5E2DB800362C2020456944B001602DB800372CB800362A212DB800382C2046B003254652582359208A208A49648A204620686164B004254620686164525823658A592F20B00053586920B000545821B040591B6920B000545821B0406559593A2DB800392C2046B00425465258238A592046206A6164B0042546206A61645258238A592FFD2DB8003A2C4B20B0032650585158B080441BB04044591B21212045B0C05058B0C0441B2159592DB8003B2C2020456944B001602020457D691844B001602DB8003C2CB8003B2A2DB8003D2C4B20B003265358B0801BB040598A8A20B0032653582321B0C08A8A1B8A235920B0032653582321B801008A8A1B8A235920B0032653582321B801408A8A1B8A235920B80003265358B0032545B8018050582321B8018023211BB003254523212321591B2159442DB8003E2C4B535845441B2121592DB8003F2C4BB800095058B101018E59B801FF85B800441DB9000900035F5E2DB800402C2020456944B001602DB800412CB800402A212DB800422C2046B003254652582359208A208A49648A204620686164B004254620686164525823658A592F20B00053586920B000545821B040591B6920B000545821B0406559593A2DB800432C2046B00425465258238A592046206A6164B0042546206A61645258238A592FFD2DB800442C4B20B0032650585158B080441BB04044591B21212045B0C05058B0C0441B2159592DB800452C2020456944B001602020457D691844B001602DB800462CB800452A2DB800472C4B20B003265358B0801BB040598A8A20B0032653582321B0C08A8A1B8A235920B0032653582321B801008A8A1B8A235920B0032653582321B801408A8A1B8A235920B80003265358B0032545B8018050582321B8018023211BB003254523212321591B2159442DB800482C4B535845441B2121592DB800492C4BB800095058B101018E59B801FF85B800441DB9000900035F5E2DB8004A2C2020456944B001602DB8004B2CB8004A2A212DB8004C2C2046B003254652582359208A208A49648A204620686164B004254620686164525823658A592F20B00053586920B000545821B040591B6920B000545821B0406559593A2DB8004D2C2046B00425465258238A592046206A6164B0042546206A61645258238A592FFD2DB8004E2C4B20B0032650585158
+
B080441BB04044591B21212045B0C05058B0C0441B2159592DB8004F2C2020456944B001602020457D691844B001602DB800502CB8004F2A2DB800512C4B20B003265358B0801BB040598A8A20B0032653582321B0C08A8A1B8A235920B0032653582321B801008A8A1B8A235920B0032653582321B801408A8A1B8A235920B80003265358B0032545B8018050582321B8018023211BB003254523212321591B2159442DB800522C4B535845441B2121592DB800532C4BB800095058B101018E59B801FF85B800441DB9000900035F5E2DB800542C2020456944B001602DB800552CB800542A212DB800562C2046B003254652582359208A208A49648A204620686164B004254620686164525823658A592F20B00053586920B000545821B040591B6920B000545821B0406559593A2DB800572C2046B00425465258238A592046206A6164B0042546206A61645258238A592FFD2DB800582C4B20B0032650585158B080441BB04044591B21212045B0C05058B0C0441B2159592DB800592C2020456944B001602020457D691844B001602DB8005A2CB800592A2DB8005B2C4B20B003265358B0401BB000598A8A20B0032653582321B0808A8A1B8A235920B0032653582321B800C08A8A1B8A235920B0032653582321B801008A8A1B8A235920B0032653582321B801408A8A1B8A235920B80003265358B0032545B8018050582321B8018023211BB003254523212321591B2159442DB8005C2C4B535845441B2121592D00000000020042000004D005BD00030007003FB800532BB800082FB800092FB8000810B80000D0B800002FB8000910B80003DCB80004DCB8000010B80007DC00BA0007000000562BBA0002000500562B3031331121112711211142048EB8FCE205BDFA43B8044DFBB3000000030052FFDC04470449000F003B003C00DD40382A30010A100B1B0C1C2733481069096A10073908120C09031B320724091D100C1D3B2B022E293BB73B023B322A2512100705081C2722171CB8018A4023171D1F07271D2E0B021D350B3C073C3C1C1407292AA8241A3E1B291C4A0F2738193D3EBC0197002100B9019600182B2B4EF44DEDF4ED4E10F64DE4FDC412392F003F3FED3FED3FEDED1239111217395D1112392EED2EED01111239111739313043794028363715220001192501360F2100181E1B21001620142101212200370221001A1D1721011521172101002B2B2B01103C2B2B2B2B818181005D015D2416333237363D010E010F0106070615013637363534262322070607233E01333217161511141633323637150E0123222726270E012322263534363713010E724E5F59962168326D62315301B43E150C837A8D3B210AA805F7A3BD767517250C1E112A2C265D2A160937CE7C95BDBA978ACF5A2C49A691151C060E0D1C2F67016C
+
082C182D5C534C2A53C69B484898FD971C220303850C06422340486AB58895A41301E4000002003BFFE103D0044E001A001B00A7402FA719019818A808AA18034A08119B14030314061D1A070D1D140B1B071B1B1710271201032702111A1D0A2717191C1DB80107B321727D182B2B4EF44DED4E10F63C4DED3939ED12392F003F3FED3FED12392F10ED313043794034001908250C150A26000E1310260112110F1007190A26000500032101010204030B160D26000F120D2600091806260104010621012B2B2B2B01103C103C2B2B103C103C2B2B2B81005D015D001617232E012322070615141633323637330E01232202351000330702D6E317AF10727EAC4A308892708319AF1EF0BBD2FA0112D41C044EB0D76383A86DA0A1DC8977D5C50133E6011A013A0500030048FFDA041A0449001C00240025010C40799708991AA71F03050E020F0514150E120F1514400C401408291A014B0BB603C701C603C71BD808D909D61FD823E817E8230BC711C712025C080521240F9A161D243906070716211D1C070A1D160B2507971CA71CB71CD71C0425160F251C05190A0C07110E270F1D27051A27242E072719192627D421A65D182B2B4EF44DFDE44E10F64DEDD4FD391239391112393912392F5D003F3FED3FED12392F3CFD3C10ED1112393130437940460023040503050205010504061F26111012101310141004060C25221B24260020001D26011E1D09170726000B150E26010D0E231A2126011E0521260108180A26000D100A2600002B2B2B2B01103C2B2B103C2B2B2B2A2B2A8101715D00715D5D00161716171615211E013332373637330E01070607062322001110003301262726232206070102B4D638361210FCEF0590978D543014B1074F3152794152C8FEEA0118E2011F0B284AAD7CA805012304476B55516C4AA2A3C55D36473B912E501C100123010601020142FE26754682B38A01DC0000000002FFDAFE50013805BD00030011002FB800532BBA0000000100562BB8000110B80007D0B8000010B80009D000B8000E2FB800112FBA0003000000562B303101233533013E0135113311140706232226270138B4B4FEA27931B4263FB00D1D1F04EDD0F93404235C04B6FB37753A620203000000000100890000013D05BD0003002940150000030A0517171A0102290003190405AA216242182B2B4EF43C4DFD3C4E456544E6003F3F31301333112389B4B405BDFA4300000001008400000625044700260085403B0708070E060F1708170E170F2708270E270F4819560B670B0C23250A1A1D23190A02041725211D171D0D060700061B1C2503130A2817171A112914B80101B21A291DB80101400A00012E25292600192728B8010DB3216242182B2B4EF43C4DFDE410F4EDF4FD4E456544E6003F173C3F3F3C4DEDED11121739011112
+
3912393130005D13331536373633321716173E01333217161511231134262322061511231134272623220615112384B240345971804E2C243CA265D84E2ABB6B4D6A99B71A297066A7B4042F984F243D3F244656539C548EFD3702E86B508EA6FD9102BB6D324B9ECFFDC80000020084000003ED04490019001A005E4031B706C706020406140627147606740705140C021418101D05070006180B0A1A071A1A000C29091A1C012E18291900191B1CB80106B3216242182B2B4EF43C4DFDE44E10F64DED12392F003F3F3C3F3FED1139390112393130005D015D1333153E01333217161511231134272623220706070E011511230184AB4CAA68E4502CB71D307E40294A382D1BB401A7042F985E529F57A2FD5102A3623C640D1642357169FDCF04490000020076FE5504250449000E00220074402CA908A717022808201C110E061D15070F060E1D1C0B220E0227181A240A2E102E2129220F1923248721BD5D182B2B4EF43C4DFDE4E44E10F64DED003F3FED3F3FED1139123931304379401C161B00051A260426001B022601051602260101190E260003170626012B2B012B2B2B2B8181005D243635342726232207061514171633013315363736333212111007062322272627112302C6A72546BABB45252546BAFE2EAF36405B7BB6FEB7749A7952303BB479D3D2805CB1BB649A7C57A603B18E49283CFEE9FEFDFEA2965F351E49FDDD00000100890000029204470011004F40262703260D37034704040E0810020E0911090C270805070006110A081A13012E10291100191213B80145B321627E182B2B4EF43C4DFDE44E10E6003F3F4D3FC4FDC411123939011112393130005D1333153E0133321617152E0123220615112389AB15A46B05181D101B108892B4042FB9369B0203BE0302AF72FD980000010017FFEF0209055A00180052B50D2E0AC00E01B8013F40250416391703060E0A111A17171A0301062900150E150F031F030203FC1619191AFC21677D182B2B4EF44DFD5D39C42F3CFD3C104E456544E6002F3F3F3C4DFD3CED10FDE431301333113315231114171633323637150E012322263511233533A8B6ABAB2615310D1E141F43277E5A9191055AFED593FD4538130B01028E0908816702C593000000020080FFE303DE044900170018005E403AB814C81402091308141913191428067703D707070800050E0A00060D0A051D120B180718180B160D2E0A290C0B1A1A01291619191AD2216242182B2B4EF44DED4E10F63C4DFDE41112392F003F3FED3F3F3C391112393130005D015D0111141716333237363511331123370607062322272635112501381A3083BC4425B4AA0223346793E5532D01AF042FFD39523460A85A9D020EFBD19E3D2A5499528902D81A0000010000000000006B8BED625F0F3CF50011080000000000
+
5F4D8F0000000000C9C13CF7F865FC270B9108F9000000090001000000000000000100000629FE2900000C01F865FCED0B9100010000000000000000000000000000000C05120042047300520400003B0473004801C7FFDA01C7008906AA0084047300840473007602AA008902390017047300800000003400FE0180024A028402A60322037E03F00436048604E0000000010000000C00920009006B0007000200100010005D000007E80A1D00040001B800532BB800492BB8003F2BB800352BB8002B2B4118008001A6009001A600A001A600030069018B0079018B0089018B0099018B00040089018B0099018B00A9018B00B9018BB2040840BA0179001A014A400B041F5414191F180A0B1FD2B80106B49E1FD918E3BB0119000D00E10119B20D0009410A01A0019F0064001F01A50025017A00480028019AB3296C1F60410A01A9007001A9008001A90003008001A9000101A9B21E321FBE012C00250401001F0126001E0401B61FE7312D1FE531B80201B21FC227B80401B21FC11EB80201400F1FC01D9E1FBF1D671FBE1D671FAB27B80401B21FAA29B80401B61FA91D6C1F931EB8019AB21F921DB80101B21F911DB80101B21F751DB80201B61F6D29961F6431B8019AB21F4C96B802ABB21F391DB80156400B1F3638211F351DE41F2F27B80801400B1F2D1D4C1F2A31CD1F241DB802ABB21F201EB8012540111F1C1D931F3A1D4C1F1E1D45273A1D4527BB01AA019B002A019BB2254A1FBA019B0025017AB349293896B8017BB348283125B8017A403648289629482725294C1F252946272729482756C80784075B07410732072B072807260721071B071408120810080E080C080A08080807B801ACB23F1F06BB01AB003F001F01ABB308060805B801AEB23F1F04BB01AD003F001F01ADB70804080208000814B8FFE0B40000010014B801ABB41000000100B801ABB606100000010006B801ADB300000100B801AD401F04000001000410000001001002000001000200000001000002010802004A00B0018DB806008516763F183F123E113946443E113946443E113946443E113946443E113946443E11394660443E11394660443E11394660442B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B18011DB0964B5358B0AA1D59B0324B5358B0FF1D592B2B2B2B2B2B2B2B182B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B2B74752B2B2B65422B2B4B5279B376706A66456523456023456560234560B08B766818B080622020B16A704565234520B003266062636820B003266165B070236544B06A234420B176664565234520B003266062636820B003266165B066236544B0762344B10066455458B166406544B27640764523614459B36242725D456523456023456560234560B08976
+
6818B080622020B172424565234520B003266062636820B003266165B042236544B072234420B1625D4565234520B003266062636820B003266165B05D236544B0622344B1005D455458B15D406544B262406245236144592B2B2B2B456953427374B8019A2045694B20B02853B049515A58B020615944B801A6204569447500
+
00>] def
+
/CharStrings 12 dict dup begin
+
/.notdef 0 def
+/a 1 def
+/c 2 def
+/e 3 def
+/j 4 def
+/l 5 def
+/m 6 def
+/n 7 def
+/p 8 def
+/r 9 def
+/t 10 def
+/u 11 def
+ end readonly def
+
currentdict dup/FontName get exch definefont pop end
+
%APLsfntEnd
+
42/FontType resourcestatus{pop pop true}{false}ifelse
+
{currentfile 0(%APLT1End\n)/SubFileDecode filter flushfile}if
+
/FontType 1 def
+
/FontMatrix [ 0.00048828125 0 0 0.00048828125 0 0 ] def
+
/FontBBox{-1947 -985 2961 2297}def
+
/UniqueID 4257378 def
+
currentdict currentfile eexec
+
54544758EC884CF30C3CD503CEDBFF3839C47C3C3333173232E3FDBFF439491DB843E1924E63AA7726BBB0485AB56D93D8C0906F647A47162891E73FFC2A9873C4B1EAC5EEBDFFC4D06084FBD84139DF4583C6E259D10699944D1068C9C45667DCCCFB9B7EA01B606435EDCBD273ABAC093D14085CCBAC149BD7382E842CFE0D7FE4FD2EF589A2471F6074A80A8B675C2F7A50D63AC1EF90D787BADD11633CB01CF6EE3B37AAF9078A69AC4740E9B6525D78BBD839551A1CB80DB8682FA5E87591BBD6EE8B946063A2A58D9CA3685AB305495DC5FB5747EB8A9A059C4976C0FE4EEAB1D56FF47F1E9664ED9F4A7DAB763AF92B2F6CF2FA7DEC24710E0B9096E30F772BA7FEA9BDBE496C42ED2CEB58F54E80BDF57CE7B4DB6CCFE7182F43BF93CCA0767AF95D62C5D2C3DC6AE1E6D139F51A2C63432117F1714C5566572EE9967A715420ABDCD1D7BD74F8450B89965FCC81C6ACA565C5F3CCF91D430D1F953E4F1A645300A98DD8C47CD64555F08F422340A85404EAE0D3229C4F9336B9470CACBD6BBF3395104750A915CC6EAAC197668267B8C62D2764C8CD69FD937CA3C924D997A0EDE7964BEB9EA2F92EF70C5E5DA0AA5567765E71F2B911B3C5586B741EEB93F3C73016EC16BFF283758900903D203992EFC8BAFAF13579C602F38C91B64DFC330C1264D9E86DB21FFDE360EA73793134E310C3576495659FA930C228F2795196FF3E6FF3F588F9E3B1B3849A2BC2982CBBE7E36632530D7D022F3B1D5F5BB72C556137326233141B7D42148ED23C383940CF5B95F9DB518C2F09A3A91A6089E9E846B2315D2E14A8994858EC00227E0085029FB2F4222AD882A60F98F69E3C935EB85C4879ECE3C8A9AE1EDBB1F1C6B45C942A12C00B866F2C39887E9B310A7532FD6A2CCC09D5B4D1D7D10AF69E05DD153B31EE80385B0FD377AACBB8E33D8760BBD2B870F6D00990493915BF4680AC05EA8A583F98083CE2D3C43E05DC1B86C7B03ED020E487D92FFE3C789FF74701E47823BA8394C661AD1528EDACA92AC76C1417DCB18037CF4EEB59CD92459457F3E8E66D17D20899C9769A694816A2230C0CF3D2288CCCF67C7A26A3804642F1AD3D26A3311C193E84FB2011EF7E5355341D6670D5298928B5B3F74941FAF1A2FDC2D6E06C21E11FB2614E785B9A33043E2095A84401671013679F967E7BB05112EA2A72A1575DD7B4C6E29B3E73C93623C485699AF75B74724FF02837C20A02C1DCB7B7A9BF82AF873430EE974EBA0430A27C9FAE8B67D967B944EFBBA02F214C44AB3183BF44DEF8363FA6730653814C67006FF804044F3EB6A7B71F7D8E2A22E65D13E9496A20D1365F76213C80BBEA05A6C5CFFEAF3A8BFB5031E225C7BB8B46D136DE18B9FC4264BC98A7BF2ACB2E531F625454098EE57D95DF3D1F90853FDA846281EE56C9E617574E
+
D4E8FFB01E533528445ABE2CA123411E0561D0E8CD38759AAB6DBEA5A2AC49FD0FB337D649FECDB19B162FB9C1A51AEB11A7F26EB034F4868DB886EF5A82999B04F283B928EAA6B0CB0364B8F12805A9500C0A469ED7ED4B1AD987A92F28D164E7B953EB095EA5BCA7039FC94D554DC590AEC86C80A441DF16263FEB87FD55D5AE9188EC821D0D9B2E0F8399B2206EA4165DAE9F4EB645D72BCD31D7A6D51F4056FBC17FEB1B97AC1724206166877868BC4A59A2EA230DFA1ABD744E928ED8DA31D242E2712C429655D237F9C06BC2227D3B5D427FBC3B29DAF3B9C8133B2495E5B9BF8281B043CC4A5878183CC899A33083D05910B9E03D4871D078C52097F73CEEA93DE634EFB7D4B78E2E4A65BD211BC552D29A9A1860ED625A62216885BE5514A33E54FA5FF81803EAC4ABF756424C17D441B64CF9F83098852FEECC4F9542E07B28A71600C52054C19771A54A7AE7CE5BDDA7A34BF56EF4623E55847DE1288ABC0084DFE4C278176B2A9FBEBB7B052D0E04C7099178CCF61A094A60FD20DE8517CFE4C2B2D78D33A9842210CDAF68EDD4C780BA55F24BB983CD158AF89DD4383FA16053405FB487ADD40FB13691723D6DD2EBD61E20B5130051A78D50CC2F750D321F95448A5944C2E8BD331811A4E6BBFBF1C4A823B42F0486CC1D0DAF9C1F0565C64B9749824E46B88A2EAB8B8B16A8416D81F7D3ACCFDDC38FE1158AC6C6A4CF3128857C0651ED529971E891BBEA10901EEE74C715B30A0C2FC85C89BD1D7F5305E6207333560B7675CBA8B0EFED77B9F5D851FC335048848F693A31E6FFD0082AC39B90F2F227E2C89D1105B48F58E67A879A0C0B16E9CAE0DB6BAA18A903FB498F066526429514E7E2A8A14F31C137C25A3A2D94284ED6A89569CE31E67D86BF1860C147BCE0714345083B29825EC5CFE24CDFD79FF733EEE723F8348D384ED01E3514187F2B829302CB2D934CB684A016C12370508BBED7A108EF51784E591CE856E4BC933BD39A6C35EFAF042C65A6449530E2E34B5AACF8ACF46560BF4DFF573F424FA62741071A3E1D52D2D5953B7EE90957F2D8AACAC841FE9A9F9B446955AFFDE3F65592D46C9231755D1D63A61E74428248F5F256B4BC357C3D9C5D80381F893EF71A053653C129528024FAD880DC482CA4F7B600B07F1AB044937C08495E23C6B0729AFC6DA1E41F867F40FD7C414AB1D9AE697DB3F5830CF92AE6232A6AAA3766B9E3FFFFEE78CFD502E8EF7945C8B6CBAF1DE71B26F403EE3AA46E47DF063DB53167915149849681E47EAE3B22229EC633D86C923872CBD1108C549F30FF882045849F4ABAC21D79FB0E910510612F51F09F97D8DBF6EB5FEECEE3E2AC8E0DA433F128A1AEAF8F8FC9F0E96BF0A33ACDEA46E8C3C2C75D9962400E48076519ED632918B7721BC26501B939E58A3D5C9E9AE15ACD0B07
+
70E4CBD1C48227D6856F8ED641A96656501BA6273D4ACF835DF027F81B0D15B0DFCC82C1EC1B035328810E52ADC7C8CBA1A051E9CC8719C97913B04FF8759C1AB2C3DD046E7EB079165EBF6E07201D39ED2A75B70226189D6E369E8C336CD6A29C282F2FE09979DB6D0E26F0D010BEC632E7ADC1A8A751AF2941B64F2B7D8886D612AFB0547B795A66A340611A472AAB326486FC3E8B9FCA0B68E2893E2B7DF45A070E7ECC34F267CE47DD55A557719FF483E5E5EC4A0193D49C6783F318F6ABCEAEC3F3C8C96A7D2E76AF8E376992
+
0000000000000000000000000000000000000000000000000000000000000000
+
0000000000000000000000000000000000000000000000000000000000000000
+
0000000000000000000000000000000000000000000000000000000000000000
+
0000000000000000000000000000000000000000000000000000000000000000
+
0000000000000000000000000000000000000000000000000000000000000000
+
0000000000000000000000000000000000000000000000000000000000000000
+
0000000000000000000000000000000000000000000000000000000000000000
+
0000000000000000000000000000000000000000000000000000000000000000
+
cleartomark end
+
%APLT1End
+
%RBIEndFontSubset
+/Helvetica cguidfix
+/F2.1/Helvetica renmfont
 [ /CIEBasedABC 4 dict dup begin 
 /WhitePoint [ 0.9505 1.0000 1.0891 ] def 
 /DecodeABC [ { 1.8008  exp } bind { 1.8008  exp } bind { 1.8008  exp } bind ] def 
@@ -726,164 +798,161 @@
 /Cs1 SC
 1 1 1 sc
 q
-0 0 267 271 rc
--97.5 344.5 m
-461.5 344.5 l
-461.5 -438.5 l
--97.5 -438.5 l
+0 0 421.5 435 rc
+-138.50052 522.50793 m
+699.99951 522.50793 l
+699.99951 -651.99207 l
+-138.50052 -651.99207 l
 h
--97.5 344.5 m
+-138.50052 522.50793 m
 f
-11 260 m
-47 260 l
-47 11 l
-11 11 l
+16.5 396 m
+78 396 l
+78 22.5 l
+16.5 22.5 l
 h
-11 260 m
+16.5 396 m
 f
 1 J
 1 j
 0 0 0 sc
-1 0 0 -1 -97 344 cm
-108 84 m
-144 84 l
+1.5 0 0 -1.5 -138 522 cm
+103 83.999992 m
+144 83.999992 l
 144 333 l
-108 333 l
+103 333 l
 h
-108 84 m
+103 83.999992 m
+S
+0 i
+1.5 0 0 -1.5 47.25 209.25 cm
+/F1.1[ 14 0 0 -14 0 0]sf
+-13.230957 -3 m
+(!"#$)[ 3.889648 7.786133 7.786133 0.000000 ] xS
+-4.6689453 14 m
+(%)s
+0.60000002 i
+1 1 1 sc
+CM
+183 312 m
+244.5 312 l
+244.5 124.5 l
+183 124.5 l
+h
+183 312 m
+f
+0 0 0 sc
+1.5 0 0 -1.5 -138 522 cm
+214 140 m
+255 140 l
+255 265 l
+214 265 l
+h
+214 140 m
 S
 /Cs2 SC
 0 sc
 0 i
-1 0 0 -1 29 135.5 cm
-/F1.1[ 12 0 0 -12 0 0]sf
--11.34082 -3 m
-(!"#$)[ 3.333984 6.673828 6.673828 0.000000 ] xS
--4.0019531 11 m
-(%)s
-0.60000002 i
-/Cs1 SC
-1 1 1 sc
-CM
-112 201 m
-148 201 l
-148 76 l
-112 76 l
-h
-112 201 m
-f
-0 0 0 sc
-1 0 0 -1 -97 344 cm
-209 143 m
-245 143 l
-245 268 l
-209 268 l
-h
-209 143 m
-S
-/Cs2 SC
-0 sc
-0 i
-1 0 0 -1 130 138.5 cm
--11.34082 -3 m
-(!"#$)[ 3.333984 6.673828 6.673828 0.000000 ] xS
--4.0019531 11 m
+1.5 0 0 -1.5 213.75 218.25 cm
+-13.230957 -3 m
+(!"#$)[ 3.889648 7.786133 7.786133 0.000000 ] xS
+-4.6689453 14 m
 (&)s
 0.60000002 i
 /Cs1 SC
 1 1 1 sc
 CM
-220 197 m
-256 197 l
-256 43 l
-220 43 l
+349.5 291 m
+405 291 l
+405 60 l
+349.5 60 l
 h
-220 197 m
+349.5 291 m
 f
 0 0 0 sc
-1 0 0 -1 -97 344 cm
-317 147 m
-353 147 l
-353 301 l
-317 301 l
+1.5 0 0 -1.5 -138 522 cm
+325 154 m
+362 154 l
+362 308 l
+325 308 l
 h
-317 147 m
+325 154 m
 S
 /Cs2 SC
 0 sc
 0 i
-1 0 0 -1 238 120 cm
--11.34082 -3 m
-(!"#$)[ 3.333984 6.673828 6.673828 0.000000 ] xS
--4.3330078 11 m
+1.5 0 0 -1.5 377.25 175.5 cm
+-13.230957 -3 m
+(!"#$)[ 3.889648 7.786133 7.786133 0.000000 ] xS
+-5.0551758 14 m
 (')s
 0.60000002 i
 /Cs1 SC
 0 0 0 sc
-1 0 0 -1 -97 344 cm
+1.5 0 0 -1.5 -138 522 cm
 144 213 m
-156.66541 172.6707 171.16776 103.6655 182 92 c
-190.75253 82.574188 197.1132 110.57954 203.98026 130.64772 c
+156.66541 172.67068 170.3345 104.16544 182 91.999992 c
+191.40759 82.189224 199.51666 109.01452 207.89716 128.15717 c
 S
 CM
-111.28468 202.76021 m
-110.95242 214.9614 l
-103.01166 211.73442 l
+181.6945 314.53339 m
+179.55629 332.71667 l
+168.12738 326.82721 l
 h
-111.28468 202.76021 m
+181.6945 314.53339 m
 f
 0 J
 0 j
-1 0 0 -1 -97 344 cm
-208.28468 141.23979 m
-207.95242 129.0386 l
-200.01166 132.26558 l
+1.5 0 0 -1.5 -138 522 cm
+213.12967 138.31107 m
+211.70419 126.18887 l
+204.08493 130.11519 l
 h
-208.28468 141.23979 m
+213.12967 138.31107 m
 S
 1 J
 1 j
-245 268 m
-257.99869 222.33791 272.00119 151.16466 284 131 c
-292.47885 116.75084 299.96075 127.96632 307.50183 137.65463 c
+255 265 m
+264.66571 220.3378 272.33453 149.49814 284 131 c
+292.89722 116.89153 304.12341 133.22391 315.01324 145.17097 c
 S
 CM
-218.64566 198.33257 m
-213.50497 209.40292 l
-207.49341 203.29306 l
+347.36475 292.8877 m
+338.77927 309.05844 l
+330.26343 299.42587 l
 h
-218.64566 198.33257 m
+347.36475 292.8877 m
 f
 0 J
 0 j
-1 0 0 -1 -97 344 cm
-315.64566 145.66743 m
-310.50497 134.59708 l
-304.49341 140.70694 l
+1.5 0 0 -1.5 -138 522 cm
+323.57651 152.74153 m
+317.85284 141.96103 l
+312.17563 148.38275 l
 h
-315.64566 145.66743 m
+323.57651 152.74153 m
 S
 1 J
 1 j
-317 301 m
-287.3363 303.66641 256.83044 324.41513 228 309 c
-202.02444 295.11133 177.39485 251.85883 152.29529 218.93036 c
+325 308 m
+292.66989 308.33331 258.16364 324.83176 228 309 c
+200.91458 294.78387 177.31604 254.49185 152.51088 223.24969 c
 S
 CM
-48.182663 134.01295 m
-51.942123 122.40063 l
-58.650635 127.73593 l
+79.820663 200.30736 m
+85.826248 183.01178 l
+95.717834 191.22533 l
 h
-48.182663 134.01295 m
+79.820663 200.30736 m
 f
 0 J
 0 j
-1 0 0 -1 -97 344 cm
-145.18266 209.98705 m
-148.94212 221.59937 l
-155.65063 216.26407 l
+1.5 0 0 -1.5 -138 522 cm
+145.21378 214.46176 m
+149.2175 225.99214 l
+155.81189 220.51645 l
 h
-145.18266 209.98705 m
+145.21378 214.46176 m
 S
 1 J
 1 j
@@ -891,25 +960,68 @@
 1
 4
 ] 0 d
-317 301 m
-257.11655 273.55341 l
+325 308 m
+266.35699 271.97641 l
 S
 CM
-149.72722 75.208344 m
-158.33087 66.550598 l
-161.90219 74.34259 l
+246.92844 123.00824 m
+258.17059 108.55774 l
+264.90027 119.51299 l
 h
-149.72722 75.208344 m
+246.92844 123.00824 m
 f
 0 J
 0 j
 [] 0 d
-1 0 0 -1 -97 344 cm
-246.72722 268.79166 m
-255.33087 277.4494 l
-258.90219 269.65741 l
+1.5 0 0 -1.5 -138 522 cm
+256.61896 265.99451 m
+264.11374 275.62817 l
+268.60019 268.32468 l
 h
-246.72722 268.79166 m
+256.61896 265.99451 m
+S
+/Cs2 SC
+0 sc
+0 i
+1.5 0 0 -1.5 138.75 400.5 cm
+/F2.1[ 15 0 0 -15 0 0]sf
+-11.253662 6 m
+(!"##)[ 7.500000 8.342285 3.332520 0.000000 ] xS
+1.5 0 0 -1.5 300.75 352.5 cm
+-12.084961 6 m
+($%&)[ 3.332520 12.495120 0.000000 ] xS
+1.5 0 0 -1.5 234 34.5 cm
+-19.592285 6 m
+('\(\)*'+)[ 4.995117 8.342285 4.167480 8.342285 4.995117 0.000000 ] xS
+1 J
+1 j
+[
+1
+4
+] 0 d
+0.60000002 i
+/Cs1 SC
+0 0 0 sc
+1.5 0 0 -1.5 -138 522 cm
+214 265 m
+154.69943 220.94815 l
+S
+CM
+80.287811 200.80048 m
+90.215607 185.4173 l
+97.882645 195.73828 l
+h
+80.287811 200.80048 m
+f
+0 J
+0 j
+[] 0 d
+1.5 0 0 -1.5 -138 522 cm
+145.52521 214.13301 m
+152.14374 224.38846 l
+157.2551 217.50781 l
+h
+145.52521 214.13301 m
 S
 ep
 end
--- a/Paper/figure/continuation.graffle	Fri Nov 18 18:11:00 2011 +0900
+++ b/Paper/figure/continuation.graffle	Sat Nov 19 18:03:15 2011 +0900
@@ -6,7 +6,7 @@
 	<integer>0</integer>
 	<key>ApplicationVersion</key>
 	<array>
-		<string>com.omnigroup.OmniGrafflePro</string>
+		<string>com.omnigroup.OmniGraffle</string>
 		<string>138.33.0.157554</string>
 	</array>
 	<key>AutoAdjust</key>
@@ -44,7 +44,7 @@
 	<key>Creator</key>
 	<string>Nobuyasu Oshiro</string>
 	<key>DisplayScale</key>
-	<string>1 0/72 in = 1 0/72 in</string>
+	<string>1 0/72 in = 1.0000 in</string>
 	<key>GraphDocumentVersion</key>
 	<integer>8</integer>
 	<key>GraphicsList</key>
@@ -57,6 +57,226 @@
 			<key>Head</key>
 			<dict>
 				<key>ID</key>
+				<integer>12</integer>
+			</dict>
+			<key>ID</key>
+			<integer>27</integer>
+			<key>Points</key>
+			<array>
+				<string>{214, 265}</string>
+				<string>{144, 213}</string>
+			</array>
+			<key>Style</key>
+			<dict>
+				<key>stroke</key>
+				<dict>
+					<key>HeadArrow</key>
+					<string>FilledArrow</string>
+					<key>HeadScale</key>
+					<real>1.4285709857940674</real>
+					<key>LineType</key>
+					<integer>1</integer>
+					<key>Pattern</key>
+					<integer>2</integer>
+					<key>TailArrow</key>
+					<string>0</string>
+					<key>TailScale</key>
+					<real>0.5</real>
+				</dict>
+			</dict>
+			<key>Tail</key>
+			<dict>
+				<key>ID</key>
+				<integer>7</integer>
+				<key>Info</key>
+				<integer>4</integer>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{214, 311}, {68, 28}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>26</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>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</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\fs30 \cf0 return}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{272, 99}, {41, 28}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>25</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>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</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\fs30 \cf0 jmp}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{164, 67}, {41, 28}}</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>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</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\fs30 \cf0 call}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+		</dict>
+		<dict>
+			<key>AllowLabelDrop</key>
+			<false/>
+			<key>Class</key>
+			<string>LineGraphic</string>
+			<key>Head</key>
+			<dict>
+				<key>ID</key>
 				<integer>7</integer>
 				<key>Info</key>
 				<integer>1</integer>
@@ -65,8 +285,8 @@
 			<integer>21</integer>
 			<key>Points</key>
 			<array>
-				<string>{317, 301}</string>
-				<string>{245, 268}</string>
+				<string>{325, 308}</string>
+				<string>{255, 265}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -102,15 +322,15 @@
 			<key>Head</key>
 			<dict>
 				<key>ID</key>
-				<integer>4</integer>
+				<integer>12</integer>
 			</dict>
 			<key>ID</key>
 			<integer>23</integer>
 			<key>Points</key>
 			<array>
-				<string>{317, 301}</string>
+				<string>{325, 308}</string>
 				<string>{228, 309}</string>
-				<string>{144, 208.5}</string>
+				<string>{144, 213}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -152,9 +372,9 @@
 			<integer>14</integer>
 			<key>Points</key>
 			<array>
-				<string>{245, 268}</string>
+				<string>{255, 265}</string>
 				<string>{284, 131}</string>
-				<string>{317, 147}</string>
+				<string>{325, 154}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -198,7 +418,7 @@
 			<array>
 				<string>{144, 213}</string>
 				<string>{182, 92}</string>
-				<string>{209, 143}</string>
+				<string>{214, 140}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -219,7 +439,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{317, 147}, {36, 154}}</string>
+			<string>{{325, 154}, {37, 154}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -261,7 +481,7 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
 
-\f0\fs24 \cf0 func\
+\f0\fs28 \cf0 func\
 C}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
@@ -269,7 +489,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{209, 143}, {36, 125}}</string>
+			<string>{{214, 140}, {41, 125}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -311,7 +531,7 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
 
-\f0\fs24 \cf0 func\
+\f0\fs28 \cf0 func\
 B}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
@@ -319,7 +539,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{108, 84}, {36, 249}}</string>
+			<string>{{103, 84}, {41, 249}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -358,10 +578,10 @@
 				<key>Text</key>
 				<string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230
 {\fonttbl\f0\fswiss\fcharset0 Helvetica;}
-{\colortbl;\red255\green255\blue255;}
+{\colortbl;\red255\green255\blue255;\red0\green0\blue0;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
 
-\f0\fs24 \cf0 func\
+\f0\fs28 \cf2 func\
 A}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
@@ -415,7 +635,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2011-11-13 20:18:52 +0000</string>
+	<string>2011-11-15 23:58:55 +0000</string>
 	<key>Modifier</key>
 	<string>Nobuyasu Oshiro</string>
 	<key>NotesVisible</key>
@@ -496,7 +716,7 @@
 			</dict>
 		</array>
 		<key>Frame</key>
-		<string>{{108, 70}, {693, 938}}</string>
+		<string>{{542, 71}, {693, 938}}</string>
 		<key>ListView</key>
 		<true/>
 		<key>OutlineWidth</key>
--- a/Paper/nobu-prosym.aux	Fri Nov 18 18:11:00 2011 +0900
+++ b/Paper/nobu-prosym.aux	Sat Nov 19 18:03:15 2011 +0900
@@ -2,11 +2,11 @@
 \newlabel{fig:cs}{{1}{1}}
 \@writefile{lol}{\contentsline {lstlisting}{source/factorial.cbc}{2}}
 \newlabel{fig:ir}{{3}{2}}
-\bibcite{1}{1}
-\bibcite{2}{2}
 \newlabel{fig:continue}{{4}{3}}
 \newlabel{fig:cs_stack}{{5}{3}}
 \newlabel{fig:fastcall}{{6}{3}}
+\bibcite{1}{1}
+\bibcite{2}{2}
 \bibcite{3}{3}
 \bibcite{4}{4}
 \bibcite{5}{5}
Binary file Paper/nobu-prosym.dvi has changed
--- a/Paper/nobu-prosym.log	Fri Nov 18 18:11:00 2011 +0900
+++ b/Paper/nobu-prosym.log	Sat Nov 19 18:03:15 2011 +0900
@@ -1,4 +1,4 @@
-This is e-pTeX, Version 3.1415926-p3.2-110415-2.3 (utf8.euc) (TeX Live 2011) (format=platex 2011.11.10)  18 NOV 2011 17:57
+This is e-pTeX, Version 3.1415926-p3.2-110415-2.3 (utf8.euc) (TeX Live 2011) (format=platex 2011.11.10)  19 NOV 2011 18:02
 entering extended mode
  restricted \write18 enabled.
  %&-line parsing enabled.
@@ -197,22 +197,26 @@
 
 LaTeX Font Info:    External font `cmex10' loaded for size
 (Font)              <7> on input line 97.
+LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <9> not available
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 133.
+LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <9> not available
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 133.
 File: figure/codesegment.eps Graphic file (type eps)
 <figure/codesegment.eps>
-Overfull \hbox (2.42252pt too wide) in paragraph at lines 126--127
+Overfull \hbox (2.42252pt too wide) in paragraph at lines 145--146
  [] 
  []
 
 LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <7> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 128.
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 147.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <7> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 128.
-LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <9> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 133.
-LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <9> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 133.
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 147.
+[1
+
 
-LaTeX Warning: Reference `fig:factorial' on page 1 undefined on input line 146.
+]
+
+LaTeX Warning: Reference `fig:factorial' on page 2 undefined on input line 158.
 
 
 (/usr/local/texlive/2011/texmf-dist/tex/latex/listings/lstlang1.sty
@@ -236,14 +240,10 @@
 )
 LaTeX Font Info:    Font shape `OML/cmr/m/n' in size <9> not available
 (Font)              Font shape `OML/cmm/m/it' tried instead on input line 8.
-) [1
-
-
-]
+)
 File: figure/ir.eps Graphic file (type eps)
-
-<figure/ir.eps>
-Overfull \hbox (19.2858pt too wide) in paragraph at lines 172--173
+ <figure/ir.eps>
+Overfull \hbox (19.2858pt too wide) in paragraph at lines 185--186
  [] 
  []
 
@@ -253,21 +253,21 @@
  <figure/cs_stack.eps>
 File: figure/fastcall.eps Graphic file (type eps)
  <figure/fastcall.eps>
-Overfull \hbox (12.43753pt too wide) in paragraph at lines 287--288
+Overfull \hbox (12.43753pt too wide) in paragraph at lines 298--299
  [] 
  []
 
-
-Overfull \hbox (13.24168pt too wide) in paragraph at lines 323--329
+[3]
+Overfull \hbox (13.24168pt too wide) in paragraph at lines 334--340
  [][] 
  []
 
 
-Overfull \hbox (13.24168pt too wide) in paragraph at lines 337--343
+Overfull \hbox (13.24168pt too wide) in paragraph at lines 348--354
  [][] 
  []
 
-[3] [4
+[4
 
 ] (./nobu-prosym.aux)
 
@@ -278,12 +278,12 @@
 
  ) 
 Here is how much of TeX's memory you used:
- 2581 strings out of 494163
- 34844 string characters out of 3160585
- 120885 words of memory out of 3000000
- 5966 multiletter control sequences out of 15000+200000
+ 2582 strings out of 494163
+ 34858 string characters out of 3160585
+ 118641 words of memory out of 3000000
+ 5967 multiletter control sequences out of 15000+200000
  17620 words of font info for 68 fonts, out of 3000000 for 9000
  745 hyphenation exceptions out of 8191
  30i,10n,52p,207b,1326s stack positions out of 5000i,500n,10000p,200000b,50000s
 
-Output written on nobu-prosym.dvi (4 pages, 21488 bytes).
+Output written on nobu-prosym.dvi (4 pages, 22144 bytes).
Binary file Paper/nobu-prosym.pdf has changed
--- a/Paper/nobu-prosym.tex	Fri Nov 18 18:11:00 2011 +0900
+++ b/Paper/nobu-prosym.tex	Sat Nov 19 18:03:15 2011 +0900
@@ -1,1 +1,1 @@
-\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}


% 巻数,号数などの設定
%\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 への実装を行った.
本論文では 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 と同じであるが,継続によりループ制御や関数コールが取り除かれる.

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 への実装を述べる.

%}{

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

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


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

継続の実態は jmp による関数の移動となる.


\subsection{コードセグメント(code segment)}
CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
関数と同じように引数を持たせて継続させることもできる.
しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.
図\ref{fig:factorial}は CbC で書いたプログラムの例である.
与えられた数 x の階上を計算して出力するプログラムとなっている.

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


%コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
%コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.


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


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

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


\subsubsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.
CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


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


\subsubsection{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” のパース}



\subsection{Tail Call Elimination}
CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる.
Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
call ではなく jmp を用いることができるという最適化である.
図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.


\begin{figure}[htpb]
  \begin{center}
\scalebox{0.50}{\includegraphics{figure/continuation.eps}}
  \end{center}
  \caption{Tail Call Elimination}
  \label{fig:continue}
\end{figure}
funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す.


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

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


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

\begin{itemize}
  \item 呼び出す関数がコードセグメントの場合返す値の型チェックを行わない.
  \item コードセグメントへの継続を Generic Tree で表す際に,return の情報も直後に持たせる.
  \item スタックサイズは決め打ちで行う.
  \item[]
\end{itemize}

スタックサイズを決め打ちで行うことで,ベースポインタを変えずにスタックを扱うことができる.
これも 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}


%expand\call 関数では Tail Call Elimination が可能かどうかを判断するために,try\_tail\_call フラグが用意されている.
%Tail call Elimination が行えないと判断されると try\_tail\_call フラグに0がセットされる.


expand\_call 関数の中で try\_tail\_call フラグ



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


\subsubsection{fastcall}
コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする.
C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う.
だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない.
そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う.
図\ref{fig:fastcall}はコードセグメントに 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}


if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ,
fastcall 属性を付けると warning を出すからである.


\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.829 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 3.890 & 0.382 & 2.288 \\ \hline
 x86\_64/OS X      & 4.078 & 0.450 &        \\ \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.252 & 2.906 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 1.827 & 0.934 & 2.288 \\ \hline
 x86\_64/OS X      & 1.101 & 2.896 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較(単位: 秒)(速度最適化)}
  \label{tab:speed-mc-vs-gcc-opt}
\end{table}



\begin{thebibliography}{7}

\bibitem{1}{河野真治}:
“継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002


\bibitem{2}{河野真治}:
“継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000

\bibitem{3}{与儀健人,河野真治}:
“Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学 情報工学科 学位論文, 2008

\bibitem{4}{与儀健人,河野真治}:
“組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院 理工学研究科 学位論文(修士), 2010

\bibitem{5}{下地篤樹,河野真治}:
“線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院 理工学研究科 情報工学専攻 学位論文(修士), 2008

\bibitem{6}{楊挺,河野真治}:
“Continuation based C の実装”. 琉球大学大学院 理工学研究科 情報工学専攻 学位論文(修士), 2002

\bibitem{7}{GNU Compiler Collection (GCC) Internals}:
“http://gcc.gnu.org/onlinedocs/gccint/”


\end{thebibliography}

\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}


% 巻数,号数などの設定
%\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 への実装を行った.
本論文では 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 プログラムの例}
\end{figure}

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

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

\subsection{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}


\subsubsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.
CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


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


\subsubsection{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” のパース}


\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.35}{\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}
  \item caller 側と callee 側の戻値の型が一致している.
  \item 関数呼び出しがリターンの直前に行われている.
  \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
  \item 引数の並びのコピーに上書きがない.
\end{itemize}
CbC の実装では上記の条件を,以下の様にして解決させている.

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

スタックサイズを決め打ちで行うことで,ベースポインタを変えずにスタックを扱うことができる.
これも 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}


%expand\call 関数では Tail Call Elimination が可能かどうかを判断するために,try\_tail\_call フラグが用意されている.
%Tail call Elimination が行えないと判断されると try\_tail\_call フラグに0がセットされる.


expand\_call 関数の中で try\_tail\_call フラグ



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


\subsubsection{fastcall}
コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする.
C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う.
だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない.
そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う.
図\ref{fig:fastcall}はコードセグメントに 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}


if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ,
fastcall 属性を付けると warning を出すからである.


\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.829 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 3.890 & 0.382 & 2.288 \\ \hline
 x86\_64/OS X      & 4.078 & 0.450 &        \\ \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.252 & 2.906 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 1.827 & 0.934 & 2.288 \\ \hline
 x86\_64/OS X      & 1.101 & 2.896 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較(単位: 秒)(速度最適化)}
  \label{tab:speed-mc-vs-gcc-opt}
\end{table}



\begin{thebibliography}{7}

\bibitem{1}{河野真治}:
“継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002


\bibitem{2}{河野真治}:
“継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000

\bibitem{3}{与儀健人,河野真治}:
“Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学 情報工学科 学位論文, 2008

\bibitem{4}{与儀健人,河野真治}:
“組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院 理工学研究科 学位論文(修士), 2010

\bibitem{5}{下地篤樹,河野真治}:
“線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院 理工学研究科 情報工学専攻 学位論文(修士), 2008

\bibitem{6}{楊挺,河野真治}:
“Continuation based C の実装”. 琉球大学大学院 理工学研究科 情報工学専攻 学位論文(修士), 2002

\bibitem{7}{GNU Compiler Collection (GCC) Internals}:
“http://gcc.gnu.org/onlinedocs/gccint/”


\end{thebibliography}

\end{document}
\ No newline at end of file
--- a/Paper/nobu-prosym.tex~	Fri Nov 18 18:11:00 2011 +0900
+++ b/Paper/nobu-prosym.tex~	Sat Nov 19 18:03:15 2011 +0900
@@ -1,1 +1,1 @@
-\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}

% 巻数,号数などの設定
%\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 への実装を行った.
本論文では 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 と同じであるが,継続によりループ制御や関数コールが取り除かれる.

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 への実装を述べる.

%}{

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

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


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

継続の実態は jmp による関数の移動となる.


\subsection{コードセグメント(code segment)}
CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
関数と同じように引数を持たせて継続させることもできる.
しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.
図\ref{fig:factorial}は CbC で書いたプログラムの例である.
与えられた数 x の階上を計算して出力するプログラムとなっている.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.40}{\includegraphics{figure/factorial.eps}}
  \end{center}
  \caption{階上を計算する CbC プログラムの例}
  \label{fig:factorial}
\end{figure}


%コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
%コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.


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


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


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


\subsubsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.
CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


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


\subsubsection{Register Transfer Language (RTL)}
構文木 GIMPLE は解析が行われた後 RTL へと変換される.
RTL での表現は低レベルで,アセンブラとほぼ同じ表現を行うことができる.


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


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


\subsection{“__code” のパース}



\subsection{Tail Call Elimination}
CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる.
Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
call ではなく jmp を用いることができるという最適化である.
図\ref{continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.


\begin{figure}[htpb]
  \begin{center}
\scalebox{0.50}{\includegraphics{figure/continuation.eps}}
  \end{center}
  \caption{Tail Call Elimination}
  \label{fig:continue}
\end{figure}
funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す.


\subsubsection{expand\_call}
ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数によって判断される.
Tail call Elimination が行える場合 try\_tail_call
expand\_call 関数の中で try_tail_call というフラグ



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

\subsubsection{fastcall}
コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする.
C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う.
だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない.
そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う.
図\ref{fig:fastcall}はコードセグメントに fastcall 属性を付与しているソースである.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/fastcall.eps}}
  \end{center}
  \caption{fastcall属性付与}
  \label{fig:fastcall}
\end{figure}

if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ為である.


\begin{thebibliography}{10}

\bibitem{1}{河野真治}:
“継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002

\bibitem{2}{河野真治}:
“継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000

\bibitem{3}{与儀健人,河野真治}:
“Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学 情報工学科 学位論文, 2008

\bibitem{4}{与儀健人,河野真治}:
“組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院 理工学研究科 学位論文(修士), 2010

\bibitem{5}{下地篤樹,河野真治}:
“線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院 理工学研究科 情報工学専攻 学位論文(修士), 2008

\bibitem{6}{楊挺,河野真治}:
“Continuation based C の実装”. 琉球大学大学院 理工学研究科 情報工学専攻 学位論文(修士), 2002

\bibitem{7}{GNU Compiler Collection (GCC) Internals}:
“http://gcc.gnu.org/onlinedocs/gccint/”


\end{thebibliography}

\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}


% 巻数,号数などの設定
%\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 への実装を行った.
本論文では 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 と同じであるが,継続によりループ制御や関数コールが取り除かれる.

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 への実装を述べる.

%}{

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

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


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

継続の実態は jmp による関数の移動となる.


\subsection{コードセグメント(code segment)}
CbC におけるプログラムの基本単位としてコードセグメントという概念がある.
コードセグメントの記述の仕方は C の関数と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
関数と同じように引数を持たせて継続させることもできる.
しかし,関数とは違ってリターンを行わない為返り値を取得することはできない.
図\ref{fig:factorial}は CbC で書いたプログラムの例である.
与えられた数 x の階上を計算して出力するプログラムとなっている.

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


%コードセグメントは関数よりも小さな単位で記述される為,最適化がされやすくなる.
%コードセグメントの記述の仕方は C の関数と同じで,引数を持たせて継続を行うことができる.


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


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

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


\subsubsection{Generic Tree}
ソースコードより読み込んだ関数の情報を木構造で表したものが Generic Tree となる.
関数の返り値,引数,変数の型,条件式とプログラムの処理全てが木構造で表される.
CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.


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


\subsubsection{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” のパース}



\subsection{Tail Call Elimination}
CbC の継続の実装には GCC の最適化の1つである Tail Call Elimination (末尾除去) が使われる.
Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に,
call ではなく jmp を用いることができるという最適化である.
図\ref{fig:continue}は Tail Call Elimination が行われた際のプログラムの処理を表している.


\begin{figure}[htpb]
  \begin{center}
\scalebox{0.50}{\includegraphics{figure/continuation.eps}}
  \end{center}
  \caption{Tail Call Elimination}
  \label{fig:continue}
\end{figure}
funcB の処理の最後に呼ばれた funcC は,返り値を funcB ではなく funcA へと返す.


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

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


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

\begin{itemize}
  \item 呼び出す関数がコードセグメントの場合返す値の型チェックを行わない.
  \item コードセグメントへの継続を Generic Tree で表す際に,return の情報も直後に持たせる.
  \item スタックサイズは決め打ちで行う.
  \item[]
\end{itemize}

スタックサイズを決め打ちで行うことで,ベースポインタを変えずにスタックを扱うことができる.
これも 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}


%expand\call 関数では Tail Call Elimination が可能かどうかを判断するために,try\_tail\_call フラグが用意されている.
%Tail call Elimination が行えないと判断されると try\_tail\_call フラグに0がセットされる.


expand\_call 関数の中で try\_tail\_call フラグ



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


\subsubsection{fastcall}
コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする.
C において fastcall を用いる場合は関数にキーワード “\_\_attribute\_\_ ((fastcall))” をつけて行う.
だが,コードセグメントを全てこのキーワードをつけて宣言することは実用できではない.
そこで,コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う.
図\ref{fig:fastcall}はコードセグメントに 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}


if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行われ,
fastcall 属性を付けると warning を出すからである.


\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.829 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 3.890 & 0.382 & 2.288 \\ \hline
 x86\_64/OS X      & 4.078 & 0.450 &        \\ \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.252 & 2.906 & 2.890 \\ \hline
 x86\_64/OS X(-m32)& 1.827 & 0.934 & 2.288 \\ \hline
 x86\_64/OS X      & 1.101 & 2.896 &        \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のGCCとmicro-cの速度比較(単位: 秒)(速度最適化)}
  \label{tab:speed-mc-vs-gcc-opt}
\end{table}



\begin{thebibliography}{7}

\bibitem{1}{河野真治}:
“継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002


\bibitem{2}{河野真治}:
“継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000

\bibitem{3}{与儀健人,河野真治}:
“Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学 情報工学科 学位論文, 2008

\bibitem{4}{与儀健人,河野真治}:
“組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院 理工学研究科 学位論文(修士), 2010

\bibitem{5}{下地篤樹,河野真治}:
“線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院 理工学研究科 情報工学専攻 学位論文(修士), 2008

\bibitem{6}{楊挺,河野真治}:
“Continuation based C の実装”. 琉球大学大学院 理工学研究科 情報工学専攻 学位論文(修士), 2002

\bibitem{7}{GNU Compiler Collection (GCC) Internals}:
“http://gcc.gnu.org/onlinedocs/gccint/”


\end{thebibliography}

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