Compiler Design Unit 4

Run time environment

1. UNIT IV Run Time Environments Mrs.D.Jena Catherine Bel , Assistant Professor, CSE, Velammal Engineering College Mrs.D.Jena Catherine Bel, AP/CSE, VEC 1

2. Runtime Environments How storage is laid out at runtime. What information is stored for each method. What happens during method call and return Mrs.D.Jena Catherine Bel, AP/CSE, VEC 2

3. Runtime Environments Before code generation static source text of a program needs to be related to the actions - must occur at runtime - implement the program. Set the relationship between names and data object The allocation and de allocation of data objects is managed by the runtime support package . Influenced by the semantics of Procedure 3 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

4. Source Language Issues Each execution of a function is referred to as an activation of the procedure/function If the function is recursive several of its activations may be alive at the same time The representation of data object at run time is determined by its type Primary data types – equivalent data objects in target machine Aggregates – collection of primitives 4 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

5. Procedures Procedure definition: a declaration that associates an i dentifier with statement The identifier is called the Procedure Name . The statement is called the Procedure Body. A Procedure Call is an invocation of a procedure within an executable statement. Procedures that return values are normally called Functions, but we ’ ll just use the name “ procedure. ” A Complete program can also be treated as a procedure Mrs.D.Jena Catherine Bel, AP/CSE, VEC 5

6. Program and Procedures PROGRAM sort( input,output ); VAR a : array[0..10] of Integer; PROCEDURE readarray ; VAR i : Integer; BEGIN for i := 1 to 9 do read(a[ i ]); END; FUNCTION partition( y,z : Integer): Integer; VAR i,j,x,v : Integer; BEGIN … END; PROCEDURE quicksort ( m,n : Integer); VAR i : Integer; BEGIN if (n > m) then BEGIN i := partition( m,n ); quicksort (m, i-1); quicksort (i+1,n) END END; BEGIN /* of main */ a[0] := -9999; a[10] := 9999; readarray ; quicksort (1,9) END. Procedure definition procedure name associated with procedure body Procedure call Actual parameters Formal parameters Mrs.D.Jena Catherine Bel, AP/CSE, VEC 6

7. Parameters of procedures The Formal Parameters are special identifiers declared in the procedure definition. The formal parameters must correspond to the Actual Parameters in the function call. They substitute the formals in the body E.g. m and n are formal parameters of the quicksort procedure. Actual parameters can be a simple identifier, or more complex expressions. Mrs.D.Jena Catherine Bel, AP/CSE, VEC 7

8. Procedure Activation and Lifetime A procedure is activated when it is called The lifetime of an activation of a procedure is the sequence of steps between the first and last steps in the execution of the procedure body A procedure is recursive if a new activation can begin before an earlier activation of the same procedure has ended 8 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

9. Activation Tree To depict the way control enters and leaves activations. In an activation tree: Each node represents activation of a procedure The root represents activation of main program Node a is the parent of the node b if the control flows from activation a to b The node a is to the left of node b if the lifetime of a occurs before the lifetime of b 9 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

10. Procedure Activations: Example 10 program sort(input, output) var a : array [0..10] of integer; procedure readarray ; var i : integer; begin for i := 1 to 9 do read(a[i]) end; function partition(y, z : integer) : integer var i, j, x, v : integer; begin … end procedure quicksort(m, n : integer); var i : integer; begin if (n > m) then begin i := partition(m, n); quicksort(m, i - 1); quicksort(i + 1, n) end end ; begin a[0] := -9999; a[10] := 9999; readarray ; quicksort(1, 9) end. Activations: begin sort enter readarray leave readarray enter quicksort(1,9) enter partition(1,9) leave partition(1,9) enter quicksort(1,3) … leave quicksort(1,3) enter quicksort(5,9) … leave quicksort(5,9) leave quicksort(1,9) end sort. Mrs.D.Jena Catherine Bel, AP/CSE, VEC

11. Activation Trees: Example 11 s q(1,9) q(1,3) p(1,3) q(1,0) q(2,3) q(2,1) p(2,3) q(3,3) p(1,9) r q(5,9) p(5,9) q(5,5) q(7,9) q(7,7) p(7,9) q(9,9) Activation tree for the sort program Note: also referred to as the dynamic call graph Mrs.D.Jena Catherine Bel, AP/CSE, VEC

12. Control Stack The flow of control of a program corresponds to depth first traversal of the activation tree Control stack is used to keep track of the live procedure activations. The idea is to push the node when activation begins and pop when it ends 12 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

13. Factorial Example discussed public static int Factorial(int num) { if (num == 1) { fact=1; } else { fact=fact+num*Factorial(--num); } return fact; } 13 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

