Added region hierarchy and unique naming reference for RegionBlocks in SCFGs

[kc611]

As titled,

This PR makes the following major changes:

• It adds a region hierarchy by the use of SCFG.parent_region and SCFG.regions
• For any SCFG that we create independently, a 'meta-region' is generated automatically which can be used to refer to the graph as a whole.
• During transformations like loop_restructuring and branch_restructuring every new region created has itself declared as the parent_region in the corresponding subregion SCFG.
• loop_restructuring and branch_restructuring now take regions (RegionBlock) as arguments instead of graphs (SCFGs). To do the transformation on an entire graph, we can simply provide the meta-region of the graph instead.
• RegionBlocks are now referred to using their own independent names. They are no longer referred using the header block's name. Hence RegionBlocks can now be treated as essentially independent blocks.
• SCFGs now have a .view() method that renders a quick preview of the current state of the SCFG. (assuming it's valid)

Note that currently RegionBlocks share jump targets with their corresponding exiting blocks. Hence any updates made to jump targets of a RegionBlock, need to be made recursively to their corresponding exiting blocks as well.

[sklam]

@kc611, I discovered a bug:

reproducer:

from numba_rvsdg.core.datastructures.byte_flow import ByteFlow
from numba_rvsdg.rendering.rendering import ByteFlowRenderer

def sum1d(s, e):
    c = 0
    for i in range(s, e):
        c += i
    return c

byteflow = ByteFlow.from_bytecode(sum1d.__code__)
bcmap = byteflow.scfg.bcmap_from_bytecode(byteflow.bc)
byteflow = byteflow.restructure()

bfr = ByteFlowRenderer()
bfr.bcmap_from_bytecode(byteflow.bc)
byteflow.scfg.view("scfg")

[sklam]

@kc611, is https://github.com/numba/numba-rvsdg/pull/61/commits/53291b85a0c0ff44093880825b5d1190e412c783 fixing https://github.com/numba/numba-rvsdg/pull/61#issuecomment-1572791281? Let's make sure we have test for it as well.

[sklam]

As of https://github.com/sklam/numba/commit/2c84e4b47cf49add64924cabdc2740ca9954617e, the numba rvsdg-frontend branch is fully working with this PR.

[esc]

I found a file with trailing whitespace:

Please double check all the files touched by this PR and remove any trailing whitespace, thank you.

[kc611]

I've currently fixed the trailing whitespaces from the entire project using pre-commit from the experimental branch locally.

[esc]

@kc611 this is fine now thank you. As a last request, please include the following test:

from numba_rvsdg.rendering.rendering import render_func

def scc(G):
    preorder = {}
    lowlink = {}
    scc_found = set()
    scc_queue = []
    out = []
    i = 0  # Preorder counter
    for source in G:
        if source not in scc_found:
            queue = [source]
            while queue:
                v = queue[-1]
                if v not in preorder:
                    i = i + 1
                    preorder[v] = i
                done = True
                for w in G[v]:
                    if w not in preorder:
                        queue.append(w)
                        done = False
                        break
                if done:
                    lowlink[v] = preorder[v]
                    for w in G[v]:
                        if w not in scc_found:
                            if preorder[w] > preorder[v]:
                                lowlink[v] = min([lowlink[v], lowlink[w]])
                            else:
                                lowlink[v] = min([lowlink[v], preorder[w]])
                    queue.pop()
                    if lowlink[v] == preorder[v]:
                        scc = {v}
                        while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                            k = scc_queue.pop()
                            scc.add(k)
                        scc_found.update(scc)
                        out.append(scc)
                    else:
                        scc_queue.append(v)
    return out

render_func(scc)

And add it such that it behaves like the other test_fig tests. Just execution when run under pytest and rendering if run as a regular Python file.

[esc]

@kc611 thank you for the patch.