MC-JIT Design

Hi all,

As promised, here is the rough design of the upcoming MC-JIT*.
Feedback appreciated!

(*) To be clear, we are only calling it the MC-JIT until we have
finished killing the old one. When I say JIT below, I mean the MC-JIT.
I basically am ignoring completely the existing JIT. I will keep
things API compatible whenever possible, of course.

I see two main design directions for the JIT:

One thing that's annoying about the current JIT is that it doesn't
integrate well into debugging, profiling, and instrumentation tools.
By changing the compilation model so that you emit discrete object
files in memory, it seems like you have the opportunity to integrate
with those kinds of tools more easily. I'm wondering what the
tradeoffs are between just emitting a native object file into memory
are.

Alternatively, do you think the FOO object file format would be stable
enough to add to things like libbfd so tools can easily learn about
JITed code? I'd imagine if you did this, you could just keep bumping
a version number if the format changes, and require people who want to
use tools on the JIT to use a current version of their tool.

Reid

Hi Daniel,

First of all, thanks for taking time. :slight_smile:

I like your idea of a FOOJIT object file format.

How do you expect to handle mappings (addGlobalMapping - GlobalValue* foo is at native address 0xB4F…) ?

Olivier.

Hi all,

As promised, here is the rough design of the upcoming MC-JIT*.
Feedback appreciated!

(*) To be clear, we are only calling it the MC-JIT until we have
finished killing the old one. When I say JIT below, I mean the MC-JIT.
I basically am ignoring completely the existing JIT. I will keep
things API compatible whenever possible, of course.

I see two main design directions for the JIT:

--

#1 (aka MCJIT) - We make a new MCJITStreamer which communicates with
the JIT engine to arrange to plop code in the right place and update
various state information.

This is the most obvious approach, is roughly similar to the way the
existing JIT works, and this is the way the proposed MC-JIT patches
work (see MCJITState object).

It also happens to not be the approach I want to take. :slight_smile:

#2 (aka FOOJIT) - MC grows a new "pure" backend, which is designed
around representing everything that "can be run" on a target platform.
This is very connected to the inherent capabilities of the hardware /
OS, and is usually a superset** of what the native object format
(Mach-O, ELF, COFF) can represent.

The "pure" backend defines a hard (but non-stable) object file format
which is more or less a direct encoding of the native MC APIs (it is
not stable, so it can directly encode things like FixupKind enum
values).

I don't have a name for this format, so for now I will call it FOO.

The "MC-JIT" then becomes something more like a "FOO-JIT". It is
architected as a consumer of "FOO" object files over time. The basic
architecture is quite simple:
(a) Load a module, emit it as a "FOO" object.

While you are at it, can you support SELinux please?
SELinux only needs that you emit code to a writable memory region, and
execute it from a different executable memory region (both backed by an
unlinked tmpfile for example).
So you need to make your relocations "as if" you emitted the code at
the address of the executable region, but write them to the writable
map.

Right now in ClamAV we disable LLVM JIT when SELinux is in enforcing
mode (and fallback to our own interpreter).

(b) Load the object into a worklist, scan for undefined symbols,
dynamically emit more "FOO" modules.

Will this allow symbol lookup to fail in a better way than
llvm_report_error? Like returning failure from getPointerToFunction, or
its equivalent.

Best regards,
--Edwin

Quick follow up here:

I talked to Eric for a bit about this proposal, and he convinced me
that we should take a slightly different tack. I'll write a bit more
about it later.

The idea Eric convinced me was better is to not invent a FOO format,
but just use the native platform object format and focus on writing
essentially a runtime linker for that platforms object files.

This has various pros and cons, but I hadn't given it enough weight before.

The pros and cons we discussed:

Pro:
- We reuse all existing MC output functionality.
- We have a shorter path to working well with the external system
tools (the real runtime linker, the debugger, the unwinder).

Cons:
- Requires developing good object file libraries for LLVM. This is
also a pro, as it coalesces work other people (Michael Spencer, Nick
Kledzik) are already interested in doing.
- Means JIT is slightly more platform dependent, as the runtime
linker could have ELF or Mach-O specific bugs that wouldn't show up on
another platform.
- Doesn't acknowledge that the JIT is a separate target. Constraints
the code generator to only doing what is actually supported on the
platform.

The last con is the main thing I wanted to not preclude in a new JIT
design, but Eric convinced me that if we start by using the native
format, we can always introduce my new FOO format transparently if we
realize there is a concrete need for it.

I'll try and sketch up some more of what this design would look like
this evening...

- Daniel

Quick follow up here:

I talked to Eric for a bit about this proposal, and he convinced me
that we should take a slightly different tack. I'll write a bit more
about it later.

The idea Eric convinced me was better is to not invent a FOO format,
but just use the native platform object format and focus on writing
essentially a runtime linker for that platforms object files.

This has various pros and cons, but I hadn't given it enough weight
before.

The pros and cons we discussed:

