SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

Syllabus

Run Time Environments:

1. Storage Organization,

2. Run Time Storage Allocation,

3. Activation Records,

4. Procedure Calls,

Displays Code Generation:

1. Issues in the Design of a Code Generator,

2. Object Code Forms,

3. Code Generation Algorithm,

4. Register Allocation and Assignment

web-D Page 1
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

Run Time Environments:

Certainly! In compiler design, a runtime environment plays a crucial role in

bridging the gap between the static source code of a program and the dynamic
actions that occur during program execution. Let’s delve into the key aspects of
runtime environments:

1. Activation Tree:

o A program consists of procedures (functions or methods), each associated

with an identifier (procedure name) and a statement (the body of the
procedure).
o An activation refers to the execution of a procedure.
o The lifetime of an activation encompasses the sequence of steps executed
within the procedure.
o Activation trees illustrate how control flows into and out of procedure
activations.
o Properties of activation trees:
 Each node represents an activation of a procedure.
 The root node corresponds to the activation of the main function.

web-D Page 2
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

 If procedure ‘x’ calls procedure ‘y’, the node for ‘x’ is the parent of the
node for ‘y’

o Example: Consider the following Quicksort program:

o main() {
o int n;
o readarray();
o quicksort(1, n);
o }
o
o quicksort(int m, int n) {
o int i = partition(m, n);
o quicksort(m, i - 1);
o quicksort(i + 1, n);
o }

The activation tree for this program would include nodes for main,
readarray, quicksort, and partition.

2. Control Stack and Activation Records:

web-D Page 3
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

o The control stack (or runtime stack) keeps track of live procedure activations
(those whose execution is ongoing).
o When a procedure is called (activation begins), its name is pushed onto the
stack; when it returns (activation ends), it is popped.

o An activation record (or frame) manages information needed for a single

execution of a procedure:

 Local variables: Hold data specific to the procedure’s execution.

 Temporary values: Store intermediate results during expression

evaluation.

 Machine status: Records the machine’s state just before the function
call.

 Access link (optional): Refers to non-local data in other activation

records.

web-D Page 4
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

3. Runtime Support System:

o The runtime environment includes:

 Software libraries: Used by the program during execution.
 Environment variables: Provide services to processes running in the
system.
o The runtime support system is often packaged with the executable
program itself and facilitates communication between processes.

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

web-D Page 5
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

STORAGE ALLOCATION TECHNIQUES

I. Static Storage Allocation

The names are bound with the storage at compiler time only and hence every
time procedure is invoked its names are bound to the same storage location
only So values of local names can be retained across activations of a
procedure. Here compiler can decide where the activation records go with
respect to the target code and can also fill the addresses in the target code for
the data it operates on.

 For any program, if we create a memory at compile time, memory will be

created in the static area.
 For any program, if we create a memory at compile-time only, memory is
created only once.
 It doesn’t support dynamic data structure i.e memory is created at compile-
time and deallocated after program completion.
 The drawback with static storage allocation is recursion is not supported.
 Another drawback is the size of data should be known at compile time
Eg- FORTRAN was designed to permit static storage allocation.

web-D Page 6
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

II. Stack Storage Allocation

 Storage is organized as a stack and activation records are pushed and
popped as activation begins and end respectively. Locals are contained in
activation records so they are bound to fresh storage in each activation.
 Recursion is supported in stack allocation

III. Heap Storage Allocation

 Memory allocation and deallocation can be done at any time and at any
place depending on the requirement of the user.
 Heap allocation is used to dynamically allocate memory to the variables and
claim it back when the variables are no more required.

1.) Storage organization :-

Let’s delve into the fascinating world of storage organization in compiler design.

1. Logical Address Space and Mapping:

o When a target program executes, it operates within its own logical address
space. Each program value has a specific location in this space.
o The logical address space is shared among the compiler, operating system,
and target machine for management and organization.
o The operating system maps logical addresses to physical addresses, which are
usually spread throughout the memory.

web-D Page 7
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

2. Subdivision of Run-Time Memory:

o Run-time storage is divided into several components:

 Generated executable code: This is the compiled code that the
