S4C — C/LLVM IR to SUBNEG4 Compiler

S4C compiles C (.c) or LLVM IR (.ll) to SUBNEG4 assembly (.s4).

SUBNEG4 is a one-instruction set computer (OISC): each instruction has 4 operands A B C D and executes mem[C] = mem[B] - mem[A]; if result < 0 then goto D.

Setup

bin/setup

This installs dependencies, checks for clang, and runs the test suite.

Requirements: Ruby 3.3+, clang (for .c input)

Quick Start

# Compile C directly to SUBNEG4 (requires clang)
./bin/s4c program.c -o program.s4

# Compile LLVM IR to SUBNEG4
./bin/s4c program.ll -o program.s4

# Skip the optimizer
./bin/s4c program.c -o program.s4 --no-opt

Pipeline

.c  →  clang -S -emit-llvm  →  .ll  →  S4C  →  .s4
                                         │
                              ┌──────────┴──────────┐
                              │  Parser (.ll regex)  │
                              │  Lowering (IR→pseudo) │
                              │  Optimizer (13 passes)│
                              │  Expander (→SUBNEG4)  │
                              │  Emitter (.s4 text)   │
                              └─────────────────────┘

Supported LLVM IR Features

• Arithmetic: add, sub, mul, sdiv, srem
• Bitwise: and, or, xor, shl, ashr, lshr
• Comparisons: icmp (slt, sgt, sle, sge, ult, ugt, ule, uge, eq, ne)
• Control flow: br (conditional/unconditional), select, phi
• Memory: alloca (scalar/array), load, store, getelementptr
• Functions: call with save/restore (recursion-safe), ret, multi-function
• Pointers: ptr parameters, indirect load/store, passing arrays
• Global variables (scalars and initialized arrays)
• Casts: sext, zext, trunc, bitcast

Optimizer

13 iterative passes (up to 10 rounds until convergence):

#	Pass	Description
1	GotoNextElimination	Remove goto L followed by L:
2	GotoChainSimplification	Redirect goto L1 when L1: goto L2
3	RedundantBranchElimination	branch(x, L) + goto L → goto L
4	UnreachableCodeElimination	Remove code after unconditional jumps
5	DeadLabelElimination	Remove unreferenced labels
6	ConstantFolding	Evaluate constant expressions at compile time
7	StrengthReduction	x + 0 → x, x - x → 0
8	PeepholeDoubleNegation	-(-x) → x
9	LocalValueNumbering	Within-block CSE (common subexpression elimination)
10	LoopInvariantCodeMotion	Hoist invariant ops before loop header
11	CopyPropagation	Forward substitution of copies
12	DeadStoreElimination	Remove writes to unused variables
13	PushPopElimination	Remove unused save/restore pairs

Additionally, the lowering phase performs constant specialization:

• mul(x, 0..8) → inline addition chains (no subroutine call)
• sdiv(x, 1), srem(x, 1) → identity/zero

Tests

rake test                           # run all tests
ruby -Ilib test/test_e2e.rb        # 26 end-to-end tests
ruby -Ilib test/test_optimizer.rb   # 54 optimizer unit tests

Test fixtures include: fibonacci, factorial, collatz, sieve of Eratosthenes, GCD, bubble sort, matrix multiplication, Tower of Hanoi, and more.

Project Structure

s4c.rb              CLI entry point
bin/
  s4c               Executable wrapper
  setup             Environment setup script
lib/
  parser.rb         Regex-based .ll parser
  ir_nodes.rb       IR data structures
  lowering.rb       IR → pseudo-op conversion
  pseudo_ops.rb     Pseudo-instruction definitions
  optimizer.rb      13-pass optimizer
  expander.rb       Pseudo-ops → SUBNEG4 expansion
  emitter.rb        SUBNEG4 assembly text output
  memory.rb         Variable/constant allocation
test/
  test_e2e.rb       E2E tests with built-in SUBNEG4 simulator
  test_optimizer.rb Optimizer unit tests
  fixtures/         .c and .ll test programs

Limitations

• No floating point
• No i8/string handling (everything is word-sized)
• No struct support
• Arithmetic operations are loop-based (mul is O(n), div/mod is O(n/d))