spcl / spcl/dace

CFG analysis does not handle properly SDFGs with structurally inaccessible states

Open
#1,625 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.