Consider using available_externally linkage for cross-crate inlined functions

[alexcrichton]

In rust, a static variable is essentially the same thing as a #define, and to achieve the same sort of optimizations about knowing the symbol at compile time we use the available_externally linkage from LLVM. What this means is that the source crate defining a static will always compile the version of the static into its own data section of the executable.

When an external crate then links to this source crate, it will import statics as they're used. Each static is imported in a manner like:

@original.source.name = available_externally i32 3

Where original.source.name is the name of the symbol in original crate, and 3 is the actual value of the constant. What this means is that LLVM can optimize based on the value of the constant (because we specify it explicitly, we loaded it from the serialized ast of the external crate). The reason we do this is so that a static has one and only one address. The available_externally linkage means that no symbol will be emitted into the crate. If LLVM determines that it needs the symbol (such as you took the address of the static), then it will link against it, otherwise LLVM optimizes it all out.

In theory, we could also apply this available_externally optimization to functions as well. What this would mean is that the source crate would provide definitions for all #[inline] functions, and then all crates linking against this crate would use available_externally. I would hope that this meant that LLVM would attempt to inline the function, but if LLVM didn't decide to inline the function it wouldn't recompile it or emit a symbol for it.

In theory this means smaller crates because all non-inlined calls to an #[inline] function would result in cross-crate calls.

I'm a little doubtful that this would provide an actual size benefit, and I'm also unsure of whether LLVM would even optimize like this. I'm only taking my vague understanding of the linkage mode and applying it to what seems reasonable for functions. Regardless, this may be an interesting project for anyone wishing to really take a bite out of dealing with LLVM, learning compiler internals, and possibly providing a nice reduction in binary size without losing any performance.

[thestinger]

This would result in an overall code size increase, because LLVM would have to emit external symbols for lots of small functions in the source crate.

[alexcrichton]

From my understanding, we currently already emit the symbols for all #[inline] functions in the crate which defined them (although this may be wrong to do so).

[thestinger]

They shouldn't be output as external symbols, it's a bug. The reachability code doesn't work at all.

[thestinger]

I think it's a huge mistake to be having programmers making manual decisions about when to use inlining. The crate model is fundamentally broken and doesn't provide either the ability to expose a stable ABI or have good performance/size.

[nikomatsakis]

On Thu, Oct 31, 2013 at 06:28:42PM -0700, Daniel Micay wrote:

I think it's a huge mistake to be having programmers making manual
decisions about when to use inlining.

In the end crates are really oriented around dynamic linking. We
designed cross-crate inlining so that people could have control over
what gets inlined across a DLL boundary and whta does not. This way,
if you are the author of a popular library, and you make a bug fix,
you can know for certain whether downstream clients will have to
recompile or not. At least that was the idea. I still think this is
an important use case.

However, there are other use cases where performance is more
important. In that case, dynamic linking seems like the wrong
choice. Static linking would probably be better. Ideally we'd emit the
LLVM bit code for each library and then statically link the whole
kit-and-kaboodle together, or possibly use LTO. We should work on
making this path easy, because it's important too.

The crate model is fundamentally broken and doesn't provide either
the ability to expose a stable ABI or have good performance/size.

I'm not sure why you say that crates don't provide the ability to
expose a stable ABI. Based on some overheard IRC conversation, I think
it has to do with reflection, but perhaps there are other concerns?

I am... amenable to reining in reflection or even removing it
altogether -- we're really not using it for much, and deriving gives
you much of the same benefit without any of the concerns -- but I
think you are exaggerating its impact. Java lets you use reflection to
do all sorts of things, including modifying private fields, and yet
somehow they have one of the richest ecosystem of libraries in
existence. Not to mention that unsafe code has the power to violate
every abstraction boundary known to man. Anyway, reflection is a
separate issue from what is under discussion here.

[nikomatsakis]

One thing: for generic functions, there may not be an externally
available variant specialized to the correct types.

[thestinger]

@nikomatsakis: Rust suffers from the same problems as C++ when it comes to dynamic linking but also makes life harder. In both languages, field privacy leads to exposing the size of every public type as part of the ABI. In Rust, visit glue also exposes all the internal details of every field reachable from a public type. The definitions of global values are also serialized to metadata.

C++ has instantiations of generics, but allows exporting specific instances of them. It contains anything relevant to the ABI in a header file, so it's obvious what you're exposing. The most widely used open-source C++ standard library (libstdc++) has kept binary compatibility since 2006.

I don't think we'll ever reach the point where you can upgrade Rust itself or idiomatic libraries and not end up having to rebuild everything using them. However, I think it is important to support writing a stable ABI. I guess it might make more sense to be using extern "C" and a header file when you're in one of those use cases but it would be nice if you didn't have to.

The issue I have with #[inline] is that almost everything in libstd is going to end up tagged that way or is generic. Nearly everything else ends up as an external symbol because an inline/generic function is calling it. The library boundary is barely there at all.

If we decided to use static linking for debug builds and link-time optimization for release builds, we could pretty much stop worrying about #[inline] and split libraries like librustc into many (30+) compilation units without any performance loss.

[thestinger]

A normal C library is composed of hundreds of compilation units handled via static linking or link-time optimization, and then presents a single static/dynamic library to users. If we moved towards that, it would definitely be an improvement, but I don't see much value in a top-level dynamically linkable shared object for Rust.

Java is essentially doing the same thing as link-time optimization path, where each compilation unit is translated/optimized in advance to bytecode and then loaded/optimized again. There's no need for ABI compatibility in that paradigm.

[thestinger]

I came up with a concrete plan for this: #14527