14. Control Stack 14 s q(1,9) q(1,3) p(1,3) q(1,0) q(2,3) p(1,9) r Activations: begin sort enter readarray leave readarray enter quicksort(1,9) enter partition(1,9) leave partition(1,9) enter quicksort(1,3) enter partition(1,3) leave partition(1,3) enter quicksort(1,0) leave quicksort(1,0) enter quicksort(2,3) … Control stack: Activation tree: s q(1,9) q(1,3) q(2,3) Mrs.D.Jena Catherine Bel, AP/CSE, VEC

15. Scope Rules Environment determines name-to-object bindings: which objects are in scope ? Independent declarations of same name in different parts Scope rules- which declaration the name applies when it occurs 15 program prg; var y : real; function x(a : real) : real; begin … end; procedure p; var x : integer; begin x := 1; … end; begin y := x(0.0); … end. Variable x locally declared in p A function x Mrs.D.Jena Catherine Bel, AP/CSE, VEC

16. Scope Rules Portion of the program to which a declaration of the name applies –scope of that declaration occurrence local if declared within the procedure Mrs.D.Jena Catherine Bel, AP/CSE, VEC 16

17. Binding of Names If a name is declared once in a program it can hold different values at runtime The term environment refers to a function that maps name to a storage location The term state is referred to a function that maps a storage location to the value held there 17 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

18. Mapping Names to Values 18 name storage value environment state var i; … i := 0; … i := i + 1; Mrs.D.Jena Catherine Bel, AP/CSE, VEC

19. Mapping Names to Values 19 name storage value environment state var i; i := 0; i := i + 1; Environment and states are different An assignment changes the state but not the environment At compile time At run time Mrs.D.Jena Catherine Bel, AP/CSE, VEC

20. Static and Dynamic Notions of Bindings 20 Static Notion Dynamic Notion Definition of a procedure Activations of the procedure Declaration of a name Bindings of the name Scope of a declaration Lifetime of a binding Mrs.D.Jena Catherine Bel, AP/CSE, VEC

21. Storage allocation 21 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

22. Subdivision of Run-Time Memory For a compiled program – the run time storage is subdivided to hold: The generated target code Sized fixed Compiler place it statically in low end of the memory Data objects Size known Place it statically determined area Control stack to keep track of procedure activations use extensions of the control stack to manage procedures Mrs.D.Jena Catherine Bel, AP/CSE, VEC 22

23. Organization of storage Fixed-size objects can be placed in predefined locations. The heap and the stack need room to grow, however. 23 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

24. Run-time stack and heap The STACK is used to store: Procedure activations. The status of the machine just before calling a procedure, so that the status can be restored when the called procedure returns. The HEAP stores data allocated under program control (e.g. by malloc () in C ). If the life of the activations cannot be represented by tee – go for heap 24 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

25. Activation records Any information needed for a single activation of a procedure is stored in the ACTIVATION RECORD (sometimes called the STACK FRAME). Today, we ’ ll assume the stack grows DOWNWARD, as on, e.g., the Intel architecture. The activation record gets pushed for each procedure call and popped for each procedure return. 25 (the access link is the “ dynamic link ” in Sebesta ’ s terminology) Mrs.D.Jena Catherine Bel, AP/CSE, VEC

26. Activation Record Fields of activation records Temporary values: temp variables used for evaluation of expressions Local Data: data that is local to the execution of the procedure Saved Machine Status: sates of the machine before the procedure called (PC, Regs ) to return when the control returns Access Link: to refer non-local data Control Link: points to the activation record of the caller Actual Parameters: used by calling procedure to supply parameters to called procedure Returned Value: used by called procedure to return the value to the calling procedure Mrs.D.Jena Catherine Bel, AP/CSE, VEC 26

27. Compile-time layout of locals Storage – blocks of contiguous bytes BYTE is the smallest addressable unit of storage . The amount of storage needed for name is determined from its type(char, int , etc) We lay out locals in the order they are declared . Keep count of the memory locations allocated for previous declarations Determine relative address with respect to the beginning of the activation record Storage layout is influenced by the constraints of the machine Some data objects require alignment with machine words. Any resulting wasted space is called PADDING. Type Size (typical ) Alignment (typical) char 8 8 short 16 16 int 32 32 float 32 32 double 64 32 27 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

28. Storage allocation strategies Static allocation Stack allocation Heap Allocation 28 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

