A "Cross-Platform Runtime Library API" in LLVM IR

My idea is an API where anyone can build a Runtime Library for any backend, including a set of functions people can inline/rename creating functions the frontend can include in the IR.

For example implementing a cross-platform runtime function that allocates memory for a new object. (Obviously the library will have to be compiled for each target).

I read about compiler-rt but I think it has nothing to do with what I'm thinking about, maybe I'm wrong?

If something like this doesn't exist, maybe I can start a little project for LLVM about this

Memory allocation is usually considered part of libc. There are several libc implementations that target multiple architectures. musl, glibc, newlib, diet libc to name just a few.

- Matthias

I know, that's the problem.
We can assume all of the system calls as runtime functions: such as I/O, allocations etc. and create a set of function implemented for all the architectures.
For example, let's think about the mem allocation again: we can provide a primitive function with the same name for all archs (e.g. __alloc() ) and then people can include this function __alloc() in their libraries, inlining it or even renaming it just to fit the frontend needs. And this can be useful: every backend should implement this set of functions ( __alloc(), __free(), __write()… just for example) so the frontends can build a library with these functions as they want.
I don't know if you get me.

I think you will need to explain a bit more. We already have such a function, it’s called malloc() and a few LLVM passes assume specific behaviour about it. What problem are you trying to solve?

David

So, the backend should implement “__alloc” that does the same as “malloc” - or something subtly different from “malloc” - and on a Windows machine, how is it different from “HeapAlloc”? And “__write” that is same as UNIX “write”, but different from “WriteFile” in Windows? And HOW do you expect the backend to implement these? By calling “malloc”/“HeapAlloc”, “write”/“WriteFile”?

This is what the C library is for, it provides a set of independent functions that are reasonably well defined and reasonably portable between archiectures. If you are compiling something different than C, you’ll need to implement something similar [and perhaps, like I did, interface to the C runtime library even in a non-C language with thin wrapper functions].

Sorry if I misunderstood your idea, as David says, maybe you need to explain a bit more…

I know but maybe malloc() is a bit higher level than a hypothetical __alloc(), which may be lower-level and then faster.

And malloc() is contained in the libc as Matthias said and so maybe a program using malloc() even for a non-C language linking against the crt is needed.

I’m just assuming that the functions we use in C such as malloc() are quite high-level interfaces and that there might be something faster.

For example, does Swift use malloc() to allocate its objects?

I know but maybe malloc() is a bit higher level than a hypothetical __alloc(), which may be lower-level and then faster.

How?

And malloc() is contained in the libc as Matthias said and so maybe a program using malloc() even for a non-C language linking against the crt is needed.

On many *NIX platforms, libc or some equivalent is the canonical interface to the system.

I'm just assuming that the functions we use in C such as malloc() are quite high-level interfaces and that there might be something faster.

For example, does Swift use malloc() to allocate its objects?

A number of high-level language don’t use malloc, but not because it is too high-level; quite the reverse. You can have a more efficient malloc implementation if you know something about allocation patterns. For example, in a class-based OO language you’re likely to have a small number of class sizes and having a separate slab allocator for each of these can be faster. If you need garbage collection, then you’ll want to associate more metadata with allocations.

malloc() is about as low-level an interface to memory management as is possible while maintaining some abstraction: you give it a size (no type, for example) and it gives you a pointer to some uninitialised memory. The only lower-level interfaces would be related to page table management (mmap and friends on *NIX, more complex APIs on Mach and entirely delegated page table manipulation on something like Xen or DUNE).

Again, what problem are you trying to solve? What is your use case for such a library?

David

This is the point,
High-level OO languages don't use malloc(), they use something else.
My idea was a C API with implementations of functions:
For example
Assuming I need to implement a function which allocates a new object.
The API provides a really basic allocator function I can use to implement the complete function the high-level language needs.

void *__newobject(int class_size) {
void *r = __alloc(class_size);
// Add GC metadata here
return r;
}

This function will be included in the runtime library. Obviously this is a stupid example maybe a better implementation can be done.

Something like this can be done for I/O.

This is the point,

