%!PS-Adobe-2.0 %%Creator: dvips 5.72 Copyright 1997 Radical Eye Software (www.radicaleye.com) %%Title: ri.dvi %%CreationDate: Tue Aug 26 22:57:53 1997 %%Pages: 10 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%DocumentFonts: Helvetica %%EndComments %DVIPSCommandLine: dvips -Z ri %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 1997.08.26:2255 %%BeginProcSet: texc.pro %! /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{ dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg} {adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{ adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{] }if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict /eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{dup length product length le{dup length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false} ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot} imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M}B /d{ -3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w} B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet %%BeginProcSet: special.pro %! TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{ /CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{ 10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{} N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto} }{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{ itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{ closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp {pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray} N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale true def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial {CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath }N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{ end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin} N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{ /SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 39158280 55380996 1000 600 600 (/home/anton/tex/rafts-internals/ri.dvi) @start %DVIPSBitmapFont: Fa cmti7 7 2 /Fa 2 117 df<1378EA07FC5BEA0078A35BA4485AA4485AEBC1FCEBC7FEEBCE0F390798 078013B013E013C0EA0F80A21300A2001EEB0F00A3141E5A150C143C15184813381478EC 3830EC3C6048EB1FC00060EB0F801E287BA723>104 D<1318133C5BA45BA4485A387FFF C0B5FC3801E000485AA4485AA448C7FCA4121EEB0180A2EB0300123C1306EA1C0CEA1E38 EA0FF0EA03C012247AA317>116 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmcsc10 10 4 /Fb 4 118 df66 D<91383FE003903801FFF8 903907E01E0790391F00078F013EEB01DF01F8EB007F484880485A0007814848805B001F 81A248C8FC825A127EA200FE92C7FCA892383FFFF8127E03001380007FED3F007EA26C7E A2120F7F6C7E12036C7E6C6C5C013E14DF6DEB018F903907E00F07903901FFFE03902600 3FF0C7FC2D2D7BAB35>103 D114 D117 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmmi9 9 1 /Fc 1 59 df<123C127E12FFA4127E123C08087A8715>58 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmr9 9 24 /Fd 24 125 df48 D<13075B5B137FEA07FFEAFFBFEAF83F1200B3B3A3EBFFC0007FEBFF80A21931 7AB026>IIII<000C14C038 0FC00F90B5128015005C5C14F014C0D80C18C7FC90C8FCA9EB1FC0EB7FF8EBE07C380F80 1E497E000E1480000CEB07C0000814E0C7FCEC03F0A315F8A31218127C12FEA315F05A00 78EB07E0126015C06C130F6C1480001CEB1F006C133E380380F83801FFE038007F801D32 7CB026>I57 D<3803FFC0000F13F848C67E383F803F6E7E6E7EEA1F00000E6D7EC7FCA4EB01FF133FEB FF873803F807EA0FE0EA1F80EA3F00127EA24815C0A4140F127C007E131B6C903833F180 391FC0E1FF2607FFC01300C6EB007C22207D9F26>97 D99 D<153FEC0FFFA2EC007F81B0EB07F0EB3FFEEBFC0F3901E001BF3907C000FF48487F90C7 7E5A123EA2127E127C12FCA8127C127EA2123E7E5D6C6C5B00075B3903E003BF3A00F81E 3F80D97FFC13FCEB0FE026347DB32B>II<151F90391FC07F8090397FF1E3C03901F07F833903C01E033A07800F018092C7FC 48486C7EA24880A56C5CA26C6C48C7FCA23803C01EEBF07C38067FF0380E1FC090C9FCA5 EA0F80EBFFFE6CEBFFC06C14F06C80000780391F0001FE003EEB003F4880168048140FA4 00781500007C5C6C143E6C5C6C6C5B3903F007E0C6B51280D91FFCC7FC22317EA026> 103 DII108 D<2703F01FE013FF00FF 90267FF80313C0903BF1E07C0F03E03C07F3803E1C01F02803F6003F307F01FC90381F60 0004E07F495CA2495CB3A2486C496C487EB53BC7FFFE3FFFF0A23C207E9F41>I<3903F0 1FC000FFEBFFF09038F1E0F83907F3007CD803F6137E01FC133E153F5BA25BB3A2486CEB 7F80B538C7FFFCA226207E9F2B>II<3903F03F8039FFF1FFF09038F3C0F83907F6003ED803FC7F49EB0F8049EB07C0A2ED 03E016F0A2150116F8A8ED03F0A216E0150716C0ED0F807F6DEB1F0001F6137C9038F381 F89038F1FFE0D9F07FC7FC91C8FCAC487EB512C0A2252F7E9F2B>I<3803E07C00FF13FF 9038E38F800007EB1FC0EA03E613ECEC0F809038F8070091C7FCA25BB3487EB512E0A21A 207F9F1E>114 D<1330A51370A313F0A2120112031207121FB512FEA23803F000B01403 A80001130613F80000130CEB7E1CEB3FF8EB07E0182E7FAD1E>116 DII124 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmss10 10 25 /Fe 25 122 df40 D<12F8127C7E7E6C7E7F12076C7E7F12017F6C7EA2137EA2133E133F7F1480A3EB 0FC0A4130714E0A5130314F0B214E01307A514C0130FA4EB1F80A314005B133E137EA25B A2485A5B12035B485A120F5B48C7FC123E5A5A14527CBD20>I<12FEA70707788617>46 D<12FEB3B3B3A4073A78B917>73 D<12FEB3B3B1B71280A5213A78B92D>76 DI97 D<12FCB3A2EB01FCEB0FFF013F13C090B57E00FD8039FFF01FF8EBC007496C7E496C 7E48130048147E157F81A21680151FA9ED3F00A35D157E6C14FE6C495A14039038C007F8 9038F03FF000FDB55A00FC5C6D5BD91FFEC7FC380007F8213B7AB92B>IIII<14FF010313C0130F5B5B148190387E00404913005BA2 1201ACB512FCA5D801F8C7FCB3AE1A3B7FBA19>I<903907E001F890383FFC1F90397FFE FFFC48B6FC5A9039F81FF8003907E007E048486C7EEB8001A248C77EA76C6C485AA2EBC0 036C6C485A3903F81FC048B5FC485C6D48C7FC6D5A381F07E090C9FCA46C7E90B512C015 FC6C14FF16804815C04815E03A3F80007FF048C7120F007E140300FE15F8481401A46C14 03007E15F0D87F80130FD83FE0EB3FE03A1FFC01FFC06CB612806C1500000114FC6C6C13 F0010790C7FC26387EA52A>I<12FCB3A2EB07F8EB1FFEEB7FFF90B5128000FD14C039FF F03FE0EBC00FEB8007010013F014035AA35AB3A71C3A79B92B>I<12FEA71200AD127EB3 B307397BB813>I<12FCB3B3B3A4063A7AB913>108 DIIII<14F0EAF807131F 133F137F13FF00F91300EAFBF8B45A13C05BA290C7FCA25AA25AB3A414267AA51C>114 DII<00FCEB03F0B3AA1407A2140F6C133F007F13FF90B5 FC14F36C13E36C1383D807F8C7FC1C2679A42B>I<00FEEC07E0007EEC0FC0A26C158015 1F7F001FEC3F007F120F157E6C7E5D7F12034A5AEA01F85D3800FC03A25DEB7E075D133E EB3F0F011F5BA292C7FCEB0F9FA2EB079EA2EB03DCA214FC6D5AA26D5AA213015C1303A2 5C13075C130F91C8FCEA201FEA383EEA3FFE5B5B5BEA0FE023367FA426>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmsy10 14.4 1 /Ff 1 36 df<1538157CB3B3B3B10060170C00FC177EB4EE01FE01C0150701F0151FD81F FCED7FF0D803FEEDFF802600FF80903803FE00D93FC0EB07F8D90FE0EB0FE0D907F0495A D903F8495AD901FC49C7FCD9007E13FC023E5BEC3F7D6EB45A6E5B6E5BA26E5B6E90C8FC A26E5AA3157CA41538A31518376A7ED23C>35 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmmi10 10 6 /Fg 6 122 df<0103B512F84914FC6D14F890390007F8005DA34A5AA44A5AA44A5AA44A C7FCA414FEA4495AA4495AA4495AA4495AA4495AA4495AA449C8FCA25BB6FCA25C26397D B824>73 D<147E903803FF8090390FC1C38090391F0067C0013C136F49133F13F84848EB 1F80485A1207485AED3F00485AA2123F90C7127E5AA300FE5CA448495A160CA3913803F0 18A2127C1407020F13306C131B001E013113606C13E1260783C013C03A03FF007F80D800 FCEB1F0026267DA42C>97 D<133FEA0FFF5AA2EA007EA45BA4485AA4485AA4485A14FCEB E3FF9038E707C0390FCC01E001D813F013F09038E000F8485A4913FCA348C7FCA4007E13 01A448EB03F8A315F014074814E0A2EC0FC0A2EC1F8015000078133EA26C5B14F06C485A 380F07C06CB4C7FCEA01FC1E3B7CB924>I110 D<903907E001F090391FF807FC9039 383C0E0E9039601E180F903AC00F301F80D80180143FD8030013E000061600EDC03E4815 1C93C7FC48495AA3C7FC4AC8FCA4147EA45C160CA349485B121C003E5DEA7E0300FE5DD9 06785B00FC4A5A27780C3C03C7FC3938381E0E391FF00FFC3907C003F029267EA42F> 120 D<13F8D801FE1470D8070F14F8000E1401000C138012181230ED03F0EA601FA33AC0 3F0007E0A3EA007EED0FC05BA34848EB1F80A44848EB3F00A4157EA45D00011301140338 00F80690387C1DF8EB3FF9EB0FE1EB00014A5AA25D000F1307D81F805B003F130F5D4948 C7FC003E133E00305B5C6C485A380E07C06CB4C8FCEA01FC25367EA429>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmtt9 9 27 /Fh 27 118 df<90383C03C090387E07E0A7EBFE0F01FC13C0A2007FB512FEB7FCA4003F 14FE3901F81F80AC003FB512FEB7FCA46C14FE3903F03F00A200075BEBE07EA73803C03C 202E7DAD27>35 D40 D<127012F812FE7E6C7E6C7EEA0F E06C7E12036C7E7F1200137EA27FA2EB1F80A3EB0FC0A4EB07E0ACEB0FC0A4EB1F80A3EB 3F00A2137EA25B12015B485A1207485AEA3FC0485A48C7FC5A12F81270133A7AB327>I< 120FEA3FC013E0EA7FF0A213F8A2123FA2120F120113F01203EA07E0120FEA7FC0EAFF80 13005A12700D14738927>44 D<007FB512F8B612FCA46C14F81E067C9927>I<130E131F A25BA25B5B5A5A123F5AB5FC13BFEA7C3F1200B3A9003FB512805A15C01580A21A2E79AD 27>49 D<121EEA7F80A2EAFFC0A4EA7F80A2EA1E00C7FCAC121EEA7F80A2EAFFC0A4EA7F 80A2EA1E000A20729F27>58 D<007FB512E0B612F0A36C14E039001F8000B3B2007FB512 E0B612F0A36C14E01C2E7BAD27>73 D<387FFFC080B5FC7E5CD803F0C8FCB3AAED0780ED 0FC0A7007FB6FCA2B7FC7E1680222E7FAD27>76 D<007FB5FCB612E081816C803907E003 FEEC00FF81ED3F80151F16C0150FA6151F1680153FED7F005DEC03FE90B55A5D5D5D92C7 FC01E0C8FCADEA7FFEB5FCA36C5A222E7FAD27>80 D<90383FC0E03901FFF9F0000713FF 5A5A383FC07FEB801F387E000F14075A1403A3EC01E06C90C7FCA2127F13C0EA3FF86CB4 7E6C13F86C13FE6CEBFF80C66C13C0010713E09038007FF0140FEC07F81403EC01FCA214 00127812FCA314016C14F86C130390388007F09038F00FE090B5FC15C0158000F9EBFE00 38701FF01E2E7CAD27>83 D<3A7FFE01FFF8B54813FCA36C486C13F83A07E0001F80B3AB 6D133F00031500A26D5B6C6C13FE6C6C485AEBFF036DB45A6D5B6D5B01071380D900FCC7 FC262E80AD27>85 D<007FB512F8B612FCA46C14F81E067C7E27>95 D<48B47E000F13F04813FC4813FF81EB807FEC1FC0381F000F00046D7EC7FCA2EB07FF13 7F0003B5FC120F5A383FF807EA7FC0130012FE5AA46C130F007F131F383F807F90B61280 6C15C07E000313F13A007F807F8022207C9F27>97 DIIII<90381FC03F90397FF1FFC048B612E05A5A390FF07FC73A1FC01FC3C0903980 0FC000A248486C7EA66C6C485AA2EBC01F390FF07F8090B5C7FC5C485BEB7FF0EB1FC090 C9FCA27F6CB5FC6C14E04814F84814FE5A90388000FF007EC7EA3F80007C140F00FC15C0 481407A46C140F007C1580007F143F6C6CEB7F00391FF003FE90B5FC000714F86C5CC66C 1380D90FFCC7FC23327E9F27>103 D<130F497E497EA46D5A6DC7FC90C8FCA7383FFF80 487FA37EEA000FB3A4007FB512F0A2B612F86C14F0A21D2F7BAE27>105 D<397F07C01F3AFF9FF07FC09039FFF9FFE091B57E7E3A0FFC7FF1F89038F03FC001E013 8001C01300A3EB803EB03A7FF0FFC3FF486C01E3138001F913E701F813E36C4801C31300 2920819F27>109 D<387FE03F39FFF1FFC001F77F90B57E6C80000313C1EC01FCEBFE00 5B5BA25BB03A7FFF83FFE0B500C713F0A36C018313E024207F9F27>II<397FFC01FC39FFFE0FFF023F13804A13C000 7F90B5FC39007FFE1F14F89138F00F809138E002004AC7FC5CA291C8FCA2137EAD007FB5 7EB67EA36C5C22207E9F27>114 D<90387FF3800007B512C0121F5AA2387F801F38FC00 0F5AA2EC07806C90C7FCEA7F8013FC383FFFE06C13FC000713FFC61480010F13C0903800 3FE014070078EB03F000FC1301A27E14036CEB07E0EBC01F90B512C01580150000FB13FC 38707FE01C207B9F27>I<133C137EA8007FB512F0B612F8A36C14F0D8007EC7FCAE1518 153C157EA315FE6D13FC148390381FFFF815F06D13E0010313C0903800FE001F297EA827 >I<397FE01FF8486C487EA3007F131F00031300B21401A21403EBF80F6CB612E06C15F0 A2EB3FFE90390FF07FE024207F9F27>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmtt12 12 5 /Fi 5 89 df<91391FE003809139FFFC07C0010313FF010F148F4914EF4914FF90387FF0 1F9038FFC00748EB00034913004848147F485A49143F485A49141F121F5B003F150F90C8 FCA25A007EED078093C7FCA212FEA25AAB7EA2127EA3007FED07806CED0FC0A27F121F7F 000F151F6D15806C7E6D143F6C6CEC7F006C6C14FE6D13016C9038C003FC90397FF00FF8 6DB55A6D5C6D5C010391C7FC010013FCEC1FE02A3F7CBD33>67 D<003FB712C04816E0B8 FCA27E7ED801F8C71207A8EE03C093C7FCA6151E153FA490B6FCA69038F8003FA4151E92 C8FCA817F0EE01F8A9003FB7FC5AB8FCA27E6C16F02D3D7DBC33>69 D<003FB712F84816FCB8FCA43AFC000FC000A800781678C71500B3B3A40107B57E498049 80A26D5C6D5C2E3D7EBC33>84 D<263FFFC090B5FC486D481480B56C4814C0A26C496C14 806C496C1400D801F8C7EA07E0B3B3A36D140F00005EA26D141F017E5D017F143F6D92C7 FC6E5B6D6C13FEECF00390390FFC0FFC6DB55A6D5C6D5C6D6C1380DA1FFEC8FCEC07F832 3E80BC33>I88 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmbx12 12 36 /Fj 36 123 df45 DI49 DII<161F5EA25E5E5DA25D5D5D5DA25D5D92B5FCEC01F715E7EC03C7EC0787 140FEC1F07141E143C147814F8EB01F014E0EB03C0EB0780130FEB1F00131E5B5B13F85B 485A485A485A120F90C7FC121E5A127C5AB91280A4C8000F90C7FCAC027FB61280A43141 7DC038>I<00031503D807E0143F01FFEB07FF91B55A5E5E5E5E5E93C7FC5D15F815E04A C8FC01C0C9FCAAEC3FF001C1B5FC01C714C09039DFC03FF09039FE000FF801F86D7E496D 7E496D7E4915806C4815C0C8FC6F13E0A217F0A317F8A21206EA1FC0487E487E12FF7FA2 17F05BA24915E06C485B5B003CC714C0003E4A1380001E16006C6C495A6C6C495AD803F0 EB3FF8D801FEEBFFF06CB65A013F1480010F01FCC7FC010113C02D427BC038>I<4AB47E 021F13F0027F13FC903901FF807E903907FC001FD90FF0EB07804948EB1FC04948137F49 48EBFFE049C7FC485C485A1207A248486D13C0A2001FED7F80EE1E00003F92C7FCA25B12 7FA3EC1FFE91383FFFC000FF497F9138E00FF89039F98007FC01FB6D7E4A6C7E01FE1580 17C0814915E0A217F0A25B17F8A3127FA6123FA217F0121F7F000F16E0A200074A13C0A2 6C6C15806C6C4913006C5D90397FC007FC90393FF03FF86DB55A010714C0010191C7FC90 38003FF82D427BC038>I65 D67 DII< B712E0A4D8001F90C7FCB3B3B3A6B712E0A423447DC32A>73 D76 D80 D<923807FFC092B512FE0207ECFFC0 91261FFE0013F0DA7FF0EB1FFC902601FFC0EB07FF010790C7000113C049486E7F49486F 7E49486F7E49486F7E49486F7E488448496F1380A248496F13C0A24890C96C13E0A24819 F04982003F19F8A3007F19FCA249177FA300FF19FEAD007F19FCA36D17FF003F19F8A300 1F19F06D5EA26C19E06E5D6C03FE15C06C912603FF8014806E486D5A6C9028E00F01E00F 13006C91261E00F05B90267FF01C9038781FFC6D6C486D485AD91FFC6E485AD90FFE4B5A D907FF6E5B010101DC92C7FC6D01FE495ADA3FFFEBFFF8020790B500E013020200170703 07EBC7F092C7EA03F872130F72131F9538FF80FF71EBFFFEA47114FCA27213F8A27213F0 A27213E07213C0721300F000FC48587AC454>III<903807FFF0017F13FF48B612C03A03FC007FF0486CEB1FF86F7E486C6D 7E6F7E83A26C487F836C5AEA00F090C7FCA4150F023FB5FC0103B6FC011F1301EB7FF038 01FFC000071300485A485A485A5B127F5B12FFA35DA26C6C5B15066C6C5B6C6C013813F0 3C0FFF80F07FFFC00003EBFFE0C6EC801F90390FFE0007322C7DAB36>97 D99 DII<177E9139 FFE001FF010FD9FE071380013F9038FF8F9F903BFFC07FFC3FC0489038001FF04848EB0F F84848EB07FC000F9238FE1F80490103EB0F00001F6FC7FCA2003F82A7001F93C7FCA200 0F5D6D130700075D6C6C495A6C6C495A6C9038C07FE0D801BFB51280D8038F49C8FC48C6 13E091CAFCA2487EA37F13F06CB612C016FE707E6C16E0836C826C8248821207D80FF0C7 EA3FFFD81FC01407484802011380007F8148C9127FA56C6CEDFF00A26C6C4A5A6C6C4A5A 6C6C4A5AD807FEEC3FF03B01FFC001FFC06C6CB6C7FC010F14F80100148032417DAC38> 103 DI<13 78EA01FE487E481380A24813C0A46C1380A26C13006C5AEA007890C7FCACEB7FC0EA7FFF A412037EB3B0B6FCA418467CC520>I108 D<90277F8007FFEC0FFEB5011F01C090383FFF80037F01F090B512E0913D81 F81FF803F03FF0913D83C00FFC07801FF80003903D870007FE0E000FFC6C018E6E488002 9C6D4913070298153002B003E080A202E05DA34A5DB3A8B60081B60003B512FEA4572C7C AB5E>I<90397F8007FEB590383FFFC04B7F913981F03FF0913983C00FF80003D987007F 6C018E80029C1307149802B080A214E0A35CB3A8B60083B512FEA4372C7CAB3E>II<90397FC01FF8B500C1B5FC02C714E09139CFC0 3FF09139FF000FFC000301FC6D7E6C01F06D7E4A6D13804A15C08218E0EF7FF0A218F8A2 173FA218FCAA18F8177FA218F0A2EFFFE0A24C13C018806E5B6E15006EEB0FFE02FEEB1F F89139CFC07FF002C7B512C002C191C7FC9138C03FF092C9FCAFB67EA4363F7DAB3E>I< 90387F807FB53881FFC0028313F091388787F891388E0FFC0003138C6C90389C1FFE1498 14B0A29138F00FFC14E0ED07F8ED01E092C7FC5CB3A7B612E0A4272C7DAB2E>114 D<90391FFE038090B512CF000314FF380FF003391F80007F90C7123F48141F007E140FA2 00FE1407A27EA201C090C7FC13F0EBFF806C13FCECFF806C14E06C14F86C806C806C80C6 1580013F14C01301EB000F020013E00070147F00F0141FA26C140FA36C15C07E16806C14 1F6D140001E0137E9038F801FC00F8B55AD8F03F13E026E007FEC7FC232C7CAB2C>III121 D<001FB71280A39026FC000F130001E0495A49133F495C90C7485A4B5A003E5B5E4A5B00 3C5B5E4A90C7FC4A5A143FC75B4A5A4A5A5B5D495B5B5D499038000780495A133F5C4948 130F494814005A5C48495B5A5C4890C75A48485C003F5D49EB03FE4848131FB7FCA3292C 7DAB32>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmtt8 8 8 /Fk 8 81 df<121FEA3F80EA7FC0A213E0A3123F121F120313C012071380121FEA7F0012 FE5A12700B12748823>44 D<90380FE06090387FF8F090B5FC5A3803F83F3807E00F380F C007EA1F80EB00035A003E1301127E127CEC00E0150012FC5AA97E127CA215E0007EEB01 F0123E123F6C1303018013E0380FC0073907E00FC03903F83F806CB512006C5B6D5AEB0F E01C297DA823>67 D69 D<387FFFFCB512FEA26C13FC38007C00B3AF387FFFFCB512FEA26C13FC17297AA823>73 D 76 D<397F8001FE00FF14FF6D5A007F14FE001F14F8391EE00778A3EBF00FEB700EA2EB 781EA2EB381CEB3C3CA2EB1C38EB1E78A2EB0E70A3EB07E0A3EB03C0A290C7FCAA397F80 01FE39FFC003FFA2397F8001FE20297FA823>I<3803FFF0000F13FC487F487F397F807F 80387E001F007C130FA348EB07C0B3A46C130F007C1480A3007E131F387F807F6CB51200 6C5B6C5B000313F01A297CA823>79 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmr6 6 4 /Fl 4 53 df<13E01201120712FF12F91201B3A7487EB512C0A212217AA01E>49 DI<13FF000313C0380F03E0381C00F014F800 3E13FC147CA2001E13FC120CC712F8A2EB01F0EB03E0EB0FC03801FF00A2380003E0EB00 F01478147C143E143F1230127812FCA2143E48137E0060137C003813F8381E03F0380FFF C00001130018227DA01E>I<14E01301A213031307130F130D131913391371136113C112 01EA038113011206120E121C12181230127012E0B6FCA2380001E0A6EB03F0EB3FFFA218 217DA01E>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmitt10 10 15 /Fm 15 117 df<1378EA01FE12037F481380A37E1400C6FC133F133E137E5B1201485AEA 0FF0EA7FE0485A5B48C7FC1270111674892C>44 D<913901FC01C091390FFF83E0023F13 E391B512F74914FF491303903807F801903A0FF0007FC0495AD93F80133F49C7FC01FE15 805B1201485A491500120749141E000F92C7FC5B121F5B123F90CAFCA35A127EA412FE5A A4ED078082007E140FA2151F5E6C143F4BC7FC6D5B001F495A390FC007FC9038F01FF86C B55A6C14C06C5C26007FFCC8FCEB0FE02B3578B32C>67 D<010FB7FC18805B7FA2D900FE C7EA3F005CA201015D177E5CA20103153C94C7FC5CA21307ED01E04A487EA2010F1307A2 91B55AA25BA25EEC800F013F131FA24A6C5A93C8FC4990C9FCA2137EA213FE160F494A7E A20001153F94C7FC5BA200035D167E007FB612FEB7FCA25E7E31337EB22C>69 D<010FB6FC17805B7F170090260003F8C7FC5DA21407A25DA2140FA25DA2141FA25DA214 3FA292C8FCA25CA2147EA214FEA25CA21301A25CA21303A25CA21307A25CA2130FA2007F B512F8B6FC815D7E293379B22C>73 D<903807FFFE497FA36D5BD9007FC7FC147EA214FE A25CA21301A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA291C8FCA25B 161E017E143FA201FE147F167E5BA2000115FE16FC007FB6FCA2B7FC6C15F8A228337EB2 2C>76 DI<91381FFF E049B512FC4980010F805BDAF001138090393FC0007F49C7123FA2137E5BA248481500A3 485AA2167E485AA448485CA44848495AA448C7485AA4484A5A127EA24B5AA300FE4A5A5A 153F6C92C7FC5D15FE6C13019038C00FFC90B55A6C5C6C5C6C1480000301FCC8FC293579 B32C>79 D<010FB512FCEEFF804915C06D15E017F0903A00FE001FF84A1307EE03FC0101 140116005CA21303A25CA21307EE01F84A130317F0010F1407EE0FE04AEB3FC0EE7F8001 1F903803FF0091B55A5E16F016C04949C7FC91C9FCA35B137EA313FE5BA312015BA31203 EA7FFFB57EA36C90C9FC2E337EB22C>I97 D<147F903803FFC0010F13F0013F13F85B9038FF81FC3801FE004848137E485AD80FE013 FE4913FC121F383F800190380007F848EB3FF090B5FC15E01580B5EAFE0014E000FCC8FC A6127E151C007F143E6C6C13FE381FC00790B5FC6C14FC6C14F0000114C039003FFC001F 2475A32C>101 D103 D<14FC903807FF80011F13E04913F090B5FC48EB83F8 3903FE01FCEBF800485A4848137E5B485A123F90C7FC5A127EA215FE12FE4814FCA21401 15F8140315F0EC07E0140F007EEB1FC0EC3F80007F13FFD83F8313006CB45A14F86C5B00 0313C0D8007EC7FC1F2476A32C>111 D<903907C007C090391FF03FF090393FF8FFFCEB 7FFD91B57E9039FC7FF87F4B7ED801F801E01380EDC01FECFF8000031400495AA23801E1 FCEA00015CA20103143FA24A1400A201075C167E16FE5E010F13014B5A4B5AECF80F011F 495A6E485A91B55A93C7FC495BEC9FF8EC07C091C9FC5BA2137EA213FEA25BA21201A25B A2387FFFE0A2B57E6C5BA2293680A32C>I114 D<14E0497E1303A21307A25CA2130FA25CA2131FA25C007FB5128015C0B6 FC7E1580C66CC7FCA2137EA213FEA25BA21201A25BA21203A25BA2000714C0EC01E09038 E003F0A2000F1307EC0FE09038C01FC0143FEC7F809038E1FF006CB45A5C6C5B6C13E0D8 003FC7FC1C3374B22C>116 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmti10 10 47 /Fn 47 122 df39 D<1504151C1538156015C0EC 0380EC0700140E5CA25C5C5C1301495A5C130749C7FC130E131E5BA25BA25BA212015B12 035BA212075BA2120F90C8FCA25A121EA2123EA2123CA2127CA31278A312F8A35AAB1270 A21278A31238A2123C121CA27EA2120612076C7E12016C7E13401E5274BD22>I<140814 0C140E1406801580A2EC01C0A2EC00E0A315F01570A21578B115F8A315F0A31401A215E0 A21403A215C0A214071580A2140F1500A2141EA2143E143CA25CA25CA2495A5C1303495A 91C7FC5B130E5B133C5B13705B485A485A48C8FC120E5A5A5A12C05A1D527EBD22>I44 D<387FFFF014F8B512F0A26C13E015057993 1E>I<120E123FEA7F80A212FFA21300127E123C0909778819>I50 D52 D<01021410D9038013F0903907F007E091B512C0168016004913FC5D15C0D9 0E1CC7FC49C8FCA45BA45BA314FE9038E7FF809038EF03E09038F801F0EBF000D801C07F 6C487F90C7127CA2157EA215FEA5000C495A123E127F5D4813035A485C48130700E05C4A 5A5D6C49C7FC0070133E5C6C485A381E07F0380FFFC06C90C8FCEA01FC243877B62A>I< 15FE913803FF80020F13C091383F81E0EC7C0049481370903903E003F0903807C007EB0F 8090391F000FE01507013E14C04990C7FC13FC5B1201485AA212075B000F13FE9038E3FF 80391FC703C09038CC01E09038D800F048487F01E0137849137CA24848137EA290C7FCA2 15FE12FEA34A5A5AA25D1403A25D4813075D4A5A5D007C131F4AC7FC003C137C003E5B38 1F03F06CB45A6C1380D801FCC8FC243876B62A>I56 DI65 D67 D<0103B612FC49EDFF8018E0903B000FF0001FF04BEB07F8EF 01FC717E4A48147F841980181F4A4815C0A2180FA24AC813E0A414FEA44948151FA44948 16C0183FA349481680187FA2190049485D60A24D5A495A4D5A60170749484A5A604D5A4D C7FC49C85A17FEEE01F8EE07F001FE4A5AEE3F800001DA03FFC8FCB712FC16E093C9FC3B 397BB83F>I<0103B8FC5B7F903A000FF000034BEB007F183E181E4A5AA44A5A181CA34A C8FCEE0380A2181802FE49C7FCA35E4948130E161E167E91B512FE495CA2ECF800167C49 481338A4494849136018E0A293386001C049481300EF0380A34948EC0700A2170E171E49 C8FC5F177C5F01FE140116070001ED7FF0B8FC5FA238397BB838>I<0103B712FE5B7F90 3A000FF000074B1300187C183C4A5AA44A5A1838A34AC8FCA21603EF803002FE49C7FCA3 5E4948130E161EA216FE49B55AA3ECF80049481378A449481370A44948136093C8FCA349 5AA449CAFCA413FEA2487EB6FCA25C37397BB836>II<0103B512F8A216F090 390007F8005DA34A5AA44A5AA44A5AA44AC7FCA414FEA4495AA4495AA4495AA4495AA449 5AA4495AA449C8FCA25B007F13FEB5FC7E25397CB820>73 D<0103B512F849806D5C9026 000FF8C7FC15E0A34A5AA44A5AA44AC8FCA414FEA4495AA4495AA4495AA44948140C171C A21738495AA21770A2494814F017E01601A249C7EA03C01607A2EE1F8001FE143FEEFF00 00011407B8FC5EA22E397BB834>76 D<902603FFF8923807FFE0494D13F06D4D13E0D900 0FEFF0004F5AA21977021D4C5AA2DA1CFCEC01CFA202384B485AF0071FA2180E02704CC7 FC181CA2183802E0ED707EA2037E14E0A2D901C04A485AEF0380A2EF0700D903804B5A17 0EA2171CD907004A485AA26F1370A2010E4B485AEE01C0A2EE0380494C5AEE0700A2160E 494A495AA2ED1FB8A24902F049C8FC5EA201F05C187E00015DD807F816FEB500C0903900 7FFFFC151EDA800E5D4C397AB84A>I<902603FFF091B51280494B14C06F1680D9000F91 39000FF000F007C06F5DA2021D93C7FCEC1CFEA2814A6C140EA26F7EA202705D6F7EA282 DAE00F5CA26F7EA2D901C05D6F7EA349486C6C5BA282150049C7495A167FA3010E91383F 8380A217C3161F4903C7C8FCEE0FE7A349EC07FEA31603495DA2160113F0705A1201EA07 F8B500C014781770173042397BB83E>II<0103B612F84915FF6D1680903B000FF0003FE04BEB0FF0EF03F8 A24A48EB01FCA318FE4A5AA44AC7EA03FCA318F802FE140718F0EF0FE0A24948EC1FC0EF 3F80EFFE004C5A4948EB0FF091B612C04CC7FC02F8C9FC495AA4495AA4495AA4495AA449 CAFCA413FEA21201B512FCA25C37397BB838>I<0103B612E04915FC17FF903B000FF000 7F804BEB1FE0170FEF07F04A48EB03F8A318FC4A5AA44AC7EA07F8A3EF0FF002FE15E017 1F18C0EF3F804948EC7E004C5AEE03F0EE1FC049B6C7FC16F89138F8007E161F49486D7E 83160783495AA283A24948495AA44948131FA449C7485A180EA301FE161C041F13180001 1738B500FC90380FE070040713E0933801FFC0CAEA7F00373A7BB83D>82 D<92387F800C913801FFF00207EBF81C91391FC07C3C91393E001E780278EB07F85C4948 1303494814F0010714015C130F91C713E05BA34915C0A393C7FC80806D7E14FCECFF806D 13F06D13FF820101806D80023F7F02077FEC007FED0FFC150315011500A2167CA2120612 0EA3001E5DA25E1501003E5D1503003F5D4B5A486C49C7FC6D131ED879F0137C3970FE01 F839F07FFFE0D8E01F138026C003FEC8FC2E3B7AB92F>I<0003B812E05AA2260FF800EB 001F01C049EB07C090C71403121E4A5A121C003C178012384A5A12781270EF07004A5A5A A2481606C7484890C7FCA44A5AA44A5AA44AC9FCA414FEA4495AA4495AA4495AA4495AA2 EB3FF0007FB512F8A3333971B83B>I97 D<137EEA0FFE121F120FEA007CA45BA4485AA4 485AA4485AEBC1F0EBC7FCEBCE0E380F980701F013809038E003C013C0001F14E0138013 00A2123EA4481307A448EB0FC0A31580141F5A15005C143E5CA25C00705B387801E03838 03C0383C0780D81E1FC7FCEA0FFCEA03F01B3B76B926>I<147F903803FFC0903807C1E0 90381F0070013C13385B4913F83801E00100031303EA07C0000F14F090388001E0001F90 C7FC90C8FC5A123E127EA35AA55AA31510153800781470007C14F0EC01E0003CEB03C06C EB0F00000E133E380781F83803FFE0C690C7FC1D2677A426>II<147E903803FF8090380FC1C090381E00E0017C13 705B485A485A485AA2484813E0121F90380001C048EB0780EC1F00387E01FC387FFFF049 C7FC007EC8FC5AA8007C14101538157015F0003CEB01E06CEB03C0EC0F006C133E380781 F83803FFE0C690C7FC1D2677A426>IIIII108 DII<147F903803 FFC0903807C1E090381F0070013C137849133C49133E485A0003141E4848131F120F5B12 1F90C7FC48143F123E127EA348147EA3157C15FC4814F8140115F0140315E00078EB07C0 007C1480EC0F00003C131E6C5B000E13F8380783E06CB45AC648C7FC202677A42A>I<90 390F800F8090391FC03FE0903938E07070903970F0C0389138FB803C01E0EB001E14FED8 01C0141F5C5CA2380381F0A3EA00014948133FA44948137EA3167C494813FCA216F81501 011F14F0ED03E0A2ED07C0013F1480ED0F00ECC01E013E5B90387C70F8EC3FE0EC1F8091 C8FC5BA4485AA4485AA3387FFF80B5FC6C90C8FC28357FA42A>I<3903E003F03907F00F FC390E383C0E391C3C700F90393EE01F800038EBC03F133F007001801300EC003E151C01 3E90C7FCEAE07E137CA212005BA4485AA4485AA4485AA4485AA448C9FCA2120E212679A4 23>114 D<14FE903807FF8090380F03C090381C00E04913705B01F013F0EBE001000113 03A215E00003EB01C06DC7FC6C7E13FF14F06C13FC6D7E6D7E6D138013019038001FC014 0F1407A2123C127E00FE1480A25A48EB0F0000E0130E0060131E00705B6C5B381E03E06C B45AD801FEC7FC1C267AA422>I<1303EB0780130FA4EB1F00A4133EA45BA2B512FC14FE 14FC3800F800A3485AA4485AA4485AA4485AA448C7FC1438A21470123EA214E014C01301 1480EB0300EA1E06EA0E1CEA07F8EA03E0173578B31C>I<13F8D803FC14C0D8070EEB01 E0D80E0F1303120C121C1238ED07C0485AA3D8E03EEB0F80A3C65AED1F005BA34848133E A448485B160EA3EDF81CA31401163814030001010613703900F00C789039783838E09039 3FF01FC090390FC00F80272679A42D>I<01F81507D803FC903901800F80D8070E903903 C01FC0D80E0F1307000C160F121C00381607ED0F8048481503A3D8E03ED91F001380A3C6 5A033EEB07005BA3484849130EA44848495BA35FA21730020114701760020314E000015E 903AF007780180000090380E3C0390277C1C1E0FC7FC90391FF80FFC903907E003F03226 79A437>119 D<13F8D803FCEB0180D8070EEB03C0D80E0F1307120C121C1238ED0F8048 5AA3D8E03EEB1F00A3C65A153E5BA348485BA448485BA44A5AA213C0EBE0035D14070001 130F0000131F9038F07FC0EB3FE7EB1F87EB00074A5AA292C7FC001E5B003F131E48133E 143C007E5B007C5B00705B495A38380780D81C1FC8FCEA0FFCEA03F0223679A428>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo cmr7 7 4 /Fo 4 53 df<13381378EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521>49 D<13FF000313E0380E03F0381800F848137C487F00787F12FC6C1480A2140FA2127CC712 1F1500A25C143E5C14785C495A495A495A49C7FC131C5B903870018013E0EA01C0390380 0300EA06005A001FB5FC5A485BB5FCA219267DA521>I<13FF000313E0380F01F8381C00 7C00307F123C007E133F80A25C123CC7123EA25C5C495AEB07E03801FF8091C7FC380001 E06D7E147C80143F801580A21238127C12FEA21500485B0078133E00705B6C5B381F01F0 3807FFC0C690C7FC19277DA521>I<14381478A214F81301A213031307130E130C131C13 381330136013E0EA01C013801203EA070012065A121C5A123012705AB612E0A2C7EAF800 A7497E90383FFFE0A21B267EA521>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fp cmr8 8 56 /Fp 56 123 df<9138FF807E01079038E3FF80903A1F8077C3C0903A3E007F07E0017813 FE5B00019138FC03C0484890387C018093C7FCA9B712FCA22703E0007CC7FCB3A6486C13 FE3A7FFF0FFFF0A22B2E7FAD29>11 D<14FF010713E090381F80F090383E00380178137C 4913FC1201485A157892C7FCA8B612FCA23803E000157CB3A5486C13FE3A7FFF0FFFE0A2 232E7FAD27>I<13031307130C131C1338137013E0A2EA01C0EA0380A2EA0700A25A120E 121EA2121C123CA35AA512F8A25AAB7EA21278A57EA3121C121EA2120E120F7EA2EA0380 A2EA01C0EA00E0A213701338131C130C1307130310437AB11B>40 D<7E7E126012707E7E7EA27EEA0380A2EA01C0A213E0120013F0A213701378A3133CA513 3EA2131EAB133EA2133CA51378A3137013F0A213E0120113C0A2EA0380A2EA0700120EA2 5A5A5A12605A5A0F437BB11B>I<1238127C12FEA212FF127F123B1203A41206A3120CA2 121812301260124008147A8614>44 DI<1238127C12FEA3127C 123807077A8614>I<15C01401A2EC0380A3EC0700A2140EA35CA35CA35CA35CA2495AA3 495AA349C7FCA3130EA25BA35BA35BA35BA3485AA2485AA348C8FCA3120EA35AA35AA25A A35AA25A1A437CB123>I<130C133C137CEA03FC12FFEAFC7C1200B3B113FE387FFFFEA2 172C7AAB23>49 DII57 D<1238127C12FEA3127C12381200AF1238127C12FEA3127C1238071D7A9C 14>I<1238127C12FEA3127C12381200AF1238127C12FEA3127E123E1206A4120CA31218 A21230A212601240072A7A9C14>I<4A7E4A7EA34A7EA24A7EA3EC19F8A2EC39FC1430A2 4A7E157EA24A7EA2010180EC801FA249486C7EA2498001061307A2496D7EA2010FB5FC49 80903818000101388001301300A249147EA201E0147F4980A20001ED1F80A2000316C0D8 0FF0EC3FE0D8FFFC0103B5FCA2302E7EAD35>65 D70 D72 DI75 DIIIII<90383F80303801FFF03903C07C70390F000EF0001C1303481301A24813 00157012F0A21530A27EA26C1400127E127FEA3FE0EA1FFEEBFFE06C13FC000313FF6C14 80D8003F13C0010313E09038003FF01407EC01F81400157CA2124000C0143CA46C1438A2 6C147815706C14E000FEEB01C039F780038039E1F00F0038C07FFEEB0FF01E2F7CAD27> 83 D<007FB712F8A29039000FC003007C150000701638A200601618A200E0161CA24816 0CA5C71500B3A94A7E011FB512E0A22E2D7EAC33>I87 D<3B7FFFE003FFF8A2000390C713806C48EC7E0000001538017F14306D14706E5B6D6C5B 6D6C485A15036D6C48C7FC903803F80601015BECFC1C6D6C5AEC7F305DEC3FE06E5A140F 816E7E81140DEC1DFCEC38FEEC307F14609138E03F8049486C7EEC800FD903007F496D7E 010E6D7E130C011C6D7E496D7E0130147E49147F01E0EC3F80D803F015C0D80FF8EC7FE0 D8FFFE0103B5FCA2302D7EAC35>I 91 D93 D97 DII<15F8141FA214011400ADEB0F E0EB7FF83801F81C3803E00738078003380F0001481300123EA2127E127C12FCA7127CA2 127E123E6C13017E380780033803C00E3901F03CFC3A007FF0FFC0EB1FC0222E7EAD27> III<15F890383F03FC 3901FFE70E3903C0FC1E38078078390F003C0C48EB3E00001E131E003E131FA6001E131E 001F133E6C133C6C6C5A6D5A380DFFE0D81C3FC7FC90C8FCA47E380FFFFC6CEBFF806C14 C0000F14E0391E0007F00038EB00F80078147848143CA5007814786C14F0001FEB03E039 07E01F803901FFFE0038003FF01F2C7E9D23>II<1207EA0F80EA1FC0A3EA0F80EA0700C7FCAAEA07C012FFA2120F1207B3A4EA0F E0EAFFFCA20E2E7EAD14>I<1307EB0F80EB1FC0A3EB0F80EB070090C7FCAAEB07C013FF A2130F1307B3AC123000781380EAFC0F1400131EEA783CEA3FF8EA0FE0123B83AD16>I< EA07C012FFA2120F1207ADEC1FFEA2EC07F015C092C7FC140E5C5C14605CEBC180EBC3C0 13CFEBDDE0EBF1F0EBE0F8EBC07880143E80806E7E816E7E140181D80FE013FC3AFFFE07 FF80A2212E7EAD25>II< 2607C07FEB07F03BFFC3FFC03FFC903AC781E0781E3B0FCC00F0C00FD807D8D9F9801380 01F090397F0007C049137EA249137CB2486C01FEEB0FE03CFFFE0FFFE0FFFEA2371D7E9C 3C>I<3807C0FFD8FFC313C09038C703E0390FCC01F0EA07D89038F000F85BA25BB2486C 487E3AFFFE1FFFC0A2221D7E9C27>II<3807 C0FE39FFC7FF809038CF03E0390FD800F0D807F0137849137C497F811680A2150F16C0A7 1680151F16005D153E6D5B6D5B9038D801F09038CE07E09038C7FF80D9C1FCC7FC01C0C8 FCAA487EEAFFFEA2222A7E9C27>I<90380FE01890387FF8383801F81C3903E006783807 C003D80F8013F8381F00015A003E1300127E127C12FCA7127C127EA2123E6C1301380F80 0312073803C00E3801F03C38007FF0EB1FC090C7FCAA4A7E91381FFFC0A2222A7E9C25> I<380781F838FF83FCEB8E1E380F9C3FEA079813B0141EEBE000A35BB0487EB5FCA2181D 7E9C1C>I<3801FE18380FFFB8381E01F838380078481338141812F0A27E6C1300EA7F80 13FC383FFF806C13E0000713F0C613F8EB07FC13000040133E12C0141E7EA26C131C6C13 3C6C133838FF01F038E3FFC000C01300171D7E9C1C>I<1360A413E0A312011203A21207 121FB512F0A23803E000AF1418A70001133013F03800F860EB3FC0EB1F8015297FA81B> II<3AFFFC01FFC0A23A0FE0007E000007143C000314 3815306D137000011460A26C6C5BA2EBFC01017C5BEB7E03013E90C7FCA2EB1F06A2148E EB0F8CA2EB07D8A2EB03F0A36D5AA26D5A221D7F9C25>I<3BFFFC3FFE07FFA23B0FE003 F001F83B07C001E000F017E06D487E000316C0A23B01F007F80180EC0678157C3B00F80C 3C0300A2153E90397C181E06A290397E381F0E90393E300F0CA2D91F701398EC600716D8 90390FC003F0A36D486C5AA36DC75A301D7F9C33>I<3AFFFC07FF80A23A07F003FC0039 03E001E0D801F05B01F85B000049C7FCEB7C06EB3E0E6D5A14B8EB0FB0EB07E013036D7E 497E1307EB067C497EEB1C1F01387FEB700F90386007C0496C7E00016D7E000780001F49 7E3AFFF007FFC0A2221D7F9C25>I<3AFFFC01FFC0A23A0FE0007E000007143C00031438 15306D137000011460A26C6C5BA2EBFC01017C5BEB7E03013E90C7FCA2EB1F06A2148EEB 0F8CA2EB07D8A2EB03F0A36D5AA26D5AA2495AA2130391C8FC1278EAFC06130E130C5BEA 7870EA3FE0EA0F80222A7F9C25>I<003FB51280A29038001F00003C133E0038137E0030 137C00705B386001F013035C495AC6485A131F91C7FC133E5B9038FC018013F8EA01F0EA 03E00007130313C0D80F801300EA1F00485B003E5B48133FB6FCA2191D7E9C1F>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fq cmsy6 6 1 /Fq 1 4 df<136013701360A20040132000E0137038F861F0387C63E0380F6F00EA03FC EA0060EA03FCEA0F6F387C63E038F861F038E060700040132000001300A2137013601415 7B9620>3 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fr cmbx10 10 42 /Fr 42 122 df<913803FF80023F13E049B512F80107EB00FCD90FF8137ED93FE013FE49 48487E4A5A13FF481300A46F5A6F5A93C7FCA592383FFF80B8FCA4000190C7FCB3AB007F D9FC3F13FEA42F3A7EB935>12 D<912603FFC09038FFF1F0023FD9F00F13FF49B5EAFC7F 0107903A007FFFC01FD90FF89138FE003FD93FE0D9FFF8137F4948485B02805C13FF4801 004A133F6F151F167FAABBFCA4000190C7397FC0001FB3AB007FD9FC1FB50007B512C0A4 4A3A7EB950>15 D<141C143C147814F0EB01E0EB03C0EB0780130FEB1F00133E137E137C 13FC485AA2485AA2485AA2120FA25B121FA25B123FA3127FA290C7FCA45AAF7EA47FA212 3FA3121F7FA2120F7FA21207A26C7EA26C7EA26C7E137C137E133E7FEB0F801307EB03C0 EB01E0EB00F01478143C141C165377BD25>40 D<12C07E7E12787E7E7E7F6C7E6C7E7F12 017F6C7EA2137EA27FA21480A2131F14C0A2130F14E0A314F0A21307A414F8AF14F0A413 0FA214E0A314C0131FA21480133FA21400A2137EA25BA2485A5B12035B485A485A90C7FC 121E5A5A5A5A5A15537ABD25>I46 D<143C147CEB01FC1307137FB5FCA3138FEA000FB3B3A6 007FB61280A4213779B630>49 DIII65 D68 DI71 DII76 DI80 D82 D I<003FB91280A4D9F800EBF003D87FC09238007FC049161F007EC7150FA2007C1707A200 781703A400F818E0481701A4C892C7FCB3AE010FB7FCA43B387DB742>I97 D<903801FFE0010F13FC017F13FF9039FF807F803801FE00D807FCEBFFC0485AA2485A00 3FEC7F80ED3F004848130C92C7FCA212FFA9127FA27F123FED01E06C7E000FEC03C07F6C 6CEB0780D801FFEB0F006CEBC07E6DB45A010F13F00101138023257DA42A>99 D<167FED7FFFA4150381AF903801FF81010F13F1013F13F99038FFC07F3901FE001F4848 130748487F000F80485A123FA2485AA312FFA9127FA3123F7F121F5D6C6C5B6C6C5B6C6C 4913802700FF80FD13FC90387FFFF9011F13E1010113012E3A7DB935>I<49B47E011F13 F0017F13FC9038FF81FE3A03FE007F804848133F4848EB1FC0484814E0150F003F15F05B 127FED07F8A212FFA290B6FCA301E0C8FCA4127FA36C7E1678121F6C6C14F816F06C6CEB 03E0D801FF13076C9038C03F80013FB51200010F13FC010013C025257DA42C>II<161FD907FEEB7F80 903A7FFFE1FFC048B538FBE7E03A03FE07FF0F3907F801FE390FF000FF001FED87C04848 90387FC380EEC000007F81A6003F5DA26C6C495A000F92C7FC6C6C485A3903FE07FC48B5 5AD8067F13E0260E07FEC8FC001ECAFCA4121F13C090B512F8EDFF806C15E0826C816C81 82000F81391F80000F48C8138048157F00FE153FA5007FED7F006C6C14FE6C6C495AD80F F0EB07F8D807FEEB3FF00001B612C06C6C91C7FC010713F02B377DA530>I<13FE12FFA4 12071203AFEDFF80020713E04A7F91381E07F891383803FC02607FECC001D9FF807FA214 00A35BB3A3B5D8F87F13FCA42E3A7CB935>II<13FE12FFA4120712 03B3B3ACB512F8A4153A7DB91A>108 DII<903801FFC0010F13F8017F13FF D9FF807F3A03FE003FE048486D7E48486D7E48486D7EA2003F81491303007F81A300FF16 80A9007F1600A3003F5D6D1307001F5DA26C6C495A6C6C495A6C6C495A6C6C6CB45A6C6C B5C7FC011F13FC010113C029257DA430>I<9038FE03FF00FF011F13E0027F13F89039FF FC0FFC9138E003FF0007D9800113806C90C713C049EC7FE0A2EE3FF0A217F8A2161F17FC A917F8163FA217F0167F17E06D15C0EEFF806E4813009138E003FE9039FEF80FFC91387F FFF0021F13C0DA07FEC7FC91C9FCACB512F8A42E357DA435>I<49B4130F010FEBE01F01 3F6D5A9038FFC07C489038001E7F4848130F48486D5A48487F121F003F805B127FA25B12 FFA9127F7FA2123FA26C6C5B120F6D5B6C6C5B6C6C133FC6EBC0F990387FFFF1011F13C1 0101130190C7FCAC037F13FCA42E357DA432>I<3901FC03F000FFEB0FFC4AB4FC91383C 7F80147000079038E0FFC000035BEBFD80A201FFEB7F809138003F00150C92C7FC5BB3A2 B512FCA422257EA427>I<90387FF0383903FFFEF84813FF381FC00F383F0003003E1300 5A157812FCA27E6C140013E06CB47E14F86C13FF6C14806C14E06C14F0000114F86C6C13 FC13039038000FFE14030070130012F0157E7EA26C147C7E6C14F890388001F09038F00F E090B512C000F0140038C01FF81F257DA426>I<131EA5133EA4137EA213FEA212011203 1207001FB512E0B6FCA3D803FEC7FCB21578A8000114F07F6CEB01E090387F83C090383F FF806D1300EB03FC1D357EB425>I<01FE147F00FFEC7FFFA400071403000380B3A35DA3 00015C5D6C6C011D138090267F807913FC90383FFFF16D13C1010313012E257CA435>I< B539E001FFF8A4D803FEC7EA1F00161E6D143E6C153C6E137C6C15786E13F8017F5CECE0 01013F5CA26D6C485AA2ECF807010F5CECFC0F010791C7FC6E5A0103131EECFF3E6D133C A26D13F8A36E5AA26E5AA26E5AA26E5AA22D257EA432>I120 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fs cmbx12 14.4 33 /Fs 33 122 df<157815FC14031407141F14FF130F0007B5FCB6FCA2147F13F0EAF800C7 FCB3B3B3A6007FB712FEA52F4E76CD43>49 DI<91 380FFF8091B512FC010314FF010F15C090263FF00313F09026FF800013FC4848C76C7ED8 03F86E7E4980D807FC168001FF16C0487F82486D15E0A3805CA27E4A4913C07E6C90C7FC D800FC168090C85A18005F167F4C5A5F4B13E04B5B030F5BDB7FFEC7FC91B512F816C016 FCEEFF80DA000713E0030013F8707E70B4FC7013807013C018E07013F0A218F88218FCA3 18FEEA01C0EA0FF8487E487E487EA2B57E18FCA44C13F86C90C7FC18F0495C6C4816E001 F04A13C06C484A1380D80FF84A1300D807FE4A5A2703FFF0035BC690B612F0013F15C001 0F92C7FC010114F8D9001F1380374F7ACD43>I<177C17FE1601A216031607160FA2161F 163F167F16FFA25D5D5DA2ED0FBF151FED3F3F157E157C15F81401EC03F0EC07E015C014 0FEC1F80EC3F00143E5C14FC495A495A5C495A130F495A91C7FC133E137E5B485A5B485A 1207485A5B48C8FC5A127E5ABA12C0A5C96C48C7FCAF020FB712C0A53A4E7CCD43>I<00 03160ED807E0153E01FCEC03FED9FFE0137F91B65A5F5F5F5F5F94C7FC5E16F85E16C04B C8FC15F801E090C9FC91CAFCABEC0FFF027F13F001E3B512FC01E714FF9026FFF80713C0 DAC0017F49C713F8496E7E01F0143F496E7E49816C5AC9148018C082A218E0A318F0A3EA 07C0EA1FF0487E487EA2487EA318E0A25B18C06C485C49168013C0003EC81400003F5D6C 6C5D6C6C4A5A6D4A5AD807F8495B6C6C01075B2701FFC03F5B6C90B6C7FC013F14FC010F 14F0010314809026007FF8C8FC344F79CD43>II<171F4D7E4D7EA2 4D7EA34C7FA24C7FA34C7FA24C7FA34C7FA24C80A283047F80EE7E3F04FE8016FC830301 814C7E03038116F0830307814C7E030F8116C083031F814C7E033F8293C7FC844B82037E 8003FE825D840201834B800203835D840207834B80020F8392B8FCA24A83A24A8492C9FC 854A84027E8202FE845C850101854A820103855C850107854A82010F855C011F83D9FFFC 84B600F8020FB712E0A55B537BD266>65 DI<932601FFF8EC01C0047FD9FF8013030303B600F01307031F03FC131F92 B8133F0203DAE001EBC07F020F01FCC7383FF0FF023F01E0EC07F94A01806EB5FC4A48C9 FC010301F8824949824949824949824949824990CA7E4948835C48854849187FA2484918 3FA2485B1B1F5AA24849180FA45A4A95C7FCA3B5FCAE7EA3806CF207C0A46C7FA26C1A0F 1C806C7FA26C6DF01F00A26C6D183E7E6E606D6C18FC6D6D4C5A6D6D4C5A6D6D16076D6D 4C5A6D6D4C5A010001FE4C5A6E6C6C03FFC7FC6E01E0EC03FC020F01FCEC1FF80203903A FFE001FFE0020091B61280031F4BC8FC030315F8DB007F14C0040101FCC9FC525479D261 >II73 D80 D82 D<0103B5FC013F14F890B612FE486F7E48D9000713E0486DC67FEE 7FFC486D133F707E707EA2846C497F846C90C7FCEA00FC90C8FCA6037FB5FC020FB6FC91 B7FC01071407011F13C090387FFE003801FFF84813E0000F5B485B91C7FC485A485AA25B 12FFA45EA26C6C141D163D6C6C14796D02F97F6C90268001F113F800079026F00FE0EBFF E06C90B5D8807F13F0C64B7E011F01FC7F010101E0010713E03C357CB441>97 D I<913801FFFE021FEBFFF091B612FC010381010F90388003FF90273FFC00071380495A49 484913C0485B485B485B4890C7FC7013805A496E1300003FED00FC94C7FCA2485AA312FF AB127FA27F123FA36C6CED03E0A27E6EEC07C06C7F6CEE0F806C6D141F6C6DEC3F00D97F FC14FE6D6C495A903A0FFFC00FF8010390B512E001001580021F49C7FC020113E033357C B43C>I<4DB47E0407B5FCA5EE001F1707B3A5913801FFC0021F13FC91B6FC010315C701 0F9038C01FE790271FFE0003B5FCD97FF8130049488048498048498048498091C8FC5A5A 5B123FA3485AA312FFAB127FA46C7EA2121FA26C7EA26C6D5C6C5E6C6D5C6C6D91B5FC6D 6C1303D93FFCD907EF13E090280FFF803FCFEBFF806D90B5128F0101ECFE0FD9003F13F0 0203138041537CD24B>I<913807FFC0027F13FC49B6FC010715C0011F010113F0903A3F FC003FF8D97FF0EB0FFC49486D7E48491303484980486F13804890C7FC7013C0485A003F 17E0A2177F485A18F0A312FFA290B8FCA318E001FCCAFCA5127FA37F123FA2001F17E06D ED01F07E6C6D1403EF07E06C6D15C06C160F6C6DEC3F80D97FF8EC7F00D93FFEEB03FE90 3A0FFFC01FFC010390B512F0010015C0023F91C7FC020113F034357CB43D>II<187EDA1FFF903803FF8049B5D8F00F13C00107DAFC3F13E0 011F9138FF7F9F90263FF8039038FC1FF09026FFE00013F04849137F4849EB3FF891C700 1F14E0489338FC0FC0F0038048486E6CC7FCA2001F82A8000F5EA26C6C4A5AA26C5E6E13 3F6C6D495A6C6D495A90267FF803138090B7C8FCD801E714FC01E114F02603C01F90C9FC 91CBFC1207A37FA27F7F13FE90B7FC17F86C16FE717E6C17E018F86C837F6D8248B9FC12 07D80FFCC7000114804848EC001F4848150748486F13C0498100FF82A66C6C4B1380A26C 6C4B13006C6C4B5A6D150FD807FFED3FF86C01C0ECFFF0C601FC010F13C0013FB7C7FC01 0F15FC010115E0D9000F01FCC8FC3C4E7CB543>I<137F497E487F487F487F487FA76C5B 6C5B6C5B6C5B6DC7FC90C8FCAEEB3FF0B5FCA512017EB3B3A5B612E0A51B547BD325> 105 D107 DIII<913801FFE0023F13FF91B612C0010715F8499038807FFC903A3FFC00 0FFFD97FF001037F49486D7F48496D7F48496E7E4890C86C7E488349151F001F83A2003F 834981007F1880A400FF18C0AB007F1880A46C6C4B1300A3001F5F6C6C4B5AA26C6D4A5A 6C5F6E14FF6C6D495B6C6C6C491380D93FFC010F90C7FC903A1FFF807FFE010790B512F8 010115E0D9003F91C8FC020113E03A357CB443>II<90397FE001FCB590380FFF80033F13E0 4B13F09238FE1FF89139E1F03FFC0003EBE3E0C69138C07FFEECE780150014EF14EE02FE EB3FFC5CEE1FF8EE07E04A90C7FCA45CB3AAB612FCA52F357CB437>114 D<903901FFE007011FEBFE1F90B7FC12033907FE001FD80FF01303D81FC07F48487F8248 C87EA2825AA27F7F01F091C7FC13FEEBFFF06CEBFF8015FC6CECFF8016E06C816C15FC6C 810001816C6C1580011F15C01303D9003F14E01400150F030113F00078EC007F00F8153F 161F7E160FA26C16E0A27E6DEC1FC07F6DEC3F806D147F01FCECFF009039FF800FFE6DB5 12F8D8FC1F14E0D8F807148027E0007FF8C7FC2C357CB435>I<143EA6147EA414FEA213 01A313031307A2130F131F133F13FF5A000F90B6FCB8FCA426003FFEC8FCB3A9EE07C0AB 011FEC0F80806D15006F5A6D143E6DEBE07C6DEBFFFC6D6C13F0021F5B020190C7FC2A4C 7ECB34>II119 D121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ft cmtt10 10 66 /Ft 66 122 df<010F133C90381F807EA8013F13FE4A5AA4007FB612F0B712F8A4003F15 F03A007E01F800A5EBFE0301FC5BA6003FB612F0B712F8A46C15F03A01F807E000A30003 130F01F05BA86C486C5A25337DB22C>35 DI<143814FC13011303EB07F8EB0FF0EB1FC0EB3F80EB7F0013FE 485A5B485A12075B485AA2485AA2123F90C7FCA25A127EA312FE5AAC7E127EA3127F7EA2 7F121FA26C7EA26C7E7F12036C7E7F6C7E137FEB3F80EB1FC0EB0FF0EB07F8EB03FC1301 13001438164272B92C>40 D<127012FC7E7E6C7E6C7EEA0FE06C7E6C7E6C7E6C7E137E7F 1480131FEB0FC0A2EB07E0A214F01303A214F81301A314FC1300AC130114F8A3130314F0 A2130714E0A2EB0FC0A2EB1F80133F1400137E13FE485A485A485A485AEA3FC0485A48C7 FC5A5A1270164279B92C>I<147814FCAF007FB612F0B712F8A46C15F0C700FCC7FCAF14 7825267DAB2C>43 DI<007FB6FCB71280A46C 150021067B9B2C>I<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A0A6F892C>I<1507ED0F 80151FA2153F16005D157E15FE5D14015D14035DA214075D140F5D141F5D143F92C7FC5C 147E14FE5CA213015C13035C13075C130F5C131F5CA2133F91C8FC5B137E13FE5B12015B 12035B12075BA2120F5B121F5B123F90C9FC5A127E12FE5AA25A127821417BB92C>II<1307497EA2131FA2133F137F13FF5A5A 127FB5FC13DF139FEA7C1F1200B3AE007FB512E0A2B612F06C14E0A21C3477B32C>IIII<000FB512FE4880A35D0180 C8FCADEB83FE90389FFF8090B512E015F8819038FC03FEEBF00001C0137F49EB3F8090C7 121F6C15C0C8120FA2ED07E0A41210127C12FE150F16C05A6C141F007EEC3F80007FEC7F 006C6C5B6D485A391FF00FFC6CB55A6C5C000114C06C6C90C7FCEB0FF823347CB22C>I< EB07FC90383FFF8090B512E0000314F84880390FFC07FE391FF001FF9038C0007F4848EB 3F8090C7121F4815C0007E140FA56CEC1F80A26C6CEB3F006D5B390FF001FE3903FC07F8 6CB55A6C6C13C0D907FCC7FC90387FFFC048B512F03903FC07F8390FF001FE391FC0007F 497F48C7EA1F80007EEC0FC0A248EC07E0A7007EEC0FC0A2007F141F6C6CEB3F806C6CEB 7F009038F001FF390FFC07FE6CB55A6C5CC614E0013F1380D907FCC7FC23357CB32C>56 D<121EEA7F80A2EAFFC0A4EA7F80A2EA1E00C7FCB0121EEA7F80A2EAFFC0A4EA7F80A2EA 1E000A246FA32C>58 DI<147F903803FFE0010F7F013F7F497F9038FF80FE3901FE007FD803 F87F4848EB1F809038E00FCF390FC03FFF494813C0001F90B5FCEA3F01393E03F87F9138 F03FE0397E07E01F397C0FC00FEC8007A2EAFC1F00F8EB0003A900FCEB8007D87C0F14C0 A2ECC00F3A7E07E01F803A3E03F03F006E5A393F01FFFED81F805B000F6D5A6D6C5A3907 E00FC09039F00003C06C6CEB07E0D801FE131F3900FF807F6DB512C06D1480010FEBFE00 010313F89038007F8023337CB22C>64 D<14FE497EA4497F14EFA301077FA214C7A3010F 7FA31483011F7FA490383F01F8A590387E00FCA401FE7F90B5FCA34880A29038F8003FA3 4848EB1F80A4000715C049130FD87FFEEBFFFC6D5AB514FE6C15FC497E27337EB22C>I< 007FB512E015F8B612FE6C8016C03903F0003FED0FE0ED07F01503A2ED01F8A6ED03F0A2 1507ED0FE0ED1FC0EDFF8090B612005D5D15FF16C09039F0001FE0ED07F0ED03F81501ED 00FCA216FE167EA616FE16FC1501ED03F8150FED3FF0007FB612E016C0B712806CECFE00 15F027337FB22C>I<027F1370903903FFE0F8010F13F9013F13FD4913FFEBFF813901FE 007F4848131FD807F0130F491307120F491303485A150148C7FCA25A007EEC00F01600A2 12FE5AAB7E127EA3007F15F06CEC01F8A26C7EA26C6C13036D14F012076DEB07E0D803FC 131F6C6CEB3FC03A00FF80FF806DB512006D5B010F5B010313E0D9007FC7FC25357DB32C >I<007FB5FCB612C015F0816C803907E003FEEC00FFED7F80153FED1FC0ED0FE0A21507 16F0150316F81501A4ED00FCACED01F8A3150316F0A2150716E0150FED1FC0153FED7F80 EDFF00EC03FE007FB55AB65A5D15C06C91C7FC26337EB22C>I<007FB612F016F8B7FC7E A23903F00001A7ED00F01600A4EC01E04A7EA490B5FCA5EBF003A46E5A91C8FCA5163C16 7EA8007FB612FEA2B7FC7E16FC27337EB22C>I<007FB612F8B712FCA37ED803F0C7FCA7 16781600A515F04A7EA490B5FCA5EBF001A46E5A92C7FCAD387FFFE0B5FC805C7E26337E B22C>I<903901FC038090390FFF87C04913EF017F13FF90B6FC4813073803FC01497E48 48137F4848133F49131F121F5B003F140F90C7FCA2127EED078092C7FCA212FE5AA89138 03FFF84A13FCA27E007E6D13F89138000FC0A36C141FA27F121F6D133F120F6D137F6C7E 6C6C13FF6D5A3801FF076C90B5FC6D13EF011F13CF6DEB0780D901FCC7FC26357DB32C> II<007FB512F8B612FCA36C14F839000F C000B3B3A5007FB512F8B612FCA36C14F81E3379B22C>I<387FFFE0B57EA36C5BD803F0 C8FCB3AE16F0ED01F8A8007FB6FCB7FCA36C15F025337DB22C>76 DIII<007FB512C015F8B67E6C14FF16802603F00013C0153FED0FE0ED07F0A21503 16F81501A6150316F01507A2ED0FE0ED3FC015FF90B61280160015FC5D15C001F0C8FCB0 387FFF80A2B57E6C5BA225337EB22C>II<387FFFFCB67E15E015F86C803907 E007FE1401EC007F6F7E151FA26F7EA64B5AA2153F4BC7FCEC01FE140790B55A5D15E081 819038E007FC14016E7E157F81A81606EE1F80A5D87FFEEB1FBFB5ECFF006F5A15076C48 5CC912F029347EB22C>I<90380FF00790397FFE0F8048B512CF000714FF5A381FF00F38 3FC003497E48C7127F127E00FE143F5A151FA46CEC0F00007E91C7FC127F7FEA3FE0EA1F F8380FFFC014FC0003EBFF806C14F0D8003F7F01077F9038003FFEEC03FF02001380153F ED1FC0150F16E0A20078140712FCA56CEC0FC0A26CEC1F806D133F01E0EB7F009038FC01 FE90B5FC5D00F914F0D8F83F13C0267003FEC7FC23357CB32C>I<007FB612FCB712FEA4 3AFC007E007EA70078153CC71400B3AF90383FFFFCA2497F6D5BA227337EB22C>I<3B7F FF803FFFC0B56C4813E0A36C496C13C03B03F00001F800B3AF6D130300015DA26D130700 005D6D130F017F495A6D6C485AECE0FF6DB5C7FC6D5B010313F86D5B9038003F802B3480 B22C>II<3A3FFF03FFE04A13F04813876C13076E13E03A01F800FE007F0000495A13FE01 7E5BEB7F03013F5B1487011F5B14CF010F5B14FF6D5BA26D90C7FCA26D5AA26D5AA2497E A2497EA2497F81EB0FCF81EB1FC7EC87F0EB3F83EC03F8EB7F01017E7FEBFE00497F0001 147E49137F000380491480151FD87FFEEBFFFC5CB514FED87FFE14FC8027337EB22C>88 D<003FB612C04815E0A4007EC7EA1FC01680153FED7F00157E15FE4A5A003C5CC712034A 5A5D140F4A5A5D143F4AC7FC147E14FE5C495A13035C495A130F5C131F495A91C8FC5B13 FE5B12014848EB03C049EB07E01207485A5B121F485A90C7FC5AB7FCA46C15C023337CB2 2C>90 D<007FB6FCB71280A46C150021067B7D2C>95 D97 DI<903803FFC0011F13FC017F7F 48B5FC48803907FC007FEA0FF049133E4848131C484890C7FC90C9FC5A127EA25AA8127E A2127F6C140F6DEB1F806C7E6C6C133F6DEB7F003907FC01FF6CB55A6C5C6C6C5B011F13 E0D903FEC7FC21247AA32C>IIIIIII<140FEC1F80EC3F C0A4EC1F80EC0F0091C7FCA848B512804814C0A37EC7120FB3B3A2141F1580007C133F15 0000FE5BEB01FEB55A6C5B5C6C5B000790C7FC1A467CB32C>II<387FFFE0B57EA37EEA00 03B3B3A5007FB61280B712C0A36C158022337BB22C>I<3A7F81F003E09039CFFC1FF83A FFDFFE3FFCD87FFF13FF91B57E3A07FE1FFC3E01FCEBF83F9039F00FE01FA201E013C0A3 01C01380B33B7FFC3FF87FF0027F13FFD8FFFE6D13F8D87FFC4913F0023F137F2D2481A3 2C>I<397FF00FE039FFF87FFC9038F9FFFE01FB7F6CB6FC00019038F03F80ECC01F0280 7FEC000F5B5BA25BB3267FFFE0B5FCB500F11480A36C01E0140029247FA32C>II< 397FF01FC039FFF8FFF801FB13FE90B6FC6C158000019038E03FC09138801FE091380007 F049130349EB01F816FC491300A216FE167EA816FE6D14FCA2ED01F86D1303ED07F06D13 0F9138801FE09138E07FC091B51280160001FB5B01F813F0EC1F8091C8FCAD387FFFE0B5 7EA36C5B27367FA32C>I114 D<90383FF87048B512F8120F5A5A387FC00F387E00034813015AA36CEB00 F0007F140013E06CB47E6C13FC6CEBFF80000114E0D8003F13F8010113FCEB0007EC00FE 0078147F00FC143F151F7EA26C143F6D133E6D13FE9038F003FC90B5FC15F815E000F814 8039701FFC0020247AA32C>I<131E133FA9007FB6FCB71280A36C1500D8003FC8FCB1ED 03C0ED07E0A5EC800F011FEB1FC0ECE03F6DB512806D14006D5B6D13F89038003FC0232E 7EAD2C>I<3A7FF003FF80486C487FA3007F7F0001EB000FB3A3151FA2153F6D137F3900 FE01FF90B7FC6D15807F6D13CF902603FE07130029247FA32C>I<3A7FFF01FFFCB514FE 148314016C15FC3A03E0000F80A26D131F00011500A26D5B0000143EA26D137E017C137C A2017E13FC013E5BA2EB3F01011F5BA21483010F5BA214C701075BA214EF01035BA214FF 6D90C7FCA26D5A147C27247EA32C>I I<3A3FFF03FFF048018713F8A36C010313F03A00FC007E005D90387E01F8013F5BEB1F83 EC87E090380FCFC0903807EF80EB03FF6D90C7FC5C6D5A147C14FE130180903803EF8090 3807CFC0EB0FC7EC83E090381F01F0013F7FEB7E00017C137C49137E0001803A7FFF01FF FC1483B514FE6C15FC140127247EA32C>I<3A7FFF01FFFCB514FE148314016C15FC3A03 E0000F806C7E151F6D140012005D6D133E137C017E137E013E137CA2013F13FC6D5BA2EB 0F815DA2EB07C1ECC3E0A2EB03E35DEB01E714F75DEB00FFA292C7FC80A2143EA2147E14 7CA214FC5CA21301001C5BEA3E03387F07E0130F495AEBFF806C90C8FC5B6C5AEA07E027 367EA32C>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fu cmsy10 10 4 /Fu 4 104 df<007FB81280B912C0A26C17803204799641>0 D15 D 102 D<127CEAFFC0EA07F0EA01FCEA007E7F6D7EA26D7EB3A86D7EA213036D7E6D7E147E EC1FF0EC07F8EC1FF0EC7E0014F8495A495A1307A2495AB3A8495AA249C7FC137E485AEA 07F0EAFFC0007CC8FC1D537ABD2A>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fv cmr10 10 81 /Fv 81 128 df11 DIIII<14FF010713C090380F83F090383E00F849137C497F153F0001 158049131F000315C0A61680153F1600A2157E5D4A5AEC07E000FFEB3F80147FEC07E000 03EB01F06E7E157C81811680ED0FC0A2ED07E0A216F0A21503A216F8A816F0A2ECF007D9 F1F813E0A2ED0FC016803A07F0F01F0000FFEBC03EEC707CEC3FF0C7EA0FC0253C7EBA2A >25 D<121C127E127FEAFF80A213C0127FA2121C1200A4EA0180A3EA0300A312065AA25A 5A12200A1979B917>39 D<146014E0EB01C0EB0380EB0700130E5B133C13385B13F05B12 01485AA2485AA348C7FCA25A121EA2123EA2123CA2127CA5127812F8B01278127CA5123C A2123EA2121EA2121F7EA26C7EA36C7EA26C7E12007F13707F133C131C7F7FEB0380EB01 C0EB00E01460135278BD20>I<7E7E7E12707E7E7E120F7E6C7E7F12017F6C7EA21378A3 7FA2133E131EA2131FA27FA21480A5130714C0B01480130FA51400A25BA2131EA2133E13 3CA25BA35BA2485A5B12035B48C7FC5A120E5A5A5A5A5A5A12527BBD20>I<15301578B3 A6007FB812F8B912FCA26C17F8C80078C8FCB3A6153036367BAF41>43 D<121C127E127FEAFF80A213C0127FA2121C1200A4EA0180A3EA0300A312065AA25A5A12 200A19798817>II<121C123E127FEAFF80A3EA7F00123E121C09 09798817>I<150C151EA2153E153CA2157C1578A215F815F0A2140115E0A2140315C0A2 14071580A2140F15005C141EA2143E143CA2147C1478A214F85CA213015CA213035CA213 075CA2130F91C7FCA25B131EA2133E133CA2137C1378A213F85BA212015B12035BA21207 5BA2120F90C8FCA25A121EA2123E123CA2127C1278A212F85AA212601F537BBD2A>II<497E1307 130F133FEA01FFB5FC13DFEAFE1F1200B3B3A7497E007FB512E0A31B3779B62A>III<1570A215F01401A214031407A2140F141F14 1B1433147314E314C31301EB038314031307130E130C131C13381330137013E013C0EA01 80120313001206120E120C5A123812305A12E0B712F8A3C73803F000AB4A7E0103B512F0 A325387EB72A>I<0006140CD80780133C9038F003F890B55A5D5D5D92C7FC14FC38067F E090C9FCABEB07F8EB3FFF9038F80F803907C003C090380001F000066D7E1204C8127C15 7EA281A31680A3123C127EB4FCA316005A485C0060147EA26C5C00385C00181301000E49 5A6C495A3903E03F806CB5C7FC38007FFCEB1FE021387CB62A>II<12301238123E003FB612E0A316C048158016000070C71203006014065DA25D48 5C5DA2C85A4A5A4AC7FCA214065CA25C143814301470A25C1301A213035C1307A3130FA2 495AA4133FA5137FA86DC8FC131E233A7BB82A>III< 121C123E127FEAFF80A3EA7F00123E121CC7FCB2121C123E127FEAFF80A3EA7F00123E12 1C092479A317>I<121C123E127FEAFF80A3EA7F00123E121CC7FCB2121C127E127F5A13 80A2127FA2121D1201A4EA0300A41206A25AA25A5AA21220093479A317>I63 D<1538A3157CA315FEA24A7EA34A7F153FA202077FEC061FA2020C7F150FA24A6C7EA34A 6C7EA34A6C7EA34A6C7EA34948137FA201038191C7123FA249B67EA3010EC7EA1FE0010C 140FA249811607A2496E7EA3496E7EA301E06E7E1201486C81D80FFC02031380B56C017F 13FEA3373B7DBA3E>65 DI<913A01FF800180020F13E0027FEBF803903A01FF80 7E07903A03FC000F0FD90FF0EB038FD91FC0EB01DF4948EB007F49C8123F13FE4848151F 4848150F1207491507120F491503121FA2485A1701127FA25B94C7FC12FFAB127FA26DED 0180A2123FA26C7E1703000F17007F00075E6D150612036C6C5D6C6C5D017F15386D6C5C 6D6C5CD90FF0495AD903FCEB0780902701FF803EC7FC9039007FFFFC020F13F002011380 313B7BB93C>IIIIIII75 DIIIII82 DI<003FB812E0A3903AC003FE001F273E0001FC1303 48EE01F00078160000701770A300601730A400E01738481718A4C71600B3B0EC07FF011F B612C0A335397DB83C>II87 D<267FFFFE90381FFFFCA3C601F001071380D93FC0D901FCC7FCEE00F0 6D6C5C5F6D6C495A6D6C130394C8FC6D6C13066D6C130E160C6D6C5B6E1338ED80306E6C 5A021F13E06F5A91380FF180EC07F303FBC9FCEC03FE1401A26E7E81828215FFEDDFE091 38018FF01403ED07F891380603FC140E91380C01FEEC180002387F02306D7E4A133F02E0 804A6D7E4948130F01038191C76C7E01061403010E81010C6E7E011C1400013C8101FE82 D807FF02037FB500E0011FEBFF80A339397EB83E>II<003FB7FCA301FCC75A01C0495A5B003EC7485A003C14075E00384A5A007814 1F00705D153F5E00604AC7FC5D5D4A5AA2C7485A14075D4A5A141F5D4A5AA24AC8FC5C5C 495AA2495A13075C4948EB0180131F5C495AA249C7FC4914035B485A12035B0007ED0700 5B48485C001F5D495C48485C4B5A48C7120FB8FCA329397BB833>II 93 D97 DIIII<147E903803FF80903807C1C090380F07E0011E13 F0EB3E0F137C13FCEC07E09038F803C0000190C7FCADB512FCA3D801F8C7FCB3AB487E38 7FFFF8A31C3B7FBA19>I<90390FF003F090393FFC1FF89039F81F7C7C3901F00FE03A03 E007C0383A07C003E010160048486C7EA2001F80A6000F5CA26C6C485AA26C6C485A6C6C 485A486C48C7FC38063FFCEB0FF0000EC9FCA4120FA26C7E90B512C06C14F86C14FE6CEC FF80000315C03A0F80007FE0001EC7120F003EEC03F048140116F8481400A5007CEC01F0 A26CEC03E06CEC07C06C6CEB0F80D807E0EB3F003901FC01FC39007FFFF0010790C7FC26 377EA42A>IIIII< EA03F012FFA3120F1203B3B3AD487EB512C0A3123A7EB917>I<2703F00FF0EB1FE000FF D93FFCEB7FF8913AF03E01E07C903BF1C01F03803E3C0FF3000F86001FD803F602CC1480 0307140F01FC02F814C0495CA3495CB3A4486C496CEB1FE0B500C1B50083B5FCA340257E A445>I<3903F00FF000FFEB3FFCECF03E9038F1C01F3A0FF3000F80D803F680150701FC 805BA35BB3A4486C497EB500C1B51280A329257EA42E>II<3903F01F E000FFEB7FF89038F1E07E9038F3801F3A07F6000F80D803FCEB07C049EB03E016F049EB 01F816FC150016FEA3167E167FA8167E16FEA216FCA2ED01F8A26DEB03F016E06DEB07C0 01F6EB0F8001F3EB1F009038F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A328357E A42E>II<3807E01F00FFEB7FC0ECE3E09038E183F0380FE307EA03E6A29038EC 03E0EC008001F81300A35BB3A3487EB512F0A31C257EA421>II<1318A51338A31378A313F8 120112031207001FB5FCB6FCA2D801F8C7FCB215C0A90000EB018013FC137C90383E0300 EB1F06EB0FFCEB01F81A347FB220>IIIIII<003FB512FCA290388001F8393E0003F0003C1307003814E00030EB0F C00070131F15800060EB3F005C14FE5C495AEA00035C495A130F495A5C49C7FC49130613 7E5B1201485A49130E485A000F140C49131C485A003F143C90C7127C007EEB03FCB6FCA2 1F247EA325>III<001C131C003E133E 007F137F39FF80FF80A3397F007F00003E133E001C131C190978B72A>127 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fw cmr12 12 17 /Fw 17 117 df<121E123FEA7F80EAFFC0A4EA7F80EA3F00121E0A0A78891B>46 D<16C04B7EA34B7EA34B7EA34B7EA3ED19FEA2ED39FF1530A203707FED607FA203C07F16 3FA2DA01807F161FA24A486C7EA302066D7EA2020E80020C1303A2021C8002181301A24A 8082A24A81177FA291B77EA3D90180C7EA1FE0A201038291C8120FA2498201061507A249 821703A249821701A2496F7EA2137801F883486C83D80FFF03037FB500E0027FEBFFC0A3 42467DC549>65 D67 D69 D77 D80 D97 D101 D104 DI107 DI<3903F801FE00 FF90380FFFC091381E03E091383001F00007496C7E000349137C2601F980137E01FBC7FC 01FE143E163F5BA35BB3A9486CEC7F80B539F01FFFFEA32F2C7DAB36>110 DI<3903F007F000FFEB1FF8EC383CEC607E 0007EBC0FF3803F1801201EBF30001F6137E153C150013FCA45BB3A7EA03FEB512FCA320 2C7DAB26>114 D<90383FE0183801FFFC3907C01E38390F000378001CEB01F848130015 785A153812F01518A37E7E127ED87F801300EA3FF0EBFF806C13F8000713FE6CEBFF806C 14C0D8003F13E0010313F09038001FF814030040EB00FC00C0147C157E153E7E151EA27E A2151C7E153C6C14386C147000FB14E039F18001C039E0F00F8039C07FFE00EB0FF01F2E 7DAC26>I<130CA6131CA4133CA2137CA213FC120112031207001FB512F0B6FCA2D800FC C7FCB3A4150CAA017C1318137EA2013E13307F90380F8060903807C0C0903803FF809038 007F001E3E7EBC26>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fx cmsy10 12 1 /Fx 1 4 df<147014F8A81470007815F0007C1401B4EC07F8D87F80EB0FF0D83FE0EB3F E0D80FF0EB7F80D803F8EBFE003900FE73F890383F77E090380FFF80D903FEC7FCEB00F8 EB03FE90380FFF8090383F77E09038FE73F83903F870FED80FF0EB7F80D83FE0EB3FE0D8 7F80EB0FF0D8FF00EB07F8007CEC01F000781400C7140014F8A81470252B7AAD32>3 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fy cmr17 17.28 20 /Fy 20 119 df67 D70 D78 D83 D<003FBC12F8A49126C00003903880000701FCC76C90C8127F01E0190F491907 4848F103FC90C81701007E1A00007C1B7CA300781B3CA400701B1CA600F01B1E481B0EA7 C91800B3B3B3A54C7FA2041F13F04AB8FCA457627CE160>I97 D<4AB47E020F13F091383F007C02FC130FD903F0EB03C04948EB00E0 D90F80147049C87E4981137E49811201484881171F4848ED7F80000F16FF495C121FA25B 003F6F1300A2007F167E94C7FCA25BA212FFAC127FA27FA2123FA36C7EEF01C0120F7F00 07EE03807F0003EE07006C7E0000160E7F017F5D6D5DD90F805CD907E05C6D6CEB03C0D9 00FC010FC7FC023F137E91380FFFF80201138032417CBF3A>99 D<181EEF3FFEEE07FFA4 EE000F1703A21701B3AAED7FC0913807FFF891383FC03E91397E000781D901F8EB01C1D9 07E0EB00E1494814314948141949C8120D017E150F49150700011603485A1701485A120F 5B121FA2485AA3127FA25BA212FFAC127FA37F123FA3121F7F120FA26C7E17036C7E0001 16076C6C150F017E150D17196DED39FFD90F8014716D6CD901E113C0D903F0D90381EBFF 80D900FCEB0F01023F137C91380FFFF00201018091C7FC41657CE349>III104 D<133C13FF487FA2487FA46C5BA26C90C7FC133C90C8FCB3A2EB03C0EA07FF127FA41201 EA007FA2133FB3B3AC497E497EB612E0A41B5F7DDE23>I108 DI111 DI<9039078003F8D807FFEB0FFFB590383C 0780037013C09238C01FE0DA818013F00001903883003F38007F86A2EB3F8CEE1FE00298 EB0FC0EE030002B090C7FCA414E0A55CB3B1497EEBFFF8B612FCA42C3F7CBE33>114 D<1438A71478A514F8A31301A21303A21307A2130F131F133F137F13FF000390B6FC120F B8FCA2260007F8C8FCB3AE17E0AE010315C06E1301A21301EE03806D7E1700027F5B6E13 0E91381FC01C913807F078913801FFF09138003FC02B597FD733>116 DI I E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 1 1 1 0 bop 512 349 a Fy(The)43 b(Structure)h(of)f(a)g(F)-11 b(orth)43 b(Nativ)l(e)h(Co)t(de)g(Compiler)3267 297 y Fx(\003)1118 589 y Fw(M.)33 b(An)m(ton)g(Ertl)237 b(Christian)34 b(Pirk)m(er)1332 706 y Fv(Institut)29 b(f)r(\177)-44 b(ur)27 b(Computersprac)n(hen)1369 798 y(T)-7 b(ec)n(hnisc)n(he)27 b(Univ)n(ersit\177)-42 b(at)27 b(Wien)1278 891 y(Argen)n (tinierstra\031e)e(8,)i(A-1040)f(Wien)1020 984 y Fu(f)p Ft(anton,pirky)p Fu(g)p Ft(@mi)o(ps.)o(co)o(mp)o(lan)o(g.)o(tuw)o(ie)o (n.)o(ac.)o(at)757 1076 y(http://www.comp)o(la)o(ng.)o(tu)o(wie)o(n.)o (ac.)o(at)o(/p)o(roj)o(ec)o(ts/)o(fo)o(rt)o(h.h)o(tm)o(l)1437 1169 y Fv(T)-7 b(el.:)37 b(\(+43-1\))26 b(58801)f(4474)1454 1261 y(F)-7 b(ax.:)37 b(\(+43-1\))26 b(505)g(78)h(38)0 1587 y Fs(Abstract)0 1781 y Fv(W)-7 b(riting)27 b(a)g(sophisticated)g (F)-7 b(orth)27 b(nativ)n(e)g(co)r(de)g(compiler)0 1880 y(p)r(oses)d(some)g(tasks)g(that)h(are)e(not)i(discussed)f(in)h (compiler)0 1980 y(text)k(b)r(o)r(oks.)41 b(Some)29 b(of)g(these)g (tasks)f(arise)g(from)g(sp)r(eci\014c)0 2080 y(language)h(features,)h (others)g(from)g(the)g(requiremen)n(t)g(for)0 2179 y(v)n(ery)g(fast)i (compilation)f(to)h(main)n(tain)f(in)n(teractivit)n(y)-7 b(.)48 b(In)0 2279 y(this)25 b(pap)r(er)f(w)n(e)g(describ)r(e)g(some)g (of)g(the)h(more)f(in)n(teresting)0 2378 y(data)h(structures)g(and)g (algorithms)f(used)h(in)h(the)g(RAFTS)0 2478 y(protot)n(yp)r(e.)0 2787 y Fs(1)135 b(In)l(tro)t(duction)0 2981 y Fv(In)44 b([Ert92)o(,)g(EP96)n(])g(w)n(e)g(discussed)g(man)n(y)g(engineering)0 3080 y(asp)r(ects)i(of)h(a)f(RAFTS)i(compiler)e(only)g(sup)r (er\014cially)-7 b(,)0 3180 y(if)48 b(at)g(all.)97 b(In)48 b(the)g(mean)n(time)g(w)n(e)f(ha)n(v)n(e)g(also)g(made)0 3280 y(some)21 b(c)n(hanges)f(in)i(preparation)e(for)h(in)n(terpro)r (cedural)f(op-)0 3379 y(timizations.)35 b(In)22 b(this)h(pap)r(er)f(w)n (e)g(discuss)f(the)i(implemen-)0 3479 y(tation)32 b(issues)f(of)h(our)g (RAFTS)g(protot)n(yp)r(e)g(compiler)f(in)0 3578 y(more)c(depth.)83 3685 y(Man)n(y)e(of)g(the)g(issues)g(discussed)g(here)g(are)f(due)h(to) h(sp)r(e-)0 3784 y(ci\014c)i(prop)r(erties)e(of)i(the)g(language)e(F)-7 b(orth:)0 3993 y Fr(In)m(teractivit)m(y)46 b Fv(demands)77 b(v)n(ery)f(fast)i(compilation.)166 4092 y(This)31 b(led)h(to)f(the)h (use)f(of)g(a)g(fast)g(instruction)g(selec-)166 4192 y(tion)36 b(tec)n(hnique)g(\(Section)g(4.2\),)h(an)f(impro)n(v)n(ed)e (in-)166 4292 y(struction)f(sc)n(heduler)f(\(Section)i(4.3\),)g(simple) f(lo)r(cal)166 4391 y(register)d(allo)r(cation)h(\(Section)h(4.4\),)g (and)f(the)i(in)n(te-)166 4491 y(gration)39 b(of)h(all)f(these)h (phases)g(in)n(to)g(a)f(few)h(passes)166 4590 y(\(Section)28 b(4.6\).)0 4782 y Fr(High)k(call)i(frequency)42 b Fv(requires)29 b(inlining)i(and/or)d(in-)166 4882 y(terpro)r(cedural)h(register)g (allo)r(cation)h(for)g(go)r(o)r(d)g(p)r(er-)166 4982 y(formance.)35 b(This)25 b(means)f(the)i(compiler)e(should)g(not)166 5081 y(generate)j(co)r(de)h(for)g(a)g(w)n(ord)f(when)i(its)f(source)g (co)r(de)166 5181 y(is)g(read.)36 b(Instead,)28 b(it)g(should)g(w)n (ait)f(as)h(long)f(as)g(p)r(os-)166 5280 y(sible,)47 b(to)42 b(mak)n(e)g(use)h(of)g(information)f(ab)r(out)h(the)166 5380 y(w)n(ord's)35 b(callers.)60 b(This)35 b(leads)h(to)f(an)h(in)n (termediate)166 5480 y(represen)n(tation)j(for)i(w)n(ords)e(that)i(w)n (ere)f(not)h(com-)166 5579 y(piled)28 b(y)n(et)f(\(Section)h(3\).)p 0 5679 740 4 v 91 5732 a Fq(\003)127 5756 y Fp(This)k(w)n(ork)f(is)h (supp)r(orted)h(b)n(y)f(the)h(FWF,)f(researc)n(h)h(pro)t(ject)0 5835 y(P11231-MA)-6 b(T.)1931 1587 y Fr(Mixing)33 b(compilation)g(and)g (execution)42 b Fv(means)2097 1686 y(that)f(the)g(compiler)f(cannot)g (w)n(ait)g(for)g(the)h(whole)2097 1786 y(program)34 b(to)h(b)r(e)h (read,)h(and)e(generate)g(co)r(de)g(then,)2097 1886 y(but)25 b(ma)n(y)e(ha)n(v)n(e)g(to)h(execute)g(a)g(part)f(of)h(the)h(program) 2097 1985 y(b)r(efore)37 b(ev)n(erything)e(is)h(read.)63 b(T)-7 b(ogether)35 b(with)i(the)2097 2085 y(requiremen)n(t)24 b(to)h(compile)f(as)g(late)g(as)g(p)r(ossible,)h(this)2097 2185 y(has)43 b(led)h(to)f(implemen)n(ting)h(co)r(de)f(generation)f(on) 2097 2284 y Ft(EXECUTE)25 b Fv(\(Section)j(3.2\).)1931 2456 y Fr(Strati\014cation)45 b Fv(of)54 b(de\014nitions)h(\(i.e.,)61 b(de\014ne)55 b(b)r(efore)2097 2555 y(use\))23 b(is)f(required)f(in)h (F)-7 b(orth)22 b(and)g(giv)n(es)f(the)h(compiler)2097 2655 y(opp)r(ortunities)d(for)f(in)n(terpro)r(cedural)f(optimizations) 2097 2755 y(whose)34 b(exploitation)f(is)h(more)f(di\016cult)i(or)e (imp)r(os-)2097 2854 y(sible)26 b(in)h(non-strati\014ed)e(languages)f (and)i(languages)2097 2954 y(with)31 b(separate)f(compilation.)45 b(W)-7 b(e)31 b(do)f(not)h(discuss)2097 3054 y(these)22 b(optimizations)f(here,)h(but)g(w)n(e)f(ha)n(v)n(e)g(prepared)2097 3153 y(for)27 b(them)i(\(Section)e(3\).)2014 3341 y(Instead)h(of)g(rep) r(eating)g(the)h(Motiv)-5 b(ation)28 b(and)g(Related)1931 3441 y(W)-7 b(orks)22 b(sections)g(from)h([EP96)n(],)h(w)n(e)e(suggest) g(reading)g(it.)3742 3411 y Fo(1)1931 3723 y Fs(2)135 b(Compilation)47 b(actions)1931 3907 y Fv(In)j([EP96)n(],)55 b(w)n(e)49 b(discussed)g(v)-5 b(arious)48 b(alternativ)n(es)g(for)1931 4007 y(dealing)19 b(with)i(the)f(problem)f(that)h(nativ)n(e)f(co)r(de)h (compilers)1931 4107 y(require)i(an)h(un)n(usual)f(and)h(non)n(uniform) g(implemen)n(tation)1931 4206 y(of)34 b(compilation.)53 b(A)n(t)34 b(that)g(time,)h(our)e(protot)n(yp)r(e)f(com-)1931 4306 y(piler)h(used)h(a)f(com)n(bination)g(of)g(the)h Fn(wor)l(d)t(list)43 b Fv(approac)n(h)1931 4406 y(\(i.e.,)g(a)d(w)n (ordlist)e(for)h(the)h(compilation)f(action)h(and)f(a)1931 4505 y(w)n(ordlist)21 b(for)g(the)h(in)n(terpretation)f(action\))g(and) h(the)g Fn(intel-)1931 4605 y(ligent)28 b Fm(COMPILE,)36 b Fv(approac)n(h)23 b(\(i.e.,)k Ft(COMPILE,)21 b Fv(p)r(erforms)1931 4704 y(a)30 b(sp)r(ecial)h(compilation)f(action)g(for)g(eac)n(h)g (execution)g(to-)1931 4804 y(k)n(en\),)g(where)f(the)h(w)n(ordlist)f (part)g(caused)g(non-standard)1931 4904 y(b)r(eha)n(viour.)2014 5005 y(In)21 b(the)g(mean)n(time)g(w)n(e)f(ha)n(v)n(e)g(switc)n(hed)g (to)h(a)f(pure)h(in)n(tel-)1931 5104 y(ligen)n(t)34 b Ft(COMPILE,)d Fv(approac)n(h.)54 b(The)34 b(c)n(hallenge)e(w)n(as)h (do-)1931 5204 y(ing)21 b(this)h(e\016cien)n(tly)f(while)g(main)n (taining)f(the)i(in)n(tegration)1931 5304 y(with)28 b(the)g(Gforth)g (threaded)f(co)r(de)h(system.)2014 5405 y(Threaded)43 b(co)r(de)f(systems)h(pro)n(vide)f(information)g(in)1931 5504 y(the)35 b(execution)f(tok)n(en)g(\(XT\))i(on)e(ho)n(w)g(to)g Ft(EXECUTE)e Fv(the)1931 5604 y(de\014nition)i(represen)n(ted)e(b)n(y)h (the)g(execution)g(tok)n(en,)h(but)p 1931 5679 V 2024 5732 a Fl(1)2058 5756 y Fp(Our)198 b(pap)r(ers)h(are)f(a)n(v)l(ailable) h(through)1931 5835 y(h)n(ttp://www.complang.tu)n(wien.ac.at/pap)r (ers/.)p %%BeginObject: online-footer gsave initmatrix 0 setgray newpath /Helvetica findfont 9 scalefont setfont 56 53 moveto (Paper and BibTeX entry are available at http://www.complang.tuwien.ac.at/papers/. This paper was published in:) show 56 42 moveto (Euroforth '97 Conference Proceedings, pages 107-116) show 56 31 moveto () show grestore %%EndObject eop %%Page: 2 2 2 1 bop 0 3 1849 4 v 50 109 a Ft(xt-cfa)271 b Fv(co)r(de)28 b(\014eld)50 208 y Ft(xt-defer)183 b Fv(CF)-9 b(A)28 b(for)f(deferred)g(de\014nition)50 308 y Ft(xt-compile)95 b Fv(XT)28 b(of)g(compilation)f(action)50 408 y Ft(...)403 b Fv(other)27 b(\014elds)50 507 y Ft(xt-pfa)271 b Fv(parameter)26 b(\014eld)i(\(b)r(o)r(dy\))p 0 576 V 85 717 a(Figure)f(1:)36 b(Structure)28 b(of)f(a)h(nativ)n(e)f(co)r(de)g(de\014nition)0 984 y(no)g(information)g(on)g(ho)n(w)g(to)h Ft(COMPILE,)c Fv(it.)37 b(The)28 b(reason)0 1083 y(is)38 b(that)g(all)f(XTs)h(are)f Ft(COMPILE,)p Fv(d)d(in)k(a)g(uniform)f(w)n(a)n(y)-7 b(,)0 1183 y(with)28 b Ft(,)p Fv(.)83 1283 y(Nativ)n(e)43 b(co)r(de)f(compilers,)k(on)d(the)g(other)g(hand,)k(of-)0 1383 y(ten)60 b(w)n(an)n(t)e(to)h(do)g(something)g(di\013eren)n(t)g (dep)r(ending)0 1482 y(on)44 b(the)h(XT)g(that)g(is)g Ft(COMPILE,)p Fv(d)1155 1452 y Fo(2)1189 1482 y Fv(;)53 b(e.g.,)c(our)44 b(proto-)0 1582 y(t)n(yp)r(e)d Ft(COMPILE,)p Fv(s)c(the)k(XT)f(of)47 b Ft(+)40 b Fv(with)h(a)f(w)n(ord)g(called)0 1682 y Ft(compile-+)i Fv(\(whic)n(h)k(is)g(ob)n(viously)f (inappropriate)f(for)0 1781 y Ft(COMPILE,)p Fv(ing)24 b(other)j(w)n(ords\).)83 1882 y(One)19 b(solution)h(w)n(ould)f(b)r(e)h (to)g(k)n(eep)f(the)h(data)f(structures)0 1981 y(of)k(the)h(threaded)e (co)r(de)h(system)g(and)g(p)r(erform)g(the)h(di\013er-)0 2081 y(en)n(t)h Ft(COMPILE,)d Fv(actions)i(for)h(di\013eren)n(t)g(XTs)g (b)n(y)g(p)r(erform-)0 2180 y(ing)32 b(a)g(table)h(lo)r(okup)f(in)g Ft(COMPILE,)p Fv(.)49 b(Another)32 b(solution)0 2280 y(is)i(to)h(c)n(hange)e(the)i(data)f(structure)g(for)g(a)g (de\014nition)g(to)0 2380 y(include)29 b(information)e(on)h(the)h (compilation)f(action.)38 b(W)-7 b(e)0 2479 y(c)n(hose)27 b(the)h(latter)f(approac)n(h)e(\(see)j(Fig.)f(1\).)83 2580 y(If)i(the)g(threaded)g(co)r(de)f(system)h(and)f(the)h(nativ)n(e)g (co)r(de)0 2679 y(compiler)37 b(ha)n(v)n(e)g(di\013eren)n(t)h(data)f (structures)g(for)g(de\014ni-)0 2779 y(tions,)30 b(ho)n(w)f(can)h(they) g(w)n(ork)e(together?)43 b(There)29 b(are)g(t)n(w)n(o)0 2879 y(directions)e(to)g(consider:)83 3064 y Fu(\017)41 b Fv(P)n(assing)31 b(the)i(XT)h(of)e(a)h(nativ)n(e)f(co)r(de)h (de\014nition)g(to)166 3164 y(a)40 b(w)n(ord)g(exp)r(ecting)h(a)f (threaded)h(co)r(de)f(XT.)h(This)166 3263 y(presen)n(ts)29 b(no)i(problem,)f(b)r(ecause)g(w)n(e)g(designed)g(the)166 3363 y(data)h(struture)g(of)g(nativ)n(e)g(co)r(de)h(de\014nitions)f(as) g(ex-)166 3462 y(tension)18 b(of)h(the)g(threaded)f(co)r(de)g(data)g (structure)g(\(see)166 3562 y(Fig.)j(1\):)33 b(The)21 b(XT)g(can)f(still)h(b)r(e)g(used)f(as)g(a)h(co)r(de)f(\014eld)166 3662 y(address)26 b(\(CF)-9 b(A\).)83 3831 y Fu(\017)41 b Fv(P)n(assing)32 b(the)j(XT)g(of)f(a)g(threaded)g(co)r(de)g (de\014nition)166 3930 y(to)28 b(a)g(w)n(ord)f(that)h(exp)r(ects)g(a)g (nativ)n(e)g(co)r(de)g(XT)g(\(and)166 4030 y(w)n(an)n(ts)41 b(to)g Ft(COMPILE,)e Fv(it\).)79 b(This)42 b(w)n(ould)f(cause)g(a)166 4129 y(crash,)27 b(and)g(m)n(ust)h(b)r(e)g(a)n(v)n(oided.)83 4315 y(So,)22 b(ho)n(w)e(can)h(w)n(e)g(use)g(threaded)f(co)r(de)h(w)n (ords)f(in)h(nativ)n(e)0 4415 y(co)r(de?)36 b(W)-7 b(e)24 b(decided)g(to)f(create)g(aliases)f(for)i(the)g(threaded)0 4514 y(co)r(de)i(w)n(ords)e(w)n(e)i(use;)g(these)g(aliases)e(ha)n(v)n (e)h(a)g(nativ)n(e)h(co)r(de)0 4614 y(de\014nition)c(structure.)35 b(The)21 b(co)r(de)h(\014eld)g(for)f(suc)n(h)h(an)f(alias)0 4713 y(\(used)g(for)g Ft(EXECUTE)p Fv(\))d(con)n(tains)i Ft(dodefer)p Fv(,)f(the)j Ft(xt-defer)0 4813 y Fv(\014eld)31 b(con)n(tains)g(the)g(CF)-9 b(A)32 b(of)f(the)h(threaded)e(co)r(de)h(w) n(ord,)0 4913 y(and)c(the)h Ft(xt-compile)c Fv(\014eld)k(\(used)g(for)f Ft(COMPILE,)p Fv(,)d(con-)0 5012 y(tains)j(the)h(XT)g(of)34 b Ft(compile-threaded)p Fv(\).)83 5113 y(The)c(default)h(searc)n(h)e (order)g(con)n(tains)h(only)g(w)n(ordlists)0 5212 y(consisting)18 b(only)h(of)f(nativ)n(e)h(co)r(de)g(structured)f(de\014nitions.)p 0 5284 740 4 v 92 5338 a Fl(2)127 5361 y Fp(Note)33 b(that)h(this)f (issue)f(is)g(indep)r(enden)n(t)j(of)d(the)i(question)f(of)0 5440 y(non-default)c(compilation)e(seman)n(tics:)40 b Fk(COMPILE,)30 b Fp(m)n(ust)d(compile)0 5519 y(the)f(execution)h(seman) n(tics)e(giv)n(en)g(b)n(y)h(the)g(XT,)e(not)i(an)n(y)g(other)g(se-)0 5598 y(man)n(tics;)c(nativ)n(e)h(co)r(de)h(compilers)c(just)j(w)n(an)n (t)g(to)g(p)r(erform)d(an)j(XT-)0 5677 y(dep)r(enden)n(t)36 b(action)f(when)g(compiling)e(the)h(XT,)g(b)r(ecause)h(nativ)n(e)0 5756 y(co)r(de)27 b(is)e(not)h(as)g(uniform)e(as)i(threaded)h(co)r(de,) g(and)f(to)h(allo)n(w)e(opti-)0 5835 y(mizations.)1931 83 y Fv(W)-7 b(e)39 b(explicitly)f(create)g(nativ)n(e)f(co)r(de)h (aliases)f(in)i(one)f(of)1931 183 y(these)32 b(w)n(ordlists)e(for)h (all)g(the)h(threaded)f(co)r(de)g(w)n(ords)f(w)n(e)1931 282 y(use.)49 b(This)32 b(is)f(not)h(v)n(ery)f(elegan)n(t,)g(but)i (simple,)g(and)e(has)1931 382 y(further)i(adv)-5 b(an)n(tages:)47 b(In)33 b(particular,)h(w)n(e)f(cannot)f(acci-)1931 482 y(den)n(tially)c(in)n(v)n(ok)n(e)e(a)h(threaded)g(co)r(de)g(w)n(ord)g (that)h(tries)f(to)1931 581 y(compile)h(something)f(with)h Ft(,)p Fv(.)1931 883 y Fs(3)135 b(Dela)l(ying)47 b(co)t(de)d (generation)1931 1074 y Fv(F)-7 b(or)36 b(in)n(terpro)r(cedural)e (register)h(allo)r(cation)g(w)n(e)h(need)g(to)1931 1173 y(compile)22 b(as)f(man)n(y)g(w)n(ords)g(together)g(as)g(p)r(ossible.) 34 b(F)-7 b(or)22 b(in-)1931 1273 y(lining)k(decisions,)f(w)n(e)h(need) g(to)f(kno)n(w)g(ho)n(w)g(often)h(a)g(w)n(ord)1931 1373 y(is)e(called)g(b)r(efore)g(inlining)h(it.)36 b(In)25 b(b)r(oth)f(cases)g(w)n(e)g(ha)n(v)n(e)f(to)1931 1472 y(dela)n(y)k(the)h(co)r(de)f(generation)g(as)f(long)h(as)g(p)r (ossible.)1931 1731 y Fj(3.1)113 b(Linear)58 b(in)m(termediate)e (represen)m(ta-)2187 1848 y(tion)1931 2010 y Fv(Of)20 b(course,)f(w)n(e)g(ha)n(v)n(e)f(to)i(represen)n(t)e(the)h(program)f (in)h(some)1931 2110 y(data)25 b(structure)g(b)r(et)n(w)n(een)h(the)g (time)g(when)g(the)g(program)1931 2210 y(is)d(compiled)g(\(as)f(p)r (erceiv)n(ed)g(b)n(y)h(the)g(user\),)g(and)g(the)g(time)1931 2309 y(when)28 b(the)g(co)r(de)f(is)h(generated)e(for)h(it.)2014 2414 y(An)45 b(ob)n(vious)e(candidate)h(w)n(ould)h(b)r(e)f(the)h(data)f (\015o)n(w)1931 2514 y(graphs)f(that)g(are)g(already)f(used)i(in)g(co)r (de)f(generation)1931 2613 y(for)37 b(basic)g(blo)r(c)n(ks.)66 b(The)37 b(con)n(trol)g(\015o)n(w)f(w)n(ould)h(ha)n(v)n(e)g(to)1931 2713 y(b)r(e)h(added)f(someho)n(w.)65 b(Ho)n(w)n(ev)n(er,)38 b(this)f(represen)n(tation)1931 2812 y(is)e(not)g(only)f(quite)h (space-consuming,)g(it)g(also)f(compli-)1931 2912 y(cates)42 b(co)r(de)g(replicating)g(optimizations)f(lik)n(e)h(inlining:)1931 3012 y(cop)n(ying)37 b(a)g(graph)f(is)h(somewhat)g(complex;)42 b(cop)n(ying)36 b(a)1931 3111 y(con)n(trol-\015o)n(w/data-\015o)n(w)f (graph)j(h)n(ybrid)g(and)h(inserting)1931 3211 y(it)28 b(in)g(another)f(suc)n(h)g(b)r(east)h(w)n(ould)f(b)r(e)h(w)n(orse.)2014 3316 y(A)43 b(linear)e(represen)n(tation)f(of)i(the)h(graph)e(w)n(ould) g(b)r(e)1931 3415 y(nicer.)34 b(A)21 b(stac)n(k-based)e(represen)n (tation)g(is)i(easy)e(to)i(trans-)1931 3515 y(form)26 b(in)n(to)h(a)f(graph,)f(and)i(it)f(is)h(easy)e(to)i(create)e(from)h (the)1931 3614 y(source)31 b(co)r(de.)52 b(So,)33 b(w)n(e)f(settled)h (on)f(a)g(stac)n(k-based)f(co)r(de)1931 3714 y(that)i(is)f(quite)h (close)e(to)h(the)h(source.)50 b(The)33 b(main)f(di\013er-)1931 3814 y(ence)40 b(from)g(source)f(is)h(that)g(the)h(names)e(are)g (resolv)n(ed.)1931 3913 y(Another)24 b(di\013erence)f(is)h(that)g(the)g (program)e(is)h(not)h(repre-)1931 4013 y(sen)n(ted)i(as)g(strings,)f (but)i(as)e(threaded)h(co)r(de;)g(th)n(us,)g(when)1931 4113 y(w)n(e)36 b(\014nally)g(w)n(an)n(t)g(to)g(generate)f(executable)h (co)r(de)g(for)g(a)1931 4212 y(piece)f(of)h(in)n(termediate)f(represen) n(tation,)g(w)n(e)g(just)h(ha)n(v)n(e)1931 4312 y(to)41 b(execute)g(the)h(in)n(termediate)e(represen)n(tation;)46 b(if)c(w)n(e)1931 4411 y(w)n(an)n(t)37 b(to)g(inline)g(a)g(colon)f (de\014nition,)k(w)n(e)d(just)h(ha)n(v)n(e)e(to)1931 4511 y(call)25 b(its)g(in)n(termediate)g(represen)n(tation)f(while)h (compiling)1931 4611 y(its)h(caller)e(\(instead)i(of)f(pro)r(ducing)g (separate)f(co)r(de)h(for)g(it,)1931 4710 y(and)j(generating)e(co)r(de) h(for)g(a)g(call)h(to)f(that)h(co)r(de\).)2014 4815 y(While)43 b(compiling)e(source)g(co)r(de)g(in)n(to)h(the)g(in)n(terme-)1931 4915 y(diate)35 b(represen)n(tation,)g(the)g(compiler)g(already)e (collects)1931 5014 y(data)c(ab)r(out)h(the)g(stac)n(k)e(e\013ects)i (and)f(other)g(information)1931 5114 y(that)j(will)g(b)r(e)g(useful)g (in)g(in)n(terpro)r(cedural)e(register)h(allo-)1931 5214 y(cation)c(and)h(other)f(in)n(terpro)r(cedural)f(optimizations.)1931 5473 y Fj(3.2)113 b(Compile)35 b(on)j Fi(EXECUTE)1931 5635 y Fv(W)-7 b(e)39 b(w)n(an)n(t)e(to)h(generate)f(co)r(de)h(for)g(a) g(de\014nition)g(at)g(the)1931 5735 y(latest)32 b(p)r(ossible)g(momen)n (t,)h(and)e(that)i(momen)n(t)f(is)f(when)1931 5835 y(the)48 b(de\014nition)g(is)f Ft(EXECUTE)p Fv(d)e(\(e.g.,)52 b(b)n(y)47 b(in)n(terpreting)p eop %%Page: 3 3 3 2 bop 0 3 1849 4 v 50 109 a Ft(il-left)271 b Fv(left)28 b(c)n(hild)g(\(or)f(un)n(used\))50 208 y Ft(il-right)227 b Fv(righ)n(t)27 b(c)n(hild)g(\(or)g(un)n(used\))50 308 y Ft(il-op)359 b Fv(no)r(de)28 b(t)n(yp)r(e)f(\(op)r(erator\))50 408 y Ft(il-val)315 b Fv(v)-5 b(alue)27 b(\(of)35 b Ft(I)p 1026 408 27 4 v 31 w(LIT)26 b Fv(no)r(de\))50 507 y Ft(il-reg)315 b Fv(target)27 b(register)50 607 y Ft(il-slabel)183 b Fv(state)27 b(\(for)h(inst.)37 b(selection\))50 707 y Ft(il-nt-insts)95 b Fv(ML)28 b(no)r(des)f(for)g(this)h(IL)f(no)r(de)50 806 y Ft(il-depends)139 b Fv(dep)r(endences)28 b(\(for)f(sc)n (heduling\))p 0 875 1849 4 v 495 1016 a(Figure)g(2:)36 b(IL)28 b(no)r(de)f(\014elds)0 1286 y(the)38 b(w)n(ord\).)65 b(A)n(t)38 b(that)f(momen)n(t,)j(the)e(compiler)f(gener-)0 1386 y(ates)g(co)r(de)f(for)h(the)g Ft(EXECUTE)p Fv(d)e(de\014nition)i (and)g(all)g(the)0 1485 y(de\014nitions)c(that)g(this)g(de\014nition)g (calls)g(statically)f(\(i.e.,)0 1585 y(without)f Ft(EXECUTE)c Fv(etc.\).)45 b(This)30 b(tec)n(hnique)g(of)h(dynamic)0 1684 y(translation)26 b(w)n(as)h(pioneered)g(b)n(y)g([DS84].)83 1787 y(This)41 b(is)g(ac)n(hiev)n(ed)f(b)n(y)h(putting)g(a)g Ft(docodegen)d Fv(co)r(de)0 1886 y(address)27 b(in)h(the)g(co)r(de)g (\014eld)g(\()p Ft(xt-cfa)p Fv(\))f(of)g(all)h(de\014nitions)0 1986 y(for)34 b(whic)n(h)g(no)h(co)r(de)f(has)g(b)r(een)h(generated)e (y)n(et.)58 b(When)0 2085 y(the)31 b(de\014nition)g(is)f Ft(EXECUTE)p Fv(d,)f(this)i(routine)f(is)h(in)n(v)n(ok)n(ed:)0 2185 y(It)38 b(generates)e(co)r(de)i(for)f(the)i(de\014nition)f(\(b)n (y)g(executing)0 2285 y(the)27 b(in)n(termediate)f(represen)n(tation\)) e(and)i(all)g(its)h(descen-)0 2384 y(den)n(ts)36 b(in)g(the)g(static)f (call)h(graph.)60 b(F)-7 b(or)35 b(all)g(de\014nitions,)0 2484 y(for)24 b(whic)n(h)h(it)g(generates)e(co)r(de,)i(it)g(replaces)e (the)i(co)r(de)g(ad-)0 2584 y(dress)35 b Ft(docodegen)d Fv(in)k(the)g(co)r(de)g(\014eld)g(with)g(a)g Ft(docode)p Fv(,)0 2683 y(the)g(co)r(de)e(address)g(for)h(executing)g(nativ)n(e)f (co)r(de)h(de\014ni-)0 2783 y(tions.)48 b(After)31 b(all)g(the)h (necessary)e(co)r(de)h(is)g(generated,)g(it)0 2882 y(\014nally)c (executes)h(the)g(nativ)n(e)f(co)r(de)g(for)g(the)h(de\014nition.)0 3128 y Fj(3.3)112 b(In)m(terpro)s(cedural)37 b(optimizations)0 3286 y Fv(W)-7 b(e)21 b(are)e(curren)n(tly)g(w)n(orking)f(on)i(adding)g (in)n(terpro)r(cedural)0 3385 y(register)25 b(allo)r(cation)g(and)i(in) n(tend)g(to)f(add)g(inlining;)i(since)0 3485 y(w)n(e)23 b(ha)n(v)n(e)g(not)h(completed)g(this)g(w)n(ork,)f(w)n(e)g(do)h(not)g (discuss)0 3585 y(it)k(in)g(depth)g(here.)83 3687 y(These)39 b(optimizations)g(will)h(collect)f(data)g(while)h(the)0 3786 y(linear)23 b(in)n(termediate)g(represen)n(tation)e(is)j(built,)h (and)e(p)r(os-)0 3886 y(sibly)j(in)h(separate)e(passes)h(just)h(b)r (efore)f(co)r(de)h(generation)0 3986 y(\(i.e.,)d(at)e(the)g(start)g(of) 28 b Ft(docodegen)p Fv(\).)k(Then)22 b(the)h(compiler)0 4085 y(mak)n(es)32 b(inlining)h(decisions)g(and)g(determines)f(the)i (regis-)0 4185 y(ter)22 b(allo)r(cations)f(at)h(the)h(basic)f(blo)r(c)n (k)f(b)r(oundaries.)35 b(These)0 4285 y(decisions)27 b(are)f(later)h(used)h(during)f(co)r(de)h(generation.)0 4572 y Fs(4)135 b(Basic)45 b(Blo)t(c)l(ks)0 4775 y Fj(4.1)112 b(Data)38 b(Structures)0 4933 y Fv(W)-7 b(e)27 b(use)g(t)n(w)n(o)f (data)g(structures)g(during)g(co)r(de)h(generation)0 5033 y(for)39 b(basic)g(blo)r(c)n(ks:)60 b(The)40 b(IL)f(\(in)n (termediate)h(language\))0 5132 y(data)26 b(\015o)n(w)g(graph)g(is)h(a) f(\(mostly\))h(mac)n(hine-indep)r(enden)n(t)0 5232 y(represen)n(tation) d(of)i(the)h(basic)e(blo)r(c)n(k;)h(the)g(ML)g(\(mac)n(hine)0 5332 y(language\))k(data)h(\015o)n(w)f(graph)h(consists)f(of)i(no)r (des)f(repre-)0 5431 y(sen)n(ting)c(the)h(target)f(mac)n(hine)g (instructions.)83 5533 y(W)-7 b(e)46 b(ha)n(v)n(e)e(describ)r(ed)h(the) h(construction)f(of)g(the)h(IL)0 5633 y(graph)26 b(for)i(a)f(basic)g (blo)r(c)n(k)g(in)h([EP96)n(].)83 5735 y(Figure)37 b(2)g(sho)n(ws)f (the)i(\014elds)g(of)f(an)g(IL)h(graph)e(no)r(de.)0 5835 y(The)h Ft(il-op)e Fv(\014eld)i(con)n(tains)f(the)i(no)r(de)f(t)n(yp)r (e)g(\(or)f(op)r(er-)p 1931 3 V 1981 109 a(T)n(yp)r(e)293 b(Op)r(erands)p 1931 142 929 4 v 1981 212 a Ft(I)p 2030 212 27 4 v 31 w(INVERT)h Fv(1)1981 311 y Ft(I)p 2030 311 V 31 w(NEGATE)g Fv(1)1981 411 y Ft(I)p 2030 411 V 31 w(PLUS)382 b Fv(2)1981 511 y Ft(I)p 2030 511 V 31 w(MINUS)338 b Fv(2)1981 610 y Ft(I)p 2030 610 V 31 w(TIMES)g Fv(2)1981 710 y Ft(I)p 2030 710 V 31 w(SLASH)g Fv(2)1981 810 y Ft(I)p 2030 810 V 31 w(MOD)426 b Fv(2)1981 909 y Ft(I)p 2030 909 V 31 w(AND)g Fv(2)1981 1009 y Ft(I)p 2030 1009 V 31 w(OR)470 b Fv(2)1981 1108 y Ft(I)p 2030 1108 V 31 w(XOR)426 b Fv(2)1981 1208 y Ft(I)p 2030 1208 V 31 w(LSHIFT)294 b Fv(2)1981 1308 y Ft(I)p 2030 1308 V 31 w(RSHIFT)g Fv(2)1981 1407 y Ft(I)p 2030 1407 V 31 w(SRSHIFT)250 b Fv(2)1981 1507 y Ft(I)p 2030 1507 V 31 w(CFETCH)294 b Fv(1)1981 1607 y Ft(I)p 2030 1607 V 31 w(FETCH)338 b Fv(1)1981 1706 y Ft(I)p 2030 1706 V 31 w(CSTORE)294 b Fv(2)1981 1806 y Ft(I)p 2030 1806 V 31 w(STORE)338 b Fv(2)1981 1905 y Ft(I)p 2030 1905 V 31 w(EQUALS)294 b Fv(2)1981 2005 y Ft(I)p 2030 2005 V 31 w(LESS)382 b Fv(2)1981 2105 y Ft(I)p 2030 2105 V 31 w(ULESS)338 b Fv(2)1981 2204 y Ft(I)p 2030 2204 V 31 w(0BRANCH)250 b Fv(1)1981 2304 y Ft(I)p 2030 2304 V 31 w(BRANCH)294 b Fv(0)1981 2404 y Ft(I)p 2030 2404 V 31 w(CALL)382 b Fv(0)1981 2503 y Ft(I)p 2030 2503 V 31 w(LIT)426 b Fv(0)1981 2603 y Ft(I)p 2030 2603 V 31 w(ZERO)382 b Fv(0)1981 2702 y Ft(I)p 2030 2702 V 31 w(MOVE)g Fv(1)1981 2802 y Ft(I)p 2030 2802 V 31 w(REG)426 b Fv(0)p 1931 2871 1849 4 v 2423 3012 a(Figure)27 b(3:)36 b(IL)28 b(no)r(de)f(t)n(yp)r(es)1931 3310 y(ator\))36 b(and)h(is)f(discussed)g(b)r(elo)n(w.)64 b(If)37 b(the)g(result)g(of)f(the)1931 3410 y(op)r(eration)i(should)h (reside)g(in)g(a)g(sp)r(ecial)g(register)e(\(sa)n(y)-7 b(,)1931 3510 y(the)31 b(return)e(stac)n(k)g(p)r(oin)n(ter)g (register\),)h(the)g Ft(il-reg)d Fv(\014eld)1931 3609 y(con)n(tains)k(the)h(register)f(n)n(um)n(b)r(er.)49 b(The)32 b(other)f(\014elds)h(are)1931 3709 y(explained)c(in)f(later)g (sections.)2014 3825 y(Figure)k(3)g(sho)n(ws)g(the)h(no)r(de)f(t)n(yp)r (es)h(\(or)f(op)r(erators\))f(of)1931 3925 y(the)d(graph.)35 b(Most)27 b(corresp)r(ond)d(directly)j(to)f(some)g(F)-7 b(orth)1931 4025 y(w)n(ord,)32 b(and)g(their)g(names)f(are)g(prett)n(y) g(self-explanatory)-7 b(.)1931 4124 y(All)39 b(other)f(F)-7 b(orth)38 b(w)n(ords)f(are)g(built)i(from)f(these)g(prim-)1931 4224 y(itiv)n(es)44 b(or)f(call)h(threaded)g(co)r(de)g(w)n(ords.)85 b Ft(I)p 3392 4224 27 4 v 31 w(RSHIFT)42 b Fv(is)1931 4323 y(the)31 b(unsigned)f(\(logical\))f(shift)i(righ)n(t,)f Ft(I)p 3217 4323 V 31 w(SRSHIFT)d Fv(is)j(the)1931 4423 y(signed)35 b(\(arithmetic\))h(shift)g(righ)n(t;)j Ft(I)p 3147 4423 V 31 w(REG)34 b Fv(represen)n(ts)g(a)1931 4523 y(sp)r(eci\014c)40 b(register)f(\(e.g.,)k(a)d(stac)n(k)f(p)r(oin)n(ter) g(register\))g(in)1931 4622 y(the)c(data)f(\015o)n(w)g(graph)g(\()p Ft(il-reg)e Fv(con)n(tains)i(the)h(register)1931 4722 y(n)n(um)n(b)r(er\);)26 b Ft(I)p 2336 4722 V 31 w(MOVE)e Fv(copies)h(a)g(register)e(and)j(is)f(needed)g(for)1931 4822 y(dealing)h(with)g(register)f(sh)n(u\017ing)h(\(see)g(Section)g (4.4.1\).)2014 4938 y(The)38 b(IL)f(op)r(erators)e(discussed)h(ab)r(o)n (v)n(e)g(are)g(mac)n(hine-)1931 5038 y(indep)r(enden)n(t.)94 b(In)47 b(addition,)k(w)n(e)46 b(ha)n(v)n(e)f(an)h(op)r(erator)1931 5137 y Ft(I)p 1980 5137 V 31 w(LITS)19 b Fv(that)h(represen)n(ts)f(a)h (small)g(\(15)f(bit\))i(constan)n(t)f(and)1931 5237 y(is)32 b(useful)h(for)e(the)i(MIPS)f(arc)n(hitecture,)g(whic)n(h)g(can)g(en-) 1931 5337 y(co)r(de)40 b(suc)n(h)f(constan)n(ts)g(directly)g(in)h (instructions.)72 b(F)-7 b(or)1931 5436 y(other)35 b(arc)n(hitectures)e (there)i(w)n(ould)g(b)r(e)g(other)g(suc)n(h)f(op-)1931 5536 y(erators.)52 b(Dealing)33 b(with)h(this)g(problem)e(already)g(at) h(the)1931 5635 y(IL)39 b(lev)n(el)g(mak)n(es)e(retargeting)h(a)g (little)i(more)e(complex,)1931 5735 y(but)27 b(allo)n(ws)d(more)h (accurate)f(decisions)h(in)h(the)g(sc)n(heduler)1931 5835 y(and)j(register)f(allo)r(cator,)g(and)g(simpli\014es)i(the)f (assem)n(bler)p eop %%Page: 4 4 4 3 bop 0 3 1849 4 v 50 109 a Ft(ml-left)358 b Fv(left)28 b(c)n(hild)g(\(or)f(un)n(used\))50 208 y Ft(ml-right)314 b Fv(righ)n(t)27 b(c)n(hild)h(\(or)f(un)n(used\))50 308 y Ft(ml-asm)402 b Fv(XT)28 b(for)f(co)r(de)g(emission)50 408 y Ft(ml-val)402 b Fv(v)-5 b(alue)28 b(of)f(a)g(literal)g(\014eld)h (\(if)h(an)n(y\))50 507 y Ft(ml-reg)402 b Fv(destination)27 b(register)50 607 y Ft(ml-count)314 b Fv(reference)27 b(coun)n(t)g(\(for)g(sc)n(heduling\))50 707 y Ft(ml-depends)226 b Fv(dep)r(endences)28 b(\(for)f(sc)n(heduling\))50 806 y Ft(ml-latency)226 b Fv(used)28 b(for)f(sc)n(heduling)50 906 y Ft(ml-let)402 b Fv(latest)28 b(ex.)36 b(time)28 b(\(for)g(sc)n(heduling\))50 1005 y Ft(ml-pathlength)94 b Fv(used)28 b(for)f(sc)n(heduling)p 0 1083 V 472 1223 a(Figure)g(4:)36 b(ML)28 b(no)r(de)g(\014elds)p 0 1392 V 95 3470 a @beginspecial 36 @llx 36 @lly 235 @urx 281 @ury 1990 @rwi @setspecial %%BeginDocument: il-graph.eps %!PS-Adobe-2.0 %%Creator: dot version 95 (4-10-95) %%For: (aertl) Martin Anton Ertl,Computersprachen,58801-4474, %%Title: g %%Pages: (atend) %%BoundingBox: 36 36 235 281 %%EndComments %%BeginProlog save /DotDict 200 dict def DotDict begin %%BeginResource: procset /coord-font-family /Times-Roman def /default-font-family /Times-Roman def /coordfont coord-font-family findfont 8 scalefont def /InvScaleFactor 1.0 def /set_scale { dup 1 exch div /InvScaleFactor exch def dup scale } bind def % styles /solid { } bind def /dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def /dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def /invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def /bold { 2 setlinewidth } bind def /filled { } bind def /unfilled { } bind def /rounded { } bind def /diagonals { } bind def % hooks for setting color /nodecolor { sethsbcolor } bind def /edgecolor { sethsbcolor } bind def /graphcolor { sethsbcolor } bind def /nopcolor {pop pop pop} bind def /beginpage { % i j npages /npages exch def /j exch def /i exch def /str 10 string def npages 1 gt { gsave coordfont setfont 0 0 moveto (\() show i str cvs show (,) show j str cvs show (\)) show grestore } if } bind def /set_font { findfont exch scalefont setfont } def /arrowhead { /arrowwidth exch def /arrowlength exch def gsave 3 1 roll translate rotate newpath arrowlength arrowwidth 2 div moveto 0 0 lineto arrowlength arrowwidth -2 div lineto closepath fill stroke grestore } def % draw aligned label in bounding box aligned to current point % alignfactor tells what fraction to place on the left. % -.5 is centered. /alignedtext { % text labelwidth fontsz alignfactor /alignfactor exch def /fontsz exch def /width exch def /text exch def gsave % even if node or edge is dashed, don't paint text with dashes [] 0 setdash currentpoint newpath moveto text stringwidth pop alignfactor mul fontsz -.3 mul rmoveto text show grestore } def /boxprim { % xcorner ycorner xsize ysize 4 2 roll moveto 2 copy exch 0 rlineto 0 exch rlineto pop neg 0 rlineto closepath } bind def /ellipse_path { /ry exch def /rx exch def /y exch def /x exch def matrix currentmatrix newpath x y translate rx ry scale 0 0 1 0 360 arc setmatrix } bind def /endpage { showpage } bind def /layercolorseq [ % layer color sequence - darkest to lightest [0 0 0] [.2 .8 .8] [.4 .8 .8] [.6 .8 .8] [.8 .8 .8] ] def /setlayer {/maxlayer exch def /curlayer exch def layercolorseq curlayer get aload pop sethsbcolor /nodecolor {nopcolor} def /edgecolor {nopcolor} def /graphcolor {nopcolor} def } bind def /onlayer { curlayer ne {invis} if } def /onlayers { /myupper exch def /mylower exch def curlayer mylower lt curlayer myupper gt or {invis} if } def /curlayer 0 def %%EndResource %%EndProlog %%BeginSetup 14 default-font-family set_font % /arrowlength 10 def % /arrowwidth 5 def %%EndSetup %%Page: 1 (atend) %%PageBoundingBox: 36 36 235 281 gsave 35 35 200 246 boxprim clip newpath 36 36 translate 0 0 1 beginpage 0 0 translate 0 rotate 0.000 0.000 0.000 graphcolor 9.00 /Helvetica set_font gsave 10 dict begin newpath 0 0 moveto 198 0 lineto 198 244 lineto 0 244 lineto closepath %% stroke end grestore % il_foo_1_100A75BC gsave 10 dict begin 135 214 29 21 ellipse_path stroke gsave 10 dict begin 112 220 moveto (I_REG) 25 9.00 0.00 alignedtext 112 209 moveto (il-reg: $03) 37 9.00 0.00 alignedtext end grestore end grestore % il_foo_1_100A75F0 gsave 10 dict begin 135 158 43 21 ellipse_path stroke gsave 10 dict begin 98 164 moveto (I_MOVE) 33 9.00 0.00 alignedtext 98 153 moveto (il-reg: unallocated) 65 9.00 0.00 alignedtext end grestore end grestore % il_foo_1_100A75BC -> il_foo_1_100A75F0 newpath 135 184 moveto 135 183 135 181 135 179 curveto stroke 135 193 -90.00 10.00 5.00 arrowhead % il_foo_1_1007BED4 gsave 10 dict begin 127 30 29 21 ellipse_path stroke gsave 10 dict begin 104 36 moveto (I_PLUS) 29 9.00 0.00 alignedtext 104 25 moveto (il-reg: $02) 37 9.00 0.00 alignedtext end grestore end grestore % il_foo_1_100A75F0 -> il_foo_1_1007BED4 newpath 168 138 moveto 174 133 180 129 183 123 curveto 190 108 191 78 183 65 curveto 177 56 164 47 152 41 curveto stroke 163 142 -38.66 10.00 5.00 arrowhead % il_foo_1_100A7588 gsave 10 dict begin 38 94 29 21 ellipse_path stroke gsave 10 dict begin 15 100 moveto (I_MOVE) 33 9.00 0.00 alignedtext 15 89 moveto (il-reg: $03) 37 9.00 0.00 alignedtext end grestore end grestore % il_foo_1_100A75F0 -> il_foo_1_100A7588 gsave 10 dict begin dotted newpath 99 139 moveto 89 134 79 128 71 123 curveto 67 120 61 115 56 111 curveto stroke 105 142 -153.43 10.00 5.00 arrowhead end grestore % il_foo_1_1007BEA0 gsave 10 dict begin 127 94 46 29 ellipse_path stroke gsave 10 dict begin 90 106 moveto (I_LITS) 26 9.00 0.00 alignedtext 90 95 moveto (il-val: 2) 28 9.00 0.00 alignedtext 90 84 moveto (il-reg: unallocated) 65 9.00 0.00 alignedtext end grestore end grestore % il_foo_1_1007BEA0 -> il_foo_1_1007BED4 newpath 127 56 moveto 127 54 127 53 127 51 curveto stroke 127 65 -90.00 10.00 5.00 arrowhead % il_foo_1_100A7588 -> il_foo_1_1007BED4 gsave 10 dict begin dotted newpath 61 73 moveto 65 70 68 67 71 65 curveto 80 59 93 50 104 43 curveto stroke 56 77 -38.66 10.00 5.00 arrowhead end grestore % il_foo_1_100A7554 gsave 10 dict begin 38 158 29 21 ellipse_path stroke gsave 10 dict begin 15 164 moveto (I_REG) 25 9.00 0.00 alignedtext 15 153 moveto (il-reg: $02) 37 9.00 0.00 alignedtext end grestore end grestore % il_foo_1_100A7554 -> il_foo_1_100A7588 newpath 38 128 moveto 38 124 38 119 38 115 curveto stroke 38 137 -90.00 10.00 5.00 arrowhead endpage grestore %%PageTrailer %%Trailer %%Pages: 1 end restore %%EOF %%EndDocument @endspecial 0 3509 V 247 3649 a(Figure)f(5:)36 b(The)28 b(IL)f(graph)g(for)g Ft(swap)42 b(2)h(+)0 3967 y Fv(\(the)e(other)e (logical)g(place)g(to)h(deal)g(with)h(o)n(v)n(erly)d(large)0 4066 y(constan)n(ts\).)83 4191 y(The)47 b(ML)g(graph)e(is)i(built)h (during)e(co)r(de)h(selection.)0 4290 y(Eac)n(h)35 b(no)r(de)h(in)g (the)h(ML)f(graph)f(corresp)r(onds)f(to)i(\(usu-)0 4390 y(ally\))d(one)h(instruction.)54 b(Figure)33 b(4)g(sho)n(ws)g(the)h (\014elds)f(of)0 4490 y(an)27 b(ML)h(graph)e(no)r(de.)83 4614 y Ft(Ml-asm)34 b Fv(con)n(tains)h(the)h(execution)g(tok)n(en)g (\(XT\))h(of)f(a)0 4714 y(w)n(ord)29 b(that)i(actually)f(creates)g(the) g(mac)n(hine)h(co)r(de)f(later,)0 4813 y(during)24 b(co)r(de)h (emission)f(\(see)h(Section)g(4.5\).)35 b Ft(Ml-val)22 b Fv(and)0 4913 y Ft(ml-reg)j Fv(are)i(also)f(needed)i(for)f(co)r(de)h (emission.)83 5038 y(Figure)18 b(5)h(sho)n(ws)e(the)i(IL)g(graph)f(for) g Ft(swap)42 b(2)h(+)p Fv(,)20 b(assum-)0 5137 y(ing)25 b(that)g(the)g(top-of-stac)n(k)e(item)i(is)g(in)g(register)e Ft($02)g Fv(and)0 5237 y(the)g(second)g(stac)n(k)f(item)i(is)f(in)g (register)e Ft($03)p Fv(,)i(b)r(oth)h(on)f(en-)0 5337 y(try)g(and)g(exit)g(of)g(the)g(basic)f(blo)r(c)n(k;)j(Fig.)d(6)h(sho)n (ws)f(the)h(ML)0 5436 y(graph,)f(and)f(Fig.)h(7)f(sho)n(ws)g(the)h (resulting)f(mac)n(hine)g(co)r(de.)0 5536 y(The)27 b(reasons)f(wh)n(y)g (the)i(graphs)e(lo)r(ok)g(lik)n(e)h(this)h(and)f(wh)n(y)0 5635 y(the)34 b(\014elds)f(con)n(tain)g(what)g(they)h(con)n(tain)e(are) h(discussed)0 5735 y(in)23 b(the)g(follo)n(wing)e(sections;)j(e.g.,)f (Section)g(4.4.1)e(explains)0 5835 y(the)28 b(presence)f(of)g(the)h Ft(I)p 762 5835 27 4 v 31 w(MOVE)e Fv(no)r(des.)p 1931 50 1849 4 v 1797 4694 a @beginspecial 36 @llx 36 @lly 290 @urx 589 @ury 2540 @rwi @setspecial %%BeginDocument: ml-graph.eps %!PS-Adobe-2.0 %%Creator: dot version 95 (4-10-95) %%For: (aertl) Martin Anton Ertl,Computersprachen,58801-4474, %%Title: g %%Pages: (atend) %%BoundingBox: 36 36 290 589 %%EndComments %%BeginProlog save /DotDict 200 dict def DotDict begin %%BeginResource: procset /coord-font-family /Times-Roman def /default-font-family /Times-Roman def /coordfont coord-font-family findfont 8 scalefont def /InvScaleFactor 1.0 def /set_scale { dup 1 exch div /InvScaleFactor exch def dup scale } bind def % styles /solid { } bind def /dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def /dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def /invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def /bold { 2 setlinewidth } bind def /filled { } bind def /unfilled { } bind def /rounded { } bind def /diagonals { } bind def % hooks for setting color /nodecolor { sethsbcolor } bind def /edgecolor { sethsbcolor } bind def /graphcolor { sethsbcolor } bind def /nopcolor {pop pop pop} bind def /beginpage { % i j npages /npages exch def /j exch def /i exch def /str 10 string def npages 1 gt { gsave coordfont setfont 0 0 moveto (\() show i str cvs show (,) show j str cvs show (\)) show grestore } if } bind def /set_font { findfont exch scalefont setfont } def /arrowhead { /arrowwidth exch def /arrowlength exch def gsave 3 1 roll translate rotate newpath arrowlength arrowwidth 2 div moveto 0 0 lineto arrowlength arrowwidth -2 div lineto closepath fill stroke grestore } def % draw aligned label in bounding box aligned to current point % alignfactor tells what fraction to place on the left. % -.5 is centered. /alignedtext { % text labelwidth fontsz alignfactor /alignfactor exch def /fontsz exch def /width exch def /text exch def gsave % even if node or edge is dashed, don't paint text with dashes [] 0 setdash currentpoint newpath moveto text stringwidth pop alignfactor mul fontsz -.3 mul rmoveto text show grestore } def /boxprim { % xcorner ycorner xsize ysize 4 2 roll moveto 2 copy exch 0 rlineto 0 exch rlineto pop neg 0 rlineto closepath } bind def /ellipse_path { /ry exch def /rx exch def /y exch def /x exch def matrix currentmatrix newpath x y translate rx ry scale 0 0 1 0 360 arc setmatrix } bind def /endpage { showpage } bind def /layercolorseq [ % layer color sequence - darkest to lightest [0 0 0] [.2 .8 .8] [.4 .8 .8] [.6 .8 .8] [.8 .8 .8] ] def /setlayer {/maxlayer exch def /curlayer exch def layercolorseq curlayer get aload pop sethsbcolor /nodecolor {nopcolor} def /edgecolor {nopcolor} def /graphcolor {nopcolor} def } bind def /onlayer { curlayer ne {invis} if } def /onlayers { /myupper exch def /mylower exch def curlayer mylower lt curlayer myupper gt or {invis} if } def /curlayer 0 def %%EndResource %%EndProlog %%BeginSetup 14 default-font-family set_font % /arrowlength 10 def % /arrowwidth 5 def %%EndSetup %%Page: 1 (atend) %%PageBoundingBox: 36 36 290 589 gsave 35 35 255 554 boxprim clip newpath 36 36 translate 0 0 1 beginpage 0 0 translate 0 rotate 0.000 0.000 0.000 graphcolor 9.00 /Helvetica set_font gsave 10 dict begin newpath 0 0 moveto 253 0 lineto 253 552 lineto 0 552 lineto closepath %% stroke end grestore % ml1_foo_1_1007BF18 gsave 10 dict begin 178 485 51 57 ellipse_path stroke gsave 10 dict begin 142 519 moveto (Rule: reg: I_REG) 63 9.00 0.00 alignedtext 142 508 moveto (ml-asm: error) 49 9.00 0.00 alignedtext 142 497 moveto (ml-count: 2) 41 9.00 0.00 alignedtext 142 486 moveto (ml-reg: $03) 42 9.00 0.00 alignedtext 142 475 moveto (ml-latency: 0) 47 9.00 0.00 alignedtext 142 464 moveto (ml-pathlength: 0) 59 9.00 0.00 alignedtext 142 453 moveto (ml-let: 1) 30 9.00 0.00 alignedtext end grestore end grestore % ml1_foo_1_1007BF44 gsave 10 dict begin 178 353 66 60 ellipse_path stroke gsave 10 dict begin 129 387 moveto (Rule: reg: I_MOVE\(reg\)) 89 9.00 0.00 alignedtext 129 376 moveto (ml-asm: asm-move) 69 9.00 0.00 alignedtext 129 365 moveto (ml-count: 2) 41 9.00 0.00 alignedtext 129 354 moveto (ml-reg: unallocated) 70 9.00 0.00 alignedtext 129 343 moveto (ml-latency: 1) 47 9.00 0.00 alignedtext 129 332 moveto (ml-pathlength: 0) 59 9.00 0.00 alignedtext 129 321 moveto (ml-let: 1) 30 9.00 0.00 alignedtext end grestore end grestore % ml1_foo_1_1007BF18 -> ml1_foo_1_1007BF44 newpath 178 418 moveto 178 416 178 415 178 413 curveto stroke 178 427 -90.00 10.00 5.00 arrowhead % ml1_foo_1_1007BF70 gsave 10 dict begin 138 77 77 68 ellipse_path stroke gsave 10 dict begin 81 116 moveto (Rule: reg: I_PLUS\(reg, cons\)) 105 9.00 0.00 alignedtext 81 105 moveto (ml-asm: asm-addiu) 69 9.00 0.00 alignedtext 81 94 moveto (ml-count: 0) 41 9.00 0.00 alignedtext 81 83 moveto (ml-val: 2) 32 9.00 0.00 alignedtext 81 72 moveto (ml-reg: $02) 42 9.00 0.00 alignedtext 81 61 moveto (ml-latency: 1) 47 9.00 0.00 alignedtext 81 50 moveto (ml-pathlength: 2) 59 9.00 0.00 alignedtext 81 39 moveto (ml-let: 1) 30 9.00 0.00 alignedtext end grestore end grestore % ml1_foo_1_1007BF44 -> ml1_foo_1_1007BF70 newpath 183 284 moveto 185 243 186 192 179 159 curveto 178 153 175 146 172 138 curveto stroke 182 293 -83.66 10.00 5.00 arrowhead % ml1_foo_1_1007BFC8 gsave 10 dict begin 110 219 66 60 ellipse_path stroke gsave 10 dict begin 61 253 moveto (Rule: reg: I_MOVE\(reg\)) 89 9.00 0.00 alignedtext 61 242 moveto (ml-asm: asm-move) 69 9.00 0.00 alignedtext 61 231 moveto (ml-count: 1) 41 9.00 0.00 alignedtext 61 220 moveto (ml-reg: $03) 42 9.00 0.00 alignedtext 61 209 moveto (ml-latency: 1) 47 9.00 0.00 alignedtext 61 198 moveto (ml-pathlength: 1) 59 9.00 0.00 alignedtext 61 187 moveto (ml-let: 1) 30 9.00 0.00 alignedtext end grestore end grestore % ml1_foo_1_1007BF44 -> ml1_foo_1_1007BFC8 gsave 10 dict begin dotted newpath 146 290 moveto 143 285 141 279 138 273 curveto stroke 150 298 -116.57 10.00 5.00 arrowhead end grestore % ml1_foo_1_1007BF9C gsave 10 dict begin 60 353 51 57 ellipse_path stroke gsave 10 dict begin 24 387 moveto (Rule: reg: I_REG) 63 9.00 0.00 alignedtext 24 376 moveto (ml-asm: error) 49 9.00 0.00 alignedtext 24 365 moveto (ml-count: 2) 41 9.00 0.00 alignedtext 24 354 moveto (ml-reg: $02) 42 9.00 0.00 alignedtext 24 343 moveto (ml-latency: 0) 47 9.00 0.00 alignedtext 24 332 moveto (ml-pathlength: 0) 59 9.00 0.00 alignedtext 24 321 moveto (ml-let: 1) 30 9.00 0.00 alignedtext end grestore end grestore % ml1_foo_1_1007BF9C -> ml1_foo_1_1007BFC8 newpath 82 294 moveto 84 288 87 282 89 276 curveto stroke 80 300 -71.57 10.00 5.00 arrowhead % ml1_foo_1_1007BFC8 -> ml1_foo_1_1007BF70 gsave 10 dict begin dotted newpath 123 154 moveto 124 151 124 148 125 144 curveto stroke 122 160 -80.54 10.00 5.00 arrowhead end grestore endpage grestore %%PageTrailer %%Trailer %%Pages: 1 end restore %%EOF %%EndDocument @endspecial 1931 4733 V 1931 4874 a(Figure)48 b(6:)79 b(The)49 b(ML)g(graph)f(for)g Ft(swap)42 b(2)h(+)p Fv(,)54 b(b)r(efore)1931 4974 y(sc)n(heduling)27 b(and)h(register)e(allo)r (cation)p 1931 5153 V 2025 5259 a Ft(move)42 b($4,$3)2025 5358 y(move)g($3,$2)2025 5458 y(addiu)f($2,$4,2)p 1931 5527 V 1931 5667 a Fv(Figure)i(7:)67 b(Mac)n(hine)42 b(co)r(de)h(generated)e(for)i Ft(swap)f(2)h(+)1931 5767 y Fv(\(the)29 b(destination)e(register)f(is)i(on)f(the)h(left\))p eop %%Page: 5 5 5 4 bop 0 83 a Fj(4.2)112 b(Instruction)36 b(Selection)0 236 y Fr(4.2.1)94 b(T)-8 b(ree)32 b(P)m(arsing)0 390 y Fv(The)19 b(metho)r(d)h(w)n(e)f(use)h(for)e(instruction)i(selection)e (is)i(called)0 489 y(tree)39 b(parsing.)69 b(W)-7 b(e)39 b(use)g(it)g(b)r(ecause)g(suc)n(h)g(instruction)0 589 y(selectors)24 b(are)g(v)n(ery)g(fast,)i(and)f(b)r(ecause)g(it)g(is)g (easy)f(to)h(use)0 688 y(\(with)j(the)g(righ)n(t)f(to)r(ols\).)83 788 y(Basically)-7 b(,)24 b(for)g(a)h(giv)n(en)f(IL)g(graph)g(the)h (instruction)g(se-)0 888 y(lector)33 b(pro)r(duces)g(the)h(equiv)-5 b(alen)n(t)33 b(ML)h(graph.)54 b(W)-7 b(e)34 b(de-)0 987 y(scrib)r(e)27 b(the)h(equiv)-5 b(alence)27 b(in)h(rules,)f(suc)n (h)h(as:)0 1155 y Fh(reg:I_PLUS\(reg,cons\)#1#binrc-)q(inst)q(#asm-)q (addi)q(u)83 1331 y Fv(Eac)n(h)e(rule)i(con)n(tains)e(four)i(parts,)e (separated)h(b)n(y)h Ft(#)p Fv(:)60 1506 y(1.)41 b(The)i(\014rst)g (parts)f(of)h(all)g(rules)f(constitute)h(a)g(tree)166 1606 y(grammar)25 b(for)i(parsing)f(IL)h(trees;)g(in)g(this)h(example,) 166 1706 y(it)c(sa)n(ys)d(that)j(w)n(e)f(can)f(parse)g(the)i(tree)f(as) f(a)h Ft(reg)f Fv(with)166 1805 y(this)k(rule,)g(if)h(the)f(op)r (erator)e(is)i Ft(I)p 1194 1805 27 4 v 31 w(PLUS)p Fv(,)e(the)j (subtree)166 1905 y(ro)r(oted)35 b(at)h(its)g(left)g(c)n(hild)g(can)f (b)r(e)i(parsed)d(as)h Ft(reg)p Fv(,)166 2004 y(and)j(the)g(subtree)g (ro)r(oted)f(at)h(its)g(righ)n(t)f(c)n(hild)h(can)166 2104 y(b)r(e)g(parsed)f(as)g Ft(cons)p Fv(.)66 b Ft(reg)36 b Fv(and)i Ft(cons)e Fv(are)h(called)166 2204 y Fn(nonterminals)7 b Fv(;)28 b(instead)g(of)g Fn(p)l(arse)j(as)g Fm(reg)p Fv(,)c(w)n(e)g(also)166 2303 y(sa)n(y)k Fn(r)l(e)l(duc)l(e)i(to)h Fm(reg)p Fv(.)49 b(In)32 b(the)g(con)n(text)g(of)f(our)h(co)r(de)166 2403 y(selector,)k(this)g(means)f(that)h(w)n(e)f(ha)n(v)n(e)f(an)h (instruc-)166 2503 y(tion)24 b(for)g(the)h(addition)f(of)g(a)g (register)e(and)i(a)g(\(small\))166 2602 y(constan)n(t,)j(deliv)n (ering)f(the)i(result)g(in)g(a)f(register.)60 2765 y(2.)41 b(The)36 b(cost)g(of)g(using)g(this)g(rule)g(to)g(parse)f(the)i(tree;) 166 2865 y(the)27 b(cost)f(should)g(re\015ect)g(the)g(cost)g(\(e.g.,)g (co)r(de)h(size,)166 2965 y(n)n(um)n(b)r(er)20 b(of)g(cycles\))g(of)h (the)f(instruction)g(that)h(is)f(gen-)166 3064 y(erated)33 b(for)g(this)h(rule.)55 b(If)34 b(there)f(are)g(sev)n(eral)f(w)n(a)n (ys)166 3164 y(to)j(parse)f(the)h(tree,)h(the)g(tree)e(parser)g(c)n(ho) r(oses)f(the)166 3264 y(c)n(heap)r(est.)44 b(The)30 b(cost)f(of)h(the)h (instruction)f(ab)r(o)n(v)n(e)e(is)166 3363 y(1)f(cycle.)60 3527 y(3.)41 b(The)22 b(action,)h(i.e.,)h(a)d(piece)h(of)h(F)-7 b(orth)21 b(co)r(de)h(for)g(build-)166 3626 y(ing)29 b(the)i(ML)e(no)r(de)h(for)f(the)h(instruction)g(describ)r(ed)166 3726 y(in)25 b(the)f(rule)h(\(if)g(suc)n(h)f(a)g(no)r(de)g(is)h(built)g (for)f(the)g(rule\).)166 3825 y(In)h(this)g(example,)g(a)f(w)n(ord)g (for)g(building)h(a)f(no)r(de)h(for)166 3925 y(an)35 b(instruction)g(with)h(a)f(register)f(and)h(a)g(constan)n(t)166 4025 y(op)r(erand.)60 4188 y(4.)41 b(A)27 b(piece)g(of)g(F)-7 b(orth)27 b(co)r(de)g(for)f(doing)h(the)g(co)r(de)g(emis-)166 4288 y(sion)38 b(for)h(the)g(ML)g(co)r(de.)70 b(This)38 b(piece)h(of)g(co)r(de)f(is)166 4387 y(wrapp)r(ed)e(in)g(a)g(colon)g (de\014nition,)i(and)f(its)f(execu-)166 4487 y(tion)d(tok)n(en)f(is)h (passed)f(to)h(the)g(ML)g(no)r(de)g(building)166 4586 y(co)r(de)27 b(\(part)h(3\).)36 b(This)28 b(XT)g(is)f(then)h(stored)f (in)n(to)g(the)166 4686 y(\014eld)k Ft(ml-asm)p Fv(.)44 b(In)31 b(this)g(example,)g(a)f(piece)h(of)g(co)r(de)166 4786 y(for)c(generating)f(an)i Ft(addiu)d Fv(instruction.)83 4961 y(W)-7 b(e)34 b(use)f(the)h(tree)f(parser)f(generator)g(Burg)g ([FHP92)o(,)0 5061 y(Pro95)n(])22 b(for)g(translating)f(these)h(rules)g (in)n(to)g(a)g(tree)g(parsing)0 5161 y(automaton.)77 b(W)-7 b(e)42 b(ha)n(v)n(e)e(mo)r(di\014ed)i(Burg)e(to)i(generate)0 5260 y(F)-7 b(orth)27 b(source)g(co)r(de)g(\(instead)h(of)f(C\))h(for)f (this)h(purp)r(ose.)83 5360 y(The)i(tree)f(parsers)f(generated)g(b)n(y) h(Burg)g(w)n(ork)f(in)i(t)n(w)n(o)0 5460 y(passes)c(o)n(v)n(er)g(the)i (tree:)83 5635 y Fu(\017)41 b Fv(The)35 b Fn(lab)l(el)t(ler)47 b Fv(runs)35 b(from)g(the)g(lea)n(v)n(es)f(to)h(the)h(ro)r(ot)166 5735 y(and)h(computes)f(a)h Fn(state)h(lab)l(el)46 b Fv(for)37 b(eac)n(h)f(no)r(de)h(\(in)166 5835 y Ft(il-slabel)p Fv(\),)23 b(based)i(on)g(the)g(no)r(de's)h(op)r(erator,)e(the)2097 83 y(states)i(of)h(its)g(c)n(hildren,)f(and)h(a)f(table)g(generated)g (b)n(y)2097 183 y(Burg.)2014 353 y Fu(\017)41 b Fv(The)29 b Fn(r)l(e)l(duc)l(er)38 b Fv(computes)28 b(the)h(rules)f(used)h(for)f (pars-)2097 452 y(ing)38 b(the)f(tree,)j(starting)d(at)g(the)h(ro)r (ot.)66 b(Our)36 b(com-)2097 552 y(piler)22 b(reduces)f(the)h(complete) g(tree)g(to)g Ft(reg)e Fv(\(the)j(goal)2097 652 y(non)n(terminal\).)36 b(The)24 b(reducer)f(determines)h(the)h(rule)2097 751 y(used)41 b(from)e(the)i(state)f(lab)r(el)g(and)g(from)g(the)h(goal) 2097 851 y(non)n(terminal.)d(It)29 b(then)g(reduces)f(the)g(subtrees)g (cor-)2097 951 y(resp)r(onding)37 b(to)g(the)h(non)n(terminals)f(on)g (the)h(righ)n(t-)2097 1050 y(hand)k(side)f(of)h(the)g(rule)f(to)h (these)g(non)n(terminals;)2097 1150 y(e.g.,)d(if)e(the)g(example)f (rule)g(ab)r(o)n(v)n(e)f(is)i(used,)h(it)f(re-)2097 1249 y(duces)j(the)g(subtree)f(ro)r(oted)g(at)h(the)g(left)g(c)n(hild)g(to) 2097 1349 y Ft(reg)p Fv(,)c(and)f(the)g(subtree)f(ro)r(oted)h(at)f(the) i(righ)n(t)e(side)2097 1449 y(to)28 b Ft(cons)p Fv(.)2097 1584 y(Since)35 b(just)g(kno)n(wing)f(the)h(rules)f(used)h(is)f(not)h (v)n(ery)2097 1683 y(useful,)21 b(the)f(reducer)e(t)n(ypically)g(also)g (p)r(erforms)g(some)2097 1783 y(co)r(de)40 b(generation)e(action;)46 b(in)40 b(our)f(case)g(it)h(builds)2097 1882 y(the)34 b(ML)g(graph,)g(usually)e(one)i(ML)f(no)r(de)h(p)r(er)f(rule)2097 1982 y(application.)2097 2117 y(Note)25 b(that)g(the)g(reducer)f(ma)n (y)g(visit)h(some)f(IL)h(no)r(des)2097 2217 y(sev)n(eral)h(times;)i (this)g(happ)r(ens)g(for)f(rules)g(lik)n(e)2097 2420 y Ft(reg:cons#...)2097 2623 y Fv(where)33 b(the)h(IL)f(no)r(de)g(is)g (\014rst)g(visited)h(for)e(the)i(goal)2097 2723 y(non)n(terminal)24 b Ft(rge)p Fv(,)g(and)h(then)g(for)f(the)h(goal)f(non)n(ter-)2097 2823 y(minal)k Ft(cons)p Fv(.)2097 2957 y(The)e(reducer)f(ma)n(y)h (also)f(skip)h(some)f(IL)h(no)r(des;)g(this)2097 3057 y(w)n(ould)h(happ)r(en)h(with)g(a)g(rule)f(lik)n(e)2097 3260 y Ft(reg:)42 b(I_FETCH\(I_PLUS\(re)o(g,)37 b(cons\)\)#...)2097 3464 y Fv(whic)n(h)28 b(w)n(ould)g(skip)g(the)h Ft(I)p 2945 3464 V 31 w(PLUS)d Fv(no)r(de.)39 b(Therefore,)2097 3563 y(the)25 b(reducer)e(can)h(translate)f(one)h(IL)g(no)r(de)g(in)n (to)g(sev-)2097 3663 y(eral)31 b(ML)h(no)r(des,)g(but)g(also)f(sev)n (eral)f(IL)h(no)r(des)h(in)n(to)2097 3763 y(only)c(one)f(ML)g(no)r(de.) 1931 3984 y Fr(4.2.2)94 b(The)32 b(Reducer)1931 4139 y Fv(The)f(lab)r(eller)g(is)g(quite)g(simple.)47 b(Ho)n(w)n(ev)n(er,)30 b(the)i(reducer)1931 4239 y(merits)j(further)g(discussion:)51 b(Basically)-7 b(,)35 b(it)h(p)r(erforms)e(a)1931 4338 y(recursiv)n(e)28 b(w)n(alk)i(of)f(a)h(tree)g(of)g(rules)f(that)h(w)n (ere)f(used)h(for)1931 4438 y(parsing)37 b(the)i(IL)f(tree.)69 b(On)39 b(returning)e(from)h(reducing)1931 4537 y(the)28 b(subtrees,)e(the)i(reducer)e(p)r(erforms)g(the)h(action)g(\(part)1931 4637 y(3\))37 b(of)f(the)h(rule,)h(passing)e(the)h(follo)n(wing)e (items)i(on)f(the)1931 4737 y(data)22 b(stac)n(k:)34 b(the)23 b(stac)n(k)e(items)i(pro)r(duced)f(b)n(y)g(the)h(actions)1931 4836 y(of)32 b(the)h(subtrees,)g(the)f(XT)h(for)e(part)h(4)g(of)g(the)g (rule,)h(the)1931 4936 y(address)22 b(of)g(the)i(ro)r(ot)e(IL)g(no)r (de)h(of)g(the)g(tree,)g(and)g(the)g(goal)1931 5036 y(non)n(terminal.) 46 b(T)n(ypically)-7 b(,)30 b(the)h(action)g(consumes)f(these)1931 5135 y(items)e(and)g(pro)r(duces)e(some)i(new)f(items.)2014 5236 y(Usually)-7 b(,)55 b(the)50 b(action)f(builds)h(an)f(ML)h(no)r (de,)55 b(that)1931 5335 y(con)n(tains)d(the)h(ML)g(no)r(de)f(p)r(oin)n (ters)g(passed)g(in)h(from)1931 5435 y(the)44 b(subtree)f(reductions)g (as)g(c)n(hildren)g(\()p Ft(ml-left)e Fv(and)1931 5535 y Ft(ml-right)p Fv(\),)33 b(and)h(the)g(XT)g(for)f(part)h(4)f(in)i Ft(ml-asm)p Fv(;)f(the)1931 5634 y(action)27 b(then)h(returns)f(a)h(p)r (oin)n(ter)f(to)g(that)h(ML)g(no)r(de.)2014 5735 y(Y)-7 b(ou)21 b(ma)n(y)f(w)n(onder)g(ho)n(w)g(w)n(e)g(k)n(eep)g(the)h(stac)n (k)f(balanced;)1931 5835 y(after)38 b(all,)i(w)n(e)d(don't)h(kno)n(w)f (whic)n(h)h(rules)f(are)f(used)i(for)p eop %%Page: 6 6 6 5 bop 0 3 1849 4 v 50 109 a Ft(reg)142 b Fv(--)27 b(ml)173 b(inst.)28 b(with)h(normal)d(register)g(result)50 208 y Ft(con)142 b Fv(--)27 b(n)219 b(constan)n(t)50 308 y Ft(cons)98 b Fv(--)27 b(n)219 b(small)28 b(constan)n(t)50 408 y Ft(addr)98 b Fv(--)27 b(ml)h(n)99 b(e\013ectiv)n(e)28 b(address)p 0 485 V 0 626 a(Figure)35 b(8:)53 b(Non)n(terminals)35 b(and)h(their)g(reduction)f(stac)n(k)0 725 y(e\013ects)28 b(\(for)f(the)h(MIPS)g(arc)n(hitecture\))0 1009 y(reducing)40 b(the)g(subtrees,)j(and,)g(therefore)d(don't)g(kno)n(w)0 1109 y(the)24 b(actions)f(used.)35 b(What)24 b(w)n(e)g(do)f(kno)n(w,)h (ho)n(w)n(ev)n(er,)e(is,)i(to)0 1209 y(whic)n(h)34 b(non)n(terminals)f (the)h(subtrees)g(are)f(reduced.)56 b(W)-7 b(e)0 1308 y(therefore)39 b(mak)n(e)f(sure)h(that)h(all)f(rules)g(that)h(reduce)f (to)0 1408 y(the)34 b(same)f(non)n(terminal)f(ha)n(v)n(e)g(the)i(same)f (o)n(v)n(erall)e(stac)n(k)0 1507 y(e\013ect;)g(this)g(o)n(v)n(erall)c (stac)n(k)i(e\013ect)h(consists)f(of)h(the)g(stac)n(k)0 1607 y(e\013ects)22 b(for)f(reducing)g(the)h(subtrees,)g(then)g (pushing)g(three)0 1707 y(stac)n(k)27 b(items,)h(and)f(then)h(the)g (action)f(of)h(the)g(rule.)83 1814 y(Figure)43 b(8)g(sho)n(ws)f(the)i (non)n(terminals)e(that)i(w)n(e)f(cur-)0 1913 y(ren)n(tly)31 b(use)h(in)h(the)f(MIPS)g(co)r(de)g(selector)e(and)i(their)g(re-)0 2013 y(duction)k(stac)n(k)g(e\013ects.)63 b(The)36 b(most)g(imp)r (ortan)n(t)g(one)f(is)0 2112 y Ft(reg)p Fv(;)k(reducing)d(an)f(IL)h (tree)g(to)g(a)g Ft(reg)f Fv(creates)f(an)i(ML)0 2212 y(tree)j(for)g(instructions)f(that)i(compute)f(the)h(expression)0 2312 y(represen)n(ted)33 b(b)n(y)i(the)g(IL)f(tree)g(and)h(lea)n(v)n(e) e(the)i(result)f(in)0 2411 y(a)i(register.)62 b(The)36 b(ML)h(no)r(de)f(p)r(oin)n(ter)g(returned)g(b)n(y)g(re-)0 2511 y(ducing)28 b(to)g Ft(reg)e Fv(is)i(the)h(ro)r(ot)e(of)h(this)g (ML)g(tree.)37 b(F)-7 b(or)28 b(sim-)0 2611 y(plicit)n(y)-7 b(,)24 b(w)n(e)f(also)e(use)i(this)g(non)n(terminal)f(for)h (instructions)0 2710 y(that)j(do)g(not)g(ha)n(v)n(e)e(a)i(result)f(in)i (a)e(register,)g(lik)n(e)g Ft(I)p 1604 2710 27 4 v 31 w(STORE)0 2810 y Fv(and)43 b Ft(I)p 226 2810 V 31 w(BRANCH)p Fv(.)d(T)-7 b(rees)42 b(consisting)g(of)h(constan)n(t)f(com-)0 2909 y(putations)36 b(can)g(b)r(e)g(reduced)g(to)g Ft(con)f Fv(and,)k(sometimes,)0 3009 y Ft(cons)p Fv(;)f(the)e(reduction)f (returns)g(the)h(v)-5 b(alue)35 b(of)h(the)g(tree.)0 3109 y(The)23 b Ft(addr)e Fv(non)n(terminal)h(is)h(a)f(factor)g(of)h (the)g(memory)f(ac-)0 3208 y(cess)28 b(instructions;)g(an)g(e\013ectiv) n(e)h(address)e(on)h(the)h(MIPS)0 3308 y(arc)n(hitecture)38 b(is)i(the)f(sum)h(of)f(a)g(register)f(and)i(a)f(small)0 3408 y(constan)n(t;)25 b(reducing)e(a)h(tree)g(to)g(an)g Ft(addr)f Fv(simply)h(returns)0 3507 y(the)e(constan)n(t)e(and)h(an)g (ML)g(no)r(de)h(p)r(oin)n(ter)f(for)f(a)h(tree)g(that)0 3607 y(computes)27 b(the)h(register.)0 3861 y Fr(4.2.3)94 b(D)m(A)m(Gs)0 4027 y Fv(Y)-7 b(ou)26 b(ma)n(y)g(ha)n(v)n(e)f(noticed)h (that)h(w)n(e)f(ha)n(v)n(e)f(discussed)h(trees)0 4127 y(in)37 b(the)h(ab)r(o)n(v)n(e,)g(but)g(use)f(the)h(tree)f(parser)f(on) g(directed)0 4226 y(acyclic)30 b(graphs)f(\(i.e.,)i(the)g(IL)g (graph\);)g(this)f(is)h(p)r(ossible,)0 4326 y(with)d(a)f(little)i (care.)83 4433 y(One)35 b(of)g(the)g(e\013ects)g(of)g(applying)g(tree)f (parsing)g(to)h(a)0 4532 y(D)n(A)n(G)e(is)g(that)g(the)g(reducer)e(ma)n (y)h(visit)h(the)g(same)f(no)r(de)0 4632 y(sev)n(eral)e(times,)k(from)d (di\013eren)n(t)h(paren)n(ts.)49 b(Moreo)n(v)n(er,)31 b(it)0 4732 y(ma)n(y)g(try)g(to)h(reduce)f(the)i(tree)e(ro)r(oted)g(at) h(that)g(no)r(de)f(to)0 4831 y(di\013eren)n(t)d(non)n(terminals.)36 b(What)29 b(w)n(e)e(w)n(an)n(t)g(the)h(co)r(de)g(se-)0 4931 y(lector)40 b(to)h(do)f(when)h(encoun)n(tering)f(an)g(IL)h(no)r (de)g(with)0 5030 y(more)31 b(than)g(one)g(paren)n(t)g(\(a)g(shared)f (no)r(de\))i(is)f(to)g(create)0 5130 y(a)c(shared)g(ML)g(no)r(de.)83 5237 y(The)35 b Ft(il-nt-insts)c Fv(\014eld)k(of)g(the)g(IL)g(no)r(de)h (pla)n(ys)e(an)0 5337 y(imp)r(ortan)n(t)g(role)g(here:)50 b(It)34 b(con)n(tains)g(an)g(arra)n(y)e(indexed)0 5436 y(with)d(non)n(terminal)e(n)n(um)n(b)r(ers;)h(eac)n(h)g(elemen)n(t)g (of)g(the)h(ar-)0 5536 y(ra)n(y)35 b(stores)h(a)g(p)r(oin)n(ter)g(to)g (the)h(ro)r(ot)f(of)h(the)g(ML)f(graph)0 5635 y(that)25 b(is)f(built)h(b)n(y)f(reducing)g(the)h(IL)g(graph)e(ro)r(oted)h(at)g (the)0 5735 y(no)r(de)35 b(to)g(the)h(resp)r(ectiv)n(e)e(non)n (terminal;)39 b(it)c(con)n(tains)g(0,)0 5835 y(if)c(suc)n(h)f(an)g(ML)g (graph)f(has)h(not)g(b)r(een)h(built)g(\(y)n(et\).)45 b(F)-7 b(or)1931 83 y(our)24 b(MIPS)g(co)r(de)g(selector,)g(only)g(the) g Ft(reg)f Fv(elemen)n(ts)h(con-)1931 183 y(tain)e(suc)n(h)f(p)r(oin)n (ters)g(\(b)r(ecause)g(ML)h(no)r(des)f(are)g(only)g(built)1931 282 y(when)28 b(reducing)f(to)g(a)h Ft(reg)p Fv(\).)2014 382 y(No)n(w,)e(b)r(efore)f(reducing)g(an)g(IL)g(graph)f(to)h(a)g(non)n (termi-)1931 482 y(nal,)40 b(the)e(reducer)f(c)n(hec)n(ks)f(the)i Ft(il-nt-insts)33 b Fv(elemen)n(t)1931 582 y(for)g(the)g(non)n (terminal.)52 b(If)34 b(it)f(already)f(con)n(tains)g(an)h(ML)1931 681 y(no)r(de)43 b(p)r(oin)n(ter,)i(then)e(the)g(reducer)f(just)h (returns)e(that)1931 781 y(p)r(oin)n(ter)35 b(instead)g(of)g(reducing)f (the)i(IL)f(graph)e(again;)38 b(if)1931 880 y(it)29 b(con)n(tains)e(0,) h(then)g(the)h(reducer)e(p)r(erforms)g(the)h(reduc-)1931 980 y(tion)c(as)e(usual,)i(and)g(the)g(actions)e(that)i(create)e(ML)i (no)r(des)1931 1080 y(put)i(them)g(in)g(the)g(appropriate)d Ft(il-nt-insts)e Fv(elemen)n(t.)2014 1180 y(This)27 b(shares)f(the)i (ML)f(no)r(des)g(and)g(a)n(v)n(oids)e(replication)1931 1279 y(in)g(cases)e(where)h(all)g(paren)n(ts)g(try)g(to)g(reduce)g(to)g (the)h(same)1931 1379 y(non)n(terminal.)36 b(F)-7 b(or)27 b(the)g(other)g(cases,)f(w)n(e)h(just)h(write)f(the)1931 1479 y(rules)32 b(in)g(a)g(w)n(a)n(y)f(that)h(a)n(v)n(oids)f (unpro\014table)g(co)r(de)h(repli-)1931 1578 y(cation.)62 b(W)-7 b(e)36 b(will)g(discuss)g(this)g(\(v)n(ery)f(in)n(v)n(olv)n (ed\))g(topic)1931 1678 y(somewhere)27 b(else.)1931 1913 y Fj(4.3)113 b(Instruction)36 b(Sc)m(heduling)1931 2067 y Fv(The)25 b(instruction)g(sc)n(heduler)g(determines)f(the)i (execution)1931 2166 y(order)17 b(of)i(the)g(instructions.)33 b(The)19 b(result)f(of)h(the)f(sc)n(heduler)1931 2266 y(is)28 b(an)f(arra)n(y)e(of)j(ML)g(no)r(des.)1931 2484 y Fr(4.3.1)94 b(Dep)s(endences)1931 2638 y Fv(The)42 b(sc)n(heduler)f(has)g(to)g(consider)g(more)f(dep)r(endences)1931 2738 y(b)r(et)n(w)n(een)51 b(the)g(instructions)f(than)g(the)h (register)e(data)1931 2837 y(\015o)n(w)32 b(dep)r(endences)h(represen)n (ted)f(b)n(y)h(the)g Ft(ml-left)d Fv(and)1931 2937 y Ft(ml-right)i Fv(\014elds.)58 b(E.g.,)35 b(it)h(has)e(to)g(tak)n(e)g (in)n(to)g(accoun)n(t)1931 3037 y(write-after-read)26 b(dep)r(endences)i(through)f(registers)f(and)1931 3136 y(dep)r(endences)21 b(through)e(memory)-7 b(.)34 b(These)19 b(additional)h(de-)1931 3236 y(p)r(endences)35 b(are)f(represen)n(ted)g (in)h(the)g(IL)g(graph)f(b)n(y)g(the)1931 3336 y Ft(il-depends)27 b Fv(\014eld,)32 b(whic)n(h)f(con)n(tains)f(a)h(list)g(of)g(p)r(oin)n (ters)1931 3435 y(to)j(IL)f(no)r(des)g(on)g(whic)n(h)h(the)f (instruction)h(dep)r(ends.)54 b(In)1931 3535 y(Section)22 b(4.2)f(w)n(e)h(skipp)r(ed)g(the)g(problem)g(of)g(ho)n(w)f(to)h(trans-) 1931 3634 y(late)j(these)g(dep)r(endences)h(in)n(to)e(dep)r(endences)i (in)f(the)h(ML)1931 3734 y(graph;)h(therefore,)g(w)n(e)g(will)h (discuss)f(this)h(problem)f(here.)2014 3834 y(In)19 b(dealing)g(with)g (this)h(problem,)g(w)n(e)f(exploit)f(t)n(w)n(o)h(facts:)2014 4002 y Fu(\017)41 b Fv(The)83 b(dep)r(endence)g(p)r(oin)n(ters)f(only)g (p)r(oin)n(t)h(to)2097 4101 y(no)r(des)46 b(with)g(the)g(op)r(erators)d Ft(I)p 3151 4101 V 31 w(FETCH)p Fv(,)h Ft(I)p 3513 4101 V 31 w(STORE)p Fv(,)2097 4201 y Ft(I)p 2146 4201 V 31 w(CFETCH)p Fv(,)18 b Ft(I)p 2526 4201 V 31 w(CSTORE)f Fv(\(for)i(memory)g(dep)r(endences\))2097 4300 y(and)45 b Ft(I)p 2325 4300 V 31 w(MOVE)d Fv(\(for)j(register)e (write-after-read)f(de-)2097 4400 y(p)r(endences\).)2014 4568 y Fu(\017)f Fv(All)c(rules)f(in)n(v)n(olving)g(these)g(op)r (erators)f(are)h(of)g(the)2097 4667 y(form)2097 4868 y Ft(reg:)42 b Fm(operator)11 b Ft(\(...\)#...)2097 5070 y Fv(where)39 b Fm(operator)50 b Fv(is)38 b(the)i(op)r(erator)d(in)i (question,)2097 5169 y(and)28 b(it)g(only)f(o)r(ccurs)g(in)g(this)h (place.)2014 5337 y(No)n(w,)c(w)n(e)f(extend)h(the)g(reducer)f(in)g (the)h(follo)n(wing)f(w)n(a)n(y:)1931 5436 y(During)30 b(its)g(recursiv)n(e)e(w)n(alk)h(of)h(the)g(graph,)f(it)i(no)n(w)e (also)1931 5536 y(follo)n(ws)45 b(the)h(dep)r(endences)g(in)g Ft(il-depends)p Fv(,)g(and)f(re-)1931 5635 y(duces)d(the)f(subtrees)g (ro)r(oted)g(there)g(to)g Ft(reg)p Fv(.)77 b(It)42 b(then)1931 5735 y(adds)36 b(the)g(resulting)g(ML)g(no)r(de)g(p)r(oin)n(ter)g(to)g (the)g(list)h(of)1931 5835 y(dep)r(endences)28 b(in)g Ft(ml-depends)p Fv(.)p eop %%Page: 7 7 7 6 bop 0 83 a Fr(4.3.2)94 b(Sc)m(heduling)0 245 y Fv(F)-7 b(or)30 b(the)g(sc)n(heduler)g(itself,)h(w)n(e)f(use)g(list)h(sc)n (heduling,)f(the)0 344 y(dominan)n(t)21 b(tec)n(hnique;)j(it)e(is)f (relativ)n(ely)f(straigh)n(tforw)n(ard,)0 444 y(and)29 b(pro)r(duces)f(go)r(o)r(d)g(co)r(de)h(\(if)g(the)h(righ)n(t)e (heuristics)g(are)0 543 y(used\).)83 648 y(List)42 b(sc)n(hedulers)f (can)h(w)n(ork)f(b)n(y)g(pro)r(ducing)h(the)g(in-)0 747 y(structions)c(from)h(the)g(\014rst)g(one)f(\(in)h(the)h(resulting)e (se-)0 847 y(quence\))g(to)h(the)f(last)g(one,)j(or)c(the)i(other)f(w)n (a)n(y)f(round.)0 946 y(W)-7 b(e)27 b(use)g(a)g(list)g(sc)n(heduler)f (that)h(starts)f(with)h(the)h(last)e(in-)0 1046 y(struction,)42 b(b)r(ecause)d(this)h(w)n(orks)d(b)r(etter)j(for)f(our)g(data)0 1146 y(structures)25 b(and)h(\014ts)g(b)r(etter)h(in)f(the)g (organization)e(of)i(the)0 1245 y(passes)g(\(see)i(Section)g(4.6\).)83 1349 y(List)20 b(sc)n(heduling)g(w)n(orks)e(b)n(y)i(selecting)g(one)f (of)h(the)h(lead-)0 1449 y(ers)30 b(\(in)h(our)f(case,)g(instructions)h (without)g(successors)d(in)0 1549 y(the)45 b(dep)r(endence)g(graph\))f (and)h(remo)n(v)n(es)d(it)k(from)e(the)0 1648 y(graph.)84 b(This)44 b(step)g(is)g(rep)r(eated)f(un)n(til)i(the)f(graph)e(is)0 1748 y(empt)n(y)-7 b(.)42 b(The)29 b(order)e(in)j(whic)n(h)f(the)g (instructions)g(are)f(re-)0 1848 y(mo)n(v)n(ed)i(is)h(the)h(rev)n(erse) d(instruction)i(order)e(of)i(the)h(basic)0 1947 y(blo)r(c)n(k.)83 2051 y(One)d(problem)f(in)i(writing)e(a)h(fast)g(instruction)g(sc)n (hed-)0 2151 y(uler)20 b(is)f(determining)h(the)h(leaders)d(quic)n(kly) i(at)f(ev)n(ery)g(step.)0 2251 y(W)-7 b(e)26 b(use)g(the)g(follo)n (wing)e(metho)r(d:)37 b(When)26 b(the)g(ML)f(graph)0 2350 y(is)d(built,)j(the)e(n)n(um)n(b)r(er)f(of)g(dep)r(endence)h (references)f(to)g(the)0 2450 y(no)r(de)34 b(is)g(stored)f(in)i Ft(ml-count)p Fv(.)53 b(When)35 b(an)f(instruction)0 2549 y(is)g(selected)g(during)f(sc)n(heduling,)i(the)g(reference)e (coun)n(ts)0 2649 y(of)27 b(all)g(the)g(ML)g(no)r(des)g(on)g(whic)n(h)f (it)i(dep)r(ends)f(are)f(decre-)0 2749 y(men)n(ted;)41 b(if)c(a)f(reference)g(coun)n(t)g(reac)n(hes)f(0,)j(the)f(corre-)0 2848 y(sp)r(onding)27 b(ML)h(no)r(de)g(is)f(added)h(to)f(the)h(set)g (of)g(leader)e(in-)0 2948 y(structions.)83 3052 y(Some)34 b(ML)f(no)r(des,)j(e.g.,)f(no)r(des)e(that)h(corresp)r(ond)e(to)0 3152 y Ft(I)p 49 3152 27 4 v 31 w(REG)h Fv(IL)h(no)r(des,)i(do)e(not)g (generate)f(an)n(y)h(instructions.)0 3251 y(These)25 b(no)r(des)g(get)h(exaggerated)d(reference)h(coun)n(ts)h(\(e.g.,)0 3351 y(in)33 b(Fig.)f(6)g(the)h(ha)n(v)n(e)e(coun)n(t)i(2,)g(but)g (only)f(one)g(reference)0 3451 y(eac)n(h\),)f(so)f(they)h(nev)n(er)f(b) r(ecome)h(leaders)f(and)g(are)g(nev)n(er)0 3550 y(sc)n(heduled.)35 b(This)24 b(a)n(v)n(oids)f(a)g(go)r(o)r(d)h(amoun)n(t)f(of)h(w)n(ork)f (dur-)0 3650 y(ing)44 b(sc)n(heduling)g(and)g(co)r(de)g(emission;)52 b(it)45 b(also)e(mak)n(es)0 3749 y(dealing)35 b(with)g(the)h(load)e (dela)n(y)g(slots)h(of)g(the)h(MIPS)f(ar-)0 3849 y(c)n(hitecture)27 b(a)h(lot)f(easier.)83 3953 y(Our)22 b(data)h(structure)f(allo)n(ws)g (\014nding)h(quic)n(kly)g(the)g(ML)0 4053 y(no)r(des)g(on)f(whic)n(h)h (a)f(giv)n(en)g(ML)h(no)r(de)g(dep)r(ends,)h(but)f(\014nd-)0 4152 y(ing)i(the)h(ML)g(no)r(des)f(that)h(dep)r(end)g(on)g(a)f(giv)n (en)g(ML)g(no)r(de)0 4252 y(is)c(slo)n(w.)33 b(Therefore,)22 b(w)n(e)e(c)n(hose)g(a)g(bac)n(kw)n(ards)f(sc)n(heduling)0 4352 y(strategy)-7 b(.)0 4591 y Fr(4.3.3)94 b(Heuristic)0 4753 y Fv(The)21 b(selection)f(heuristic)g(determines)g(the)h(qualit)n (y)f(of)h(the)0 4852 y(sc)n(hedule.)45 b(An)31 b(o)n(v)n(erview)d(can)i (b)r(e)h(found)g(in)g([SKAH91)o(].)0 4952 y(The)d(heuristic)f(w)n(e)g (use)h(is:)0 5153 y Fr(largest)k(latest)h(execution)f(time)g(\(LET\))43 b Fv(The)166 5252 y(LET)37 b(of)g(an)g(instruction)g(is)g(the)h(last)f (cycle)g(when)166 5352 y(the)51 b(instruction)f(can)h(start)f (executing)g(without)166 5451 y(causing)38 b(an)n(y)g(later)h (instruction)f(to)h(stall)g(w)n(aiting)166 5551 y(for)27 b(the)h(result.)37 b(Ties)27 b(are)g(brok)n(en)f(b)n(y)0 5735 y Fr(maxim)m(um)32 b(path)h(length)41 b Fv(The)j(path)f(length)h (is)f(the)166 5835 y(sum)i(of)f(the)i(latencies)e(along)f(the)i (longest)f(path)2097 83 y(from)24 b(the)h(start)e(of)i(the)f(basic)g (blo)r(c)n(k)3253 53 y Fo(3)3289 83 y Fv(.)36 b(This)24 b(heuris-)2097 183 y(tic)41 b(exp)r(oses)f(dela)n(y)f(slots)h(early)-7 b(,)43 b(while)d(there)h(are)2097 282 y(other)27 b(instructions)g(to)h (\014ll)g(them.)2014 477 y(The)39 b(LET)g(is)f(stored)h(in)g Ft(ml-let)p Fv(,)g(the)g(path)h(length)1931 577 y(in)d Ft(ml-pathlength)p Fv(.)57 b(The)36 b(path)g(length)g(is)g(computed) 1931 677 y(b)r(efore)50 b(the)h(sc)n(heduler)f(prop)r(er)g(starts,)55 b(whereas)49 b(the)1931 776 y(LET)23 b(is)f(determined)h(during)g(sc)n (heduling)f(\(therefore)g(the)1931 876 y(LET)37 b(v)-5 b(alues)37 b(sho)n(wn)g(in)g(Fig.)h(6)f(are)f(not)h(useful\).)67 b(F)-7 b(or)1931 976 y(b)r(oth)27 b(computations)f(the)g(latency)g(of)g (the)h(instruction)f(is)1931 1075 y(needed;)i(it)g(is)g(stored)e(in)i Ft(ml-latency)p Fv(.)1931 1324 y Fj(4.4)113 b(Lo)s(cal)37 b(Register)f(Allo)s(cation)1931 1483 y Fv(Lo)r(cal)i(register)e(allo)r (cation)h(assigns)g(registers)f(to)i(most)1931 1583 y(ML)28 b(no)r(des.)2014 1685 y(Some)41 b(no)r(des)g(already)e(ha)n(v)n(e)h (registers)f(b)r(efore)h(lo)r(cal)1931 1785 y(register)19 b(allo)r(cation:)32 b(no)r(des)20 b(that)h(compute)f(stac)n(k)g(p)r (oin)n(t-)1931 1885 y(ers)j(or)f(that)h(compute)g(stac)n(k)f(items)h (that)h(reside)e(in)h(regis-)1931 1984 y(ters;)k(and)f Ft(I)p 2325 1984 V 31 w(REG)f Fv(no)r(des)i(that)f(represen)n(t)g(stac) n(k)f(p)r(oin)n(ters)1931 2084 y(or)36 b(stac)n(k)g(items)h(in)g (registers.)63 b(I.e.,)39 b(all)d(registers)f(that)1931 2184 y(liv)n(e)28 b(at)g(the)g(basic)f(blo)r(c)n(k)h(b)r(oundaries:)37 b Ft(I)p 3262 2184 V 31 w(REG)26 b Fv(no)r(des)i(for)1931 2283 y(registers)35 b(that)j(liv)n(e)e(at)h(the)g(start)g(of)f(the)i (basic)e(blo)r(c)n(k,)1931 2383 y(other)28 b(no)r(des)g(for)f (registers)f(that)j(liv)n(e)f(at)f(its)i(end.)38 b(Stac)n(k)1931 2482 y(items)31 b(in)f(registers)e(arise)h(from)h(some)f(sort)h(of)g (global)e(or)1931 2582 y(in)n(terpro)r(cedural)e(register)g(allo)r (cation.)2014 2685 y(These)42 b(register)f(n)n(um)n(b)r(ers)g(are)g (put)i(in)g(the)f Ft(il-reg)1931 2784 y Fv(\014eld)36 b(of)f(the)h(IL)f(and)g(are)g(copied)g(to)g(the)g Ft(ml-reg)e Fv(\014eld)1931 2884 y(during)g(ML)h(graph)e(construction.)54 b(This)33 b(relies)g(on)g(the)1931 2984 y(fact)27 b(that)f(the)g(IL)h (no)r(des)f(with)g(prede\014ned)g(registers)f(are)1931 3083 y(ro)r(ots)33 b(of)h(trees)f(that)i(are)d(reduced)i(to)g Ft(reg)p Fv(.)55 b(F)-7 b(or)33 b Ft(I)p 3623 3083 V 31 w(REG)1931 3183 y Fv(no)r(des)h(this)h(is)g(determined)f(b)n(y)g (the)h(grammar,)f(for)g(the)1931 3283 y(compute)25 b(no)r(des)f(this)h (is)f(ensured,)h(b)r(ecause)f(these)h(no)r(des)1931 3382 y(are)i(ro)r(ots)f(of)i(the)g(IL)g(graph.)2014 3485 y(If)f(an)f(ML)h (no)r(de)f(has)g(not)h(y)n(et)f(b)r(een)h(assigned)e(a)h(regis-)1931 3585 y(ter,)i(its)f Ft(ml-reg)f Fv(\014eld)i(con)n(tains)e Ft(regs-unused)p Fv(.)2014 3687 y(The)59 b(lo)r(cal)f(register)f(allo)r (cator)g(w)n(alks)h(bac)n(kw)n(ards)1931 3787 y(\(starting)38 b(at)g(the)h(instruction)f(that)h(will)g(b)r(e)g(executed)1931 3887 y(last\))34 b(through)f(the)i(arra)n(y)c(of)j(ML)g(no)r(des)g(pro) r(duced)g(b)n(y)1931 3986 y(the)23 b(sc)n(heduler.)34 b(F)-7 b(or)21 b(ev)n(ery)g(ML)h(no)r(de,)i(it)e(en)n(ters)f(the)i (reg-)1931 4086 y(ister)28 b(that)g(the)h(ML)f(no)r(de)g(computes)g(to) g(the)g(list)h(of)f(free)1931 4185 y(registers;)37 b(some)e(registers,) g(e.g.,)i(stac)n(k)d(p)r(oin)n(ters,)i(can-)1931 4285 y(not)31 b(b)r(e)h(freed.)47 b(Then)31 b(it)g(tak)n(es)f(registers)g (from)g(the)i(free)1931 4385 y(list)k(and)f(assigns)e(them)j(to)f(the)h (y)n(et)f(unassigned)f(input)1931 4484 y(registers)26 b(of)i(the)g(ML)f(no)r(de.)2014 4587 y(The)21 b(input)g(registers)e(of) h(an)g(ML)g(no)r(de)h(are)e(the)i Ft(ml-reg)1931 4687 y Fv(\014elds)39 b(of)g(the)h(c)n(hildren)e(\()p Ft(ml-left)f Fv(and)i Ft(ml-right)p Fv(\))d(of)1931 4786 y(the)24 b(no)r(de.)36 b(F)-7 b(or)23 b(this)h(reason,)f(w)n(e)h(ha)n(v)n(e)e (ML)i(no)r(des)g(corre-)1931 4886 y(sp)r(onding)j(to)g(the)g Ft(I)p 2576 4886 V 31 w(REG)f Fv(IL)h(no)r(des,)g(ev)n(en)g(though)g (these)1931 4986 y(ML)h(no)r(des)f(do)h(not)f(generate)g(an)g (instruction.)1931 5218 y Fr(4.4.1)94 b(Register)31 b(Sh)m(u\017ing) 1931 5377 y Fv(One)g(of)h(the)f(problems)g(that)h(w)n(e)f(get)g(if)h(w) n(e)f(try)g(to)g(k)n(eep)1931 5477 y(stac)n(k)23 b(items)i(in)f (registers)e(across)g(basic)i(blo)r(c)n(ks)f(is:)35 b(Some)1931 5576 y(registers)21 b(ma)n(y)g(liv)n(e)h(at)g(the)g(start)g(of)g(the)h (basic)e(blo)r(c)n(k)h(and)1931 5676 y(at)h(the)g(end,)h(but)g(don't)e (con)n(tain)h(the)g(same)f(thing;)j(at)d(the)p 1931 5758 740 4 v 2024 5811 a Fl(3)2058 5835 y Fp(The)i(path)h(length)g(is)e (de\014ned)i(di\013eren)n(tly)f(in)f([SKAH91].)p eop %%Page: 8 8 8 7 bop 0 83 a Fv(end)25 b(a)g(register)f(ma)n(y)g(con)n(tain)h (something)g(that)g(w)n(as)f(in)i(a)0 183 y(di\013eren)n(t)i(register)e (at)h(the)h(start.)83 361 y(A)40 b(particularly)f(nast)n(y)g(v)n (ersion)f(of)i(this)g(problem)f(is)0 460 y(this:)61 b(Assume)40 b(that)f Fg(x)h Fv(is)g(in)g Ft($1)e Fv(at)i(the)g(start)e(of)i(the)0 560 y(basic)23 b(blo)r(c)n(k)g(and)g(should)h(b)r(e)g(in)g Ft($2)f Fv(at)g(the)h(end,)h(whereas)0 660 y Fg(y)33 b Fv(starts)c(in)i Ft($2)e Fv(and)h(ends)h(up)f(in)h Ft($1)p Fv(.)44 b(The)30 b(solution)g(for)0 759 y(this)e(problem)g (needs)g(three)g(mo)n(v)n(es.)37 b(Ho)n(w)28 b(can)g(w)n(e)g(solv)n(e)0 859 y(the)g(problem)f(in)h(general?)83 1037 y(The)19 b(solution)f(w)n(e)g(use)g(is)h(to)f(access)g(the)h(input)g(registers)0 1137 y(through)36 b Ft(I)p 372 1137 27 4 v 31 w(MOVE)f Fv(no)r(des)h(instead)h(of)g(directly)f(through)0 1236 y Ft(I)p 49 1236 V 31 w(REG)28 b Fv(no)r(des.)43 b(W)-7 b(e)29 b(insert)h(dep)r(endence)g(edges)e(b)r(et)n(w)n(een)0 1336 y(the)36 b(mo)n(v)n(e)e(from)h(a)g(register)e(and)i(the)h(no)r(de) f(that)h(com-)0 1436 y(putes)28 b(that)f(register;)g(this)g(ensures)g (that)h(the)f(register)f(is)0 1535 y(copied)e(to)h(a)f(temp)r(orary)f (register)g(b)r(efore)h(it)h(is)g(o)n(v)n(erwrit-)0 1635 y(ten.)83 1813 y(If)42 b(an)f(input)h(register)e(has)h(to)g(mo)n(v)n(e) f(to)i(an)f(output)0 1913 y(register)34 b(without)j(an)e(in)n (termediate)h(computation,)i(w)n(e)0 2012 y(ma)n(y)c(ha)n(v)n(e)f(to)h (insert)h(another)e Ft(I)p 1092 2012 V 31 w(MOVE)g Fv(no)r(de)h(for)g (mo)n(v-)0 2112 y(ing)25 b(that)h(register)e(to)h(its)g(\014nal)h (destination,)f(th)n(us)h(allo)n(w-)0 2212 y(ing)38 b(the)h(v)-5 b(alue)39 b(to)f(mo)n(v)n(e)g(in)n(to)g(a)h(temp)r(orary)e(if)i(neces-) 0 2311 y(sary)-7 b(.)45 b(If)31 b(w)n(e)f(did)h(not)g(add)f(an)n(y)i Ft(I)p 1096 2311 V 31 w(MOVE)d Fv(no)r(des,)i(the)g(ad-)0 2411 y(ditional)24 b(dep)r(endences)h(could)g(form)f(a)g(cycle)h(\(and) f(break)0 2511 y(the)41 b(sc)n(heduler\).)74 b(Adding)41 b(the)f(minim)n(um)h(n)n(um)n(b)r(er)f(of)0 2610 y Ft(I)p 49 2610 V 31 w(MOVE)20 b Fv(no)r(des)h(that)h(do)r(es)f(not)g(in)n(tro) r(duce)g(cycles)g(is)g(quite)0 2710 y(complex)27 b(and)h(probably)e (slo)n(w.)83 2888 y(W)-7 b(e)35 b(use)f(the)g(follo)n(wing)f(fast,)j (but)f(sub)r(optimal)f(solu-)0 2988 y(tion:)56 b(Consider)36 b(mo)n(ving)h(a)g(v)-5 b(alue)37 b(from)g(register)e Fg(a)i Fv(to)0 3087 y(register)e Fg(b)p Fv(,)k(with)e Fg(b)f Fv(con)n(taining)f(another)h(v)-5 b(alue)37 b(at)f(the)0 3187 y(start)30 b(of)g(the)h(basic)f(blo)r(c)n(k.)45 b(If)31 b(the)g(destination)f(register)0 3286 y(of)f(the)h(mo)n(v)n(e)e (from)g Fg(b)h Fv(is)g(unassigned,)g(w)n(e)g(set)g(the)g(desti-)0 3386 y(nation)j(register)f(of)h(the)h(mo)n(v)n(e)e(from)h Fg(a)g Fv(to)g Fg(b)p Fv(;)i(otherwise)0 3486 y(w)n(e)d(in)n(tro)r (duce)f(another)g(mo)n(v)n(e,)h(with)h(the)f(mo)n(v)n(e)f(from)g Fg(a)0 3585 y Fv(as)i(source)f(and)i Fg(b)f Fv(as)g(destination.)52 b(This)32 b(sc)n(heme)g(elim-)0 3685 y(inates)e(the)g(danger)f(of)h (cycles)f(and)h(in)n(tro)r(duces)g(at)g(most)0 3785 y(half)k(as)f(man)n (y)h Ft(I)p 560 3785 V 31 w(MOVE)e Fv(no)r(des)i(as)f(the)h(straigh)n (tforw)n(ard)0 3884 y(approac)n(h)26 b(\(alw)n(a)n(ys)g(creating)g(an)h Ft(I)p 1138 3884 V 31 w(MOVE)f Fv(no)r(de\).)83 4062 y(No)n(w,)h(w)n(e)g(w)n(an)n(t)g(to)g(a)n(v)n(oid)f(actually)h (generating)e(mo)n(v)n(e)0 4162 y(instructions)g(if)h(p)r(ossible.)35 b(This)26 b(is)f(p)r(ossible)g(if)h(the)f(mo)n(v)n(e)0 4262 y(copies)40 b(the)h(register)f(to)g(itself.)77 b(So,)44 b(w)n(e)c(enhance)h(the)0 4361 y(register)31 b(allo)r(cator)f(lik)n(e)i (this:)46 b(When)32 b(it)h(encoun)n(ters)e(an)0 4461 y(instruction)19 b Fg(I)27 b Fv(whose)19 b(result)g(is)h(in)g(an)f (input)h(register,)g(the)0 4561 y(register)f(allo)r(cator)g(lo)r(oks)h (at)h(the)g(ML)f(no)r(de)h(for)f(the)h(mo)n(v)n(e)0 4660 y(from)f(that)h(register.)33 b(If)21 b(the)f(mo)n(v)n(e)g(has)g(no)g (result)g(register)0 4760 y(assigned)26 b(to)h(it)h(y)n(et,)f(the)h (register)e(allo)r(cator)f(assigns)h(the)0 4859 y(input)c(register)e (\(and)h(tak)n(es)g(it)g(from)g(the)h(free)f(list\).)35 b(If)22 b(the)0 4959 y(mo)n(v)n(e)37 b(has)g(a)h(result)f(register,)j (this)e(means)f(that)i(there)0 5059 y(is)e(an)g(instruction)g(b)r (ehind)h Fg(I)44 b Fv(that)38 b(uses)f(the)g(result)g(of)0 5158 y(the)32 b(mo)n(v)n(e,)g(so)f(w)n(e)h(cannot)f(a)n(v)n(oid)f(the)j (mo)n(v)n(e)d(\(with)j(this)0 5258 y(sc)n(hedule\).)83 5436 y(There)27 b(is)h(one)g(more)f(reason)f(for)h(in)n(tro)r(ducing)i Ft(I)p 1648 5436 V 31 w(MOVE)0 5536 y Fv(no)r(des:)k(Eac)n(h)20 b(op)r(eration)f(has)h(only)g(one)g(destination)h(reg-)0 5635 y(ister;)k(if)g(the)g(result)f(of)h(a)f(computation)g(should)g (reside)g(in)0 5735 y Fg(n)d Fv(registers)f(at)h(the)h(end)f(of)g(the)h (basic)f(blo)r(c)n(k,)h Fg(n)6 b Fu(\000)g Fv(1)20 b(mo)n(v)n(es)0 5835 y(are)27 b(necessary)e(to)j(get)f(it)h(there.)p 1931 3 1849 4 v 2839 122 a Ff(#)p Fe(linea)n(r)h(rep)n(resentation)p 2424 174 892 4 v 2424 423 4 250 v 2502 268 a(build)g(IL)e(graph)2502 368 y(lab)r(el)i(\(inst.)38 b(selection\))p 3311 423 V 2424 426 892 4 v 2839 534 a Ff(#)p Fe(IL)28 b(graph)p 2205 585 1329 4 v 2205 1034 4 449 v 2283 680 a(reduce)f(\(inst.)38 b(selection\))2283 780 y(build)29 b(ML)e(graph)g(\(inst.)38 b(selection\))2283 879 y(count)27 b(references)h(\(scheduling\))2283 979 y(compute)e(path)h(length)h(\(scheduling\))p 3530 1034 V 2205 1037 1329 4 v 2839 1145 a Ff(#)p Fe(ML)f(graph)p 2501 1196 737 4 v 2501 1445 4 250 v 2579 1291 a(schedule)2579 1391 y(allo)r(cate)i(registers)p 3234 1445 V 2501 1448 737 4 v 2839 1557 a Ff(#)p Fe(ML)e(a)n(rra)n(y)p 2621 1608 497 4 v 2621 1758 4 150 v 2699 1703 a(emit)g(co)r(de)p 3114 1758 V 2621 1761 497 4 v 2839 1869 a Ff(#)p Fe(co)r(de)p 1931 1931 1849 4 v 1931 2072 a Fv(Figure)e(9:)35 b(Phases,)24 b(passes)g(and)h(data)f(structures)g(in)h(our)1931 2171 y(co)r(de)j(generator)1931 2441 y Fj(4.5)113 b(Co)s(de)37 b(Emission)1931 2599 y Fv(Co)r(de)22 b(emission)f(just)h(w)n(alks)f (forw)n(ard)f(through)h(the)h(arra)n(y)1931 2699 y(of)31 b(ML)f(no)r(des,)h(and)g Ft(EXECUTE)p Fv(s)c(the)k(XTs)g(stored)e(in)i (the)1931 2798 y Ft(ml-asm)c Fv(\014elds.)41 b(These)29 b(w)n(ords)f(collect)h(the)g(information)1931 2898 y(stored)e(in)g(the) g Ft(ml-val)e Fv(and)i Ft(ml-reg)e Fv(\014elds)i(of)g(the)h(no)r(de) 1931 2997 y(and)i(its)g(c)n(hildren,)g(and)g(call)g(the)g(righ)n(t)f (assem)n(bler)g(w)n(ord)1931 3097 y(for)e(generating)f(the)i(co)r(de.) 2014 3199 y(The)54 b(co)r(de)f(emitter)g(also)f(deals)h(with)h(load)e (dela)n(y)1931 3299 y(slots:)61 b(The)40 b(co)r(de)f(emission)h(action) f(for)g(load)g(instruc-)1931 3398 y(tions)25 b(c)n(hec)n(ks)e(whether)h (the)h(next)g(ML)f(no)r(de)h(dep)r(ends)g(on)1931 3498 y(the)31 b(load)f(through)g(a)g(\015o)n(w)g(dep)r(endence;)i(if)f(y)n (es,)f(it)h(gen-)1931 3598 y(erates)e(a)g Ft(nop)g Fv(ofter)g(the)h (load.)43 b(Branc)n(h)28 b(dela)n(y)h(slots)h(are)1931 3697 y(handled)e(simply)g(b)n(y)f(\014lling)h(them)g(with)g Ft(nop)p Fv(s)3423 3667 y Fo(4)3459 3697 y Fv(.)1931 3942 y Fj(4.6)113 b(P)m(asses)1931 4099 y Fv(While)29 b(w)n(e)f(w)n(ould)g(prefer)g(to)g(k)n(eep)g(the)h(di\013eren)n(t)f (phases)1931 4199 y(separate)j(for)g(soft)n(w)n(are)g(engineering)g (reasons,)g(w)n(e)h(ha)n(v)n(e)1931 4299 y(in)n(tegrated)26 b(them)h(to)f(impro)n(v)n(e)f(the)i(compile)g(time.)37 b(This)1931 4398 y(results)30 b(in)h(the)h(follo)n(wing)d(passes)h(o)n (v)n(er)f(the)i(data)f(struc-)1931 4498 y(tures)e(\(see)f(Fig.)h(9\):) 2014 4690 y Fu(\017)41 b Fv(While)33 b(building)f(the)g(IL)g(graph,)g (w)n(e)f(also)g(p)r(erform)2097 4790 y(the)d(lab)r(elling)g(part)f(of)g (co)r(de)h(selection.)2014 4965 y Fu(\017)41 b Fv(Then)31 b(w)n(e)g(p)r(erform)g(the)g(reducer)f(part)g(of)h(co)r(de)g(se-)2097 5065 y(lection)21 b(as)f(a)g(recursiv)n(e)e(graph)i(w)n(alk.)33 b(Up)r(on)21 b(return-)2097 5164 y(ing)i(from)f(the)h(recursion,)f(w)n (e)h(build)g(the)g(ML)g(graph,)2097 5264 y(coun)n(t)g(the)h(references) e(to)h(eac)n(h)g(no)r(de)g(and)h(compute)2097 5363 y(the)k(path)g (length)g(for)f(the)h(sc)n(heduler.)p 1931 5442 740 4 v 2024 5496 a Fl(4)2058 5519 y Fp(The)20 b(ob)n(vious)f(approac)n(h)h (to)f(utilizing)g(them)g(w)n(ould)g(b)r(e)g(a)g(mo)r(d-)1931 5598 y(i\014ed)27 b(sc)n(heduler;)i(ho)n(w)n(ev)n(er,)g(this)d(approac) n(h)j(is)d(not)i(w)n(ork)l(able,)f(b)r(e-)1931 5677 y(cause)e(some)e (ML)g(no)r(des)i(corresp)r(ond)f(to)g(more)f(than)h(one)h(instruc-)1931 5756 y(tion)30 b(\(due)g(to)f(other)h(w)n(arts)f(in)g(the)h(MIPS)f(arc) n(hitecture\),)j(and)d(it)1931 5835 y(w)n(ould)24 b(not)h(do)f(to)g (put)g(suc)n(h)g(a)g(no)r(de)h(b)r(ehind)f(a)g(branc)n(h.)p eop %%Page: 9 9 9 8 bop 0 3 1849 4 v 864 130 4 92 v 1193 103 a Fd(pro)r(ducing)221 146 y(relativ)n(e)26 b(time)p 864 222 V 901 194 a(threaded)f(co)r(de)67 b(nativ)n(e)25 b(co)r(de)p 0 225 1854 4 v 360 289 a(threaded)g(co)r(de) p 864 316 4 92 v 405 w(1)p Fc(:)p Fd(00)313 b(4)p Fc(:)p Fd(03)33 332 y(running)405 380 y(nativ)n(e)25 b(co)r(de)p 864 408 V 510 w(|)311 b(2)p Fc(:)p Fd(95)p 0 455 1849 4 v 0 596 a Fv(Figure)26 b(10:)36 b(Relativ)n(e)26 b(compile)h(times)g (of)g(di\013eren)n(t)g(com-)0 695 y(pilers)j(executed)h(with)g (di\013eren)n(t)g(execution)g(tec)n(hniques)0 795 y(\(compiling)c(the)h (RAFTS)h(protot)n(yp)r(e\))83 1071 y Fu(\017)41 b Fv(The)d(next)h(pass) e(p)r(erforms)g(sc)n(heduling)h(and)g(lo)r(cal)166 1171 y(register)25 b(allo)r(cation,)h(starting)f(at)i(the)g(last)f(instruc-) 166 1270 y(tion,)i(and)f(pro)r(ceeding)g(to)g(the)h(\014rst.)83 1449 y Fu(\017)41 b Fv(Finally)-7 b(,)33 b(the)g(co)r(de)f(is)g (emitted)h(in)f(a)g(forw)n(ard)e(pass)166 1549 y(o)n(v)n(er)c(the)i(sc) n(heduled)f(co)r(de.)83 1744 y(Note)34 b(that)g(the)h(use)f(of)g(bac)n (kw)n(ard)e(sc)n(heduling)h(sa)n(v)n(es)0 1843 y(t)n(w)n(o)27 b(passes.)0 2135 y Fs(5)135 b(P)l(erformance)0 2322 y Fv(All)30 b(timings)f(rep)r(orted)g(here)g(w)n(ere)f(tak)n(en)h(on)g(a) g(DecSta-)0 2422 y(tion)f(5000/200)23 b(\(25MHz)28 b(R3000\))e(with)i (40MB)f(RAM.)0 2671 y Fj(5.1)112 b(Compilation)35 b(Sp)s(eed)0 2830 y Fv(The)41 b(in)n(tro)r(duction)g(of)h(the)f(faster)g(sc)n (heduler)g(and)g(the)0 2930 y(in)n(tegrated)32 b(pass)h(structure)g (has)g(caused)g(a)g(sp)r(eedup)h(in)0 3029 y(compilation)h(sp)r(eed)i (b)n(y)e(a)h(factor)f(of)h(t)n(w)n(o)f(o)n(v)n(er)g(the)h(re-)0 3129 y(sults)27 b(in)h([EP96)n(],)g(ev)n(en)e(though)h(w)n(e)g(also)g (added)g(the)g(lin-)0 3228 y(ear)32 b(in)n(termediate)g(co)r(de.)51 b(Y)-7 b(ou)33 b(can)f(\014nd)h(a)f(compilaton)0 3328 y(sp)r(eed)h(comparison)f(of)h(Gforth's)g(compiler)g(\(pro)r(ducing)0 3428 y(threaded)26 b(co)r(de\))h(and)f(RAFTS)h(in)g(Fig.)g(10:)35 b(the)27 b(curren)n(t)0 3527 y(RAFTS)40 b(protot)n(yp)r(e)e(\(running)h (in)h(nativ)n(e)f(co)r(de\))g(com-)0 3627 y(piles)32 b(itself)h(2.95)e(times)h(slo)n(w)n(er)f(than)h(Gforth)g(\(running)0 3727 y(in)f(threaded)f(co)r(de\))g(compiles)g(it.)45 b(The)31 b(sp)r(eedup)g(of)f(the)0 3826 y(nativ)n(e)39 b(co)r(de)g(v)n(ersion)e(of)i(RAFTS)h(o)n(v)n(er)d(the)j(threaded)0 3926 y(co)r(de)34 b(v)n(ersion)f(is)i(1.37;)h(w)n(e)e(attribute)h(this) g(disapp)r(oin)n(t-)0 4025 y(ing)23 b(sp)r(eedup)g(to)g(the)g(high)g(n) n(um)n(b)r(er)g(of)g(calls)f(to)h(threaded)0 4125 y(co)r(de)k(w)n (ords.)83 4228 y(Figure)e(11)f(sho)n(ws)h(some)g(n)n(um)n(b)r(ers)g(on) g(the)h(size)f(of)g(our)0 4327 y(protot)n(yp)r(e)42 b(and)g(on)h(the)g (absolute)f(sp)r(eed.)82 b(Y)-7 b(ou)43 b(ma)n(y)0 4427 y(w)n(onder)h(ab)r(out)g(the)h(discrepancy)f(in)h(the)g(n)n(um)n(b)r (er)f(of)0 4527 y Ft(COMPILE,)p Fv(s)32 b(and)j(linear)f(IR)i(w)n (ords;)h(note)f(that)f(literals)0 4626 y(and)24 b(w)n(ords)f(with)i(sp) r(ecial)f(compilation)g(seman)n(tics)f(\(e.g.,)0 4726 y Ft(IF)i Fv(and)h Ft(;)p Fv(\))h(are)e(not)h(COMPILE,d,)f(and)h(they)g (ma)n(y)f(gen-)0 4826 y(erate)e(more)h(than)g(one)g(linear)f(IR)i(w)n (ord)e(\(e.g.,)h Ft(ELSE)f Fv(gen-)0 4925 y(erates)k(four\).)83 5028 y(W)-7 b(e)22 b(think)f(that)h(there)f(is)g(still)h(an)f (order-of-magnitude)0 5128 y(impro)n(v)n(emen)n(t)51 b(in)h(compile-time)g(p)r(ossible;)64 b(ho)n(w)n(ev)n(er,)0 5227 y(curren)n(tly)41 b(w)n(e)h(fo)r(cus)h(our)e(e\013orts)h(on)g(in)n (terpro)r(cedural)0 5327 y(register)26 b(allo)r(cation.)0 5576 y Fj(5.2)112 b(Co)s(de)38 b(Qualit)m(y)0 5735 y Fv(The)f(impro)n(v)n(emen)n(ts)e(in)i(the)g(co)r(de)g(generator)e(had)h (not)0 5835 y(only)25 b(p)r(ostitiv)n(e)h(e\013ects)g(on)g(the)g (compilation)f(sp)r(eed,)i(but)p 1931 3 V 2624 139 4 100 v 2691 109 a(items)99 b(cycles/item)p 1931 142 1517 4 v 1981 212 a(compile-time)28 b(\(s\))p 2624 242 4 100 v 165 w(9.89)180 b(25000000)p 1931 245 1517 4 v 1981 315 a(lines)p 2624 345 4 100 v 576 w(6411)303 b(38566)1981 414 y Ft(COMPILE,)p 2624 444 V 386 w Fv(6214)g(39789)1981 514 y(linear)27 b(IR)h(w)n(ords)p 2624 544 V 134 w(15940)303 b(15511)1981 614 y(IL)28 b(no)r(des)p 2624 643 V 380 w(32520)345 b(7603)1981 713 y(ML)28 b(no)r(des)p 2624 743 V 334 w(24687)303 b(10015)1981 813 y(nativ)n(e)27 b(co)r(de)h(cells)p 2624 843 V 102 w(26984)345 b(9162)p 1931 882 1849 4 v 1931 1022 a(Figure)41 b(11:)64 b(Size)42 b(of)g(the)g(compiler)f(and)g(compilation)1931 1122 y(sp)r(eed)36 b(\(absolute)g(and)f(in)i(cycles/item\);)i(this)d(is)g(not)g(a)1931 1222 y(split)28 b(of)g(the)g(time)g(in)n(to)f(v)-5 b(arious)27 b(subtasks.)p 1931 1367 V 2176 3044 a @beginspecial 79 @llx 88 @lly 242 @urx 285 @ury 1630 @rwi @setspecial %%BeginDocument: regs-vs-speed.eps %!PS-Adobe-2.0 EPSF-1.2 %%BoundingBox: 79 88 242 285 %%Pages: 1 1 %%DocumentFonts: Helvetica %%EndComments 1 setlinejoin 0 0 translate %.91 .91 scale 0.3 setlinewidth /over {1 index} def /pick {index} def /drop {pop} def /swap {exch} def %transformation /tf {80 mul 100 add exch 15 mul 100 add exch} def /mt {tf moveto} def /lt {tf lineto} def /tf1 {instructions div tf} def /mt1 {0 swap over swap tf1 moveto 1 add} def /lt1 {over swap tf1 lineto 1 add} def /instructions 1 def %bubble [] 0 setdash 1.74 mt1 1.75 lt1 1.75 lt1 1.75 lt1 1.76 lt1 1.76 lt1 1.76 lt1 1.77 lt1 pop stroke %fib [4 4] 0 setdash 1.19 mt1 0.93 lt1 0.99 lt1 1.07 lt1 1.13 lt1 1.18 lt1 1.26 lt1 1.32 lt1 pop stroke %mm [4 2 1 2] 0 setdash 1.18 mt1 1.10 lt1 1.04 lt1 1.0 lt1 1.01 lt1 1.02 lt1 1.02 lt1 1.03 lt1 pop stroke %siev [1 1] 0 setdash 1.80 mt1 1.72 lt1 1.71 lt1 1.77 lt1 1.85 lt1 1.83 lt1 1.87 lt1 1.87 lt1 pop stroke [] 0 setdash /xbase 0 def /ybase 0 def 0.5 setlinewidth xbase 2 mt xbase ybase lt 7 ybase lt stroke newpath /Helvetica findfont 9 scalefont setfont /xjright {dup stringwidth pop neg 0 rmoveto} def /xjcenter {dup stringwidth pop 2 div neg 0 rmoveto} def /yjtop {0 -7 rmoveto} def /yjcenter {0 -3.5 rmoveto} def 7.2 ybase mt (registers) yjcenter show xbase 2.21 mt (run time/) xjcenter show xbase 2.1 mt (C run time) xjcenter show /str 20 string def %x xtick /xtick { dup ybase mt 0 -2 rlineto 0 -2 rmoveto str cvs xjcenter yjtop show } def 0 xtick 1 xtick 2 xtick 3 xtick 4 xtick 5 xtick 6 xtick 7 xtick stroke /ytick { dup xbase exch mt -2 0 rlineto -2 0 rmoveto str cvs xjright yjcenter show } def 0 ytick 0.5 ytick 1 ytick 1.5 ytick 2 ytick stroke /xlabel 200 def /ylabel 130 def 0.3 setlinewidth xlabel ylabel 20 add moveto (bubble) xjright yjcenter show [] 0 setdash xlabel 10 add ylabel 20 add moveto 20 0 rlineto stroke xlabel ylabel 10 add moveto (fib) xjright yjcenter show [4 4] 0 setdash xlabel 10 add ylabel 10 add moveto 20 0 rlineto stroke xlabel ylabel moveto (matrix-mult) xjright yjcenter show [4 2 1 2] 0 setdash xlabel 10 add ylabel moveto 20 0 rlineto stroke xlabel ylabel -10 add moveto (sieve) xjright yjcenter show [1 1] 0 setdash xlabel 10 add ylabel -10 add moveto 20 0 rlineto stroke %%EndDocument @endspecial 1931 3083 V 1931 3224 a(Figure)38 b(12:)58 b(Co)r(de)38 b(qualit)n(y)g(of)h(RAFTS)g(with)g(v)-5 b(arying)1931 3323 y(n)n(um)n(b)r(ers)36 b(of)h(stac)n(k)e(items)i(in)g (registers,)g(scaled)f(to)g(the)1931 3423 y(run-time)28 b(of)f(co)r(de)h(pro)r(duced)f(b)n(y)i Ft(gcc-2.5.8)39 b(-O2)1931 3717 y Fv(also)c(on)h(the)g(co)r(de)g(qualit)n(y)g(\(b)r (etter)g(instruction)g(selec-)1931 3816 y(tion)i(and)g(sc)n (heduling\).)68 b(W)-7 b(e)38 b(ha)n(v)n(e)f(also)g(implemen)n(ted)1931 3916 y(our)28 b(suggestion)f(\(in)i([EP96)n(]\))f(to)h(k)n(eep)e(the)i (top)f(of)h(stac)n(k)1931 4015 y(\(or)23 b(more)g(stac)n(k)g(items\))h (in)g(registers)e(across)g(basic)h(blo)r(c)n(k)1931 4115 y(b)r(oundaries,)36 b(with)g(a)e(\014xed)h(mapping)g(\(i.e.,)i(not)e(a) g(real)1931 4215 y(global)f(or)h(in)n(terpro)r(cedural)e(register)h (allo)r(cation,)i(more)1931 4314 y(lik)n(e)27 b(a)h(calling)f(con)n(v)n (en)n(tion\).)2014 4427 y(Figure)h(12)g(sho)n(ws)g(the)h(results,)f (relativ)n(e)g(to)g(the)h(com-)1931 4527 y(bination)g(of)g(forth2c)g ([EM95)n(])h(and)f(gcc-2.5.8)d(-O2.)41 b(The)1931 4626 y(n)n(um)n(b)r(er)e(of)f(registers)f(seems)h(to)h(ha)n(v)n(e)e(little)i (in\015uence)1931 4726 y(here,)28 b(but,)h(based)e(on)h(the)h(results)e (in)i([Ert95)n(],)f(w)n(e)g(think)1931 4825 y(that)i(this)f(is)g(due)g (to)g(the)g(c)n(hoice)f(of)h(b)r(enc)n(hmarks)g(\(most)1931 4925 y(of)38 b(whic)n(h)h(do)e(most)h(w)n(ork)f(in)i(simple)f(coun)n (ted)g(lo)r(ops\),)1931 5025 y(and)32 b(is)f(not)h(v)-5 b(alid)32 b(in)g(general.)47 b(W)-7 b(e)32 b(think)g(that)g(in)g(gen-) 1931 5124 y(eral)37 b(the)h(results)f(lo)r(ok)g(more)g(lik)n(e)g(the)h (results)f(for)g(the)1931 5224 y(\014b)c(b)r(enc)n(hmark,)h(i.e.,)g(a)f (few)g(\014xed)f(registers)g(help,)i(but)1931 5324 y(more)28 b(h)n(urt)h(\(b)r(ecause)g(they)g(ha)n(v)n(e)f(to)h(b)r(e)h(mo)n(v)n (ed)e(around)1931 5423 y(whenev)n(er)f(a)g(basic)g(blo)r(c)n(k)g(c)n (hanges)f(the)i(stac)n(k)f(depth\).)2014 5536 y(Ov)n(erall,)42 b(the)f(results)e(are)g(quite)i(encouraging:)60 b(On)1931 5635 y(one)35 b(b)r(enc)n(hmark)e(RAFTS)j(b)r(eats)e(the)h (forth2c/gcc,)g(on)1931 5735 y(another)i(it)i(can)e(k)n(eep)h(up,)i (and)e(the)g(w)n(orst)f(one)h(has)f(a)1931 5835 y(slo)n(wdo)n(wn)k (factor)h(of)h(1.75.)81 b(Ho)n(w)n(ev)n(er,)44 b(these)f(b)r(enc)n(h-)p eop %%Page: 10 10 10 9 bop 0 83 a Fv(marks)34 b(are)g(v)n(ery)g(small,)j(and)e(the)g (results)g(for)f(realistic)0 183 y(programs)c(ma)n(y)h(b)r(e)i (di\013eren)n(t.)51 b(This)32 b(sho)n(ws)f(the)i(neces-)0 282 y(sit)n(y)39 b(of)g(larger)f(b)r(enc)n(hmark)g(programs)f(for)i(ev) -5 b(aluating)0 382 y(sophistsicated)27 b(compilers.)0 663 y Fs(6)135 b(Conclusion)0 847 y Fv(W)-7 b(e)23 b(ha)n(v)n(e)e (presen)n(ted)h(some)g(of)h(the)g(more)e(in)n(teresting)h(im-)0 947 y(plemen)n(tation)27 b(details)h(of)f(our)g(RAFTS)i(protot)n(yp)r (e:)83 1117 y Fu(\017)41 b Fv(Ho)n(w)30 b(w)n(e)f(com)n(bine)h(the)g (goals)e(of)i(in)n(tegration)f(with)166 1216 y(the)37 b(threaded)f(co)r(de)g(system)g(and)g(e\016cien)n(t)h(w)n(ord-)166 1316 y(sp)r(eci\014c)28 b(compilation)f(actions,)83 1487 y Fu(\017)41 b Fv(A)25 b(stac)n(k-based)e(threaded)h(co)r(de)h(in)n (termediate)f(rep-)166 1587 y(resen)n(tation)33 b(for)i(programs)d (that)j(allo)n(ws)e(dela)n(ying)166 1686 y(co)r(de)27 b(generation)g(un)n(til)h Ft(EXECUTE)p Fv(.)83 1857 y Fu(\017)41 b Fv(The)20 b(data)f(structures)f(and)i(algorithms)e(that)h (w)n(e)g(use)166 1957 y(in)28 b(basic)f(blo)r(c)n(k)g(co)r(de)g (generation.)0 2238 y Fs(Ac)l(kno)l(wledgemen)l(ts)0 2422 y Fv(Bernd)45 b(P)n(a)n(ysan,)i(Manfred)e(Bro)r(c)n(khaus)e(and)i (Andreas)0 2522 y(Krall)22 b(pro)n(vided)g(helpful)i(commen)n(ts)f(on)f (earlier)g(v)n(ersions)0 2621 y(of)28 b(this)f(pap)r(er.)0 2902 y Fs(References)0 3087 y Fv([DS84])167 b(L.)39 b(P)n(eter)e (Deutsc)n(h)i(and)f(Allen)h(M.)g(Sc)n(hi\013-)406 3186 y(man.)85 b(E\016cien)n(t)43 b(implemen)n(tation)h(of)g(the)406 3286 y(Smalltalk-80)63 b(system.)148 b(In)65 b Fn(Principles)406 3386 y(of)31 b(Pr)l(o)l(gr)l(amming)f(L)l(anguages)h(\(POPL'84\))p Fv(,)406 3485 y(pages)26 b(297{302,)f(1984.)0 3656 y([EM95])143 b(M.)34 b(An)n(ton)h(Ertl)f(and)g(Martin)g(Maierhofer.)406 3756 y(T)-7 b(ranslating)50 b(F)-7 b(orth)52 b(to)g(e\016cien)n(t)g(C.) 109 b(In)406 3855 y Fn(Eur)l(oF)-6 b(orth)42 b('95)h(Confer)l(enc)l(e)g (Pr)l(o)l(c)l(e)l(e)l(dings)p Fv(,)406 3955 y(Sc)n(hlo\031)26 b(Dagstuhl,)i(German)n(y)-7 b(,)27 b(1995.)0 4126 y([EP96])162 b(M.)51 b(An)n(ton)g(Ertl)g(and)g(Christian)f(Pirk)n(er.)406 4226 y(RAFTS)28 b(for)f(basic)h(blo)r(c)n(ks:)36 b(A)28 b(progress)d(re-)406 4325 y(p)r(ort)33 b(on)g(F)-7 b(orth)34 b(nativ)n(e)f(co)r(de)g(compilation.)406 4425 y(In)46 b Fn(Eur)l(oF)-6 b(orth)48 b('96)g(Confer)l(enc)l(e)g(Pr)l(o)l(c)l(e)l (e)l(d-)406 4525 y(ings)p Fv(,)28 b(St.)g(P)n(etersburg,)e(Russia,)h (1996.)0 4696 y([Ert92])154 b(M.)48 b(An)n(ton)h(Ertl.)98 b(A)49 b(new)f(approac)n(h)e(to)406 4795 y(F)-7 b(orth)42 b(nativ)n(e)g(co)r(de)g(generation.)78 b(In)43 b Fn(Eu-)406 4895 y(r)l(oF)-6 b(orth)51 b('92)p Fv(,)58 b(pages)50 b(73{78,)k(Southamp-)406 4994 y(ton,)25 b(England,)f(1992.)f(MicroPro)r (cessor)e(En-)406 5094 y(gineering.)0 5265 y([Ert95])154 b(M.)29 b(An)n(ton)g(Ertl.)40 b(Stac)n(k)29 b(cac)n(hing)f(for)g(in)n (ter-)406 5365 y(preters.)d(In)d Fn(SIGPLAN)h('95)i(Confer)l(enc)l(e)g (on)406 5464 y(Pr)l(o)l(gr)l(amming)k(L)l(anguage)h(Design)e(and)i(Im-) 406 5564 y(plementation)p Fv(,)e(pages)f(315{327,)d(1995.)0 5735 y([FHP92])103 b(Christopher)76 b(W.)h(F)-7 b(raser,)88 b(Rob)r(ert)77 b(R.)406 5835 y(Henry)-7 b(,)30 b(and)g(T)-7 b(o)r(dd)31 b(A.)f(Pro)r(ebsting.)43 b Fb(Bur)n(g)2337 83 y Fv(|)62 b(fast)g(optimal)g(instruction)g(selection)2337 183 y(and)45 b(tree)f(parsing.)86 b Fn(SIGPLAN)45 b(Notic)l(es)p Fv(,)2337 282 y(27\(4\):68{76,)24 b(April)k(1992.)34 b(Av)-5 b(ailable)27 b(from)2337 382 y(ftp://k)-5 b (aese.cs.wisc.edu/pub/burg.shar.Z.)1931 548 y([Pro95])144 b(T)-7 b(o)r(dd)48 b(A.)f(Pro)r(ebsting.)94 b(Burs)47 b(automata)2337 648 y(generation.)158 b Fn(A)n(CM)68 b(T)-6 b(r)l(ansactions)68 b(on)2337 747 y(Pr)l(o)l(gr)l(amming)49 b(L)l(anguages)f(and)h(Systems)p Fv(,)2337 847 y(17\(3\):461{486,)24 b(Ma)n(y)i(1995.)1931 1013 y([SKAH91])41 b(Mark)65 b(Smotherman,)75 b(Sanja)n(y)65 b(Krishna-)2337 1112 y(m)n(urth)n(y)-7 b(,)28 b(P)-7 b(.)29 b(S.)f(Ara)n(vind,)g(and)g(Da)n(vid)g(Hun-)2337 1212 y(nicutt.)144 b(E\016cien)n(t)63 b(D)n(A)n(G)g(construction)2337 1312 y(and)29 b(heuristic)f(calculation)g(for)g(instruction)2337 1411 y(sc)n(heduling.)38 b(In)28 b Fn(MICR)n(O-24,)k Fv(24)3422 1381 y Fa(th)3518 1411 y Fn(A)n(nnual)2337 1511 y(Intl.)h(Symp.)g(on)f(Micr)l(o)l(ar)l(chite)l(ctur)l(e)p Fv(,)h(pages)2337 1611 y(93{102,)25 b(1991.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF