SET- 5 Reg. No.

IFET COLLEGE OF ENGINEERING

(An Autonomous Institution)
INTERNAL ASSESSMENT EXAMINATION-II
DEPARTMENT OF CSE & IT-
SUB CODE: 19UCSPC601 MAX MARKS: 60
SUB NAME: COMPILER DESIGN DURATION: 120Min
DATE: 12.04.2024/FN YEAR/ SEMESTER: III/VI
ANSWER KEY
PART-A (10  2=20)
Answer All Questions
(Each answer should have minimum 7 lines)
1. What are the functions performed in synthesis phase? R CO
1
 Intermediate code generation.
 Code generation.
 Code optimization.

2. Differentiate NFA and DFA U CO

1
2

3. State the rule to eliminate left recursion in a grammar U CO

2

4. Consider the grammar E → E+E | E*E | id and parse the input id+id*id using Shift-Reduce A CO
parser 2
5. Give syntax directed definition for if-else statement. S CO
3

6. Convert the assignment statement d:= (a-b) + (a-c) + (a-c) into three address code. A CO
3

7. How is the amount of storage needed for name determined? U CO

4
  In static allocation, the compiler decides the amount of storage for each data object and binds 2
the name of data objects to the allocated storage at compile time.
 The amount of storage needed for a name in stack allocation depends on the number of local
variables used in the function and the size of each variable. The storage is allocated when the
function is called and deallocated when the function returns
 The amount of storage needed for a name in heap allocation is dynamic and depends on the
user's requirement. The memory is allocated and freed dynamically as needed at runtime from a
data area called the heap

8. Draw the DAG for a := b * -c + b * -c. S CO

4
T1:= uminus c
T2:=b*t1
T3:= uminus c
T4:=b*t1
a:=t2+t4
+

* *

b -c b -c

9. Define peephole optimization R CO

5
 Peephole optimization is a simple and effective technique for locally improving target
code.
 This technique is applied to improve the performance of the target program by
examining the short sequence of target instructions and replacing these instructions by
shorter or faster sequence.
 Peephole optimization can also be applied directly after intermediate code generation to
improve the intermediate representation.

10. Compare machine independent with machine dependent optimization U CO

5
Machine Independent Code Optimization Machine Dependent Code Optimization
 Machine independent code  Machine dependent code
optimization refers to optimizing optimization refers to optimizing
code for use on any type of code specifically for a particular
hardware. type of computer or hardware
platform.
 The purpose of machine independent  The purpose of machine dependent
code optimization is to make the code optimization is to take
 code as efficient as possible across advantage of specific features or
all hardware platforms. characteristics of a particular
hardware platform.
 Machine independent code  Machine dependent code
optimization is applicable to any optimization is limited to a specific
hardware platform. hardware platform.

PART-B (Total=40 Marks)

(2  16=32&1  8=8)
Answer All Questions
(Each answer should be written for minimum 5 pages with minimum 25 lines per page)
11. A i) Describe the Input buffering technique U (8) CO
1
Some efficiency issues concerned with the buffering of input.
 Speed of lexical analysis is a concern.
 Lexical analysis needs to look ahead several characters before a
match can be announced

To ensure that a right lexeme is found, one or more characters have to be

looked up beyond the next lexeme.
 A two-buffer input scheme that is useful when lookahead on the
input is necessary to identify tokens.
 Techniques for speeding up the lexical analyser, such as the use of
sentinels to mark the buffer end.

There are three general approaches for the implementation of a lexical

analyzer:
 By using a lexical-analyzer generator, such as lex compiler to
produce the lexical analyzer from a regular expression based
specification. In this, the generator provides routines for reading
and buffering the input.
 By writing the lexical analyzer in a conventional systems-
programming language, using I/O facilities of that language to
read the input.
 By writing the lexical analyzer in assembly language and
explicitly managing the reading of input.
 Because of the amount of time taken to process characters and the
 large number of characters that must be processed during the
compilation of a large source program, specialized buffering
techniques have been developed to reduce the amount of overhead
required to process a single input character. The following fig 1.10
shows the buffer pairs which are used to hold the input data.

11. A ii) Explain in detail about the specifications of tokens U (8) CO

1
Regular expressions are a notation to represent lexeme patterns for a
token. Regular expressions are used to represent the language for lexical
analyser. It assists in finding the type of token that accounts for a
particular lexeme
Strings and Languages
 An alphabet or a character class is a finite set of symbols. Typical
examples of symbols are letters, digits and punctuation. The set {0,
1} isthe binary alphabet. ASCII and EBCDIC are two examples of
an alphabets.
 A string over some alphabet is a finite sequence of symbol taken
from that alphabet. In language theory, the terms "sentence" and
"word" are often used as synonyms for "string”. The length of a
string s, usually written |s|, is the number of occurrences of
symbols in s. For example, banana is a string of length six. The
empty string, denoted ε, is the string of length zero.
 A language is a set of strings over some fixed alphabet. The
language may contain a finite or an infinite number of strings

The following string-related terms are commonly used:

 A prefix of string s is any string obtained by removing zero or
more symbols from the endof string s. For example, ban is a
prefix of banana.
  A suffix of string s is any string obtained by removing zero or
more symbols from the beginning of s. For example, nana is a
suffix of banana.
 A substring of s is obtained by deleting any prefix and any suffix
from s. For example,nan is a substring of banana.
 The proper prefixes, suffixes, and substrings of a string s are those
prefixes, suffixes, and substrings, respectively of s that are not ε
or not equal to s itself.
 A subsequence of s is any string formed by deleting zero or more
not necessarily consecutive positions of s. For example, baan is a
subsequence of banana.

Operations on Languages
The following are the operations that can be applied to languages:
Union
Union of two languages Land M produces the set of strings which may be
either in language L or in language M or in both.
Example:
Let L and M be two languages where L = {dog, ba, na} and M = {house,
ba} then Union of L & U=LUM = {dog, ba, na, house}
Concatenation
Concatenation of two languages L and M, produces a set of strings which
are formed by merging the strings in L with strings in M (strings in L
must be followed by strings in M)
Example:
Concatenation of L & M = LM = {doghouse, dogba, bahouse, baba,
nahouse, naba}
Kleene closure
Kleene closure refers to zero or more occurrences of input symbols in a
string, i.e., it includes empty string Ɛ (set of strings with 0 or more
occurrences of input symbols). The kleene closure of language L, denoted
by L*.
For example, If L = {a, b}, then L* = { , a, b, aa, ab, ab, ba, bb, aaa, aba,
baa, . . . }
 Positive closure
Positive closure indicates one or more occurrences of input symbols in a
string, i.e., it excludes empty string Ɛ (set of strings with 1 or more
occurrences of input symbols). The positive closure of Language L
denoted by L+. For example, If L = {a, b}, then
L+ = {a, b, aa, ba, bb, aaa, aba, . . . }
Precedence of operators
 Unary operator (*) is having highest precedence.
 Concatenation operator (.) is second highest and is left
associative.
 Union operator (| or U) has least precedence and is left
associative.

Based on the precedence, the regular expression is transformed to finite

automata when implementing lexical analyzer
Regular Expressions
Regular expressions are a combination of input symbols and language
operators such as union, concatenation and closure. It can be used to
describe the identifier for a language. The identifier is a collection of
letters, digits and underscore which must begin with a letter. Hence, the
regular expression for an identifier can be given by,
Letter_ (letter | digit)*

(OR)
11. B 11. B. Construct the minimized DFA for the regular expression
(0+1)*(0+1)10.

12. A Construct a predictive parsing table for the following grammar and
also write the necessary algorithms. Show how the string(a, a) is (16)
parsed by the predictive parser S->a| ↑ | (T), T->T, S | S.
 (OR)
