Run-Time Environments

The compiler demands for a block of memory to operating system. The

compiler utilizes this block of memory for executing the compiled [Link]
block of memory is called run time storage.

• The Code consist of Target code.

• Static data Consist of local and Gobal Data,.
• Stack: The stack is used to manage the active procedures (Activation
Record) managing ,active procedure means that when a procedure call
occurs the Activation record is created.
• Heap area is the area of run time storage in which other information is
stored.

Activation Record:
• Activation record is used to manage the information needed by a single
execution of a procedure.
• An activation record is pushed into the stack when a procedure is called
and it is popped when the control returns to the caller function.
• Actual parameters: It holds the Actual parameters of calling function
• Returned values: To store the result of function call
• Control links: It points to the Activation record of calling function
• Access Link: It refers the to the local data of called function.
• Saved machine status: Stores Address of next instruction to be executed.
• Local variables: These variables are local to a function
• Temporary variables:Needed during Expression Evaluation

Storage allocation strategies:

There are various storage allocation techniques are as follows
1. Static storage allocation
2. Stack storage allocation
3. Heap storage allocation
1) Static Storage Allocation
• It is the simplest allocation scheme in which allocation of data objects is
done at compile time because the size of every data item can be determined
by the compiler.
• Recursive Subprogram and Arrays of adjustable length are not permitted
in a language.
• In static allocation, the compiler can decide the amount of storage needed
by each data object.
• Thus, it becomes easy for a compiler to identify the address of these data
in the activation record.
Advantages
• It is easy to implement.
• It allows type checking during compilation.
• It eliminates the feasibility of running out of memory.
Disadvantages
• It is incompatible with recursive subprograms.
• It is not possible to use variables whose size has to be determined at run
time.
2) Stack storage allocation
• The stack allocation is a runtime storage management technique. The
activation records are pushed and popped as activations begin and end
respectively.
• On each execution of a procedure, An Activation Record is generated,
which contains information like Local data, actual parameter, return value,
return address of a procedure. The Activation Record for that procedure is
saved onto the stack.
• Storage for the locals in each call of the procedure is contained in the
activation record for that call. Thus, locals are bound to fresh storage in
each activation, because a new activation record is pushed onto the stack
when the call is made.
• It can be determined the size of the variables at a run time & hence local
variables can have different storage locations & different values during
various activations.
• It allows recursive subprograms.
• If procedure A calls B, and then B calls C, then stack allocation will be

Advantages
• It supports recursion.
• It creates a data structure for the data item dynamically.
Disadvantages
• Memory Addressing can be done using pointers & index Registers.
3) Heap Storage Allocation
• Heap allocation is the most flexible allocation scheme.
• Storage can be allocated & freed arbitrarily from an area known as Heap.
• Heap Allocation is helpful for executing data whose size varies as the
program is running.
• Heap is maintained as a list of free space called free space list.
 Advantages
A large block of storage can be partitioned into smaller blocks at run
time.
Disadvantages
It creates the problem of fragmentation.

Introduction to Garbage Collection:

• Garbage collection (GC) is a memory recovery feature built into
programming languages such as C# and Java.
• A GC-enabled programming language includes one or more garbage
collectors (GC engines) that automatically free up memory space that has
been allocated to objects no longer needed by the program.
• The reclaimed memory space can then be used for future object allocations
within that program.
• Garbage collection ensures that a program does not exceed its memory
quota or reach a point that it can no longer function.
• It also frees up developers from having to manually manage a program's
memory, which, in turn, reduces the potential for memory-related bugs.
• In older programming languages, such as C++, the developer must
manually delete objects and free up memory.
• For example, a developer might forget to free up memory after the
program no longer needs it, leading to a memory leak that quickly
consumes all the available RAM.
 • Programming languages that include garbage collection try to eliminate
these types of bugs by using carefully designed GC algorithms to control
memory deallocation.
• The garbage collector automatically detects when an object is no longer
needed and removes it, freeing up the memory space allocated to that object
without affecting objects that are still being used.

