Single block loops not placed into loop region

[sklam]

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

[esc]

This happens when there is a backedge from header to itself.

This is the reproducer:

        original = """
        "0":
            jt: ["1"]
        "1":
            jt: ["1", "2"]
        "2":
            jt: ["1", "3"]
        "3":
            jt: []
        """

And this is the rendering of it:

This, on the other hand is the rendering of the failed transform, as you can see the backedge from header to header has simply not been processed.

[esc]

The following patch will fix this case:

diff --git i/numba_rvsdg/core/transformations.py w/numba_rvsdg/core/transformations.py
index b3d59811b6..e991de2ba2 100644
--- i/numba_rvsdg/core/transformations.py
+++ w/numba_rvsdg/core/transformations.py
@@ -143,7 +143,7 @@ def loop_restructure_helper(scfg: SCFG, loop: Set[Label]):
                     # matters in this case.
                     new_jt[new_jt.index(jt)] = synth_assign
                 # If the target is the loop_head
-                elif jt in headers and label not in doms[jt]:
+                elif jt in headers: #and label not in doms[jt]:
                     # Create the assignment and record it
                     synth_assign = SynthenticAssignment(str(scfg.clg.new_index()))
                     new_blocks.add(synth_assign)

And yield the following, correct, result:

However, this breaks the fig.3 test with:

    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

[esc]

However, this breaks the fig.3 test with:

    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

This is the same error as in: #48

[esc]

An alternative fix that doesn't break the test suite may be:

diff --git i/numba_rvsdg/core/transformations.py w/numba_rvsdg/core/transformations.py
index b3d59811b6..a630ef45cb 100644
--- i/numba_rvsdg/core/transformations.py
+++ w/numba_rvsdg/core/transformations.py
@@ -143,7 +143,7 @@ def loop_restructure_helper(scfg: SCFG, loop: Set[Label]):
                     # matters in this case.
                     new_jt[new_jt.index(jt)] = synth_assign
                 # If the target is the loop_head
-                elif jt in headers and label not in doms[jt]:
+                elif jt in headers and (label not in doms[jt] or label == jt):
                     # Create the assignment and record it
                     synth_assign = SynthenticAssignment(str(scfg.clg.new_index()))
                     new_blocks.add(synth_assign)