12. B Consider the following grammar
S->L=R
S->R
L->*R
L->id
R->L
Discuss about LALR parsing method for the above grammar. List out
the canonical collection Items and also construct the parse table
13. A(i) Given the Syntax-Directed Definition below construct the annotated
parse tree for the input expression: “int a, b, c”.
Grammar Semantic Rule
D -> T L [Link] = [Link]
T -> int [Link] = integer
T -> float [Link] = float
L -> L1, id [Link] = [Link] addType([Link],[Link])
L -> idaddType([Link],[Link])
Nonterminal D represents a declaration, which, from production 1,
consists of a type T followed by a list L of identifiers. T has one attribute, T.
type, which is the type in the declaration D. Nonterminal L also has one
attribute, which we call inh to emphasize that it is an inherited attribute. The
purpose of [Link] is to pass the declared type down the list of identifiers, so
that it can be added to the appropriate symbol-table entries. Productions 2
and 3 each evaluate the synthesized attribute [Link], giving it the appropriate
value, integer or float. This type is passed to the attribute 1. the appropriate
for production 1. Production 4 passes [Link] down the pane tree. That is, the
value Linh is computed at a parse-tree node by copying the value of L. inh
from the parent of that node; the parent corresponds to the heal of the
 production. Productions 4 and 5 also have a rule in which a function
addType is called with two arguments:
1. [Link], a lexical value that points to a symbol-table object, and
2. [Link], the type being assigned to every identifier on the list.

We suppose that function add Type properly installs the type [Link] as the
type of the represented identifier.

13 A(ii) Explain in detail about the declaration and assignment statements.

 (OR)
13. B Explain in detail about the three address code and its types and also
Write quadruple, triples and indirect triples for following expression
:(x + y) * (y + z) + (x + y + z)
In three-address code, there is at most one operator on the right side of an
instruction; that is, no built-up arithmetic expressions are permitted. Thus
a source-language expression like x+y*z might be translated into the
sequence of three-address instructions
T1:= y*z
T2:= x+t1
where t1 and t2 are compiler-generated temporary names. This unraveling
of multi-operator arithmetic expressions and of nested flow-of-control
statements makes three-address code desirable for target-code generation
and optimization. The use of names for the intermediate values computed
by a program allows three-address code to be rearranged easily.

Three address code is

T1:=x+y
T2:=y+z
T3:=T1+T2
T4:=T1+z
T5:=T3+T4
Quadruple representation
The quadruple is a structure with at the most four fields such as op, arg1,
arg2, result. The op field is used to represent the internal code for
operator, the arg1 and arg2 represent the two operands used and result
field is used to store the result of an expression.
Triples
In the triple representation the use of temporary variables is avoided by
referring the pointers in the symbol table.

Indirect triples
In the indirect triple representation the listing of triples is been [Link]
listing pointers are used instead of using statements
14 A Explain in detail about the different storage allocation
From the perspective of the compiler writer, 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 compiler, operating system, and target machine. The
operating system maps the logical addresses into physical addresses,
which are usually spread throughout [Link] storage comes into
blocks, where a byte is used to show the smallest unit of addressable
memory. Using the four bytes a machine word can form. Object of
multibyte is stored in consecutive bytes and gives the first byte address.
Run-time storage can be subdivide to hold the different components of an
executing program shown in Fig. 4.1:
 Generated executable code
 Static data objects
 Dynamic data-object- heap
 Automatic data objects- stack
