Comment by pcwalton | Hacker News Reader

Comment by pcwalton | Hacker News Reader

Parent Full thread

That part of the interview is incorrect about LLVM. I implemented segmented stacks via LLVM for Rust. It's actually pretty easy, because there is support for them in X86FrameLowering already (and it was there at the time of Go's release too). If you enable stack segmentation, then LLVM emits checks in the function prolog to call into __morestack to allocate more stack as needed. (The Windows MSVC ABI needs very similar code in order to support _chkstk, which is a requirement on that platform, so the __morestack support goes naturally together with it.)

Actually, getting GDB to understand segmented stacks was harder than any part of the compiler implementation. That's independent of the backend.

What I think the author might be confusing it with is relocatable stacks. That was hard to implement at the time, because it requires precise GC, though Azul has implemented it now in LLVM. Back then, the easiest way to implement precise GC would have been to spill all registers across function calls, which requires some more implementation effort, though not an inordinate amount. (Note that I think the Plan 9 compiler does this anyway, so that wouldn't be a performance regression over 6g/8g.) In any case, Azul's GC support now has the proper implementation which allows roots to be stored in registers.

> is incorrect about LLVM.

He didn't say it was not possible, but that it would have required too much effort in modifying the ABI and the garbage collector.

> because it requires precise GC

Which is why they avoided LLVM for a much smaller and easier to manipulate existing compiler. Their point is that it would have slowed things down too much to even try it inside someone else's project. Sometimes "roll your own" is the best idea.

> He didn't say it was not possible, but that it would have required too much effort in modifying the ABI and the garbage collector.

__morestack doesn't really have an ABI. It's just a call to an address emitted in the function prolog. LLVM and 6g/8g emit calls to it the exact same way. I suppose you could consider the stack limit part of the ABI, but it's trivial: it's just [gs:0x18] or something like that (also it is trivial to change in LLVM).

The garbage collector is irrelevant here as the GC only needs to be able to unwind the stack and find metadata. Only the runtime implementation of __morestack has any effect on this; the compiler isn't involved at all.

> Which is why they avoided LLVM for a much smaller and easier to manipulate existing compiler. Their point is that it would have slowed things down too much to even try it inside someone else's project.

I was suggesting that Rob Pike possibly confused segmented stacks with relocatable stacks. Segmented stacks have only minimal interaction with the GC, while relocatable stacks have major interaction.

Assuming good faith, either (1) Rob misremembered the problem being relocatable stacks instead of segmented stacks; or (2) the Go team didn't realize that LLVM had segmented stack support, so this part of the reasoning was mistaken. (Not saying there weren't other reasons; I'm only talking about this specific one.)

> Segmented stacks have only minimal interaction with the GC, while relocatable stacks have major interaction.

Okay.. this is where I'm losing your argument. Can you quantify the difference here between 'minimal' and 'major' from the 2012 perspective this was framed in?

The GC needs to unwind the stack to find roots. The only difference between segmented stacks and contiguous stacks as far as unwinding the stack is concerned is that in segmented stacks the stack pointer isn't monotonically increasing as you go up. This is usually not a problem. (The only time I've seen it be a problem is in GDB, where some versions have a "stack corruption check" that ensures that the stack pointer is monotonically increasing and assumes the stack has been corrupted if it isn't. To make such versions of GDB compatible with segmented stacks, you just need to remove that check.)

Relocatable stacks are a different beast. With relocatable stacks, pointers into the stack move when the stack resizes. This means that you must be able to find those pointers, which may be anywhere in the stack or the heap, and update them. The garbage collector already knows how to do that--walking the heap is its job, after all--so typically resizable stacks are implemented by having the stack resizing machinery call into the GC to perform the pointer updates.

Note that, as an alternative implementation of relocatable stacks, you can simply forbid pointers into the stack. This means that your GC doesn't need to be moving. I believe that's what Go does, as as far as I'm aware Go doesn't have moving GC (though I'm not up to date and very much could be wrong here). This doesn't help Pike's argument, though, because in that scenario the impact of relocatable stacks on the GC is much less.

As an aside, in my view the legitimate reasons to not use LLVM would have been (1) compile times and (2) that precise GC, which Go didn't ship with but which was added not too long thereafter, was hard in LLVM at the time due to SelectionDAG and lower layers losing the difference between integer and pointer.

> SelectionDAG and lower layers losing the difference between integer and pointer

Doesn't pointer-provenance support address this point nowadays? AIUI, a barebones version of what amounts to provenance ("pointer safety" IIRC) was even included in the C++ standard as a gesture towards GC support. It's been removed from the upcoming version of the standard, having become redundant.

I think CHERI addresses the issue, but I don't know how much of that is in upstream LLVM. Pointer provenance as used for optimization mostly affects the IR-level optimizations, not CodeGen ones.

In any case, Azul's work addresses the GC metadata problem nowadays.

> you can simply forbid pointers into the stack. This means that your GC doesn't need to be moving. I believe that's what Go does

I might have misunderstood your comment, but FWIW, Go does allow pointers into the stack from the stack.

When resizing/moving/copying a stack, the Go runtime does indeed find those pointers (via a stack map) and adjust them to point to the new stack locations. For example:

https://github.com/golang/go/blob/b25f5558c69140deb652337afa...

(The growable stacks I think replaced the segmented stacks circa Go 1.3 or so; I can't speak to whether they were contemplating growable stacks in the early days whilst considering whether to start their project with the Plan 9 toolchain, LLVM, or GCC, but to your broader point, they were likely considering multiple factors, including how quickly they could adapt the Plan 9 toolchain).

Reply on news.ycombinator.com