RSS
Twitter
Facebook
Showing posts with label COMPILER DESIGN. Show all posts
COMPILER DESIGN
In case of local
optimization straight line codes with in basic block are optimized. The basic
block consists of only assignment statements with no jumps or loops. Some of
the optimization techniques that can be used for local optimization are
constant folding, constant propagations and algebraic transformations.
Optimization
considering many basic blocks of single procedure is called global
optimization. They use optimization techniques like code motion, elimination of
induction variables and reduction in strength of expression. Global
optimization requires data flow analysis to detect jump boundaries before
optimization.
Inter-procedural
optimization deals with optimization of entire program as a whole. This is very
difficult to achieve as it has to take care of different parameters passing
mechanization and non local variable access. The advantage of inter procedural
optimization is that each procedure can be optimized independently and linked
together at the end with the help of linker which performs optimization later
on.
COMPILER DESIGN
Code
Optimization phase in mainly use to optimize the code for better utilization of
memory and reduce the time taken for execution. Code optimization takes input
from intermediate code generator and performs machine independent optimization.
Code optimizer may also take input from code generator and perform machine
dependent code optimization. Compilers that use code optimization transformations
are called as optimizing compilers. Code optimization does not consider target machine
properties for optimization (like register allocation and memory management) if
input is from intermediate code generator.
Code
optimization tries to optimize that part of the code which are executed more
number of times, like statements within flow control block of for statement and
while statement. This is because the most programs always spend maximum
execution time on executing only few statements Code
optimization
analysis programs in two levels control flow analysis and data flow analysis.
In control flow analysis code optimization concentrates more on improving the
code of inner loops than outer statements, as inner loops are executed more
number of times than outer ones. A detailed data flow
analysis is
required for debugging the optimized code. Data flow analysis collects the
information of statistics about statements being executed more number of times.
This information is used in the process if optimization. Code optimization
should be such that best results crop up with minimum
effort.
Code
Optimization has to mainly achieve two goals
1. Preserve the
meaning of code – The output generated before (without) Code Optimization should
be same as the code after optimization.
2. Optimization
should reduce the cost of execution considerably. The effort spent on code optimization
should be worth it.
It implies that
amount of time taken for optimization should be very less when compared to the reduction
of overall execution time. Generally, a fast non optimizing compilers are
preferred for debugging programs
Code improvement
always need not be in code optimization phase. It can be incorporated in source
program or in intermediate code or on target code. In source program say, for
sorting program, user can choose different algorithm based on the cost function
like minimum space or minimum time. Each algorithm can be efficient it its own
way or other, like quick sort is very fast on unsorted/random array where as
other sorting like bubble sort is efficient on partially sorted array.
Intermediate code can be improved by improving loops and efficient address
calculation may give better results. In final code generation phase, optimized
code can be efficiently generated by selecting appropriate instruction, use
registers efficiently and some instruction transformations. Example: Keeping
most
used variables
in registers which avoids frequent fetching and storing in memory location.
This chapter deals with optimization of intermediate code represented as three
address code. Intermediate code is relatively independent at target machine so
optimization is machine independent.
Programs are
represented as flow graphs to study control flow and temporary variables are
used to store intermediate results help in data flow analysis. It is seen that
compilation speed is proportional to the size at program being compiled hence
amount of time taken for code optimization should be relatively less.
COMPILER DESIGN
Code
generation for function code is base on the runtime storage. The runtime
storage can by static allocation or stack allocation. In case of static
allocation the position of activation record in memory is fixed at the compile
time. To recollect about activation record, whenever a function is called,
activation records are generated, these records store the parameters to be
passed to functions, local data, temporaries, results & some machine status
information along with the return address. In case of stack allocation, every
time a function is called, the new activation record in generated & is
pushed onto stack, once the function completes, the activation record is popped
from stack. The three address code for function call consists of following
statements
1.
Call.
2.
Return
3.
end
4.
action
Call
statement is used for function Call, it has to mail the control to the function
along with saving the status of current function.
Return statement is used to give the control
back to called function. Action defines other operations or instructions for
assignment or flow control statements. End indicates the completion of
operations of called function.
COMPILER DESIGN
Target code
mainly depends on available instruction set and efficient usage of registers.
The main issues in design of code generation are
• Intermediate
representation: Linear representation like postfix and three address code
or quadruples and graphical representation like Syntax tree or DAG. Assume type
checking is done and input in free of errors. This chapter deals only with intermediate
representation as three address code.
• Target Code:
The target code may be absolute code, re-locatable machine code or assembly
language code. Absolute code can be executed immediately as the addresses are
fixed. But in case of re-locatable it requires linker and loader to place the
code in appropriate location and map (link) the required library functions. If
it generates assembly level code then assemblers are needed to convert it into
machine level code before execution. Re-locatable code provides great deal of
flexibilities as the functions can be compiled separately before generation of
object code.
• Address
mapping: Address mapping defines the mapping between intermediate representations
to address in the target code. These addresses are based on the runtime
environment used like static, stack or heap. The identifiers are stored in symbol
table during declaration of variables or functions, along with type. Each identifier
can be accessed in symbol table based on width of each identifier and offset. The
address of the specific instruction (in three address code) can be generated
using back patching
• Instruction
Set: The instruction set should be complete in the sense that all operations
can be implemented. Some times a single operation may be implemented using many
instruction (many set of instructions). The code generator should choose the
most appropriate instruction. The instruction should be chosen in such a way
that speed is of execution is minimum or other machine related resource
utilization should be minimum.
COMPILER DESIGN
malloc and free
are explicitly called in the program for dynamic management of memory. In case
of run time stack the memory management should be automatically done by the
calling sequence. Fully
dynamic runtime
environment automatically reclaim previous allocated blocks which are not used further
without explicit free call. This process is called as garbage collection.
Garbage collection can be achieved in any of the following methods
mark and sweep
stop and copy
generational
garbage collection
Mark and sweep: In
this method no memory is freed until malloc fails for insufficient memory. At
this point, the mark process marks the memory blocks whose values are not used
any more. In the sweep process the marked memory blocks are cleared and put
into free list. Some time memory compaction may be required in order to get
large free block.
Stop and copy:
In this method, the memory is divided into two halves and allocating storage
only from one half at a time. During the marking process all the updated blocks
(the blocks whose values are changed) are stored in second half. If performs
memory compaction automatically. Once all blocks in the used area have copied,
the used and unused halves of memory are interchanged and the processing continues.
Generational
garbage collection: The aim of this method is to reduce the delay. In order to
do this, the allocated objects that survive for long time are copied onto
permanent space and are not deallocated during reclaimation. This reduces the
search space for newer storage and hence reducing the time for searching.
COMPILER DESIGN
Heap is a linear
block of memory which is used to handle pointer allocation and deallocation.
Heap performs two operations, allocate and free. Allocate operation takes input
as size in bytes and returns pointer to block of memory of defined size. If no
memory exists, it returns null pointer. Free operation is used to free the
allocated block. Pascal uses new and dispose, where as C+ uses new and delete
for allocate and free operation respectively. C language uses malloc and free
as a part of standard library
stdlib.h for
allocation and dellocating memory. The prototype of these functions are as
follows
void *malloc
(unsigned size);
void free (void
*ptr);
One way of
implementing heap is maintaining a circular list of free blocks, from which memory
can be drawn through malloc function and returned through free function. Though
this is very simple to implement and maintain, it has few disadvantages. One of
the disadvantage is that, the pointer to free block may not be the one given to
malloc. Possibility of user giving invalid pointer corrupts the heap. Secondly
there can be small fragments of free blocks. This has to be compacted so that
large blocks of continuous memory are available for malloc.
More efficient
way of heap implementation is using circular linked list which keeps track of
both allocated and free blocks. Heap consists of nodes (blocks) which has
information of size of used area and size of free area followed by user space
and free space as shown below.
COMPILER DESIGN
Memory
for the program execution is broadly divided into two areas, one for storing
user data called data area and other for storing program called program area.
Normally the contents of program area do not change during the execution of the
program. Data area stores the global or static constants or literals.
Example:
Printf
(“ The solution is = % d”, 426);
In
the above example the value 426 is constant and the string “The solution is =”
are to be stored in global area. Other than global variables, there will be
local variables whose value changes during the execution, these are to be
stored in area local of the particular function. For this purpose stacks are
used.
The runtime memory is divided into following parts.
a.
Code area to store target code
b.
Static data area – to store global variables or literals
c.
Stack area – to store activation record during procedure calls and return.
Stack Operates in LIFO fashion [Last In First Out]
d. Heap –
This is used for dynamic memory allocation.
|
Code area
|
|
Global/Static
area
|
|
Stack
|
|
Free space
|
|
Heap
|
Stack and
heap may have separate memory blocks or they may share the same memory area.
COMPILER DESIGN
We
generate a series of branching statements with the targets of the jumps
temporarily left unspecified. Use a to-be-determined label table, each entry of
which contains a list of places that need to be back-patched. The same table
can also be used to implement labels and goto’s.
There
are two possible ways to translate switch statements.
Scheme 1:
code to evaluate E
into t
goto test
L[1]: code for S[1]
goto next
...
L[k]: code for S[k]
goto next
L[d]: code for S[d]
goto next
test:
if t = V[1] goto L[1]
...
if t = V[k] goto L[k]
goto L[d]
next:
...
Scheme 2:
code to evaluate E
into t
if t <> V[1]
goto L[1]
code for S[1]
goto next
L[1]: if t <>
V[2] goto L[2]
code for S[2]
goto next
...
L[k-1]: if t <>
V[k] goto
L[k]
code for S[k]
goto next
L[k]: code for S[d]
next:
The
first scheme is simpler to implement as it creates all the necessary labels
first and then goes for test and branching.
Case
three-address-code instructions used to translate a switch statement are as
below.
case t V1 L1
case t V2
L2
...
case t Vn-1
Ln-1
case t t Ln
label next
COMPILER DESIGN
Control
flow includes the study of Boolean expressions, which have two roles.
1.
They can be computed and treated similar to integers or real. Once can declare Boolean
variables, there are boolean constants and boolean operators. There are also
relational operators that produce Boolean values from arithmetic operands.
2.
They are used in certain statements that alter the normal flow of control.
Boolean
Expressions
One
question that comes up with Boolean expressions is whether both operands need
be evaluated. If we need to evaluate A OR B and find that A is true, must we
evaluate B? For example, consider evaluating A=0 OR 3/A < 1.2 when A is
zero.
This
comes up some times in arithmetic as well. Consider A*F(x). If the compiler
knows that for this run A is zero must it evaluate F(x)? Functions can have
side effects, do it could be a potential problem .
Short-Circuit
Code
This
is also called jumping code. Here the Boolean operators AND, OR, and NOT do not
appear in the generated instruction stream. Instead we just generate jumps to
either the true branch or the false branch.
Example:
if
( x < 100 II x > 200
&& x != y ) x = 0;
if
x < 100 goto L2
if
False x > 200 goto L1
if
False x != y goto L1
L2:
x = 0
L1:COMPILER DESIGN
The
goal is to generate 3-address code for expressions. Assume there is a function
gen() that given the pieces needed does the proper formatting so gen(x = y + z)
will output the corresponding 3-address code. gen() is often called with
addresses rather than lexemes like x. The constructor Temp() produces a new
address in whatever format gen needs.
COMPILER DESIGN
Data
structures for representation of TAC can be objects or records with fields for operator
and operands. Representations include quadruples, triples and indirect triples.
Quadruples
•
In the quadruple representation, there are four fields for each instruction: op,
arg1, arg2, result
– Binary ops have the
obvious representation
– Unary ops don’t use
arg2
– Operators like
param don’t use either arg2 or result
– Jumps put the
target label into result
•
The quadruples in Fig (b) implement the three-address code in (a) for the
expression
a = b * - c + b * - c
COMPILER DESIGN
•
TAC consists of a sequence of instructions, each instruction may have up to
three addresses, prototypically t1 = t2 op t3
•
Addresses may be one of:
–
A name. Each name is a symbol table index. For convenience, we write
the
names as the identifier.
–
A constant.
–
A compiler-generated temporary. Each time a temporary address is needed, the
compiler generates another name from the stream t1, t2, t3, etc.
• Temporary names
allow for code optimization to easily move instructions
• At target-code
generation time, these names will be allocated to registers or to memory.
•
TAC Instructions
–
Symbolic labels will be used by instructions that alter the flow of control.
The
instruction addresses of labels will be filled in later.
L: t1 = t2 op t3
–
Assignment instructions: x = y op z
• Includes binary arithmetic and logical
operations
–
Unary assignments: x = op y
• Includes unary arithmetic op (-) and
logical op (!) and type
conversion
–
Copy instructions: x = y
–
Unconditional jump: goto L
• L is a symbolic label of an instruction
–
Conditional jumps:
if x goto L If x is
true, execute instruction L next
ifFalse x goto L If x
is false, execute instruction L next
–
Conditional jumps:
if x relop y goto L
–
Procedure calls. For a procedure call p(x1, …, xn)
param x1
…
param xn
call p, n
–
Function calls : y= p(x1, …, xn) y = call p,n , return y
–
Indexed copy instructions: x = y[i] and x[i] = y
•
Left: sets x to the value in the location i memory units beyond y
•
Right: sets the contents of the location i memory units beyond x to y
–
Address and pointer instructions:
•
x = &y sets the value of x to be the location (address) of y.
•
x = *y, presumably y is a pointer or temporary whose value is a
location.
The value of x is set to the contents of that location.
•
*x = y sets the value of the object pointed to by x to the value of y.
Example:
Given the statement do i = i+1; while (a[i] < v ); , the
TAC can be written as below in two ways, using either symbolic labels or
position number of instructions for labels.
COMPILER DESIGN
TAC
can range from high- to low-level, depending on the choice of operators. In
general, it is a statement containing at most 3 addresses or operands.
The
general form is x := y op z, where “op” is an operator, x is the result, and y
and z are operands. x, y,
z are variables, constants, or “temporaries”. A
three-address instruction consists of at most 3 addresses for each statement
It
is a linearized representation of a binary syntax tree. Explicit names
correspond to interior nodes of the graph. E.g. for a looping statement ,
syntax tree represents components of the statement, whereas three-address code
contains labels and jump instructions to represent the flow-of-control as in
machine language.
A
TAC instruction has at most one operator on the RHS of an instruction; no
built-up arithmetic expressions are permitted.
e.g.
x + y * z can be translated as
t1 = y * z
t2 = x + t1
where
t1 & t2 are compiler–generated temporary names.
Since
it unravels multi-operator arithmetic expressions and nested control-flow statements,
it is useful for target code generation and optimization.
COMPILER DESIGN
Nodes
of a syntax tree or DAG are stored in an array of records. The integer index of
the record for a node in the array is known as the value
number of that node.
The
signature of a node is a triple < op, l, r> where op is the label, l the
value number of its left child, and r the value number of its right child. The
value-number method for constructing the nodes of a DAG uses the signature of a
node to check if a node with the same signature already exists in the array. If
yes, returns the value number. Otherwise, creates a new node with the given
signature.
Since
searching an unordered array is slow, there are many better data structures to
use. Hash tables are a good choice.
COMPILER DESIGN
•
Draw the parse tree
•
Perform a post order traversal of the parse tree
•
Perform the semantic actions at every node during the traversal
–
Creates a syntax tree if a new node is created each time functions Leaf and Node
are called
–
Constructs a DAG if before creating a new node, these functions check
whether
an identical node already exists. If yes, the existing node is returned.
SDD
to produce Syntax trees or DAG is shown below.
For
the expression a + a * ( b – c) + (b - c) * d, steps for constructing the DAG
is as below.
COMPILER DESIGN
A directed
acyclic graph (DAG) for an expression identifies the common sub
expressions (sub expressions that occur more than once) of the expression.
DAG's can be constructed by using the same techniques that construct syntax
trees.
A DAG has leaves
corresponding to atomic operands and interior nodes corresponding to operators.
A node N in a DAG has more than one parent if N represents a common sub expression,
so a DAG represents expressions concisely. It gives clues to compiler about the
generating efficient code to evaluate expressions.
Example 1: Given
the grammar below, for the input string id + id * id , the parse tree, syntax
tree and the DAG are as shown.
COMPILER DESIGN
SDT
is a complementary notation to SDD. All applications of SDD can be implemented using
SDT. SDT is a context-free grammar with program fragments called semantic actions
embedded within production bodies.
Any
SDT can be implemented by first building a parse tree and then performing the actions
in a left-to-right depth-first order i.e. during a pre-order traversal.
Typically SDT's are implemented during parsing without building parse tree.
During parsing, an action in a production body is executed as soon as all the
grammar symbols to the left of action have been matched.
SDT's
that can be implemented during parsing can be characterized by introducing distinct
marker nonterminals in place of each
embedded action. Each marker M has only one
production M _ _. If
grammar with marker nonterminals can be parsed by a given method, then the SDT
can be implemented during parsing.
COMPILER DESIGN
SDDs
are useful for is construction of syntax trees. A syntax tree is a condensed form
of parse tree.
• Syntax trees are useful for representing
programming language constructs like expressions and statements.
• They help compiler design by decoupling
parsing from translation.
• Each node of a syntax tree represents a
construct; the children of the node represent the meaningful components of the
construct.
• e.g.
a syntax-tree node representing an expression E1 + E2 has label
+
and
two children representing the sub expressions E1 and E2
• Each node is implemented by objects with
suitable number of fields; each object will have an op
field that is the label of the node with additional
fields as follows:
_ If
the node is a leaf, an additional field holds the lexical value for the
leaf
. This is created by function Leaf(op, val)
_ If
the node is an interior node, there are as many fields as the node has
children
in the syntax tree. This is created by function Node(op,
c1, c2,...,ck) .
Example:
The S-attributed definition in figure below constructs syntax trees for a
simple expression grammar involving only the binary operators + and -. As
usual, these operators are at the same precedence level and are jointly left
associative. All nonterminals have one synthesized attribute node,
which represents a node of the syntax tree.
Syntax
tree for a-4+c using the above SDD is shown below.
Steps
in the construction of the syntax tree for a-4+c
If
the rules are evaluated during a post order traversal of the parse tree, or
with reductions during a bottom-up parse, then the sequence of steps shown
below ends with p5 pointing to the root of the constructed syntax tree.
Constructing
Syntax Trees during Top-Down Parsing
With
a grammar designed for top-down parsing, the same syntax trees areconstructed, using
the same sequence of steps, even though the structure of the parse trees
differs significantly from that of syntax trees. The L-attributed definition
below performs the same translation as the S-attributed definition shown
before.
Dependency
Graph for a-4+c with L-Attributed SDD
Structure
of a Type
This
is an example of how inherited attributes can be used to carry information one
part of the parse tree to another. In C, the type int [2][3] can be read as,
"array of 2 arrays of 3 integers." The corresponding type expression
array(2, array(3, integer)) is represented by the tree as shown below.
The
nonterminals B and T have a synthesized attribute t representing a type. The nonterminal
C has two attributes: an inherited attribute b and a synthesized attribute t. The
inherited b attributes pass a basic type down the tree, and the synthesized t
attributes accumulate the result.
An
annotated parse tree for the input string int [2][3]
is shown below. The corresponding type expression is constructed by passing the
type integer from B, down the chain of C's through the inherited attributes b.
The array type is synthesized up the chain of C's through the attributes t.
COMPILER DESIGN
The
idea behind this class is that, between the attributes associated with a
production body, dependency-graph edges can go from left to right, but not from
right to left(hence "L-attributed"). Each attribute must be either
1.
Synthesized, or
2.
Inherited, but with the rules limited as follows. Suppose that there is a
production A->X1
X2 • • • Xn, and that there is an inherited attribute Xi.a
computed by a rule associated with this production. Then the rule
may use only:
(a)
Inherited attributes associated with the head A.
(b)
Either inherited or synthesized attributes associated with the occurrences of symbols
X1 X2 • • • Xi-1 located to the left
of Xi
(c)
Inherited or synthesized attributes associated with this occurrence of Xi
itself,
but only in such a way that there are no cycles in a dependency graph formed by
the attributes of this Xi.
Example
1: The following definition is L-attributed. Here the inherited attribute of T_ gets
its values from its left sibling F. Similarly, T1_ gets
its value from its parent T_ and left sibling F.
