Here is example #1:
iterator doStuff(): seq[int] {.closure.} =
var x = @[1, 2, 3]
echo cast[uint](addr x[0])
yield @[] # <- breaks things
yield ensureMove x
proc main() =
var it = doStuff
var x: seq[int]
while not finished(it):
x = it()
if x.len > 0:
echo cast[uint](addr x[0])
main()
var storage {.threadvar.}: seq[int]
iterator doStuff(): void {.closure.} =
var x = @[1, 2, 3]
echo cast[uint](addr x[0])
yield # <- breaks things
storage = ensureMove x
proc main() =
var it = doStuff
while not finished(it):
it()
echo cast[uint](addr storage[0])
main()These programs compile if the offending lines are commented.
This stuff is relevant for async backends, as it causes spurious copies. Calling move explicitly helps, but isn't very convenient. Can this be improved, or is there something special about iterators that makes the control flow analysis very hard or impossible?
The problem is not with control-flow analysis. Rather, no non-destructive move (what you're requesting with ensureMove) can be performed if the source is a pointer indirection.
The underlying problem is that the phase ordering is wrong (depending on your perspective): destructor injection (which injects =destroy calls) and move analysis (which turns copies into moves, resolves ensureMove, turns assignments into =copy and =sink calls, and some other things) happen after closure iterator transformation.
This ordering is an issue due to how closure iterator lowering/transformation (responsible for turning the closure iterators into normal procedures) work. Conceptually, the body is split into multiple continuations, which each yield turned into a return that also sets the next continuation to run when the iterator is resumed. All locals used in a continuation other than the one they're created in are lifted into the iterator's environment, which is a heap-allocated, ref-counted object passed around with the iterator instance.
In practice, the compiler uses a case dispatcher and while loop to implement the continuations. For example, this is what your first doStuff iterator is transformed into (as reported by macros.getImplTransformed):
iterator doStuff(:envP): seq[int] {.closure.} =
# note: `:envP` is of type `ref object`
while true:
block :stateLoop:
case :envP.`:state`
of 0:
var :envP.x1 = @[1, 2, 3]
echo [cast[uint](addr(:envP.x1[0]))]
:envP.`:state` = 1
return []
of 1:
:envP.`:state` = 2
return ensureMove :envP.x1
of 2:
:envP.`:state` = -1
break :stateLoop
else:
returnAs you can see, ensureMove is now used with :envP.x, which is a location coming from a pointer indirection. These are not non-destructively movable from without leaving the source in a potentially observable unknown state, hence the ensureMove reporting an error.
Also note that the current phase ordering means that the observable lifetimes of locals may change. That is, they may be destroyed in an order that's not the usual inverse definition order. Example:
iterator test(): int {.closure.} =
var a = @[1, 2, 3]
var b = @[4, 5, 6]
yield 0
echo b[0]Cool, thanks for the explanation! Everything makes sense now.
Do you have any thoughts on how to enable lifetime analysis for iterators? If my intuition is correct, yield statements are equivalent to function calls (yield(yielded: sink T)) from the point of view of local variable lifetime analysis. So in principle the existing machinery could be used to inject the moves before the transformation.
Do you have any thoughts on how to enable lifetime analysis for iterators?
It is enabled for iterators (though only indirectly for .inline iterators) -- it just happens too late. For example, the following compiles and runs just fine:
iterator test(): int {.closure.} =
let x = @[1, 2, 3]
let y = ensureMove x
# `x` is not live across continuations and thus stays a "real" local
yield y[0]
var iter = test
doAssert iter() == 1If my intuition is correct, yield statements are equivalent to function calls (yield(yielded: sink T)) from the point of view of local variable lifetime analysis.
Your intuition is almost correct. What's missing is that yield also invalidates the state of all parameters, which the current data-flow analysis also considers locals. There's also an additional consideration regarding locals with destructors, but more on that later.
You're also correct in that the existing machinery (the injectdestructors.nim, dfa.nim, and optimizer.nim modules of the compiler) can be used to inject the moves (among other things) before the closure iterator transformation, at least in theory.
In theory, one only needs to apply the injectedestructors pass (which implements move analysis and destructor injection) before the closureiters pass (which implements the closure iterator transformation) and update data-flow analysis to handle the nkYield statement.
There are some complexities in practice, however. From the top of my head:
Destructor injection also needs to consider to-be-lifted variables, which it cannot inject destructors normally for anymore, at least not without a subsequent wasMoved call to disarm the destructor call happening as part of the environment object's destructor.
Finally, as I've hinted at earlier, yield (return too) needs to be understood by optimizer (the module implementing the wasMoved elimination) to be a destructor call on an unknown location, so that the wasMoved call in, e.g.:
var y = ...
...
=sink(x, y)
wasMoved(y)
yield
discard y # y exists across continuations