Compiler Design Oral Questions and Answer Part 4

1. Mention the properties that a code generator should possess.

• · The code generator should produce the correct and high quality code. In other words, the code generated should be such that it should make effective use of the resources of the target machine.
• · Code generator should run efficiently.
  • · Define and use – the three address statement a:=b+c is said to define a and to use b and c.
  • · Live and dead – the name in the basic block is said to be live at a given point if its value is used after that point in the program. And the name in the basic block is said to be dead at a given point if its value is never used after that point in the program.

2. List the terminologies used in basic blocks.

3. What is a flow graph?

A flow graph is a directed graph in which the flow control information is added to the basic blocks.

• · The nodes to the flow graph are represented by basic blocks
• · The block whose leader is the first statement is called initial block.
• · There is a directed edge from block B1 to block B2 if B2 immediately follows B1 in the given sequence. We can say that B1 is a predecessor of B2.

4. What is a DAG? Mention its applications.

Directed acyclic graph(DAG) is a useful data structure for implementing transformations on basic blocks.

DAG is used in

• · Determining the common sub-expressions.
• · Determining which names are used inside the block and computed outside the block.
• · Determining which statements of the block could have their computed value outside the block.
• · Simplifying the list of quadruples by eliminating the common su-expressions and not performing the assignment of the form x := y unless and until it is a must.

5. Define peephole optimization.

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.

6. List the characteristics of peephole optimization.

• · Redundant instruction elimination
• · Flow of control optimization
• · Algebraic simplification
• · Use of machine idioms

7. How do you calculate the cost of an instruction?

The cost of an instruction can be computed as one plus cost associated with the source and destination addressing modes given by added cost.

MOV R0,R1 1

MOV R1,M 2

SUB 5(R0),*10(R1) 3

8. What is a basic block?

A basic block is a sequence of consecutive statements in which flow of control enters at the beginning and leaves at the end without halt or possibility of branching.

Eg. t1:=a*5

t2:=t1+7

t3:=t2-5

t4:=t1+t3

t5:=t2+b

9. How would you represent the following equation using DAG?

a:=b*-c+b*-c