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.

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.

From DEBUGGRAPH=1 pytest numba_rvsdg/tests/test_mock_asm.py::test_mock_scfg_double_exchange_loop in #42

CFG:

loop and branch restructured

Missing branch regions inside loop region.

Create an example ipynb file with some examples on how to use numba-rvsdg.

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.

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

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.

• Activate numba_rvsdg on readthedocs
• setup a GHA to build the docs on push

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.

From DEBUGGRAPH=1 pytest numba_rvsdg/tests/test_mock_asm.py::test_mock_scfg_fuzzer_case36 of #42 .

Single block loops are not restructured:

CFG:

After loop restructuring

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.

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.

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.

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

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.

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.

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

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

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.

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

The SCFG

Notice that both "branch" regions contain a RETURN_VALUE.

I have two workarounds at sklam/numba@c9d3634:

• rewrite the bytecode to turn RETURN_VALUE into jumps and inserting a unified RETURN_VALUE after the last bytecode offset. sklam/numba@c9d3634#diff-777376747c149410653d20624af95aff1bc2dc050186ef11e4e8a222288184aaR628-R672
• a SCFG version of the above logic but done before restructuring. sklam/numba@c9d3634#diff-777376747c149410653d20624af95aff1bc2dc050186ef11e4e8a222288184aaR596-R619

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.

Reimplement or cherry-pick the tracing simulator from the experimental branch:

a5cfba2

733dd71

#30

As per:

#61 (comment)

We want to remove BasicBlock.replace_back_edge entirely to save on code and complexity.

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:

4284250

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: []

section of transformed graph showing the bad edge:

This issue serves as a checklist for the things/features that we want for the 0.0.3 release.

• #71
• #66
• #64
• #63
• #73
• #75

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 #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.

This is a reminder to refactor numba_rvsdg/tests/test_figures.py as per:

#50 (comment)

Pending merge of #50 and #75