program executes.
 Static data objects: These are variables with fixed memory locations.
 Dynamic data objects (heap): Memory allocated during program
execution for dynamic data structures.
 Automatic data objects (stack): These include local variables and
function call information.

3. Stack Storage:
o Many compilers use a stack-based strategy for dynamic storage
allocation.
o Local variables within a procedure are allocated space on a stack.
o The stack supports the normal call/return policy for procedures.

web-D Page 8
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

4. Heap Storage:
o The heap is another strategy for dynamic storage allocation.
o It allows for more flexible memory allocation and deallocation.
o Objects created dynamically during program execution are stored in the
heap.

2.) Run-time storage organizations :-

The run-time environment is the structure of the target computers

registers and memory that serves to manage memory and maintain
information needed to guide a programs execution process.

Types of Runtime Environments –

1. Fully Static :
Fully static runtime environment may be useful for the languages in which
pointers or dynamic allocation is not possible in addition to no support for
recursive function calls.
 Every procedure will have only one activation record which is allocated
before execution.
 Variables are accessed directly via fixed address.
 Little bookkeeping overhead; i.e., at most return address may have to
be stored in activation record.

web-D Page 9
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

 The calling sequence involves the calculation of each argument address

and storing into its appropriate parameter location and saving the return
address and then a jump is made.

2. Stack Based :
In this, activation records are allocated (push of the activation record)
whenever a function call is made. The necessary memory is taken from the
stack portion of the program. When program execution return from the
function the memory used by the activation record is deallocated (pop of
the activation record). Thus, the stack grows and shrinks with the chain of
function calls.

3. Fully Dynamic :
Functional language such as Lisp, ML, etc. use this style of call stack
management. Silently, here activation record is deallocated only when all
references to them have disappeared, and this requires the activation
records to dynamically freed at arbitrary times during execution. Memory
manager (garbage collector) is needed.
The data structure that handles such management is heap an this is also
called as Heap Management.

Activation Record –
Information needed by a single execution of a procedure is managed using a
contiguous block of storage called “activation record”.

web-D Page 10
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

An activation record is allocated when a procedure is entered and it is

deallocated when that procedure is exited. It contain temporary data, local
data, machine status, optional access link, optional control link, actual
parameters and returned values.

 Program Counter (PC) – whose value is the address of the next instruction
to be executed.
 Stack Pointer (SP) – whose value is the top of the (top of the stack, ToS).
 Frame pointer (FP) – which points to the current activation.

3.) Activation records :-

An activation record is a contiguous block of storage that manages information required
by a single execution of a procedure.

o When you enter a procedure (function or method), an activation record is

allocated, and when you exit that procedure, it is deallocated.
o Essentially, it stores the status of the current activation function.
o Whenever a function call occurs, a new activation record is created and
pushed onto the top of the stack. It remains in the stack until the
execution of that function is complete.
o Once the procedure finishes and control returns to the calling function,
the activation record is popped out of the stack.

web-D Page 11
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

2. Components of an Activation Record:

o Return values: Holds the result of the function.

o Parameter list: Contains the function’s input parameters.
o Control links: Used for managing the call hierarchy.
o Access links: Refers to information stored in other activation records that
is non-local. It allows accessing data not present in the local scope of the
activation record.
o Saved machine status: Holds information about the state of the machine
just before the procedure is called (e.g., program counter and machine
registers).
o Local data: Stores data local to the execution of the procedure.
o Temporaries: Holds temporary values arising during expression
evaluation.

o Access Link Example:

Consider the following C code snippet:

o #include <stdio.h>
o int g = 12;
o void Geeks() {
o printf("%d", g);
o }
o void main() {
o Geeks();
o }
 In this example, when Geeks() is called from main(), it needs to
print the value of g.
 However, g is not defined within the local scope of Geeks().
 Here, the access link allows Geeks() to access the global variable
g and print its value (which is 12).

3. Nested Procedures and Access Links:

o Nested procedures include an activation record access link that enables

users to access the activation record of the most recent outer procedure.
o This chain of access links traces the static structure of the program.

web-D Page 12
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

4.) Procedure calls

A procedure call is an essential and frequently used programming construct for a

