Objects with non-primitive fields #52

New Issue

pca006132 · 2021-10-06T10:30:40+08:00

pca006132 commented

2021-10-06 10:30:40 +08:00

For objects with non-primitive fields, if we do alloca inside the constructor, the fields will become dangling pointers once we exit the constructor.

Example:

class Foo:
    a: int32
    
    def __init__(self, a: int32):
    	self.a = a
        
class Bar:
    foo: Foo
    
    def __init__(self, a: int32):
    	# alloca here, dangling pointer after return
    	self.foo = Foo(a)

I can think of three ways to fix this:

Inline the constructors.
Use trampoline to make sure that every call is a tail call, thus they can run in the same stack frame.
Pass the field pointers as an implicit argument into the __init__ function, allocate them in the caller. Note that the field pointer list should include all allocations needed in the constructor, not only the object's fields, but fields of fields etc.

For objects with non-primitive fields, if we do `alloca` inside the constructor, the fields will become dangling pointers once we exit the constructor. Example: ```python class Foo: a: int32 def __init__(self, a: int32): self.a = a class Bar: foo: Foo def __init__(self, a: int32): # alloca here, dangling pointer after return self.foo = Foo(a) ``` I can think of three ways to fix this: 1. Inline the constructors. 2. Use trampoline to make sure that every call is a tail call, thus they can run in the same stack frame. 3. Pass the field pointers as an implicit argument into the `__init__` function, allocate them in the caller. Note that the field pointer list should include all allocations needed in the constructor, not only the object's fields, but fields of fields etc.

pca006132 commented

2021-10-08 22:46:05 +08:00

@sb10q What do you think?

sb10q commented

2021-10-09 12:03:37 +08:00

I suppose those __init__ and classes should be decorated with @kernel.

Inlining the constructors (1) seems fine and something not too unusual (many existing compilers have ways to force inlining of functions).
The others seem complicated - do they have clear advantages?

I suppose those ``__init__`` and classes should be decorated with ``@kernel``. Inlining the constructors (1) seems fine and something not too unusual (many existing compilers have ways to force inlining of functions). The others seem complicated - do they have clear advantages?

pca006132 commented

2021-10-09 14:59:53 +08:00

I suppose those __init__ and classes should be decorated with @kernel.

Inlining the constructors (1) seems fine and something not too unusual (many existing compilers have ways to force inlining of functions).
The others seem complicated - do they have clear advantages?

Inlining would not support recursive references, and the instructions required can be exponential (consider A contains 2 B, B contains 2 C, etc.).

> I suppose those ``__init__`` and classes should be decorated with ``@kernel``. > > Inlining the constructors (1) seems fine and something not too unusual (many existing compilers have ways to force inlining of functions). > The others seem complicated - do they have clear advantages? Inlining would not support recursive references, and the instructions required can be exponential (consider A contains 2 B, B contains 2 C, etc.).

LPTK commented

2021-11-08 18:50:10 +08:00

I agree inlining is not a satisfactory solution. We'd still have the problem for all other functions, and there's no particular reason to have special treatment for constructors. E.g.:

class Bar:
    foo: Foo
    def baz(self, a: int32):
    	self.foo = Foo(a)

In my opinion, the best way to solve this is to do a quick static analysis to know where things should be allocated. Even if we don't go all the way to proper region-based memory management, we can still do a simplified region analysis that would tell us, here, that since it's stored in self.foo, the Foo(a) allocation should outlive the call to baz (or __init__).
To keep it simple and avoid having to support dynamic regions (since we don't want to change the runtime for now), we could require that there should be a statically bounded number of escaping allocations – so all allocations performed in loops should remain strictly local to the loop.
Each function would take an array arr of adresses as a parameter, write its first escaping value into arr[0], etc. The analysis would keep track of the assigned stack regions of all manipulated data and their fields, allocating the stack spaces in the right places, and passes the corresponding addresses through the array parameter.
Recursive functions containing escaping allocations would be disallowed, similarly to loops.

I don't see how the "tail-recursion through trampolines" idea would work. Trampolines require allocating some sort of closure capturing the current context, so that does not really seem to solve the problem.

On the other hand, what we could do is a CPS transformation of the whole program. Assuming users don't use non-tail recursive functions, this would allow allocating everything on the stack safely. But we'd still need to make sure allocations performed in loops don't leak out of the loop. And making the CPS code perform well would require a later defunctionalization pass, which is complictaed to implement. So I don't think it's a very attractive option.

I agree inlining is not a satisfactory solution. We'd still have the problem for all other functions, and there's no particular reason to have special treatment for constructors. E.g.: ```py class Bar: foo: Foo def baz(self, a: int32): self.foo = Foo(a) ``` In my opinion, the best way to solve this is to do a quick static analysis to know where things should be allocated. Even if we don't go all the way to proper region-based memory management, we can still do a simplified region analysis that would tell us, here, that since it's stored in `self.foo`, the `Foo(a)` allocation should outlive the call to `baz` (or `__init__`). To keep it simple and avoid having to support dynamic regions (since we don't want to change the runtime for now), we could require that there should be a statically bounded number of escaping allocations – so all allocations performed in loops should remain strictly local to the loop. Each function would take an array `arr` of adresses as a parameter, write its first escaping value into `arr[0]`, etc. The analysis would keep track of the assigned stack regions of all manipulated data and their fields, allocating the stack spaces in the right places, and passes the corresponding addresses through the array parameter. Recursive functions containing escaping allocations would be disallowed, similarly to loops. --- I don't see how the "tail-recursion through trampolines" idea would work. Trampolines require allocating some sort of closure capturing the current context, so that does not really seem to solve the problem. On the other hand, what we _could_ do is a CPS transformation of the whole program. Assuming users don't use non-tail recursive functions, this would allow allocating everything on the stack safely. But we'd still need to make sure allocations performed in loops don't leak out of the loop. And making the CPS code perform well would require a later defunctionalization pass, which is complictaed to implement. So I don't think it's a very attractive option.

sb10q commented

2021-11-10 11:34:28 +08:00

@LPTK Strictly speaking you are correct. But creating objects on the device is a bit of an advanced feature (old compiler doesn't support it at all) and restrictions such as being able to store them in fields only in constructors would be acceptable.

Anyway we can explore what you propose.

@LPTK Strictly speaking you are correct. But creating objects on the device is a bit of an advanced feature (old compiler doesn't support it at all) and restrictions such as being able to store them in fields only in constructors would be acceptable. Anyway we can explore what you propose.

LPTK commented

2021-12-21 16:47:26 +08:00

See related issue: #51

See related issue: https://git.m-labs.hk/M-Labs/nac3/issues/51

sb10q added the

high-priority

label 2021-12-21 18:52:05 +08:00

pca006132 was assigned by sb10q

2021-12-21 18:52:19 +08:00

pca006132 commented

2022-03-31 10:27:33 +08:00

if constructed via constructor: local object
otherwise: non-local object (including object fields)
for non-local objects: prohibit assigning non-global objects to non-local object's fields

if constructed via constructor: local object otherwise: non-local object (including object fields) for non-local objects: prohibit assigning non-global objects to non-local object's fields

sb10q added this to the Alpha milestone 2022-03-31 10:29:18 +08:00

pca006132 was unassigned by sb10q

2024-06-20 15:48:55 +08:00

Sign in to join this conversation.