UNIT IV RUN-TIME ENVIRONMENT AND CODE GENERATION

untime Environments – source language issues – Storage organization –

Storage Allocation Strategies: Static, Stack and Heap allocation -
Parameter Passing-Symbol Tables - Dynamic Storage Allocation - Issues
in the Design of a code generator – Basic Blocks and Flow graphs - Design
of a simple Code Generator - Optimal Code Generation for
Expressions– Dynamic Programming Code Generation.

IMPORTANT QUESTIONS.
PART A

1) Define code generations with ex? NOV /DEC 2020

2) What are the issues in the design of code generator?
3) Give the variety of forms in target
4) Give the factors of instruction selections
5) What are the sub problems in register allocation strategies?
6) Give the standard storage allocation NOV / DEC 2021, APRIL MAY 2022
7) What are the actions to perform the code generation algorithms?
8) Write the addressing mode and associated costs in the target machine.
9) Define basic block and flow graph.
10) Write the step to partition a sequence of 3 address statements into basic blocks.

11) Give the important classes of local transformations on basic blocks

12) Describe algebraic transformations.
13) What is meant by register descriptors and address descriptors?
14) What are the actions to perform the code generation algorithms?
15) Write the code sequence for the d:=(a-b)+(a-c)+(a-c).
16) What are the fields of activation record? NOV / DEC 2021
17) What is the order of calling sequence ?
18)What is dynamic scoping?
19)What are the properties of optimizing compiler?
20) Write the addressing mode and associated costs in the target machine.
21) Define basic block and flow graph.
22) Write the step to partition a sequence of 3 address statements into basic
blocks.

23) Give the important classes of local transformations on basic blocks

24) Describe algebraic transformations
25) What is meant by register descriptors and address descriptors?
26) What are the actions to perform the code generation algorithms?
27)Suggest a suitable approach for computing hash function.
28) Define static allocations and stack allocations NOV / DEC 2020
29) Task of code generator NOV/DEC 2020
 PART B

1. Write in detail about the issues in the design of code generator. NOV /DEC 2022
2. Discuss in detail about the run time storage arrangement. NOV / DEC 2017
3. What are different storage allocation strategies. Explain. NOV/DEC 2022
4. Explain in detail about the translation of source language details into run time environment.
MAY/JUNE2009
5. memory manager subsystem that is responsible for allocating and deallocating space
within the heap. NOV/ DEC 2020
6. Illustrate the algorithm that generates code for a single basic
block with three address instructions. NOV /DEC 2021
7. Write an algorithm used in code generation NOV/DEC 2022

PART A

1. Define code generations with ex?

It is the final phase in compiler model and it takes as an input an
intermediate representation of the source program and output produces as equivalent target
programs. Then intermediate instructions are each translated
into a sequence of machine instructions that perform the same task.

2. What are the issues in the design of code generator?

 Input to the generator
Target programs Memory
management Instruction
selection Register
allocation
 Choice of evaluation
order Approaches to code
generation.

3. Give the variety of forms in target

programAbsolute machine language.
Relocatable machine language.
Assembly language.

4. Give the factors of instruction selections.

Uniformity and completeness of the instruction sets
Instruction speed and machine idioms
Size of the instruction sets.

5. What are the sub problems in register allocation strategies?

During register allocation, we select the set of variables that will reside in register at
a point in the program.
During a subsequent register assignment phase, we pick the specific register that a
variable reside in.
6. Give the standard storage allocation NOV / DEC 2021
strategies.
Static allocation
Stack allocation.
7. Define static allocations and stack allocations

Static allocation is defined as lays out for all data objects at compile time. Names are bound
to storage as a program is compiled, so there is no need for a Run time support package.

Stack allocation is defined as process in which manages the run time as a Stack. It is based
on the idea of a control stack; storage is organized as a stack, And activation records are
pushed and popped as activations begin and end.

8. What are the actions to perform the code generation algorithms?

Invoke a function get reg to determine the location L.
Consult the address descriptor for y to determine y‟, the current location of y.
If the current values of y and/or z have no next uses, are not live on exit from the block, and
are in register, alter the register descriptor.

9. Write the addressing mode and associated costs in the target machine.

MODE FOR ADDRESS ADDED COST

M
Absolute M M 1
Register R R 0
Indexed c(R) c+contents(R) 1
Indirect register *R contents(R) 0
Indirect indexed *c(R) contents(c+contents(R)) 1

10. Define basic block and flow graph.

A basic block is a sequence of consecutive statements in which flow of Control enters at the
beginning and leaves at the end without halt or possibility Of branching except at the end.
A flow graph is defined as the adding of flow of control information to the Set of basic
blocks making up a program by constructing a directed graph.

