[Release 1.0] FuseStates collapse wrong edge + undefined behavior

[FlorianDeconinck]

Hunting for a bad write in our model we discovered that DaCe had swapped two maps order with no data dependency. This was tracked down to FuseStates misbehaving. While reproducing, the error was fickle, disappearing easily - we rebuild a partial reproducer showing the bug and showing a determinism issue with the pass.

Fuse States issue

The original SDFG looks like this (file attached below)

Block_3 has q has an input
Block_5 has q has an output
Block 3 and 5 are effectively not sharing data dependency (output of 3 is not used in 5) but the order of blocks matter since this is a write-after-read situation.

When FuseStates applied (see beloew) FuseStates produces a single Block:

instead of two:

Lack of determinism

Using the attached unsimplified.sdfg.txt as the input

This simple script should reproduce the above

import dace
from dace.transformation.passes.fusion_inline import FuseStates


def f():
    sdfg = dace.SDFG.from_file("./unsimplified.sdfg")
    ret = FuseStates().apply_pass(sdfg, {})
    print(f"Fuzed state: {ret}")
    return 0


if __name__ == "__main__":
    f()

Will print 7 if the error shows BUT could be printing 6 if the error magically doesn't show.

Wrapping into a simple bash should show the issue

#!/bin/bash

for i in {1..10}
do
    python code_dace.py
done

[FlorianDeconinck]

First quick look shows that this code in StateFusion.can_be_applied

                # If we have potential candidates, check if there is a
                # path from the first write to the second write (in that
                # case, there is no hazard):
                for cand in write_write_candidates:
                    nodes_first = [n for n in first_output if n.data == cand]
                    nodes_second = [n for n in second_output if n.data == cand]

                    # If there is a path for the candidate that goes through
                    # the match nodes in both states, there is no conflict
                    if not self._check_paths(
                        first_state,
                        second_state,
                        match_nodes,
                        nodes_first,
                        nodes_second,
                        second_input,
                        False,
                        False,
                    ):
                        return False
                # End of write-write hazard check

Is (sometimes) not triggered leading to the bad merge

[FlorianDeconinck]

Fix on: https://github.com/FlorianDeconinck/dace/tree/fix/v1/state_fusion_check_all_paths

Unit tests to follow before PR

[FlorianDeconinck]

Partial PR #1954 (no new unit tests)