No, you are still failing to make a point.

High-level OO languages don't use malloc(), they use something else.

That’s not entirely true. They need to get the memory that they provide to programs from somewhere. They may provide their own pool allocators, but they will often just call malloc() and then subdivide the returned chunk. If they’re doing garbage collection, they will ask for a large number of pages and use that as a heap managed by the garbage collector.

My idea was a C API with implementations of functions:
For example
Assuming I need to implement a function which allocates a new object.
The API provides a really basic allocator function I can use to implement the complete function the high-level language needs.

void *__newobject(int class_size) {
void *r = __alloc(class_size);
// Add GC metadata here
return r;
}

You have still completely failed to explain why __alloc() is better than malloc(). If you wish to implement a language-specific allocator like this, then why would it want to call __alloc() from your hypothetical library instead of malloc(), provided by something like jemalloc(), which has over a decade of careful optimisation behind it to ensure that it scales well on multithreaded systems?

This function will be included in the runtime library. Obviously this is a stupid example maybe a better implementation can be done.

Again, why would I, as the author of a high-level language, want to depend on your runtime library? You have not given a compelling use case for someone wanting to depend on your hypothetical runtime library instead of the target platform’s libc. If I write my language-specific code against libc, then other people will implement the platform-specific parts for me. I can rely on C interfaces existing on pretty much any platform that I want to target, from desktop and server operating systems down to real-time embedded operating systems. What does your proposal give me?

David

I'm not talking about a new library instead of the libc, I'm talking about letting people create a library optimized for a specific frontend, regardless of the target.

Your FIRST premise, that languages don’t use malloc to allocate memory is incorrect in the first place.

gnu libc++:
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/libsupc%2B%2B/new_op.cc

libcxx (LLVM’s C++ library):
https://github.com/llvm-mirror/libcxx/blob/master/src/new.cpp#L50

My Pascal compiler does essentially the same thing:
https://github.com/Leporacanthicus/lacsap/blob/master/runtime/alloc.c

It sounded as if you were talking about a library that sits underneath such a thing. Lots of languages have their own runtime libraries (I maintain two of them), including Go, C++, Swift, and Objective-C. These are generally intended to be portable across front ends, defining the low-level binary interfaces that compilers target.

David

But HOW is that going to work for multiple languages, on multiple hardware
platforms. And have you got ANY evidence that the extra call level between
C++'s `operator new` and `malloc` actually causes noticeable overhead?

You guys are saying that the library which defines the runtime library is written in C for many languages.
The problem is that such functions are in the libc and so the object files have to be linked against the **entire** libc.
Sorry if I'm wrong but isn't it a little inefficient or hard to handle?
With "hard to handle" I mean the entry point:
if I use C's I/O operations, ain't I forced to use the C _start() implementation that calls its initializers (such as stdin and stdout initialization) before calling main() ?

I was thinking about maybe trying to make the languages runtimes independent from the C runtime. Wouldn't it make runtimes faster?

At least for Linux/Unix, there’s very little you can actually achieve without at least some of the libc linked into your own system. Unless you actually write your own system call interface functions - which is dependent on the processor architecture (using int X [or syscall] in x86, perhaps trap Y in 68K, swi on ARM, etc) - values for X may vary depending on OS too, and ABI (different registers/calling convention may exist for the same architecture) - and of course, it will be yet different on Windows, either way. Using standard library functions in the C library will give a reasonable semblance of working on most platforms for which there is a C compiler.

Sure, you can reduce the size of the application itself by a fair bit [when statically linked - my typical Pascal test executables are in the tens of kilobytes, because they dynamically link to libc], but I very much doubt you’ll gain much overall time from using something other than libc - but you’ll end up doing a lot of work.

Do, by all means, investigate this, and if you find some significant savings, report back. But in general, I’d say, you probably end up doing the same thing that libc does already. And most languages need some start-up code, so calling _start at that point isn’t such a terrible thing. I use the C compiler as a linker, so I just call my language’s startup main and be done with it. But you’ll probably find yourself implementing something like this:
https://github.com/Leporacanthicus/lacsap/blob/master/runtime/main.c