STORAGE ALLOCATION STRATEGIES
The different storage allocation strategies are:
1. Static allocation - lays out storage for all data objects at compile time.
2. Stack allocation - manages the run-time storage as a stack.
[Link] allocation - allocates and deallocates storage as needed at run time
from a data area known as heap.
Static allocation
Static allocation is a procedure which is used for allocation of all the data
objects at compile time. Static allocation is possible only when the
compiler knows the size of data object at compile time. In this type of
allocation, formation of data objects is not possible under any
circumstances at run time. In static allocation, compiler decides the
amount of storage for each data object and binds the name of data objects
to the allocated storage. In static allocation, names are bound to storage
locations. If memory is created at compile time then the memory will be
created in static area and only once.
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.
The static allocation can be completed if the size of the data object is
called compile time.
Stack allocation
Almost all compilers for languages that use procedures, functions, or
methods as units of user- defined actions manage at least part of their run-
time memory as a stack. Each time a procedure is called, space for its
local variables is pushed onto a stack, and when the procedure terminates,
that space is popped off the stack. This arrangement not only allows space
to be shared by procedure calls whose durations do not overlap in time,
but it allows us to compile code for a procedure in such a way that the
relative addresses of its nonlocal variables are always the same, regardless
of the
sequence of procedure calls. In stack storage allocation, storage is
organized as a stack. An activation record is pushed into the stack when
activation begins and it is popped when the activation end. 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. It works on the basis of last-in-first-out
(LIFO) and this allocation
supports the recursion process.
Heap allocation
Heap allocation is the most flexible allocation scheme. Allocation and
deallocation of memory can be done at any time and at any place
depending upon the user's requirement. Heap allocation is used to allocate
memory to the variables dynamically and when the variables are no more
used then claim it back. Heap storage allocation supports the recursion
process.
 or
14 B Discuss the various issues in code generation with necessary examples
The most important criterion for a code generator is that it produce correct
code. The following issues arises during the code generation phase.
 Input to the Code Generator
 The Target Program
 Memory Management
 Instruction Selection
 Register Allocation
 Evaluation Order

1 Input to the Code Generator

The input to the code generator is the intermediate representation (IR) of
the source program produced by the front end, along with information in
the symbol table that is used to determine the run-time addresses of the
data objects denoted by the names in the IR. The choice for the
intermediate representation includes the following:
 Three-address representations such as quadruples, triples, indirect
triples;
 Virtual machine representations such as bytecodes and stack-
machine code;
 Linear representations such as postfix notation.
 Graphical representations such as syntax trees and DAG's.

The front end has scanned, parsed, and translated the source program into
a relatively lowlevel IR, so that the values of the names appearing in the
IR can be represented by quantities that the target machine candirectly
manipulate, such as integers and floating-point numbers. All syntactic and
static semantic errors have been detected, that the necessary type checking
has taken place, and that typeconversion operators have been inserted
wherever necessary. The code generator can proceed on the assumption
that its input is error free.
The Target Program
The output of the code generator is the target program which is going to
run in the following
computers.
 The instruction-set architecture of the target machine has a
significant impact on the difficulty of constructing a good code
generator that produces high-quality machine code. The most
common target-machine architectures are RISC (reduced
instruction set computer), CISC (complex instruction set
computer), and stack based.
 A RISC machine typically has many registers, three-address
instructions, simple addressing modes, and a relatively simple
instruction-set architecture.
 In contrast, a CISC machine typically has few registers, two-
address instructions, a variety of addressing modes, several
register classes, variable-length instructions, and instructions with
side effects.
 In a stack-based machine, operations are done by pushing
operands onto a stack and then performing the operations on the
operands at the top of the stack. To achieve high performance the
top of the stack is kept in registers.
 The JVM is a software interpreter for Java byte codes, an
intermediate language produced by Java compilers. The interpreter
provides software compatibility across multiple platforms, a major
factor in the success of Java. To improve the high performance
interpretation just-intime (JIT) Java compilers have been created.
 The output of the code generator may be:
 Absolute machine language program: It can be placed in a fixed
memory location and immediately executed.
 Reloadable machine-language program: It allows subprograms
(object modules) to be compiled separately. A set of relocatable
object modules can be linked together and loaded for execution by
a linking loader. the compiler must provide explicit relocation
information to the loader if automatic relocation is not possible.
 Assembly language program: The process of code generation is
somewhat easier, but assembly must be converted into machine
executable code with help of assembler.
Memory Management
Names in the source program are mapped to addresses of data objects in
run-time memory by both the front end and code generator.
 Memory Management uses symbol table to get names
information.
 The amount of memory required by declared identifies are
calculated and storage space is reserved in memory at run time.
 Labels in three address code are converted into equivalent
