RUNTIME ENVIRONMENT

Run time environments – storage optimization – static Vs dynamic allocation – stack

allocation of space - activation trees and records – calling sequences. Code
generation –issues in the design of a code generator – the target language – a simple
target machinemodel. Code optimization - the principal sources of optimization –
data flow analysis – abstraction – data flow analysis schema – data flow schemas on
basic blocks.

STORAGE ORGANISATION

The executing target program runs in its own logical address space in which each
program value has a location. The management and organization of this logical
address space is shared between the complier, operating system and target machine.
The operating system maps the logical address into physical addresses, which are
usually spread throughout memory.

 Run-time storage comes in blocks, where a byte is the smallest unit of

addressable memory. Four bytes form a machine word. Multibyte objects are
stored in consecutive bytes and given the address of first byte
 The storage layout for data objects is strongly influenced by the addressing
constraints of the target machine.
 A character array of length 10 needs only enough bytes to hold 10 characters,
a compiler may allocate 12 bytes to get alignment, leaving 2 bytes unused.
 This unused space due to alignment considerations is referred to as padding.
 The size of some program objects may be known at run time and may be
placed in an area called static.
 The dynamic areas used to maximize the utilization of space at run time are
stack and heap.

1
Storage Allocation

The different ways to allocate memory are:

1. Static storage allocation

2. Stack storage allocation
3. Heap storage allocation

Static storage allocation

o In static allocation, names are bound to storage locations.

o If memory is created at compile time then the memory will be created in
static area and only once.
o Static allocation supports the dynamic data structure that means memory
is created only at compile time and deallocated after program completion.
o The drawback with static storage allocation is that the size and position of
data objects should be known at compile time.
o Another drawback is restriction of the recursion procedure.

2
Stack Storage Allocation

o In static storage allocation, storage is organized as a stack.

o An activation record is pushed into the stack when activation begins and
it is popped when the activation end.
o Activation record contains the locals so that they are bound to fresh
storage in each activation record. The value of locals is deleted when the
activation ends.
o It works on the basis of last-in-first-out (LIFO) and this allocation supports
the recursion process.

Heap Storage Allocation

o Heap allocation is the most flexible allocation scheme.

o Allocation and deallocation of memory can be done at any time and at any
place depending upon the user's requirement.
o Heap allocation is used to allocate memory to the variables dynamically
and when the variables are no more used then claim it back.
o Heap storage allocation supports the recursion process.

Stack Allocation of Space

Almost all compilers for languages that use procedure, functions, or methods
manage their run-time memory as a stack. Whenever a procedure is called, the
local variable's space is pushed into a stack and popped off from the stack when
the procedure terminates.

Activation Trees
A program is a set of instruction with some operation associated with it. The
sequence in which the procedure executes is known as activation. We also
assume that a procedure executes in a sequential manner, and this sequence is
easily represented by a tree known as the activation tree.

The following example illustrates the nesting of procedure calls:

3
The above code shows that array ‘a’ reads nine integers and sorts them using
the recursive quicksort algorithm.The task of the main function is to invoke the
function readArray, sets the sentinels, and then call the function quicksort on
the entire data array.

The code below shows a set of calls that might result from the execution of a
program.

4
The figure below shows the possible activation tree for the given code.

Activation Records

A run-time stack known as a control stack manages the procedure calls and
returns. The control stack stores the activation record of each live activation.
The top of the stack will hold the latest activation record.
The content of the activation record is given below.

5
Temporaries: The values which arise from the evaluation of expression will be
held by temporaries.
Local data: The data belonging to the execution of the procedure is stored in
local data.
Saved machine status: The status of the machine that might
contain register, program counter before the call to the procedure is stored in
saved machine status.
Access link: The data's information outside the local scope is stored in the
access link.
Control link: The activation record of the caller is pointed by the control link.
Returned values: It represents the space for the return value of the called
function if any.
Actual parameter: It represents the actual parameters used by the calling
procedure.

Example

6
CALLING SEQUENCES

 Procedures called are implemented in what is called as calling sequence,

which consists of code that allocates an activation record on the stack and
enters information into its fields.
 A return sequence is similar to code to restore the state of machine so the
calling procedure can continue its execution after the call.
 The code in calling sequence is often divided between the calling procedure
(caller) and the procedure it calls (callee)
 When designing calling sequences and the layout of activation records, the
following principles are helpful:
 Values communicated between caller and callee are generally
placed at the beginning of the callee's activation record, so they are
as close as possible to the caller's activation record.

7
Variable length data on stack:
 The run-time memory management system must deal frequently with the
allocation of space for objects, the sizes of which are not known at the
compile time, but which are local to a procedure and thus may be allocated
on the stack.
 The reason to prefer placing objects on the stack is that we avoid the
expense of garbage collecting their space.
 The same scheme works for objects of any type if they are local to the
procedure called and have a size that depends on the parameters of the
call.

 Procedure p has three local arrays, whose sizes cannot be determined at

compile time. The storage for these arrays is not part of the activation
record for p.
 Access to the data is through two pointers, top and top-sp. Here the top
marks the actual top of stack; it points the position at which the next
activation record will begin.

8
 The second top-sp is used to find local, fixed-length fields of the top
activation record.
 The code to reposition top and top-sp can be generated at compile time, in
terms of sizes that will become known at run time.

Fixed length items are generally placed in the middle. Such items typically
include the control link, the access link, and the machine status fields.
Items whose size may not be known early enough are placed at the end of
the activation record The most common example is dynamically sized
array, where the value of one of the callee's parameters determines the
length of the array We must locate the top-of-stack pointer judiciously. A
common approach is to have it point to the end of fixed-length fields in the
activation record. Fixed-length data can then be accessed by fixed offsets,
known to the intermediate-code generator, relative to the top-of-stack
pointer.

The calling sequence and its division between caller and callee are as follows

 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 caller then increments the top sp to the
respective positions.

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

A suitable, corresponding return sequence is

 The callee places the return value next to the parameters.
 Using the information in the machine-status field, the callee restores top
sp and other registers, and then branches to the return address that the
caller placed in the status field.
 Although top sp has been decremented, the caller knows where the return
value is, relative to the current value of top sp, the caller therefore may
use that value

CODE GENERATION

The final phase in compiler model is the code generator. It takes as input an
intermediate representation of the source program and produces as output an
equivalent target program. The code generation techniques presented below can
be used whether or not an optimizing phase occurs before code generation.

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

10
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 : goto i generates jump instruction as follows :
 if i < j, a backward jump instruction with target address equal to
location of code for quadruple i is generated.
 if i > j, the jump is forward. We must store on a list for quadruple i
the location of the first machine instruction generated for quadruple
j. When i is processed, the machine locations for all instructions that
forward jumps to i are filled

11
 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-odd register pairs for 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.

THE TARGET LANGUAGE

TARGET MACHINE

 Familiarity with the target machine and its instruction set is a prerequisite for
designing a good code generator.
 The target computer is a byte-addressable machine with 4 bytes to a word.
 It has n general-purpose registers, R0, R1, . . . , Rn-1.

12
 It has two-address instructions of the form: op source, destination where, op
is an op-code, and source and destination are data fields.
 It has the following op-codes : MOV (move source to destination) ADD (add
source to destination) SUB (subtract source from destination)
 The source and destination of an instruction are specified by combining
registers and memory locations with address modes.

 For example : MOV R0, M stores contents of Register R0 into memory location
M ; MOV 4(R0), M stores the value contents(4+contents(R0)) into M.

Instruction costs :
 Instruction cost = 1+cost for source and destination address modes. This cost
corresponds to the length of the instruction.
 Address modes involving registers have cost zero.
 Address modes involving memory location or literal have cost one.
 Instruction length should be minimized if space is important. Doing so also
minimizes the time taken to fetch and perform the instruction.
]
For example : MOV R0, R1 copies the contents of register R0 into R1. It has cost
one, since it occupies only one word of memory.

13
 In order to generate good code for target machine, we must utilize its addressing