Pro:
- We reuse all existing MC output functionality.
- We have a shorter path to working well with the external system
tools (the real runtime linker, the debugger, the unwinder).

Cons:
- Requires developing good object file libraries for LLVM. This is
also a pro, as it coalesces work other people (Michael Spencer, Nick
Kledzik) are already interested in doing.
- Means JIT is slightly more platform dependent, as the runtime
linker could have ELF or Mach-O specific bugs that wouldn't show up on
another platform.

Don't forget PE (or is it pecoff?), otherwise JIT won't work on win32.
But what does the obj format has to do with the JIT?
Sure for debug info its good to have an ELF around to give to gdb, but
otherwise can't you just emit the code to memory, with a small header
to keep info you need, and thats it?

2010/11/15 Török Edwin <edwintorok@gmail.com>

The pros and cons we discussed:

Pro:

  • We reuse all existing MC output functionality.
  • We have a shorter path to working well with the external system
    tools (the real runtime linker, the debugger, the unwinder).

Cons:

  • Requires developing good object file libraries for LLVM. This is
    also a pro, as it coalesces work other people (Michael Spencer, Nick
    Kledzik) are already interested in doing.
  • Means JIT is slightly more platform dependent, as the runtime
    linker could have ELF or Mach-O specific bugs that wouldn’t show up on
    another platform.

Don’t forget PE (or is it pecoff?), otherwise JIT won’t work on win32.
But what does the obj format has to do with the JIT?
Sure for debug info its good to have an ELF around to give to gdb, but
otherwise can’t you just emit the code to memory, with a small header
to keep info you need, and thats it?

If I understand correctly, the idea is to use native platform format (ELF, Mach-O, COFF…) even when emitting code in memory for the JIT.

What kind of restrictions will the existing object file formats impose
on the JIT? I don't know enough about the JIT and object file format
interaction to know if this will be an issue. It seems clear that it would
be worse to try to encode "extra things" in some obscure way than to create
the FOO format initially. If FOO is truly a superset of everything this
could even be the generic object file format that Michael Spencer was thinking
about creating. Perhaps this is going the wrong direction since you wanted
something less stable and directly tied to the MC infrastructure. How would
introducing the FOO format later on work?

- Jan

What kind of restrictions will the existing object file formats impose
on the JIT? I don't know enough about the JIT and object file format
interaction to know if this will be an issue. It seems clear that it would
be worse to try to encode "extra things" in some obscure way than to create
the FOO format initially. If FOO is truly a superset of everything this
could even be the generic object file format that Michael Spencer was thinking
about creating. Perhaps this is going the wrong direction since you wanted
something less stable and directly tied to the MC infrastructure. How would
introducing the FOO format later on work?

The idea here is that our JIT (which is essentially a runtime linker)
is perfectly capable of being written so that it can link object files
from distinct formats.

Linking Mach-O and COFF or ELF files might be hard, but we could
probably make it easy to link any native format and a FOO format file
without too much trouble.

The idea is that then we could have the JIT machinery use the native
format when it needs to interface with external runtime interfaces on
the platform, and it could use the FOO format when targeting code
which is purely target specific.

We sort of end up in the same place as what I originally proposed, but
this way probably lets us get something which (a) works and (b) has
nice features (like debugging support) sooner, and then introducing
the FOO-infrastructure becomes more of a quality-of-implementation
issue as to how fast we JIT, how many fancy JIT tricks we support.

- Daniel

Quick follow up here:

I talked to Eric for a bit about this proposal, and he convinced me
that we should take a slightly different tack. I'll write a bit more
about it later.

The idea Eric convinced me was better is to not invent a FOO format,
but just use the native platform object format and focus on writing
essentially a runtime linker for that platforms object files.

This has various pros and cons, but I hadn't given it enough weight
before.

The pros and cons we discussed:

Pro:
- We reuse all existing MC output functionality.
- We have a shorter path to working well with the external system
tools (the real runtime linker, the debugger, the unwinder).

Cons:
- Requires developing good object file libraries for LLVM. This is
also a pro, as it coalesces work other people (Michael Spencer, Nick
Kledzik) are already interested in doing.
- Means JIT is slightly more platform dependent, as the runtime
linker could have ELF or Mach-O specific bugs that wouldn't show up on
another platform.

Don't forget PE (or is it pecoff?), otherwise JIT won't work on win32.

Don't worry -- out of sight but not out of mind! :slight_smile:

But what does the obj format has to do with the JIT?
Sure for debug info its good to have an ELF around to give to gdb, but
otherwise can't you just emit the code to memory, with a small header
to keep info you need, and thats it?

You are right, this was the line of thought following my initial proposal.

Ultimately I think we need both pieces. We need the native object
piece, because the reality is the JIT does need to interface with
other code on the platform. We want the FOO object piece, because the
code generator etc. shouldn't be constrained by what can be
represented in the native object format.

The question is which way gets us onto the right path faster...

- Daniel

Hi,

I've been watching the MC-JIT progress for some time, and #2 certainly looks like the best idea to me. I think however you've missed an important selling point of the "FOOJIT" architecture:

