Code Optimization Questions and Answers

Q: Data flow equations are solved by

Correct answer: iterating until no set changes any furtherThe equations are recursive round loops, so they are solved by initialising the sets and applying the transfer and meet functions repeatedly until nothing changes. Termination is guaranteed because the sets form a finite lattice and each iteration moves monotonically in one direction, so the process cannot cycle.

21.

The following are all typical peephole optimisations EXCEPT

A.reordering the basic blocks of the whole procedure
B.eliminating a load immediately following the matching store
C.replacing a jump to a jump by a single jump to the final target
D.removing an instruction that is unreachable from any jump

Answer: A

Correct answer: reordering the basic blocks of the whole procedure

Peephole optimisation looks through a sliding window of a few adjacent instructions and knows nothing beyond it. Reordering blocks requires a view of the whole flow graph, so it is a global transformation. The other three - redundant load elimination, jump chaining and unreachable instruction removal - are all decidable within a small window.

Discuss in Forum

22.

Data flow analysis computes

A.whatever faults of form the parser somehow failed to detect
B.facts about the values or expressions holding at each program point
C.the number of times each instruction will be executed at run time
D.the machine registers each variable will eventually occupy

Answer: B

Correct answer: facts about the values or expressions holding at each program point

Data flow analysis propagates sets of facts round the flow graph until they stabilise, answering questions such as which definitions reach here, which variables are live, and which expressions are available. Everything a global optimiser does rests on those answers.

Discuss in Forum

23.

A definition of a variable reaches a point if

A.the variable is live at the point in question
B.the definition is the only one in the whole procedure
C.there is a path from the definition to the point with no redefinition
D.the definition happens to appear earlier in the text than the point

Answer: C

Correct answer: there is a path from the definition to the point with no redefinition

Reaching definitions is a forward analysis, and the definition of the property is a path property: some path exists along which the assignment is not overwritten. Note the word some - the analysis is a may analysis, so a definition reaches if it might, which is what makes the result conservative and therefore safe.

Discuss in Forum

24.

A variable is live at a point if

A.it has been assigned some value earlier on in the program
B.it is declared in the innermost enclosing block
C.it appears anywhere in the procedure being analysed
D.its current value may be used along some path from that point

Answer: D

Correct answer: its current value may be used along some path from that point

Liveness is a backward analysis and again a may property: the variable is live if any path from here reads it before writing it. Its principal use is register allocation, since two variables that are never live at the same time can share a register, and dead code elimination, since an assignment to a dead variable can be deleted.

Discuss in Forum

25.

An expression is available at a point if

A.it has been computed on every path and no operand has changed since
B.it has been computed on at least one of the paths reaching the point
C.all of its operands are compile time constants
D.it appears at least twice in the procedure being analysed

Answer: A

Available expressions is a forward analysis with intersection as its meet, because the value must be valid along every path. It is what justifies common subexpression elimination. An expression available on only some paths is a case for partial redundancy elimination.

Discuss in Forum

26.

Match each data flow problem with its direction and meet operation.
List I
A. reaching definitions
B. live variables
C. available expressions
D. very busy expressions
List II
1. forward, intersection
2. forward, union
3. backward, intersection
4. backward, union

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

Answer: B

Direction says whether information flows with or against control, and the meet says whether a fact must hold on all paths or on some. Together they classify every classical problem. A new analysis is usually described by naming its place in the same scheme.

Discuss in Forum

27.

A data flow analysis whose meet operation is intersection is answering a question of the form

A.how many paths reach this point in total
B.which path will actually be taken at run time
C.does this hold along every path reaching the point
D.does this hold along at least one path reaching the point

Answer: C

Intersection means all paths must agree, which is what availability and very busy expressions require. Union answers the weaker question of whether any path establishes the fact. Choosing the wrong meet operation produces an analysis that is simply unsound.

Discuss in Forum

28.

Data flow equations are solved by

A.a single pass over the flow graph in textual order
B.solving a system of linear equations exactly
C.executing the program on representative inputs
D.iterating until no set changes any further

Answer: D

Correct answer: iterating until no set changes any further

The equations are recursive round loops, so they are solved by initialising the sets and applying the transfer and meet functions repeatedly until nothing changes. Termination is guaranteed because the sets form a finite lattice and each iteration moves monotonically in one direction, so the process cannot cycle.

Discuss in Forum

29.

Assertion (A): Iterative data flow analysis is guaranteed to terminate.
Reason (R): Each iteration changes the sets only in one direction and the lattice of possible values has finite height.

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 it is the standard termination argument. Monotone transfer functions over a finite lattice cannot cycle, so the iteration must reach a fixed point in a bounded number of rounds.

Discuss in Forum

30.

The meet over all paths solution to a data flow problem is

A.an approximation that is rather weaker than the iterative solution
B.the ideal answer, which the iterative solution may only approximate
C.always exactly what the iterative algorithm computes
D.computed by enumerating every path through the flow graph

Answer: B

Correct answer: the ideal answer, which the iterative solution may only approximate

The meet-over-all-paths solution takes the meet of the facts along every path reaching a point, which is what one would ideally like to know. The iterative algorithm computes the maximum fixed point instead, and the two coincide when the transfer functions distribute over the meet - which they do for many, but not all, analyses.

Discuss in Forum

Loading…

Topics

Other Subjects

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

Code Optimization Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications