Clone Detection

The core of the cone detection algorithm is a data-flow analysis to identify multiple dynamic writes that each take as input the same array value. What we really want is path-sensitive linear types, but we're not doing that, so what we have instead is a path insensitive data-flow analysis with a decent enough conservative approximation.

The lattice value is the set of nodeID that have been used, the two nodes of interest are phi and writes; phis insert their arguments to the use set and remove their output from the used set, but do not indicate a clone if their argument is already in the used set. For writes, we add their array argument to the used set and remove their output from the used set and indicate a clone if their array argument is already in the used set. This just determines which writes are offending, further analysis is required to determine where to place the clone, what writes are offending with respect to what other writes, etc.

See photos: https://drive.google.com/file/d/1_Mvpss_3nvJ2lSemlhZhQTlFZM8f3ESH/view?usp=sharing

Amendment - phis may induce a clone (more precisely, are "problematic", the clone still needs to happen in the lowest common dominator) if on a particular input block, the used set overlaps with the phi's use from the branch. In this sense, only phis are path sensitive.

mentioned in issue #6 (closed)

Further amendment: multiple uses of an array value inside of a fork-join should not induce a clone just outside the fork-join as in a loop, but rather should induce an extra dimension on the array allocation. i.e. if I have a fork(8) which writes to, but doesn't reduce over, an array of dimension (4, 4), the array should actually be allocated with dimension (8, 4, 4)

@aaronjc4, we need to consider how to handle array writes inside fork-joins where the array doesn't get reduced over. a straight dataflow analysis is not enough since there's no backedge in the fork-join to carry the array value use info upwards. maybe this is a separate analysis to find writes that depend on thread id but not on reduce inside fork-joins, and these are always "problematic"?

Good point. It seems to me that the issue arises for any write (or at least any write at an thread-id dependent index) to an array whose source is not a reduce (i.e. if you track the array value back through the series of phi/write nodes you should eventually reach a reduce or the write is "problematic"). It might just be its own analysis, as otherwise the dataflow analysis would have to handle forks in a special way (which might be a possible alternative).

Some writes that don't depend on thread-id could also be an issue if there's a read of the array within the fork before the write, if all threads share the same version of the array then we'd have to synchronize them to ensure everything executes the read before any thread executes the write.

Closing this issue since the hard part is resolved by !99 (merged), and the fork-join case is well understood.

closed