numba-rvsdg

Numba compatible RVSDG (Regionalized Value State Dependence Graph) utilities.

This repository contains Numba compatible utilities for working with RVSDGs (Regionalized Value State Dependency Graphs). RVSDGs are a type of Intermediary Representation (IR) suitable for regularizing Python bytecode within Numba.

The code in this repository is an implementation of the CFG restructuring algorithms in Bahmann2015, specifically those from section 4.1 and 4.2: namely “loop restructuring” and “branch restructuring”. These are interesting for Numba because they serve to clearly identify regions within the Python bytecode.

Philosophy

The transformational algorithms LOOP-RESTRUCTURE and BRANCH-RESTRUCTURE as described in Bahmann2015 are to be implemented in this repository. The idea is to use these algorithms to regularize Python bytecode such that it becomes “structured”. Using the terms of the paper, to take an existing Control Flow Graph (CFG) and restructure it into a Structured Control Flow Graph (SCFG). The algorithms consist of two parts conceptually: restructuring the CFG such that regions (Loop, Head, Branch and Tail) can be identified clearly. That is to say there is “data” in the form of the blocks of a CFG and analysis in the form or regions that are “overlayed” on top of the data.

API stability

Warning

The API currently being documented is still experimental and under heavy development. It is subject to potential changes, which as a result, may change the API’s behavior, structure, and functionality suddenly without prior notice.