Avoid overspecialization

[maleadt]

We currently duplicate the C++ type hierarchy of LLVM objects (e.g. Argument, Instruction, Function, etc), even though the C API only exposes a flattened one (Value). This has several advantages:

• the ability to overload names, e.g. unsafe_delete!, parent, name, automatically dispatching to the correct C method based on the type
• type checking to avoid using the wrong method, which would abort in LLVM (and thus kill your session)

... but also a disadvantage: code gets overspecialized because we have many representations of a Value. For example:

using LLVM

function main()
    Context() do ctx
        mod = LLVM.Module("SomeModule")

        param_types = [LLVM.Int32Type(), LLVM.Int32Type()]
        ret_type = LLVM.FunctionType(LLVM.Int32Type(), param_types)

        sum = LLVM.Function(mod, "SomeFunctionSum", ret_type)

        entry = BasicBlock(sum, "entry")

        @dispose builder=IRBuilder() begin
            position!(builder, entry)

            tmp = add!(builder, parameters(sum)[1], parameters(sum)[2])
            tmp = add!(builder, tmp, ConstantInt(LLVM.Int32Type(), 1))
            tmp = add!(builder, tmp, parameters(sum)[2])
            ret!(builder, tmp)
        end
    end
end

isinteractive() || main()

❯ jl --trace-compile=stderr --project wip.jl
precompile(Tuple{typeof(LLVM.add!), LLVM.IRBuilder, LLVM.AddInst, LLVM.ConstantInt})
precompile(Tuple{typeof(LLVM.add!), LLVM.IRBuilder, LLVM.AddInst, LLVM.Argument})

Here you can see that the add! method was specialized multiple times, even though the generated code is basically identical: accessing the handle and passing it to C.

Is this even a problem?

I'm not sure. Although we overspecialize, we only do so for tiny methods, so I would think the added latency is minimal.

Possible solution 1: hint the compiler

We could add @nospecialize(x::Value) annotations to functions that do not need to be specialized. That's a bit cumbersome, and also doesn't suffice. For example:

add!(builder::IRBuilder, @nospecialize(LHS::Value), @nospecialize(RHS::Value), Name::String="") =
    Value(API.LLVMBuildAdd(builder, LHS, RHS, Name))

Even though this successfully avoids overspecialization of add!, the underlying wrapper function is still specialized:

precompile(Tuple{typeof(LLVM.API.LLVMBuildAdd), LLVM.IRBuilder, LLVM.AddInst, LLVM.ConstantInt, String})
precompile(Tuple{typeof(LLVM.API.LLVMBuildAdd), LLVM.IRBuilder, LLVM.AddInst, LLVM.Argument, String})

Adding @nospecialize over there (which isn't a trivial thing to add to our wrapper generators) pushes the specialization down another layer:

precompile(Tuple{typeof(Base.unsafe_convert), Type{Ptr{LLVM.API.LLVMOpaqueValue}}, LLVM.AddInst})
precompile(Tuple{typeof(Base.unsafe_convert), Type{Ptr{LLVM.API.LLVMOpaqueValue}}, LLVM.ConstantInt})

... but that one is probably acceptable, and would result in code that can get reused.

Still, lots of changes across the codebase. And FWIW, Base.Experimental.@max_methods 1 function add! end doesn't help, neither does adding that to the LLVM.API submodule. Base.@nospecializeinfer also doesn't help.

Possible solution 2: Rework the type hierarchy

We could rework the type hierarchy to be either flat (only Value) or maybe trait based. The former would mean losing a lot of functionality, the latter reimplementing what Julia does for us (e.g. checking trait as function preconditions), so I'm not inclined to implement this.

Furthermore, we currently do actually sometimes use the ability to store extra fields in Value subtypes, e.g., to store lists of roots, or parent objects. Flattening everything would remove that ability.

[maleadt]

Since people are describing this as "gratuitous dynamism" and even "bad design", I gave this some more thought.

---

One radical redesign of the type hierarchy would involve making Value a concrete type, and for lack of multiple inheritance, introducing abstract classes to add functionality to. In pseudo code:

abstract type AbstractValue end
LLVM.name(val::AbstractValue) = API.LLVMGetValueName(val.ref)

struct Value <: AbstractValue
  ref::ValueRef
end

abstract type AbstractUser <: AbstractValue end
operands(user::AbstractUser) = API.LLVMGetOperands(user.ref)

struct Instruction <: AbstractUser
  ref::ValueRef
end

Then, we'd make APIs return Values instead of dynamically inferring the value type, and provide converters a la cast<User> or cast<Instruction> to convert the returned Value to what the user expects.

This would bring the level of dynamism back to what C++ provides, expecting the user to check and convert to leaf types based on what's expected or what functionality is required. In turn, this should make functions type stable, as there's no unknown conversion from Value to a subtype.

However, I'm not sure this would solve the problem some people are experiencing. AFAIU, the issue isn't necessarily the type instabilities, but the fact that lots of code is being compiled (specialized), which is separate from the type instabilities. And with the proposed solution here, removing our current dynamism to go back to the C++ level, the API functions would still be invoked with lots of leaf types (in fact, it would be worse as it would also concretize the previously abstract types like Value or User, resulting in more code being generated).

In addition, this would be a massively breaking change, requiring all LLVM.jl users to update their code to include manual conversions.

---

It seems like the only way to make affected people happy is to strip all dynamism to the level of the C API, such that there are no type instabilities (everything is a Value), and no specialization (all methods are only invoked with a Value). As mentioned in the top post, that's a non starter. The given examples aren't particularly convincing though, as functions like LLVM.name could actually be implemented using a sequence of if statements to select the correct method (e.g., API.LLVMIsaStructTy && LLVMGetStructName) instead of relying on dispatch.

A more fitting example may be the functionality we have around getindex, for example, as with ConstantSequentials such as ConstantArray:

julia> ca = ConstantArray([1, 2, 3])
[3 x i64] [i64 1, i64 2, i64 3]

julia> ca[1]
i64 1

If everything were a Value, including these constants, it's near impossible to provide user-friendly wrappers like that. We'd need to disambiguate functions using their names, so this'd become constant_sequential_getindex(::Value), which is obviously not a user-friendly solution.

---

Bottom line, given the design of LLVM, it seems like the goal of having a user-friendly wrapper is at odds with a wrapper that works without generating any superfluous code or run-time dynamism. I'd love to be proven wrong though, so if anybody has any ideas, feel free to suggest them here or try them out.

If not, the best path forwards to me seems to improve the Julia compiler in a way that we can annotate these structures to avoid specialization in (at least) the API wrappers and related conversion methods (see top post).

As should be obvious by now, this design was not chosen willy nilly, but was a careful attempt to try and make the use of LLVM's C APIs as user friendly and safe as possible. The overheads associated with it are unfortunate, but very hard to avoid without sacrificing much of the value of LLVM.jl, at which point it's almost like ccalling the C API directly. I'd appreciate if this wasn't characterized as "bad design" without chiming in, providing concrete examples of the issue, or suggesting potential solutions.

cc @chriselrod