Generate Duplicated NestedSDFGs only once

[TizianoDeMatteis]

PR for #392

First commit, so that we can iterate.

Goal: avoid generating 2+ times the same code for a NestedSDFGs that is used multiple times (which include also LibNodes after expansion)

Current implementation:

• we need to unequivocally identify SDFG. For the moment, I've added to the SDFG an additional property unique_name (type string, default empty)
• this is used in the code generator (CPU) to keep track of the already generated Nested SDFG. If we try to generate an already seen NestedSDFG, it will skip it
• there are two additional tests for checking that it works on CPU and FPGA (under the assumption that the topmost SDFG is scheduled on the CPU)

So, up to now, it is up to the user to specify the SDFG unique name. We would probably need something (in the configuration file?), to disable this.

Don't know why code coverage fails: the relative difference is 100%

[codecov]

Codecov Report

Merging #393 into master will increase coverage by 0.03%.
The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master     #393      +/-   ##
==========================================
+ Coverage   82.65%   82.68%   +0.03%     
==========================================
  Files         148      148              
  Lines       28335    28364      +29     
==========================================
+ Hits        23420    23452      +32     
+ Misses       4915     4912       -3     

Impacted Files	Coverage Δ
dace/codegen/targets/cpu.py	87.50% <100.00%> (+0.20%)	⬆️
dace/sdfg/sdfg.py	86.81% <100.00%> (+0.29%)	⬆️
dace/properties.py	77.07% <0.00%> (+0.14%)	⬆️
dace/transformation/interstate/transient_reuse.py	94.31% <0.00%> (+1.63%)	⬆️

---

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update d6dc3cf...8c15009. Read the comment docs.

[tbennun]

That might not be a good idea

[TizianoDeMatteis]

Thanks for spotting it. Some wrong editing!

[tbennun]

not sure why you'd want to put that in a condition, since above you skip the generation of the function

[TizianoDeMatteis]

global_code is created in one of the ifs above

[TizianoDeMatteis]

Also @tbennun : the unique_name property (set at the original SDFG name) is still used to generate the name for the function, otherwise it uses a combination of the name and various id to generate it. I don't like it too much.

The hashing is breaking multiple tests.
Probably the simplest one is softmax_test where there are two reduces, one with Sum and the other with Max, but in this way only one of the two is generated, therefore resulting in an error

[definelicht]

@TizianoDeMatteis I discussed this with Tal, and we think there's a pretty clean solution that will benefit the whole codegen (not just FPGA). We generate nested SDFGs bottom up instead of top down:

• When we serialize the SDFG before code generation, we will also hash each nested SDFG, and build a call graph for nested SDFGs, where nested SDFGs are uniquely identified by the hash of their string representation.
• Instead of starting from the top-level SDFG, we traverse the nested SDFG call graph backwards (reverse toppological order), and generate the SDFGs in this order.
• Whenever we encounter a nested SDFG while traversing, we simply replace this with a function call and return (the function has already been generated at this point).

[TizianoDeMatteis]

@definelicht @tbennun

I didn't quite get your proposals:

1. What is the rationale behind using a reverse topological order?
2. How to traverse NestedSDFG using that order: this seems to be different than how code is currently generated
3. Where should be placed the code for the Nested SDFG? Some additional file that will be then included/compiled together

Independently from this, we should decide how to hash (symbols are included? access nodes?...)

[tbennun]

@TizianoDeMatteis

1. I think the meaning was more "bottom up in the nested SDFG hierarchy"
2. The difference is we generate the nested-most SDFGs first, and then record that we have (so that we don't generate them again)
3. Where we always did, but move the code to generate the nested SDFG's "body" to the frame code generator.
4. In the discussion Johannes and I had, we found that while it would be beneficial to ignore connector/array names inside the nested SDFG, right now in our standard use case they're all going to be the same anyway. Thoughts/counter-arguments?

[TizianoDeMatteis]

@tbennun
Regarding 2: this still seems a different ordering wrt to what is currently used. IIRC now code is generated by following the topological ordering of the SDFG, while in this proposal we should first generate innermost components (that is the bottom of NestedSDFG hierarchy). But, I will probably have more precise questions when I will work on this

Regarding 4. Ok, I think is that the main problem could be related to symbols. But that (the way in which hashing is done) could be easily changed later on.

Another minor thing: the way in which function names for nested SDFG is generated must be changed as well.

[TizianoDeMatteis]

We should decide whether to have a configuration to enable/disable this behavior. Maybe be useful especially for FPGAs, where we explicitly want to generate duplicated code

[tbennun]

One (not so) minor comment

[tbennun]

@TizianoDeMatteis if it's done and passing all tests, make sure it's not WIP and re-tag me for review. looks like some minor documentation updates