(Aktu Btech) Compiler Design Important Unit-5 Code Generation

With B.Tech AKTU Quantum Book, you can delve into the complexities of Compiler Design. Access key notes, frequently asked questions, and helpful insights for understanding this critical area. Unit-5 Code Generation

Dudes 🤔.. You want more useful details regarding this subject. Please keep in mind this as well.

Important Questions For Compiler Design:
*Quantum               *B.tech-Syllabus
*Circulars                *B.tech AKTU RESULT
* Btech 3rd Year     * Aktu Solved Question Paper

Q1. What is code generation ? Discuss the design issues of code generation.

Ans. 1. Code generation is the final phase of compiler. 

2. It takes as input the Intermediate Representation (IR) produced by the front end of the compiler, along with relevant symbol table information, and produces as output a semantically equivalent target program as shown in Fig.

Design issues of code generator are: 

• 1. Input to the code generator: 
  • a. The input to the code generator is the intermediate representation of the source program produced by the front end, along with information in the symbol table. 
  • b. IR includes three address representations and graphical representations.  
• 2. The target program: 
  • a. 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. 
  • b. The most common target machine architectures are RISC (Reduced Instruction Set Computer), CISC (Complex Instruction Set Computer), and stack based.
• 3. Instruction selection: 
  • a. The code generator must map the IR program into a code sequence that can be executed by the target machine.
  • b. If the IR is high level, the code generator may translate each IR statement into a sequence of machine instructions using code templates. 
• 4. Register allocation: 
  • a. A key problem in code generation is deciding what values to hold in which registers on the target machine do not have enough space to hold all values. 
  • b. Values that are 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.  
  • c. The use of registers is often subdivided into two subproblems: 
    • i. Register allocation, during which we select the set of variables that will reside in registers at each point in the program. 
    • ii. Register assignment, during which we pick the specific register that a variable will reside in.
• 5. Evaluation order: 
  • a. The order in which computations are performed can affect the efficiency of the target code. 
  • b. Some computation orders require fewer registers to hold intermediate results than others.

Q2. Write an algorithm to partition a sequence of three address statements into basic blocks.

Ans. The algorithm for construction of basic block is as follows: 

Input: A sequence of three address statements. 

Output: A list of basic blocks with each three address statements in exactly one block.

Method: 

• 1. We first determine the set of leaders, the first statement of basic block. The rules we use are given as: 
  • a. The first statement is a leader. 
  • b. Any statement which is the target of a conditional or unconditional goto is a leader. 
  • c. Any statement which immediately follows a conditional goto is a leader. 
• 2. For each leader construct its basic block, which consist of leader and all statements up to the end of program but not including the next leader. Any statement not placed in the block can never be executed and may now be removed, if desired.

Q3. What is code optimization ? Discuss the classification of code optimization.

Ans. Code optimization: 

• 1. The code optimization refers to the techniques used by the compiler to improve the execution efficiency of generated object code. 
• 2. It involves a complex analysis of intermediate code and performs various transformations but every optimizing transformation must also preserve the semantic of the program.

Classification of code optimization: 

• 1. Machine dependent: The machine dependent optimization can be achieved using following criteria: 
  • a. Allocation of sufficient number of resources to improve the execution efficiency of the program. 
  • b. Using immediate instructions wherever necessary. 
  • c. The use of intermix instructions along with the data increases the speed of execution.  
• 2. Machine independent: The machine independent optimization can be achieved using following criteria: 
  • a. The code should be analyzed completely and use alternative equivalent sequence of source code that will produce a minimum amount of target code. 
  • b. Use appropriate program structure in order to improve the efficiency of target code. 
  • c. By eliminating the unreachable code from the source program. 
  • d. Move two or more identical computations at one place and make use of the result instead of each time computing the expressions. 

Q4. Write a short note on direct acyclic graph.

Ans. DAG: 

• 1. The abbreviation DAG stands for Directed Acyclic Graph. 
• 2. DAGs are useful data structure for implementing transformations on basic blocks. 
• 3. A DAG gives picture of how the value computed by each statement in the basic block is used in the subsequent statement of the block. 
• 4. Constructing a DAG from three address statement is a good way of determining common sub-expressions within a block. 
• 5. A DAG for á basic block has following properties: 
  • a. Leaves are labeled by unique identifier, either a variable name or constants. 
  • b. Interior nodes are labeled by an operator symbol. 
  • c. Nodes are also optionally given a sequence of identifiers for labels.
• 6 Since, DAG is used in code optimization and output of code optimization is machine code and machine code uses register to store variable used in the source program. 

Advantage of DAG: 

• 1. We automatically detect common sub-expressions with the DAG help of algorithm. 
• 2. We can determine which identifiers have their values used in the block. 
• 3. We can determine which statements used outside compute values which could be the block.

Q5. How DAG is different from syntax tree ? Construct the DAG for the following basic blocks :

                        a := b + c

                        b := b – d

                        c := c + d

                        e = b + c 

Also, explain the key application of DAG.

Ans. DAG v/s Syntax tree:

• 1. Directed Acyclic Graph is a data structure for transformations on the basic block. While syntax tree is an abstract representation of the language constructs. 
• 2. DAG is constructed from three address statement while syntax tree is constructed directly from the expression. 

DAG for the given code is: 

• 1. The two Occurrences of sub-expressions b + c compute the same value. 
• 2. Value computed by a and e are same.

Applications of DAG: 

• 1. Scheduling: Directed acyclic graphs representations of partial orderings have many applications in scheduling for systems of tasks. 
• 2. Data processing networks: A directed acyclic graph may be used too represent a network of processing elements. 
• 3. Data compression: Directed acyclic graphs may also be used as a compact representation of a collection of sequences. In this type of application, one finds a DAG in which the paths form the sequences. 
• 4. It helps in finding statement that can be recorded. 

Q6. What is data flow analysis ? How does it use in code optimization?

Ans.

• 1. Data flow analysis is a process in which the values are computed using data flow properties. 
• 2. In this analysis, the analysis is made on data flow. 
• 3. A program’s Control Flow Graph (CFG) is used to determine those parts of a program to which a particular value assigned to a variable might propagate.
• 4. A simple way to perform data flow analysis of programs is to set up data flow equations for each node of the control flow graph and solve them by repeatedly calculating the output from the input locally at each node until the whole system stabilizes, i.e., it reaches a fix point. 
• 5. Reaching definitions is used by data flow analysis in code optimization.  

Reaching definitions:  

1. A definition D reaches at point p if there is a path from D top along which D is not killed. 

2. A definition D of variable x is killed when there is a redefinition of x.

3. The definition d1 is said to a reaching definition for block B2. But the definition dl is not a reaching definition in block B3, because it is killed by definition d2 in block B2.  

Compiler Design Btech Quantum PDF, Syllabus, Important Questions

Compiler Design Quantum PDF | AKTU Quantum PDF:

AKTU Important Links | Btech Syllabus

Important Links-Btech (AKTU)