Compilers ECS 142
Popular in Course
Popular in Engineering Computer Science
This 119 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 142 at University of California - Davis taught by Sean Peisert in Fall. Since its upload, it has received 40 views. For similar materials see /class/187736/ecs-142-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Compilers
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/08/15
Register Allocation Lecture 26 Dr Sean Peisert ECS I42 Spring 2009 Status 0 Project4 dueJune 5 55pm 0 This Week 0 Of ce Hours today at lam 0 NextWeek 0 MondayAutomatic Memory Management 0 Wednesday Static Analysis for Security 0 Friday Final Exam Review The Memory Hierarchy 0 Registers l cycle 2568000 bytes 0 Cache 3 cycles 256kIM 0 Main memory 20l00 cycles 32MIG 0 Disk 055M cycles l0G2T Managing the Memory Hierarchy Programs are written as if there are only two kinds of memory main memory and disk Programmer is responsible for moving data from disk to memory eg le lO Hardware is responsible for moving data between memory and caches Compiler is responsible for moving data between memory and registers Current Trends 0 Cache and register sizes are growing slowly 0 Processor speed improves faster than memory speed and disk speed 0 The cost of a cache miss is growing 0 The widening gap is bridged with more caches 0 It is very important to 0 Manage registers properly 0 Manage caches properly 0 Compilers are good at managing registers The Register Allocation Problem 0 Recall that intermediate code uses as many temporaries as necessary 0 This complicates nal translation to assembly 0 But simpli es code generation and optimization 0 Typical intermediate code uses too many temporaries O The register allocation problem 0 Rewrite the intermediate code to use fewer temporaries than there are machine registers 0 Method assign more temporaries to a register 0 But without changing the program behavior History Register allocation is as old as intermediate code Register allocation was used in the original FORTRAN compiler in the 50s 0 Very crude algorithms A breakthrough was not achieved until I980 when Gregory Chaitin invented a register allocation scheme based on graph coloring 0 Relatively simple global and works well in practice An Example Consider the program 0 a c d 0 e a b 0 f e with the assumption that a and e die after use Temporary a can be reused after a b Same with temporary e after e Can allocate a e and fall to one register rl rcd rrb rr Basic Register Allocation Idea 0 The value in a dead temporary is not needed for the rest of the computation 0 A dead temporary can be reused 0 Basic rule 0 Temporaries t and t2 can share the same register if at any point in the program at most one of t or t2 is live Algorithm Part The Register Interference Graph Two temporaries that are live simultaneously cannot be allocated in the same register We construct an undirected graph 0 A node for each temporary 0 An edge between tl and t2 if they are live simultaneously at some point in the program 0 This is the register interference graph RIG 0 Two temporaries can be allocated to the same register if there is no edge connecting them Register Interference Graph Example Register Interference Graph Properties 0 It extracts exactly the information needed to characterize legal register assignments 0 It gives a global ie over the entire flow graph picture of the register requirements 0 After RIG construction the register allocation algorithm is architecture independent Graph Coloring De nitions 0 A coloring of a graph is an assignment of colors to nodes such that nodes connected by an edge have different colors 0 A graph is kcolorable if it has a coloring with k colors Register Allocation Through Graph Coloring 0 In our problem colors registers 0 We need to assign colors registers to graph nodes temporaries 0 Let k number of machine registers 0 If the RIG is kcolorable then there is a register assignment that uses no more than k registers Graph Coloring Example Computing Graph Colorings 0 How to compute graph coloring 0 It s not easy 0 In fact very hard N P hard No ef cient algorithms are known 0 Solution heuristics 0 A coloring might not exist for a given number of registers 0 Solution later Graph Coloring Heuristic 0 Observation 0 Pick a node t with fewer than k neighbors in RIG 0 Eliminate t and its edges from RIG 0 If the resulting graph has a kcoloring then so does the original grap 0 Why 0 Let CCn be the colors assigned to the neighbors of tin the reduced graph Since n lt k we can pick some color for t that is different from those of its neighbors Graph Coloring Heuristic 0 The following works well in practice 0 Pick a node t with fewer than k neighbors 0 Push t on a stack and remove it from the RIG 0 Repeat until the graph has one node 0 Then start assigning colors to nodes on the stack starting with the last node added 0 At each step pick a color different from those assigned to already colored neighbors Graph Coloring Example Spilling 0 Since optimistic coloring failed we must spill temporary f 0 We must allocate a memory location as the home off 0 Typically this is in the current stack frame 0 Call this address fa 0 Before each operation that uses f insert 0 f 2 load fa 0 After each operation that de nes f insert 0 store f fa Recomputing Liveness Information The new liveness information is almost as before f is live only 0 Between a f 2 load fa and the next instruction 0 Between a store f fa and the preceding instr Spilling reduces the live range off And thus reduces its interferences Which result in fewer neighbors in RIG forf Recompute RIG After Spilling O The only changes are in removing some of the edges of the spilled node 0 In our case f still interferes only with c and d 0 And the resulting RIG is 3colorable Spilling Cont 0 Additional spills might be required before a coloring is found 0 The tricky part is deciding what to spill 0 Possible heuristics 0 Spill temporaries with most conflicts 0 Spill temporaries with few de nitions and uses 0 Avoid spilling in inner loops 0 Any heuristic is correct Caches 0 Compilers are very good at managing registers 0 Much better than a programmer could be 0 Compilers are not good at managing caches 0 This problem is still left to programmers 0 It is still an open question whether a compiler can do anything general to improve performance 0 Compilers can and a few do perform some simple cache optimization Cache Optimization 0 Consider the loop 0 forj jlt 0j O foriilt000i 39 ai bi O This program has a terrible cache performance 0 Why Cache Optimization Cont Consider the program fori l K 000 i 0 forj lj lt l0j 0 ai bi Computes the same thing But with much better cache behavior 0 Might actually be more than l0x faster A compiler can perform this optimization 0 called loop interchange Spilling Example Conclusions 0 Register allocation is a must have optimization in most compilers 0 Because intermediate code uses too many temporaries 0 Because it makes a big difference in performance 0 Graph coloring is a powerful register allocation schemes 0 Register allocation is more complicated for CISC machines Work on Project 4 BottomUp Parsing Lecture 6 Dr Sean Peisert ECS I42 Spring 2009 BottomUp Parsing 0 Preferred method in practice 0 Also called LR parsing O L means that tokens are read left to right 0 R means that it constructs a rightmost derivation O We ll talk about LL parsing later Idea LR parsing reduces a string to the start symbol by inverting productions str 6 input string of terminals repeat 0 Identify B in str such thatA gt B is a production ie str 0 B y 0 Replace B byA in str ie str becomes 0A y unti str S bottomup parse diagram Important Fact I 0 An LR parser traces a rightmost derivation in reverse Where Do Reductions Happen Let 0 B y be a step of a bottomup parse Assume the next reduction is byA gt B Then y is a string of terminals Why Because 0A y gt 0 B y is a step in a right most derivation you would have reduced y otherwise Bottom Up Parsing Lecture 6 Dr Sean Peisert ECS I42 Spring 2009 7 Notation 0 Split the string into two substrings 0 Right substring a string of terminals is as yet unexamined by parser 0 Left substring has terminals and nonterminals 0 The dividing point is marked by a D 0 The D is not part of the string 0 Initially all input is examined gtXX2 Xn ShiftReduce Parsing 0 Bottomup parsing uses only two kinds of actions o Shi 0 Reduce Shift 0 Shift Move D one place to the right 0 Shifts a terminal to the left string ED int gtE int Reduce Reduce Apply an inverse production at the right end of the left string If E gt E E is a productionthen EEEDgtEE D shiftreduce diagram The Stack 0 Left string can be implemented as a stack 0 Top of the stack is the D 0 Shift pushes a terminal on the stack 0 Reduce pops 0 or more symbols off of the stack production rhs and pushes a non termianl on the stack production lhs When to Shift vs Reduce 0 Decide based on the left string the stack 0 Idea use a nite automaton DFA to decide when to shift or reduce 0 The DFA input is the stack 0 The language consists of terminals and nonterminals 0 We run the DFA on the stack and we examine the resulting state X and the tokenT after D 0 If X has a transition labeled T then shift 0 If X is labeled with A B on T then reduce LR I parsing diagram Representing the DFA O Parsers represent the DFA as a 2D table 0 Recall tabledriven lexing 0 Rows correspond to DFA states 0 Columns correspond to terminals and nonterminals 0 Typically columns are split into 0 Those for terminals action table 0 Those for nonterminals goto table representing the DFA diagram LR Parsing Algorithm After a shift or reduce action rerun the DFA on the entire stack Remember for each stack element to which state it brings the DFA LR parser maintains a stack ltsyml stategt ltsymn statengt statelt is the nal state of the DFA on ltsym symkgt LR Parsing Algorithm Let I w be initial input Let 0 Let DFA state 0 be the start state Let stack dummy 0 repeat case action topstatestacklj of shift k push ljk reduce X v 0 pop X pairs push X Goto to pstate stack X accept halt normally error halt and report error LR Parsing Notes Can parse more grammars than LL next lecture Most programming languages are LR Can be described as a simple table There are tools for building the table How is the table constructed Status 0 Today 55pm Project Due 0 Project 2 Due FridayApr 24 55pm LL Parsing A piece of cake after LR Lecture Dr Sean Peisert ECS I42 Spring 2009 i LL Parsing 0 Still speci ed using a CFG 0 Still reads lefttoright 0 Now is leftmost derivation XL rather than rightmost XR O Constructed from the top in the order that tokens appear in the token stream Parsing Algorithms LL LR E E gt2 EE E 393 2E E gtEE 2EE Egt8 23E EgtEE 238 5quot5 LR vs LL 0 LR bisonCUP harder to implement but allows more grammars 0 LL easier to write but less flexible in the grammars Recursive Descent Parsing 0 Consider the grammar 0 E gt T E T 0 Tgt intintTE O Token stream is int5 intz 0 Start with toplevel nonterminal E 0 Try the rules E in order Recursive Descent Parsing 0 E0 TI E2 0 Then try a rule forTl 39 E3 0 But does not match the input token ints 0 TryTl 39 int Token matches 0 But afterTl does not match the input token 0 TryTl 39 intTz O This will match but afterTl will be unmatched 0 Have exhausted the choices forTl 0 Backtrack to choice for E0 Recursive Descent Parsing 0 E0 9 TI 0 Follow same steps as before forTl 0 And succeed with TI 39 int T2 and T2 39 int Recursive Descent Parsing Parsing given a string of tokens tt2t3t4t5 nd its parse tree Recursive descent parsing Try a of the productions exhaustively At a given moment the nge of the parse tree isztl t1 tkA Try a the productions fork if A 39 BC is a productionthe new nge is tt2 tk BC Backtrack where the nge doesn t match the string Stop when there are no more nonterminals Construction of Decision Table 0 for each rule X 39 X 0 for each a in Firstx 0 table XaX39 X 0 so if we see the very rst symbol match the rule 0 if E is in Firstapha 0 for each h in FollowsX 0 tableX b X gt x 0 That s it NonLL Grammars 0 There are a lot of nonLL grammars The patterns to look for are 0 LeftRecursive rules goes into an in nite loop 0 which must be rewritten as rightrecursive 0 Common pre x rules 0 which must be rewritten to move the common pre x to one rule Left Recursion 0AgtAa 0Agtb 0 For LL FirstA gt Aa b 0 For LL FirstA gt b b 0 this gives a conflict Rewrite the Grammar 0AgtbA 0A gtaA 0A 39E Common Pre x 0Xgtabc X 39abd O This works for LR O For LL the parser only looks at the First set of rules not the entire rule 50 the rules cause a conflict Rewritten Grammar 0XgtabY 0Ygtc Y 39d Recursive Descent 0 Simple and general but unpopular and slow because of backtracking O Often we can avoid backtracking somewhat Predictive Parsing 0 Like recursivedescent but parser can predict which production to use 0 By looking at the next few tokens O No backtracking O Predictive parsers accept LLk grammars LL I Languages 0 In recursivedescent for each nonterminal and input token there may be a choice of production 0 LLI means that for each nonterminal and tokenthere is only one production that could lead to success 0 Can be specified as a 2D table 0 dim for curent nonterminal to expand 0 dim for neXt token 0 A table entry contains one production Example Grammar l OGrammar 0 EgtTET 0TgtintintTE O Impossible to predict becauseT has two productions with int For E it is not clear how to predict 0 Grammar must be leftfactored Left Factoring 0 Grammar 0 E gt T E T 0 Tgt intintTE 0 Factor out common pre xes of productions 0 E gt T X o X gt E g 0 T gt E intY 0 Y gt T E LL I Parse Table Example 0 LeftFactored Grammar 0 E gt T X X gt E E 0 TgtEintY YgtTE 0 The LLI parsing table is a special end marker LL I Parse Table 0 Consider the E int entry 0 When current nonterminal is E and next input is int use production E gt TX 0 This production can generate an int in the rst place 0 Consider the Y entry 0 When current nonterminal is y and current token is get rid on 0 We ll see later why this is so LL I Parse Table 0 Blank entries indicate error situtations O Eg consider the E gt entry 0 There is no way to derive a string starting with from nonterminal E Using Parse Tables 0 Similar to recursive descent except 0 For each nonterminal S 0 We look at the next token a 0 And choose the production shown at Sa 0 Use a stack to keep track of pending nonterminals 0 Reject when we encounter an error state 0 Accept when we encounter an endtoinput LL I Parsing Algorithm initialize stack ltS gt and next pointer to tokens repeat case stack of ltX restgt ifTX next YiYn then stack YiYn restgt else error ltt restgt ifT next then stack ltrestgt else error until stack lt gt LL I Parsing Example int int terminal 1 Example Grammar 2 0DgtvLcT 0LgtLmi 0Lgti 0Tgtr OvVarLdList O ccoonTtype O m commai id r REAL After xing L which was rightrecursive 0DgtvLcT 0LgtiX 0XgtmiX 0X 39E T Vr Algorithm 0 start with the start symbol on the stack 0 repeat until done 0 if top of stack rst char of input 0 pop l of stac advance input 0 else if top of stack nonterminal T 0 consult T input 0 if Tinput T 39 X P P 0 push input in reverse order 0 rintT 39 X reduce 0 else if Tinput empty rel ct 0 else if stack is empty and input is empty 0 accept I else if stack is empty and input is not empty 0 eject LL Decision Table input vimicr vimicr imicr imicr micr action Dvmatch D 9 vLcTpop v v match so Li match L 9 iX ii match X m match X 9 miX m m match ii match c matchX 9 E cc match Tr matchT 9 r r r39 match Done Accept Type Checking in Cool n Lecture I8 Dr Sean Peisert ECS I42 Spring 2009 Status 0 2 weeks to go on project 3 O Readskim Ch 6 by Monday May 0 Read Sec 7 through 74 by Monday May I8 Handling the SELFTYPE U nSoundness 0 Type preservation 0 Types in programs should remain invariant under evaluation or reduction rules of a language 0 Progress 0 Programs should never enter unde ned states where no transitions are possible 0 Related to memory safety copying arbitrary bits btwn locations 0 Examples lmproper allocationdeallocation of memory Dangling pointers C allows many unchecked conversions Linked libraries can sometimes cause problems even at runtime An Example class Count 0 Class Count i zint 0 incorporates a counter inco COUm 0 The inc method works for any subclass 0 But there is disaster I I l lurklng In the type SElf system An Example 0 Consider a subclass Stock of Count class Stock inherits Count name String name of item 0 And the following use of Stock class Main Stock a new Stockinc Type checking error aname What Went Wrong We want new Stockinc to be of type Count But new Stockinc has dynamic type Stock So it is legitimate to write 0 Stock a new Stockinc But this is not welltyped 0 new Stockinc has static type Count The type checker loses type information This makes inheriting inc useless 0 So we must rede ne inc for each of the subclasses with a specialized return type SELFTYPE to the Rescue 0 We will extend the type system 0 Insight inc returns self Therefore the return value has same type as self Which could be Count or any subtype of Count In the case of new Stockinc the type is Stock 0 We introduce the keyword SELFTYPE to use for the return value of such functions 0 We will also need to modify the typing rules to handle SELFTYPE SELFTYPE to the Rescue 0 SELFTYPE allows the return type of inc to change when inc is inherited 0 Modify the declaration of inc to read 0 inc SELFTYPE O The type checker can now prove 0 CM i new Countinc Count 0 O M i new Stockinc Stock 0 The program from before is now well typed Notes about SELFTYPE O SELFTYPE is not a dynamic type 0 It is only a static type It helps the type checker to keep better track of types It enables the type checker to accept more correct programs In short having SELFTYPE increases the expressive power of the type system SELFTYPE and Dynamic Types Examples 0 What can the dynamic type of the object returned by inc 0 Answer whatever could be the type of self classA inherits Count class B inherits Count class C inherits Count inc could be invoked through any of these classes 0 Answer Count or any subtype of Count SELFTYPE and Dynamic Types Example 0 In general if SELFTYPE appears textually in the class C as the declared type of E then it denotes the dynamic type of the sef expression dynamictypeE dynamictypeself s C 0 Note the meaning of SELFTYPE depends on where it appears 0 We write SELFTYPEc to refer to an occurrence of SELFTYPE in the body of C Type Checking 0 This suggests a typing rule SELFTYPEc s C 0 This rule has an important consequence 0 In type checking it is always safe to replace SELFTYPEc by C 0 But that would disallow some programs 0 This suggests one way to handle SELFTYPE 0 Replace all occurrences of SELFTYPEc by C 0 This would be correct but it is like not having SELFTYPE at all Operations on SELFTYPE 0 Recall the operations on types 0 TI S T2 TI is a subtype osz 0 ubTT2 the leastupper bound ole and T2 0 We must extend these operations to handle SELFTYPE Extending S 0 LetT and T be any types but SELFTYPE 0 There are four cases in the de nition of S I SELFTYPEc S T if C S T 0 SELFTYPEc can be any subtype of C 0 This includes C itself 0 Thus this is the most flexible rule we can allow 2 SELFTYPEc S SELFTYPEc 0 SELFTYPEc is the type of the self expression 0 ln Cool we never need to compare SELFTYPEs coming from different classes Extending S 3 T S SELFTYPEc 0 Note SELFTYPEc can denote any subtype of C 4 T S T according to the rules from before 0 Based on these rules we can extend lub N w Extending ubTT LetT and T be any types but SELFTYPE Again there are four cases ubSELFTYPEc SELFTYPEc SELFTYPEc ubSELFTYPEc T ubCT 39 This is the best we can do because SELFTYPEc S C ubT SELFTYPEc ubCT 4 lub T T de ned as before Where Can SELFTYPE Appear in COOL I The parser checks that SELFTYPE appears only where a type is expected I But SELFTYPE is not allowed everywhere a type can appear I classT inherits T I TT cannot be SELFTYPE 0 Because SELFTYPE is never a dynamic type 2 x T I T can be SELFTYPE I An attribute whose type is SELFTYPEc Where Can SELFTYPE Appear in COOL 3 let X T in E 0 T can be SELFTYPE 0 X has type SELFTYPEc 4 newT 0 T can be SELFTYPE 0 Creates an object of the same type as self 5 mTEEn 0 T cannot be SELFTYPE Typing Rules for SELFTYPE Since occurrences of SELFTYPE depend on the enclosing class we need to carry more context during type checking New form of the typing judgment 0 MC I e T An expression e occurring in the body of C has static type T given a variable type environment 0 and method signatures M Type Checking Rules 0 The next step is to design type rules using SELFTYPE for each language construct 0 Most of the rules remain the same except that S and lub are the new ones Oid To O I e TI TI STo O I id eT 2 I l What s Different Recall the Old Rule for Dispatch OMC l eo To OMC l ei TI 0 M C l en Tn MTo f TI Tn Tn Tn l SELFTYPE TiSTi for l S i S n O M C l eofeen Tn 22 I l What s Different 0 If the return type of the method is SELFTYPE then the type of the dispatch is the type of the dispatch expression OMC I eo To 0 M C I en Tn MTo f TI Tn SELFTYPE TiSTi for S i S n 23 I l What s Different 0 This rule handles the Stock example 0 Formal parameters cannot be SELFTYPE 0 Actual arguments can be SELFTYPE 0 The extended S relation handles this case 0 The type To of the dispatch expression could be SELFTYPE 24 I l Static Dispatch Recall ltexprogtlttypegtidltexprgtltexprngt Provides a way of accessing parent classes that have been hidden by rede nitions in child classes Eg Class B has method f class C rede nes f and we re in class C but want to call the f in B not In normal dispatch ltexprogt would determine the class method used In static dispatch lttypegt determines this Eg eBf invokes f in class B on the object that is the value of e The static type of ltexprogt must conform to lttypegt Static Dispatch Recall the Old Rule for Static Dispatch OMC l eo To 0 M C l en Tn To S T MT f Ti Tn Tn SELFTYPE Tn l SELFTYPE TiSTi for S i S n 26 I l Static Dispatch 0 If the return type of the method is SELFTYPE we have OMC I eo To 0 M C I en Tn To S T MT f TI Tn SELFTYPE TiSTi for S i S n O M C I eoTfeen To 27 I l Static Dispatch 0 Why is this rule correct 0 If we dispatch a method returning SELFTYPE in class T don t we get back aT O No SELFTYPE is the type of the self parameter which may be a subtype of the class in which method appears 0 The static dispatch class cannot be SELFTYPE New Rules 0 There are two new rules using SELFTYPE O M C I selfSELFTYPEc O M C I new SELFTYPE SELFTYPEc 0 There are a number of other places where SELFTYPE is used Where SELFTYPE Cannot Appear in COOL mx T T 0 OnIyT can be SELFTYPE What could go wrong ifT were SELFTYPE classA compx SELFTYPE Bool class B inheritsA b int compx SELFTYPE Bool xb let x A new B in xcompnewA Summary of SELFTYPE 0 The extended s and lub operations can do a lot of the work Implement them to handle SELFTYPE 0 SELFTYPE can only be used in a few places Be sure it isn t used anywhere else 0 A use of SELFTYPE always refers to any subtype in the current class 0 The exception is the type checking of dispatch 0 SELFTYPE as the return type in an invoked method might have nothing to do with the current class Why Cover SELFTYPE 0 SELFTYPE is a research idea 0 It adds more expressiveness to the type system 0 SELFTYPE is itself not so important except for the project 0 Rather SELFTYPE is meant to illustrate that type checking can be quite subtle O In practice there should be a balance between the complexity of the type system and its expressiveness Type Systems 0 The rules in these lectures were Coolspeci c O Other languages have very different rules 0 General themes 0 Type rules are de ned on the structure of expressions 0 Types of variables are modeled by an environment 0 Types are a play between flexibility and safety Semantic Analysis 0 Semantic analysis type checking and scoping check for errors 0 They also determine the behavior of the resulting program Translate Very Roughly class Main data main0nt 0 align 2 globl classnameTab globl Mainprot0bj globl ntprotObj Maininit addiu sp sp 2 sw fp 2sp sw 50 8sp sw ra 4sp addiu fp sp 4 move 50 210 A Huge Step 0 General problem is bridging the semantic gap 0 Cool is highlevel 0 MIPS is lowlevel 0 Size of gap implies we might want to bridge in smaller steps 0 Also these two operate via different paradigms 0 names vs memory addresses amp registers 0 calls vs gotos 0 typed vs untyped 0 Need a model for bridging this Bridging Concept Includes 0 A call stack for managing callreturn 0 A call frame for managing local data 0 base offset addressing for variables 0 registers used as temporaries not longterm storage 0 calling conventions for keeping this data straight 0 A memory heap for dynamically allocated memory