Department of Computer Science and
Engineering
A Project Report on
PYTHON-LIKE SSA COMPILER
for the course CSL74: SKILL ENHANCEMENT LABORATORY
by
Pathan Irbaz 1MS22CS100
Pranshu Saraswat 1MS22CS105
Sharanya Sandeeep 1MS22CS131
Siddhanth Pradhan 1MS22CS142
Under the guidance of
Vishwachetan D
Assistant Professor
M S RAMAIAH INSTITUTE OF TECHNOLOGY
(Autonomous Institute, Affiliated to VTU)
BANGALORE-560054
[Link]
Sept – Dec 2025
ABSTRACT
This project implements a compiler pipeline that transforms a Python-like source language into Static
Single Assignment (SSA) form, a critical intermediate representation used in modern optimizing
compilers. The pipeline consists of three main stages: parsing the source code into an Abstract Syntax
Tree (AST), generating Three-Address Code (TAC) as an intermediate representation, and constructing
SSA form through control flow graph analysis, dominator computation, and $\phi$-function insertion.
The implementation demonstrates fundamental compiler construction techniques including lexical
analysis, syntax-directed translation, basic block identification, dominance frontier computation, and
variable renaming algorithms. The system successfully handles assignment statements, conditional
branches (if-else), and loop constructs (while), producing correct SSA output with properly placed
$\phi$-functions at control flow merge points.
1. Introduction
1.1 Background
Static Single Assignment (SSA) form is an intermediate representation (IR) used by compilers where each
variable is assigned exactly once and every variable is defined before it is used. This property simplifies
many compiler optimizations including constant propagation, dead code elimination, and register
allocation. Major production compilers such as LLVM, GCC, and the Java HotSpot VM utilize SSA form
as their primary IR.1.2 Problem Statement
Traditional intermediate representations allow multiple assignments to the same variable, making data
flow analysis complex and optimization algorithms difficult to implement efficiently. SSA form addresses
these challenges by ensuring each variable has a single static definition point, but constructing SSA
requires sophisticated algorithms for:
● Building control flow graphs from linear code
● Computing dominance relationships between basic blocks
● Identifying locations requiring $\phi$-functions
● Renaming variables to maintain the single-assignment property
1.3 Objectives
The primary objectives of this project are:
1. Design and implement a parser for a Python-like subset language supporting assignments,
conditionals, and loops
2. Develop a Three-Address Code generator that translates AST to linear IR
3. Implement the complete SSA construction algorithm including:
○ Basic block identification and CFG construction
○ Dominator and dominance frontier computation
○ $\phi$-function insertion using the dominance frontier algorithm
○ Variable renaming using the standard SSA renaming algorithm
1.4 Scope
The implementation supports:
● Assignment statements with arithmetic and comparison expressions
● Conditional statements (if-else constructs)
● Loop constructs (while loops)
● Operators: arithmetic (+, -, *, /), comparison (==, !=, <, >, <=, >=), and logical (and, or)
2. Methodology
2.1 System Architecture
The compiler pipeline consists of three main modules organized in a sequential transformation flow:
Source Code → Parser → AST → TAC Generator → TAC → SSA Builder → SSA Form
2.2 Parsing Module (parser_py.py)
The parser implements a recursive descent parser for Python-like syntax with indentation-based block
structure.2.2.1 AST Node Definitions
class Node: pass
class Assign(Node):
def __init__(self, lhs, expr):
[Link] = lhs
[Link] = expr
class If(Node):
def __init__(self, cond, then_body, else_body):
[Link] = cond
self.then_body = then_body
self.else_body = else_body
class While(Node):
def __init__(self, cond, body):
[Link] = cond
[Link] = body
2.2.2 Parsing Algorithm
The parser uses indentation levels to determine block boundaries:
● Tracks current indentation level (multiples of 4 spaces)
● Recursively parses nested blocks for control structures
● Returns when indentation decreases below expected level
2.3 Three-Address Code Generation (tac_generator.py)
2.3.1 Expression Translation
Expressions are translated using an operator-precedence parsing algorithm:
● Tokenization: Regular expressions extract identifiers, numbers, and operators
● Precedence handling: Operators are processed according to precedence table
● Temporary generation: Intermediate results stored in temporaries (t0, t1, ...)
prec = {
"or":1, "and":2,
"==":3, "!=":3,
"<":4, ">":4, "<=":4, ">=":4,
"+":5, "-":5,
"*":6, "/":6
}
2.3.2 Control Flow Translation
● If statements: Generate conditional branch (if_not ... goto), then-block, unconditional jump,
else-block, and end label
● While loops: Generate start label, condition check, loop body, back-edge jump, and exit label
2.4 SSA Construction (ssa_builder.py)
2.4.1 Basic Block Identification
Leaders (block entry points) are identified as:
1. First instruction of the program
2. Target of any jump instruction
3. Instruction immediately following a jump
2.4.2 Control Flow Graph Construction
def build_cfg(blocks, label_to_block):
succ = {b['id']: set() for b in blocks}
pred = {b['id']: set() for b in blocks}
# Analyze last instruction of each block
# Build successor/predecessor relationships
return succ, pred
2.4.3 Dominator Computation
Uses iterative data-flow analysis:
● Initialize: Dom(entry) = {entry}, Dom(n) = all nodes for n ≠ entry
● Iterate: Dom(n) = {n} $\cup$ ($\cap$ Dom(p) for p in predecessors(n))
● Continue until fixed point
2.4.4 Dominance Frontier Algorithm
The dominance frontier DF(n) contains nodes where n's dominance ends:
def compute_dominance_frontier(nodes, succ, pred, idom):
df = {n: set() for n in nodes}
for n in nodes:
if len(pred[n]) >= 2:
for p in pred[n]:
runner = p
while runner is not None and runner != idom[n]:
df[runner].add(n)
runner = idom[runner]
return df
2.4.5 $\phi$-Function Insertion
For each variable v:
1. Find all blocks where v is defined
2. Add $\phi$-function at each block in the dominance frontier
3. Recursively process newly added definitions
2.4.6 Variable Renaming
Uses a stack-based algorithm traversing the dominator tree:
1. Rename $\phi$-function left-hand sides
2. Rename uses and definitions in block instructions
3. Fill $\phi$-function arguments in successor blocks
4. Recursively process dominated blocks
5. Pop definitions when leaving block
3. Results and Discussion
3.1 Test Case Analysis
Input Program:
x=1
if x > 0:
y=2
else:
y=3
z=y
Generated Three-Address Code:
x=1
t0 = x > 0
if_not t0 goto L0
y=2
goto L1
L0:
y=3
L1:
z=y
Final SSA Form:
Block0:
x.1 = 1
t0.1 = x.1 > 0
if_not t0.1 goto L0
Block1:
y.1 = 2
goto L1
L0:
y.2 = 3
L1:
y.3 = phi(y.1, y.2)
z.1 = y.3
3.2 Analysis of Results
1. Correct $\phi$-function placement: The $\phi$-function for variable y is correctly placed at
block L1, which is the merge point where control flow from both branches converges.
2. Proper variable versioning: Each variable receives a unique version number (x.1, y.1, y.2, y.3,
z.1), satisfying the single-assignment property.
3. $\phi$-function arguments: The $\phi$-function y.3 = phi(y.1, y.2) correctly references the
definitions from both branches.
3.3 Performance Characteristics
Phase Time Complexity
Parsing
O(n) where n = source lines
TAC Generation O(n $\times$ m) where m = expression
complexity
Block Construction O(k) where k = TAC instructions
Dominator Computation O($n^2$ $\times$ e) where e = CFG edges
$\phi$-insertion O(v $\times$ d) where v = variables, d =
definitions
Renaming O(k) single pass over blocks
3.4 Limitations
1. No procedure support: The implementation handles single-function programs only
2. Limited type system: All variables treated as generic values
3. No optimization passes: SSA is generated but not optimized
4. Simple error handling: Parser assumes well-formed input
4. Conclusion
This project successfully implements a complete SSA construction pipeline for a Python-like
language subset. The implementation demonstrates:
1. Correct SSA semantics: Variables are assigned exactly once, with $\phi$-functions properly
placed at control flow merge points
2. Standard algorithms: The implementation follows established compiler construction algorithms
for dominator computation and SSA construction
3. Modular design: Clear separation between parsing, TAC generation, and SSA construction
enables independent testing and extension
4. Educational value: The code serves as a clear demonstration of SSA construction principles
suitable for compiler education
Future Work:
Potential extensions include:
● Support for function definitions and calls
● Array and pointer operations
● Optimization passes (constant propagation, dead code elimination)
● SSA destruction for code generation
● More sophisticated error reporting
5. Acknowledgements
We take this opportunity to express our gratitude to the people who have been instrumental in
the successful completion of this project. We would like to express our profound gratitude to the
Management and Dr. N.V.R Naidu Principal, M.S.R.I.T, Bengaluru for providing us with the
opportunity to explore our potential.
We extend our heartful gratitude to our beloved Dr R China Appala Naidu, Professor and HoD,
Dept of Computer Science and Engineering, for constant support and guidance.
We whole heartedly thank our Guide Vishwachetan D, Assistant Professor, Dept of Computer
Science and Engineering for providing us with the confidence and strength to overcome every
obstacle at each step of the project and inspiring us to the best of our potential. We also thank
our Guide for constant guidance, direction and insight during the project.
This work would not have been possible without the guidance and help of several individuals
who in one way or another contributed their valuable assistance in preparation and completion of
this study.
Finally, we would like to express sincere gratitude to all the teaching and non-teaching faculty
of CSE Department, our beloved parents, and my dear friends for their constant support during
the course of work.