pyir — Python Intermediate Representation

pyir turns ordinary Python functions into a small, readable compiler IR: three-address code organised into basic blocks with an explicit control-flow graph. You can print it, optimise it and run it. It is meant for learning, teaching and experimenting with compiler ideas while staying in Python, without LLVM or a C toolchain.

Every stage is plain Python with no dependencies. The front end uses the stdlib ast module. The IR is a handful of dataclasses. The passes are textbook dataflow analyses. An interpreter executes the IR, so you can check a transformation by comparing its result against CPython running the original source.

Features

• Front end: lowers a useful subset of Python via ast. Supported: functions, local variables, if/elif/else, while, for x in range(...), break/continue, return, tuple assignment (a, b = b, a % b), augmented assignment, arithmetic, bitwise and comparison operators (including chained comparisons), short-circuit and/or with Python's operand-returning semantics, conditional expressions, recursion and calls between functions, and a few builtins (abs, min, max, int, float, bool, str, round, print).
• IR: three-address code (x = a + b, branch c, L1, L2, jump L, return v, call f(...)) in basic blocks, plus helpers for predecessors, reachability (reverse post-order) and structural verification.
• Pretty-printer: a stable, diff-friendly text format.
• Optimisation passes:
  • constant_fold: global constant propagation and folding, which also turns branches on known conditions into jumps.
  • eliminate_dead_code: removes unreachable blocks and unused assignments, driven by liveness analysis.
  • simplify_cfg: threads jumps through empty blocks and merges straight-line block chains.
  • optimize: runs the passes to a fixed point.
• Interpreter: executes IR with a step budget. Python exceptions (ZeroDivisionError, ...) propagate unchanged, so results can be compared with CPython one-to-one.
• CLI: python -m pyir file.py [-O] [--run FUNC ARG...].
• Standard library only. Typed (py.typed). Python 3.10+.

Install

pip install pyir            # once published
# or, from a checkout:
pip install -e .

Quickstart

import pyir

source = '''
def clamp_sum(n):
    limit = 4 * 25
    debug = False
    total = 0
    for i in range(n):
        if debug:
            print(i)
        total += i
    return total if total < limit else limit
'''

module = pyir.compile_source(source)   # Python source -> IR Module
print(pyir.format_module(module))      # or simply print(module)

pyir.optimize(module)                  # constant folding + DCE + CFG cleanup, in place
print(module)

assert pyir.interpret(module, "clamp_sum", 10) == 45
assert pyir.interpret(module, "clamp_sum", 100) == 100

You can also lower a live function, as long as its source is available to inspect:

def triple_plus_one(x):
    return 3 * x + 1

module = pyir.compile_function(triple_plus_one)
pyir.interpret(module, "triple_plus_one", 4)   # 13

From the command line:

python -m pyir examples.py            # print IR
python -m pyir -O examples.py         # print optimised IR
python -m pyir examples.py --run gcd 48 18

What the IR looks like

clamp_sum above, straight out of the front end. Python locals keep their names and compiler temporaries are written %tN. The for loop runs on a hidden counter (%t2), so reassigning i in the body cannot change the iteration.

function clamp_sum(n):
entry:
    limit = 4 * 25
    debug = False
    total = 0
    %t2 = 0
    %t3 = n
    jump for.cond.1
for.cond.1:
    %t4 = %t2 < %t3
    branch %t4, for.body.2, for.end.4
for.body.2:
    i = %t2
    branch debug, if.then.5, if.end.6
if.then.5:
    %t5 = call print(i)
    jump if.end.6
if.end.6:
    total = total + i
    jump for.step.3
for.step.3:
    %t2 = %t2 + 1
    jump for.cond.1
for.end.4:
    %t7 = total < limit
    branch %t7, ifexp.then.7, ifexp.else.8
ifexp.then.7:
    %t6 = total
    jump ifexp.end.9
ifexp.else.8:
    %t6 = limit
    jump ifexp.end.9
ifexp.end.9:
    return %t6

After pyir.optimize(module), limit is folded to 100 and propagated. The if debug: branch is folded, which leaves the print call unreachable, so it is deleted. The dead limit/debug assignments are removed and the loop body's blocks are merged:

function clamp_sum(n):
entry:
    total = 0
    %t2 = 0
    %t3 = n
    jump for.cond.1
for.cond.1:
    %t4 = %t2 < %t3
    branch %t4, for.body.2, for.end.4
