OptiC-Optimizing-SSA-Compiler

OptiC is a high-performance optimizing compiler and virtual execution pipeline written in modern C++17, configured with CMake, featuring an SSA construction pass (Cytron's mem2reg), dominator tree CFG analysis, an SSA IR verifier, a fixed-point optimization pipeline (Constant Folding, Dead Code Elimination, CFG Branch Folding & Dead Block Removal), and dual AST/IR interpreters for automated differential verification.

---

1. Language Grammar

The source language, Mini, is a statically typed (integer only), block-scoped imperative programming language.

Program         ::= Statement* EOF

Statement       ::= VarDeclStmt
                  | AssignStmt
                  | IfStmt
                  | WhileStmt
                  | ReturnStmt
                  | PrintStmt
                  | BlockStmt
                  | ExprStmt
                  | ';'

VarDeclStmt     ::= 'let' IDENTIFIER ('=' Expression)? ';'
AssignStmt      ::= IDENTIFIER '=' Expression ';'
IfStmt          ::= 'if' '(' Expression ')' Statement ('else' Statement)?
WhileStmt       ::= 'while' '(' Expression ')' Statement
ReturnStmt      ::= 'return' Expression? ';'
PrintStmt       ::= 'print' ('(' Expression ')' | Expression) ';'
BlockStmt       ::= '{' Statement* '}'
ExprStmt        ::= Expression ';'

Expression      ::= LogicalOr
LogicalOr       ::= LogicalAnd ( '||' LogicalAnd )*
LogicalAnd      ::= Equality ( '&&' Equality )*
Equality        ::= Relational ( ( '==' | '!=' ) Relational )*
Relational      ::= Additive ( ( '<' | '<=' | '>' | '>=' ) Additive )*
Additive        ::= Multiplicative ( ( '+' | '-' ) Multiplicative )*
Multiplicative  ::= Unary ( ( '*' | '/' | '%' ) Unary )*
Unary           ::= ( '-' | '!' | '+' ) Unary | Primary
Primary         ::= NUMBER | IDENTIFIER | '(' Expression ')'

Operators & Precedence

From lowest to highest precedence:

1. || (Logical OR, short-circuiting)
2. && (Logical AND, short-circuiting)
3. ==, != (Equality)
4. <, <=, >, >= (Relational)
5. +, - (Additive)
6. *, /, % (Multiplicative)
7. -, !, + (Unary negation, logical NOT)

Semantic Rules

• Type System: int (64-bit signed integer).
• Truthiness: 0 is false; any non-zero value is true. Relational and logical expressions evaluate to 1 (true) or 0 (false).
• Scoping: Lexical block scoping { ... }. Variable declarations are scoped to their enclosing block.
• Shadowing: Shadowing variables defined in an outer scope is permitted; redeclaring the same variable within the exact same block scope is an error.
• Undefined Variables: Using an identifier before its declaration within reachable scopes is a compile-time semantic error.

---

2. Architecture Diagram

Source Code (.mini)
        │
        ▼
   [ Lexer ]  ──► Token Stream (line & column tracking)
        │
        ▼
   [ Parser ] ──► AST (Recursive Descent + Pratt Precedence Climbing)
        │
        ▼
 [ Semantic Checker ] ──► Scoped Symbol Resolution & Type Checking
        │
        ▼
 [ AST-to-IR Lowering ] ──► Three-Address Memory-Slot IR (alloca/load/store)
        │
   ┌────┴────────────────────────┐
   ▼                             ▼
[ AST Interpreter ]      [ IR Lowered Code ]
 (Ground Truth)                  │
                                 ▼
                     [ CFG Reachability & Pruning ]
                                 │
                                 ▼
                    [ Dominator Tree & Frontiers ]
                                 │
                                 ▼
                     [ SSA Mem2Reg (Cytron et al.) ] ──► Verified SSA IR
                                 │
                                 ▼
                     [ Fixed-Point Pass Manager ]
                       ├── Constant Folding & Algebraic Identities
                       ├── Dead Code Elimination (DCE)
                       └── CFG Simplification (Branch Folding & Dead Blocks)
                                 │
                                 ▼
                     [ IR Verifier ] (Dominance, SSA Single Def, Phi Consistency)
                                 │
                                 ▼
                     [ IR Interpreter ]
                                 │
                                 ▼
                     [ Differential Testing Engine ] (AST vs IR Output Match)

---

3. Before/After Optimization Examples

1. SSA Construction (Mem2Reg)

Promotes memory slots (alloca/load/store) into pure SSA virtual registers and places $\phi$ nodes using Iterated Dominance Frontiers ($IDF$).

• Before (Unoptimized Memory IR):

  entry_0:
    %slot_x = alloca
    store 10, %slot_x
    %t0 = load %slot_x
    print %t0
    ret 0

• After (Mem2Reg):

  entry_0:
    print 10
    ret 0

---

2. Constant Folding & Algebraic Simplification

Evaluates compile-time constant arithmetic, boolean logic, and algebraic identities ($x + 0 \rightarrow x$, $x \times 1 \rightarrow x$, $x \times 0 \rightarrow 0$, strength reduction $x \times 2 \rightarrow x + x$).

• Before:

  %t0 = add 10, 20
  %t1 = mul %t0, 3
  %t2 = mul %t1, 1
  %t3 = add %t2, 0
  print %t3

• After:

  print 90

---

3. Dead Code Elimination (DCE)

Removes all non-side-effecting instructions whose results are never read.

• Before:

  %unused1 = add 100, 200
  %unused2 = mul %unused1, 5
  print 42
  ret 42

• After:

  print 42
  ret 42

---

4. CFG Simplification

Folds constant branches (br 1 -> jmp trueTarget, br 0 -> jmp falseTarget) and removes unreachable basic blocks.

• Before:

  entry_0:
    br 1, label %then_1, label %else_2
  then_1:
    print 42
    jmp label %merge_3
  else_2:
    print 99
    jmp label %merge_3
  merge_3:
    ret 0

• After:

  entry_0:
    jmp label %then_1
  then_1:
    print 42
    jmp label %merge_3
  merge_3:
    ret 0

---

4. Benchmark & Optimization Results

Static instruction count reduction measured across all 17 integration benchmark programs using tests/benchmark.py:

Benchmark Program	Unoptimized IR Insts	Optimized IR Insts	Reduction (%)	Status
01_arithmetic.mini	41	6	85.4%	PASSED
02_comparisons.mini	35	9	74.3%	PASSED
03_logical_ops.mini	70	12	82.9%	PASSED
04_simple_if.mini	26	10	61.5%	PASSED
05_nested_if.mini	37	8	78.4%	PASSED
06_while_loop.mini	21	11	47.6%	PASSED
07_nested_while.mini	34	20	41.2%	PASSED
08_shadowing.mini	18	6	66.7%	PASSED
09_fibonacci.mini	33	13	60.6%	PASSED
10_collatz.mini	31	20	35.5%	PASSED
11_division_modulo.mini	49	9	81.6%	PASSED
12_early_return.mini	27	16	40.7%	PASSED
13_complex_expressions.mini	107	16	85.0%	PASSED
14_gcd.mini	23	10	56.5%	PASSED
15_power.mini	33	19	42.4%	PASSED
16_factorial.mini	24	11	54.2%	PASSED
17_scopes.mini	24	2	91.7%	PASSED
TOTAL / AVERAGE	633	198	68.7%	17/17 PASS

---

5. Design Decisions & Limitations

1. Memory-Slots Lowering vs. Direct SSA:
   • Decision: Lowering initially targets stack memory slots (alloca/load/store). SSA construction is isolated to Mem2Reg.
   • Rationale: Mirrors Clang/LLVM design; cleanly decouples AST lowering from dominance frontier calculations.
2. Iterative Dominator Tree Analysis:
   • Decision: Implemented Cooper, Harvey, & Kennedy's "Simple, Fast Dominance Algorithm".
   • Rationale: Maintains high performance and clarity without the implementation complexity of Lengauer-Tarjan.
3. Fail-Fast SSA Verifier:
   • Decision: An IRVerifier runs after SSA construction and after every optimization pass.
   • Rationale: Validates definition-dominates-uses invariants, single static assignment, and $\phi$-node predecessor consistency.
4. Differential Oracle Testing:
   • Decision: An AST interpreter serves as executable specification ground truth against the IR interpreter.
   • Rationale: Guarantees semantic equivalence before and after optimization passes across all execution paths and outputs.
5. Current Limitations:
   • The type system is strictly 64-bit integers.
   • Function definitions are scoped to @main; inter-procedural analysis is left for future expansion.

---

6. Build and Test

# Build
mkdir -p build && cd build
cmake ..
cmake --build .

# Run CTest unit test suite (8 suites, 100% pass)
ctest --output-on-failure

# Run benchmark evaluation
python3 ../tests/benchmark.py

# Run differential testing harness
python3 ../tests/run_tests.py

CLI Options

./optic <file> --emit-ast        # Print AST
./optic <file> --emit-ir         # Print unoptimized 3-address IR
./optic <file> --emit-ssa        # Print SSA IR (after Mem2Reg)
./optic <file> --opt             # Run full optimization pipeline
./optic <file> --opt --emit-ir   # Print optimized SSA IR
./optic <file> --run-ast         # Execute via AST interpreter
./optic <file> --run-ir          # Execute via IR interpreter
./optic <file> --run             # Execute via IR interpreter (default)
./optic <file> --verify          # Verify AST vs IR output equivalence
./optic --help                   # Display CLI usage options