JuliaLang/julia — pull request #4042 by loladiro (2013-08-13 06:37:50+00:00)
Title: Tuples made me sad (so I fixed them)

Alright, this rabbit hole turned out to be a giant dungeon instead, but I think I have finally found the exit.

Basically what this does is prevent heap allocation of tuples whenever possible, instead passing them in registers or on the stack (or wherever llvm thinks is most efficient). An easy example is this:
```
julia> bar() = (1,2)

julia> code_llvm(bar,())

; Function Attrs: sspreq
define <2 x i64> @julia_bar714() #2 {
top:
ret <2 x i64> , !dbg !3834
}
```

whereas before it used to heap allocate it (albeit it was smart enough to recognize that the result was constant, it only did it once, but still: (from the old version)
```julia
julia> bar() = (1,2)

julia> code_llvm(bar,())

define %jl_value_t* @julia_bar() {
top:
ret %jl_value_t* inttoptr (i64 62429664 to %jl_value_t*), !dbg !3407
}
```

A perhaps more exciting and real work application is `size` on various array, e.g.

```julia
julia> code_llvm(size,(Array{Int64,2},))

; Function Attrs: sspreq
define <2 x i64> @julia_size(%jl_value_t*) #2 {
top:
%1 = getelementptr inbounds %jl_value_t* %0, i64 4, i32 0, !dbg !3876
%2 = load %jl_value_t** %1, align 8, !dbg !3876
%3 = ptrtoint %jl_value_t* %2 to i64, !dbg !3876
%4 = insertelement <2 x i64> undef, i64 %3, i32 0, !dbg !3881, !julia_type !3882
%5 = getelementptr inbounds %jl_value_t* %0, i64 5, i32 0, !dbg !3881
%6 = load %jl_value_t** %5, align 8, !dbg !3881
%7 = ptrtoint %jl_value_t* %6 to i64, !dbg !3881
%8 = insertelement <2 x i64> %4, i64 %7, i32 1, !dbg !3881, !julia_type !3882
ret <2 x i64> %8, !dbg !3881
}
```

Note that there is now no allocation involved, whereas before (again from the old version):

```julia
julia> code_llvm(size,(Array{Int64,2},))

define %jl_value_t* @julia_size(%jl_value_t*, %jl_value_t**, i32) {
top:
%3 = alloca [3 x %jl_value_t*], align 8
%.sub = getelementptr inbounds [3 x %jl_value_t*]* %3, i64 0, i64 0
%4 = getelementptr [3 x %jl_value_t*]* %3, i64 0, i64 2, !dbg !3419
store %jl_value_t* inttoptr (i64 2 to %jl_value_t*), %jl_value_t** %.sub, align 8
%5 = getelementptr [3 x %jl_value_t*]* %3, i64 0, i64 1, !dbg !3419
%6 = load %jl_value_t*** @jl_pgcstack, align 8, !dbg !3419
%.c = bitcast %jl_value_t** %6 to %jl_value_t*, !dbg !3419
store %jl_value_t* %.c, %jl_value_t** %5, align 8, !dbg !3419
store %jl_value_t** %.sub, %jl_value_t*** @jl_pgcstack, align 8, !dbg !3419
store %jl_value_t* null, %jl_value_t** %4, align 8
%7 = load %jl_value_t** %1, align 8, !dbg !3419
%8 = getelementptr inbounds %jl_value_t* %7, i64 4, i32 0, !dbg !3419
%9 = load %jl_value_t** %8, align 8, !dbg !3419
%10 = ptrtoint %jl_value_t* %9 to i64, !dbg !3419
%11 = call %jl_value_t* @jl_box_int64(i64 %10), !dbg !3424
store %jl_value_t* %11, %jl_value_t** %4, align 8, !dbg !3424
%12 = call %jl_value_t* @allocobj(i64 32), !dbg !3424
%13 = getelementptr inbounds %jl_value_t* %12, i64 2, i32 0, !dbg !3424
store %jl_value_t* %11, %jl_value_t** %13, align 8, !dbg !3424
%14 = getelementptr inbounds %jl_value_t* %12, i64 0, i32 0, !dbg !3424
store %jl_value_t* inttoptr (i64 28847136 to %jl_value_t*), %jl_value_t** %14, align 8, !dbg !3424
%15 = getelementptr inbounds %jl_value_t* %12, i64 1, i32 0, !dbg !3424
store %jl_value_t* inttoptr (i64 2 to %jl_value_t*), %jl_value_t** %15, align 8, !dbg !3424
%16 = getelementptr inbounds %jl_value_t* %12, i64 3, i32 0, !dbg !3424
store %jl_value_t* null, %jl_value_t** %16, align 8, !dbg !3424
store %jl_value_t* %12, %jl_value_t** %4, align 8, !dbg !3424
%17 = getelementptr inbounds %jl_value_t* %7, i64 5, i32 0, !dbg !3424
%18 = load %jl_value_t** %17, align 8, !dbg !3424
%19 = ptrtoint %jl_value_t* %18 to i64, !dbg !3424
%20 = call %jl_value_t* @jl_box_int64(i64 %19), !dbg !3424
store %jl_value_t* %20, %jl_value_t** %16, align 8, !dbg !3424
%21 = load %jl_value_t** %5, align 8, !dbg !3424
%22 = getelementptr inbounds %jl_value_t* %21, i64 0, i32 0, !dbg !3424
store %jl_value_t** %22, %jl_value_t*** @jl_pgcstack, align 8, !dbg !3424
ret %jl_value_t* %12, !dbg !3424
}
```

Another exciting part of this pull request that if your types happen to correspond to a machine vector type (aka SIMD type), I make it just that, allowing fun things like

```
julia> foo(x::(Int32,Int32,Int32,Int32)) = llvmcall("""%3 = add <4 x i32> %1, %0
ret <4 x i32> %3""",(Int32,Int32,Int32,Int32),((Int32,Int32,Int32,Int32),(Int32,Int32,Int32,Int32)),(int32(1),int32(2),int32(3),int32(4)),
x)
# methods for generic function foo
foo(x::(Int32,Int32,Int32,Int32)) at none:1

julia> code_llvm(foo,((Int32,Int32,Int32,Int32),))
; Number of arguments: 2
define <4 x i32> @julia_foo1(<4 x i32> ,<4 x i32> ) {
%3 = add <4 x i32> %1, %0
ret <4 x i32> %3
}
define linkonce_odr <4 x i32> @julia_foo1(<4 x i32>, <4 x i32>) {
%3 = add <4 x i32> %1, %0
ret <4 x i32> %3
}

; Function Attrs: sspreq
define <4 x i32> @julia_foo(<4 x i32>) #2 {
top:
%1 = add <4 x i32> %0,
ret <4 x i32> %1, !dbg !3798
}

julia> code_native(foo,((Int32,Int32,Int32,Int32),))
.text
Filename: none
Source line: 1
push	RBP
mov	RBP, RSP
sub	RSP, 16
mov	RAX, QWORD PTR FS:[40]
mov	QWORD PTR [RBP - 8], RAX
mov	RAX, QWORD PTR FS:[40]
cmp	RAX, QWORD PTR [RBP - 8]
jne	20
movabs	RAX, 140737297706192
paddd	XMM0, XMMWORD PTR [RAX]
Source line: 1
add	RSP, 16
pop	RBP
ret
movabs	RAX, 140737322375370
call	RAX
```

Note in particular the `paddd` in the native disassembly. The `llvmcall` used here is a new intrinsic to easily embed any LLVM IR into your julia functions. It is part of this pull request for demonstration purposes mostly, but is fully featured and ready to be used, but if people would rather not have it, I can rebase it out.

The tuple unboxing currently is only enabled for immutable types due to GC considerations, but I will follow up with that patch after discussion on this one is done (it already work fine for other types if you disable the GC).

Fixes #2496
Fixes #2299
/cc @JeffBezanson