Nested SDFGs reduce either readability or optimization capability

[tbennun]

Background

Nested SDFGs were added at a time that the SDFG IR did not have Views and References. Thus, they served both as a way to introduce control flow inside dataflow scopes (i.e., map/consume) and reshape/offset/reinterpret data containers. This dual use is no longer relevant and it is detrimental to working with DaCe.

Problem Setting

Consider the following simple program:

@dace.program
def sample(A: dace.float32[M + 3, N], ind: dace.int32[M, N]):
    for i, j in dace.map[1:M, 2:N]:
        A[3 + i, 4 + ind[i, j]] += 1

The resulting SDFG looks like:

Issues

1. ind[i, j] correctly appears on the outside of the nested SDFG. However, the __tmp_* internal data containers are named in a confusing manner, and the internal index is [0], which loses the ability to understand, at O(1) time, what address is directly pointed at.
2. The outgoing memlet has the data-dependent index (2nd dimension) internally, which is as expected. However, the other half of the index is also in the nested SDFG, which creates a very over-approximated range of [0:i+4] on the outside. This makes analysis harder, but also transformations such as LocalStorage impossible.
3. The behavior is also inconsistent with the map outside, as the index may repeat inside and outside the map via propagated memlets (and still yield an analyzable expression), but that is not the case for the nested SDFG control flow region.
4. There are other invisible issues here, for example, the symbol mapping in the nested SDFGs can lead to confusion if they are mapped in certain ways (e.g., N (external) ->M (internal) and M (external) -> N (internal), which creates undue stress on transformation authoring and analysis checks.

Proposal

Change nested SDFG semantics in the following manner:

• Memlets going into and out of a nested SDFG behave as if they are going to a scope via a passthrough connector. This means no offsetting in the code generation and only a union operation in memlet propagation.
• Nested SDFGs will not have their own descriptor repositories (i.e., arrays, symbols, constants, callbacks), and will instead share theirs with their parent.
  • Squeezing and unsqueezing memlets will no longer be necessary.
  • The symbol_mapping property of NestedSDFG will no longer exist.
• Nested SDFGs will contain a ControlFlowRegion instead of a fully-fledged SDFG object.

The changes will be made to code generation, memlet propagation, the add_nested_sdfg method (which will adapt the nested SDFG to its new parent), and all built-in transformations and passes that deal with nested SDFGs.

We will not lose any representational power (as the same can be achieved with Views), and gain both readability and analyzability.

The only aspect lost is the ability to save a nested SDFG as its own separate unit. However, External SDFGs (i.e., #1671) will enable this functionality as necessary.