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


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

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 122 page Class Notes was uploaded by Orrin Rutherford on Wednesday September 2, 2015. The Class Notes belongs to CS 322 at Portland State University taught by Staff in Fall. Since its upload, it has received 17 views. For similar materials see /class/168284/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/02/15
38322 Languages and Compiler Design II Lecture 3 123104 PSU C8322 W3905 C Andrew Tolmach 19972005 Introduction to SPARC Architecture SPARC Scaleable Processor ARChitecture One of original RISC machines RISC 2 Reduced Instruction Set Computer Developed from research at UCBerkeley ca 1980 Commercialized by Sun Microsystems Licensed freely to others Similar parallel effort at Stanford led to MIPS machine Also IBM RS6000 HPPA DEC ALPHA PowerPC etc Key idea simple uniform instruction set allowing fast cycle times and fast time to market Has eclipsed CISC machines C Complex like the DEC VAX but not the Intel X86 line V8 is 32bit version V9 is 64bit extension with extra instructions We39ll assume V8 in this course 123104 PSU C8322 W3905C Andrew Tolmach 19972005 SPARC 32 generalpurpose registers Only simple loadstore to memory 1d r2 r3 1d r2 12 r3 1d r2 r7 r3 13 bit signed offset All arithmeticlogical ops are registertoregister add r2 r1 r1 add r2 17 r5 13 bit signed immediate Ops set condition codes which are tested by Bicc ops eg bne 1abe1 branch if 1ast op result ltgt 0 b1e 1abe1 branch if 1ast op resu1t lt 0 Special instruction to load highorder bits of fullword constant sethi hiva1ue r7 net effect is to load or r7lova1ue r7 all of value into r7 123104 PSU c5322 W3905C Andrew Tolmach 19972005 3 SPARC Delayed Branches Implementation is pipelined It takes time to process a branch because must fetch and decode target instruction So Why not execute a useful instruction in the meantime Specify this instruction by placing it in the delay slot tst r6 executes first bne L1 executes third inc r5 delay slot executes second whether or not branch is executed Also applies to calls and returns ca11 fred move 99 oO executes before ca11 move oO 17 executes after ca11 Loads stores oating point ops may also cause delays but programmer generally can t see these directly 123104 PSU CS3 W3905C Andrew Tolmach 19972005 SPARC Register Windows Very important to keep data parameters locals temporaries etc in registers as much as possible Subroutines normally mess up register allocation because registers must be saved at a call at least if the callee is unknown This can be done before the call callersave or after calleesave in either case register contents must be stored on stack which is slow SPARC idea provide multiple separate sets of registers one for each active subroutine Register names look alike in each routine but actual registers referred to are different The visible set of registers is called the register Window 123104 PSU C8322 W3905C Andrew Tolmach 19972005 SPARC Registers Actually want some of the Visible registers to be shared between callercallee to pass arguments a overlapping windows There are 32 registers Visible in each routine 8 are global shared among all routines g0 g7 r0 r7 8 are local to routine 1017 r16r23 8 are shared with caller so contain inputs also contain return values i0 i7 r24 r31 fp i6 8 are shared with callee so are outputs 00 07 r8 r15 sp 06 123104 PSU CS322 W3905C Andrew Tolmach 19972005 6 SPARC Register Window Shifts At top of each routine a save instruction is used to shift the window so that the caller s out registers become the callee s in registers The restore instruction reverses the process Suppose f calls g and b calls h f 1017 1017 ooo7 save 9 1017 1017 ooo7 erestore h 1017 1017 0007 123104 PSU C8322 W3905C Andrew Tolmach 19972005 7 SPARC More register windows How many windows can exist at one time Answer Implementationdependent Example Many current machines have 7 windows so 8 global 7 x 8 local 7 x 8 shared inputoutput 120 physical registers What happens when we run out of windows while trying to do a save Hardware traps to 08 which dumps Window contents onto the stack This also happens during a process context switch User code must cooperate by leaving 16 words free above sp at all times Is all this worth it Dubious 123104 PSU CS322 W3905C Andrew Tolmach 19972005 SPARC Activation Records for C sp always points to true top of stack fp frame pointer points to top of stack at entry to procedure used to reference stackpassed arguments and stackstored local variables The save instruction creates a stack frame by subtracting a specified number of bytes from sp and switching windows old sp becomes new fp But in simple cases arguments are just passed in registers oool etc for caller i0i 1 etc for callee and locals are kept in registers too 10etc so nothing important goes in frame Still always need to allocate a frame of minimum size 96 bytes If you store locals on the stack you may need more Hint Compiling with 02 will make cc try hard to avoid usingthe frame 12 04 PSU CS322 W3905C Andr Tolmach19972005 Memory fn Addresses l Caller s locals arg n gt 6 Caller Argument offsets are Frame 2 positive with arg l at 1 fp 174 and arg n at structure returnuaddr reserved fp 17 4 II1 4 register window area reserved sp 0 ofp Local offsets are negative with rst integer local at cause S locals fp 4 and n th integer local at fp n4 must not overlap Callee Fr me Callee s argument build area gt2 6 words Frame size structure return addr reserved 161 4 reglster w1ndow save maX6 maxargS 4 area reserved size oflocals rounded 0 OS u to multi le of8 S k p p p tac Growth 123104 PSU C8322 W3905C Andrew Tolmach 19972005 10 Sparc Calling Conventions Example int power int a int n if n gt 0 return a poweran l else return 1 section quottextquot align 4 global power power 1 i0 a i1 n save sp 96 sp 1 remap o bank to i bank push frame cmp il 0 1 compare nO blea done 1 branch if n lt2 O mov 1 i0 1 annulled Delay Slot return value 2 add il l ol 1 recursive call arg n n 1 call power 1 do recursive call mov iOoO 1 Delay Slot recursive call arg a a umul iOoOiO 1 return value l a recursive call39s return value done ret restore 1 Delay Slot remap i bank to o bank 1 pop frame 123104 PSU C8322 W3905C Andrew Tolmach 19972005 11 Optimizing Leaf Routines A routine that does not call any other routines called a leaf can sometimes execute in the same register Window and stack frame as its caller Hence no save and restore instructions are used Arguments now live in ol02 etc rather than being shifted into i1 i2 etc Similarly return value goes in 52500 Of course this only works if routine doesn39t trample on any registers that might be used by its caller GCC often uses this optimization See Architecture Manual Appendix D5 for details 123104 PSU CS322 W3905C Andrew Tolmach 19972005 12 Floating Point Registers There are 32 single precision 32bit oating point registers f0 f1 completely separate from integer registers and not windowed By convention they are managed as callersave registers ie it is the caller39s responsibility to save them if it needs to the callee can use them freely Doubleprecision 64 bit operations act on pairs of adjacent f registers the rst of the pair must have an even number eg f2 f3 is a valid pair To move a doubleprecision value from one pair of f registers to another must do two fmovs instructions fmovd is a synthetic instruction There is no way to move values directly between integer and fp registers must use memory 123104 PSU C8322 W3905C Andrew Tolmach 19972005 13 C8322 W OS Lecture Notes Lecture 5 PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 2 Expressions 0 Essential component of highlevel languages 0 Most familiar for arithmetic operators 0 Abstract away from precise order of evaluation naming of in termediate results x1 b sqrtbb 4ac 2 a ti b t2 bb t3 4a t4 t3c t5 t2 t4 t6 sqrtt5 t7 t1 t6 t82a t9 t7t8 0 Issue Precedence rules handled in parsing 0 Issue Mixedmode expressions and implicit coercions real ab intczab c int a int int b c int a real b illegal PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 3 Boolean expressions Many languages extend highlevel expression facility to non arithmetic values such as booleans o Operands true false booleanvalued variables 0 Operators and or not 0 Contexts Wherever a boolean value makes sense i f s wheres etc Remember that booleans are typically a separate type CC is an exception Issue Does language use shortcircuit evaluation for boolean ex pressions o a AND b evaluate b only if a evaluates to true oa OR b evaluatebonly if a evaluates to false if x lt 7 ampamp costlyy gt 6 if p 1 NULL ampamp p gtX gt 7 if x lt 7 printfquothellor1quot y gt 6 Common misuse of booleans BOOLEAN flag flag IF x lt 2 THEN true ELSE false PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 4 Richer expression domains Some languages support expressions over larger values e g vec tor strings etc int alO blO clO c a 5b C for i O i lt 10 i ci ai 5bi string a b c a C b amp substringc24 char abc int n maxstrlenc 24 a mallocstrlenb n l strcpyab strncpyastrlenbc2n astrlenbn O More generally can View operators as just special way of denot ing functions So to de ne expressions over an arbitrary type just de ne appropriate operator functions 0 Operator syntax precedence etc may be xed for language or programmerde nable 0 Issues like sharing storage management are tricky 0 Not all operators act like functions PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 5 Statementlevel Control Structures 0 Sequencing 0 Selection 0 Iteration Concurrency Primary mechanisms developed in FORTRAN and ALGOL60 mostly minor changes since then 30 years Talk of control structures as opposed to structureless code us ing got 0 s and indirect jumps spaghetti code Concurrent computation may be more natural for brains and hardware but appears hard to reason about accurately PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 6 Machinelevel Control Flow 0 Sequencing unless otherwise directed do the next instruction 0 Labels ie addresses in target code 0 Unconditional GOTOs o Arithmetic and logical IF THEN GOTO constructs These more than suf ce to compute anything that can be com puted as best we know PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 7 Structured Programming eg Edsger Dijkstra G0 to statement considered harmful CACM 113 March 1968 147148 Branches conditional and unconditional su ice to program any thing they are what machines use BUT problems are best solved in terms ofhigher level constructs such as loops and conditional blocks 0 Program text should make programmer s intent explicit 0 Static structure of program text should resemble dynamic struc ture of program execution Undisciplined use of GOTO s makes these goals hard to achieve Not just GOTOs are bad PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 8 Structured Programming Basic Elements Singleentry singleexit Loops while ltconditiongt loop ltstatementsgt end loop Can also put test at end Sometimes want it in the middle loop ltstatementsgt exit if ltconditiongt ltstatementsgt end loop Using exit violates singleexit goal If loops are nested want ab yUJexitanynun mrofbvds PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 9 Forloops for i in ltlower boundgtltupper boundgt loop ltstatementsgt end loop Conunonquemknm c When are bounds calculated Are they recalculated oChnltstatementsgtchmgevdueofi oIkmsilwveade nmlvduea mwheend loop 0 Can one jump into or out of loop othifupper boundislamthmllower boundtosmn VVl J Ciexanq e for i p i gt O i can be optimized better than for i1 i lt p i PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 10 Iteration is Recursion We can give recursive de nitions to the meaning of iterative state ments Example while ltconditiongt do ltstatementsgt is equivalent to if ltconditiongt then begin ltstatementsgt while ltconditiongt do ltstatementsgt end Any iteration can be converted to a recursion The converse is not true in general But any tailrecursion such as the one above can be converted into an iteration Any decent compiler should take advantage of this though many don t PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 11 Conditionals and Cases if ltconditiongt then ltstatementsgt elsif lt conditiongt then ltstatementsgt elsif else ltstatementsgt endif Vh ouspanscmibenns ng case ltexpressiongt of ltvaluelgtz ltstatementsgt ltvalue2gtz ltstatementsgt otherwise ltstatementsgt end case Permits more ef cient code a jump table if values are dense That s All Folks This small set of statements suf ces for nearly all programs PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 12 Taming goto Completely unrestricted jumps are seldom allowed It makes little sense to allow jumps into the middle of a block since none of the blocklocal storage will have been properly ini tialized Many languages permit jumps out to enclosing blocks in a stack allocation scheme such jumps require quietly popping one or more frames Most languages provide special forms of escapes from structured program components such as loop exit These discourage uses of got 0 but some good uses remain PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 13 Uses for goto Problem Given a key value k search an array a for a matching entry and increment the corresponding element of an array b If not found add the new key to the end of a A solution with goto in C int i for i O i lt n i if ai k goto found n ai k bi 0 found bi PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 14 A solution with booleans in Java boolean found false inti0 while i lt n ampamp lfound if ai found true else i if lfound n 1 ai k bi O bi This is clumsier and slower PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 15 A solution with onelevel exit in Java boolean found false int i for i O i lt n i if ai k found true break 1 n n ai bi 0 bi This is better but still requires testing found below the loop PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 16 A solution with multilevel exit in Java In Java unlike CC we can break from any named enclosing block int i search for i O lt n i if ai k break search Il n ai k bi O bi This does the trick But is it any better than the original goto version PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 17 The COME FROM statement 10 J 1 ll COME FROM 20 12 PRINT J STOP l3 COME FROM 10 20 J J 2 R Lawrence Clark A linguistic contribution to GOTOless pro gramming Datamation 1912 1973 6263 But is this really a joke Even with a GO TO we must examine both the branch and the target label to understand the programmer s intent PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 18 Exceptions Programs often need to handle exceptional conditions ie devi ations from normal control ow Exceptions may arise from 0 failure of builtin or library operations eg division by zero end of le 0 userde ned events eg key not found in dictionary Awkward or impossible to deal with these conditions explicitly Without distorting normal code Most recent languages Ada C Java etc provide a means to de ne raise and handle exceptions Ada example Help exception begin if gone wrong raise Help xab exception when Help gt report problem when NumericError gt X 99 end PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 19 VVhatudoinzulexcep onalcase o In most languages uncaught exceptions propagate to next dy namically enclosing handler E g caller can handle uncaught ex ceptions raised in callee foo throw Blahyucc bar int icky try icky foo catch Blah yucc icky yucc o A few languages support resumption of the program at the point where the exeption was raised okwapmwuhsatryfinallycmm ua f openfilen try catch Badinput cleanup finally closefilef PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 20 Fun with C Problem Sending characters to an output device as quickly as possible Given char p quothello worldquot char m p int n length of p define outputc do output Solution 1 for i O i lt n i outputm Faster maybe if n do outputm while n Avoids compare with 11 each time PS U C5322 W 05 Lecture 5 Andrew Tolmach 19922005 21 Faster t0 unroll 100p say 4 times while n amp 3 outputm I1 n 4 if n do output m output m output m output m while n Or the Duff Loop i n34 if n switch n amp 3 case 0 do outputm case 3 outputm case 2 outputm case 1 outputm while i Tins is ne n10st aniazhig piece of CII Ve ever seen Ben Thonqmon Garbage Collection Marius Nita marius cspdxedu Adapted from Andrew Tolmach s slides Hoping to cover Motivation amp basics 9 Introduction to three families of collection algorithms 9 Reference Counting 9 Mark amp Sweep 6 Copying Collection 9 Advanced issues and topics Motivation Problems with manual memory management Q It is extremely tedious and errorprone It introduces software engineering issues Who is supposed to free the memory o It is by no means intrinsically efficient free is not free Q In many cases the costs outweigh the benefits Garbage Collection GC e The automatic reclamation of unreachable memory aka garbage Q Universally used for high level languages with closures and complex data structures that are allocated implicitly Q Useful for any language that supports heap allocation Q It removes the need for explicit deallocation no more delete and free Q Let the GC implementor deal with memory corruption issues once and for all How does it work Typically The user program mutator is linked against a library known as the runtime system RTS eg libc In the RTS resides the memory allocation service which exposes an allocation routine to the user program When the user program desires more memory it invokes the allocation routine eg malloc The allocation service may then perform a collection to free unused memory before the allocation routine returns Terminology Heap A directed graph whose nodes are dynamically allocated records and whose edges are pointers between nodes Typically laid out in a contiguous memory space Root set The set of pointers into the heap from an external source eg the stack global variables Live data The set of heap records that are reachable by following paths starting at members of the root set Garbage The set of heap records that are not live Note reachability is a conservative liveness estimate Simple heap model For simplicity consider a simple heap of cons cells twofield records both fields are pointers to other records 3 GLOBALS STACK HEAP Reference counting Most straightforward collection strategy Q Add a counter field to each record Increment a record s counter when taking a new pointer to it o Decrement it when releasing a pointer to it Q When it reaches 0 put the record on a free list When allocating a new record check the free list first Reference counting simple easy to understand and implement Q immediate reclamation of storage no extended periods of time in which the collector might be running while the mutator waits Reference counting simple easy to understand and implement e immediate reclamation of storage no extended periods of time in which the collector might be running while the mutator waits However 9a Reference counting simple easy to understand and implement e immediate reclamation of storage no extended periods of time in which the collector might be running while the mutator waits However e space overhead one integer per record speed overhead every pointer assignment is wrapped in counter operations and checks Q too simpleminded can t collect cyclic garbage 9b Stop amp Collect There is no need to get rid of garbage if you do not have to A better approach is to wait until the allocator fails to allocate new memory due to lack of space Then The collector takes over and frees enough memory to satisfy the allocation request The allocation now succeeds or we re out of memory o Control is returned to the mutator This is known as stop amp collect mutator is effectively paused while the collector runs Mark amp Sweep Two phases 1 Mark each live record by tracing all pointers starting at the root 2 Sweep unmarked records garbage onto a free list making them available for reuse Unmark marked cells at the same time Already marked records are ignored in the marking step so termination is guaranteed MampS implementation struct cell int markzl struct cell c2 struct cell free heapEHEAPSIZE rootsRO0TS Initially all cells are on free list Use c O to link members of free list void initheap for i0 i lt HEAPSIZEl i heapi cO ampheapi1 heapHEAPSIZE1c0 0 free ampheap0 MampS implementation struct cell allocate struct cell newCell if free no more room gt gC try gc if free still no more room die newCell free take the first free cell free free gtcO off of the free list return newCell MampS implementation void gC for i0 iltRO0TS i markrootsi sweep void markstruct cell Cell if Cellgtmark cellgtmark 1 markcellgtCO markcellgtC1 void sweep for i0 iltHEAPSIZE i if heapi mark unmark live data heapi mark 0 else sweep garbage heapic0 free free ampheapi MampS implementation void gc for i0 iltRO0TS i markrootsi sweep void markstruct cell Cell if Cellgtmark cellgtmark 1 markcellgtCO markcellgtC1 void sweep for i0 iltHEAPSIZE i if heapimark unmark live data heapimark 0 else sweep garbage heapic0 free free ampheapi Notice anything strange about mark 14a MampS pointer reversal It s recursive void markstruct cell cell if lcellgtmark cellgtmark 1 markcellgtc0 markcellgtC1 It could use a lot of stack hence a lot of memory Pointer reversal is typically used to avoid this problem Copying collection Q Divide the heap into two semispaces Allocate into one space the tospace c When it fills up move the live data to the fromspace and reverse the roles of the two spaces Q Must reassign a pointers as a consequence Can t have a copying collector for C Q Inherently compacting no fragmentation problems good spatial locality Copying cont d ALLOCATION SPACE RESERVE SPACE START OF CYCLE DATA ALLOCATION SPACE RESERVE SPACE BEFORE COLLECTION quotDATA 3quot AREAGEquot RESERVE SPACE AELO AITION SPACE AFTER COLLECTION DATA Copying cont d o The live data is traversed breadthfirst using the tospace itself as the queue Cheney s algorithm d When a record is copied a forwarding pointer pointing to the new location is left in the original Q Subsequent attempts to forward that same record will immediately observe the forwarding pointer Copying cont d FROM SPACE ROOT SET To SPACE BEFORE COLLECTION a FROM SPACE ROOT SET To SPACE AFTER COLLECTION Copying details GRAPH B Root A Set E TO SPACE C D 1 S scan p01nter F free p01nter A B S F El copied but not scanned copled and scanned A B C all pointers are to S F to space 20 Copying implementation struct cell struct cell c2 struct cell space2HALFSIZE struct cell rootsRO0TS struct cell free ampspace0O struct cell end ampspace0HALFSIZE int fromspace 0 int tospace 1 struct cell allocate if free end no room gc if free end still no room die return free 21 Copying implementation gc int i struct cell scan ampspacetospace0 free scan for i O i lt ROOTS i rootsi forwardrootsi while scan lt free scan gtc0 forwardscan gtc0 scangtc1 forwardscangtc1 scan fromspace 1fromspace tospace 1tospace end spacefromspaceHALFSIZE 22 Copying implementation struct cell forwardstruct cell p if p gt ampspacefromspace0 ampamp p lt ampspacefromspaceHALFSIZE if p gtc0 gt ampspacetospace0 ampamp p gtCO lt ampspacetospaceHALFSIZE return pgtC0 else free p pgtCO free return p gtc0 else return p 23 Conclusions MampS Pros 9 Big win is that it can use the whole heap for allocation o Works well in systems with large amounts of live data many long lived objects Cons Fragmentation is a real problem e Allocation can be expensive in a heavily fragmented heap o Potential spatial locality issues bad cache behavior 24 Conclusions Copying Pros o Simple to understand and implement Q Allocation is very fast contiguous free memory Q Good locality favorable effect on cache behavior Cons Q It can use only half the heap space for allocation a real concern in systems with limited memory Q Poor performance in systems with large amounts of live data 25 More advanced topics Q Distinguishing pointers from integers e Representing arrays tuples records sums 0 Root set protocol Q Minimizing collection time c Avoiding unnecessary scanning of longlived data Compaction Q Conservative generational incremental collection 26 C8322 W OS Lecture Notes Lecture 91 PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 2 Procedures as Parameters Hcm mhm ywp smpu uNSpmmna swomm gmn order procedures This feature is supported by many languages including Pascal Ada ML and CC but not directly by Java Exanq es o Parameterized algorithms e g in C typedef int leqfn intint void isortint n int a leqfn leq 1nt ijt for i n l 1 gt 0 1 t ai for j i j lt n l ampamp leqaj1t j aj ajl aj t int upint pint q return p lt q int downint p int q return p gt q int a 213 isort3 a up a 123 isort3 a down a 321 PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 3 Procedures as Parameters cont 0 Callbacks from surrounding system typedef void clickhandlerint void handlerint button switchbutton case 1 cut case 2 copy case 3 paste registerClickHandlerhandler Standard implementation Just pass a pointer to the rst instruc tion of the procedure PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 4 Procedures as Parameters cont 0 Parameterized data structure traversals eg in ML fun map g int gt int u int list int list let fun f v int list int list case v of nil gt nil I hzzt gt g hf t in f u end fun add3 X X 3 fun subl X X l val w map add3 l23 yields 456 val z map subl l23 yields 012 ML also supports anonymous function values 16 functions that chbede nedxw houtbeuugnmnedCoukidoaboveexanu eas val w map fn X gt X 3 123 val z map fn X gt X 1 123 PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 5 Using Local Nested Procedures 0 Sometimes want to pass local functions as parameters fun meandeltas u int list int list let val mean int computemean u fun computedelta xint x mean in map computedeltau end 0 Lexical scope rules apply so function body can use data associ ated with outer function 0 Here computeldelta uses the value of mean which is local to meandeltas 0 Cannot express this in CCJava which have no nested func tions 0 Possible implementation pass pair of codepointer access link as value of procedure 0 Depends on fact that access link is still valid when procedure is called PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 6 More Nested Procedures Another example fun deltasnint uint list let fun computedelta xint x n in map computedeltau end deltas3l75 yields 242 0 Here computedelta depends on the value of variable n which is a local parameter of deltas What if we want to compute deltas on a several different lists with a xed n 0 Can be handy to treat procedure values just like other values eg to return them as function results or store them into vari ables PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 7 Firstclass Procedures Example fun deltas nzint int list gt int list let fun deltas u int list int list let fun computedelta xzint int x n in map computedeltau end in deltas end val g int list gt int list deltas 3 val x int list g 175 yields 242 val y int list g 246 yields ll3 val z int list deltas 3 246 yields 113 ML also provides syntactic sugar to make such Curried func mmewm cwnwhAMWemcgmnmemmmbmuI fun deltas nzint uint list int list let fun computedelta xint x n in map computedeltau end PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 8 Using Curried functions 0 When de ning multiargument functions in ML have a choice using a tuple argument and Currying 0 Can apply Curried version deltas to either one or two argu ments 0 Function application associates to the left so deltas 3 246 deltas 3 246 0 Function type arrows associate to the right so the type of deltas is int gt int list gt int list int gt int list gt int list 0 Currying most often useful when passing partially applied func tions to other higherorder functions eg map deltas 3 l75246 yields N242l ll3ll Here we assume map works on lists of any type in this case lists of lists of integers PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 9 Problems with rstclass procedures Consider activation tree for deltas example main deltas 3 g246 deltas246 mapcomputedelta246 emnmsvmuend computedelta2 Activation of deltas is no longer live when compute elta is called If n is stored in activation record for deltas and activation record is stackallocated it will be gone at the point where compute elta needs it To avoid this problem 0 Pascal prohibits upward funargs procedure values can only be passed downward and can t be stored 0 Some other languages only permit toplevel procedures to be manipulated as procedure values in C this means all proce dures PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 10 Heap Storage for Procedure Values 0 Languages supporting rstclass nested procedures eg Lisp Scheme ML Haskell etc solve problem by using heap to store variables like 1 0 Simple solution Just put all activation records in the heap to begin with Garbage collection is a must 0 More re ned solution Represent procedure values by a heapallocated closure record containing the procedure s code pointer and values of the nonlocal free variables referenced by the procedure 0 Involves taking copies of the values of nonlocal variables so only works when values are immutable 0 Can always introduce extra level of indirection to achieve this PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 11 Functional Programming What does functional mean Two main senses 0 Functions are supported as rstclass values 0 Programs consist of functions with no side effects also say programs are pure or applicative Claim functional programs are 0 clearer o easier to get right 0 easier to test 0 easier to transform 0 easier to parallelize o easier to prove things about Important examples 0 Lisp Scheme strict dynamically typed impure 0 Standard ML CAML strict statically typed impure o Haskell lazy statically typed pure PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 ML Example Dictionaries with Sorted Lists PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 13 datatype dict Node of int string dict dict Leaf fun insert dzdiot kintvstring dict case d of Node k v leftright gt if k lt k then Node k v insert left kvright else if k gt k then Node k v left insert right kv else k k Node kv leftright Leaf gt Node kvLeafLeaf fun member dzdiot kzint bool case d of Node k v leftright gt k lt k andalso member left k orelse k gt k andalso member right k orelse k k Leaf gt false val a insert Leaf lquotaquot val a Node lquotaquotLeafLeaf dict val b insert a 7quotbquot val b Node lquotaquotLeaf Node 7quotbquotLeafLeaf dict val o insert b 4quotoquot val o Node lquotaquotLeaf Node 7quotbquotNode 4quotoquotLeafLeaf Leaf dict val q member b 4 val q false bool PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 14 Features 0 Identi ers denote values not changeable variables 0 Datatype de nition introduces new tree type constructed us ing Leaf and Node and tested and destructured using pattern matching 0 insert is a function that returns a new tree Without changing its argument 0 Control structure is recursion not iteration PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 15 Why bother Functions can t have sideeffects Therefore they can t have dan gerous hidden sideeffects Consider this C fragment insertlquotqquott x ft source not here s member1t Will s be true It depends whether f modi es t Compare this functional code val t insert 1quotqquot t val X f t val s member 1 t Here s must be true because f can t modify it s argument or anything else Also compare val t insert 1quotqquot t val Xt f t val s member 1 t PS U C5322 W 05 Lecture 91 Andrew Tolmach 19922005 16 It s testable 0 True functions can always be tested separately fun appendx k t let val v find k t val t delete k t in insert kv A quotxquot t end If appendx is wrong then its de nition is wrong or find or delete or insert must be wrong The problem can t be due to a hidden interaction between f ind delete andor insert Any coupling between functions must be made explicit in their arguments or return values This helps discourage coupling In principle debugging by divide and conquer can even be auto mated In practice conventional troubleshooting is much easier C8322 W OS Lecture Notes Lecture 10 PSU C5322 W 05 Lecture 10 Andrew Tolmach 19922005 2 Machine Code Generation 0 Instruction Selection 0 Register Allocation and Assignment 0 Optimization Issues 0 Complexity of Target Machine 0 Level of Translation expression statement basic block rou tine program 0 Management of Scarce Resources PSU C5322 W 05 Lecture 10 Andrew Tolmach 19922005 3 Approaches to Instruction Selection For RISC targets translate one IR instruction to one or more tar get instructions For CISC targets translate several IR instructions to one target instruction Example Source a b assuming ab in frame 3 addr IR t1 fp 12 t2 t1 t3 fp8 t3 t2 Typical Tree IR mov mem mem fp 8 fp 12 extreme RISC add fp 12r3 1d r3 r7 add fp8r4 st r7r4 moderate RISC 1d fp 12 r7 st r7 fp 8 CISC move fp 12fp8 PSU C5322 W 05 Lecture 10 Andrew Tolmach 19922005 4 Simplistic SPARC Instruction Selection for PCAT IR Generate instructions from 3addresssty1e IR 0 Already includes explicit code for array and record calculations 0 Still needs to resolve variable addresses Alternatively could generate SPARC code directly from AST Approach 0 Take advantage of SPARC s Mregconst addressing mode to generate good code for frame references FOR THIS IR 1d a t20 DO THIS 1d fp l2 r7 NOT THIS add fp l2r3 1d r3 r7 PSU C5322 W 05 Lecture 10 Andrew Tolmach 19922005 0 But don t try to improve IR code that is already expanded THIS PCAT xa record dereference GAVE THIS IR 1d X th adda t103tll Id tlltl2 SETTLE FOR THIS 1d fp8 r3 add r3l2r3 Id r3r3 0 Use small constants directly where possible DO THIS add rl42rl NOT NOT mov 42r2 add rlr2rl 0 Fill delay slots with nop s unless producing a canned se quencethatcantmetheni PSU C5322 W 05 Lecture 10 Andrew Tolmach 19922005 6 Register Allocation and Assignment Task Manage scarce resources registers in environment with imperfect information static program text about dynamic pro gram behavior General aim is to keep frequentlyused values in registers as much as possible to lower memory traf c Can have a large effect on program performance Variety of approaches are possible differing in sophistication and in scope of analysis used Allocator may be unable to keep every live variable in registers must then spill variables to memory Spilling adds new instruc tions which often affects the allocation analysis requiring a new iteration If spilling is necessary what should we spill Some heuristics 0 Don t spill variables used in inner loops 0 Spill variables not used again for longest time o Spill variables which haven t been updated since last read from memory PSU C5322 W 05 Lecture 10 Andrew Tolmach 19922005 7 Simplistic Register Management for PCAT 0 Assume variables normally live in memory 0 Use existing often redundant fetches and stores present in IR 0 So only need to allocate registers to IR temporaries t 0 Certain SPARC registers are reserved see SparcregUsable o Ignore possibility of spills o Liveness information for all temporaries is already calculated for you see Liveness 0 Use simple linear scan register allocator based on liveness in tervals PSU C5322 W 05 Lecture 10 Andrew Tolmach 19922005 8 Liveness To determine how long to keep a given variable or temporary in a register need to know the range of instructions for which the variable is live A variable or temporary is live immediately following an instruc tion if its current value will be needed in the future ie it will be used again and it won t be changed before that use Example mov 3 mov add t add t live after instruction t2 t2 t3 t2 t4 t4 nothing It s easy to calculate liveness for a consecutive series of instruc tions without branches just by working backwards PSU C5322 W 05 Lecture 10 Andrew Tolmach 19922005 Liveness continued But if a value can stay in a register over a jump things get harder Example mov add add mul t2 cmp tl bl L1 return 0 t1 t3 Ll lmU39lIPUJNH t 2 l I t3 live after instruction t1 t3 t2 t3 t2 t3 t1 t3 t1 t3 t1 t3 nothing To calculate liveness in this case requires iterative ow analysis and the result is only conservative approximation to true live ness more later The live range of a variable is the set of instructions which leave it live E g in 2nd example live range of t1 is 1 4 5 6 live range of t3 is 1 6 Basic idea If two variables have disjoint live ranges they can occupy the same physical register So in both examples 2 physical registers suf ce to allocate all temporaries Without spilling PSU C5322 W 05 Lecture 10 Andrew Tolmach 19922005 Linear Scan Allocation Using live ranges turns out to be computationally expensive more later A simple alternative is to approximate each live range by a live interval This is the consecutive interval of instructions between the rst and last use of each temporary Example 1 mov 0 t1 2 L1 add t1 1 ot2 3 add t3 t2 t3 4 mul t2 2 t1 5 cmp tl 1000 6 b1 L1 7 return t3 Live ranges tl l456 Live intervals tl 16 live after instruction t1 t3 t2 t3 t2 t3 t1 t3 t1 t3 t1 t3 nothing t223 t3l23456 t2 23 t3 16 Revised Basic idea if two temporaries have nonoverlapping live intervals they can occupy the same physical register PS U C5322 W 05 Lecture 10 Andrew Tolmach 19922005 11 Linear Scan Allocation Algorithm Details 1 Compute startpoint and endpoint of live interval z for each temporary For HW4 this has been done for you Store the intervals in a list in order of increasing start point 2 Initialize set active 0 and pool of free registers all usable registers 3 For each live interval 239 in order of increasing start point a For each interval j in active in order of increasing end point 0 If endpoint Z startpoint break to step 3b 0 Remove j from active 0 Add register to pool of free registers b Set registeri next register from pool of free registers and remove it from pool If pool is already empty need to spill 0 Add 239 to active sorted by increasing end point Selected SPARC Instruction Set This document describes a useful subset of SPARC version 8 or 9 instruc tions it is by no means complete The SPARC Architecture Manual and your assembler reference manual both available from the course web page are also important in particular you7ll need the list of assembler pseudooperatorsi ln struction syntax conforms to the notation used in the architecture manuali Only actual instructions are shown here see also the list of synthetic instructions in Appendix A of the architecture manua Many of the following instructions take a reg as rst operand and either a reg or a 13 bit signed immediate value simml as second operandi The value of the second operand 0102 is either the contents of the register or the sign extended value of the immediate valuei Many of these instructions have one form that doesn7t affect condition codes and the other with cc appended to it that does The SPARC s condition codes are N last result negative Z last result 0 V last result over owed in two s complement C last result carried The codes are tested by the various conditional branch instructionsi Register g0 r0 behaves speciallyi If it is a source operand the constant value 0 is read if it is a destination operand the data written is discarded Arithmetic Instructions addcc regm reg0rimmed regrd add subcc regrsl reg0rimmed regrd subtract umu1cc regm reg0rimmed regrd unsigned multiply smu1cc regm reg0rimmed regrd signed multiply udivcc regm reg0rimmed regrd unsigned divide sdivcc regrsl reg0rimmed regrd signed divide Logical Instructions andcc regm reg0rimmed regrd bitwise and andncc regm reg0rimmed regrd bitwise and with NOT0p2 orcc regm reg0rimmed regrd bitwise 0r orncc regm reg0rimmed regrd bitwise or with NOT0p2 xorcc regrsl reg0rimmed regrd bitwise xor xnorcc regm reg0rimmed regrd bitwise war with NOT0p2 Shifts sll regrsl reg0rimmed regrd shift left by up srl regrsl reg0rimmed regrd shift right by 0102 zero ll sra regm reg0rimmed regrd shift right by 0102 sign extend Only the ve loworder bits of the shift count up matteri Miscellaneous sethi const22 regrd sethi hi value regrd Zero loworder 10 bits of regrd and set highorder 22 bits to constQZ The hi pseudoop can be used to extract and rightshift the highorder 22 bits of a literal valuei nop No operationi Control save regrsl reg0rimmed regrd restore regrsl reg0rimmed reg d Adjust register Window as described in class notes Otherwise7 instructions act like add7 except that source operands are read from old Window7 and result is Written into target register in new Windowi call label Write opc to o o7 and perform a delayed jump to speci ed labeli Any address in Whole 32bit space is legal jmpl address regT Write opc to rd and perform a delayed jump to speci ed address7 Branch Instructions baa label branch always bn a label branch never bnea label branch on not equal bea label branch on equal bga label branch on greater b1ea label branch on less or equal bgea label branch on greater or equal b1a label branch on less bgua label branch on greater unsigned b1eua label branch on less or equal unsigned bcca label branch on carry clear greater or equal unsigned bcsa labe ranch on carry set less unsigned bposa label branch on positive bnega label branch on negative bvca label branch on over ow clear bvsa label branch on over ow set If condition is met according to current condition codes perform PCrelative delayed branch to label Which must be expressible as PC 4 signextdisp22i Appending a sets the annul bit for these instructions Which has this effect if a conditional branch is executed and the branch is not taken or if a ba or bn is executed the delay slot instruction is annulled not executed Load and Store Instructions 1dsb address regrd load signed byte 1dsh address regrd load signed halfword 2 bytes 1dub address regrd load unsigned byte 1duh address regrd load unsigned halfword 1d address regT load word 4 bytes 1dd address regrd load double word 8 bytes stb regrd address store byte sth regrd address store halfword st regrd address store word std regrd address store double word All addresses must be aligned iiei halfword addresses must be divisible by 2 word addresses by 4 and doubleword address by 8 Unsigned loads zero ll highorder bits signed loads signextendi Register numbers for double word instructions must be even and two registers are readWritteni Floating Point Operations This lists only the doubleprecision 8 byte operations there are also single and quad precision operations oub eprecision operators act on pairs of oating registers7 speci ed by the lower evennumbered registeri Loads and stores of doubles must be to 8byte aligned memory addressesi Note that there is no way to move a value directly between integer and oat registers it must transmitted through memoryi faddd fregm fregrsgjregrd add double fsubd fregm fregrsgjregrd subtract double fmuld fregT51fregT52fregTd multiply double fdivd fregT51fregT52fregTd divide double fmovd fregrs fregrd move fnegd fregrs fregrd negate fabsd fregrs fregrd absolute value fitod fregrs fregrd convert integer to double fdtoi fregrs fregrd convert double to integer std fregrd address store double 1dd address fregrd load double fcmpd fregm fregrsg compare double fbaa label branch always fbn a label branch never fbua label branch on unordered fbga label branch on greater fbuga label branch on unordered or greater fbla label branch on less fbu1a label branch on unordered or less fblga label branch on less or greater fbnea label branch on not equal fbea label branch on equal fbuea label branch on unordered or equal fbgea label branch on greater or equal fbugea label branch on unordered or greater or equal fblea label branch on less or equal fbu1ea label branch on unordered or less or equal fbo a label ranch on ordered Floating point comparisons are made explicitly using fcmpd7 which sets the oating point condition codes the results are then tested by the oating con ditional branchsi A comparison returns unordered if one or both operands is NaN not a number The annul bit operates the same way as for integer branchesi C8322 W OS Lecture Notes Lecture 8 PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 Runtime Environments 0 Data Representation covered in C8321 0 Storage Organization 0 Procedures amp Stacks Activation Records Access to nonlocal names Parameter Passing Procedures as rstclass values 0 Storage Allocation StaticStackHeap Garbage Collection PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 3 Storage Organization 0 Subdivide machine address space by function access alloca tion 0 Typical organization Unix STACK top of stack but stacks nearly always grow DOWN i in VM systems these pages don t actually exist I T controlled by sbrk system call HEAP Managed by allocatorcollector CODE Readonly in obj ect le PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 4 Storage Classes Static Data Permanent Lifetimes 0 Global variables and constants C Allows xed address to be compiled into code 0 No runtime management costs 0 Original FORTRAN no recursion used static activation records Stack Data Nested Lifetimes o Allocationdeallocation is cheap just adjust stack pointer 0 Most architectures support cheap spbased addressing 0 Good locality for VM systems caches o C Algol family including PCAT use stack for activation records Heap Data Arbitrary Lifetimes o Requires explicit allocation and dangerous explicit dealloca tion or garbage collection 0 Lisp ML many interpreted languages need heap for activation records which have nonnested lifetimes PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 5 Procedures and Activations o A procedure de nition associates a name with a procedure body and associated formal parameters 0 A procedure activation is created during execution when the procedure is called with actual parameters 0 Activations have lifetimes the time between execution of the rst and last statements in the procedure 0 Activations are either nested eg ab or nonoverlapping eg bc a a b C b T c I d d 0 Procedure f is recursive if two or more activations of f are nested Note that f need not call itself directly PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 6 Activation Trees Example 1 int a9 1032567 17893180 51 2 main 3 quicksort08 4 5 void exchangeint i int j 6 int X ai ai aj aj X 7 8 int partitionint y int 2 9 int i y j z 1 10 while i lt j 11 i while ai lt ay i 12 j while aj gt ay j 13 if i lt j exchangeij l4 15 exchangeyj 16 return j 17 18 void quicksortint m int n 19 if n gt m 20 int i partitionmn 21 quicksortmi 1 22 quicksorti1n 23 24 PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 7 Activation Trees Example Cont Aka call tree Execution corresponds to depth rst traversal of tree Identify activations by name of function e exchange p parti tion q quicksort and actual argument values I q08 I I po8 I q58 I gb3 e18 e27 e45 e04 x p58 q57 q98 P0I3 q0I2 q4l3 e58 q03 e r3 P012 q010 q212 p517q55q77 p03 e03 e01 e56 Control stack keeps track of live activations it contains activa tions along the path from root to current activation see example above PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 8 Activation Records aka Frames Contain data associated with a particular activation of a proce dure 0 Actual parameters maybe in registers 0 Return value maybe in register 0 Local variables including temporaries perhaps containing saved registers 0 Access or Static link pointer to statically enclosing activa tion record to access nonlocal variables if needed Also convenient to include control information about the calling procedure 0 Return address in caller 0 Control or Dynamic Link pointer to caller s activation record if needed Use xed layout as far as possible for activation records so contents can be referenced as frame pointer statically known offset Most architectures perform such references ef ciently PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 9 Activation Record Lifetimes The lifetime of an activation record corresponds to the longest lifetime of anything contained in it The lifetimes of all contents begin when the activation begins ie when the procedure is called The lifetime of control information ends when the activation s lifetime ends ie when the procedure returns For most conventional languages including C Pascal PCAT etc the lifetimes of local data are also contained within the activa tion s lifetime Thus since activation lifetimes behave in a stacklike manner we can allocate and deallocate activation records on a stack For some languages like Lisp ML etc data lifetimes don t obey these rules such data cannot be stackallocated More later We don t push and pop whole activation records instead we build and destroy them in pieces PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 10 Calling Sequence Sequence of steps that taken together build and destroy activa tion records Typically divide into 0 Call sequence performed by caller 0 Entry sequence performed by callee 0 Exit sequence performed by eitherboth Key problem caller and callee know very little about each other 0 Single callee may have many callers o Caller may not callee statically e g C function pointers o Caller shouldn t need to know details of callee s implementation may be compiled separately Thus caller and callee must blindly cooperate Via a set of con ventions PS U C5322 W 05 Lecture 8 Andrew Tolmach 19922005 11 Typical Activation Records eg X86 Warning NOT like SPARC local variables Last Frame callersaved registers Addressing argn argi Mfp2i local Mf 391 addresses grow 3 p 3 argl old fp Mfp static link old pc M fp1 return address Current dynamic link Frame FPgt local variables amp temporaries Common variations xed sue order of info calleesaved registers defn of quotframequot stack grows local Val lables use of dynamic sizing dynamic size SPgt Depends on callersaved registers hardware arg n convention 0 1 ext frame will go here arg 1 PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 12 Typical Calling Sequence eg X86 1 Caller pushes callersave registers 2 Caller pushes arguments in reverse order and static link if any 3 Caller executes call instruction which pushes pc details vary according to machine architecture 4 Callee pushes f p as dynamic link and sets fp sp 5 Callee adjusts sp to make room for xedsize locals 6 Callee pushes calleesave registers 7 Callee can adjust sp dynamically during procedure execution to allocate dynamicallysized data on the stack PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 13 Typical Return Sequence eg X86 1 Callee restores calleesave registers 2 Callee resets sp fp thereby popping locals and any dynamicallysized data 3 Callee pops dynamic link into fp 4 Callee does a return which pops return address into pc 5 Caller pops static link and args 6 Caller restores callersave registers Common variations 0 Hardware instructions do more or less 0 Arguments may be passed in registers Return value almost always is o If everything is xedsize there s no real need for a frame pointer or a dynamic link but still handy PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 Typical Sequence Example Quicksort Stack on entry to e03 ignoring registers temporaries and static links main q08 q03 O p03 e03 huh 0 U0 PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 15 Access to Nonlocal Variables o In Pascal Ada PCAT etc we can nest procedure declarations inside other procedure declarations Cannot do this in C 0 Parameters and local variables of outer procedures are visible within inner procedures 0 More precisely the variables associated with the most recent stilllive activation of the outer procedure are visible within inner procedures 0 References to these variables must be compiled to code that can locate the corresponding values at runtime c Any variables that are referenced nonlocally must be stored in activation records in memory they cannot be held just in registers 0 Can analyze program to tell which variables are so referenced or as we ll do for PCAT just assume the worst 0 In most languages if procedure f is declared inside g then f can only appear as descendent of g in the activation tree This allows us to stackallocate activation records and still guarantee that nonlocal variables will still exist when they are needed PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 Example Quicksort Revisited in PCAT PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 17 PROGRAM 1 IS TYPE IARRAY IS ARRAY OF INTEGER VAR a IARRAYlt9 OF Ogtb IARRAYlt99 OF Ogt PROCEDURE sort 2 nINTEGER a IARRAY IS PROCEDURE exchange 3 ij INTEGER IS BEGIN X ai ai aj aj X END PROCEDURE quicksort 3 mn INTEGER IS VAR i INTEGER O PROCEDURE partition4yzINTEGERINTEGER VAR ij INTEGER 0 BEGIN WHILE ai lt ay DO i i 1 END exchangeyj RETURN j END BEGIN IF n gt m THEN i partitionmn quicksortmi l quicksortiln END END BEGIN quicksort0n l END BEGIN sort9a sort99b END PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 18 Access Links for Nonlocal Variables 0 Each activation record can include an access link aka static link pointing to the statically enclosing activation record 0 If p is nested immediately inside q then the access link in p s activation record points to the activation record for the most recent live activation of q o Nonlocal v is found by following one or more access links to the activation record that contains v and then taking the appro priate offset Within that record 0 If v is declared locally at depth m and accessed in p at depth 71p then the number of access links to follow is just 71p nu o In general variable locations can be described as a pair number of access links to follow offset Within resulting activation record Local variable at offset 2 is represented as 0 These locations are fully known at compi 1e time 0 Access links are initialized during the calling sequence usually calculated by the caller and passed as a hidden rst argument PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 19 Example with Static Links Quicksort Stack on entry to e03 dl lt fp for main dl lt fp for s0rt9a dl ltfp for quicksort08 dl lt fp for quicksort03 dl lt fp for partiti0n03 sl ra dl lt fp for exchange03 Note A static link always points into an activation record at the same place as the frame pointer for that activation PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 20 Another Addressing Example PROCEDURE fOO IS VAR X INTEGER PROCEDURE f azINTEGER IS VAR y INTEGER PROCEDURE g b INTEGER IS VAR Z INTEGER BEGIN f Xyz gab END BEGIN gay fX END BEGIN fX END If the body of foo is at scope level n then 0 Symbol foo is at scope level n l 0 Symbols x f are at scope level n 0 Symbols a y g are at scope level n 1 0 Symbols b z are at scope level n 2 Make sure you can calculate the addressing code for each mention of each symbol PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 21 SPARC Runtime Environment 0 Somewhat different from generic architecture 0 Procedure frame contains procedure s own locals and argu ments passed to called routines 0 Frame is normally xedsize 0 Most register saving including old f psppc is taken care of by register windows 0 Arguments are normally passed in registers up to 6 we won t do this for PCAT however Register window shifts 00 save gt iO lt restore 005 c215 06 sp fp 6 07 saved pc caller 0397 0 None the less extra space must be reserved in frame for regis ters and arguments due to system and C conventions PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 SPARCC Language Frame Layout Memory fo Addresses i Caller s locals arg n gt 6 Caller Argument offsets are Frame 2 positive with arg l at 1 fp 174 and arg n at structure returnuaddr reserved WP 17 4 111 4 register window area reserved sp fp Local offsets are negative with rst integer local at callee S locals fp 4 and n th integer local at fp n4 must not overlap Callee Fr me Callee s argument build area gt2 6 words Frame size structure return addr reserved 161 4 gtllt reglster wmdow save maxm maxargs 4 area reserved s1ze of locals rounded S k 0 oSp up to multiple of 8 tac Growth PSU C5322 W 05 Lecture 8 Andrew Tolmach 19922005 23 SPARCC Calling Sequence 1 Caller puts arguments in 00 01 05 Arguments beyond 6th word are put in argument build area of frame 2 Caller executes call instruction which jumps to label and stores old pc in o7 3 Callee executes save instruction which shifts register window and allocates frame Small leaf procedures can avoid this 4 Callee optionally stores arguments into argument build area of caller s frame Return Sequence 1 Callee puts integer return value in i O 2 Callee executes restore instruction which resets register window and deallocates frame 3 Callee executes ret instruction which jumps to i78 just past delay slot in caller Floating Point arguments are spread over pairs of registers fp return values are in f 0 all fp registers are callersave Structures may be multiple words Arguments are spread over multiple registers return values are written to space allocated by the caller and pointed to by sp64 C8322 W OS Lecture Notes Lecture 7 PSU C5322 W 05 Lecture 7 Andrew Tolmach 19922005 2 Uses of Boolean Expressions Used to drive conditional execution of program sections Examples IF a lt 17 OR b 12 THEN else WHILE NOT Xl gt 39 DO end In some languages may be assigned to boolean variables or passed as parameters Example VAR b BOOLEAN a lt 17 OR b 12 IF b THEN ELSE myprocb procedure call PSU C5322 W 05 Lecture 7 Andrew Tolmach 19922005 3 Boolean Expressions Two representations may be useful 0 Value Representation Encode true and false numerically e g as l and O and treat boolean expressions like arithmetic expressions Pro Language may support boolean values Con Bad match to hardware 0 Flowof control Representation Position in generated code represents boolean value Pro Good when shortcircuit evaluation is allowed or re quired e g in C expression e 1 e2 e2 should be evaluated only if e1 is false Reminder Some languages mandate shortcircuit evaluation oth ers prohibit it still others leave it up to the compiler writer Pro Convenient for control statements 0 For PCAT we ll use owofcontrol approach and convert to values when necessary PSU C5322 W 05 Lecture 7 Andrew Tolmach 19922005 4 Sample Productions for Valuebased Conditional Evaluation B El lt E2 Bplace newtemp Bcode let true newlabel after newlabel in Elcode E2code gentrueifltElplaceE2place genBplaceO genaftergoto gentrue genBplacel genafter II enerates IF El lt E2 GOTO Ll T O GOTO L2 L1 T 1 L2


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

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!"

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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.