Assignment on Compiler Design

Assignment:03

1. What is Code generation ?

ans:-Code generation is a mechanism where a compiler takes the source code as an input and converts it into machine code. This machine code is actually executed by the system. Code generation is generally considered the last phase of compilation, although there are multiple intermediate steps performed before the final executable is produced. These intermediate steps are used to perform optimization and other relevant processes.

The code generation process is performed by a component known as a code generator, part of the compiler program. The original source code of any program passes through multiple phases before the final executable is generated. This final executable code is actually the machine code, which computer systems can execute readily.

In the intermediate phases of compilation, code optimization rules are applied one at a time. Sometimes these optimization processes are dependent on each other, so they are applied one after another based on the dependency hierarchy. After passing multiple phases, a parse tree or an abstract syntax tree is generated and that is the input to the code generator. At this point, the code generator converts it into linear sequential instructions. After this stage, there may be some more steps depending upon the compiler. The final optimized code is the machine code for execution and output generation.

2. Explain dag representation of program & Code generation from dag .

DAG Representation

• DAG stands for Directed Acyclic Graph
• Syntax tree and DAG both, are graphical representations. Syntax tree does not find the common sub expressions whereas DAG can
• Another usage of DAG is the application of optimization technique in the basic block
• To apply optimization technique on basic block, a DAG is a constructed three address code which is the output of an intermediate code generation

Characteristics of DAG are:

• All internal nodes store operator values
• External or leaf nodes are identifiers or variable names or constants

Algorithm for Construction of DAG

There are three possible cases to construct DAG on three address code:

Case 1: x = y op z

Case 2: x = op y

Case 3: x = y

DAG can be constructed as follows:

STEP 1:

If y is undefined then create a node with label y. Similarly create a node with label z.

STEP 2:

For case 1, create a node with label op whose left child is node y, and node z will be the right child. Also, check for any common sub expressions. For case 2, determine if a node is labelled op. such node will have a child node y. for case 3 node n will be node y.

STEP 3:

Delete x from list of identifiers for node x. append x to the list of attached identifiers for node n found in step 2.

Example:

Consider the following three address code statements.

                                                                       a = b * c

                                                                       d = b

                                                                       e = d * c

                                                                       b = e

                                                                       f = b + c

                                                                       g = f + d

Step 1

Consider the first statement, i.e., a = b * c. Create a leaf node with label b and c as left and right child respectively and parent of it will be *. Append resultant variable a to the node *.

Step 2

For second statement, i.e., d = b, node b is already created. So, append d to this node.

Step 3

For third statement e = d * c, the nodes for d, c and * are already create. Node e  is not created, so append node e to node *.

Step 4

For fourth statement b = e, append b to node e.

Step 5

For fifth statement f = b + c, create a node for operator + whose left child b and right child c and append f to newly created node +

Step 6

For last statement g = f + d, create a node for operator + whose left child d and right child f and append g to newly created node +.

DAG Applications:

• Determines the common sub expressions
• Determines the names used inside the block, and the names that are computed outside the block
• Determines which statements of the block could have their computed value outside the block
• Code may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code; this representation allows the compiler to perform common subexpression elimination efficiently
• Several programming languages describe systems of values that are related to each other by a directed acyclic graph. When one value changes, its successors are recalculate; each value is evaluated as a function of this predecessors in the DAG

 Code Generation from DAG's

The optimal code generation algorithm is an NP-complete problem. Directed acyclic graphs allow a code Generation heuristic:

Put out code for each node immediately after code for its children has been emitted as far as possible because then the results are more apt to still be available, say in a register.

To prepare the list of DAG nodes to compute (that is, the list for which code is to be emitted), start at the root of the right-most subtree. Put this node on the list, L, and continue by adding a left-most node to the list after all its parents are already on the list. Then generate code for the nodes in L by starting at the end of L and proceeding to the beginning.

Example 10

Generating code from a DAG

Thus, we would put out code for node 8 first, then node 9, etc.

Another way to put out good code from DAG's is to break the DAG up into trees and to use a code generation algorithm which is optimal on trees. (Of course, it takes time to break up the DAG.)

Example 11

Breaking DAG's into trees

3. Explain intermediate code generation in brief.

Ans: During the translation of a source program into the object code for a target machine, a compiler may generate a middle-level language code, which is known as intermediate code or intermediate text.

A source code can directly be translated into its target machine code, then why at all we need to translate the source code into an intermediate code which is then translated to its target code? Let us see the reasons why we need an intermediate code.

• If a compiler translates the source language to its target machine language without having the option for generating intermediate code, then for each new machine, a full native compiler is required.
• Intermediate code eliminates the need of a new full compiler for every unique machine by keeping the analysis portion same for all the compilers.
• The second part of compiler, synthesis, is changed according to the target machine.
• It becomes easier to apply the source code modifications to improve code performance by applying code optimization techniques on the intermediate code.

SHARE

About Admin of the Blog:

Rajnish kumar is the CEO/founder of Tech Hindi Sagar .He is a Computer Science Engineer ,Web Designer,Web Developer and a Pro Blogger..Inspired to make things looks better.

• 
• 
• 
• 
•