for.body.2:
    i = %t2
    total = total + i
    %t2 = %t2 + 1
    jump for.cond.1
for.end.4:
    %t7 = total < 100
    branch %t7, ifexp.then.7, ifexp.else.8
ifexp.then.7:
    %t6 = total
    jump ifexp.end.9
ifexp.else.8:
    %t6 = 100
    jump ifexp.end.9
ifexp.end.9:
    return %t6

The IR is three-address code, not SSA: a variable may be assigned in several places, as %t6 is above. The passes use classic dataflow analyses that do not depend on single assignment.

API overview

Everything below can be imported from the top-level pyir package.

Front end (pyir.lower)

Name	Description
compile_source(source: str) -> Module	Parse source (top-level defs only, plus an optional module docstring) and lower every function. Raises UnsupportedSyntaxError for constructs outside the subset.
compile_function(fn) -> Module	Lower one live function via inspect.getsource. It may call itself and builtins.

IR (pyir.ir)

Name	Description
Module(functions: dict[str, Function])	Container. Supports module["name"], in, iteration over functions, .verify() and str().
Function(name, params, blocks)	blocks is an ordered dict[str, BasicBlock], and the first block is the entry. Provides .entry, .predecessors(), .reachable() (labels in reverse post-order), .instruction_count(), .verify() and str().
BasicBlock(label, instructions, terminator)	Provides .successors().
Const(value), Var(name)	Operands. Const equality is type-aware: Const(1) != Const(True). Var.is_temp is true for %tN temporaries.
Copy(dest, src)	dest = src
BinOp(dest, op, left, right)	op is one of + - * / // % ** << >> & | ^ == != < <= > >= is or is not
UnaryOp(dest, op, operand)	op is one of - + ~ not
Call(dest, func, args)	Calls a module function, or else an entry of BUILTINS
Jump(target), Branch(cond, if_true, if_false), Return(value)	Terminators
BUILTINS	Name-to-callable map of the builtins that IR may call

Each instruction and terminator has .uses(), which lists the operands it reads.

Printing (pyir.printer)

format_module(module), format_function(function) and format_block(block) each return a str.

Optimisation (pyir.passes)

Name	Description
constant_fold(fn) -> bool	Constant propagation and folding, plus constant-branch folding
eliminate_dead_code(fn) -> bool	Removes unreachable blocks and dead assignments
simplify_cfg(fn) -> bool	Jump threading, branch c, L, L → jump L, and block merging
optimize(target, passes=None, max_rounds=10)	Runs passes (default DEFAULT_PASSES) on a Module or Function until nothing changes. Works in place and returns target.
DEFAULT_PASSES	(constant_fold, eliminate_dead_code, simplify_cfg)

A pass is any callable Function -> bool that mutates the function in place and returns whether it changed anything.

Execution (pyir.interp)

Name	Description
interpret(module, name, *args, max_steps=10_000_000)	Run a function and return its result
Interpreter(module, max_steps=...)	.run(name, *args). .steps holds the number of instructions executed by the last run.

Errors (pyir.errors)

PyIRError is the base class. Its subclasses are:

• UnsupportedSyntaxError (has .lineno)
• IRVerificationError
• IRRuntimeError: unknown function, variable read before assignment, or step budget exhausted

Semantics notes and limitations

• Values are dynamically typed Python objects. Operators are executed with the operator module, so the IR's semantics are exactly CPython's for the supported operations.
• Constant folding never folds an operation that raises (for example 1 // 0). It also leaves alone is comparisons between objects other than None/True/False, and results that would be huge (very large ints or long strings).
• Dead code elimination always keeps calls. It also keeps arithmetic that commonly fails on ordinary numbers: division or modulo by a non-constant or zero, and shifts or ** with a non-constant or negative right operand. Other dead arithmetic is assumed not to raise. For example, unused = a + b is removed even if a and b happen to have incompatible types.
• Reading a local before it is assigned raises IRRuntimeError, where CPython would raise UnboundLocalError.
• Not supported: classes, closures, lambdas, globals, containers and subscripts, attributes, keyword arguments, try, with, and for loops over anything but range (whose optional step must be an integer literal).

Development

PYTHONPATH=src python3 -m unittest discover -s tests -v
# or, with pytest installed:
python3 -m pytest

The test suite runs a set of sample programs and 300 randomly generated programs three ways (CPython, IR, optimised IR) and checks that results and exception types agree.

License

MIT