Overview

I sought to replicate the logic of FFTW’s genfft: a metaprogram that generates straight-line, highly optimized C code. The goal was to understand how abstract algebra (group theory) could be translated into efficient machine code through symbolic manipulation.

Features

The build is functional metaprogramming applied to compiler construction:

  • Symbolic AST: Modeled mathematical operations as a Directed Acyclic Graph (DAG) in Haskell (data Node), separating the definition of the math from its execution.
  • Algebraic Simplification: Implemented a symbolic optimization pass that pruned operations at compile-time (e.g., eliminating multiplications by $1$, $0$, or $-1$) before code generation.
  • Monadic State Management: Used Haskell’s State Monad to manage the graph construction and memoization, ensuring common subexpressions (like reusable cosine factors) were calculated only once.
  • Code Generation: The system outputted unrolled, straight-line C code (e.g., fftw4.c), mimicking the “codelets” used by the actual FFTW library.

Usage

The compiler is run via the command line, taking the desired FFT size as input and outputting the optimized C code.

Retrospective

  • Where the speed comes from: unrolling recursion and managing register pressure at compile time, not from writing faster loops.
  • Known limit: the scheduler colors nodes Red/Blue for register allocation, a heuristic approximation of the optimal Aho-Johnson-Ullman algorithm.
  • Carries forward: domain-specific compilers outperform hand-tuned generic code.