Code Generation Questions and Answers

31.

Sethi Ullman numbering labels each node of an expression tree with

A.the minimum number of registers needed to evaluate that subtree
B.the number of instructions that the subtree will finally produce
C.the depth of the node below the root of the tree
D.the cost in cycles of the operation at that node

Answer: A

Correct answer: the minimum number of registers needed to evaluate that subtree

The label of a node follows from its children: equal labels need one more register than either, unequal labels need the larger of the two. Evaluating the more demanding subtree first then minimises the registers required, which is what the numbering is for.

Discuss in Forum

32.

In Sethi Ullman labelling, a leaf that is the left child is labelled 1 and a leaf that is the right child is labelled 0. What label does an interior node whose children are labelled 2 and 2 receive?

Answer: B

When the two labels are equal the node is labelled one more than either, so two and two give three. When they differ the node takes the larger of the two labels unchanged. Working a small tree by hand is the quickest way to fix the rule in mind.

Discuss in Forum

33.

An interior node in Sethi Ullman labelling has children labelled 3 and 1. What label does it receive?

Answer: C

Unequal labels mean the larger subtree can be evaluated first and its result held in one register while the smaller is evaluated, so the maximum is unchanged at three. Reversing the order would have required a fourth register.

Discuss in Forum

34.

Evaluating the child with the larger Sethi Ullman label first is advantageous because

A.the larger of the subtrees contains more instructions to schedule
B.the smaller subtree may be eliminated as dead code
C.the machine can only evaluate left children first
D.the result of the smaller subtree then needs only one held register

Answer: D

Holding one register while evaluating the smaller subtree costs less than the reverse order. The saving is exactly what makes the labelling worth computing at all. On a machine with few registers the difference can decide whether spilling occurs.

Discuss in Forum

35.

Sethi Ullman numbering assumes

A.an expression tree with no shared subexpressions
B.a machine with an unlimited number of registers
C.that every operation costs exactly one cycle
D.that the expression contains only unary operators

Answer: A

Sharing turns the tree into a graph and the optimality argument no longer holds. The method also assumes a uniform register set with no special purpose registers. Real machines often violate both assumptions, so the result is a useful guide rather than a rule.

Discuss in Forum

36.

An instruction schedule that violates a data dependence produces code that is

A.unable to be assembled into machine instructions
B.wrong rather than merely slower than it might be
C.correct but slower than the original ordering was
D.identical in behaviour to any other valid schedule

Answer: B

Reading a value before it has been written gives the wrong answer, not a stall. Dependences are therefore hard constraints on the schedule, while latencies are merely costs the scheduler tries to hide by filling the gaps with independent work.

Discuss in Forum

37.

A data dependence between two instructions means

A.they use the same machine register as a destination
B.the second one is unreachable from the first
C.they cannot be reordered without changing the result
D.they must be placed in different basic blocks

Answer: C

True dependences, where one reads what the other wrote, are the fundamental constraint. Anti and output dependences arise from reusing names and can often be removed by renaming. Only the true dependence reflects an actual flow of data.

Discuss in Forum

38.

Match each kind of dependence with its description.
List I
A. true dependence
B. anti dependence
C. output dependence
D. no dependence
List II
1. two writes to the same location
2. a read of a value that was just written
3. the instructions may be freely reordered
4. a write to a location that was just read

A.A-4, B-2, C-1, D-3
B.A-2, B-4, C-3, D-1
C.A-3, B-1, C-4, D-2
D.A-2, B-4, C-1, D-3

Answer: D

Only the true dependence reflects real data flow. The other two arise from reusing a name and can often be removed by giving one of the instructions a fresh destination. Static single assignment form removes them all by construction.

Discuss in Forum

39.

Assertion (A): Anti dependences and output dependences can often be removed by renaming.
Reason (R): They arise from reusing a storage location rather than from any real flow of data between the instructions.

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

Answer: A

Both are true and the reason gives the mechanism, and this is one of the attractions of static single assignment form. Giving each write its own name leaves only the true dependences, which the schedule genuinely must respect.

Discuss in Forum

40.

List scheduling within a basic block works by

A.delaying every instruction until all its successors are ready
B.repeatedly issuing a ready instruction chosen by a priority rule
C.trying every possible ordering and keeping the shortest
D.issuing the instructions in the order they were generated

Answer: B

Correct answer: repeatedly issuing a ready instruction chosen by a priority rule

List scheduling maintains the set of instructions whose operands are available and picks one by a heuristic - usually the longest path to the end of the block. It is greedy and not optimal, but optimal scheduling is NP-hard and list scheduling comes close enough at a fraction of the cost.

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