Introduction to Trace-Based Collection:

Instead of collecting garbage as it is created, trace-based collectors run
periodically to find unreachable objects and reclaim their space. Typically,
we run the trace-based collector whenever the free space is exhausted or
its amount drops below some threshold.

A Basic Mark-and-Sweep Collector

• Mark-and-sweep garbage-collection algorithms are straight forward, that
find all the unreachable objects, and put them on the list of free space.
visits and "marks" all the reachable objects in the first tracing step and then
"sweeps" the entire heap to free up unreachable object.

Issues in the Design of a Code Generator:

Code generator converts the intermediate code to target code.
The following issue arises during the code generation phase:
i) Input to code generator –
• The input to the code generator is the intermediate code generated by the
front end, along with information in the symbol table that determines the
run-time addresses of the data objects denoted by the names in the
intermediate representation.
• Intermediate codes may be represented mostly in quadruples, triples,
indirect triples, Postfix notation, syntax trees, DAGs, etc
• The code generation phase just proceeds on an assumption that the input is
free from all syntactic and state semantic errors, the necessary type
checking has taken place and the type-conversion operators have been
inserted wherever necessary.
ii)Target program:
 • The target program is the output of the code generator. The output may be
absolute machine language, relocatable machine language, or assembly
language.
• Absolute machine language as output has the advantages that it can be
placed in a fixed memory location and can be immediately executed.
• Relocatable machine language as an output allows subprograms and
subroutines to be compiled separately. Relocatable object modules can be
linked together and loaded by a linking loader. But there is added expense
of linking and loading.
• Assembly language as output makes the code generation easier. We can
generate symbolic instructions and use the macro-facilities of assemblers
in generating code.
III)Instruction selection –
• Selecting the best instructions will improve the efficiency of the program.
It includes the instructions that should be complete and uniform
• Instruction speeds and machine idioms also play a major role when
efficiency is considered.
• For example, the respective three-address statements would be translated
into the latter code sequence as shown below:

• Here the fourth statement is redundant as the value of the P is loaded again
in that statement that just has been stored in the previous statement. It leads
to an inefficient code sequence.
IV)Register allocation issues
• Use of registers make the computations faster in comparison to that of
memory, so efficient utilization of registers is important. The use of
registers is subdivided into two subproblems:
1. During Register allocation – we select only those sets of variables that
will reside in the registers at each point in the program.
2. During a subsequent Register assignment phase, the specific register is
picked to access the variable.

V)Evaluation order :
• The code generator decides the order in which the instruction will be
executed.
• The order of computations affects the efficiency of the target code.
• Among many computational orders, some will require only fewer registers
to hold the intermediate results. However, picking the best order in the
general case is a difficult.

The Target Language:

The target language models a three-address machine consisting with load
and store operations, computation operations, jump operations, and
conditional jumps.
The target language consist of following kinds of instructions are
available:
 i)Load operations: The most common form of this instruction is LD r, x
which loads the value in location x into register r. An instruction of the
form LD r1,r2 is a register-to-register copy in which the contents of register
r2 are copied into register r1
ii) Store operations: The instruction ST x, r stores the value in register r
into the location x. This instruction denotes the assignment x = r
iii)Computation operations: Computation operations of the form OP dst,
src1,src2 , where OP is a operator like ADD or SUB. The effect of this
machine instruction is to apply the operation represented by OP to the
values in locations src1and src2 , and place the result of this operation in
location dst. For example, SUB r1,r2 ,r3 computes r1 = r2 – r3.
iv)Unconditional jumps: The instruction BR L causes control to branch to
the machine instruction with label L. (BR stands for branch.)
v) Conditional jumps: Conditional jumps of the form Bcond r, L, where r
is a register, L is a label, and cond stands for any of the common tests on
values in the register r. For example, BLTZ r, L causes a jump to label L if
the value in register r is less than zero, and allows control to pass to the
next machine instruction if not.
Example:The three-address statement x = y - z can be implemented by the
machine instructions:
LD Rl, y // Rl = y
LD R2, z // R2 = z
SUB Rl, Rl, R2 // Rl = Rl - R2
ST x, Rl // x = Rl

