SCFG failing case

[sklam]

def udt(i):
    while i < 10:
        if i > 2:
            s = 123
        i += 1
    return s

numba-rvsdg/numba_rvsdg/core/datastructures/scfg.py:734: in restructure
    self.restructure_loop()
numba-rvsdg/numba_rvsdg/core/datastructures/scfg.py:712: in restructure_loop
    restructure_loop(self.region)
numba-rvsdg/numba_rvsdg/core/transformations.py:269: in restructure_loop
    loop_restructure_helper(scfg, loop)
numba-rvsdg/numba_rvsdg/core/transformations.py:34: in loop_restructure_helper
    headers, entries = scfg.find_headers_and_entries(loop)
numba-rvsdg/numba_rvsdg/core/datastructures/scfg.py:393: in find_headers_and_entries
    headers = {self.find_head()}
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

self = SCFG(graph={'1': PythonASTBlock(name='1', _jump_targets=('2', '3'), backedges=(), begin=-1, end=-1, tree=[<ast.Compare..._region_0', _jump_targets=(), backedges=(), kind='meta', parent_region=None, header=None, subregion=..., exiting=None))

    def find_head(self) -> str:
        """Finds the head block of the SCFG.

        Assuming the SCFG is closed, this will find the block
        that no other blocks are pointing to.

        Returns
        -------
        head: str
            Name of the head block of the graph.
        """
        heads = set(self.graph.keys())
        for name in self.graph.keys():
            block = self.graph[name]
            for jt in block.jump_targets:
                heads.discard(jt)
>       assert len(heads) == 1
E       AssertionError

[esc]

looks like the graph has no entry node and is just a long cycle:

SCFG(graph={'1': PythonASTBlock(name='1', _jump_targets=('2', '3'), backedges=(), begin=-1, end=-1, tree=[<ast.Compare object at 0x106047610>]),
            '2': PythonASTBlock(name='2', _jump_targets=('5', '7'), backedges=(), begin=-1, end=-1, tree=[<ast.Compare object at 0x1060445d0>]),
            '3': PythonASTBlock(name='3', _jump_targets=(), backedges=(), begin=-1, end=-1, tree=[<ast.Return object at 0x106047650>]),
            '5': PythonASTBlock(name='5', _jump_targets=('7',), backedges=(), begin=-1, end=-1, tree=[<ast.Assign object at 0x106047850>]),
            '7': PythonASTBlock(name='7', _jump_targets=('1',), backedges=(), begin=-1, end=-1, tree=[<ast.AugAssign object at 0x1060479d0>])},
     name_gen=NameGenerator(kinds={'meta': 1}),
     region=RegionBlock(name='meta_region_0',
                        _jump_targets=(),
                        backedges=(),
                        kind='meta',
                        parent_region=None,
                        header=None,
                        subregion=...,
                        exiting=None))

[esc]

The problem is that since the first statement of the function is a while loop, the block with index 0 is pruned erroneously, hence you end up with a loop. The loop transformation depends on being able to find an entry block, that no other blocks point to. The error message means that heads is an empty set.

[esc]

I shortened the reproducer to be:

    def function(i):
            while i < 10:
                i += 1
            return i

[esc]

The first solution here is to avoid printing the first/genesis block and to emit a simple pass for an empty block. I guess the latter would be needed anyway, in case someone deactivates the empty block pruning. Alternatively I could emit a Pass in that block, however, currently the removal of no-ops is scheduled before the removal of empty blocks and so that approach would be nullified with the default pipeline.

[esc]

The first solution here is to avoid printing the first/genesis block and to emit a simple pass for an empty block. I guess the latter would be needed anyway, in case someone deactivates the empty block pruning. Alternatively I could emit a Pass in that block, however, currently the removal of no-ops is scheduled before the removal of empty blocks and so that approach would be nullified with the default pipeline.

The first solution is implemented here:

https://github.com/numba/numba-rvsdg/pull/151/commits/2f7924aac7f197d82ac8ce30693013ce470161b6