compiler.

It is used to generate efficient code for procedure calls and returns.

During a procedure call, a sequence of actions occurs on entry and exit from each
procedure.

1. Calling Sequence:
o The translation for a call involves several steps:
 Space Allocation for Activation Record: When a procedure call occurs,
space is allocated for the activation record.
 Argument Evaluation: The arguments of the called procedure are
evaluated.
 Environment Pointers: Environment pointers are established to enable
the called procedure to access data in enclosing blocks.
 State Saving: The state of the calling procedure is saved so that it can
resume execution after the call. The return address (where the called
routine must transfer after completion) is also saved.
 Jump to Called Procedure: Finally, a jump instruction is generated to
begin executing the code for the called procedure.
2. Example Grammar:
o Consider the following grammar for a simple procedure call statement:
o S → call id (Elist)
o Elist → Elist, E
o Elist → E
 Here, id represents the procedure identifier, and Elist represents
the list of arguments passed to the procedure.
3. Transition Scheme for Procedure Call:
o Let’s define a suitable transition scheme for procedure calls:
 Production Rule: S → call id (Elist)
 For each item p on the queue:
 Generate the parameter for p.
 Generate the call to the procedure identified by [Link].
 Initialize the queue to contain only [Link].

Remember, understanding procedure calls is crucial for efficient code generation

and proper handling of function calls and returns!

web-D Page 13
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

6.) Displays
Certainly! Let’s delve into the fascinating world of displays in compiler design. 🚀

1. What Are Displays?

o In the context of compiler design, a display is an array of pointers to
activation records.
o Each activation record corresponds to a procedure or function call.
o Displays are used to access non-local names (variables or functions
defined in enclosing blocks).
2. Purpose of Displays:
o Accessing Non-Local Names: Displays allow procedures to access variables
declared in outer scopes.
o Managing Activation Records: Each level of nesting has its own activation
record, and displays help organize them.
3. How Displays Work:
o Suppose we have nested procedures (functions within functions).
o For each level of nesting, there is an array (the display) containing pointers
to the activation records.
o When a procedure is called, its activation record is pushed onto the stack,
and the display is updated.
o The display allows efficient access to variables in outer scopes.
4. Example:
o Consider the following code snippet:
o int globalVar = 42;
o void outer() {
o int outerVar = 10;
o void inner() {

web-D Page 14
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

o int innerVar = 5;
o // Access globalVar, outerVar, and innerVar
here
o }
o inner();
o }
o In this example:
 inner() can access globalVar, outerVar, and its own local
innerVar.
 The display helps inner() access outerVar and globalVar.
5. Error Detection and Recovery:
o Error detection and recovery are crucial in compilers.
o Strategies include:
 Panic Mode Recovery: Remove characters until a synchronizing
token is found.
 Phrase Level Error Recovery: Fill empty entries in the parsing table
with error routines.
 Error Productions: Augment the grammar with productions for
common errors.
 Global Correction: Analyze the input globally to find errors
(expensive but effective).

Remember, displays play a vital role in managing activation records and accessing
non-local names during compilation!

web-D Page 15
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

Displays code generation

Code generation is a crucial phase in compiler design where the compiler

translates the optimized intermediate representation (usually in the form of
three-address code) into machine code or assembly language that can be executed
by the computer.

Let’s delve into the details:

1. Target Code Generation:

o Objective: Produce the final code that the computer can execute.
o Input: Optimized intermediate representation (e.g., three-address code).
o Output: Target code (machine-readable code or assembly code).
o Tasks Performed:

web-D Page 16
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

 Register Allocation: Assign program variables to registers to

minimize memory access.
 Optimization: Optimize the code for efficiency.
o Mapping: Each line in optimized code may map to one or more lines in
machine or assembly code (1:N mapping).
o Registers: Registers are used for efficient computations due to their
speed, but they are limited and costly.
o Advantages of Registers:
 Fast access.
 Allows computations directly on them.
 Deterministic (no cache misses).
 Reduces memory traffic and computation time.
o Disadvantages of Registers:
 Limited availability (up to a few hundred KB).
 Fixed sizes (vary across processors).
 Complex management during context switches and procedure calls.

