coer4i'o|{|P'liqiP6L'dREGISTER ALLOCATION VIA COLORINGGREcoRy J, CH^ltrN, MAic A. AuslrNDll. AsHoR K. CHTNoRA, Jo+IN CocKE,MAxnN E. Hopt(rNs ard psrExt W. M^l((lrErNtBM L. warron Rearch Ccn|.r, yo*toen H.irh!5, Ny IOr98, U.S.A.lR...tv.tt 9 Octobe. 'JAO)Atdr..r-R.gin4 alqrioi r.t bc vi.y.d s I g.ph otoinS Fobld. Ea.h rod. in rh.srapn n..th for I cohp{cd qusrry !n.r rBjd6 in r h&hh;,.9't.r, ""d l;;;; ;;:conner.d by &..rB.irrh. quurls,nk.rs. w,rh ach odd. rr,.r n-rr ir,iy * iii,"iii.i"liJr. ' shr pohr n ,h. ooFd p,osah rhu rppro.dr lnou8h ,.",i_.a i"ir,i, [iiiiiii]iiiincvc hprchdr.d b.ror. pEuh,n.ry rc$hi of&.rpcri,.nhl inDlcnar! oD in I pLioFidDrS compil.! !u!i6r rh.r 8lob.t E8lrcr.lt@fio. rpDr@chinr rh.t oI h.nd{od;emDry u.&rl! mrv bc .rrajngl.R.i .ralte..id OpdninigcoopilcB Or.ph@lorinsI, OVERVIIW OF REGISTER ALLOCAIIONIn this papc-r r',/e dcscribc rhe Rcgisrcr Allocation phas. of an cxpcrimcnbl pLlI cqjnpilcrlor rbc _IBM SystcmB?o. (For an oi,ervicw of th! cntirc cornpilcr scc Cockc ana.ULf-stcitr fll.Ior baclground informadon on oprimizarion. scc ha"tr: -Jiril;, iilh.rlsponsibiuty of this pha$ to maD rhc untimitcd nulnf., of,yrnOlrd" ,"giit'rJ ""r"rJiD thc irrcrmcdiatc languaSc iDto thc t7 rcal machinc rcgisterq narncly -the 15 gencral-n6c rcgrstcrs (R0-Rt5). and rhc coadition-codc lCO.t.csscDce of our approach is thal it is unifonn ajd systqhatic Compilc, back.erdstbu"-(dcal wirh thc idio6yncrasics of rhe machin. inrt^.u6n.; ro, "r"-pii-r"gilii-p-"i'ilhc fact fiar rcgisrcr R0 is an invalid bas. rcgisrcr, and thal th. contcnlsof soi" a"L;nlrcgistcr arc dctroyed as a sidc€tred ol funicutar i*m"ti";a.'l;;;;;;.;;';jthcs. idiosyoffasics arc cnkred in a unifor; manner in our dare itrucrurc, ihe inicifeicnce graph. Afrcrwards rhis dara srruclure ts ,nanip"t"t.a in " "c.y ivrtiiiU" ""u. '',-ALo. our approach has a rarhcr difi.rcnr pcrson;hy d;;.Jiffi;;;;;i;. *.uu groDar rcgrster aIocitlton actoss cntirc procedurcs Funhcrmorq cxccpt for fhc rccjs-lcr which always contains rhe addrcss ot-thc DSA C.dy""*" .i";;;;;;i;;";;;;st.cl framr, and js rhe anchor for all addrcssability, "fi orf,", ..giri"'" i."-";;:;;il1;oc_.pan of i unrform pool ard all compurarions 'conpcrc "" ; i;J;;;-i;;;rc8$lcrs Mosl compilcrs res.rve subs.ts of the regi""ri to, .p"an" i".po.."; *. ao ii.cxact oPposite.__rlr our-compilcr a d€liberate cfron is madc to make things as hsrd as possible forrc&slcr allocarion, i.e-to lccp as many computarion, ". p*riUta in ,"gi.r..,i"ri"_.-r#{ssrarage foJ cxarDpE automatic scalals ara usually Lcpt in rcgislcrs rathcr than i! thc".?r, ano tuDrout|ltc ljntaga also attcEpts to p6ss as nuch inforhation as Dossible;:::-1T t p.":o lr.rs rhc rGponsibiliry of cod. gcn€rarior and optimizadon jo €tcqJqragc ot,lnc untrmilcd numbcr of rcgistcrs allowcd in thc intcftcdiatc lanruaca in"'uEr ro drntmrze tt|c nurlbcr of loads alrd stor?s in tlc progra.m, sincc thcse a-rc riuch}i,.._lFll*. rhan registcr lo rcgisrcr instructionc tlcn tr-opefuuy ;di;;il;;qru rlap rli thlsc rtgisrcn into thc 17 rhar are acluaUy *"it"Ui. L O" fr-".a"ar". iii.i'. D E8lslcr auocatron's Fcsponsibi[ty to pul back into thc objcc! progam lhc r'linimunadlo_unl of spill cod., i.c. oa sbrcs ard rjoads of r.gislcrs, $;t is D;ed.",^. ,9o8 f no spill codc ncld bc iDuoduccd $t fc€l thal our approach !o recisr.r- |on ooca a bc|lcr Job tbr! cen b. donc by hsnd-codcls Foa cxall|oL. if Ucri is ,.. qrangc tn a prograrD, whcn it is r.compild thc Rcgistcr Auocstion ph&sc fiayr".,.rucc r.complctely difr.rcnr alloc.tioo to accorncrodati thc dange. A ;a;.;;;--ru or rncsponsrDl. to procccd in ruch a fashion. Wc also f.al rhar our comoilcrCnaorv .1. Cnrrn .r ,r$cccrds in k.€ping things in rcisrcrs raihcr than in storagc bc(cr than orhcr compibrra.d that this is onc of thc salicnt fcrrurcs ol thc pc.sooaliay of tbc objcct codc Wproduac. Moreovd thc marh.matical clcgan€ of the Sraph colorirg approach dcscdbd!bclo% its sysldnadc and uniform eay of dca[Ig with hardwa.c idiosync.asicsa and th(fact that ils algorithms arc computarionally highly cfrcicnl, arc convincing arglmcnts h,.eits favo..2. IEOISTER AL.'-OCATION AS A GIAPII COLORINC PROBLEMOur approaah to regislar allocrtion is via gaph colorin& This has t!€.n suggesrcd byCocke [2], Ycrshov [3], Schwartz [4], and othcrs. but has nevcr bccn wo.ked-oul ind€tail nor implcmctltcd bcforc. R.call thEl a coloring of a graph is an assignmcnt of acolor to cach ofits nod6 in such a mrorlcr tbat if two nodcs arc adjaccnt. i.€, colncctadby an cd8. of thc graph ihcn thcy havc dificrcn! colors. A coloring of a graph is ssid tobc an ,.coloring if il doc! lot usc morc than r difrer.nt colors. And rhc chromaticnumbcr of a graph is dc6D.d to b. thc minimai numbcr of colors in any of ils coloring!,i.c. th. lcas! n for which thcrc is an n-colorinc of it._ ft is wcll-kno*n [5] that givcn e gapir G and a narural numbcr, > 2. the problcm ofdctermining whcthcr O is n-colonblq i.c. whctier or not thcrc is lm n-coloring of 6, isNP-complctc. This suggEsts that in somc cascs ar altoglthcr impractical amoudt ofcomputation is lccdcd to dccidc thil ic, that in some cas6 thc amount o[ cohDubtiotrmusi bc e! cxponendal funclion of rhc sizc ofc,In facl axpcnmental evidcnce indicatcs that the Np-complcrcncss of graph coloring isnot a siSnificanl obstaclc to a rcgistcr allocaiion schcrn. brsed oo graph colorio& Horv-cvcr ii should bc pointcd out that givcn aD arbitrary g:aph it is possiblc to construct rproStsm whos. rcgist.r allocation is formulaicd in terms of coloring thia graph (s.aAppcndii 2). Thus some progrerff must Bivc risc to s.rious coloring probl.nsOur sppfoad to rcgistcr allocatio[ is to bulld a rcghaer htalercrce gruph Io. .slca !proccdurc in thc sourcc progrerE, and lo obtsin I 7-colorings of th6. inrcrfcrcnce graphr . "Roughly spcalin& lwo coDputations ehjch r6idc itl r[cbin€ registfis arc said t; idcr.lcrc with cach oths il lhcy arc livc si[ultaftously al ary point in rha program.For cach proccdurc P in thc sourca progam ar inle arcnca graph rs construclcd fwhos! nodcs stand for thc I 7 machirc rcgisl€rs ard lor all computadons in thc proccdurrP which rcaidr in machinc rcgistars, and whosc cdgas stand for registcr inlcrfcrcnccs. Ifthc chrornaiic numb.r of this g!.ph fu l?, thcn a rcgistcr allocation has bccn acbicve4 jend $c rcgisLr aslign.d (o a coEputation is that ona of thc l7 machinc r€gisrcrs whidr ihas tha satrrc color thal ii docs- Thus