BASIC BLOCKS:
• A basic block is a sequence of consecutive statements in which flow of
control enters at the beginning and leaves at the end without any halt or
possibility of branching except at the end.
 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
Basic Block Construction:
Algorithm: Partition into basic blocks
Input: A sequence of three-address statements
Output: A list of basic blocks with each three-address statement in exactly
one block
Method:
[Link] first determine the set of leaders, the first statements of basic blocks.
The rules we use are of the following:
a. The first statement is a leader.
b. Any statement that is the target of a conditional or unconditional goto is
a leader.
c. Any statement that immediately follows a goto or conditional goto
statement is a leader.
2. For each leader, its basic block consists of the leader and all statements
up to but not including the next leader or the end of the program.
 Consider the following source code for dot product of two vectors a and b
of length 20
 The three-address code for the above source program is given as :

Basic block 1: Statement (1) to (2)

Basic block 2: Statement (3) to (12)

Flow Graphs:
 Flow graph is a directed graph containing the flow-of-control
information for the set of basic blocks making up a program.
 The nodes of the flow graph are basic blocks. It has a distinguished
initial node.
E.g.: Flow graph for the vector dot product is given as follows

 B1 is the initial node. B2 immediately follows B1, so there is an edge

from B1 to B2. The target of jump from last statement of B1 is the
first statement B2, so there is an edge from B1 (last statement) to B2
(first statement).
 B1 is the predecessor of B2, and B2 is a successor of B1.
Loops
  A loop is a collection of nodes in a flow graph such that
1. All nodes in the collection are strongly connected.
2. The collection of nodes has a unique entry.
 A loop that contains no other loops is called an inner loop.

Optimization of Basic Blocks:

 Optimization is the process of transforming a program that
improves the code by consuming fewer resources and delivering
high speed.
 In optimization, high-level codes are replaced by their equivalent
efficient low-level codes.
 Optimization of basic blocks can be machine-dependent or machine-
independent.
There are two types of basic block optimizations:
1. Structure preserving transformations
2. Algebraic transformations
[Link]-Preserving Transformations:
The structure-preserving transformation on basic blocks includes:
i) Dead Code Elimination
ii) Common Subexpression Elimination
iii) Renaming of Temporary variables
iv) Interchange of two independent adjacent statements
i) Dead Code Elimination:
Dead code is defined as that part of the code that never executes during the
program execution. So, for optimization, such code or dead code is eliminated.

Example:
ii).Common Subexpression Elimination:
In this technique, the sub-expression which are common are used frequently are
calculated only once and reused when needed. DAG ( Directed Acyclic Graph )
is used to eliminate common subexpressions.
Example:
 iii)Renaming of Temporary Variables:
Statements containing instances of a temporary variable can be changed to
instances of a new temporary variable without changing the basic block
value.
Example: Statement t = a + b can be changed to x = a + b where t is a
temporary variable and x is a new temporary variable without changing the
value of the basic block.
iv)Interchange of Two Independent Adjacent Statements:
If a block has two adjacent statements which are independent can be
interchanged without affecting the basic block value.
Example: t1=a+b
t2=c+d
These two independent statements of a block can be interchanged without
affecting the value of the block.
2) Algebraic Transformation:
Countless algebraic transformations can be used to change the set of
expressions computed by a basic block into an algebraically equivalent
set. Some of the algebraic transformation on basic blocks includes:
i) Constant Folding
ii) Copy Propagation
iii) Strength Reduction

[Link] Folding:
 Solve the constant terms which are continuous so that compiler does not
need to solve this expressions