capabilities efficiently.

CODE OPTIMIZATION

 The code produced by the straight forward compiling algorithms can often
be made to run faster or take less space, or both. This improvement is
achieved by program transformations that are traditionally called
optimizations. Compilers that apply code-improving transformations are
called optimizing compilers.
 Optimizations are classified into two categories.
They are
 Machine independent optimizations:
 Machine dependant optimizations:
Machine independent optimizations:  Machine independent optimizations
are program transformations that improve the target code without taking into
consideration any properties of the target machine.
Machine dependant optimizations:  Machine dependant optimizations are
based on register allocation and utilization of special machine-instruction
sequences.

PRINCIPAL SOURCES OF OPTIMISATION

 A transformation of a program is called local if it can be performed by looking

only at the statements in a basic block; otherwise, it is called global.

14
 Many transformations can be performed at both the local and global levels.
Local transformations are usually performed first.
Function-Preserving Transformations
 There are a number of ways in which a compiler can improve a program without
changing the function it computes.
 The transformations
 Common sub expression elimination,
 Copy propagation,
 Dead-code elimination
 Constant folding
are common examples of such function-preserving transformations. The other
transformations come up primarily when global optimizations are performed.
 Frequently, a program will include several calculations of the same value, such
as an offset in an array. Some of the duplicate calculations cannot be avoided by
the programmer because they lie below the level of detail accessible within the
source language.
Common Sub expressions elimination:

An occurrence of an expression E is called a common sub-expression if E was

previously computed, and the values of variables in E have not changed since
the previous computation. We can avoid recomputing the expression if we can
use the previously computed value.
 For example

The above code can be optimized using the common sub-expression elimination

15
The common sub expression t4: =4*i is eliminated as its computation is already
in t1. And value of i is not been changed from definition to use.

Copy Propagation:
 Assignments of the form f : = g called copy statements, or copies for short. The
idea behind the copy-propagation transformation is to use g for f, whenever
possible after the copy statement f: = g. Copy propagation means use of one
variable instead of another. This may not appear to be an improvement, but as
we shall see it gives us an opportunity to eliminate x.
 For example:

x=Pi;
……
A=x*r*r;

The optimization using copy propagation can be done as follows:

A=Pi*r*r;
Here the variable x is eliminated
Dead-Code Eliminations:

 A variable is live at a point in a program if its value can be used subsequently;

otherwise, it is dead at that point. A related idea is dead or useless code,
statements that compute values that never get used. While the programmer is
unlikely to introduce any dead code intentionally, it may appear as the result of
previous transformations. An optimization can be done by eliminating dead code.

Example:

Here, ‘if’ statement is dead code because this condition will never get satisfied.

Constant folding:

 We can eliminate both the test and printing from the object code. More
generally, deducing at compile time that the value of an expression is a constant
and using the constant instead is known as constant folding.
 One advantage of copy propagation is that it often turns the copy statement
into dead code.
16
For example,

a=3.14157/2 can be replaced by a=1.570 there by eliminating a division

operation.

Loop Optimizations:
 We now give a brief introduction to a very important place for optimizations,
namely loops, especially the inner loops where programs tend to spend the bulk
of their time. The running time of a program may be improved if we decrease the
number of instructions in an inner loop, even if we increase the amount of code
outside that loop.
 Three techniques are important for loop optimization:
 code motion, which moves code outside a loop;
 Induction-variable elimination, which we apply to replace variables from
inner loop.
 Reduction in strength, which replaces and expensive operation by a
cheaper one, such as a multiplication by an addition.

Code Motion:
 An important modification that decreases the amount of code in a loop is code
motion. This transformation takes an expression that yields the same result
independent of the number of times a loop is executed ( a loop-invariant
computation) and places the expression before the loop. Note that the notion
“before the loop” assumes the existence of an entry for the loop. For example,
evaluation of limit-2 is a loop-invariant computation in the following while-
statement:

while (i <= limit-2) /* statement does not change limit*/

Code motion will result in the equivalent of

