State Fusion ignores RW dependencies due to Memlets

[alexnick83]

Sample code demonstrating the issue:

    i = dace.define_local_scalar(dace.int32)
    i = 0
    while i < N:
        do_something(A[i], B[i])
        i += 1

The frontend will generate two states for the body of the while loop, one for the do_something statement, and one for i += 1. There is a read/write dependency on the value of i between the two states. However, because the dependency is in the Memlets for A and B, StateFusion does not check for it and instead fuses the two states.

Potential solutions:

• Fix StateFusion to check for such dependencies. (preferable?)
• Make somehow i a special iteration variable, or perhaps make i += 1 an assignment in the interstate edge.

[tbennun]

In StateFusion (or at least in one of the redundant state removal transformations) there is a TODO there to check if the assigned value is used in the state, and if so bail. Perhaps we should complete that TODO...

[tbennun]

@alexnick83 This issue is stranger than I initially thought. It seems that i is accessed directly in the memlet, which is supposed to be disallowed since i is a scalar and not a symbol:

[alexnick83]

@tbennun If we disallow using data in memlet subsets, how do you suggest that a while loop should be implemented then in SDFG?

[tbennun]

in other frontends, we use interstate edges for this. I don't know what would be the easiest solution in the python frontend though.

[alexnick83]

@tbennun I feel that this is too restrictive. Fundamentally, the loop guard evaluates some boolean expression. Shouldn't it possible for the user to use whatever he/she wants in this expression (symbols, numbers, data)? I have actually fixed this for if-conditions. The visitor checks if the test is a comparison node with a subscript expression (therefore memlet). In such a case, it generates the necessary computation subgraph in the guard state and uses the (boolean) result in the interstate edges. For whatever reason, I didn't do the same for while loops. I will fix it in the next few days and push to python-frontend-docs. Note that this will not change the SDFG for the code above, because i is scalar and no memlet expression is needed to access it. It is easy to change that, though, if it would be the correct approach. What do you think?

[tbennun]

It will fix at least some of the problem. The issue with accessing scalars is that memlets and subsets are supposed to refer to expressions that are not going to change throughout a state (i.e., only contain symbols) or a scope they are defined in, and accessing through a scalar, which can change, violates that.

In your opinion, do we need to discuss that part of the representation further, or just say that every scalar defined in Python code and used in subsets is promoted automatically to a symbol upon parsing? In the latter case, assignments will then be interpreted to interstate edges and uses in memlets will be fine (with your while-loop fix, it will look exactly as we want it to)

[alexnick83]

I only don't get the "scalars promoted to a symbol" part. Does this mean that we accept symbols and scalars (e.g., boolean scalars) in interstate edges, or that the scalar to be used in the interstate edge must become a symbol? If it is the latter, we should discuss the implementation (can we actually set a symbol's value through a Tasklet?). If it is the former, then I believe that all is clear.

[tbennun]

@alexnick83 I think this is fixed now (except for the while expression part, I guess)