CFG analysis does not handle properly SDFGs with structurally inaccessible states
- Dominant language
- Python
- Stars
- 593
- Forks
- 163
- Avg merge
- 2d 23h
- Merged PRs (30d)
- 60
Description
There are some changes from DaCe [v0.16 to v0.16.1](https://github.com/spcl/dace/compare/v0.16...v0.16.1) especially in the CFG analysis that appear to be incompatible with SDFGs that have structurally inaccessible states. There is a workaround involving calling DeadStateElimination first to remove those states so that they don't cause issues in subsequent passes.
The error I get is the following:
```
_external_src/gt4py/src/gt4py/next/program_processors/runners/dace_iterator/__init__.py:302: in build_sdfg_from_itir
sdfg.simplify()
_external_src/dace/dace/sdfg/sdfg.py:2384: in simplify
return SimplifyPass(validate=validate, validate_all=validate_all, verbose=verbose).apply_pass(self, {})
_external_src/dace/dace/transformation/passes/simplify.py:113: in apply_pass
result = super().apply_pass(sdfg, pipeline_results)
_external_src/dace/dace/transformation/pass_pipeline.py:547: in apply_pass
newret = super().apply_pass(sdfg, state)
_external_src/dace/dace/transformation/pass_pipeline.py:502: in apply_pass
r = self.apply_subpass(sdfg, p, state)
_external_src/dace/dace/transformation/passes/simplify.py:90: in apply_subpass
ret = p.apply_pass(sdfg, state)
_external_src/dace/dace/transformation/passes/constant_propagation.py:141: in apply_pass
internal = self.apply_pass(node.sdfg, _, const_syms)
_external_src/dace/dace/transformation/passes/constant_propagation.py:141: in apply_pass
internal = self.apply_pass(node.sdfg, _, const_syms)
_external_src/dace/dace/transformation/passes/constant_propagation.py:72: in apply_pass
per_state_constants: Dict[SDFGState, Dict[str, Any]] = self.collect_constants(sdfg, initial_symbols)
_external_src/dace/dace/transformation/passes/constant_propagation.py:196: in collect_constants
for state in optional_progressbar(cfg.stateorder_topological_sort(sdfg), 'Collecting constants',
_external_src/dace/dace/cli/progress.py:55: in optional_progressbar
for counter, elem in enumerate(iter):
_external_src/dace/dace/sdfg/analysis/cfg.py:296: in stateorder_topological_sort
ptree = state_parent_tree(sdfg, loopexits)
_external_src/dace/dace/sdfg/analysis/cfg.py:87: in state_parent_tree
for be in back_edges(sdfg, idom, alldoms):
_external_src/dace/dace/sdfg/analysis/cfg.py:67: in back_edges
return [e for e in sdfg.edges() if e.dst in alldoms[e.src]]
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
.0 =
> return [e for e in sdfg.edges() if e.dst in alldoms[e.src]]
E KeyError: SDFGState (join)
_external_src/dace/dace/sdfg/analysis/cfg.py:67: KeyError
```
Workaround code (thanks to @alexnick83), before applying simplify to the corresponding SDFG:
```
import dace
from dace.transformation.pass_pipeline import Pipeline
from dace.transformation.passes import DeadStateElimination
sdfg = dace.SDFG.from_file('sdfg_before_simplify.sdfg')
my_pipeline = Pipeline([DeadStateElimination()])
for sd in sdfg.all_sdfgs_recursive():
my_pipeline.apply_pass(sd, {})
```
I have attached the SDFG that causes this issue. While for DaCe v0.16 everything works as expected, for DaCe v0.16.1 I get the error above.
[sdfg_v0.16_after_simplify.json](https://github.com/user-attachments/files/16441582/sdfg_v0.16_after_simplify.json)
[sdfg_v0.16_before_simplify.json](https://github.com/user-attachments/files/16441584/sdfg_v0.16_before_simplify.json)
[sdfg_v0.16.1_before_simplify.json](https://github.com/user-attachments/files/16441585/sdfg_v0.16.1_before_simplify.json)
cc: @alexnick83
Contributor guide
Research direction
Start with dace/sdfg/analysis/cfg.py, especially state_parent_tree and back_edges, then follow the call from constant_propagation.py during simplify.py. Reproduce the KeyError on the attached sdfg_v0.16.1_before_simplify.json with DaCe v0.16.1 and compare behavior with v0.16. Done means CFG analysis and simplify handle structurally inaccessible states without requiring DeadStateElimination first.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100