t= limit-2;
while (i<=t) /* statement does not change limit or t */

Induction Variables :
 Loops are usually processed inside out. For example consider the loop around
B3.
 Note that the values of j and t4 remain in lock-step; every time the value of j
decreases by 1, that of t4 decreases by 4 because 4*j is assigned to t4. Such
identifiers are called induction variables.
17
  When there are two or more induction variables in a loop, it may be possible
to get rid of all but one, by the process of induction-variable elimination. For the
inner loop around B3 in Fig. we cannot get rid of either j or t4 completely; t4 is
used in B3 and j in B4. However, we can illustrate reduction in strength and
illustrate a part of the process of induction-variable elimination. Eventually j will
be eliminated when the outer loop of B2 - B5 is considered.

Example: As the relationship t4:=4*j surely holds after such an assignment to

t4 in Fig. and t4 is not changed elsewhere in the inner loop around B3, it follows
that just after the statement j:=j-1 the relationship t4:= 4*j-4 must hold. We may
therefore replace the assignment t4:= 4*j by t4:= t4-4. The only problem is that
t4 does not have a value when we enter block B3 for the first time. Since we must
maintain the relationship t4=4*j on entry to the block B3, we place an
initializations of t4 at the end of the block where j itself is

The replacement of a multiplication by a subtraction will speed up the object

code if multiplication takes more time than addition or subtraction, as is the
18
case on many machines.
Reduction In Strength:

 Reduction in strength replaces expensive operations by equivalent cheaper

ones on the target machine. Certain machine instructions are considerably
cheaper than others and can often be used as special cases of more expensive
operators.
 For example, x² is invariably cheaper to implement as x*x than as a call to an
exponentiation routine. Fixed-point multiplication or division by a power of two
is cheaper to implement as a shift. Floating-point division by a constant can be
implemented as multiplication by a constant, which may be cheaper

DATAFLOW ANALYSIS

It is the analysis of flow of data in control flow graph, i.e., the analysis that determines
the information regarding the definition and use of data in program. With the help of
this analysis, optimization can be done. In general, its process in which values are
computed using data flow analysis. The data flow property represents information that
can be used for optimization.
Data flow analysis is a technique used in compiler design to analyze how data flows
through a program. It involves tracking the values of variables and expressions as they
are computed and used throughout the program, with the goal of identifying
opportunities for optimization and identifying potential errors.
The basic idea behind data flow analysis is to model the program as a graph, where
the nodes represent program statements and the edges represent data flow
dependencies between the statements. The data flow information is then propagated
through the graph, using a set of rules and equations to compute the values of
variables and expressions at each point in the program
Advantages
1. Improved code quality: By identifying opportunities for optimization and eliminating
potential errors, data flow analysis can help improve the quality and efficiency of the
compiled code.
2. Better error detection: By tracking the flow of data through the program, data flow
analysis can help identify potential errors and bugs that might otherwise go
unnoticed.
3. Increased understanding of program behavior: By modeling the program as a graph
and tracking the flow of data, data flow analysis can help programmers better
understand how the program works and how it can be improved.
Basic Terminologies –

19
 Definition Point: a point in a program containing some definition.
 Reference Point: a point in a program containing a reference to a data item.
 Evaluation Point: a point in a program containing evaluation of expression.

Data Flow Properties –

 Available Expression – A expression is said to be available at a program point x if

along paths its reaching to x. A Expression is available at its evaluation point.
An expression a+b is said to be available if none of the operands gets modified
before their use.
Example –

It is used to eliminate common sub expressions.

 Reaching Definition – A definition D is reaches a point x if there is path from D to

x in which D is not killed, i.e., not redefined.

20
 Example –

It is used in constant and variable propagation.

 Live variable – A variable is said to be live at some point p if from p to end the
variable is used before it is redefined else it becomes dead.
Example –

It is useful for register allocation.It is used in dead code elimination.

21
 Busy Expression – An expression is busy along a path if its evaluation exists
along that path and none of its operand definition exists before its evaluation along
the path.

It is used for performing code movement optimization.

22