KAIST CS420 — KECC Compiler (IR generation + optimizations)

A C compiler built on the KECC (KAIST Educational C Compiler) framework in Rust — an independent, from-skeleton implementation of the CS420: Compiler Design homeworks (KAIST), part of a csdiy.wiki full-catalog build.

Overview

CS420 has students implement translations and optimizations inside KECC, a real C compiler written in Rust that targets actual C (tested with the Csmith fuzzer) and RISC-V. This repository implements the homework pieces on top of the official kaist-cp/kecc-public skeleton (imported as the base commit) and verifies each one with the course's own cargo nextest test harness against the shipped examples/.

Implemented and verified: the C AST printer (write_c), all four IR optimizations (simplify_cfg, mem2reg, deadcode, gvn), and C→IR generation (irgen) for the scalar subset plus arrays/floats. RISC-V asmgen and struct-by-value irgen are the remaining pieces (see Not completed).

Results (measured on WSL2 Ubuntu, x86-64, CPU-only)

Verified with cargo nextest — full log in results/nextest_verified.log:

6 tests run: 6 passed
    PASS  test_examples_write_c
    PASS  test_examples_simplify_cfg
    PASS  test_examples_mem2reg
    PASS  test_examples_deadcode
    PASS  test_examples_gvn
    PASS  test_examples_irgen_small

Homework	Test	What is verified	Result
write_c	test_examples_write_c	60 C files: parse → print → re-parse → AST-equivalent	60/60
simplify_cfg	test_examples_simplify_cfg	4 sub-passes + ir0→ir1 over 60 files	pass
mem2reg	test_examples_mem2reg	example + ir1→ir2 over 60 files	pass
deadcode	test_examples_deadcode	example + ir2→ir3 over 60 files	pass
gvn	test_examples_gvn	example + ir3→ir4 over 60 files	pass
irgen (scalar+array+float)	test_examples_irgen_small	~48 C files: KECC IR interpreted vs clang executable	pass

Optimizer correctness: the full O1 pipeline was additionally run over all 60 examples/ir0 inputs and each result executed with the KECC IR interpreter — 0 miscompiles (return values identical to the originals). See results/RESULTS.md. An end-to-end irgen → O1 demonstration on fibonacci.c is captured in results/fibonacci_pipeline.txt.

Implemented assignments

• write_c — C AST → source pretty-printer (src/c/write_c.rs), round-trips through the parser to a structurally equivalent AST. Handles nested pointer/array/function declarators, structs, typedefs, casts, sizeof.
• simplify_cfg — constant-propagation of branch/switch exits, unreachable-block removal, straight-line block merging, empty-block bypass (src/opt/simplify_cfg.rs).
• mem2reg — SSA construction: promotes non-address-taken allocations, places phinodes at the iterated dominance frontier, renames on the dominator tree (src/opt/mem2reg.rs).
• deadcode — liveness-based removal of nops, dead pure instructions, dead phinodes and unused allocations, with index compaction (src/opt/deadcode.rs).
• gvn — global value numbering with dominance-based redundancy elimination and demand-driven partial-redundancy (phi) insertion (src/opt/gvn.rs).
• irgen (scalar + arrays + floats) — C → KECC IR: l-value/r-value translation, usual arithmetic conversions with integer promotion, short-circuit &&/||, ?:, pointer arithmetic and array subscript / struct member access via getelementptr, all of if/while/do-while/for/switch (src/irgen/mod.rs).
• asmgen — RISC-V assembly generation (not implemented).

Project structure

kaist-cs420/
├── src/
│   ├── c/            # C parser (given) + write_c (implemented)
│   ├── ir/           # IR types, parser, printer, interpreter (given)
│   ├── irgen/        # C -> IR generation (implemented: scalar/array/float)
│   ├── opt/          # simplify_cfg, mem2reg, deadcode, gvn (implemented) + opt_utils
│   ├── asm/          # RISC-V asm types (given)
│   └── asmgen/       # IR -> RISC-V (not implemented)
├── examples/         # course-provided C and IR examples (test fixtures)
├── tests/            # course test harness + Csmith fuzzer
├── results/          # measured verification outputs (this build)
└── docs_KECC_manual.md   # original KECC build/usage manual (from skeleton)

How to run

Toolchain: Rust (the repo pins 1.85.0 via rust-toolchain.toml; it also builds on newer stable — this build was verified with stable 1.96). The irgen test additionally needs clang. On Windows this was run inside WSL2 Ubuntu.

cargo install cargo-nextest   # once

# Run the verified homework tests
RUST_MIN_STACK=33554432 cargo nextest run test_examples_write_c
RUST_MIN_STACK=33554432 cargo nextest run test_examples_simplify_cfg
RUST_MIN_STACK=33554432 cargo nextest run test_examples_mem2reg
RUST_MIN_STACK=33554432 cargo nextest run test_examples_deadcode
RUST_MIN_STACK=33554432 cargo nextest run test_examples_gvn
RUST_MIN_STACK=33554432 cargo nextest run test_examples_irgen_small   # needs clang

# Compile a C file to IR / optimize / interpret
cargo run --features=build-bin -- -i            examples/c/fibonacci.c   # irgen
cargo run --features=build-bin -- -O --iroutput examples/c/fibonacci.c   # optimize
cargo run --features=build-bin -- --irrun       examples/c/fibonacci.c   # interpret

Verification

Every optimization pass is checked by test_opt, which compares the pass output to the reference IR under structural equivalence (ir::IsEquiv) — blocks are matched by CFG pre-order and allocations, phinodes and instructions must line up exactly. write_c is checked by re-parsing the printed source and comparing ASTs. irgen is checked by interpreting the generated IR and comparing the result to a natively clang-compiled executable of the same C program. The composed O1 pipeline was independently validated for semantic correctness with the IR interpreter (0 miscompiles across 60 programs).

Reproduced outputs live under results/.

Tech stack

Rust 2024 edition; lang-c (C parser), peg (IR grammar), itertools, ordered-float. Dominance / dominance-frontier analysis for SSA construction and PRE.

Key ideas / what I learned

• SSA construction end-to-end: dominators (Cooper–Harvey–Kennedy), iterated dominance frontiers for phi placement, and dominator-tree renaming (mem2reg).
• Global value numbering and why eager PRE over-inserts phinodes — demand-driven phi insertion is what matches a real optimizer, and a phinode's incoming values must be read across all CFG edges (a subtle miscompile otherwise).
• C's declarator grammar is "inside-out"; reconstructing source requires care with pointer vs. array/function binding and precedence parentheses.
• Faithful C→IR lowering: l-value/r-value distinction, integer promotion and usual arithmetic conversions, short-circuit evaluation and ?: via explicit control flow.

Credits & license

Based on the CS420: Compiler Design homeworks and the KECC skeleton by Jeehoon Kang and the KAIST Concurrency & Parallelism Lab. This repository is an independent educational reimplementation; the KECC framework, examples, and specifications belong to their original authors. Original implementation code here is released under the MIT License.