JuliaLang/julia — pull request #8134 by vtjnash (2014-08-26 07:30:47+00:00)
Title: WIP: gc on-stack

This is an improvement to the GC by pre-computing the GC escape analysis and entirely avoiding malloc when it is detected that the value cannot leave the stack frame. In it's current form, this appears to have no impact on the perf tests (as expected), since it doesn't trace values across function calls. Through the addition of a gc-analysis pass to inference.jl, this can be easily improved however. Where this is most helpful is in allocating boxes for ccall for very cheap, allowing the elimination of the `&` special syntax without performance penalty:

Some initial function to be merged into base:
```julia
julia> type Ref{T}
x::T
end

julia> Base.getindex(x::Ref) = x.x
getindex (generic function with 171 methods)

julia> Base.convert{T}(::Type{Ptr{T}}, b::Ref{T}) = ccall(:jl_value_ptr,Ptr{T},(Ptr{Ref},),&b)
convert (generic function with 452 methods)
```

And an example:
```julia
julia> function call_fortran()
x = Ref{Int}(0)
ccall(:jl_, Void, (Ptr{Int}, Ptr{Int},), x, Ref{Int}(1))
return x[]
end
call_fortran (generic function with 1 method)

julia> code_llvm(call_fortran,())

; Function Attrs: sspreq
define i64 @"julia_call_fortran;40340"() #2 {
top:
%0 = alloca [5 x %jl_value_t*], align 8
%.sub = getelementptr inbounds [5 x %jl_value_t*]* %0, i64 0, i64 0
%1 = getelementptr [5 x %jl_value_t*]* %0, i64 0, i64 2, !dbg !1136
store %jl_value_t* inttoptr (i64 6 to %jl_value_t*), %jl_value_t** %.sub, align 8
%2 = load %jl_value_t*** @jl_pgcstack, align 8, !dbg !1136
%3 = getelementptr [5 x %jl_value_t*]* %0, i64 0, i64 1, !dbg !1136
%.c = bitcast %jl_value_t** %2 to %jl_value_t*, !dbg !1136
store %jl_value_t* %.c, %jl_value_t** %3, align 8, !dbg !1136
store %jl_value_t** %.sub, %jl_value_t*** @jl_pgcstack, align 8, !dbg !1136
store %jl_value_t* null, %jl_value_t** %1, align 8, !dbg !1136
%4 = getelementptr [5 x %jl_value_t*]* %0, i64 0, i64 3, !dbg !1136
store %jl_value_t* null, %jl_value_t** %4, align 8, !dbg !1136
%5 = load i8** @jl_alloca_stack, align 8, !dbg !1136
%6 = getelementptr [5 x %jl_value_t*]* %0, i64 0, i64 4
store %jl_value_t* null, %jl_value_t** %6, align 8
%7 = alloca [3 x i8*], align 8, !dbg !1137
%.sub1 = getelementptr inbounds [3 x i8*]* %7, i64 0, i64 0
%8 = load i8** @jl_alloca_stack, align 8, !dbg !1137
store i8* %8, i8** %.sub1, align 8, !dbg !1137
%9 = bitcast [3 x i8*]* %7 to i8*, !dbg !1137
store i8* %9, i8** @jl_alloca_stack, align 8, !dbg !1137
%10 = getelementptr [3 x i8*]* %7, i64 0, i64 1, !dbg !1137
%11 = bitcast i8** %10 to %jl_value_t*, !dbg !1137, !isAlloca !1139
store i8* inttoptr (i64 140638926508672 to i8*), i8** %10, align 8, !dbg !1137
store %jl_value_t* %11, %jl_value_t** %6, align 8, !dbg !1137
%12 = getelementptr [3 x i8*]* %7, i64 0, i64 2, !dbg !1137
%13 = load i64* inttoptr (i64 140638888978504 to i64*), align 8, !dbg !1137
%.c2 = inttoptr i64 %13 to i8*, !dbg !1137
store i8* %.c2, i8** %12, align 8, !dbg !1137, !tbaa %jtbaa_user
store %jl_value_t* %11, %jl_value_t** %1, align 8, !dbg !1137
%14 = alloca [3 x i8*], align 8, !dbg !1142
%.sub3 = getelementptr inbounds [3 x i8*]* %14, i64 0, i64 0
%15 = load i8** @jl_alloca_stack, align 8, !dbg !1142
store i8* %15, i8** %.sub3, align 8, !dbg !1142
%16 = bitcast [3 x i8*]* %14 to i8*, !dbg !1142
store i8* %16, i8** @jl_alloca_stack, align 8, !dbg !1142
%17 = getelementptr [3 x i8*]* %14, i64 0, i64 1, !dbg !1142
%18 = bitcast i8** %17 to %jl_value_t*, !dbg !1142, !isAlloca !1139
store i8* inttoptr (i64 140638926508672 to i8*), i8** %17, align 8, !dbg !1142
store %jl_value_t* %18, %jl_value_t** %6, align 8, !dbg !1142
%19 = getelementptr [3 x i8*]* %14, i64 0, i64 2, !dbg !1142
%20 = load i64* inttoptr (i64 140638888978536 to i64*), align 8, !dbg !1142
%.c4 = inttoptr i64 %20 to i8*, !dbg !1142
store i8* %.c4, i8** %19, align 8, !dbg !1142, !tbaa %jtbaa_user
store %jl_value_t* %18, %jl_value_t** %4, align 8, !dbg !1142
%21 = bitcast i8** %12 to i64*, !dbg !1142
%22 = bitcast i8** %19 to i64*, !dbg !1142
call void inttoptr (i64 4318594960 to void (i64*, i64*)*)(i64* %21, i64* %22), !dbg !1142
%23 = load i64* %21, align 8, !dbg !1143, !tbaa %jtbaa_user
%24 = load %jl_value_t** %3, align 8, !dbg !1143
%25 = getelementptr inbounds %jl_value_t* %24, i64 0, i32 0, !dbg !1143
store %jl_value_t** %25, %jl_value_t*** @jl_pgcstack, align 8, !dbg !1143
store i8* %5, i8** @jl_alloca_stack, align 8, !dbg !1143
ret i64 %23, !dbg !1143
}
```
No `allocobj`!

TODO items:
- [ ] remove the alloca stack frame when it isn't used
- [ ] frob the stack less
- [x] future work: implement more complete gc analysis pass in julia (store info in Expr objects)