Code assume conditional-branch cannot go to the same target

[sklam]

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

[esc]

Here is the reproducer and image:

        "0":
            jt: ["1", "2"]
        "1":
            jt: ["3", "3"]
        "2":
            jt: ["4"]
        "3":
            jt: ["2"]
        "4":
            jt: ["3", "5"]
        "5":
            jt: ["4", "6"]
        "6":
            jt: []

[esc]

Using the patch:

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)

Actually allows the loop restructuring to continue, but then it produces:

[esc]

Incidentally, the SCCs for the case are:

{ControlLabel(index='3'), ControlLabel(index='2'), ControlLabel(index='5'), ControlLabel(index='4')}

But I think I need to apply "loop restruturing" manually to know what to expect. Python doesn't have a goto, I don't think the code is equipped to handle a backedge that ends up in the middle of the loop somewhere.

[sklam]

I am changing the mockasm code so no branches have the same jump target on both side.

However, the assert len(diff) == 1 can trip on group like:

YAML:

"mock_block_0":
    jt: ["mock_block_5", "mock_block_8"]
"mock_block_2":
    jt: ["mock_block_3", "mock_block_4"]
"mock_block_3":
    jt: ["mock_block_4"]
"mock_block_4":
    jt: ["mock_block_5"]
"mock_block_5":
    jt: ["mock_block_3", "mock_block_6"]
"mock_block_6":
    jt: ["mock_block_8", "mock_block_9"]
"mock_block_7":
    jt: ["mock_block_2", "mock_block_11"]
"mock_block_8":
    jt: ["mock_block_9"]
"mock_block_9":
    jt: ["mock_block_7", "mock_block_2"]
"mock_block_11":
    jt: []

[sklam]

Tracking:

numba-rvsdg/numba_rvsdg/tests/test_mock_asm.py

Lines 270 to 273 in 371b3df

	# https://github.com/numba/numba-rvsdg/issues/48
	# failing seeds: [58, 153, 262, 275, 476, 607, 724, 742, 763, 824, 832, 928,
	# 930, 934, 945, 955, 984, 999]
	"assert len(diff) == 1",