11. Write the step to partition a sequence of 3 address statements into basic blocks.

First determine the set of leaders, the first statement of basic blocks. The rules we can use are
the following.
The first statement is a leader.
Any statement that is the target of a conditional or unconditional goto is a leader.
Any statement that immediately follows a goto or conditional goto statement is a leader.
1. For each leader, its basic blocks consists of the leader and all
statements Up to but not including the next leader or the end of the
program.
12. Give the important classes of local transformations on basic blocks
Structure preservation transformations
Algebraic transformations.

13. Describe algebraic transformations.

It can be used to change the set of expressions computed by a basic blocks into A
algebraically equivalent sets. The useful ones are those that simplify the
Expressions place expensive operations by cheaper ones.
X = X+ 0 X = X * 1

14. What is meant by register descriptors and address descriptors?

A register descriptor keeps track of what is currently in each register. It is Consulted
whenever a new register is needed.
An address descriptor keeps track of the location where ever the current Value of the
name can be found at run time. The location might be a register, a Stack location, a memory
address,

15. What are the actions to perform the code generation algorithms?
Invoke a function get reg to determine the location L.
Consult the address descriptor for y to determine y‟, the current location of y.
If the current values of y and/or z have no next uses, are not live on exit from the block, and
are in register, alter the register descriptor.

16. Write the code sequence for the d:=(a-b)+(a-c)+(a-c).

Statement Code generation Register descriptor Address

descriptor
t:=a-b MOV a,R0 R0 contains t t in R0
SUB b,R0
u:=a-c MOV a,R1 R0 contains t t in R0
SUB c,R1 R1 contains u u in R1
v:=t+u ADD R1,R0 R0 contains u in R1
v R1 contains v in R0
u
d:=v+u ADD R0 contains d d in R0
R1,R0 d in R0
MOV R0,d and
memory
17. What are the fields of activation record? NOV / DEC 2021

18. What is the order of calling sequence ?

The caller evaluates the actual parameters

The caller stores a return address and the old value of top- sp into the callee's activation record.

The callee saves the register values and other status information.
The callee initializes its local data and begins execution.

19. What is dynamic scoping?

In dynamic scoping a use of non-local variable refers to the non-local data declared in most
recently called and still active procedure. Therefore each time new findings are set up for local
names called procedure. In dynamic scoping symbol tables can be required at run time.

20. What are the properties of optimizing compiler?

The source code should be such that it should produce minimum amount of target code.
There should not be any unreachable code.
Dead code should be completely removed from source language.
The optimizing compilers should apply following code improving transformations on source
language.
• common subexpression elimination
• dead code elimination
• code movement

21. Write the addressing mode and associated costs in the target machine.

MODE FORM ADDRESS ADDED COST

Absolute M M 1
Register R R 0
Indexed c(R) c+contents(R) 1
Indirect register *R contents(R) 0
 Indirect indexed *c(R) contents(c+contents(R)) 1

22. Define basic block and flow graph.

A basic block is a sequence of consecutive statements in which flow of Control enters at the
beginning and leaves at the end without halt or possibility Of branching except at the end.
A flow graph is defined as the adding of flow of control information to the Set of basic
blocks making up a program by constructing a directed graph.

23. Write the step to partition a sequence of 3 address statements into basic blocks.
First determine the set of leaders, the first statement of basic
blocks. The rules we can use are the following.
The first statement is a leader.
Any statement that is the target of a conditional or unconditional goto is a leader.
Any statement that immediately follows a goto or conditional goto statement is a leader.
For each leader, its basic blocks consists of the leader and all
statements Up to but not including the next leader or the end of the
program.

24. Give the important classes of local transformations on basic blocks

Structure preservation transformations
Algebraic transformations.

25. Describe algebraic transformations.

It can be used to change the set of expressions computed by a basic
blocks into A algebraically equivalent sets. The useful ones are those that
simplify the
Expressions place expensive operations by cheaper ones.
X=
X+ 0
X=X
*1

26. What is meant by register descriptors and address descriptors?

A register descriptor keeps track of what is currently in each register. It is
Consulted whenever a new register is needed.
An address descriptor keeps track of the location where ever the current Value of
the
name can be found at run time. The location might be a register, a Stack location, a
memory address,

27. What are the actions to perform the code generation algorithms?
Invoke a function get reg to determine the location L.
Consult the address descriptor for y to determine y‟, the current location of y.
If the current values of y and/or z have no next uses, are not live on exit from the
block, and are in register, alter the register descriptor.
Call by value Call by reference Copy-
restore Call by name
28. Suggest a suitable approach for computing hash function.

