Code Optimization Questions and Answers

Q: A back edge in a flow graph is an edge

Correct answer: from a node to one of its dominatorsA dominator of a node is a node through which every path to it must pass, so an edge back to a dominator closes a cycle in which the target is guaranteed to precede the source. This is what identifies a natural loop, and finding back edges is therefore the first step in every loop transformation.

41.

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

42.

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

43.

A conservative approximation in data flow analysis is one that

A.computes the exact answer in every possible case
B.requires the program to contain no loops at all
C.may miss an optimisation but never enables an unsafe one
D.enables every optimisation but occasionally breaks the program

Answer: C

Correct answer: may miss an optimisation but never enables an unsafe one

Every data flow analysis errs deliberately, and the direction of the error is chosen so that uncertainty costs performance rather than correctness. Being told a variable might be live when it is not merely wastes a register; being told it is dead when it is not corrupts the program.

Discuss in Forum

44.

A node d of a flow graph dominates node n if

A.d appears before n in the textual order of the blocks
B.there is at least one path from d to n in the graph
C.n is reachable from d and d is reachable from n
D.every path from the entry to n passes through d

Answer: D

Dominance is what identifies loop headers and is the basis for finding natural loops. The entry node dominates every node, and every node dominates itself. The relation is computed once and used repeatedly by later passes.

Discuss in Forum

45.

A back edge in a flow graph is an edge

A.from a node to one of its dominators
B.from a node to any node earlier in textual order
C.leaving the procedure and returning to its caller
D.connecting two nodes that have no common dominator

Answer: A

Correct answer: from a node to one of its dominators

A dominator of a node is a node through which every path to it must pass, so an edge back to a dominator closes a cycle in which the target is guaranteed to precede the source. This is what identifies a natural loop, and finding back edges is therefore the first step in every loop transformation.

Discuss in Forum

46.

The natural loop of a back edge from n to d consists of

A.every node of the flow graph reachable from d
B.d together with all nodes that can reach n without passing through d
C.every node lying between d and n in the textual order of the blocks
D.only the two nodes d and n themselves

Answer: B

The definition captures exactly the region controlled by the header. Natural loops are either disjoint or nested, which is what makes them convenient to optimise. Irreducible graphs can produce loops that overlap without nesting.

Discuss in Forum

47.

State whether the following is true or false.
A compiler can identify loops in a program without reference to the source syntax.

A.True only at large scales
B.False only at small scales
C.True
D.False

Answer: C

Back edges in the flow graph reveal the loops whatever construct produced them. A loop built from conditional jumps is optimised exactly as one written with a while statement. The optimiser works from the graph and never sees the source syntax at all.

Discuss in Forum

48.

A reducible flow graph is one in which

A.every node has at most two successors in the graph
B.the graph contains no cycles of any kind at all
C.every loop was written using a structured statement
D.every back edge goes to a dominator of its source

Answer: D

Programs written with structured control constructs produce reducible graphs. Reducibility makes many analyses simpler and faster, which is one argument against unrestricted jumps. Irreducible graphs can still be analysed, at greater cost.

Discuss in Forum

49.

A use definition chain links

A.a use of a variable to the definitions that may reach it
B.a definition of a variable to the block that contains it
C.two variables that must hold the same value
D.a procedure call to the procedure it invokes

Answer: A

Such chains are built directly from reaching definitions. A use with exactly one reaching definition that assigns a constant is immediately a candidate for constant propagation. Definition use chains run the other way and support dead code elimination.

Discuss in Forum

50.

Static single assignment form makes data flow analysis simpler because

A.the flow graph reduces to a single basic block
B.each use is reached by exactly one definition by construction
C.the program is left containing no branches at all once converted
D.every variable becomes a compile time constant

Answer: B

Renaming makes the reaching definition immediate rather than something to be computed. Phi functions at join points name the versions arriving along each incoming edge. Converting back out of the form inserts copies that later passes clean up.

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