Newbie

[Vania_Joloboff1]

Hello,

We are a research project in joint french-chinese laboratory. We are considering using
LLVM in our project but we’d like to have some additional info before we dive in.
Since we are new kids on the block, please bear with us…

We are interested in using LLVM for emulation of real hardware. What we have as
input is the binary code of the program to run. Today we emulate each instruction
behavior sequentially, which has pros and cons. We want to build a faster simulator,
and an idea is to decompile the binary code into an LLVM representation, then compile
it to the simulation host and run it. Hopefully it would be faster because perhaps we
may use one LLVM instruction for several machine instructions, and we can benefit
from the real host stack and the real registers instead of a simulated stack
and simulated registers.

So we have several questions:

1. Do you have an opinion on the feasibility of the project ?
   Do you know if it has been done before.

2. There is an in-memory representation for LLVM. Where shall we look in the
   documentation about it to understand how to generate it properly ?

3 We want to generate directly the in-memory IR and dynamicall call the LLVM code
generator on a chunk of code that has been decompiled, not a complete program.
Is this possible ? Is it worthwile in terms of performance ?

Sincerely,
– Vania

[John_Criswell2]

Vania Joloboff wrote:

Hello,

We are a research project in joint french-chinese laboratory. We are considering using
LLVM in our project but we'd like to have some additional info before we dive in.
Since we are new kids on the block, please bear with us...

We are interested in using LLVM for emulation of real hardware. What we have as
input is the binary code of the program to run. Today we emulate each instruction
behavior sequentially, which has pros and cons. We want to build a faster simulator,
and an idea is to decompile the binary code into an LLVM representation, then compile
it to the simulation host and run it. Hopefully it would be faster because perhaps we
may use one LLVM instruction for several machine instructions, and we can benefit
from the real host stack and the real registers instead of a simulated stack
and simulated registers.

Very cool. I'm probably not the person best qualified to answer your questions, but since no one else has answered them yet, I'll take a shot.

So we have several questions:

1. Do you have an opinion on the feasibility of the project ?
           Do you know if it has been done before.

There was a Google Summer of Code (GSoC) project last year where someone started the work of modifying Qemu (a simulator) to use LLVM for JIT compilation for faster simulation. I don't know how well it worked, but it's very similar to what you want to do. I'd say it's quite feasible, and, in fact, LLVM should make it easier with its JIT libraries.

2. There is an in-memory representation for LLVM. Where shall we look in the
documentation about it to understand how to generate it properly ?

The LLVM Programmers Manual (LLVM Programmer’s Manual — LLVM 16.0.0git documentation) might be a good place to start; it describes the basic classes used for the LLVM in-memory IR in the latter half of the document. The doxygen documentation is also surprisingly useful (LLVM Programmer’s Manual — LLVM 16.0.0git documentation) to describe the details of the LLVM programming APIs.

The in-memory representation is very easy to generate if you're writing your program in C++. Basically, there are C++ classes for each type of object in the LLVM IR. To create the in-memory IR, you simply create a new object of the correct class. For example, to create a new function, you simply create a new Function object (i.e. Function * f = new Function (...)).

3 We want to generate directly the in-memory IR and dynamicall call the LLVM code
    generator on a chunk of code that has been decompiled, not a complete program.
/ /Is this possible ? Is it worthwile in terms of performance ?

This should be possible using the JIT libraries included with LLVM. I have not used these extensively, but I'm sure someone else on the list has and would be happy to answer any specific questions you may have.

Whether it will be worthwhile in performance, I am not sure, but since you are currently doing emulation, I'd think that dynamic binary translation with LLVM would be much faster.

-- John T.

[Patrick_Meredith]

Vania Joloboff wrote:

Hello,

We are a research project in joint french-chinese laboratory. We are
considering using
LLVM in our project but we'd like to have some additional info before
we dive in.
Since we are new kids on the block, please bear with us...

