Important Short Questions and Answers: Compiler Design - Code Generation

1. What are basic blocks?

A sequence of consecutive statements which may be entered only at the beginning and when entered are executed in sequence without halt or possibility of branch , are called basic blocks.

2.     What is a flow graph?

·     The basic block and their successor relationships shown by a directed graph is called a flow graph.

·     The nodes of a flow graph are the basic blocks.

3.     Mention the applications of DAGs.

·     We can automatically detect common sub expressions.

·     We can determine the statements that compute the values, which could be used outside the block.

·     We can determine which identifiers have their values used in the block.

4.     What are the advantages and disadvantages of register allocation and assignments?

·     Advantages:

i.     It simplifies the design of a compiler

·     Disadvantages:

i.     It is applied too strictly.

ii.     It uses registers in efficiently. Certain registers may go unused over substantial portions of the code, while unnecessary load and stores are generated.

5.     What is meant by virtual machine?

An intermediate language as a model assembly language, optimized for a non-existent

but ideal computer called a virtual machine.

6.     Discuss back-end and front end?

·     Back-end

i.     Intermediate to binary translation is usually done by a separate compilation pass called back end.

·     Front end

i.     There are several back ends for different target machines, all of which use the same parser and code generator called front end.

7.     Define relocatable object module.

The unpatched binary image is usually called a relocatable object module.

8.     What is meant by multiregister operations?

We can modify our labeling algorithm to handle operations like multiplication, division,

or function calls which normally requires more than one register to perform. Hence this operation is called multiregister operations.

9.     What is meant by peephole optimization?

Peephole optimization is a technique used in many compliers, in connection with the

optimization of either intermediate or object code. It is really an attempt to overcome the difficulties encountered in syntax directed generation of code.

10. List the types of addressing modes:-

i)                   Intermediate mode

ii)                Direct mode

iii)              Indirect mode

iv)              Effective address mode

11.            What is input to code generator?

The input to code generator consists of the intermediate representation of the source

program produced by the front end together 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 intermediate representation.

12.            How the use of registers is subdivided into 2 sub-problems?

·     During register allocation we select the set of variables that will reside in registers at a point in the program.

·     During a subsequent register assignment phase, we pick the specific register that a variable will reside in.

13.            How would you calculate the cost of an instruction?

·     The cost of an instruction to be one plus the costs associated with the source and destination address modes. This cost corresponds to the length of the instruction.

·     Address modes involving registers have cost zero, while those with a memory location or literal in them have cost one.

14.            What are the primary structure preserving transformations on basic blocks?

·     Common sub-expression elimination

·     Dead-code elimination

·     Renaming of temporary variable

·     Interchange of 2 independent adjacent statements.

15.            Give some examples for 3 address statements.

·     Call

·     Return

·     Halt

·     Action

16.            What are the characteristics of peephole optimization?

·     Redundant –instruction elimination

·     Flow-of control optimizations

·     Algebraic simplifications

·     Use of machine idioms

17.            What is a recursive procedure?

A procedure is recursive a new activation can begin before an earlier activation of the

same procedure has ended.

18.            What are the common methods for associating actual and formal parameters?

·     Call-by-value

Call-by-reference 

·     Copy-restore

·     Call-by-name

·     Macro-expansion

19.            Define DAG. Nov/Dec 2007

A DAG for a basic block is a directed acyclic graph with the following labels on

nodes:

i)                   Leaves are labeled by unique identifiers, either variable names or constants.

ii)                Interior nodes are labeled by an operator symbol.

iii)              Nodes are also optionally given a sequence of identifiers for labels.

20.            What are the issues in the design of code generators? Nov/Dec 2007

i)                   Input to the code generator

ii)                Target programs

iii)              Memory management

iv)              Instruction selection

v)                Register allocation

vi)              Choice of evaluation order

vii)           Approaches to code generation

21.            What are the various forms of target programs?

i)                   Absolute machine language

ii)                Relocatable machine language

iii)              Assembly language

22.            What is memory management?

Mapping names in the source program to addresses of data object in run time memory done comparatively by the front end and the code generator is called memory management

23. What is backpatching?

Process of leaving a blank slot for missing information and fill in the slot when the information becomes available is known as backpatching.

24. What are the rules to determine the leaders of basic blocks? i) The first statement is a leader

ii) Any statement that is the target of a conditional or unconditional goto is a leader

iii) Any statement that immediately follows a goto or conditional goto statement is a leader.

25. What is the use of algebraic transformation?

Algebraic transformation can be used to change the set of expressions computed by a basic blocks into an algebraically equivalent set.

26. What is meant by loop?

A loop is a collection of nodes in a flow graph such that

i) All nodes in the collection are strongly connected i.e., from any node in the loop to any other, there is a path of length one or more, wholly within the loop

ii) The collection of nodes has a unique entry, i.e. a node in the loop such that the only way to reach a node of the loop from a node outside the loop is to first go through the entry.

27.                        What is register descriptor and address descriptor?

·     A register descriptor keeps track of what is currently in each register.

·     An address descriptor keeps track of the location where the current value of the name can be found at run time.

28.                        What are the characteristics of peephole optimization?

i) Redundant – instruction elimination iii) Flow – of – control optimizations

ii) Algebraic simplifications iv) Use of machine idioms