Compiler Data-Flow Analysis Engine

A small compiler-analysis project written in Python that parses a subset of C, builds a Control-Flow Graph (CFG), and solves classic data-flow problems using a reusable worklist algorithm.

Features

• Parses C code with pycparser
• Builds CFGs for declarations, assignments, if/else, while, for, return, break, and continue
• Implements Reaching Definitions as a forward may-analysis
• Implements Live Variables as a backward may-analysis
• Uses a generic fixed-point worklist solver
• Exports CFGs as PNG and Graphviz DOT files
• Includes sample C programs and automated regression tests

Repository Structure

Compiler-Data-Flow-Analysis/
├── src/
│   ├── main.py
│   ├── cfg.py
│   ├── analyses.py
│   └── utils.py
├── examples/
│   ├── if_else.c
│   ├── while_if.c
│   └── for_loop.c
├── tests/
│   └── test_engine.py
├── docs/
│   ├── report.md
│   └── assets/
├── requirements.txt
├── .gitignore
├── .gitattributes
└── README.md

Analyses

Reaching Definitions

For each basic block B:

IN[B]  = union(OUT[P]) for P in predecessors(B)
OUT[B] = GEN[B] union (IN[B] - KILL[B])

Live Variables

For each basic block B:

OUT[B] = union(IN[S]) for S in successors(B)
IN[B]  = USE[B] union (OUT[B] - DEF[B])

Installation

python -m venv .venv

Activate the environment, then install the dependencies:

pip install -r requirements.txt

Usage

Run all built-in examples:

python src/main.py

Analyze a supplied C file:

python src/main.py --file examples/if_else.c --outdir out

The command prints the CFG blocks, reaching-definition sets, live-variable sets, and worklist updates. It also writes PNG and DOT CFG files to the selected output directory.

Example CFGs

If / Else

While + If

For Loop

Tests

Run the regression tests with:

python -m unittest discover -s tests -v

The tests cover important correctness cases including for initializers, repeated definitions, returning branches, compound assignments, and loop break handling.

Scope

This is an educational analysis engine, not a full C compiler. It intentionally supports a practical subset of C and uses simplified alias/memory modeling. Pointer aliasing, full preprocessing, interprocedural analysis, and all C control-flow constructs are outside the current scope.

Documentation

See docs/report.md for the theory, equations, implementation outline, and experiment discussion.

Technologies

• Python
• pycparser
• NetworkX
• Matplotlib
• Compiler data-flow analysis