We are interested in using LLVM for emulation of real hardware. What
we have as
input is the binary code of the program to run. Today we emulate each
instruction
behavior sequentially, which has pros and cons. We want to build a
faster simulator,
and an idea is to decompile the binary code into an LLVM
representation, then compile
it to the simulation host and run it. Hopefully it would be faster
because perhaps we
may use one LLVM instruction for several machine instructions, and we
can benefit
from the real host stack and the real registers instead of a simulated
stack
and simulated registers.

Very cool. I'm probably not the person best qualified to answer your
questions, but since no one else has answered them yet, I'll take a shot.

So we have several questions:

1. Do you have an opinion on the feasibility of the project ?
           Do you know if it has been done before.

There was a Google Summer of Code (GSoC) project last year where someone
started the work of modifying Qemu (a simulator) to use LLVM for JIT
compilation for faster simulation. I don't know how well it worked, but
it's very similar to what you want to do. I'd say it's quite feasible,
and, in fact, LLVM should make it easier with its JIT libraries.

2. There is an in-memory representation for LLVM. Where shall we look
in the
documentation about it to understand how to generate it properly ?

The LLVM Programmers Manual
(LLVM Programmer’s Manual — LLVM 16.0.0git documentation) might be a good place to
start; it describes the basic classes used for the LLVM in-memory IR in
the latter half of the document. The doxygen documentation is also
surprisingly useful (LLVM Programmer’s Manual — LLVM 16.0.0git documentation) to
describe the details of the LLVM programming APIs.

The in-memory representation is very easy to generate if you're writing
your program in C++. Basically, there are C++ classes for each type of
object in the LLVM IR. To create the in-memory IR, you simply create a
new object of the correct class. For example, to create a new function,
you simply create a new Function object (i.e. Function * f = new
Function (...)).

3 We want to generate directly the in-memory IR and dynamicall call
the LLVM code
    generator on a chunk of code that has been decompiled, not a
complete program.
/ /Is this possible ? Is it worthwile in terms of performance ?

You would basically *have* to do this:
binary translation is a very difficult problem. What
ISA are you currently implementing? If it is has fixed instruction width this makes the process *much* easier. Even
with a fixed instruction width keep in mind that it is virtually impossible to to do static binary translation on anything
but the simpliest of programs (in particular indirect jumps are painful). Whatever you do will probably end up being
dynamic, so I think this is your best route.

[Tilmann_Scheller1]

Hello,

We are a research project in joint french-chinese laboratory. We are considering using
LLVM in our project but we’d like to have some additional info before we dive in.
Since we are new kids on the block, please bear with us…

We are interested in using LLVM for emulation of real hardware. What we have as
input is the binary code of the program to run. Today we emulate each instruction
behavior sequentially, which has pros and cons. We want to build a faster simulator,
and an idea is to decompile the binary code into an LLVM representation, then compile
it to the simulation host and run it. Hopefully it would be faster because perhaps we
may use one LLVM instruction for several machine instructions, and we can benefit
from the real host stack and the real registers instead of a simulated stack
and simulated registers.

So we have several questions:

1. Do you have an opinion on the feasibility of the project ?
   Do you know if it has been done before.

Using LLVM for dynamic binary translation is definitely feasible, last year I was working on llvm-qemu during Google Summer of Code 2007 which in fact does binary translation with LLVM. It is a modified version of qemu which uses the LLVM JIT for optimization and code generation. Currently it translates from ARM machine code to LLVM IR (at basic block level) and via the LLVM JIT to x86 machine code. All source architectures supported by qemu (x86, x86-64, ARM, SPARC, PowerPC, MIPS, m68k) can be translated to LLVM IR this way (adding support for one of these architectures only requires minor changes to llvm-qemu).

The end result was that llvm-qemu was running about half the speed of regular qemu on the synthetic benchmark nbench (using a hotspot-like approach: interpretation of blocks with few executions and JITing of blocks with high execution counts). However, there is still potential for improvement, one being an efficient implementation of direct block chaining (in certain cases a block can directly jump to its successor instead of falling back to the dispatcher, this is currently implemented with calls instead of jmps, which should be possible to implement with jmps now, after the recent work on tail call optimizations). Direct block chaining is a very useful optimization, on the nbench test case enabling direct block chaining for regular qemu leads to a 100% speed increase. Another promising improvement would be the capability to build “super”-blocks from a set of connected basic blocks, resembling a “hot path”. This work is partially finished and, once complete, should yield a significant performance improvement since a “super”-block offers a lot more optimization potential compared to a single basic block. Nevertheless, it is unlikely that llvm-qemu will ever be much faster than regular qemu (by replacing its code generator completely, which it currently does), which is due to the fact that regular qemu has a very lightweight code generator (it basically only copies blocks of memory and performs some patching to them and only does static register allocation) which generates reasonably good code, with a very low overhead for compilation time. In contrast the LLVM JIT generates really high quality code (in fact the JIT and the static compiler share the same code generator), but at a higher price in terms of compilation time. Ideally the current code generator of qemu would coexist with the LLVM JIT in llvm-qemu, allowing for different levels of code quality/compilation time depending on the execution frequency of a particular block.

I guess in your situation, the chances are much higher that you will see a significant performance increase since you apparently don’t do any dynamic binary translation yet, especially if you decide to use your existing interpreter in combination with the LLVM JIT in a hotspot-like manner.

An important question is how you perform the translation from your source architecture to LLVM IR, for llvm-qemu I could benefit from the fact that qemu translates from source machine code to an intermediate representation which has its instructions implemented in C, thus I could use llvm-gcc to compile the instructions to equivalent LLVM IR and did not have to worry about the actual translation from machine code to qemu IR. Going directly from machine code to LLVM IR certainly requires more effort.

Which architectures are you interested in particularly?

3 We want to generate directly the in-memory IR and dynamicall call the LLVM code
generator on a chunk of code that has been decompiled, not a complete program.
Is this possible ? Is it worthwile in terms of performance ?

Yes, that’s perfectly possible and that’s what llvm-qemu does too (translation is performed at basic block level). As Patrick already pointed out, static recompilation is not really feasible in most cases.

If you’re interested, you can find llvm-qemu at http://code.google.com/p/llvm-qemu/, the Wiki contains a page which lists the progress of the project (including some numbers regarding performance).

Greetings,

Tilmann Scheller

[RalphCorderoy]

Hi Tilmann,

Nevertheless, it is unlikely that llvm-qemu will ever be much faster
than regular qemu (by replacing its code generator completely, which
it currently does), which is due to the fact that regular qemu has a
very lightweight code generator (it basically only copies blocks of
memory and performs some patching to them and only does static
register allocation) which generates reasonably good code, with a very
low overhead for compilation time. In contrast the LLVM JIT generates
really high quality code (in fact the JIT and the static compiler
share the same code generator), but at a higher price in terms of
compilation time.

How about storing generated code on disc? Or the intermediate IR? I'd
typically use the same things under qemu day after day and would be
happy to slowly build up a cache on disc. Perhaps starting qemu with a
'spend time and add to cache' option when I'm getting it to learn and a
'use only what's in the cache already' when I having got the time to
wait.

Cheers,

Ralph.

[Tilmann_Scheller1]

A similar approach is used by FX!32 to translate Win32 x86 binaries to Alpha binaries (to run them on Windows NT for Alpha). Basically FX!32 performs incremental static recompilation. On the first run the binary runs with an interpreter and profiling data is gathered (e.g. the targets of indirect branches, as they usually can’t be determined statically). FX!32 runs a background process which uses the gathered data to statically recompile the binary (doing optimizations which would be too expensive to be done at runtime). The next time the user executes the binary, he is already executing native Alpha code and in case he executes parts of the program which he didn’t reach the last time or which FX!32 couldn’t determine statically, FX!32 will fall back to the interpreter and collect profiling data again. This way the binary is translated incrementally from x86 to Alpha.

