implement "dynamic drop" semantics using flags on the stack rather than zeroing

[thestinger]

(Tracking issue for RFC 320.)

Original Description

The current liveness check has a concept of "alive" and "maybe dead", so I'll just describe this in terms of a hypothetical "move optimization pass" (although liveness can probably be extended with "surely dead").

Hypothetical move optimization pass:

In each scope where they exist, all variables are given an associated boolean representing whether they were certainly moved from. Moving from a variable in a scope marks it as such for that scope. This can be bubbled up if and only if the variable is also moved from in every other branch.

If the compiler can bubble this up to the scope where the variable is declared, the drop glue can be omitted and all moves from that variable do not need to zero it.

This can probably be extended to fields too, but I'm not sure on what the semantics would be.

@nikomatsakis: does this look like something that would be reasonable to implement (probably as part of liveness)? It doesn't actually need to bubble it up to be useful - even if it only worked in a local scope, it would allow the destructor of the save variable in the TreeMap split and skew functions to be omitted (since it's moved from in the same scope where it's declared) and that would be a big performance win.

[nikomatsakis]

This seems doable and straightforward. It's basically adding another bit to track per variable ("was moved") which uses intersection on join when propagating.

However, there is another approach that @pcwalton and I have toyed with from time to time, which is saying that when you move things, the destructor for the moved thing runs "early"---basically at the point where control flow on the non-moved path (if any) rejoins the control flow from the moved path. The idea here was to remove the need to zero 100% of the time. However, I am not sure if that idea (early destructing) is such a good idea, because it seems hard to specify and predict, whereas the current semantics (destructors run at the same time unless moved) is easier.

So if we keep current semantics, then I think something like this seems like a good optimization. In principle we could do better and identify nodes in the CFG where, upon entering the node, we know the value will be moved (this is what liveness will be computing, actually). Then we could avoid zeroing as long as we dominate the node. That might be trickier though given the way failure and unrolling works, so maybe it's better to only optimize the case where the variable declaration is such a node.

[graydon]

http://llvm.org/docs/LangRef.html#llvm-lifetime-end-intrinsic may also be interesting

[catamorphism]

Nominating for milestone 1, well-defined.

[graydon]

Accepted for well defined. This needs to be documented.

[glaebhoerl]

I don't think the alternative would necessarily be harder to specify and predict. It's basically dynamic vs. static transfer of ownership. With the current rule, a variable's destructor is run at the end of the scope it was declared in, unless ownership of it was dynamically transferred to an inner scope. With the alternative rule, referring to the variable in an inner scope statically transfers ownership of it to that inner scope. The compiler already uses the latter rule to determine when a variable is legal to access, so the programmer has to think about it (if not, the compiler will make her). The alternative would make destructors follow the same rules. Currently you can have points in the code where the compiler won't let you access a variable but the variable's destructor may not have been run, which might be unintuitive itself.

[nikomatsakis]

Current plan (based on meeting discussion) is to have the compiler issue an error if there are ever two control flows that meet where one does a move and the other does not, so that this issue becomes a moot point. I am in the process of preparing a pull request taking some steps in this direction.

[nikomatsakis]

I'm somewhat working on this, btw. Also, it will affect the semantics of what moves are legal, particularly around vectors, since in those cases the compiler will not be able to determine statically which indices have been moved and which have not. I imagine we'll just disallow moves from like let x = vec[y] and instead offer a method like let x = vec.move(y) where move is a fn(self) method.