Strip address space after gcframe allocation

[yuyichao]

The use of address space for gcframe allocation is nice but currently has a few issues.

1. It seems that it might disable some optimizations that is legal to do after gcframe allocation

2. It makes code_llvm really hard to read. Just to give a taste, this is the code_llvm for g2(Ref(1), Ref(2))with @noinline g2(a...) = a[1][].

   %26 = call %jl_value_t addrspace(10)* @jl_gc_pool_alloc(i8* %ptls_i8, i32 1432, i32 16)
   %27 = addrspacecast %jl_value_t addrspace(10)* %26 to %jl_value_t addrspace(11)*
   %28 = bitcast %jl_value_t addrspace(11)* %27 to %jl_value_t addrspace(10)* addrspace(11)*
   %29 = getelementptr %jl_value_t addrspace(10)*, %jl_value_t addrspace(10)* addrspace(11)* %28, i64 -1
   store %jl_value_t addrspace(10)* addrspacecast (%jl_value_t* inttoptr (i64 140059207824816 to %jl_value_t*) to %jl_value_t addrspace(10)*), %jl_value_t addrspace(10)* addrspace(11)* %29, align 8
   %30 = bitcast %jl_value_t addrspace(10)* %26 to i64 addrspace(10)*
   %31 = addrspacecast i64 addrspace(10)* %30 to i64 addrspace(11)*
   store i64 1, i64 addrspace(11)* %31, align 16
   store %jl_value_t addrspace(10)* %26, %jl_value_t addrspace(10)** %15, align 8
   %32 = call %jl_value_t addrspace(10)* @jl_gc_pool_alloc(i8* %ptls_i8, i32 1432, i32 16)
   %33 = addrspacecast %jl_value_t addrspace(10)* %32 to %jl_value_t addrspace(11)*
   %34 = bitcast %jl_value_t addrspace(11)* %33 to %jl_value_t addrspace(10)* addrspace(11)*
   %35 = getelementptr %jl_value_t addrspace(10)*, %jl_value_t addrspace(10)* addrspace(11)* %34, i64 -1
   store %jl_value_t addrspace(10)* addrspacecast (%jl_value_t* inttoptr (i64 140059207824816 to %jl_value_t*) to %jl_value_t addrspace(10)*), %jl_value_t addrspace(10)* addrspace(11)* %35, align 8
   %36 = bitcast %jl_value_t addrspace(10)* %32 to i64 addrspace(10)*
   %37 = addrspacecast i64 addrspace(10)* %36 to i64 addrspace(11)*
   store i64 2, i64 addrspace(11)* %37, align 16
   store %jl_value_t addrspace(10)* %32, %jl_value_t addrspace(10)** %22, align 8
   store %jl_value_t addrspace(10)* addrspacecast (%jl_value_t* inttoptr (i64 140059206975592 to %jl_value_t*) to %jl_value_t addrspace(10)*), %jl_value_t addrspace(10)** %.sub, align 8
   store %jl_value_t addrspace(10)* %26, %jl_value_t addrspace(10)** %23, align 8
   store %jl_value_t addrspace(10)* %32, %jl_value_t addrspace(10)** %24, align 8
   %38 = call %jl_value_t addrspace(10)* @jl_invoke(%jl_value_t addrspace(10)* addrspacecast (%jl_value_t* inttoptr (i64 140058681133584 to %jl_value_t*) to %jl_value_t addrspace(10)*), %jl_value_t addrspace(10)** %.sub, i32 3)

[Keno]

This is a bit annoying since it requires rewriting essentially every single instruction. The other problem is with function signatures which you can't really update.

[Keno]

Note for the missed optimizations, we can simply drop the ni requirement when we get past this pass.

[maleadt]

WIP. Doesn't rewrite IR yet as replacing the LLVM functions breaks because of stale functionObjects; not sure how to replace those easily. CloneFunctionInto is probably going to be too expensive as well.

EDIT: this is getting hairy. RAUW not working because of types mismatching requires us to recreate a bunch of instructions, many of which don't have "exhaustive" ctors (eg. AllocaInst alignment requires separate call). Unless I'm missing something, patching the back-ends is probably going to be easier?

[maleadt]

Spent some more time at it, see this branch, but it is getting unwieldy because of basically two issues:

1. LLVM instructions seem to cache their type at the point they're created. For example:

// create a module with alloca(ptr with as) |> gep

auto M = new Module("mod", Ctx);
auto FT = FunctionType::get(Type::getVoidTy(Ctx), false);
Function *F = cast<Function>(M->getOrInsertFunction("fun", FT));
auto BB = BasicBlock::Create(Ctx, "entry", F);

IRBuilder<> Builder(Ctx);
Builder.SetInsertPoint(BB);

auto ElTy = Type::getInt32Ty(Ctx);
auto PtrTy = ElTy->getPointerTo(10);

auto Alloca = Builder.CreateAlloca(PtrTy, ConstantInt::get(ElTy, 1));
auto GEP = Builder.CreateGEP(Alloca, ConstantInt::get(ElTy, 0));
Builder.CreateRetVoid();

F->dump();
GEP->getType()->dump();

define void @fun() {
entry:
  %0 = alloca i32 addrspace(10)*
  %1 = getelementptr i32 addrspace(10)*, i32 addrspace(10)** %0, i32 0
  ret void
}

i32 addrspace(10)**

Let's now replace the alloca with one for a generic pointer (mimicking what we need to do):

// plain RAUW checks type
template<typename T>
void unsafeReplaceAllUsesWith(T *from, T *to) {
    while (!from->use_empty()) {
        auto &U = *from->use_begin();
        U.set(to);
    }
}

auto GenericPtrTy = ElTy->getPointerTo(0);
Builder.SetInsertPoint(Alloca);
auto GenericAlloca = Builder.CreateAlloca(GenericPtrTy, Alloca->getArraySize());
unsafeReplaceAllUsesWith(Alloca, GenericAlloca);
Alloca->eraseFromParent();

F->dump();
GEP->getType()->dump();

define void @fun() {
entry:
  %0 = alloca i32*
  %1 = getelementptr i32 addrspace(10)*, i32** %0, i32 0
  ret void
}

i32 addrspace(10)**

Surprisingly, the GEP's output type hasn't been updated. Which means we have to recreate that instruction as well...

2. we can have address spaces hidden in non-operand inputs to instructions. For example, CallInst, where the function to be called can be a ConstExpr(IntToPtr) with non-generic AS. However, that is not part of the User::operands, which only lists the run-time argument values to the function call. So we need to special-case CallInst handling to deal with that.

The result of 1 + 2 is that we need to process and possible rewrite each instruction (because changes do not percolate through), while requiring special-case handling for most instructions/value. Hence all this code which doesn't even get me very far yet.

Any ideas/comments/input? @Keno @yuyichao @vtjnash

[yuyichao]

Which means we have to recreate that instruction as well...

That's actually what I'm doing in https://github.com/JuliaLang/julia/pull/22684/files#diff-396d884a3fff7980811535c6018c6f6dR192

[tshort]

Thumbs up in this. The addrspace's are my current roadblock in getting Julia code compiled with Emscripten. It mainly comes up with code that uses llvmcall (I'm trying to use that to access libjulia). Rust used addrspace in an old GC but removed it.

[yuyichao]

What Rust does is irrelevant here...