Implement Static Single Assignment (SSA) Form

Topic Overview

SSA: One Assignment Per Variable

Static Single Assignment form gives each variable exactly one definition site, simplifying dataflow analysis. LLVM IR, GCC's SSA GIMPLE, and HotSpot's C1 IR all use SSA. The Cytron algorithm inserts phi-nodes at control-flow joins to merge values.

Converting to SSA

Rename each assignment to a fresh version: x becomes x1, x2. At join points after if/else, insert x3 = phi(x1, x2). Optimizations like constant propagation and dead code elimination become trivial on SSA.

cCopy
Loading…

• Phi-nodes go at dominance frontiers of definitions
• SSA enables sparse dataflow analyses
• Destruction phase lowers phi to copies before codegen
• Each SSA name has a single reaching definition

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will convert your IR to static single assignment form. This exercise asks you to rename variables and insert phi-nodes at merge points so each SSA name is assigned exactly once.

Your Task

Convert straight-line three-address code into Static Single Assignment form: every variable is assigned exactly once, so each definition gets a fresh versioned name and every use refers to the version that reaches it. (Merging values from different control-flow paths with φ-nodes comes later, in Add Phi-Nodes to Your SSA IR; here there are no jumps.)

Input

Straight-line TAC, one instruction per line (blank lines ignored):

cCopy
Loading…

Operands are integer literals or variable names.

Renaming rules

• Each variable has a version counter starting at 0. Every definition of x increments it and writes x_N.
• Every use of x becomes x_N for the current N. A variable used before any definition is an incoming value, x_0.
• In x = x + 1 the use is renamed before the definition: x_1 = x_0 + 1.
• Literals are unchanged.

Output

The renamed code, one instruction per line, then:

cCopy
Loading…

listing every variable that was defined, in order of its first definition, with its final version.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. A table from variable name to its current version.
2. Rename uses first, then create the definition's new version: per instruction, in program order.

Hidden tests cover long chains of redefinitions, incoming values used several times, return, and variables whose names end in digits (t1 becomes t1_1).