Do some basic escape analysis

[alexnask]

We should be able to determine if the lifetime of an object is local and stack allocate it if it is.

This should only be done for objects that are created from an auto-generated new method and that do not define a custom destroy function, to prevent breaking of gc=off programs and covers from C types that define custom new methods.

In addition to that, it should be an opt-in flag, since there could be programs that would blow up the stack with huge objects and an annotation to turn it off for specific objects should be nice.

I realize that this is quite a complicated feature but it would be really beneficial (imho) and it would provide a nice starting point if we ever want to implement a more advanced RAII/lifetime system (which I doubt we ever would)

[fasterthanlime]

You're asking for trouble :)

[alexnask]

I remember some ooc manual saying that the compiler decides whether the object is stack or heap allocated, so it is (or was) in the language "specs" too :P

Here is a basic case that would be covered, as well as the ideally generated code:

f: func {
    foo := Foo new(42)
    foo doSomeNoneEscapingTask()
}

// Becomes
f: func {
    fooTemp: Foo_struct // Foo_struct is the actual C struct
    foo := (fooTemp& init(42), fooTemp& as Foo)

    foo doSomeNoneEscapingTask()
}

This would obviously work for objects created on the fly (in function arguments etc), if they are deemed to be non-escaping

[fasterthanlime]

I think what ultimately discouraged me to even attempt doing this (apart from the fact that there were so many other fires to put out) was that we would then have to annotate every function with 'pure' or not, and sometimes it gets pretty hard to tell

[alexnask]

Walking into the functions the object is passed to and seeing if it is ever copied into a non-local object/thing (C/ooc array, etc) should work.

If we ever get to a C function this is were a pure(/some other) annotation would be needed in order to make it work but without it, it would be enough to say the object does escape (safest case).

This also works with generics because when we get to a memcpy call the object is automatically deemed as escaping (for memcpy, we would even need more than a pure annotation for actual escape analysis, since we would need to see if the destination argument itself is local)

[alexnask]

Actually, I assume "pure" would mean "no side effects", which is a superset of the annotation we would need (something like noescape(argument)) but as I said, I have no intention of diving that deep.

[fasterthanlime]

This also works with generics because when we get to a memcpy call the object is automatically deemed as escaping

So all generic values escape.. hey, feel free to try it in a branch, after all I did implement generic inlining in a branch too for a semester project! Just make sure it doesn't break everything :)

[alexnask]

Yes (unless memcpy is special), which is inconvenient but taking this step by step, a little work at a time seems like the way to go.

Generics are a great complication for most features, tackling them head on in escape analysis would be suicidal ;)

[alexnask]

I'll be writing down some pen and paper stuff and starting up some code soon (tm).

Hopefully I can make it stable enough (maybe? :P) to make an experimental flag out of it.
I'm really curious about how many non-escaping objects would be detected in rock and if I can manage to bootstrap with escape analysis.

[vendethiel]

FWIW, Dlang has explicit constructs for that:

void foo(scope int a) { 
 // a is forbidden from going out foo's scope,i.e. being assigned globally
}

void foo() {
  scope int a;
  // a is allocated on the stack. ^ that's deprecated though, now...
}

[alexnask]

Huh, that would actually also a be a good way to explicitly annotate escape analysis and thus object stack allocation (even when the switch is off, with a warning in that case)

Also a good way to make sure stack allocated variables (even non-Object, non "escapable" values) don't accidentally escape.

[vendethiel]

glad it looks useful :). (fwiw, the last use of "scope" in D is scope guards, i.e. scope(exit) destroyResource() and scope(debug) printMsg())

[alexnask]

I'm aware of scope exits (and how they can be replicated in c++ :P) and I do like the concept but let's go one step at a time :)

[vendethiel]

They're relying on RAII in c++, so a bit less straightforward (passing a lambda to a new instance of ... Blabla), but you're right

[alexnask]

Well, I would expect the C++ compilers to be able to optimize the Scope object + lambda combinations to pretty much the same code that D generates but, yeah, a little less elegant to say the least :)