2. Example of Register Allocation:

o Consider the following optimized code:
o L1: a = b + c * d
o L2: e = f - g / d
o Register allocation:
 Example 1:
 R1 ← a
 R2 ← b
 R3 ← c
 R4 ← d
 MOV R3, c

web-D Page 17
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

 MUL R3, R4
 ADD R2, R3
 MOV R1, R2
 MOV a, R1
 Example 2:
 R1 ← e
 R2 ← f
 R3 ← g
 R4 ← h
 MOV R3, g
 DIV R3, R4
 SUB R2, R3
 MOV R1, R2
 MOV e, R1

1.) Issues in the Design of a Code Generator

Certainly! Let’s explore some of the key issues encountered during the design of a
code generator in the context of compiler design:

1. Target Machine Independence:

o Challenge: The code generator must produce target code that is
independent of the specific machine architecture. It should work on
different platforms without modification.
o Solution: Use an intermediate representation (such as three-address
code) that abstracts away machine-specific details. Translate this
intermediate code to target code during the final phase.

web-D Page 18
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

2. Register Allocation:
o Challenge: Efficiently allocate registers for program variables.
Registers are limited, and their management impacts performance.
o Solution: Implement register allocation algorithms (e.g., graph
coloring) to minimize memory access and maximize computation
speed.
3. Instruction Selection:
o Challenge: Choose appropriate instructions (e.g., load, store,
arithmetic) for each operation in the intermediate code.
o Solution: Map high-level operations to machine instructions.
Consider factors like available instructions, addressing modes, and
operand types.
4. Code Optimization:
o Challenge: Optimize the generated code for speed, size, or both.
Balance between execution time and memory usage.
o Solution: Apply various optimization techniques (e.g., constant
folding, common subexpression elimination, loop optimization) to
improve code quality.
5. Handling Control Flow:
o Challenge: Translate control flow constructs (conditionals, loops,
function calls) from intermediate code to target code.
o Solution: Generate appropriate assembly instructions for jumps,
branches, and function calls. Maintain accurate control flow.
6. Data Representation:
o Challenge: Represent data (variables, constants) efficiently in the
target code.

web-D Page 19
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

o Solution: Choose appropriate data types, handle memory layout, and

manage data alignment.
7. Addressing Modes:
o Challenge: Determine how operands (variables, constants) are
accessed in memory.
o Solution: Support various addressing modes (e.g., immediate, direct,
indexed, indirect) based on the target architecture.
8. Peephole Optimization:
o Challenge: Optimize small code sequences (peepholes) by replacing
them with more efficient alternatives.
o Solution: Identify common patterns and apply local optimizations
(e.g., constant propagation, dead code elimination).

2.) Object code forms :-

In compiler design, object code forms refer to different representations of the
machine-readable code generated by the compiler.

web-D Page 20
 SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

These forms serve as intermediate stages between the source code and the final
executable program. Here are the key forms:

1. Absolute Code:

 Directly executable: Contains exact memory addresses for instructions and data.
 Cannot be relocated: Tied to a specific memory layout.
 Applications: Device drivers, firmware, embedded systems.

2. Relocatable Code:

 Partially executable: Requires adjustment before execution.

 Contains symbolic addresses: Final addresses determined during linking.
 Can be combined with other object files: Facilitates modular development.

3. Assembler Code:

 Human-readable: Uses mnemonics to represent machine instructions.

 Translated to machine code: by an assembler program.
 Allows manual optimization and control: Useful for performance-critical code.

4. Linked Object Code:

Result of linking multiple object files: Combines code and data into a single
executable unit.
 Resolves references: Ensures symbols and variables are correctly linked.
 May be in absolute or relocatable format: Depends on linking process and target
system.

web-D Page 21
 SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

5. Executable Code:

 Final form ready for execution: Can be directly run on the target machine.
 Contains all necessary instructions and data: Self-contained, no external
dependencies.

Key Considerations:
 Form choice: Depends on compiler design, target system, and application
requirements.
 Relocation: A program's ability to run in different memory locations is crucial for