memory address.
 For instance if a reference to ―goto j‖ is encountered in three
address code then appropriate jump instruction can be generated
by computing memory address for label j.
 Some instruction address can be calculated in run time only that is
also after loading the program.
Instruction Selection
The code generator must map the IR program into a code
sequence that can be executed by the target
machine. The complexity of performing this mapping is
determined by factors such as
 The level of the intermediate representation (IR).
 The nature of the instruction-set architecture.
 The desired quality of the generated code.
If the IR is high level, the code generator may translate each IR
statement into a sequence of machine instructions using code
templates. Such statement-by-statement code generation,
however, often produces poor code that needs further
optimization. If the IR reflects some of the low-level details of the
underlying machine, then the code generator can use this
information to generate more efficient code
sequences.
The uniformity and completeness of the instruction set are
important factors. The selection of instruction depends on the
instruction set of the target machine. Instruction speeds and
machine idioms are other important factors in selection of
instruction. If we do not care about the efficiency of the target
program, instruction selection is straightforward. For each type of
three-address statement, we can design a code skeleton that
defines the target code to be generated for that construct.
For example, every three-address statement of the form x = y + z,
where x, y, and z are
statically allocated, can be translated into the code sequence.
LD R0, y // R0 = y (load y into register RO)
ADD R0, R0, z // R0 = R 0 + z (add z to R0)
ST x, R0 // x = R0 (store RO into x)
This strategy often produces redundant loads and stores. For
example, the sequence of threeaddress
statements
a=b+c
d=a+e
would be translated into the following code
LD R0, b // R0 = b
ADD R0, R0, c // R0 = R0 + c
ST a, R0 // a = R0 LD R0, a // R0 = a
ADD R0, R0, e // R0 = R0 + e
ST d, R0 // d = R0
Here, the fourth statement is redundant since it loads a value that
has just been stored, and so is the third if a
is not subsequently used.
The quality of the generated code is usually determined by its
speed and size. On most machines, agiven IR program can be
implemented by many different code sequences, with significant
cost differences between the different implementations. A naive
translation of the intermediate code may therefore lead to correct
but unacceptably inefficient target code.
Register Allocation
A key problem in code generation is deciding what values to hold
in what registers. Registers are the fastest computational unit on
the target machine, but we usually do not have enough of them to
 hold all values. Values not held in registers need to reside in
memory. Instructions involving register operands are invariably
shorter and faster than those involving operands in memory, so
efficient utilization of registers is particularly important.
The use of registers is often subdivided into two subproblems:
 Register allocation, during which we select the set of variables
that will reside in registers at eachpoint in the program.
 Register assignment, during which we pick the specific register
that a variable will reside in. Finding an optimal assignment of
registers to variables is difficult, even with single-register
machines. Mathematically, the problem is NP-complete. The
problem is further complicated because the hardware and/or the
operating system of the target machine may require that certain
register-usage conventions be observed. Certain machines require
register-pairs for some operands and results Consider the two
three-address code sequences, the only difference is the operator
in the second statement.
t=a+b
t=t*c
t=t/d
The efficient Optimal machine-code sequences with only one
register
R0 LD R0, a
ADD R0, b
MUL R0, c
DIV R0, d
ST R0, t
Evaluation Order
The evaluation order is an important factor in generating an
efficient target code. Some computation orders
require fewer registers to hold intermediate results than others.
However, picking a best order in the general case is a difficult
NP-complete problem. We can avoid the problem by generating
code for the three-address statements in the order in which they
 have been produced by the intermediate code
generator.

15 A(i) Describe about the Flow graphs with example.

A flow graph is simply a directed graph. For the set of basic blocks, a
flow graph shows the flow ofcontrol information. A control flow graph is
used to depict how the program control is being parsed among the blocks.
A flow graph is used to illustrate the flow of control between basic blocks
once an intermediate code has been partitioned into basic blocks. An edge
can flow from one block X to another block Y in such a case when the Y
block‟s first instruction immediately follows the X
block‟s last instruction. The following ways will describe the edge:
 There is a conditional or unconditional jump from the end of X to
