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.

31.

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

32.

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

33.

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

34.

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

35.

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

36.

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

37.

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

38.

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

39.

Partial redundancy elimination generalises common subexpression elimination by

A.computing expressions before the program starts running
B.restricting attention to a single basic block at a time
C.removing a computation redundant on some but not all paths
D.removing a computation redundant on absolutely every path

Answer: C

Correct answer: removing a computation redundant on some but not all paths

Common subexpression elimination requires the expression to be available on every path, which fails if one branch computes it and another does not. Partial redundancy elimination inserts the computation on the paths lacking it, making it fully redundant at the join, and then removes it - and it subsumes loop invariant code motion as a special case.

Discuss in Forum

40.

Code motion that inserts a computation on a path where it was not previously performed is safe only if

A.the computation appears at least twice in the procedure
B.the target machine happens to have an idle functional unit available
C.the inserted computation is a compile time constant
D.the computation cannot raise an exception or have side effects

Answer: D

A division that would have been skipped must not be executed early if it might trap. Compilers therefore restrict speculative motion to operations that cannot fault. Hardware support for speculation relaxes the restriction on some machines.

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