In principle a system like FX!32 could be implement with llvm-qemu. For user-mode emulation it is certainly possible (these days, the demand for such a system seems rather low though). However, for system emulation (unlike user-mode emulation, system emulation also requires MMU emulation) I would say static recompilation is not feasible since addresses change very frequently, e.g. a program running on the system is very likely to be loaded at different addresses on every invocation, so you would end up falling back to the interpreter most of the time.

Greetings,

Tilmann Scheller

[John_Criswell2]

Ralph Corderoy wrote:

Hi Tilmann,

Nevertheless, it is unlikely that llvm-qemu will ever be much faster
than regular qemu (by replacing its code generator completely, which
it currently does), which is due to the fact that regular qemu has a
very lightweight code generator (it basically only copies blocks of
memory and performs some patching to them and only does static
register allocation) which generates reasonably good code, with a very
low overhead for compilation time. In contrast the LLVM JIT generates
really high quality code (in fact the JIT and the static compiler
share the same code generator), but at a higher price in terms of
compilation time.
    

One of the things I noticed in the last message on llvm-qemu was that you were compiling with output from qemu with llvm-gcc? Is this correct?

If so, then wouldn't that be one of the sources of overhead when using LLVM? It would make more sense to me (but also be more implementation work) to link the LLVM JIT and CodeGen libraries directly into Qemu and to forgo the Qemu->C->LLVM translation process. Not only should this speed it up (because you're removing the C preprocessing, C parsing, and exeve() overhead), but it should also give you more control over what LLVM is doing (you can use LLVM's JIT infrastructure to re-codegen functions at run-time and things like that).

-- John T.

[Tilmann_Scheller1]

Not really, llvm-gcc is only invoked once when llvm-qemu is being built.

Qemu’s code generator works like this: a source machine instruction is decomposed into several simpler micro ops (basically the IR of qemu), for every micro op there is a C implementation, which at build time is compiled for the respective target architecture. At build time the actual code generator is generated by the tool dyngen, which parses the compiled micro op object file and generates a C function which receives a micro op stream and generates the corresponding machine code by concatenating the respective machine code for the micro ops and doing some additional patching (like inserting parameters for the micro ops). What I did for llvm-qemu is to write llvm-dyngen, which instead of an ELF file reads in a bitcode op.o (generated by compiling op.c with llvm-gcc) and creates a function which basically concatenates and patches the LLVM IR ops and after that JITs them. Every source architecture has different micro ops, thus llvm-dyngen needs to be used to create the code generator for a particular architecture.

Greetings,

Tilmann

[Vania_Joloboff]

Thanks to all those who responded to our email.

Tilmann Scheller wrote:

However, there is still potential for improvement, one being an efficient implementation of direct block chaining (in certain cases a block can directly jump to its successor instead of falling back to the dispatcher, this is currently implemented with calls instead of jmps, which should be possible to implement with jmps now, after the recent work on tail call optimizations). Direct block chaining is a very useful optimization, on the nbench test case enabling direct block chaining for regular qemu leads to a 100% speed increase. Another promising improvement would be the capability to build “super”-blocks from a set of connected basic blocks, resembling a “hot path”. This work is partially finished and, once complete, should yield a significant performance improvement since a “super”-block offers a lot more optimization potential compared to a single basic block. Nevertheless, it is unlikely that llvm-qemu will ever be much faster than regular qemu (by replacing its code generator completely, which it currently does), which is due to the fact that regular qemu has a very lightweight code generator (it basically only copies blocks of memory and performs some patching to them and only does static register allocation) which generates reasonably good code, with a very low overhead for compilation time. In contrast the LLVM JIT generates really high quality code (in fact the JIT and the static compiler share the same code generator), but at a higher price in terms of compilation time. Ideally the current code generator of qemu would coexist with the LLVM JIT in llvm-qemu, allowing for different levels of code quality/compilation time depending on the execution frequency of a particular block.

I guess in your situation, the chances are much higher that you will see a significant performance increase since you apparently don’t do any dynamic binary translation yet, especially if you decide to use your existing interpreter in combination with the LLVM JIT in a hotspot-like manner.

We do dynamic binary translation. We are in a similar situation to qemu except we are SystemC / TLM compliant for hardware and bus models. Our current technology is somewhat like qemu, we translate the binary into “semantic ops”, which are pre-compiled at build time, like qemu. Then we execute that code. The difference is that we extensively use partial evaluation to translate each binary instruction into one specialized op. We do not intend to use LLVM at the basic block level. Our initial idea is similar to what you call super-block, but also to carry the LLVM compilation in a separate thread, so that we can use the now available quad-core PC’s without slowing down the on-going execution. In fact similar to what we did a few years ago with the Java VM,
but on a separate computer because we did not have even dual-core at the time.

An important question is how you perform the translation from your source architecture to LLVM IR, for llvm-qemu I could benefit from the fact that qemu translates from source machine code to an intermediate representation which has its instructions implemented in C, thus I could use llvm-gcc to compile the instructions to equivalent LLVM IR and did not have to worry about the actual translation from machine code to qemu IR. Going directly from machine code to LLVM IR certainly requires more effort.

This is the effort we are considering. But we already have C++ binary decoders.

Which architectures are you interested in particularly?

ARM, MIPS, PowerPC and SH
  

Thanks again,
Vania

[Tilmann_Scheller1]

Sounds great, maybe pre-compiling to LLVM IR is an option for you too?
(at least to get an initial working system)

I would be curious to see the performance results of a system with the
properties you mentioned (optimization at super-block level,
compilation on a different core) and IMO using LLVM for such a system
would be a great choice.

Is there any public information about your emulation system? E.g. a
paper or a web site?

Greetings,

Tilmann

[Vania_Joloboff]

Tilmann Scheller wrote:

I would be curious to see the performance results of a system with the
properties you mentioned (optimization at super-block level,
compilation on a different core) and IMO using LLVM for such a system
would be a great choice.
  

We have looked more into LLVM docs. Indeed it looks feasible and promissing.
We are wondering about passes. The kaleidoscope tutorial refers to

    OurFPM.add(createInstructionCombiningPass());
    // Reassociate expressions.
    OurFPM.add(createReassociatePass());
    // Eliminate Common SubExpressions.
    OurFPM.add(createGVNPass());
    // Simplify the control flow graph (deleting unreachable blocks, etc).
    OurFPM.add(createCFGSimplificationPass());

Where are these passes documented ?

Is there any public information about your emulation system? E.g. a
paper or a web site?
  

Our new system is too young. We do not have accepted papers yet …
References to our previous work :
Vania

[Holger_Schurig1]

Where are these passes documented ?

From http://llvm.org/docs/

http://llvm.org/docs/Passes.html: LLVM's Analysis and Transform
Passes - A list of optimizations and analyses implemented in
LLVM.

BTW: your e-mail client is weird. It doesn't denote which parts
are quoted by "> " at the left side. Also you sent HTML e-mail,
which you shouldn't normally do when sending to mailing lists.
Those things tend to be not nice to email web archives.

[Vania_Joloboff]

Holger Schurig wrote:

BTW: your e-mail client is weird. It doesn't denote which parts are quoted by "> " at the left side. Also you sent HTML e-mail, which you shouldn't normally do when sending to mailing lists. Those things tend to be not nice to email web archives.
  

Apologies. I had forgotten to set the "plain text"option for this mailing list.
This message should not be in html...

Vania