Code Generation Questions and Answers

11.

Assertion (A): Dynamic programming can find the least cost tiling of an expression tree.
Reason (R): The optimal cost of a node depends only on the optimal costs of its subtrees.

A.A is true but R is false
B.A is false but R is true
C.Both A and R are true, and R is the correct explanation of A
D.Both A and R are true, but R is not the correct explanation of A

Answer: C

Both are true and the reason gives the mechanism, and the property is exactly what dynamic programming requires. Optimality no longer follows once the intermediate form is a graph rather than a tree, since a shared node has more than one parent.

Discuss in Forum

12.

Optimal instruction selection over a directed acyclic graph rather than a tree is

A.solved by the same dynamic programming algorithm unchanged
B.impossible because the graph contains cycles by definition
C.unnecessary because graphs never arise in real programs
D.computationally hard, so heuristics are used in practice

Answer: D

Correct answer: computationally hard, so heuristics are used in practice

A tree can be tiled optimally in linear time because each subtree has one parent and can be solved independently. A directed acyclic graph has shared subexpressions with several parents, so the choices interact and the problem becomes NP-hard - which is why the graph is usually split into trees and each tiled separately.

Discuss in Forum

13.

A.which values reside in registers over which parts of the program
B.which particular register each value will occupy
C.the sequence in which the instructions will finally be executed
D.how many bytes each declared variable will occupy

Answer: A

Allocation chooses what to keep in registers and assignment chooses which register. The two are often performed together, though the distinction matters when discussing algorithms. Machine constraints on particular registers make the second decision non trivial.

Discuss in Forum

14.

A.whether the target machine has registers enough for the purpose
B.which specific register holds each value that has been allocated one
C.which values are worth keeping in registers at all
D.the sequence in which the generated instructions appear

Answer: B

Assignment matters because instructions may restrict which register a particular operand may use. Register pairs for multiplication and division are the classic constraint. Such constraints are expressed as pre-coloured nodes in the interference graph.

Discuss in Forum

15.

The number of colours available when register allocation is modelled as graph colouring corresponds to

A.the number of basic blocks in the procedure's flow graph
B.the number of distinct types declared in the source program
C.the number of registers the target machine provides
D.the number of values that the procedure computes

Answer: C

Each colour stands for one physical register, so a graph needing more colours than the machine has registers cannot be coloured as it stands. Removing a node by spilling its value to memory is what makes the remaining graph colourable.

Discuss in Forum

16.

Two values interfere in a register allocator when

A.they are assigned in the same basic block
B.they have the same type in the source program
C.one of them is used as an operand of the other
D.both are live at the same point in the program

Answer: D

Simultaneous liveness means they cannot share storage. Building the interference graph therefore depends on a liveness analysis over the flow graph. An inaccurate liveness result produces either wrong code or wasted registers.

Discuss in Forum

17.

An interference graph requires 5 colours but the machine has only 4 registers. What must the allocator do?

A.spill at least one value to memory
B.reject the program as impossible to compile
C.allocate a fifth register that the machine lacks
D.recolour the graph using only three colours

Answer: A

Spilling removes a node from the graph, which may make the rest colourable. The spilled value is stored and reloaded around its uses, which costs memory traffic but always succeeds. Spilling therefore guarantees that allocation eventually terminates.

Discuss in Forum

18.

Spilling a value means

A.recomputing it from scratch at every point of use
B.keeping it in memory and loading it around each use
C.throwing it away on the grounds that it will never be read again
D.handing it to a register that belongs to some other procedure

Answer: B

A store after the definition and a load before each use replace the register. Allocators choose to spill the value whose uses are fewest or least frequently executed. A value used only outside loops is nearly always the better candidate.

Discuss in Forum

19.

Rematerialisation as an alternative to spilling means

A.extending the lifetime of the value across the whole procedure
B.colouring the interference graph with one additional colour
C.recomputing a cheap value instead of storing and reloading it
D.moving the value into a different register of the machine

Answer: C

A constant or a simple address computation often costs less to recompute than to load from memory. The allocator marks such values as candidates before it starts spilling. The decision depends on the relative cost of a load on the target machine.

Discuss in Forum

20.

Assertion (A): A constant is usually rematerialised rather than spilled.
Reason (R): Recomputing a constant costs a single instruction while reloading it costs a memory access.

A.Both A and R are true, but R is not the correct explanation of A
B.A is true but R is false
C.A is false but R is true
D.Both A and R are true, and R is the correct explanation of A

Answer: D

Both are true and the reason gives the mechanism, and the same reasoning extends to simple address computations. Anything whose operands are still available and whose cost is below a load is worth recomputing rather than storing.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Code Generation Questions and Answers || Code Generation MCQ Questions and Answers || Code Generation GK Questions and Answers || Code Generation GK MCQ Questions || Code Generation Multiple Choice Questions and Answers || Code Generation GK || GK on Code Generation || Compiler Design Questions and Answers || Compiler Design MCQ Questions and Answers || Compiler Design GK Questions and Answers || GK on Compiler Design

Code Generation Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications