Compiler Design CIS 631
Popular in Course
Popular in Computer & Information Science
This 38 page Class Notes was uploaded by Lindsay Bergstrom Sr. on Wednesday October 21, 2015. The Class Notes belongs to CIS 631 at Syracuse University taught by Staff in Fall. Since its upload, it has received 51 views. For similar materials see /class/225600/cis-631-syracuse-university in Computer & Information Science at Syracuse University.
Reviews for Compiler Design
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/21/15
Runtime Environments The compiler creates and manages a run time environment in which it assumes the target program Will be executed 0 Issues for run time environment Layout and allocation of storage locations for named program objects Mechanism for the target program to access variables Linkages between procedures Mechanisms for passing parameters Interfaces to the operating system for IO and other programs Storage Organization 0 Assumes a logical address space Operating system will later map it to physical addresses decide how to use cache memory etc 0 Memory typically divided into areas for Program code Other static data storage including global constants and compiler generated data Stack to support callreturn policy for procedures Heap to store data that can outlive a call to a procedure gt Code Static Heap Free Memory Stack Runtime stack 0 Each time a procedure is called or a block entered space for local variables is pushed onto the stack 0 When the procedure is terminated the space is popped off the stack 0 Procedure activations are nested in time If procedure p calls procedure q then even in cases of exceptions and errors q will always terminate before p 0 Activations of procedures during the running of a program can be represented by an activation tree 0 Each procedure activation has an activation record aka frame on the run time stack The runtime stack consists of the activation records at any point in time during the running of the program for all procedures which have been called but not yet returned Procedure Example quicksort int al l void readArray gt lt Reads 9 integers into al through a9 gtk int i int partition int m int n gt lt picks a separator V and partitions am n so that am pl are less than V ap V ap1 n are equal to or greater than V Returns p gtk void quicksort int m int n int i if n gt m i partitionmn quicksortm il quicksortil n main readArray aO 9999 alO 9999 quicksort l 9 Activation Records 0 Elements in the activation record temporary values that could not fit into registers local variables of the procedure saved machine status for point at which this procedure called includes return address and contents of registers to be restored access link to activation record of previous block or procedure in lexical scope chain control link pointing to the activation record of the caller space for the return value of the function if any actual parameters or they may be placed in registers if possible actual params return values control link access link saved machine state local data temporaries Procedure Linkage The standardized code to call a procedure the calling sequence and the return sequence may be divided between the caller and the callee parameters and return value should be first in the new activation record so that the caller can easily compute the actual params and get the return value as an extension of its own activation record also allows for procedures with a variable number of params fixedlength items are placed in the middle of the activation record saved machine state is standardized local variables and temporaries are placed at the end especially good for the case when the size is not known until runtime such as with dynamic arrays location of the topof stack pointer is commonly at the end of the fixedlength fields fixed length data can be accessed by local offsets known to the intermediate code generator relative to the TOPSP negative offsets variable length fields are actually above the top of stack pointer and their offsets calculated at runtime via positive offsets from the TOPSP Activation Record Example 0 Showing one way to divide responsibility between the caller and the callee K actual params and return val Caller A39R39 control link access link Af and saved machlne state local data and temporaries can responsibility actual params and return val Callee A39R39 control link access link 4 and saved machine state v TOPSP 39 Callee L local data and temporaries responsibility actual top of stack 7 Calling Sequence 0 A possible calling sequence matching the previous diagram caller evaluates the actual parameters caller stores the return address and old value of TOP SP in the callee s AR Caller then increments TOP SP to the callee s AR Caller knows the size of the caller s local data and temps and the callee s parameters and status fields Caller jumps to callee code callee saves the register values and other status fields callee initializes local data and begins execution Return Sequence 0 Corresponding return sequence callee places the return value next to the parameters using information in the status fields callee restores TOP SP and other registers Callee jumps to the return address that the caller placed in the status field Although TOP SP has been restored to the caller AR the caller knows Where the return value is relative to the current TOP SP Variablelength data on the stack 0 It is possible to allocate objects arrays or other structures of unknown size on the stack as long as they are local to a procedure and become inaccessible When the procedure ends 0 For example represent a dynamic array in the activation record by a pointer to an array located between the activation records actual params and return val proc p control link access link and saved machine state pointer to array a array a actual params and return val pI OC q 1 control link access link and saved machine state local data and temporaries Access to Nonlocal Data on the Stack Simplest case are languages Without nested procedures or classes C and many C based languages 0 All variables are defined either Within a single procedure function or outside of any procedure at the global level 0 Allocation of variables and access to variables Global variables are allocated static storage Locations are xed at compile time All other variables must be local to the activation on the top of the stack These variables are allocated when the procedure is called and accessed via the TOPSP pointer Nested procedures Will use a set of access links to access variables at other levels on the stack Nested Procedure Example Outline in ML fun sortinputFile outputFile let val a array 11 0 fun readArray inputFile a body of readArray accesses a fun exchange i j a so does exchange fun quicksort m n let val V fun partition y z a V exchange in a V partition quicksort end in a readArray quicksort end the function sort accesses a and calls readArray and quicksort12 Access Links 0 Access links allow implementation of the normal static scope rule if procedure p is nested immediately within q in the source code then the access link of an activation of p points to the more recent activation of q Access links form a chain one link for each lexical level allowing access to all data and procedures accessible to the currently executing procedure 0 Look at example of access links from quicksort program in ML previous slide Defining Access Links for direct procedure calls 0 Procedure q calls procedure p explicitly case 1 procedure p is at a nesting depth 1 higher than q can t be more than 1 to follow scope rules Then the access link is to the immediately preceding activation record of p example quicksort calls partition case 2 recursive call ie q is p itself The access link in the new activation record for q is the same as the preceding activation record for q example quicksort called quicksort case 3 procedure p is at a lower nesting depth than q Then procedure p must be immediately nested in some procedure r de ned in r and there must be an activation record for r in the access chain of q Follow the access links of q to find the activation record of r and set the access link of p to point to that activation record of r partition calls exchange which is de ned in sort Defining Access Links parameter procedures 0 Suppose that procedure p is passed to q as a parameter When q calls its parameter Which may be named r it is not actually known which procedure to call until run time 0 When a procedure is passed as a parameter the caller must also pass along With the name of the procedure the proper access link for that parameter 0 When q calls the procedure parameter it sets up that access link thus enabling the procedure parameter to run in the environment of the caller procedure Displays If the nesting depth of access links gets large then access to nonlocal variables will be inefficient to follow the chain of access links Solution is to keep an auxiliary array the display in which each element is the highest activation record on the stack for the procedure at that nesting depth Whenever a new activation record is created at level 1 it will save the value of displayl to restore when it is done display stack dl d2 d3 S OH q19 saved d2 I q13 saved d2 T p13 saved d3 e13 saved d2 Dangling pointers in the stack 0 In a stack based environment typically used for parameters and local variables variables local to a procedure are removed from the stack When the procedure exits 0 There should not be any pointers still in use to such variables 0 Example from C intgt lt danglevoid int x return ampX 0 An assignment addr dangle causes addr to point to a deallocated stack location In C this is considered to be a programming error not one that the compiler checks for 17 Organization of Memory for Arrays 18 Heap Management 0 Store used for data that lives inde nitely or until the program explicitly deletes it 0 Memory manager allocates and deallocates memory in the heap serves as the interface between application programs generated by the compiler and the operating system calls to free and delete can be generated by the compiler or in some languages explicitly by the programmer 0 Garbage Collection is an important subsystem of the memory manager that finds spaces Within the heap that are no longer used and can be returned to free storage the language Java uses the garbage collector as the deallocation operation Memory Manager The memory manager has one large chunk of memory from the operating system that it can manage for the application program 0 Allocation When a program requests memory for a variable or an object anything requiring space the memory manager gives it the address of a chunk of contiguous heap memory if there is no space big enough can request the operating system for Virtual space if out of space inform the program 0 Deallocation returns deallocated space to the pool of free space doesn t reduce the size of space and return to the operating system 20 Properties of Memory Manager 0 Space efficiency minimize the total heap size needed by the program accomplished by minimizing fragmentation 0 Program efficiency make good use of the memory subsystem to allow programs to run faster locality of placement of objects 0 Low overhead important for memory allocation and deallocation to be as efficient as possible as they are frequent operations in many programs 21 Memory Hierarchy 0 Registers are scarce explicitly managed by the code generated by the compiler 0 Other memory levels are automatically handled by the operating system chunks of memory copied from lower level to higher level as HBCBSSEII y typical sizes typical access times 33915 disk gt2GB 256MB 2GB lOOlSOns 125KB 4MB 4060ns 16 64KB 510nd 32 words lns 22 Taking Advantage of Locality 0 Programs often exhibit both temporal locality accessed memory locations are likely to be accessed again soon spatial locality memory close to locations that have been accessed are also likely to be accessed 0 Compiler can place basic blocks sequential instructions on the same cache page or even the same cache line 0 Instructions belonging to the same loop or function can also be placed together 23 Placing objects in the heap 0 As heap memory is allocated and deallocated it is broken into free spaces the holes and the used spaces on allocation a hole must be split into a free and used part 0 Best Fit placement is deemed the best strategy uses the smallest available hole that is large enough this strategy saves larger holes for later possibly larger requests 0 Contrasted to the First Fit strategy that uses the first hole on the list that is large enough has a shorter allocation time but is a worse overall strategy 0 Some managers use the bin approach to keeping track of free space for many standard sizes keep a list of free spaces of that size keep more bins for smaller sizes as they are more common makes the best fit strategy more efficient 24 Coalescing Free Space 0 When an object is freed it Will reduce fragmentation if we can combine the deallocated space With any adjacent free spaces 0 Data structures to support coalescing boundary tags at each end of the chunk keep a bit indicating whether the chunk is free and keep its size doubly linked embedded free list pointers to next free chunks are kept at each end next to the boundary tags 0 When B is deallocated it can check if A and C are free and is so coalesce blocks and adjust the links of the free list chunk A chunk B chunk C 0200 2000 0100 1000 080 800 pointers doubly link free chunks not in physical order 25 Problems with Manual Deallocation 0 It is a notoriously difficult tasks for programmers or compilers to correctly decide when an object will never be referenced again 0 If you use caution in deallocation then you may get chunks of memory that are marked in use but are never used again memory leaks 0 If you deallocate incorrectly so that at a later time a reference is used to an object that was deallocated then an error occurs dangling pointers 26 Garbage Collection In many languages program variables have pointers to objects in the heap e g through the use of new These objects can have pointers to other objects Everything reachable through a program variable is in use and everything else in the heap is garbage in an assignment X y an object formerly pointed to by X is now garbage if X were the last pointer to it A requirement to be a garbage collectible language is to be type safe we can tell if a data element or component of a data element is a pointer to a chunk of memory true for Java ML not true for C C H I gt CD g 27 Performance Metrics 0 Overall execution time garbage collection touches a lot of data and it is important that it not substantially increase the total run time of an application 0 Space Usage garbage collector should not increase fragmentation Pause time garbage collectors are notorious for causing the application to pause suddenly for a very long time as garbage collection kicks in as a special case realtime applications must be assured that they can achieve certain computations within a time limit 0 Program locality garbage collector also controls the placement of data particularly ones Which relocate data 28 Reachability The data that can be accessed directly by the program Without any deferencing is the root set and its elements are all reachable the compiler may have placed elements of the root set in registers or on the stack 0 Any object With a reference stored in the field members or array elements of any reachable object is also a reachable object 0 The program sometimes called the mutator can change the reachable set object allocation by the memory manager parameter passing and return values objects pointed to by actual parameters and by return results remain reachable reference assignments X y procedure returns if the only reference to a reachable object is popped off the stack then that object becomes unreachable 29 Reference Counting Garbage Collectors 0 Keep a count of the number of references to any object and when the count drops to 0 the object can be returned to free 0 Every object keeps a eld for the reference count which is maintained object allocation the count of a new object is l parameter passing the reference count of an actual parameter object is increased by 1 reference assignments X y reference count of object referred to by y goes up by 1 reference count of old object pointed to by X is decreased by l procedure returns objects pointed to by local variables have counts decremented transitive loss of reachability whenever the count of an object goes to 0 we must decrement by 1 each of the objects pointed to by a reference within the object Simple but imperfect cannot do circular objects 0 Overhead is very high but is incrementally spread over execution 30 Basic Mark and Sweep Garbage Collection 0 Trace based algorithms recycle memory as follows program runs and make allocation requests garbage collector discovers reachability by tracing unreachable objects are reclaimed for storage 0 The Mark and Sweep algorithms use four states for chunks of memory Free ready to be allocated during any time Unreached reachability has not been established by gc when a chunk is allocated it is set to be unreached Unscanned chunks that are known to be reachable are either scanned or unscanned an unscanned object has itself been reached but its points have not been scanned Scanned the object is reachable and all its pointers have been followed 31 Mark and Sweep Algorithm 0 Stop the program and start the garbage collector 0 Marking phase set Free list to be empty set the reached bit to l and add root set to the list Unscanned loop over unscanned list remove object o from unscanned list for each pointer p in object if p is unreached bit is 0 set the bit to l and put p in unscanned list 0 Sweeping phase for each chunk of memory 0 in the heap if 0 is unreached add 0 to the Free list otherwise set the reached bit to 0 32 Baker s Mark and Sweep algorithm 0 The basic algorithm is expensive because it examines every chunk in the heap 0 Baker s optimization keeps a list of allocated objects 0 This list is used as the Unreached list in the algorithm Scanned 2 empty set Unscanned 2 root set loop over Unscanned set move object o from Unscanned to Scanned for each pointer p in o if p is Unreached move p from Unreached to Unscanned Free 2 Free Unreached Unreached Unscanned 33 Copying Collectors Relocating 0 While identifying the Free set the garbage collector can relocate all reachable objects into one end of the heap while analyzing every reference the gc can update them to point to a new location and also update the root set 0 Mark and compact moves objects to one end of the heap after the marking phase 0 Copying collector moves the objects from one region of memory to another as it marks extra space is reserved for relocation separates the tasks of finding free space and updating the new memory locations to the objects 0 gc copies objects as it traces out the reachable set 34 ShortPause Garbage Collection Incremental garbage collection interleaves garbage collection with the mutator incremental gc is conservative during reachability tracing and only traces out objects which were allocated at the time it begins not all garbage is found during the sweep oating garbage but will be collected the next time Partial Collection the garbage collector divides the work by dividing the space into subsets Usually between 8098 of newly allocated objects die young ie die within a few million instructions and it is cost effective to garbage collect these objects often Generational garbage collection separates the heap into the young and the mature areas If an object survives some number of young collections it is promoted to the mature area The train algorithm is used to collect multigeneration areas 35 Parallel and concurrent garbage collection 0 A garbage collector is parallel if it uses multiple threads and it is concurrent if it runs in parallel with the mutator 66 based on Dijkstra s onthe y garbage collection coloring the reachable nodes white black or gray 0 This version partially overlaps gc with mutation and the mutation helps the gc Find the root set with the mutator stopped Interleave the tracing of reachable objects with the mutators 0 whenever the mutator writes a reference that points from a Scanned object to an Unreached object we remember it called the dirty objects Stop the mutators to rescan all the dirty objects which will be quick because most of the tracing has been done already 36 Cost of Basic Garbage Collection 0 Mark phase Depth first search takes time proportional to the number of nodes that it marks ie the number of reachable chunks Sweep phase time proportional to the size of the heap 0 Amortize the collection divide the time spent collecting by the amount of garbage reclaimed R chunks of reachable data H is the heap size cl is the time for each marked node and c2 the time to sweep clR 02H H R 0 If R is close to H this cost gets high and the collector could increase H by asking the operating system for more memory 37 References Aho Lam Sethi and Ullman Compilers Principles Techniques and Tools Addison Wesley 2006 The purple dragon book 0 Keith Cooper and Linda Torozon Engineering at Compiler ElseVier 2004 38