the starting of Y.
 Y immediately follows X in the original order of the three-address
code, and X does not endin an unconditional jump

We say that X is a predecessor of Y, and Y is a successor of X. Then we

add two nodes called theentry and exit. The entry and exit nodes are not
correspond to executable intermediate [Link] is an edge from
the entry to the first executable node of the flow graph. There is an edge
tothe exit from any basic block that contains an instruction that could be
the last executed instruction of the program. If the final instruction of the
program is not an unconditional jump, then the blockcontaining the final
instruction of the program is one predecessor of the exit, but so is any
basicblock that has a jump to code that is not part of the program.
  Block B1 is the entry point for the flow graph because B1 contains
starting instruction.
 B2 is the only successor of B1 because B1 doesn't end with
unconditional jumps, and the B2 block's leader immediately
follows the B1 block's leader.
 B3 block has two successors. One is a block B3 itself because the
first instruction of the B3 block is the target for the conditional
jump in the last instruction of block B3. Anothersuccessor is block
B4 due to conditional jump at the end of B3 block.
 B6 block is the exit point of the flow graph.

Loops:
 Loops are important because programs spend most of their time executing
them, and optimizations that improve the performance of loops can have a
significant impact. Thus, it isessential that we identify loops and treat
them specially.
Loops also affect the running time of program analyses. If a program does
not contain anyloops, we can obtain the answers to data-flow problems by
making just one pass through the program. For example, a forward data-
flow problem can be solved by visiting all the nodes once, in topological
order.
Dominators :
In a flow graph, a node d dominates node n, if every path from initial node
of the flow graph to n goes through d. This will be denoted by d dom n.
Every initial node dominates all the remaining nodes in the flow graph
and the entry of a loop dominates all nodes in the loop. Similarly every
node dominates itself.

15 A(ii) Explain in detail about the Natural loops

One application of dominator information is in determining the loops of a
flow graph suitable for improvement. There are two essential properties of
loops:
A loop must have a single entrypoint, called the header. This entry point-
dominates all nodes in the loop, or it would not be the sole entry to the
loop.
There must be at least one way to iterate the loop(i.e.)at least one path
back to the header One way to find all the loops in a flow graph is to
search for edges in the flow graph whose heads dominate their tails. If
a→b is an edge, b is the head and a is the tail. These types of edges are
called as back edges.
Example:
In the above graph,
7→4 4 DOM 7
10 →7 7 DOM 10
4→3
8→3
9 →1
The above edges will form loop in flow graph. Given a back edge n → d,
we define the natural loop of the edge to be d plus the set of nodes that
can reach n without going through d. Node d is theheader of the loop.
Algorithm: Constructing the natural loop of a back edge.
Input: A flow graph G and a back edge n→d.
Output: The set loop consisting of all nodes in the natural loop n→d.
Method: Beginning with node n, we consider each node m*d that we
know is in loop, to make sure that m‟s predecessors are also placed in
loop. Each node in loop, except for d, is placed onceon stack, so its
predecessors will be examined. Note that because d is put in the loop
initially, we never examine its predecessors, and thus find only those
nodes that reach n without going throughd.
Procedure insert(m);
if m is not in loop then begin loop := loop U {m};
push m onto stack end;
stack : = empty;
loop : = {d}; insert(n);
while stack is not empty do begin
pop m, the first element of stack, off stack;
for each predecessor p of m do insert(p)
end

Inner loops:
If we use the natural loops as “the loops”, then we have the useful
property that unless two loops have the same header, they are either
disjointed or one is entirely contained in the other. Thus,neglecting loops
with the same header for the moment, we have a natural notion of inner
loop: one that contains no other loop. When two natural loops have the
same header, but neither is nested within the other, they are combined and
treated as a single loop.
Pre-Headers:
Several transformations require us to move statements “before the
header”. Therefore begin treatment of a loop L by creating a new block,
called the preheader. The pre-header has only the header as successor, and
all edges which formerly entered the header of L from outside L instead
enter the pre-header. Edges from inside loop L to the header are not
changed. Initially the pre- header is empty, but transformations on L may
place statements in it.