Using hash function we should obtain exact locations of name in symbol table. The
hash function should result in uniform distribution of names in symbol table.
e hash function should be such that there will be minimum number of collisions. Collision is
such a situation where hash function results in same location for storing the names.

29. Define static allocations and stack allocations NOV / DEC 2020

Static allocation is defined as lays out for all data objects at compile time.
Names are bound to storage as a program is compiled, so there is no need for a run time
support package.

Stack allocation is defined as process in which manages the run time as a Stack. It is based
on the idea of a control stack; storage is organized as a stack, and activation records are
pushed and popped as activations begin and end.

30. Task of code generator NOV/DEC 2020

 PART B

1. Write in detail about the issues in the design of code generator. NOV /DEC 2022

ISSUES IN THE DESIGN OF A CODE GENERATOR

The following issues arise during the code generation phase :

1. Input to code generator

2. Target program
3. Memory management
4. Instruction selection
5. Register allocation
6. Evaluation order

1. Input to code generator:

 The input to the code generation consists of the intermediate representation of the
source program produced by front end , together with information in the
symbol table to determine run-time addresses of the data objects denoted by
the names in the intermediate representation.

 Intermediate representation can be :

a. Linear representation such as postfix notation
b. Three address representation such as quadruples
c. Virtual machine representation such as stack machine code
d. Graphical representations such as syntax trees and dags.

 Prior to code generation, the front end must be scanned, parsed and translated into
intermediate representation along with necessary type checking. Therefore,
input to code generation is assumed to be error-free.

2. Target program:
 The output of the code generator is the target program. The output may be :
a. Absolute machine language
- It can be placed in a fixed memory location and can be executed immediately.
b. Relocatable machine language
- It allows subprograms to be compiled separately.

c. Assembly language
- Code generation is made easier.

3. Memory management:
 Names in the source program are mapped to addresses of data objects in
run-time memory by the front end and code generator.

 It makes use of symbol table, that is, a name in a three-address statement

refers to a symbol-table entry for the name.
  Labels in three-address statements have to be converted to addresses of
instructions.

For example,
j:gotoigenerates jump instruction as follows :
 ifi<j, a backward jump instruction with target address equal to
location of code for quadrupleiis generated.
 ifi>j, the jump is forward. We must store on a list for
quadrupleithe location of the first machine instruction
generated for [Link]
processed, the machine locations for all instructions that forward
jumps toi are filled.

4. Instruction selection:
 The instructions of target machine should be complete and uniform.

 Instruction speeds and machine idioms are important factors when

efficiency of target program is considered.

 The quality of the generated code is determined by its speed and size.

 The former statement can be translated into the latter statement as shown below:

5. Register allocation
 Instructions involving register operands are shorter and faster than those
involving operands in memory.

 The use of registers is subdivided into two subproblems :

 Register allocation– the set of variables that will reside in registers at
a point in the program is selected.
 Register assignment– the specific register that a variable will
reside in is picked.

 Certain machine requires even-oddregister pairsfor some operands

and results. For example , consider the division instruction of the
form :
D x, y

where, x – dividend even register in even/odd

 register pair y – divisor
even register holds the
remainder odd register
holds the quotient

6. Evaluation order
 The order in which the computations are performed can affect the efficiency
of the target code. Some computation orders require fewer registers to
hold intermediate results than others.

2. Discuss in detail about the run time storage arrangement. NOV / DEC 2017

RUN-TIME STORAGE MANAGEMENT

 Information needed during an execution of a procedure is kept in a block

of storage called an activation record, which includes storage for names local
to the procedure.
 The two standard storage allocation strategies are:
1. Static allocation
2. Stack allocation
 In static allocation, the position of an activation record in memory is fixed at
compile time.

 In stack allocation, a new activation record is pushed onto the stack for each
execution of a procedure. The record is popped when the activation ends.
 The following three-address statements are associated with the run-time
allocation and deallocation of activation records:
1. Call,
2. Return,
3. Halt, and
4. Action, a placeholder for other statements.
 We assume that the run-time memory is divided into areas for:
1. Code
2. Static data
3. Stack

Static allocation

Implementation of call statement:

The codes needed to implement static allocation are as follows:

MOV#here+ 20,callee.static_area/*It saves return address*/

GOTOcallee.code_area/*It transfers control to the target code for the called

procedure */ where,
callee.static_area– Address of the activation record
callee.code_area– Address of the first instruction for called procedure
#here+ 20 – Literal return address which is the address of the instruction following GOTO.

Implementation of return statement:

A return from procedurecalleeis implemented by :

GOTO*callee.static_area

