Metadata-Version: 2.4
Name: pyir
Version: 0.1.0
Summary: Python Intermediate Representation: lower a Python subset to basic-block IR, optimise it and interpret it.
Author: nehz
License-Expression: MIT
Keywords: compiler,ir,intermediate representation,ast,optimization,interpreter,education
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Education
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Software Development :: Compilers
Classifier: Topic :: Software Development :: Interpreters
Classifier: Typing :: Typed
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

# 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

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

## Quickstart

```python
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`:

```python
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:

```bash
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 `def`s 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

```bash
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