29. Static allocation Names are bound to storage at compile time. Storage bindings of statically allocated names never change, so even if a name is local to a procedure, its name is always bound to the same storage . Local variable are retained across activations of procedures Helps to retain the same value of local when the control returns. The compiler uses the type of a name (retrieved from the symbol table) to determine storage size required. The required number of bytes (possibly aligned) is set aside for the name . Address consist of offset from an end of the activation record for the procedure From this the storage for each name in the record is fixed The address of the storage is fixed at compile time. 29 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

30. Static allocation Limitations: The size required must be known at compile time. Recursive procedures cannot be implemented as all locals are statically allocated. No data structure can be created dynamically as all data is stat ic. 30 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

31. Stack-dynamic allocation Storage is organized as a stack (control Stack). Activation records are pushed and popped. Locals and parameters are contained in the activation records for the call. This means locals are bound to fresh storage on every call because of its new activation record If we have a stack growing downwards, we just need a stack_top pointer. To allocate a new activation record, we just increase stack_top . To de-allocate an existing activation record, we just decrease stack_top . 31 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

32. 32 Position in Activation Tree Activation Records on the Stack Mrs.D.Jena Catherine Bel, AP/CSE, VEC

33. Address generation in stack allocation The position of the activation record on the stack cannot be determined statically. Therefore the compiler must generate addresses RELATIVE to the activation record. If we have a downward-growing stack and a stack_top pointer, we generate addresses of the form stack_top + offset 33 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

34. Calling sequences The CALLING SEQUENCE for a procedure allocates an activation record and fills its fields in with appropriate values. The RETURN SEQUENCE restores the machine state to allow execution of the calling procedure to continue. Calling sequence code is part of the calling procedure (caller), and the part of the called procedure( callee ). What goes where depends on the language and machine architecture. 34 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

35. 35 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

36. Sample calling sequence Caller evaluates the actual parameters and places them into the activation record of the callee. Caller stores a return address and old value for stack_top in the callee ’ s activation record. Caller increments stack_top to the beginning of the temporaries and locals for the callee. Caller branches to the code for the callee. Callee saves all needed register values and status. Callee initializes its locals and begins execution. 36 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

37. Sample return sequence Callee places the return value at the correct location in the activation record (next to caller ’ s activation record) Callee uses status information previously saved to restore stack_top and the other registers. Callee branches to the return address previously requested by the caller. [Optional] Caller copies the return value into its own activation record and uses it to evaluate an expression. 37 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

38. Variable-length data In some languages, array size can depend on a value passed to the procedure as a parameter . The storage of these arrays is not part of the activation record – but only the pointer to the beginning of array appears in the activation record. The relative address of these pointers are known in compile time Target code access array elements through pointers 38 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

39. Example of variable- length data 39 All variable-length data is pointed to from the local data area. Mrs.D.Jena Catherine Bel, AP/CSE, VEC

40. Dangling pointers Stack dynamic allocation means that pointers might end up DANGLING Reference to storage that has been de-allocated int main( void ) { int *dangle( void ) { int *p; int i = 23; p = dangle(); return &i; } } 40 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

41. Draw backs of Stack Values of local name must be retained The called procedure outlives the caller – Activation tree cannot shows the flow of control between the procedures De-allocation is not of the form – last-in first out Mrs.D.Jena Catherine Bel, AP/CSE, VEC 41

42. Heap allocation Allocate storage as a contiguous block as needed for activation records De-allocated in any order Draw backs Time and space overhead For efficiency Use linked list of free blocks Fill the request of size ‘s’ with block size ‘s’ 42 Mrs.D.Jena Catherine Bel, AP/CSE, VEC

43. Mrs.D.Jena Catherine Bel, AP/CSE, VEC 43

44. Parameter Passing Communication between procedure Through –non- local names Parameters Methods Call-by-value Call-by-reference Copy-restore Call-by-name Macro expansion Mrs.D.Jena Catherine Bel, AP/CSE, VEC 44

45. Call-by-value Actual parameter are evaluated and their values(r-values) are passed to the called procedure Implemented as Formal parameter is treated as local name Caller evaluates the actual parameter and store r-values Call-by-value affects its caller either through nonlocal names or through pointers explicitly Mrs.D.Jena Catherine Bel, AP/CSE, VEC 45

46. Call-by-Reference Call-by-address or call-by-location Caller passes a pointer to the storage address of each actual parameter to the called procedure If actual parameter –name with l-value-then pass l-value If an expression without l-value- now evaluate the expression in new location and the address is passed Mrs.D.Jena Catherine Bel, AP/CSE, VEC 46

47. Call-by-Name Copy rule Procedure is treated as Macro Actual parameters are substituted as formal- Macro expansion Local names of the called procedure are kept distinct from the calling procedure Need to preserve the integrity of actual parameters Mrs.D.Jena Catherine Bel, AP/CSE, VEC 47