numba / numba-rvsdg Goto Github PK
View Code? Open in Web Editor NEWNumba compatible RVSDG (Regionalized Value State Dependence Graph) utilities.
Home Page: https://numba-rvsdg.readthedocs.io/
License: BSD 2-Clause "Simplified" License
Numba compatible RVSDG (Regionalized Value State Dependence Graph) utilities.
Home Page: https://numba-rvsdg.readthedocs.io/
License: BSD 2-Clause "Simplified" License
As a numba-rvsdg user and as a developer, I want to be able to view an SCFG both from the terminal.
The proposed API should perhaps look like:
scfg.view()
And then, if we are in an IPython notebook environment render the SCFG inside the notebook and if we are in a Python or IPython terminal session, attempt to render the SCFG to a PDF files and open it in an existing viewer.
Currently the release.yml
only produces sdist
and wheel
artifacts. As part of the release process, as a developer, I also want this workflow to produce conda
packages. They should be built and uploaded to the GitHub release in addition to the PyPi generated packages.
From #80 (comment), I noticed that it's possible to make RVSDG from Python bytecode already. (I hadn't been paying close attention to all the progress that was being made here, but I just noticed it now.)
This is a note to myself (which I will assign to myself) to write a demonstrator of Python bytecode โ Python AST, at least for a subset of simple expressions, to get a sense of how it will go. I understand that the RVSDG development is very much in flux and that the demonstrator will get out of date quickly, but it would be good for me to do a first test-run, to get familiar with RVSDG as a concept and discover what the fundamental issues are.
As titled,
The ByteFlow
and FlowInfo
classes can be removed to reduce complexity. All of the methods of the classes can either be made part of the SCFG
object or can be made into a function rather than a part of the class.
During the last release, 0.0.5 the version number in the sphinx based docs was not updated:
https://github.com/numba/numba-rvsdg/blob/main/docs/source/conf.py#L12
Reproducer and SCFG rendering in https://gist.github.com/sklam/f43f7c4eb574a79eaca9d5b4d27ef6ba
When calling find_headers_and_entries
in a header loop region that's inside a branch region, it fails to find the entry node.
The usecase is to insert a new block as the new header for the loop.
From DEBUGGRAPH=1 pytest numba_rvsdg/tests/test_mock_asm.py::test_mock_scfg_fuzzer_case0
in #42.
We need special handling for endless loop like this:
A potential fix is described in: https://github.com/phate/jlm/pull/71/files#diff-5da2c1eea581b6b09d5820765778b4d657700c2b2fbb46c64fa498d66bcd182fR259-R260
The test.yaml
workflow only tests the installation via pip
and tests the software. As a developer I would like to see inclusion of testing the package building too to make sure that none of my PRs break packaging. The idea is to try to build a sdist
and wheel
for PyPi and a noarch
package using conda
and to check that these packages are sane, i.e. they can be installed and the included tests can be run successfully.
To stay pure and faithful to the original paper, i'd suggest removing the SyntheticForIter
. As mentioned in OOB discussion, the transformation should be able to operate base on a interface of:
class OpIFace:
def is_jump(self) -> bool: ...
def get_jump_targets(self) -> Tuple[Label]: ...
If the FOR_ITER bytecode is doing too much, i suggest preprocessing it into synthetic small operations before the rvsdg transform.
From DEBUGGRAPH=1 pytest numba_rvsdg/tests/test_mock_asm.py::test_mock_scfg_fuzzer_case36
of #42 .
Single block loops are not restructured:
The attribute jump_target
of BasicBlock
class is mutated over the course of various transformations, this leads to the blocks being rebuilt and the SCFG being deep copied every time a transformation is applied.
It should be made a mutable property of the SCFG class instead of an immutable property of the BasicBlock
frozen data class. This will prevent unnecessary copies.
Currently, only the block structure is part of the YAML representation, this means the Regions and their placement can not be tested effectively. As a numba developer I want to be able to test loop_restructure
and branch_restructure
effectively and for this I will need to be able to encode the expected result, including regions, in a simple YAML syntax.
Then -- once this syntax is established -- all the existing tests need to be refactored such that region testing is added to them.
This is a reminder to refactor numba_rvsdg/tests/test_figures.py
as per:
See images below. Loop block has edge violating the region structures.
Reproducer 1
YAML:
"mock_block_0":
jt: ["mock_block_2", "mock_block_10"]
"mock_block_2":
jt: ["mock_block_5", "mock_block_11"]
"mock_block_5":
jt: ["mock_block_10", "mock_block_5"]
"mock_block_10":
jt: ["mock_block_11"]
"mock_block_11":
jt: []
original graph:
section of transformed graph showing the bad edge:
Reproducer 2
YAML:
"mock_block_0":
jt: ["mock_block_11", "mock_block_2"]
"mock_block_1":
jt: ["mock_block_7", "mock_block_6"]
"mock_block_2":
jt: ["mock_block_3"]
"mock_block_3":
jt: ["mock_block_4"]
"mock_block_4":
jt: ["mock_block_5"]
"mock_block_5":
jt: ["mock_block_4", "mock_block_1"]
"mock_block_6":
jt: ["mock_block_18", "mock_block_5"]
"mock_block_7":
jt: ["mock_block_10", "mock_block_8"]
"mock_block_8":
jt: ["mock_block_5", "mock_block_11"]
"mock_block_9":
jt: ["mock_block_3", "mock_block_12"]
"mock_block_10":
jt: ["mock_block_10", "mock_block_6"]
"mock_block_11":
jt: ["mock_block_12"]
"mock_block_12":
jt: ["mock_block_15", "mock_block_17"]
"mock_block_15":
jt: ["mock_block_9", "mock_block_17"]
"mock_block_17":
jt: ["mock_block_18"]
"mock_block_18":
jt: []
The code here should probably read _jump_targets
. The `jump_targets are the "discounted" targets, i.e. w/o the backedges. Thus, if a block has only a single backedge, under this code it would also be considered an "exiting" block. However, exiting blocks are blocks that contain a return statement or equivalent and basically denote the termination block of a program.
As per:
We want to remove BasicBlock.replace_back_edge
entirely to save on code and complexity.
As a developer I will need conda
packages for numba-rvsdg
such that it can be included in Numba as a dependency. Otherwise people installing numba
via conda
will not be able to resolve the dependency chain. Ideally these can be produced on uploading tags for stable release and on merged to main
as nightly builds. They should arrive on the numba/label/main
channel and numba/label/dev
respectively.
Ref: numba/numba#9043
From DEBUGGRAPH=1 pytest numba_rvsdg/tests/test_mock_asm.py::test_mock_scfg_fuzzer_case9
in #42.
CFG:
Loop restructured:
The loop should switch between offset 4 and offset 6 blocks but there are no assignment to control-variable a within the loop.
This is a variant on the SCC algorithm, mainly the yield
statement are replaced: https://gist.github.com/sklam/dbe21c6df5b882bc41a27ff3e6cf79a0
Error:
Traceback (most recent call last):
File "/path/to/numba-rvsdg/test_fig_scc.py", line 72, in <module>
lflow = cflow._restructure_loop()
^^^^^^^^^^^^^^^^^^^^^^^^^
File "/path/to/numba-rvsdg/byteflow2.py", line 637, in _restructure_loop
restructure_loop(region.subregion)
File "/path/to/numba-rvsdg/byteflow2.py", line 928, in restructure_loop
extract_region(bbmap, loop, "loop")
File "/path/to/numba-rvsdg/byteflow2.py", line 1002, in extract_region
assert len(headers) == 1
AssertionError
Create an example ipynb file with some examples on how to use numba-rvsdg.
From DEBUGGRAPH=1 pytest numba_rvsdg/tests/test_mock_asm.py::test_mock_scfg_double_exchange_loop
in #42
CFG:
Missing branch regions inside loop region.
From DEBUGGRAPH=1 pytest numba_rvsdg/tests/test_mock_asm.py::test_mock_scfg_fuzzer_case146
in #42
CFG:
Traceback:
def test_mock_scfg_fuzzer_case146():
> run_fuzzer(seed=146)
numba_rvsdg/tests/test_mock_asm.py:611:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
numba_rvsdg/tests/test_mock_asm.py:562: in run_fuzzer
compare_simulated_scfg(asm)
numba_rvsdg/tests/test_mock_asm.py:442: in compare_simulated_scfg
scfg = to_scfg(instlist)
numba_rvsdg/tests/test_mock_asm.py:312: in to_scfg
restructure_loop(scfg)
numba_rvsdg/core/transformations.py:228: in restructure_loop
loop_restructure_helper(bbmap, loop)
numba_rvsdg/core/transformations.py:165: in loop_restructure_helper
bbmap.add_block(block.replace_jump_targets(jump_targets=tuple(jts)))
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
self = BranchBlock(label=SyntheticHead(index='8'), _jump_targets=(MockAsmLabel(index='2'), MockAsmLabel(index='1')), backedges=set(), variable='a', branch_value_table={0: MockAsmLabel(index='1'), 1: MockAsmLabel(index='2')})
jump_targets = ()
def replace_jump_targets(self, jump_targets: Tuple) -> "BasicBlock":
fallthrough = len(jump_targets) == 1
old_branch_value_table = self.branch_value_table
new_branch_value_table = {}
for target in self.jump_targets:
if target not in jump_targets:
# ASSUMPTION: only one jump_target is being updated
diff = set(jump_targets).difference(self.jump_targets)
> assert len(diff) == 1
E AssertionError
numba_rvsdg/core/datastructures/basic_block.py:94: AssertionError
The RETURN_VALUE
bytecode is not unified by when SCFG join returns. This leads to SCFG that semantically terminates in the middle of switches.
For example:
import dis
from numba_rvsdg.core.datastructures.scfg import SCFG
from numba_rvsdg.core.datastructures.byte_flow import ByteFlow
def example(x):
if x:
return 1
else:
return 2
dis.dis(example)
bf = ByteFlow.from_bytecode(example).restructure()
bf.scfg.view()
The bytecode is:
5 0 RESUME 0
6 2 LOAD_FAST 0 (x)
4 POP_JUMP_FORWARD_IF_FALSE 2 (to 10)
7 6 LOAD_CONST 1 (1)
8 RETURN_VALUE
9 >> 10 LOAD_CONST 2 (2)
12 RETURN_VALUE
Notice that both "branch" regions contain a RETURN_VALUE
.
I have two workarounds at sklam/numba@c9d3634:
Update - Aug 4
I have a new workaround that solely addresses the problem in RVSDG->NumbaIR (bcinterp.py) at numba/numba@a117aae. It relies on interpreting RETURN_VALUE
as non terminating.
Graph rendering code can be messy. Sometimes we need viz-backend specific logic. It's also hard to test.
The suggestion is to add a AbstractDataType for hiding the details of graph rendering. All it needs is really a set of nodes, edges and node grouping for regions.
Sample implementation in: https://github.com/numba/numba/blob/edfc1b95bf633abb346fbbe265acf2bb20560a6e/numba/core/frontend2/regionrenderer.py#L56
Such a class will also allow us to exercise graph rendering in tests. For instance, the sample implementation has a .verify()
method to ensure the graph is wellformed; e.g. edges points to existing locations.
This ADT will allow backend specific code to be isolated: https://github.com/numba/numba/blob/edfc1b95bf633abb346fbbe265acf2bb20560a6e/numba/core/frontend2/regionrenderer.py#L127
Testing for this will be hard to automate but now it's contained in one place without mixing with other logic.
When attempting to release 0.0.3 it turned out that when pushing the tag, the release.yml
workflow didn't trigger. The assumption is that this didn't work because the regex looks for a tag with v
prefix. During testing this was found to not make a difference, but it seems like either that discovery was erroneous or that something has changed in the meantime. For the 0.0.4 release an experimental fix has been included:
This issue lists Renovate updates and detected dependencies. Read the Dependency Dashboard docs to learn more.
This repository currently has no open or pending branches.
.github/workflows/release.yml
actions/checkout v4
taiki-e/create-gh-release-action v1
actions/checkout v4
actions/setup-python v5
actions/upload-artifact v4
actions/checkout v4
actions/upload-artifact v4
actions/checkout v4
actions/download-artifact v4
actions/checkout v4
ubuntu 22.04
.github/workflows/test.yml
actions/checkout v4
conda-incubator/setup-miniconda v3
pyproject.toml
docs/rtd-requirements.txt
.pre-commit-config.yaml
pre-commit/pre-commit-hooks v4.6.0
asottile/pyupgrade v3.16.0
psf/black 24.4.2
pycqa/autoflake v2.3.1
pycqa/flake8 7.0.0
pre-commit/mirrors-mypy v1.10.0
Sample implementation used in Numba RVSDG frontend: https://github.com/numba/numba/blob/edfc1b95bf633abb346fbbe265acf2bb20560a6e/numba/core/frontend2/regionpasses.py
RegionVisitor
and RegionTransformers
enables a hierarchical thinking for compiler pass implementation. This simplifies compiler passes to just 3 abstract methods:
visit_block()
: handle a purely data-dependence block in RVSDG.visit_loop()
: handle a loop region.visit_switch()
: handle a switch region.A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.