Reducible flow graphs:

Reducible flow graphs are special flow graphs, for which several code
optimization transformations are especially easy to perform, loops are
unambiguously defined, dominators can be easily calculated, data flow
analysis problems can also be solved efficiently. Exclusive use of
structured flow-of-control statements such as if-then-else, while-do,
continue, and break statements produces programs whose flow graphs are
always reducible.
 The most important properties of reducible flow graphs are that
1. There are no umps into the middle of loops from outside;
2. The only entry to a loop is through its header
Definition:
A flow graph G is reducible if and only if we can partition the edges into
two disjoint groups,
forward edges and back edges, with the following properties.
1. The forward edges from an acyclic graph in which every node can be
reached from initial node
of G.
2. The back edges consist only of edges where heads dominate theirs tails.
Example: The above flow graph is reducible. If we know the relation
DOM for a flow graph, we can find and remove all the back edges. The
remaining edges are forward edges. If the forward edges form an acyclic
graph, then we can say the flow graph reducible. In the above example
remove the five back edges 4→3, 7→4, 8→3, 9→1 and 10→7 whose
heads dominate their tails, the remaining graph is acyclic.

Or
15 B How is the optimization of basic block performed in compliers?
Explain it with necessary examples.
Optimization is applied to the basic blocks after the intermediate code
generation phase of the compiler. 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. These
transformations are useful for improving thequality of code that will be
ultimately generated from basic block.
There are two types of basic block optimizations:
1. Structure preserving transformations
2. Algebraic transformations
5.4.1 Structure preserving transformations
The structure-preserving transformation on basic blocks includes:
1. Dead Code Elimination
2. Common Subexpression Elimination
3. Renaming of Temporary variables
4. Interchange of two independent adjacent statements
1. Common sub-expression elimination:
In the common sub-expression, we don't need to be computed it over and
over again.
Instead of this we can compute it once and kept in store from where it's
referenced when
encountered again.
1. a : = b + c
2. b : = a - d
3. c : = b + c
4. d : = a - d
In the above expression, the second and forth expression computed the
same expression.
So the block can be transformed as follows:
1. a : = b + c
2. b : = a - d
3. c : = b + c
4. d : = b
2. Dead-code elimination
o It is possible that a program contains a large amount of dead code.
o This can be caused when once declared and defined once and forget to
remove them in this case they serve no purpose.
o Suppose the statement x:= y + z appears in a block and x is dead symbol
that means it will never subsequently used. Then without changing the
value of the basic block can safely remove this statement.
3. Renaming temporary variables
A statement t:= b + c can be changed to u:= b + c where t is a temporary
variable and u is a new temporary variable. All the instance of t can be
replaced with the u without changing the basic block value.
4. Interchange of statement
Suppose a block has the following two adjacent statements:
1. t1 : = b + c
2. t2 : = x + y
These two statements can be interchanged without affecting the value of
block when value of t1 does not affect the value of t2.
Algebraic transformations
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:
1. Constant Folding
2. Copy Propagation
3. Strength Reduction
1. Constant Folding:
Solve the constant terms which are continuous so that compiler does not
need to solve this expression.
Example:
x = 2 * 3 + y ⇒ x = 6 + y (Optimized code)
2. Copy Propagation:
It is of two types, Variable Propagation, and Constant Propagation.
Variable Propagation:
Constant Propagation:
3. StrengthReductin:
x = y ⇒ z = y + 2 (Optimized code)
z=x+2
x = 3 ⇒ z = 3 + a (Optimized code)
z=x+a
Replace expensive statement/ instruction with cheaper ones.
x = 2 * y (costly) ⇒ x = y + y (cheaper)
x = 2 * y (costly) ⇒ x = y << 1 (cheaper)
Staff In-charge HoD