CS453 Intro and PA1 1CS453 Lecture Register allocation for expression trees 1Plan for today Finish possible improvements over spill all– register allocation for Tree.Exp Review predictive parsing– first and follow sets– predictive parsing table– predictive parsing code– error recovery for predictive parsingCS453 Lecture Register allocation for expression trees 2Possible approaches for improving over spill all Linear passes over the Assem.Instrs– after spill all, remove loads from sw-lw pairs where the temp and frame locationare the sameeg. sw $t2, -16($fp) lw $t2, -16($fp)– before spill all, assign each Temp to a callee-saved register until run outeg. t34 ==> frame.RAt35 ==> frame.S0 ...calleeSaves = { RA, S0, S1, S2, S3, S4, S5, S6, S7}– after spill all, assign each frame location to a callee-saved register until run outeg. $fp-12 ==> frame.RA$fp-16 ==> frame.S0...calleeSaves = { RA, S0, S1, S2, S3, S4, S5, S6, S7}CS453 Lecture Register allocation for expression trees 3Possible improvements over spill all cont... Register allocation for expression Trees– assign Temps associated with machine registers to intermediate resultswithin an expression tree– indicate to spillAll that those Temps should not be spilled– here can use caller-saved registers as well as callee-saved registers sinceExpCALL won’t be an intermediate expression treeCS453 Lecture Register allocation for expression trees 4Reviewing predictive parsing Write a predictive parser using panic mode error recovery for thegrammar shown below.(0) S -> E $(1) E -> B E’(2) E’ -> ‘or’ B E’(3) E’ -> epsilon(4) B -> t(5) B -> f$$or $FOLLOWnot fSnot fEyesorE’not fBnullableFIRSTCS453 Intro and PA1 2CS453 Lecture Register allocation for expression trees 5Predictive parsing table Building a predictive parsing table– one row for each nonterminal, one column for each terminal– production “X -> gamma” should be in row X, column T for each T infirst(gamma)– if gamma is nullable, put “X -> gamma” in row X, column T for each T infollow(X)CS453 Lecture Register allocation for expression trees 6Predictive parser implementation Implementing a predictive parser– write a function for each nonterminal X with a switch on the current input token– switch statements will have a case for each terminal T, where row X and column Tin the parsing table contains a production rule– in function X, case T, nonterminal functions and eat(token) calls will parse theright-hand-side of the production in row X and column T of the parsing table void eat(t) { if (tok==t) advance(); else error(); } void advance() { tok=getToken(); }void S() { switch(tok) { case t: case f: E(); eat($); break; default:
View Full Document
Unlocking...