* The use of a custom object file format directly enables the use of ahead-of-time compilation (using the JIT to recompile dynamically). Not only this but it allows the resaving of any functions that may have been JIT-optimised during runtime so they can be used immediately next run.

This, coincidentally, is something that I was pondering on a way to try to crowbar into the current JIT (was thinking along the lines of parsing relocatable ELF into memory and running a link step manually, then "informing" the JIT about the memory object...)

Sounds excellent.

James Molloy
Graduate Compiler Engineer, ARM Ltd.

Hi,

I’ve been watching the MC-JIT progress for some time, and #2 certainly looks like the best idea to me. I think however you’ve missed an important selling point of the “FOOJIT” architecture:

  • The use of a custom object file format directly enables the use of ahead-of-time compilation (using the JIT to recompile dynamically). Not only this but it allows the resaving of any functions that may have been JIT-optimised during runtime so they can be used immediately next run.

This, coincidentally, is something that I was pondering on a way to try to crowbar into the current JIT (was thinking along the lines of parsing relocatable ELF into memory and running a link step manually, then “informing” the JIT about the memory object…)

I have “MCJIT”-like code in my own project (sadly not open-source…) writing code in memory (without memory relocation informations) or in file (with relocation informations). This allow to reload code from previous run, or even to have a powerful server preparing code and clients executing code.
This not really tied to first or second proposition. And even for creating a “FOOJIT” format, you need a FOOJITStreamer, a FOOJITObjectWriter and probably a raw_ostream interface to write in memory. Seems really similar to the first set of patchs to me.

What need to be done :

  • We need to define a FOOJIT format. Maybe we can focus on having a FOOJIT format only for “fast path” now, and adding relocations, symbols later ?
  • We need to discuss on mapping for external relocations (I really want to cut dependency between runtime JIT and GlobalValue* : I want to run JITed functions without a module)

What if FOOJIT format is used for “fast path” only (as the current jit works) and we use ELF/MachO/COFF for more complex task “fast path” + reloading binary on next run ? JIT users will have to choose faster but one shot “FOOJIT” format or maybe slower but reusable “ELF/MachO/COFF” format ?

Olivier.

As previous mentioned here, I think the best design would be to JIT
code fast (using the FOO type) and then allow the user to build to
some other format later if he/she wants. Reloading pre-JITed functions
is a feature I'd like to see, because sometimes you have to JIT fast
an inefficient function just to get it working and later optimize it.
If you could save the functions for latter use would be a major
improvement.

And I know I don't engage lots of talks here (usually I'm just a
reader), but I'm trying to build a game based on JIT compilation for
everything, including add-ons, patches and user scripts. So I just
follow the JIT part of LLVM, but if there is anything I can help, I'd
be glad.

Miranda.

As previous mentioned here, I think the best design would be to JIT
code fast (using the FOO type) and then allow the user to build to
some other format later if he/she wants. Reloading pre-JITed functions
is a feature I'd like to see, because sometimes you have to JIT fast
an inefficient function just to get it working and later optimize it.
If you could save the functions for latter use would be a major
improvement.

And I know I don't engage lots of talks here (usually I'm just a
reader), but I'm trying to build a game based on JIT compilation for
everything, including add-ons, patches and user scripts. So I just
follow the JIT part of LLVM, but if there is anything I can help, I'd
be glad.

Miranda.

in my own VM effort (not LLVM based) I have been (for a very long time) working typically by producing object files in memory, and then "linking" them however is needed.

yeah, even for JIT, I usually actually produce both textual ASM, convert this into object files (via an "assembler" library), and link these (via a "linker" library, which shares the same DLL/SO as the assembler for historical reasons).

some people have complained to me that all this would be too slow, but in practice I have had nowhere near the levels of extreme code-spewing to where this would actually effect much (and, meanwhile, textual ASM is much nicer to work with IMO).

with some tweaks, it is possible to process in excess of 15MB of textual ASM per second, which seems plenty good enough (though with default settings it is a little slower, around 2MB/s, due to supporting ASM macros and using multiple-passes to compact jumps and similar).

currently all this is x86 and x86-64 only...

my assembler also uses a variant of NASM's syntax. basic syntax is about the same, but the preprocessor is different and many minor differences exist (including some extensions), but it is possible to write code which works with both (with some care).

GC'ed JIT is also supported (where the linker links the objects into GC'ed executable memory). this is mostly used for one-off executable objects (typically implementing closures and special purpose thunks, which are usually used as C function pointers).

I am aware of the SELinux issue, but haven't fully added support for it yet (lower priority, as I mostly develop on/for Windows...). mostly it would be done via using a software write barrier to redirect writes to the alternate memory address (or similar).

single-mapping would still be used on systems supporting read/write/execute memory.

typically, I am using COFF internally, even on Linux and similar.

caching object files to disk is done by several of my frontends, because yes, it is sort of pointless to endlessly recompile the same code every time the app starts or similar (especially since my C compiler is slow...).

or such...