You may know that static single assignment means one definition per name and still lose the question by counting only left-hand-side versions. Live-in variables, expression operations and control-flow leaders create different counting problems, so one shortcut cannot solve them all. Six different counts are in play: SSA versions, temporaries per operator, total names including live-ins, basic-block leaders, CFG edges and backpatch lists. Attempt each item before reading its explanation.
Keep two conventions separate. Temporary variables are fresh results needed while evaluating an expression. Total variables include those results or renamed definitions plus live-in names used on the right-hand side. Mixing the two is the usual way a mark goes missing here. The full topic module is SSA and control flow in intermediate code generation.
SSA and control flow MCQs: five question families and what to write first
Question family | What to write first | Questions here |
|---|---|---|
SSA renaming | Mark every definition and reaching use | Q1 |
Temporary-variable counting | Write one three-address instruction per operation | Q2-Q4 |
Total-variable counting | List live-ins and versioned definitions separately | Q5-Q8 |
Control-flow graph | Identify leaders, then blocks, then edges | Q9 |
Backpatching | Track unresolved true, false and next lists | Q10 |
In SSA, each name has one definition, not one use. A basic-block leader is the first instruction, a jump target, or an instruction following a jump. Backpatching records incomplete jump targets and fills them when the target address becomes known.
For mixed-topic practice, use Compiler Design MCQs. Broader preparation sits under GATE CS Exam Preparation Courses and Test Series.
Static single assignment form: rename every definition and its uses
Scan top to bottom. Give every definition a fresh version and update its reaching uses.
Question 1: choose the valid SSA renaming
GATE 2017, Set 1
Consider the following intermediate program in three address code
p = a - b
q = p * c
p = u * v
q = p + q
Which one of the following corresponds to a static single assignment form of the above code?A. p1 = a - b
q1 = p1 * c
p1 = u * v
q1 = p1 + q1
B. p3 = a - b
q4 = p3 * c
p4 = u * v
q5 = p4 + q4
C. p1 = a - b
q1 = p2 * c
p3 = u * v
q2 = p4 + q3
D. p1 = a - b
q1 = p * c
p2 = u * v
q2 = p + qAnswer: B. The definitions arrive as p3, q4, p4, q5, so the last use is q5=p4+q4. Subscripts may start anywhere; uniqueness and correct reaching uses make B valid.
Continue from the representation to optimization in Syntax-Directed Translation and Code Optimization.
SSA temporary-variable MCQs: count operations, not symbols
Apply precedence and emit one instruction per operation. Whether the final result gets its own temporary or writes the destination directly varies by question setter, so read each item's convention before counting.
Question 2: count temporaries for repeated products and subtractions
GATE 1999
The least number of temporary variables required to create a three-address code in static single assignment form for the expression a = b * d - c + b * e - c is ______A. 3
B. 4
C. 5
D. 6Answer: C, 5. This question uses the convention of creating a temporary for every operator result: t1=b*d, t2=t1-c, t3=b*e, t4=t2+t3, t5=t4-c, then a=t5. The five binary operations therefore give five temporaries. Under the different convention used in Question 4, the final subtraction could instead write directly to a, giving four temporaries, so check which convention a question is using before you count.
Question 3: count temporaries in a longer precedence chain
GATE 2015, Set 1
The least number of temporary variables required to create a three-address code in static single assignment form for the expression q + r / 3 + s - t * 5 + u * v / w is _______________.Answer: 8. For q+(r/3)+s-(t*5)+((u*v)/w), use t1=r/3, t2=t*5, t3=u*v, t4=t3/w, t5=q+t1, t6=t5+s, t7=t6-t2, t8=t7+t4. Eight operations require eight fresh results.
Question 4: count temporaries for the quadratic-form expression
The minimum number of temporary variables required to generate three-address code in SSA (Static Single Assignment) form for the following expression is:
-b + sqrt(b * b - 4 * a * c)
x = --------------------------------
2 * aAnswer: 7. This question uses the convention that the final operation writes directly to the destination: t1=b*b, t2=a*c, t3=4*t2, t4=t1-t3, t5=sqrt(t4), t6=t5-b, t7=2*a, then x=t6/t7. The expression has eight operator results, but the final division produces x, so only the preceding seven need temporary names. This differs from Question 2, whose setter counts a temporary for the final operator result as well.
SSA total-variable MCQs: add live-ins to versioned definitions
Use total SSA variables = distinct live-ins + assigned names. Reuse counts one live-in; each assignment creates a fresh name.
Question 5: total variables after repeated assignments to x and y
GATE 2016, Set 1
Consider the following code segment.
x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;
The minimum number of total variables required to convert the above code segment to static single assignment form is __________ .Answer: 10. Rename to x1=u-t, y1=x1*v, x2=y1+w, y2=t-z, y3=x2*y2. Five definitions plus live-ins u, t, v, w, z give 5+5=10; repeated t counts once.
Question 6: recognise the same total-variable trap in MCQ form
TPSC 2025, Senior Informatics Officer
Consider the following code segment :
x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;
The minimum number of total variables required to convert the above code segment to static single assignment form isA. 6
B. 8
C. 9
D. 10Answer: D, 10. The same program has definitions x1, x2, y1, y2, y3 and five live-ins. Options 6 and 8 miss several live-ins, while 9 omits one; there are five assignment versions, not six.
Question 7: count live-ins and four assigned results
Consider the intermediate code given below:
a = c + d
b = f * g
h = b * a
i = j + h
If the above code is converted into static single assignment, the minimum number of variables required is?Answer: 9. Rename as a1=c+d, b1=f*g, h1=b1*a1, i1=j+h1. Five live-ins {c, d, f, g, j} plus four definitions give 5+4=9.
Question 8: total SSA names for a nested arithmetic expression
Consider the following expression:
((a + b) * a) - ((b * c) + a)
Total minimum variables required for the above expression in SSA (static single assignment) form is?Answer: 8. With live-ins a1, b1, c1, write t1=a1+b1, t2=t1*a1, t3=b1*c1, t4=t3+a1, result=t2-t4. Three live-ins plus five definitions give 3+5=8, unlike a temporary-only count.
Control-flow graph MCQ: leaders, blocks, nodes and edges
Separate basic blocks from explicit Entry and Exit nodes before comparing options.
Question 9: count nodes and edges in a nested-loop CFG
GATE 2015
Consider the intermediate code given below:
1. i = 1
2. j = 1
3. t1 = 5 * i
4. t2 = t1 + j
5. t3 = 4 * t2
6. t4 = t3
7. a[t4] = -1
8. j = j + 1
9. if j <= 5 goto (3)
10. i = i + 1
11. if i < 5 goto (2)
The number of nodes and edges in the control-flow graph constructed for the above code, respectively, areA. 5 and 7
B. 6 and 7
C. 5 and 5
D. 7 and 8Answer: B, 6 nodes and 7 edges. Leaders 1, 2, 3, 10 form B1 = {1}, B2 = {2}, B3 = {3,4,5,6,7,8,9}, B4 = {10,11}; Entry and Exit make six nodes. The seven edges are Entry -> B1, B1 -> B2, B2 -> B3, B3 true -> B3, B3 false -> B4, B4 true -> B2, B4 false -> Exit.
Backpatching MCQ: one pass through unresolved jumps
truelist, falselist and nextlist hold jumps with blank targets. backpatch(list, target) fills them later.
Question 10: identify what backpatching can generate in one pass
GATE 2025
Consider the following statements about the use of backpatching in a compiler for intermediate code generation:
Backpatching can be used to generate code for Boolean expression in one pass
Backpatching can be used to generate code for flow-of-control statements in one pass
Which ONE of the following options is CORRECT?A. Only (I) is correct
B. Only (II) is correct
C. Both (I) and (II) are correct
D. Neither (I) nor (II) is correctAnswer: C. Boolean expressions emit unresolved jumps into true and false lists. if, if-else and loops also use true, false and next lists, patching targets when blocks begin, so both support one-pass generation.
SSA and control flow MCQs: the short answer pattern and next step
Pattern | Proof to write |
|---|---|
SSA renaming | Fresh name per definition; each use points to its reaching definition |
Temporary count | Fresh result per operation, such as 5 or 8 here |
Total-variable count | Live-ins plus versions, such as 10 here |
CFG count | Leaders, blocks and edges; state Entry and Exit for 6 nodes and 7 edges |
Backpatching | Record incomplete targets, then fill them when their addresses become known |
Cover the solutions, allow 90 seconds per counting item and 3 minutes for the CFG. Accept only a written three-address trace or edge list.
Next, attempt Parsing MCQs: 12 Solved GATE Questions and Answers. For the full concept-to-PYQ sequence, use GATE Guidance by Sanchit Sir. If you need only this topic, re-solve these ten questions without the explanations.
