Liveness Analysis(Data flow analyses) MCQs
Liveness Analysis(Data flow analyses) MCQs
1.
Liveness analysis determines:
A) Which variables hold constant values
B) Which variables are used before definition
C) Which variables may be needed in the future
D) Which variables can be replaced by constants
✅ Answer: C) Which variables may be needed in the future
Solution:
A variable is live at a program point if its value may be used later before being redefined.
2.
Liveness analysis is a:
A) Forward data flow analysis
B) Backward data flow analysis
C) Bidirectional analysis
D) None
✅ Answer: B) Backward data flow analysis
Solution:
It proceeds backward from program exits because liveness depends on future uses.
3.
In liveness analysis, “use” and “def” sets are computed for:
A) Each basic block
B) Each instruction
C) Entire program only
D) Function parameters
✅ Answer: A) Each basic block
Solution:
Liveness is first computed per basic block and then propagated across the control flow graph (CFG).
4.
A variable becomes dead when:
A) It’s defined again before use
B) It’s used before definition
C) It’s declared globally
D) It’s initialized to zero
✅ Answer: A) It’s defined again before use
Solution:
Redefinition kills the previous value, marking it dead.
5.
Liveness analysis primarily supports:
A) Register allocation
B) Syntax analysis
C) Loop unrolling
D) Dead code insertion
✅ Answer: A) Register allocation
Solution:
It identifies simultaneously live variables to optimize register usage.
6.
In a flow graph, the data flow equation for liveness is:
A) OUT[n] = ⋃ succ(IN[s])
B) IN[n] = USE[n] ∪ (OUT[n] – DEF[n])
C) OUT[n] = DEF[n] – USE[n]
D) IN[n] = DEF[n] ∪ USE[n]
✅ Answer: B) IN[n] = USE[n] ∪ (OUT[n] – DEF[n])
Solution:
The standard liveness equation for backward data flow analysis.
7.
Which lattice structure is used in liveness analysis?
A) Powerset lattice
B) Interval lattice
C) Boolean lattice
D) Product lattice
✅ Answer: A) Powerset lattice
Solution:
It uses sets of variables ordered by subset relation.
8.
The boundary condition for liveness analysis at the exit node is:
A) IN = ∅
B) OUT = ∅
C) IN = DEF
D) OUT = USE
✅ Answer: B) OUT = ∅
Solution:
No variable is live beyond the program exit.
9.
Which variable is not live at the end of a statement?
x = y + z;A) x
B) y
C) z
D) All are live
✅ Answer: A) x
Solution:x is just defined, not yet used — thus not live immediately after assignment.
10.
For instruction a = b + c, which set contains b and c?
A) DEF
B) USE
C) OUT
D) IN
✅ Answer: B) USE
Solution:
They are read to compute the new value of a.
11.
Liveness analysis proceeds until:
A) Convergence of IN/OUT sets
B) One iteration completes
C) All variables become dead
D) All loops are unrolled
✅ Answer: A) Convergence of IN/OUT sets
Solution:
The analysis iterates until data flow values stop changing.
12.
Consider:
1: a = 2
2: b = a + 3
3: print(b)At line 2, which variable is live before the statement?
A) a
B) b
C) None
D) Both
✅ Answer: A) a
Solution:a is used in line 2, so it must be live before it.
13.
Liveness analysis helps construct:
A) Interference graph
B) Syntax tree
C) Call graph
D) Symbol table
✅ Answer: A) Interference graph
Solution:
Used in register allocation — edges show variables live at same time.
14.
If a variable is live on multiple paths, it remains live:
A) If live on any path
B) Only if live on all paths
C) Only in loops
D) Never
✅ Answer: A) If live on any path
Solution:
Union operation (join) combines liveness from all successors.
15.
Liveness analysis belongs to:
A) Static analysis
B) Dynamic analysis
C) Profiling
D) Parsing
✅ Answer: A) Static analysis
Solution:
Performed without executing the program.
16.
For x = y + z, which variable kills liveness of others?
A) x
B) y
C) z
D) None
✅ Answer: A) x
Solution:
Redefinition of x kills its previous live value.
17.
If a loop body modifies a variable not used later, that variable is:
A) Dead after loop
B) Live forever
C) Constant
D) None
✅ Answer: A) Dead after loop
Solution:
No further use makes it dead post-loop.
18.
Which of the following optimizations relies heavily on liveness info?
A) Dead code elimination
B) Loop unrolling
C) Constant folding
D) Strength reduction
✅ Answer: A) Dead code elimination
Solution:
If a value isn’t live after assignment, its computation can be removed.
19.
In the equation IN[n] = USE[n] ∪ (OUT[n] – DEF[n]),
the operator “–” denotes:
A) Set difference
B) Complement
C) Union
D) Intersection
✅ Answer: A) Set difference
Solution:
Variables defined (DEF) kill their previous liveness from OUT.
20.
If OUT[B1] = {a,b}, DEF[B1] = {b}, USE[B1] = {c}, then
IN[B1] = ?
A) {a,b,c}
B) {a,c}
C) {b,c}
D) {a,b}
✅ Answer: B) {a,c}
Solution:
IN = USE ∪ (OUT – DEF) = {c} ∪ ({a,b} – {b}) = {a,c}.
21.
When two variables interfere in register allocation?
A) When both are live simultaneously
B) When both are dead simultaneously
C) When defined together
D) When constant
✅ Answer: A) When both are live simultaneously
Solution:
They cannot share the same register.
22.
The fix-point iteration for liveness may require multiple passes because:
A) Loops create cyclic dependencies
B) Recursion is not allowed
C) Compiler phases interfere
D) Symbol table changes
✅ Answer: A) Loops create cyclic dependencies
Solution:
Loop back edges require repeated analysis until stabilization.
23.
Which graph property does liveness depend on?
A) Successor relationships
B) Predecessor relationships
C) Both
D) Neither
✅ Answer: A) Successor relationships
Solution:
Liveness flows backward from successors to predecessors.
24.
If instruction 5 uses variable x, then x is live:
A) Just before instruction 5
B) After instruction 5
C) Only at function start
D) Never
✅ Answer: A) Just before instruction 5
Solution:
Liveness indicates value needed before a use.
25.
Which of the following is not affected by liveness?
A) Register allocation
B) Dead code removal
C) Constant propagation
D) Loop unrolling
✅ Answer: D) Loop unrolling
Solution:
Loop unrolling is a control-flow optimization, independent of variable liveness.
26.
In backward data flow analysis, the initial OUT set at exit nodes is:
A) Empty set
B) All variables live
C) USE set
D) DEF set
✅ Answer: A) Empty set
Solution:
No variable is live beyond program exit, so OUT = ∅.
27.
Which of the following is true for live variables in loops?
A) Variables used inside a loop are always live outside
B) Variables defined but never used inside a loop are dead outside
C) Variables in loops cannot be analyzed
D) Liveness is ignored inside loops
✅ Answer: B) Variables defined but never used inside a loop are dead outside
Solution:
Variables not used beyond their definition in a loop are dead after the loop.
28.
Which set operation is used at control flow merges in liveness analysis?
A) Intersection
B) Union
C) Difference
D) Symmetric difference
✅ Answer: B) Union
Solution:
A variable is live if it is live on any successor path.
29.
If x is live at the end of a block and defined inside the block but never used, then:
A) It is still considered live
B) It becomes dead
C) It propagates as constant
D) None
✅ Answer: B) It becomes dead
Solution:
Redefinition kills previous liveness, and unused variables are dead.
30.
Liveness analysis helps prevent:
A) Register spilling
B) Memory leaks
C) Deadlocks
D) Parsing errors
✅ Answer: A) Register spilling
Solution:
By knowing which variables are live simultaneously, register allocation can be optimized.
31.
Which type of compiler optimization is closely tied with liveness?
A) Peephole optimization
B) Global optimization
C) Syntax optimization
D) Parsing optimization
✅ Answer: B) Global optimization
Solution:
Liveness is computed over the entire CFG, making it a global optimization.
32.
The iterative process in liveness analysis guarantees termination because:
A) The lattice height is finite
B) Loops are finite
C) Variables are constants
D) CFG has no cycles
✅ Answer: A) The lattice height is finite
Solution:
The powerset lattice over finite variables ensures fixpoint convergence.
33.
If x is never used after being defined, the compiler can:
A) Remove the assignment
B) Keep it for safety
C) Substitute constant
D) Inline it
✅ Answer: A) Remove the assignment
Solution:
Dead assignments can be eliminated safely.
34.
At what granularity can liveness analysis be applied?
A) Instruction level
B) Basic block level
C) Function level
D) All of the above
✅ Answer: D) All of the above
Solution:
It can be computed per instruction, block, or globally for optimizations.
35.
In x = y + z; print(x);, variable y is live:
A) Before instruction
B) After instruction
C) Never
D) Only inside a loop
✅ Answer: A) Before instruction
Solution:y is used to compute x, so it must be live prior to usage.
36.
Which of the following may increase the number of live variables?
A) Loop headers
B) Function calls
C) Variable redefinitions
D) Conditional branches
✅ Answer: D) Conditional branches
Solution:
Different paths may use different variables, increasing live variable set at joins.
37.
Liveness information is essential for which type of graph?
A) Interference graph
B) Control dependency graph
C) Syntax tree
D) Call graph
✅ Answer: A) Interference graph
Solution:
It shows variables that cannot share registers because they are live simultaneously.
38.
Which of the following instructions kills the liveness of a variable?
A) Variable redefinition
B) Variable use
C) Variable read
D) None
✅ Answer: A) Variable redefinition
Solution:
A new definition overwrites the old value, making previous value dead.
39.
At the merge of multiple paths, liveness is computed using:
A) Intersection of IN sets
B) Union of OUT sets
C) Difference of DEF sets
D) Sum of USE sets
✅ Answer: B) Union of OUT sets
Solution:
If a variable is live on any path, it must be considered live at merge.
40.
Which of the following is true for dead code elimination using liveness?
A) Only instructions assigning to dead variables can be removed
B) All instructions can be removed
C) Liveness does not help
D) Only loops can be removed
✅ Answer: A) Only instructions assigning to dead variables can be removed
Solution:
Safe removal requires that the value is never used later.
41.
If x = y + z and x is never used, then:
A) Instruction is dead
B) y and z become dead
C) Instruction is live
D) All variables become constants
✅ Answer: A) Instruction is dead
Solution:
The computation of x has no effect if x is never used.
42.
Which type of analysis does liveness belong to?
A) Must analysis
B) May analysis
C) Either
D) None
✅ Answer: B) May analysis
Solution:
A variable may be live on any path, making it a may analysis.
43.
If a variable is live at entry of a block but never used in it, it is:
A) Live throughout block
B) Dead immediately
C) Constant
D) Undefined
✅ Answer: A) Live throughout block
Solution:
Liveness is backward propagated; variable is needed later, so it remains live.
44.
Which of the following can be computed from liveness?
A) Interference graph
B) Constant propagation opportunities
C) Loop bounds
D) Function inlining
✅ Answer: A) Interference graph
Solution:
Live variable sets at each point define edges in the interference graph.
45.
If a variable is redefined in all successor blocks, liveness:
A) Killed
B) Preserved
C) Constant
D) Ignored
✅ Answer: A) Killed
Solution:
New definitions prevent old value propagation.
46.
Liveness of variables is particularly important in:
A) Register-constrained architectures
B) Memory abundant architectures
C) High-level languages only
D) Linkers
✅ Answer: A) Register-constrained architectures
Solution:
Efficient register allocation depends on accurate liveness info.
47.
Which algorithm is typically used for liveness?
A) Iterative backward analysis
B) Recursive descent
C) Topological sort
D) Greedy allocation
✅ Answer: A) Iterative backward analysis
Solution:
Repeated iterations are needed until IN/OUT sets stabilize.
48.
The OUT set for a block is:
A) Union of IN sets of successors
B) Intersection of IN sets of successors
C) Equal to IN set
D) Equal to USE set
✅ Answer: A) Union of IN sets of successors
Solution:
A variable is live if live in any successor block.
49.
Which of the following statements is true about liveness analysis?
A) Forward analysis
B) Backward analysis
C) Both
D) Neither
✅ Answer: B) Backward analysis
Solution:
It flows information from uses back to definitions.
50.
A variable that is live at a loop header may be:
A) Live throughout loop
B) Dead immediately
C) Constant
D) Unused
✅ Answer: A) Live throughout loop
Solution:
If needed inside the loop, it remains live until last use.
51.
Which of the following variables is live at function exit?
A) Variables used after function returns
B) Variables not used later
C) Variables only used inside function
D) None
✅ Answer: D) None
Solution:
No local variable is live beyond function exit.
52.
Liveness analysis and reaching definitions are:
A) Forward and backward analysis respectively
B) Both forward
C) Both backward
D) Unrelated
✅ Answer: A) Forward and backward analysis respectively
Solution:
Reaching definitions: forward; liveness: backward.
53.
Which type of variables are never live?
A) Variables never used after assignment
B) Variables used once
C) Global variables
D) Loop counters
✅ Answer: A) Variables never used after assignment
Solution:
No future use implies dead variables.
54.
The purpose of the IN set in liveness is to:
A) Identify variables live at block entry
B) Identify variables used at block exit
C) Identify constants
D) Identify dead code
✅ Answer: A) Identify variables live at block entry
Solution:
IN = USE ∪ (OUT – DEF), representing variables needed at block start.
55.
Which of the following is not directly impacted by liveness?
A) Register allocation
B) Dead code elimination
C) Syntax tree construction
D) Interference graph
✅ Answer: C) Syntax tree construction
Solution:
Liveness is a data flow optimization, not a parsing concern.
56.
For x = y + z, y is live if:
A) y is used later
B) y is redefined immediately
C) y is dead
D) None
✅ Answer: A) y is used later
Solution:
Variable must be live if its value is needed in future computation.
57.
Union operator in liveness analysis corresponds to:
A) May analysis
B) Must analysis
C) Both
D) Neither
✅ Answer: A) May analysis
Solution:
Variable is live if it may be used in any successor.
58.
The OUT set of a basic block is:
A) IN of its successors
B) DEF of block
C) USE of block
D) All variables
✅ Answer: A) IN of its successors
Solution:
Liveness flows backward from successors to current block.
59.
Variable a is live at point P if:
A) There is a path from P to a use of a without redefining it
B) a is defined at P
C) a is constant
D) a is global
✅ Answer: A) There is a path from P to a use of a without redefining it
Solution:
By definition of liveness.
60.
Which property guarantees termination of liveness analysis?
A) Finite variable set
B) Infinite loops
C) Dynamic allocation
D) Recursion
✅ Answer: A) Finite variable set
Solution:
Finite number of variables → powerset lattice → fixpoint reached.
61.
A variable defined and used in the same instruction is:
A) Live only before use
B) Live after definition
C) Dead immediately
D) Constant
✅ Answer: A) Live only before use
Solution:
Liveness considers variables needed before use in backward analysis.
62.
Which of the following is an example of dead code?
x = 5;
y = x + 2;If y is never used.
A) y = x + 2
B) x = 5
C) Both
D) None
✅ Answer: A) y = x + 2
Solution:y is never used, making the assignment dead.
63.
In SSA form, liveness analysis:
A) Uses phi nodes for merging
B) Ignores loops
C) Treats all variables live
D) Works only globally
✅ Answer: A) Uses phi nodes for merging
Solution:
Phi nodes merge live variables across control paths in SSA.
64.
A variable is live at the end of a loop if:
A) Used after loop
B) Defined but unused
C) Constant
D) Not modified
✅ Answer: A) Used after loop
Solution:
Future use determines liveness at loop exit.
65.
Which scenario increases number of live variables?
A) Multiple successors
B) Single path
C) Constant-only block
D) Empty block
✅ Answer: A) Multiple successors
Solution:
Union of successor IN sets may increase live variable set.
66.
For x = 10; y = x + 5; print(y); at x = 10, which variable is live?
A) x
B) y
C) Both
D) None
✅ Answer: A) x
Solution:
x is used to compute y → live before assignment.
67.
At a
basic block exit, OUT contains:
A) Variables needed in successors
B) Variables defined in block
C) Variables used in block
D) Constants
✅ Answer: A) Variables needed in successors
Solution:
Liveness flows backward from successors to determine needed variables.
68.
Which operator is used to combine liveness from multiple successors?
A) Union
B) Intersection
C) Difference
D) Symmetric difference
✅ Answer: A) Union
Solution:
Variable live on any successor is considered live.
69.
The “use” set of a block contains:
A) Variables read before defined in the block
B) Variables defined in the block
C) Variables killed in block
D) Variables live at exit
✅ Answer: A) Variables read before defined in the block
Solution:
This ensures correct backward propagation.
70.
The “def” set of a block contains:
A) Variables assigned values in the block
B) Variables used in the block
C) Variables live at exit
D) Constants
✅ Answer: A) Variables assigned values in the block
Solution:
Definitions kill prior liveness of those variables.
71.
Which property of liveness makes register allocation feasible?
A) Identifying live ranges
B) Identifying constants
C) Identifying loops
D) Identifying unreachable code
✅ Answer: A) Identifying live ranges
Solution:
Variables simultaneously live cannot share a register.
72.
Liveness analysis is essential for:
A) Dead code elimination
B) Constant propagation
C) Loop fusion
D) Inline expansion
✅ Answer: A) Dead code elimination
Solution:
Dead assignments can only be safely removed if variable is dead after definition.
73.
If a variable is live at a program point and never used later, what happened?
A) Analysis error
B) Redundant assignment
C) Variable constant
D) None
✅ Answer: B) Redundant assignment
Solution:
Dead code exists due to unused assignment.
74.
Liveness information is computed:
A) Backward over CFG
B) Forward over CFG
C) Both directions
D) Randomly
✅ Answer: A) Backward over CFG
Solution:
Variables needed in the future → backward propagation.
75.
A variable is live if:
A) Its value may be read in the future
B) Its value is written
C) Its value is constant
D) Its value is global
✅ Answer: A) Its value may be read in the future
Solution:
Definition of liveness.
76.
During iterative computation, convergence occurs when:
A) IN/OUT sets stop changing
B) Loops end
C) Registers assigned
D) CFG reduced
✅ Answer: A) IN/OUT sets stop changing
Solution:
Fixpoint iteration ensures stability of live variable sets.
77.
Which type of variables are never considered live?
A) Dead assignments
B) Used once
C) Constants
D) Global variables
✅ Answer: A) Dead assignments
Solution:
No future use → never live.
78.
Which analysis complements liveness for optimization?
A) Reaching definitions
B) Constant propagation
C) Loop unrolling
D) Both A and B
✅ Answer: D) Both A and B
Solution:
They together enable various global optimizations.
79.
In a = b + c; b = 5; print(a); at b = 5, which variables are live?
A) a
B) b
C) c
D) a and c
✅ Answer: D) a and c
Solution:a is used in print; c contributes to a’s value. b is redefined → not live.
80.
Which set is updated first in iterative liveness?
A) OUT
B) IN
C) USE
D) DEF
✅ Answer: A) OUT
Solution:
OUT is computed from successor IN sets; then IN is updated.
81.
Liveness analysis can be used to detect:
A) Dead code
B) Infinite loops
C) Stack overflows
D) Type errors
✅ Answer: A) Dead code
Solution:
Variables never used → corresponding instructions are dead.
82.
The IN set is:
A) Variables live at block entry
B) Variables live at block exit
C) Variables defined in block
D) Constants
✅ Answer: A) Variables live at block entry
Solution:
Standard backward analysis formula: IN = USE ∪ (OUT – DEF).
83.
Which of the following increases live variable count at merges?
A) Multiple successor paths with different live variables
B) Single path
C) Empty block
D) Constant-only block
✅ Answer: A) Multiple successor paths with different live variables
Solution:
Union of successors’ IN sets increases the live set.
84.
In the backward analysis equation IN = USE ∪ (OUT – DEF), the DEF set:
A) Kills liveness
B) Adds liveness
C) Does nothing
D) Propagates constants
✅ Answer: A) Kills liveness
Solution:
Definition removes prior value’s liveness.
85.
Variables live across basic blocks are:
A) Global variables
B) Live-in and live-out variables
C) Constants
D) Loop counters
✅ Answer: B) Live-in and live-out variables
Solution:
They connect liveness across block boundaries.
86.
Which type of analysis is liveness?
A) May analysis
B) Must analysis
C) Either
D) None
✅ Answer: A) May analysis
Solution:
If live on any path → variable considered live.
87.
Liveness analysis requires which control flow info?
A) Successor blocks
B) Predecessor blocks
C) Both
D) None
✅ Answer: A) Successor blocks
Solution:
Backward propagation uses successors to determine current liveness.
88.
For x = y + z;, what happens if x is never used later?
A) Instruction dead
B) Instruction live
C) Variable constant
D) None
✅ Answer: A) Instruction dead
Solution:
Dead code removal possible if no future use.
89.
Liveness analysis uses which type of equation?
A) Set-based equation
B) Arithmetic equation
C) Linear equation
D) Boolean equation
✅ Answer: A) Set-based equation
Solution:
IN and OUT are sets of variables.
90.
The OUT set of block B is:
A) Union of IN sets of successors
B) Intersection of IN sets of successors
C) DEF of B
D) USE of B
✅ Answer: A) Union of IN sets of successors
Solution:
Live on any successor → live at block exit.
91.
Variables live simultaneously create:
A) Interference edges
B) Constant propagation opportunities
C) Loop invariants
D) Dead code
✅ Answer: A) Interference edges
Solution:
Graph-based register allocation uses live overlaps.
92.
A variable not live at exit but live inside block is:
A) Live locally only
B) Live globally
C) Constant
D) Dead
✅ Answer: A) Live locally only
Solution:
Does not propagate to successors.
93.
Union operator is used in liveness because:
A) May analysis
B) Must analysis
C) Both
D) None
✅ Answer: A) May analysis
Solution:
If live on any path → live.
94.
Dead code elimination requires:
A) Liveness info
B) Syntax tree
C) Constants
D) Loop counts
✅ Answer: A) Liveness info
Solution:
Used to identify instructions with no future uses.
95.
Which variable is live at entry if used in a successor block?
A) Yes
B) No
C) Only if constant
D) None
✅ Answer: A) Yes
Solution:
Backward propagation → needed variables marked live.
96.
A variable live in multiple blocks indicates:
A) Requires register allocation consideration
B) Dead code
C) Constant
D) Loop invariant
✅ Answer: A) Requires register allocation consideration
Solution:
Simultaneously live variables cannot share the same register.
97.
Which operation reduces live variable set?
A) Variable definition
B) Variable use
C) Constant propagation
D) None
✅ Answer: A) Variable definition
Solution:
Kills previous value → reduces liveness.
98.
Which of the following sets is always subset of OUT?
A) IN
B) USE
C) DEF
D) All
✅ Answer: A) IN
Solution:
IN = USE ∪ (OUT – DEF) ⊆ OUT ∪ USE → IN ⊆ OUT ∪ USE.
99.
The fixpoint iteration in liveness analysis is:
A) Guaranteed to converge
B) May not converge
C) Random
D) Infinite
✅ Answer: A) Guaranteed to converge
Solution:
Finite lattice ensures fixpoint.
100.
Liveness analysis is essential for:
A) Efficient register allocation
B) Dead code elimination
C) Both
D) None
✅ Answer: C) Both
Solution:
Identifies variables’ live ranges and dead assignments.