Static single assignment (SSA) form; counting variables and temporaries

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• In jumping code for B₁ || B₂, where does B₁’s true exit go? from Lesson 4.2.3
• How many instructions does x = (a + b) * (c − d) + e need in TAC? from Lesson 4.2.1
• Is the attribute computed by E.val = E₁.val + T.val synthesized or inherited? from Lesson 3.1

1 · The Story

📖

Never overwrite

Ishaan, who will tidy the draft later, keeps getting confused: “price” means one value on card 3 and another on card 9, because the speech updates the price. He asks Dev to never overwrite a name. Every time a name gets a new value, Dev stamps a new version: price₁, price₂, ….

A problem appears at the end of a detour. The draft says “if the monsoon is good, price₁ = 50, otherwise price₂ = 60; then announce price”. Which version is announced? Dev adds a special card where the two paths join: price₃ = “price₁ if we came from the first path, price₂ if from the second”.

2 · Predict First

🤔

In SSA form, how many distinct names appear in p = a + b; q = p − c; p = q * d; p = e − p; q = p + q? Write your guess down. The answer is in the vault.

3 · Core Concept

Definition

A program is in static single-assignment (SSA) form if every variable is assigned in exactly one place in the program text. Each assignment to x creates a new version x₁, x₂, …; every use refers to the version that reaches it.

“Static”: one assignment in the text, even if a loop executes it many times.

Straight-line code

Rename left to right: each assignment gets the next version of its target; each use gets the current version. Variables that are only read keep their original names (or version 0).

φ-functions

Where control paths join and different versions of x reach, SSA inserts a φ-function: x₃ = φ(x₁, x₂), which takes the version from the path that was actually taken. φ-functions are placed at join points (in loops, at the loop header).

if (flag) x = -1;         if (flag) x1 = -1;
else      x = 1;          else      x2 = 1;
y = x * a;                x3 = φ(x1, x2);
                          y1 = x3 * a;

Why SSA

Each name has exactly one definition, so the optimizer can see immediately where a value comes from and whether two names hold the same value. Many modern compilers (GCC, LLVM) use SSA as their main IR.

Story → compiler term

4 · Visual

Renaming straight-line code (computed).

A φ-function at the join point picks x1 or x2 depending on the path taken.

5 · Worked Examples

Example 1 Easy

Convert to SSA: p = a + b; q = p − c; p = q * d; p = e − p; q = p + q.

Solution

p1 = a + b
q1 = p1 - c
p2 = q1 * d
p3 = e - p2
q2 = p3 + q1

Every use takes the latest version: in p₃ = e − p₂ and q₂ = p₃ + q₁. Total distinct names: 10. Dev’s version stamps make each card’s inputs unambiguous.

Example 2 Medium

Convert to SSA and count all variables: x = a + b; y = x * c; x = y − a; y = x + y; z = x * y.

Solution

x1 = a + b
y1 = x1 * c
x2 = y1 - a
y2 = x2 + y1
z1 = x2 * y2

Names: a, b, c, x₁, y₁, x₂, y₂, z₁ → 8.

Example 3 GATE

Where must a φ-function be placed for x in: if (flag) x = −1; else x = 1; y = x * a;? How many versions of x exist?

Solution

At the join point before y = x * a: x₃ = φ(x₁, x₂). Three versions: x₁ (then), x₂ (else), x₃ (φ). Without the φ, the use of x after the join would not know which definition reaches it.

6 · Shortcuts

⚡

Count SSA names = number of assignments (each creates one new version) + variables that are only used (never assigned). Valid when: straight-line code without φ-functions.

⚡

φ needed at a join if two different definitions of x reach it along different paths. Valid when: placing φ-functions in small if/else or loop examples.

7 · GATE Traps

⚠️

• SSA is about the program text: a loop body assignment is still one assignment.
• Every use must refer to the version that reaches it (the latest one in straight-line code).
• φ-functions are not real instructions; they are removed (turned into copies) before code generation.
• Variables that are only read keep one name; do not number them.
• Count questions: check whether the original variable names (a, b, …) are to be counted.

8 · Memory Hook

🧠

SSA: one name, one birth. Where paths join, φ picks the right parent.

9 · Connect the Dots

The draft now has unique names, but it is still one long list. The next lesson cuts it into straight-line chunks and draws the map of which chunk can follow which: the structure every optimization works on.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksSSA count

How many distinct variable names appear in the SSA form of t = a * b; a = t + c; t = a * a; b = t − a?

Numerical answer: ________

Q2MCQ1 markDefinition

In SSA form:

• (A) every variable is used once
• (B) every variable is assigned exactly once in the program text
• (C) every variable is assigned once per execution
• (D) there are no temporaries

Q3MCQ1 markφ

A φ-function is placed:

• (A) at every assignment
• (B) at a join point where different versions of a variable arrive
• (C) at the start of the program
• (D) after every use

Q4NAT1 markSSA count

In the SSA form of x = a + b; y = x * c; x = y − a; y = x + y; z = x * y, how many versions of x and y together exist?

Numerical answer: ________

Q5MSQ1 markFacts

Which are true?

• (A) SSA makes each use’s definition explicit.
• (B) φ-functions are executed as machine instructions.
• (C) A loop header may need φ-functions.
• (D) Renaming straight-line code needs no φ-functions.

11 · Rule Card

• SSA: each variable assigned once in the text; versions x₁, x₂, ….
• Straight-line: rename targets in order; uses take the latest version.
• Joins: x₃ = φ(x₁, x₂) picks by incoming path; loop headers too.
• Count = assignments + read-only variables.

12 · Concept Ledger

static single assignment (SSA)version (x₁, x₂)φ-functionjoin point

13 · Answer Vault