LLVM Garbage Collector support

[KavinduZoysa]

This discussion was initiated to evaluate the LLVM support for garbage collectors.

LLVM does not provide garbage collectors, instead, it provides a framework that helps users to implement GCs. That framework provides the requirements for the GC. Before we discuss more about it, we have to figure out couple of terms.

1. safepoints - In general, how GC works is that, when the collection is required, GC raises a flag to inform the frontend. The frontend should check this flag and compiled code should hold its execution to allow the collection. To hold the execution, compiled code should come to a position where the required information(especially heap references) is visible(parseable) to GC. These particular places are called safepoints. Typically allocation sites and method calls or loops are considered safepoints. The LLVM provides us an intrinsic to place safepoints called llvm.experimental.gc.statepoint
2. stack map - The required information for GC such as heap reference locations is stored in stack map section. This is generated when we call the statepoint intrinsic.

At the initial phase what I have done is add the safepoints for a given LLVM IR and generate the stack map. Please follow https://github.com/KavinduZoysa/test-GCs/tree/master/statepoints for source codes.

A C code is written in order to generate the LLVM IR and the basic structure is that main function calls bar, bar calls foo(main -> bar -> foo). Then GC is enabled to main and bar. Now the llvm automatically identified where to put safe points. In this case, those are method calls.

define i32 @bar(i32* %0) #0 gc "statepoint-example" {
  %2 = alloca i32*, align 8
  store i32* %0, i32** %2, align 8
  %3 = load i32*, i32** %2, align 8
  store i32 234, i32* %3, align 4
  %4 = load i32*, i32** %2, align 8
  %5 = load i32, i32* %4, align 4
  %statepoint_token = call token (i64, i32, void (i32)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidi32f(i64 2882400000, i32 0, void (i32)* @foo, i32 1, i32 0, i32 %5, i32 0, i32 0)
  %6 = load i32*, i32** %2, align 8
  %7 = load i32, i32* %6, align 4
  ret i32 %7
}

define i32 @main() #0 gc "statepoint-example" {
  %1 = alloca i32, align 4
  %2 = call i8* @malloc(i64 4) #3
  %3 = bitcast i8* %2 to i32*
  store i32* %3, i32** @heapPtr, align 8
  %4 = load i32*, i32** @heapPtr, align 8
  %5 = getelementptr inbounds i32, i32* %4, i32 1
  store i32* %5, i32** @heapPtr, align 8
  %6 = load i32*, i32** @heapPtr, align 8
  %statepoint_token = call token (i64, i32, i32 (i32*)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i32p0i32f(i64 2882400000, i32 0, i32 (i32*)* @bar, i32 1, i32 0, i32* %6, i32 0, i32 0)
  %7 = call i32 @llvm.experimental.gc.result.i32(token %statepoint_token)
  store i32 %7, i32* %1, align 4
  ret i32 0
}

Based on this IR we can generate stack map at safepoints and it is visible in assembly code.

[KavinduZoysa]

Here I have attached the stack map with a brief explanation of each filed.

__LLVM_StackMaps:
	.byte	3                       ; LLVM stackmap version 3
        .byte	0                       
	.short	0
	.long	2                       ; number of functions where GC is enables ---- (A)
	.long	0
	.long	2                       ; total number of method calls that have statepoints
	.quad	bar                     ; 1st function address in (A)
	.quad	24                      ; stack size of the function
	.quad	1                       ; number of function calls that have statepoints
	.quad	main                    ; 2nd function address in (A)
	.quad	24                      ; stack size of the function
	.quad	1                       ; number of function calls that have statepoints
	.quad	2882400000
	.long	.Ltmp0-bar
	.short	0
	.short	3                       ; num of locations (live heap references)
	.byte	4                       ; location of 1st live reference (Register | Direct | Indirect | Constant | ConstantIndex)
	.byte	0                       ; location size
	.short	8
	.short	0
	.short	0
	.long	0                       ; offset
	.byte	4
	.byte	0
	.short	8
	.short	0
	.short	0
	.long	0
	.byte	4
	.byte	0
	.short	8
	.short	0
	.short	0
	.long	0
	.p2align	3
	.short	0
	.short	0
	.p2align	3
	.quad	2882400000
	.long	.Ltmp1-main
	.short	0
	.short	3
	.byte	4
	.byte	0
	.short	8
	.short	0
	.short	0
	.long	0
	.byte	4
	.byte	0
	.short	8
	.short	0
	.short	0
	.long	0
	.byte	4
	.byte	0
	.short	8
	.short	0
	.short	0
	.long	0
	.p2align	3
	.short	0
	.short	0
	.p2align	3

[KavinduZoysa]

Hi All, please follow that https://github.com/KavinduZoysa/test-GCs/tree/master/statepoints. It contains the instructions to read the LLVM StackMap

[KavinduZoysa]

Please consider this diagram. It shows the generated stack for https://github.com/KavinduZoysa/test-GCs/blob/master/statepoints/main.c when it calls from main() to bar(). Assume we are going to read the LLVM stack map, after bar() calls foo() and foo() returns.

We have heap references in both main()(h1) and bar()(h2). By reading the LLVM stackmap, we can get those locations with respect to rsp.
h1 = rsp + 16
h2 = rsp + 32

At this moment we can get the h2 without any issue because we know the rsp of the stack(red arrow in diagram). But for h1, rsp should be taken with respect to main() function's stackframe. So my suggestion to get the h1 is,

h1 = rsp + size of the stackframe of bar() + 16

Please add your suggestions on this.
@ayonam, @manuranga

[ayonam]

@KavinduZoysa Yes, that is exactly what you need to do. In fact, there are library routines in the DWARF library that will help you to walk up the stack without having to explicitly find out the frame size. That library works in a state machine like manner. So you need to initialize the state with the frame details of the frame that is under current execution. Once done, you can go from the frame of bar() to the frame of main() directly through a library call. Then you will get the value of $rsp as the value that it would be if the register were to point to the frame of main(). Now you can use the computation of $rsp+16 to arrive at the location of h1.

Do let me know if you are not getting how to accomplish this. I will then dig up the DWARF documentation and give more precise directions.

[KavinduZoysa]

@ayonam, I will try DWARF lib and let you know. Thank you for your answer.

[KavinduZoysa]

Also using gdp I was able to verify the heap references are located in correct places.

[KavinduZoysa]

Please read https://github.com/KavinduZoysa/test-GCs/tree/master/statepoints/manual-heapref-read, for source code.

[KavinduZoysa]

This commit https://github.com/KavinduZoysa/test-GCs/tree/2a92abbe5f2e116427c5cce4834f6ef633627a0a/statepoints contains the test code to read heap references programmatically.

[KavinduZoysa]

This commit https://github.com/KavinduZoysa/test-GCs/tree/f44be8debb06bedd2db2de3e22ca3d815c76cd98/statepoints contains the test code to read heap references using backtrace.

[KavinduZoysa]

This commit https://github.com/KavinduZoysa/test-GCs/tree/3d306445aec3731d42d987380ad27a0eca28993e/statepoints contains the test we have done with libbacktrace.