[Link] Propagation:
It is of two types, Variable Propagation, and Constant Propagation.
 iii. Strength Reduction:
Replace expensive statement/ instruction with cheaper ones.
Example:

Peephole Optimization:
 Peephole optimization is a type of code Optimization performed on
a small part of the code. It is performed on a very small set of
instructions in a segment of code.
 It basically works on the theory of replacement in which a part of
code is replaced by shorter and faster code without a change in
output. The peephole is machine-dependent optimization.
 characteristics of peephole optimizations:
1 Redundant-instruction elimination
2 Eliminating Unreachable Code
3 Flow-of-control optimizations
4 Algebraic simplifications and Reduction in Strength
 5 Use of machine idioms
1 Redundant-instruction elimination :
If we see the instruction sequence
LD a, R0
ST R0, a
in a target program, we can delete the store instruction because whenever it is
executed, the first instruction will ensure that the value of a has already been
loaded into register R0.
[Link] Unreachable Code:
Another opportunity for peephole optimization is the removal of unreachable
instructions. An unlabeled instruction immediately following an unconditional
jump may be removed.
Example: In the intermediate code representation
if debug == 1 goto LI
goto L2
L I: print debugging information
L2:
the code sequence above can be replaced by
if debug != 1 goto L2
print debugging information
L2:
3 Flow-of-Control Optimizations
Simple intermediate code-generation algorithms frequently produce jumps to
jumps, jumps to conditional jumps, or conditional jumps to jumps. These
unnecessary jumps can be eliminated in either the intermediate code or the target
code.
Example:
goto L1
LI: goto L2
by the replacing
goto L2
LI: goto L2
If there are no jumps to LI, then it may be possible to eliminate the statement LI:
goto L2.
4) Algebraic simplifications and Reduction in Strength
The algebraic identities can also be used by a peephole optimizer to eliminate
three-address statements
such as x = x + 0 or x = x * 1
Similarly, reduction-in-strength transformations can be applied in the peephole
to replace expensive operations by equivalent cheaper ones on the target machine.
For example, x2 is invariably cheaper to implement as x * x .
5) Use of Machine Idioms:
• The target machine may have hardware instructions to implement certain
specific operations efficiently.
• Detecting situations tha t permit the use of these instructions can reduce
execution time significantly.
• For example, some machines have auto-increment and auto-decrement
addressing modes.
• These modes can also be used in code for statements like x = x + 1.

Register Allocation and Assignment

 Instructions involving only register operands are faster than those involving
memory operands.
 Therefore, efficient utilization of registers is vitally important in generating
good code.
 There are various strategies for deciding at each point in a program what
values should reside in registers (register allocation) and in which register each
value should reside (register assignment).
 One approach to register allocation and assignment is to assign specific
values in the target program to certain registers.
  For example, we could decide to assign base addresses to one group of
registers, arithmetic computations to another, the top of the stack to a
fixed register, and so on.
[Link] Register Allocation
The frequently used variables and keep these registers consistent across block
boundaries (globally).
Since programs spend most of their time in inner loops, a natural approach to
global register assignment is to try to keep a frequently used value in a fixed
register throughout a loop.
2 .Usage Counts
we shall assume that the savings to be realized by keeping a variable x in a register
for the duration of a loop L is one unit of cost for each reference to x if x is already
in a register.
Thus, an approximate formula for the benefit to be realized from allocating a
register x within loop L is

Use(x,B)->[Link] times x used & not preceded by an assignment to x in

sameblock.
Live(x,B)-> 1,if x is live on exit & x is assigned a value in B.
->0, otherwise
• To evaluate for x = a, we observe that a is live on exit from B1 and is assigned
a value there, but is not live on exit from B2 , B3 , or B4 . Thus,use(a,B) = 2.
Hence the value of for x = a is 4.
• That is, four units of cost can be saved by selecting a for one of the global
registers. The values of for b, c, d, e, and f are 5, 3, 6, 4, and 4, respectively.