This transfers control to the address saved at the beginning of the activation record.

Implementation of action statement:

The instruction ACTION is used to implement action statement.

Implementation of halt statement:

The statement HALT is the final instruction that returns control to the operating system.

Stack allocation

Static allocation can become stack allocation by using relative addresses for
storage in activation records. In stack allocation, the position of activation record is
stored in register so words in activation records can be accessed as offsets from the
value in this register.

The codes needed to implement stack allocation are as follows:

Initialization of stack:

MOV#stackstart, SP /*

initializes stack */ Code for the first

procedure

HALT /* terminate execution */

Implementation of Call statement:

ADD#[Link], SP /* increment stack

pointer */ MOV#here+ 16, *SP /*Save return

address */ GOTOcallee.code_area

where,
[Link]– size of the activation record
#here+ 16 – address of the instruction following theGOTO

Implementation of Return statement:

 GOTO*0 ( SP ) /*return to the caller */

SUB#[Link], SP /* decrement SP and restore to previous value */

3. What are different storage allocation strategies. Explain. NOV/DEC 2022

STATIC ALLOCATION
Statically allocated 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.
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 [Link] address of the storage is fixed at
compile time.
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’s static.
Return value offset = 0

float f(int k)
{
float c[10],b;
Parameter k offset = 4
b=
c[k
]*3
.14 Local c[10] offset = 8

;
ret
urn
Local b offset = 48
b;

}
  Stack-dynamic allocation
 Storage is organized as a 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.
 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 deallocate an existing activation record, we just decrease stack_top.

 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

4. Explain in detail about the translation of source language details into run time
environment. (Page No.473) MAY/JUNE2009

Activation Tree

A program consist of procedures, a procedure definition is a declaration that, in its simplest

form, associates an identifier (procedure name) with a statement (body of the procedure). Each
execution of the procedure is referred to as an activation of the procedure. Lifetime of an
activation is the sequence of steps present in the execution of the procedure. If ‘a’ and ‘b’ be
two procedures then their activations will be non-overlapping (when one is called after other)
or nested (nested procedures).

A procedure is recursive if a new activation begins before an earlier activation of the same
procedure has ended. An activation tree shows the way control enters and leaves activations.
Properties of activation trees are :-

 Each node represents an activation of a procedure.

 The root shows the activation of the main function.
 The node for procedure ‘x’ is the parent of node for procedure ‘y’ if and only if the control
flows from procedure x to procedure y.

main() {

Int n;
readarray();
quicksort(1,n);
}

quicksort(int m, int n) {

Int i= partition(m,n);
quicksort(m,i-1);
quicksort(i+1,n);
}

The activation tree for this program will be:

First main function as the root then main calls readarray and quicksort. Quicksort in turn calls
partition and quicksort again. The flow of control in a program corresponds to a pre-order
depth-first traversal of the activation tree which starts at the root.

CONTROL STACK AND ACTIVATION RECORDS

Control stack or runtime stack is used to keep track of the live procedure activations i.e the
procedures whose execution have not been completed. A procedure name is pushed on to the
stack when it is called (activation begins) and it is popped when it returns (activation ends).
Information needed by a single execution of a procedure is managed using an activation record
or frame. When a procedure is called, an activation record is pushed into the stack and as soon
as the control returns to the caller function the activation record is popped.

A general activation record consists of the following things:

 Local variables: hold the data that is local to the execution of the procedure.

 Temporary values: stores the values that arise in the evaluation of an expression.

 Machine status: holds the information about the status of the machine just before the
function call.

 Access link (optional): refers to non-local data held in other activation records.

 Control link (optional): points to activation record of caller.

 Return value: used by the called procedure to return a value to calling procedure

 Actual parameters
Control stack for the above quicksort example:

SUBDIVISION OF RUNTIME MEMORY

Runtime storage can be subdivided to hold :



 Target code- the program code, is static as its size can be determined at compile time
 Static data objects
 Dynamic data objects- heap
 Automatic data objects- stack
 5. memory manager subsystem that is responsible for allocating and deallocating space
within the heap. NOV/ DEC 2020

HEAP ALLOCATION

Some languages do not have tree-structured allocations. In these cases, activations

have to be allocated on the heap. This allows strange situations, like callee activations that
live longer than their callers’ activations. This is not common Heap is used for allocating
space for objects created at run timeFor example: nodes of dynamic data structures such as
linked lists and trees

Dynamic memory allocation and deallocation based on the requirements of the

program
malloc() and free() in C programs
new()and delete()in C++ programs
new()and garbage collection in Java programs

Allocation and deallocation may be completely manual (C/C++), semi-automatic(Java), or

