Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

SCFG failing case #150

Open
sklam opened this issue Sep 23, 2024 · 5 comments · May be fixed by #151
Open

SCFG failing case #150

sklam opened this issue Sep 23, 2024 · 5 comments · May be fixed by #151

Comments

@sklam
Copy link
Member

sklam commented Sep 23, 2024 

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
Copy link
Member

esc commented Sep 23, 2024

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
Copy link
Member

esc commented Sep 23, 2024

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 esc linked a pull request Sep 24, 2024 that will close this issue
Open
@esc
Copy link
Member

esc commented Sep 25, 2024

I shortened the reproducer to be:

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

@esc
Copy link
Member

esc commented Sep 25, 2024

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
Copy link
Member

esc commented Sep 25, 2024

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:

2f7924a

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix issue 150 esc/numba-rvsdg
2 participants
@esc @sklam