New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Orrin Rutherford


Orrin Rutherford
GPA 3.91

Jingke Li

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Jingke Li
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 40 page Class Notes was uploaded by Orrin Rutherford on Tuesday September 1, 2015. The Class Notes belongs to CS 322 at Portland State University taught by Jingke Li in Fall. Since its upload, it has received 18 views. For similar materials see /class/168268/cs-322-portland-state-university in ComputerScienence at Portland State University.

Similar to CS 322 at PSU

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/01/15
IR Tree Canonicalization Jrngke L Portland State Unlverslty megs Ll Fenland Sate Unlverslty 222 H Tree cenomeelnenon Problems with the Current IR Tree Representation The e are two areas n the current IR tree language that may cause potentral problems Multlple CALL nodes wlthln the same exprelon may cause problems wlth callrrelated regrster usage when mapped to lowerrlevel code 0 ESEQ and CALL nodes wlthln expresslons may brlng slde effects to dlfferent eyaluatron orders of subexpresslons eausrng problems for loweleyel optrmrzatrons megs Ll Fenland Sate Unlverslty 222 H Tree cenomeelnenon IR Tree Canonicalization To resolve these problems we could perform canonicallzatlon on a tree 0 lgn each return value rmmedrately Into a TEMP turn a CALL node Into an ESEQ no e CALL llAME f COllsT 1 gt EsEO MOVE TEMP 100 CALL llAME f COllsT 1 TEMP 100 0 Pull the statements In all ESEQ nodes out of an expreSlOn tree effectlvely ellmlnatlng all ESEQ nods ASSch TEMP 101 BIND t COMST 2 CALL llAME r COllST 1 gt LASSIcll TEMP 101 EIMOP COllsT 2 ESEO MOVE TEMP 100 CALL llAME f COllsT 1 TEMP 100 gt OlOVE TEMP 100 CALL llAME f COllsT 1 LAss GM TEMP 101 BIllOP t COMST 2 TEMP 100 The resultlng tree ls called a canonical IR tree huge Ll Fenland Sate Unlverslty 5222 H Tree ceremeeluenm 3 1 Implementatlon canomeahzatron can be Implemented as a vlsltor program over an IR tree The Vlsltor program vlslts every expresslon node extract statemens out and forward them to upper level pubhc class Canon rnplenrents IrVI pubhc PRDG vJthPROG t return new PROGtfuncsacceptths pubhc FUMClet VstFUIlClet c FUMClJSt funcs new FUMClJStO for Jnt 10 Jlttsze J runesaddFUllC te1ementAtnacceptthns return funcs pubhc PullC VstFUIlC t return new FUMCt1abe1 tvarCnt LargCnt sTMThst tstmtsacceptths huge Ll Fenland Sate Unlverslty 5222 H Tree ceremeeluenm a 1 Handling CALL Nodes a new temp to save the return value and replace the node wrtn o e Introduce an ESEQ n publlc EXP VlsltCALL t EXP ar targsacceptthls STMT s getStntargs TEMP tnp new TEMPlt new cALLtrunc EXPllst getExparg E return new ESEQmergestmtsssi tmp prlvate srm getstmtEXP e i r e lnstanceof ESE return ESEQ estnt turn null prlvate EXP getExpltEXP e n e lnstanceof ESEQ ESEQ eeXp retur return e uneetr penrenusereunueere 5222 turreecenenrenenen 51 Handling Other EXP Nodes Aumlng components are commutative publlc EXP VlsltMEM t EXP exp Lexpaccep thls STMT s etStmt eX n s u 1 return new ESEQs new MEMgetEXpeXp return t publlc EXP vlsltBIIl0P t EXP left tleftacceptthls EXP rlght tr ceptthls STMT s nergeStntsgetStntlert getStmtrlght n s l null return new ESEQs new Elu0Ptop getExpuert getExprnght return t nt ngse Lt menu stete Unwerslty Sm u Tree cenenuetnenen Handling Other EXP Nodes cont VlsltEXPllst t nu new EXPllstO for Int 10 JlttSJZ O In EXP e EX telementAtlaccepttnrs STMT Si getstmte s mergeStmt sy s1 1 1 l null argaddgetEXpe publlc EXP lf 3 l null return new ESEQs args return t publlc EXP VlsltESEQ t tmt STMT s tstmtacceptthls eXpacceptthlS39 EXP exp t STMT s uergeStutsstut getstmtexp r s l null return new Esme getEXpeXp return t ler ll menu see WWW 222 u Tvee tenemuenm Handling STMT Nodes publlc STMT VlsltM0VE t XP st tdstacceptthls EXP s tsrcacceptthls TMT s uergeStutsgetStutdst getStutsrc r s l null return uergeStutss new MovEgetExpdst getExpsrc return t publlc STMT VlsltCJUMP t EXP left tleftacceptthls EXP rlght trlghtacceptthls STMT s uergeStutsgetStutlert getStmtrlght r s l null CJUMPtop getEXpuert return mergestmtss new getExprlgnt ttarge return t ler ll menu see WWW 222 u Tvee tenemuenm Handling STMT Nodes cont pubhc STMT VstCALLST t XP args t argsacceptths s r s TMT s getStmta g 1f 3 nu return uergeStutss new cALLSTtrunc EXPlet getExparg return t pubhc STMT vJthRETURIl t EXP exp Lexpaccep thls STMT s getStutexp 1f 3 null return uergeStutss new RETURMgetExpexp return t Nye Lt menu see WWW Sm u Tvee momentum Code Generation ngke L Port znd State Umverswty ngse u venom Sate Unwemty 222 Curie ceneedon 1 1 Code Generation IR code e e target cede Goal Generating correct and highequamy target eode Mam Issue Instruction selection The mapping from an IR eode to target eode s not unique Factors that affect selection 0 variety oflnstructlons variety of address modes ngse u venom Sate Unwemty 222 Curie ceneedon An Example M BIIIOP MAME fp 8 fp M BIIIOP 7 IIAME fp 12gt t1 712 MOVE ME fp8 t1 ME Target code I Moderate RISC 1d newer st 39r539fp8 I Extreme RISC CISC move Itp7121 39fp8 Inge LI Pan and sets UnIversIty SE22 Curie ceneenen CodeGen Algorithms Nane Codeecen 7 Map eaeIn IR statement Independently to a xed set of Instructlons 7 srmpIe can be automated e eodegen generators exlst 7 Not exIble code quaIrty may be poor codecen by Pattern Matching 7 Map a group of IR statements e g a subtree as a unIt 7 Allow IoeaI optrmrzatron Optimizing Codeecen with Dynamic ngrammmg 7 rate a cost to each IR statement and then perform gIobaI optImIzatIon to nd the best target code pattern for the IR program 7 Most expenslve but stIII aeeeptabIe n generaI Inge LI Pan and sets UnIversIty SE22 Curie ceneenen A Simple CodeGen Algorithm Input A sequence of threeaddre statements from a hasrc block Appmach Generate code for each statement Independently Internal Structure Registerdescrlptori Keeps tract of what ls currently m each reglster Multlple yanables may be auarlable m the same reglster x y Address descriptor 7 Keeps track of the locatons where the mrrent value of a yanable A locatron for a value X ls denoted Ly whlch could be a reglster a stack locatron or a memory addras Function getreglt5gt 7 Returns a locatron for storlng the result of a threeraddress Statement 5 mes Ll Fenland sets umyersrty 222 Curie caneetron s l An getreg Example getreg x y 0 z o If Ly IS a reglster let LX Lyotl1erwlse o If LI IS a reglster and 0p communltlve let LX LI otherwlse o If there IS an empty reglster R let LX R otherwlse If op requlrs a reglster hnd an occupled reglster R store Its value m memory and let LX R otherw se 0 LX the memory locatlon of x mes Ll Fenland sets umyersrty 222 Curie caneetron n l Simple CodeGen cont 1 Consult the address descrtptor to determme Ly and LI Invoke getregO to determme the locatton Ly update the address descriptor for x update the regtster descrtptor If LX IS a regtster If Ly Ly or Ly L1 generate up LyLZ or up LDLX Otherwrse generate mov LwLX then up LDLX quot If the current values of y andor 2 have no next uses on blockeexrt and are regrsters update the regrster descriptor Jew and are not IlVe m srnnlarly handled nga tr Pur and seate unused csm Curie caneenen Simple CodeGen cont b m stack slot Sb mov fpSb quotnr mov quotur1 a b m regtster quotnrb mov rb1 a b In memory Mb mov Mbquotnr mov quotur1a a In stack slot Sa mov fpSa quotnr mov b quotur1 a In memory Ma mov Maquotnr mov b quotur1 a n regrster quottra mov bquotura1 tx mpy gate 2 1 Move x and y to regtsters If they are not there yet 2 Generate amp LXLy 3 Generate quotejunp rap L1 quot mese tr Pur and seate unused csm Curie caneenen x t An Example celter nw mete tr Pur and stete Unwerswy 222 cede ceneenen CodeGen with Dynamic Programming Goal Try to generate optimal code for a broad class of register machines Machine Model k Interchangeable registers r0 r1 wry1 Instructions are of the form r E where E Is an expraslon containing operators regrsters and memory locations denoted M 0 Every Instruction has an associated cost c0 c1 cy 7 It39s de ned for an expression E Cost Vedor CE where e0 7 the cost of computing E Into memory wrth the use of unbounded number of registers c 7 the cost of computmg E Into a regtster Wlth the use of up to r regtsters mete tr Pur and stete Unwerswy Sm Curie ceneenon m t Dynamic Programming Review Example Consider multiplying a sequence of matrices 7 a x p x c x d x 6 3x5 5X8 8X1 1x2 2x5 r a x a Aume the cost for multiplying an m X n matrix and an n X I matrix is Om X n X I Question What is the best order to multiply the sequence 0 A naive solution is to go from left to right r agtltbgtltcgtltdgtlte totalcost186 o A better solution is r agtltbgtltcgtltdgtlte totalcost85 DP Idea 7 Try every possible combination but avoid redundant computations niece ii were see unwed tsaa tune ceiaenei ii i Dynamic Programming Review cont The cost of computing a sequence 5 based on a particular partition 5 5152 can be expressed as C51 l 52 C51 C52 C12 Create a table to record the lowest cost for computing each su u n e of abc e Cab cbc ccd cde cabc obcd ccde DiVide and conquer 7 consider all four possible ways to partition the sequence abcde caiiicde 0ablcde cabcide Cabcdle Remrsively iind the lowest cost for each case then Cabcde niincaibcde Cablcde Cabclde cabcdle linge ti Fenland State university Sm Code caneetien i2 i Applying DP to CodeGen 1 Compute bottomcup for each node n of the expression tree T an array c of costs 2 Traverse T using the cost vectors to determine which subtrees of T must be computed mto memory 3 Traverse T and generate the hhai target code The code for the subtrees computed mto memory locations IS generated first Target Machine Model Example 3 e b c de Two registers re r1 Uniformrcost Instructions n M huge Li Portland state WWW 5222 Curie ceneehen i i Example cont Step 1 Select the best from the 9 p s ossible c3 Resuls for the whole tree nonnnnnnn n on on w wwwwwwwww 2 3 3 2 2 2 2 2 2 llulltuul huge Li Portland state WWW 5222 Curie ceneehen M i Example cont Step 2 M 0 0 am r1 r1ro ngse Lt payment Sate Unwemty 222 Curie cement 15 1 CodeGen by Pattern Matching Assume an IR tree language De ning tiles 1e patterns ieach corresponds to an Instruction Tiling the IR tree 7 covering the tree wuth nonoverlapplng tiles ngse Lt payment Sate Unwemty 222 Curie cement to 1 CodeGen by Pattern Matching cont hhifk 1 r H rk rwwc r H MM 2 MM 515 r 1mm LT Mam 5W Unwemty 222 we Caneanon n 1 An Example MOVE MEM BIMOP MEM BIMOP TEMP tFP COMST a EIMOP MUL TEMP n COMST 4 MEM BIMOP TEMP tFP COMST x 0 Solution 1 MOVE MEM MEM EIMOP TEMP tFP COMST a 4gt gtgtgt MEM BIMOP COMST x oad r1 H mm 3 r2 5 m 4 mu 2 H I X 72 add r1 n r2 oad r2 5 Mfp x store MM r2 1mm LT Mam 5W Unwemty 222 we Caneanon 18 1 An Example cont 0 Solution 2 MOVE MEM MEM Blue COMST a mad BIND com xh COMST 4 oad r17 Mfp 3 add r2 7 m 4 rnut r2 7 r x r2 add r1 7 n m b 27w movem MM 7 Mr2 urea u were see unwed 222 cede comm 191 Finding the Best Tiling c n assoetate a cost to each trle then we can measure quantitatively the quahty of a tiling of an IR tree 7 the best tiling corresponds to an Instruction sequence of least cost Two Levels of Optimality 0 Optimal Tiling 7 no two adjacent tlls can be combined Into a single tlle of lower cost A greedy algorithm ean be used to hnd an optimal tiling Optimum Tiling 7 the tiles sum to the lowest possrble value na e programming technique ean be apphed to tiling to hnd the optimum tiling for an IR tree nga Lt Pun and sene Untverstty csm Curie ceneenen 2n 1 Maximal Munch Algorithm For llndlng an optlmal tlllng Start at the root of the tree hnd the largest llttlng tlle whlch covers the root and maybe several other nodes hear the root Several subtrees may result from thls step 2 Repeat the same step for each subtree Largest means most nodes If two tlles of equal size match at the root the cholce between them Is arbltrary Example Applylng thls algorlthm to the tree on the prevlous page wrll result n Solutlon 2 mes Ll Fenland State Unlverslty 222 Curie ceneenon 21 l Dynamic Programming Algorithm For llndlng the optlmum tlllng The algorlthm asslgns a cost to every node In the tree Wl1lCl1 IS the sum of the lnstructlons coss of t e lnstructlon sequence that can tlle the subtree rooted at that node It works bottomrup For each tlle t of cost c that matches at node n there wrll be zero or more subtrees 5 correspondlng the leavs of the tlle Aume the cost for the subtree 5 Is c whlch has already been computed then the total cost of matchlng tlle t at node n IS c Z c 1 Start at the leaves of the tree For each node n flnd all the tlles that matches at n and compute thelr coss The tlle WIth the mlnlmum eost ls dmsen and the mlnlmum cost Is algned to n Repeat thls step for other nodes untll the root node39s eost ls mpute Now the algorlthm gas toprdown to emlt lnstructlons by calllng Emlsslonmot The Emission routlne ls de ned as follows Emlsslonnode n 7 for each leaf I of the tlle selected at node n recursively pertorm Emlsslonl Then emlt the lnstructlon matched 221 to w mes Lanand State Unlverslty 222 Curie ceneenon A DP Example MEM BIMOP t 001132 1 COMST 2 A CONST node can be matd1ed With only an addl Instruction wuth cost 1 So the two CONST nodes each ges assigned a valu 1 At the map node several matchs are possible We 131110 a a 31110 COMST a 81110 t cullsT at at addl lnx T Cox L Cox T Cox add 1 11 addl 1 1 2 1 2 The second ttle IS chosen and the mlnlmum cost of 2 IS asstgned to the BINUP node huge tl Punland state uhwemy Sm Code ceheeheh 2 1 A DP Example cont 0 At the MEM node also several matches are pwlble Tle lnx T Cox L Cox T Cox MEM at load 2 3 ml Bump t at COMST at load 1 1 2 MEM Blue 001132 at a load 1 1 2 Elther of the last two matches wlll be optlmum The Instructions emitted for thls tree are addl r1 5 r0 1 load r1 5 Mr1 2 huge tl Punland state uhwemy Sm Code ceheeheh 2o 1 Register Allocation ngke L Portland 5mg University JMQK ll mom sex WWW 522 RegsuvAllmatiun 1 2x Register Allocation Inan unbounded number of temporanes to a fixed number of reglsters Example load 3 quotr1 load gt r2 sub quotr1gt quotr2gt quotr1 load o quotr3 add quotr2gt quotr3gt quotr2 load d quotr mul quotr1gt quotr3gt quotr3 add quotr2gt quotr3gt quotr2 quotr1 quotr1 mul gtquotr2gt sub quotr2gt quotr1gt quotr1 JMQK ll mom sex WWW 522 RegsuvAllmatiun 2 2x Register Allocation Approaches A Nane FIISPCOmeFIrstSene Approach 7 Treat all regrsters equal allocate regrsters along codegeneratron flrstccomecflrstcserve run out of regrsters dum some to memor Just keep track of the usage of each regrster and handle requests very slmple and fast CategoryBased Approach 7 Classlfy program yalues Into categones e basic addresses anthmetrc computatlons etc and assrgn group of regrsters to each category From there follow the nalve approach But these approaches are n general not good enough In allocatrng reglsters we have an Optlmlzatlon goal to mlnlmlze memory operatlons loads amp stores and regrster mom whlch motryates the followlng approach usageesased Approach 7 Analyze program to collect yaluesusage lnformatlon then try to put and keep frequentlycused yalues n reglsters urea tr were see unyeers 522 Reese dream a m UsageBased Register Allocation The usage analysrs can be performed at dlfferent scope levels 0 Local Register Allocation 7 Analyze yanable usages m a basic block and optlmlze based on the lnformatlon It Is slmple an as 0 Register Allocation for Loops 7 Focus usage analysrs on a loop Need to ldentlfy loops otherwlse stlll smple and a o Global Register Allocation 7 Analyze yanable usages across a whole procedure vla dataflow analysrs and optlmlze based on the lnformatlon can provlde really elhcrent usage of regrsters very useful for machlnes wlth only a small number of regrsters ayarlable Jlngse Ll Fenland sets Unlverslty 522 RegserAlloceoon a 2x Local Register Allocation Conslder a smgle base block Algn regrsters based on usage count of temps Reserve a few regrsters 273 to handle memory accases m cases where the number of regrsters ls smaller than the number of temps Algorithm mpute a priority for each temp 7 In a hnear pass over the lnstructlons n the block tally the number of occurrences of each t p The occurrence count for a temp becomes 5 prlorlty Sort the temps mto pmmty order wm Assign registers In pnonty order 7 If there are k regrsters avallable the rst k temps get assrgned to them 4s Rewnte code 7 walk over the block a second tlme Replace each regrbound temp wlth the regrster39s name and replace other temps wlth load store lnstructlons Jlngse Ll Fenland State Unlverslty 522 Regsermloceoon 5 2x An Example ume two regs are reserved for memory acceses and two regs are avallable for assrgnment span t2 7 roam ta Usage counts span M a c dt1t2t3t4tst6 13 2 3 2 21 span ts 2 roam M u roam ts Assngyuuents 1 7 span to 3 39r4 Observation Further optrmrzatron possble but needs temps39 lweness lnformatlon wee u omen see new 5322 Regs ev Alloceoon a 2x Register Allocation for Loops Usage Counts usegtltB 7 the number oftlmes varlable X 5 used m baslc block B prior to any deflnltlon IlveXB 7 51 lfx s allve on exlt from B and s 3lgned a value m B s o otherwlse twee u menu see mm 5322 Reese werequot 12x RegAlloc for Loops cont Calculating the Bene ts The bene t from allocatmg a reglster to x wtthln loop L E costJd x usex B cosLst x llvex B BEL The rst term 5 the cost of addrelng ualue m memory and the second term IS the cost of storlng value Into memor Aume costJd Costjt 1 t en behehte L 3 behehtm L 4 benefltc L 3 beneflt beneflte L 1 behehtt L 3 t Assume that we have two reglsters avallable for thls loop Then b and d would be the wlnners thee Ll menu state Unlverslty 522 RegaevAHmatlun x 2x RegAlloc for Loops cont Regrster Assignment b and d are kept in reglsters gzx 522 Regsm Allmatlun JinQK ti percent sete University Register Allocation by Coloring 0 Perform datafow lneness analysis over a C collect variable llveness into at every program ppint Build an Interference graph each node represents a emporary val each edge represents an interference can t be assigned to the same register ue between two temporarlesithey Color the interference graph colors registers want to s few colors as possible for a machinewith K registers decidewhether the lnterferencegraph is Kecpipra l it yes the coloring gives a register assignment it no need to spill some temporaries to me w an be used either at the local scope or at the global scope in 2x JinQK ti percent sete University 522 Regsm Allmatlun An Example lryeness Analysls Result and Interference Graph Statement o colonng 7 How many colors do we need Two Problems Remarnrng o Keeolorabrhty problem rs NPeeompIeteI o How to handle spthng If needed twee Li Puniand State University 522 Regsermioeeoon 1128 Coloring by Simplification To overcome the NPeeompIete problem a heurlstlc aIgorrthm rs used Fact 7 Let m be a node In G with fewer than K neighbors let G be the graph G e m If 5 rs Keeolorable then so s A Heurlstlc Colorlng Algonthm Sex Repeatedly slmpllfy the graph by remowng and n a stack nodes of degree I h n K until either 1 no more node rs left whd1 means the graph rs Keeolorable or 2 an remarnrng nods are of degree more than K which means the graph rs not rcoorabe Example Is the hrst graph 3eeolorable7 Note that this algorrthm may gwe wrong answers Is the second graph 2eeoorabe7 twee Li Puniand State University 522 Regsermioeeoon 12 m A Coloring Example Statement We Vamab es g mem12 k J h k e 1 k g J r g h J e J r m J r e b r e m c e m b d c m b k m b d J b d k d J k ngse tt Pan and sete Mme 522 Regeemteeehen 13 m A Coloring Example cont Let K 4 o o o o o All remaining nodes have a degree Ie than 4 The graph 5 Leolomble huge tt mend Sate uhwemy 522 RegaevAHmatmn to 2x Spilling if there are k regrsters but the nterferenee graph is not heolorable we need to Splll temporaries to stac The SplIlng Action 0 After the temps definition it is stored to stack Before each use the temp needs to be loaded back to a reg Effects of Splllng 0 To handle data on stack 2 or 3 registers are need The node eorrespondrng to the spilled temp can be removed from the nterferenee grap How to Select 9 Variable Choose least frequently accased variables Choose nodes with the most conflicts n the nterferenee graph meg u were see unyeew 522 Ragnar Anselm 15 28 Register Allocation with Coloring Chaitin s Algorithm 1 Build 7 Construct the nterferenee graph m SImpI i Repeatedly srmphfy the graph sol7 When no more nodes can be srmphfred d1005e a node to spill add t to the spill set and remove t from the graph Repeat Steps 2amp3 until no more nodes left n the graph 4s Start Overi if the spill set s not empty insert spill eode for all spilled nodes e load before eaeh use store after eaeh defrmtron reconstruct the nterferenee graph Repeat the algonthm on this rewritten program an s 7 Assrgn eolors to nodes Starting with an empty graph repeatedly addmg a node from the top of the stack There should always be a new eolor available lines Ll Fenland State unryerswy 522 Regsermloeeoon in 2x An Example emrmexiwa mmHmemHmH c 3 stack co or huge Lt menu state Unwemty 522 RegaevAHmatmn nzx Delaying Spilling Brigg Recall that when the heuristic algorithm says that a graph s not krcolorable t may not be true When the algorithm gets stuck m the smphheaton step we 0 not have to spill right away 1 Btu117 Construct the mterference graph 2 Smpfyi Repeated y snnphfy the graph 3 SpHiWhen no rnore nodes can be srmph ed choose a node for potenta ser remove rt from the graph and push rt on the s ac Repeat Steps 2amp3 Myth 3 nodes are on the stack 4 Seecti Assrgn co ors to nodes Stamng wrth an empty graph repeated y addmg a node from the top of the stack For a snnphhed node there rs ahyays a new co or avar ab e for a potentm ser node there may strH be a new co or avar ab e Start Over7 f the Seect step rs unabe to nd a coor for some nodes then the prograrn must be rewrrtten to fetch thern from memoryjust before each use and store thern back after each dehnrtron The a go thm rs repeated on thrs rewrrtten prograrn huge Lt menu state Unwemty 522 RegaevAHmatmn 1x 2x Node Coalescing Fact 7 If there rs no edge rn the Interference graph between the source and destrnatron of a MOVE rnstructron then the source and destrnatron nodes can be coalesced Into a new node whose edges are the unlon of the two Effectlvely delete the MOVE rnstructron In prrncrple any parr of nodes not connected by an Interference edge could be coalesced However coalescrng can make a Krcolorable graph not scolorable Conservative Coalesclng Strategies 7 Guarantees that coalescrng wrll preserve the graph 39s krcolorablllty property 0 Br 5 7 Neda a and b can be coalesced If the resultlng node ab wrll have fewer than k nerghbors of srgnrhcant degree r e havrng 2 K e ges George amp Appe 7 Nodes a and b can be coalsced If for every nerghbor t of a erther t already lnterferes wrth b or t rs of rnsrgnrlrcant degree Jlngse Ll Fenland State unrversrty 522 RegsuvAllmatlun 19 2x Register Allocation with Coloring Improved Version 1 Burd7 Construct the lrlterfererlce graph and categorrze each node as elther moyeeteated or nonemoyeeteated 2 Srmplrry7 Repeatedly slmpllfy the graph by removrng nonemoverelated no es of lt K degree Conserwtlve Coalesce7 Coalesce two nodes accordrng to Brlgg s or GeorgeampAppel s condrtrons Repeat Slmpllfy and Coalesce steps untrl only 3 Kedegree or moverelated nodes remarn 4 Freeze7 Look for a moverelated node of low degree and freezethe moves r e grvrng up future coalesce attempts on them Resume slmpllfy and coa esce 5prll7 lf there rs no lowedegree nodes select a hrghedegree node for potentlasplll remove lt from the graph and push rt on the stack 6 Seect 7 Pop the entrre stack assrgnrng colors 7 Start oyer7 lf an actual sprll occurs rewrrte the program and rerun the algorrthm Jlngse Ll Fenland State unrversrty 522 RegsuvAllmatlun 2n 2x Back to the Example Nodej and b are MOVE related so are d and c o o e Coalesce nodsj amp b and d amp C mm L Portland Sate WWW 522 RegsuvAllmatmn 2123 Final Coloring dampc Jam ltm rm gt73 stack color mm L Portland Sate WWW 522 RegsuvAllmatmn 22 2x Pre Colored Nodes ln modehng a reahstre regrster alloeatron some nodes n the Interference graph need to be preeo ore e assrgned to speerhe maehrne regrsters for example the frame polnter regrster or the return value regrster Preeolored nodes eannot be srmphhed nor spllled The ongrnal regrster alloeatron algonthm can be modrhed to work wlth preeolored nodes 7 Just leave preeolored nodes to the end Preeolored nodes ean also make an otherwlse Krcolorable graph not Krcolora Jlnyse Ll Puniand state Unlverslty 522 Regsermloeeoon 2 2x Optimizations with Pre Colored Nodes Creating temporary Coples ofpreeolored regrsters enter defltr7gt enter defltr7gt r231 lt7 17 gt H r7 lt7 r231 exlt useltr7gt exlt useltr7gt These coples wrll shorten the Ilve range of preeolored regrsters The extra move lnstructlons wrll automatreally be removed l they are not actually nee ed Drstrngurshrng calleresave and calleeesave regrsters Force a defat the entry of the subroutlne and a use at the end for every ealleesave regrsters Jlnyse Ll Puniand state Unlverslty 522 Regsermloeeoon 2 2x Example 1n mm a 1n b enter a e r3 3 5 r1 Jnt 10 ea b 5 r2 do d db d e 0 e e7 e e a thle egt0 loop d e db return d e e 971 n 6 gt0 goto loop r1 d 3 r e c return 1 r3 hve out No opportunity for simplify freeze or coalesce so we must 5pm The phohty for spllllng can be computed c a b d e so we select node c for spllllng huge u mend Sate uhweew 522 Regs evAHmatmn 25 2x Example cont aeampr1 or dampr2 Choose t e latter The graph can now be fully slmpllfle Coalesce aeampr1 huge u mend Sate uhweew 522 Regs evAHmatmn 2n 2x Example cont srhee there Is a sprlhhg we need to modify the program enter 1 M loop Thrs graph can be to quoty simplifiedcoalesced The nal coloring e no es are node COW G dea tr were sere memo 522 Regeer werequot 21 2r Example cont The resulting program After removing trivial move Instructions enter r3 H r3 Moc 5 r3 enter Moc 5 r3 1 H r1 r3 H 0 H e r2 r1 1 r3 e 0 loop r3 e r3r2 71 H I Xi H rlil loop r3 e r3r2 1 r1 gt0 goto loop 71 H rlil Xi H r3 1 r1 gt0 goto loop r3 e MUOE 71 H r3 return r3 5 Moc 73 H r3 return dea tr were sere memo 522 Regeer werequot H m Language Interpreters ngke L Portland State Unlverslty huge Ll Fenland Sate Unlverslty 5322 tergdege Mummers llx Language Interpreters Ah mterpreter reads m a source program and executs t Immediatey 0 Advantages 7 Easrer to wrlte than comprlers and more portable o Drawbacks 7 Slower than ruhmhg complled code Levels of Interpretatlon Lowelevel Language Including IR Code lnterpretatron 7 program ISJLISt a slmple sequence of lnstructlons e smgle hamespace although hmctroh calls have local data 0 ngheLelel Language Interpretatlon can be complex declaratrohs data types modules exceptlons et 7 multlple hamespaces wlth varlables huge Ll Fenland Sate Unlverslty 5322 tergdege Mummers 2lx Interpreting LowLevel Languages The Interpreter needs to manage a slmple memory model and executes a fetcheexecute Cyde thle there are fetch the next Jnstruc execute thJs Jnstructlo stJll nstructlons tJon Example Interpretlng an assembly language for a machlne wuth only two no Jlngse Ll Fenland sea Unlyemy 5322 Lengnege Mummers lx The Data Structures pubhc c1ass Instructlon b pu 11c stath fJnal byte LOAD RE1 MOVE 2 AD JUMPZ HAL SUB JUMP s pubhc byte 0 pubhc short pubhc class State pubhc stath fJnal short CODESIZE4096 DATASIZE 96 pubhc stath r nal byt RUNNINGO llALH FAILED 2 structonCODESIZE code new I pubhc short data new short DATASIZE pubhc short PC A pubhc byte status Jlngse Ll Fenland sea Unlyemy 5322 Lengnege Mummers a lx The FetchExecute Cycle pubhc class Interpreter extends State pubhc von loadO t load the program 01d pubhc v goo PC 0 ACC 0 status RUNNING do Instructlon Jnst codePC short d 1n t sultch Jnstop case LOAD ACC datad break case STORE datad ACC break case MOVE ACC reak case ADD ACC datad break 01 break a break break thle status RUNNING mien peniendseemmny 5322 Languagelntevpmers s ix Handling Function Calls Needs to deal with the allocation and derallocation of activation records on the stac rs AR 139s mm smack P rs lacalvars space acamdbyf g39sAR g 39s pmms g 39s lacalvars Jingse Li Portland see WWW 5322 Language imam n ix Handling Function Calls cont von lnterpFunCFUMC f Sp 7 s 7 rvarcht 7 r do the maln Inter Instructlon In short aIgCnt 7 allocate an AR oh the stack pretatlon loop 7 codePC sultch d 7 Just nstop case 0 7o lltargsslze n n1 7 ltarg gt fP SP nterpFunC 3 SP fP fp 7 memsp uhlle status 77 RUNNING Sp 7 Sp fva rcht faIgCnt 1 de7allocate the AR ngse u mend see WWW 5322 teneeee Mummers uh Interpreting HighLevel Languages New Issues declarations and scop The Interpreter nee around age a symbol table to keep Information and the Interpretation actlons need to take place In environment Program Text functlon aunt bunt cunt 7 prntntac var J ab Var a hello prntnta prnhtghtw a 777 prnhtnhtc an n Um base enwonment empt s 7 n a H y U2U1Jgt Hn m met cht U302agt Strmg nee h mend sea hum 5222 Language Mummers xix Environments For imperative languages there is only one aCtIle environment at any time 39 tion This active environment corresponds to the For other languages several environmens can be active at the same time Example simultaneous active envlronments in an OOP program Enl Program Text package m 3H mt class E EHU m We statlc Jnt 36 Us br r ml aHlnL class M m ll H U3 statlc nt b10 alt r int sta c Jnt aEab DHU U1Uzm0n a lla class D statlc Jnt d urge ti Fenland sere uriversry 5322 tereueee lntevpmers g ii A Simple Expression Language VAR egt exp W exp exp sgt LET VAR exp Ill exp EllD A program in thls language which should evaluate to 26 urge ti Fenland sere uriversry 5322 tereueee lntevpmers in ii Interpreting the Expression Language Attributed Grammar Producton prog egt exp exp egt MUM exp egt VAR ookupexpenv VARJd exp egt exp1 w exp2 expenv ex expenv exp1va exp2va exp egt LET VAR 12 exp1 expenv Iii exp2 EiID v extendexpenv VARJd exp1va xpva exp2va Anya Li Puniand sexa University 5322 Language Mummers n 1x Interpreting the Expression Language cont Translation Scheme Uslng a global envlronment prog 7gt env empty exp progw expw exp 7gt NUM expw NUMnum exp 7gt VAR expw ookupenvgt VAR19 exp 7gt exp177exp2expW exp1W expzwh exp 7gt LET VAR gtgt exp1 env extem env VARd exp1WD IN exp2 END env retmc env WARM expva exp2va Anya Li Puniand sexa University 5322 Language Mummers 12 1x A Second Language Adding functions prog gt exp exp 7gt M exp VAR exp 7gt exp I 2 exp exp 7gt LET VAR 22 exp HI exp END exp 7gt F VAR new exp P exp A program m this language let add2 fn x new x 2 1n 14 Wthh should evaluate to 26 ngse u mend see WWW 5322 Language Mummers u m Interpre ing the Second Language Atmbutex Producton Frog gt W expva exp 7gt MUM MU um exp 7gt VAR expva ookupexpenv VARd exp 7gt exp1 w exp2 expenv expenv exp1va exp2va exp 7gt LET VAR 12 exp1 expenv In exp2 END extenMexpenv VARd exp1va exp2va exp 7gt FM VAR HgtH exp1 expva EoxureVARd exp1 expenv exp 7gt exp1 exp2 va body ndexp1vaenv exp1vaforma exp2va A funcmon dosure conswsts of formsV body and env ngse u mend see WWW 5322 Language Mummers m m Interpreting the Second Language cont prog egt env empty exp progva expva exp 7gt MUM expva MUMnun exp 7gt VAR expva ookupenv VARd exp 7gt exp1 w exp2 expva va exp2va exp 7gt LET VAR 22 exp1 env e extem em VARd exp1va HI exp2 END env remcmenv VARd expva exp2va exp 7gt F VAR HgtH exp1 expva coxureVARd exp1 env e 8 exp egt expi a exp1va exp va puxhexxamenv nv extendcenv cformah actuaD p a bodyva env PoprxtaEW ngse Lx mend see Unwemty 5322 Lengege Mummers 15 1x An Implementation in C typedef char 1d typedef struct Exps Exp struct Ex 3 enulu RumVarP1usPrmcLecAssxgn kJnd unlon struct nt m num struct d v var struct Exp e1e2 plus struct xp e pr t struct 1d Exp e1e2 1 c struct Jnt v Exp e asslgn ngse Lx mend see Unwemty 5322 Lengege Mummers m 1x


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.