dynamic memory management and shared libraries.
 Linking: Processes multiple object files to create a single executable.
Additional Forms:
 Partially linked code: intermediate state during linking.
 Shared object code: Used for shared libraries to conserve memory and disk space.
 Dynamically linked code: Loaded at runtime to increase flexibility and reduce file
sizes.

Understanding object code forms is essential for comprehending compiler design,

linking processes, and program execution on different systems.

3.) Code generation algorithm :-

web-D Page 22
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

Certainly! Let’s delve into the code generation algorithm within the context of
compiler design. This algorithm is a pivotal component of the compilation
process, responsible for translating the optimized intermediate representation
(such as three-address code) into machine code or assembly language that can be
executed by the computer.

Here are the key steps involved in the code generation process:

1. Register and Address Descriptors:

o The code generator sets up register descriptors and address descriptors.
o A register descriptor keeps track of what is currently stored in each
register.
o An address descriptor stores the location where the current value of a
variable (or name) can be found at runtime.
2. Algorithm Overview:
o The code-generation algorithm takes a sequence of three-address
statements as input.
o For each three-address statement of the form a := b op c, perform the
following actions:
1. Invoke a function (e.g., getreg) to find out the location L where
the result of computation b op c should be stored.
2. Consult the address descriptor for y to determine y'. If the value of
y is currently in both memory and a register, prefer the register y'.

3. If the value of y is not already in location L, generate the instruction

MOV y', L to place a copy of y in L.
4. Generate the instruction OP z', L, where z' represents the
current location of z. If z is in both memory and a register, prefer a
register over a memory location.

web-D Page 23
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

5. Update the address descriptor of x to indicate that x is in location

L.

6. If x is already in location L, update its descriptor and remove x

from all other descriptors.
7. If the current value of y or z has no next uses or is not live on exit
from the block (or is in a register), alter the register descriptor to
indicate that after execution of x := y op z, those registers will
no longer contain y or z.
3. Generating Code for Assignment Statements:
o Let’s consider the assignment statement: d := (a - b) + (a - c) +
(a - c).
o This can be translated into the following sequence of three-address code:
o t := a - b
o u := a - c
o v := t + u
o d := v + u

The corresponding code sequence is as follows:

Statement Code Generated

--------------------------------
t := a - b MOV a, R0
SUB b, R0
; R0 contains t

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

v := t + u ADD R1, R0

web-D Page 24
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

; R0 contains v, R1 contains u

d := v + u ADD R1, R0
MOV R0, d
; R0 contains d

4.) Register Allocation and Assignment

Certainly! Let’s delve into the concepts of register allocation and assignment
within the context of compiler design.

1. Register Allocation:
o Objective: Efficiently allocate registers for program variables during
code generation.
o Why Registers?: Registers are fast, low-latency storage locations
within the CPU. Utilizing them optimally reduces memory access
time.
o Challenges:
 Limited number of registers (typically 8 to 32).
 Register management impacts performance.
o Register Allocation Algorithms:
 Graph Coloring: Treat register allocation as a graph coloring
problem. Nodes represent variables, and edges indicate
interference (variables used together). Assign colors (registers)
to nodes without conflicts.

web-D Page 25
SEM :- 3-2 (R20) COMPILER DESIGN UNIT-5

 Linear Scan: Allocate registers based on variable lifetimes.

Scan through the code linearly and assign registers to variables
as needed.
 Spilling: If there aren’t enough registers, spill (store) some
variables to memory temporarily.
o Advantages of Registers:
 Fast access.
 Allows computations directly on them.
 Deterministic (no cache misses).
 Reduces memory traffic and computation time.
o Disadvantages of Registers:
 Limited availability (up to a few hundred KB).
 Fixed sizes (vary across processors).
 Complex management during context switches and procedure
calls.
2. Assignment:
o Objective: Assign values to variables during code generation.
o Example:
o t := a - b
o u := a - c
o v := t + u
o d := v + u
 Here, t, u, v, and d are temporary variables.
 The corresponding assembly code assigns values to these
variables.

Remember that efficient register allocation and proper assignment contribute to

producing optimized and executable code during the compilation process .

web-D Page 26