fully automatic (Lisp)
PARAMETERS PASSING
A language has first-class functionsif functions can bedeclared within any scope
passed as arguments to other functions returned as results of [Link] a language with
first-class functions and static scope, a function value is generally represented by a
closure. a pair consisting of a pointer to function code a pointer to an activation
[Link] functions as arguments is very useful in structuring of systems using

upcalls
An example: main()
{ int x = 4;
int f (int y) { retur n x*y;
}
int g (int →int h){ int x = 7;

Call-by-Value

The actual parameters are evaluated and their r-values are passed to
the called procedure

A procedure called by value can affect its caller either through nonlocal
names or through pointers.
Parameters in C are always passed by value. Array is unusual, what is
passed by value is a pointer.
Pascal uses pass by value by default, but var parameters are passed by reference.

Call-by-Reference

Also known as call-by-address or call-by-location. The caller passes

to the called procedure the l-value of the parameter.

If the parameter is an expression, then the expression is evaluated in a

new location, and the address of the new location is passed.
Parameters in Fortran are passed by reference an old implementation bug in Fortran

Copy-Restore
A hybrid between call-by-value and call-by reference.
The actual parameters are evaluated and their r-values are passed as in call-
 by-value. In addition, l values are determined before the call.

When control returns, the current r-values of the formal parameters are
copied back into the l-values of the actual parameters.

Call-by-Name
The actual parameters literally substituted for the formals. This is like
a macro- expansion or in-line expansion Call-by-name is not used in
practice.

However, the conceptually related technique of in-line expansion is

commonly used. In-lining may be one of the most effective optimization
transformations if they are guided by execution profiles.

6. Illustrate the algorithm that generates code for a single basic

block with three address instructions. NOV /DEC 2021

Basic Block is a straight line code sequence that has no branches in and out branches except
to the entry and at the end respectively. Basic Block is a set of statements that always executes
one after other, in a sequence.

The first task is to partition a sequence of three-address codes into basic blocks. A new basic
block is begun with the first instruction and instructions are added until a jump or a label is
met. In the absence of a jump, control moves further consecutively from one instruction to
another. The idea is standardized in the algorithm below:

Algorithm: Partitioning three-address code into basic blocks.

Input: A sequence of three address instructions.

Process: Instructions from intermediate code which are leaders are determined. The following
are the rules used for finding a leader:

1. The first three-address instruction of the intermediate code is a leader.

2. Instructions that are targets of unconditional or conditional jump/goto statements are

leaders.
3. Instructions that immediately follow unconditional or conditional jump/goto statements are
considered leaders.

Each leader thus determined its basic block contains itself and all instructions up to excluding
the next leader.

Example 1:
The following sequence of three-address statements forms a basic block:

t1 := a*a
t2 := a*b
t3 := 2*t2
t4 := t1+t3
t5 := b*b
t6 := t4 +t5

A three address statement x:= y+z is said to define x and to use y and z. A name in a
basic block is said to be live at a given point if its value is used after that point in the program,
perhaps in another basic block.

7. Write an algorithm used in code generation NOV/DEC 2022

The algorithm takes as input a sequence of three-address statements

constituting a basic block. For each three-address statement of the form x : =
y op z, perform the following actions:

1. Invoke a function getreg to determine the location L where the result of

the computation y op z should be stored.

2. Consult the address descriptor for y to determine y’, the current location
of y. Prefer the register for y’ if the value of y is currently both in memory
and a register. If the value of y is not already in L, generate the instruction
MOV y’ , L to place a copy of y in L.

3. Generate the instruction OP z’ , L where z’ is a current location of z.

Prefer a register to a memory location if z is in both. Update the address
descriptor of x to indicate that x is in location L. If x is in L, update its
descriptor and remove x from all other descriptors.

4. If the current values of y or z have no next uses, are not live on exit from
the block, and are in registers, alter the register descriptor to indicate that,
after execution of x : = y op z , those registers will no longer contain y or z
Generating Code for Assignment Statements:

5. The assignment d : = (a-b) + (a-c) + (a-c) might be translated into the

 following three-address code sequence:

t:= a-b
u:= a-c
v:= t +u
d:= v+u

Code sequence for the example is as follows:

Statement Code Generated Register descriptor Address descriptor

Register empty

t:= a - b MOV a, R0 R0 contains t t in R0

SUB b, R0

u:= a - c MOV a, R1 R0 contains t t in R0

SUB c, R1 R1 contains u u in R1

v:= t + u ADD R1, R0 R0 contains v u in R1

R1 contains u v in R1

d:= v + u ADD R1, R0 R0 contains d d in R0

MOV R0, d d in R0 and memory