Guys,
regarding alloca.
not only are exceptions a problem here, but just plain old “longjmp”.
-Peter Lawrence.
Guys,
regarding alloca.not only are exceptions a problem here, but just plain old "longjmp".
Yes,
On IRC Sanjoy pointed out that it should be possible to handle this by changing longjmp. I am not sure it can be done in general. The alloca might have been called a dynamic number of times for example.
In fact, now that I think of it, the presence of longjmp pretty much forces a model where stacklets are not deallocated on return, just reused if stack grows again.
We discussed the use of allocas a bit in the rust channel. One idea that came out was that maybe we only need to support the "simple" case of allocas that are in the entry bb. That would still be a bit nasty as finding that size this late in the pipeline would not be trivial.
I think my suggestion for now would be to not support frames with allocas and afterwards, if time allows, we can add a llvm intrinsic that tells the codegen how much stack will be used by dynamic allocas. That way a FE that really wants split stacks and really wants dynamic allocas could write something like
define void @foo(i32 a, i32 b) {
%how_much_dynamic_space_this_frame_needs = add i32 %a, %b
llvm.dynamic_alloca_use(%how_much_dynamic_space_this_frame_needs)
%x = alloca i8, i32 a;
%y = alloca i8, i32 b;
....
}
-Peter Lawrence.
Cheers,
Rafael
Sorry for the delay in responding.
Guys,
regarding alloca.not only are exceptions a problem here, but just plain old "longjmp".
Yes,
On IRC Sanjoy pointed out that it should be possible to handle this by
changing longjmp. I am not sure it can be done in general. The alloca
might have been called a dynamic number of times for example.In fact, now that I think of it, the presence of longjmp pretty much
forces a model where stacklets are not deallocated on return, just
reused if stack grows again.
Perhaps only longjmp/exception throws need to not free stacklets- returns still do.
Segmented stacks are exciting to me, but only if the stacklets can be freed. Here's why: if segmented stacks allow for "infinite" stacks, tail call optimization becomes a lot less important in functional languages- still useful, but not live or die.
For example, the natural way to implement the map function over lists is:
let rec map f lst =
match lst with
> x :: xs -> (f x) :: (map f xs)
> ->
;;
Interestingly enough, this is also the fastest implementation of map. But it's not tail recursive- which means if you pass in a list long enough, you run out stack space and your program blows up. So you end up writing a much more complicated version which is also slower, but which is tail recursive.
I'd love to have virtual infinite stacks- stacks which expanded as needed, but got freed when no longer needed. That means being tail recursive goes back to being nice, not necessary.
Just my $0.02.
Brian
We discussed this on IRC a while ago. IMHO it is good enough if the
stack segments are kept in a double linked list and the allocation
callback (slow path!) checks if the current segment is the last. If it
isn't, it can reuse the next segment and free all others.
Advantage is that longjmp/setjmp and stack unwinding functions just
work. Function exit doesn't have to do any checks either, so it is
faster. Down side is that a deep recursion followed by code not using
much stack will keep the unused stack around potentially for ever.
Joerg
Perhaps there can be a function that can be called to trim the stack (keep 1 segment and free the rest)? This could then be called occassionally- say, at the start of a GC pass.
Brian
Perhaps there can be a function that can be called to trim the stack (keep
1 segment and free the rest)? This could then be called occassionally-
say, at the start of a GC pass.
That sounds like a good idea, especially if a managed language (like Go)
is being compiled to LLVM IR. Also, should be rather straightforward to
implement.