either way, even if it’s not precisely called main, and isn’t written in C.

Yes, it’s necessary to call _start or equivalen, if you want to stdin and stdout, to initialize those - but sooner or later, you’ll end up wanting to buffer I/O a little bit beyond calling the OS read/write operations (write is pretty rubbish for implementing printf or Pascal’s writeln - because you get far too many user-kernel-user transitions, making it slow), and most likely, you don’t want to call sbrk and mmap to allocate memory directly either. So, the runtime library for language X will have to have some runtime library that sets things up in accordance to how it’s file and memory handling.

The key point here is “how much do you gain, and how much effort is it”. If it’s a very small gain, and a large amount of effort, is there something else that makes it meaningful to do? So far, I see no such case.

By all means, if you want to implement your own language, and write your own runtime to go with that, LLVM will allow that. But you will need to implement some reasonably efficient handling of file-I/O and memory allocation for each OS you want. And a reason why you won’t want to do ONE library that allows this for many languages is that different languages have different semantics for the DETAILS of how you do certain things (error handling could be throwing exceptions, returning error codes, aborting the execution - or some combination thereof based on compiler or language pragma, etc, etc).

You guys are saying that the library which defines the runtime library is written in C for many languages.
The problem is that such functions are in the libc and so the object files have to be linked against the **entire** libc.
Sorry if I'm wrong but isn't it a little inefficient or hard to handle?
With "hard to handle" I mean the entry point:
if I use C's I/O operations, ain't I forced to use the C _start()
implementation that calls its initializers (such as stdin and stdout
initialization) before calling main() ?

And? The CRT startup often does a variety of things and if you want to
co-exist with C libraries at all, you won't be able to avoid it. Even if
you can avoid it, it adds a lot of OS and target specific knowledge to
your language runtime with little gain. Even for static linkage, a well
written stdio implementation is not that heavy. Just because glibc
requires 2MB for static linking hello-world, doesn't mean everyone else
does.

I was thinking about maybe trying to make the languages runtimes
independent from the C runtime. Wouldn't it make runtimes faster?

Unlikely. You might be able to reduce startup time a bit, but even that
is quite possible in the noise. On the other hand, you gain all the
advantage of dealing with different system call conventions, different
ways for managing kernel ABI compatibility etc. It's a pain when dealing
with Go already...

Joerg

Actually my idea was not to provide the same library for all languages, but it was to provide an API for creating a library that better fits the needs of a specific language.

If you tell me that relying on the C runtime is the best way to make a runtime library and there are really few disadvantages, then ok.

I also have to say that creating a runtime independent from the C runtime might make the language unable to be interoperable with the C itself, so effectively this would be a great disadvantage.

The main disadvantages of the libc integration are:

  • The executables might result a little larger, containing some useless C entities.
  • The entry point might be uselessly “heavier than needed”, calling useless initializations
  • If a language wants to add its own global initializers, it has to use the main() function called by _start(), and I think that all programs for convention should start from main()

The main disadvantages of the libc integration are:
- The executables might result a little larger, containing some useless C entities.

Dynamically linking libc adds very little to the binary size.

- The entry point might be uselessly "heavier than needed", calling useless initializations
- If a language wants to add its own global initializers, it has to use the main() function called by _start(), and I think that all programs for convention should start from main()

This has very little to do with libc, but rather to do with the C runtime parts (csu / crt*). These are misnamed, as they’re not really specific to C. If you want things like LLVM’s llvm.init globals to work, then you must either use these or use something equivalent. If you want to start things before main() then you can use exactly the same mechanism as libc.

David

OT:
I don't think duplicating the libc API with a different name is very
useful but what I do think would be useful is some way to tell LLVM
that certain runtime functions behaves similar to malloc/free.

For example, it would be great if LLVM can remove the call to our
runtime allocation function (which might be GC'd, making it different
from malloc of course...) if it can prove that the result is never
escaped. (much like what is done with `malloc`/`free` pairs).

There are certain attribute (noalias for example) that helps but IIRC
the removal of malloc/free isn't available for other functions by
attaching metadata?