3 ms·

Maybe one day someone will write a native JIT for x86[-64]. Native x86 code in, optimized native x86 code out. It should be possible to JIT native code and run

by vardump 11y ago

Maybe one day someone will write a native JIT for x86[-64]. Native x86 code in, optimized native x86 code out. It should be possible to JIT native code and run it faster than running the native code directly! It could do: 1) Peephole optimizations (and known sequence/function replacement). Utilize target instruction set extensions. 2) "Constant" folding. Replace code that processes values that can be proven to be immutable with a constant. Also removes unnecessary branches. Guards at loads, indirect stores, by marking page read only, etc. 3) Vectorization. This includes widening existing vectorization if target instruction set supports it. 4) Loadable library call inlining. This could even mean inlining system calls, but of course in that case the JIT would need to be running in kernel... 5) Profile guided optimization. Of course there are some very hard problems. For example, there'd need to be guards for the case the assumed constant value does change. Or that unexpected call target occurs. Etc. Maybe this system could learn possible call targets and unexpectedly changing "constants".

lmz 11y ago
Wasn't that what some x86 emulators did before hardware virtualization? (maybe not to that extent).
- dfox 11y ago
  Translating code for one architecture into code for host (possibly same) architecture is what Qemu does. But Qemu does not do any significant optimizations in this process as it attempts to do this without extensive knowledge of host architecture (it does not even directly generate separate instructions). Other thing that comes to mind is HP Dynamo (http://www.hpl.hp.com/techreports/1999/HPL-1999-78.html http://www.hpl.hp.com/techreports/1999/HPL-1999-78.html), which essentially is PA-RISC on PA-RISC optimizing JIT VM (that also does trace-driven optimization).
ndesaulniers 11y ago
Doesn't LTO do some of these things?
- vardump 11y ago
  I was talking about runtime executable optimization. In general, I don't think this is possible at link time. If the binary is linked in 2015, it's not possible to know about CPUs available in 2035 or to utilize the new features, even if they're binary compatible. Compiling (incl. linking) bakes in assumptions about target CPU. If these assumptions are incorrect, the performance will be sub-optimal. Even pathologic cases are possible, like order of magnitude lower performance in AMD Jaguar AVX stores. CPUs have wildly different combinations of instruction set extensions. Instruction throughput and latency varies significantly. Cache subsystems are different. So code that runs well on one CPU can run sub-optimally on another binary-compatible CPU.
- jevinskie 11y ago
  The LTOs I know of always operate on an IR like LLVM or GIMPLE, not binary code.
jevinskie 11y ago
Look at things like PIN tool [0], DynamoRIO [1], and Valgrind [2] to do this at runtime or at any of the LLVM based decompilers like dagger [3], libcpu [4], or fracture [5] to do AoT compilation. I'm not sure if QEMU's IR would be a good fit. DynamoRIO and Valgrind IR may also be able to be AoTed if you work hard enough. Of course, stuff like indirect branches and self-modifying code can really throw a wrench in your JITter's gears. [0]: https://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool https://software.intel.com/en-us/articles/pin-a-dynamic-bina... [1]: http://www.dynamorio.org/ http://www.dynamorio.org/ [2]: http://valgrind.org/ http://valgrind.org/ [3]: http://dagger.repzret.org/ http://dagger.repzret.org/ [4]: https://github.com/libcpu/libcpu https://github.com/libcpu/libcpu [5]: https://github.com/draperlaboratory/fracture https://github.com/draperlaboratory/fracture
pag 11y ago
What you're talking about is binary translation. Here are a few pointers: - DynamoRIO: http://www.dynamorio.org/ - Intel PIN: https://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool - Rosetta: https://www.apple.com/asia/rosetta/ - Transmeta Crusoe: http://en.wikipedia.org/wiki/Transmeta_Crusoe - Binary Translation using Peephole Superoptimization: http://theory.stanford.edu/~aiken/publications/papers/osdi08.pdf You might also find program specialization interesting and related: - SynthesisOS: http://valerieaurora.org/synthesis/SynthesisOS/ I've personally created three binary translators, and worked on DynamoRIO as well as a Linux kernel variant of DynamoRIO. It's hard to do well / right, but at the same time it's fun. If you're interested, it might be worth starting with an existing system to give yourself some good ideas of how to structure the system, and perhaps even how not to do it. It might also give you a sense of a niche worth targeting. Your list is interesting, but tackling all that is non-trivial, or at least, tackling all that in a general way is non-trivial. However, if you restrict yourself to some subset of programs / use cases, then you can make an impact. Creating faster code is incredibly tricky. That was the original motivation for things like DynamoRIO (and HP's Dynamo before it), and it's mostly not worth it. You can sometimes do it for specific workloads in a way that is similar to feedback-directed optimization. You can also sometimes do with with inlining / outlining (e.g. moving cold code off the critical path of the icache) / specializing (creating specialized versions of code for specific inputs, use sites, etc.).

by vardump 11y ago

lmz 11y ago

Wasn't that what some x86 emulators did before hardware virtualization? (maybe not to that extent).

dfox 11y ago
Translating code for one architecture into code for host (possibly same) architecture is what Qemu does. But Qemu does not do any significant optimizations in this process as it attempts to do this without extensive knowledge of host architecture (it does not even directly generate separate instructions). Other thing that comes to mind is HP Dynamo (http://www.hpl.hp.com/techreports/1999/HPL-1999-78.html http://www.hpl.hp.com/techreports/1999/HPL-1999-78.html), which essentially is PA-RISC on PA-RISC optimizing JIT VM (that also does trace-driven optimization).

ndesaulniers 11y ago

Doesn't LTO do some of these things?

vardump 11y ago
I was talking about runtime executable optimization. In general, I don't think this is possible at link time. If the binary is linked in 2015, it's not possible to know about CPUs available in 2035 or to utilize the new features, even if they're binary compatible. Compiling (incl. linking) bakes in assumptions about target CPU. If these assumptions are incorrect, the performance will be sub-optimal. Even pathologic cases are possible, like order of magnitude lower performance in AMD Jaguar AVX stores. CPUs have wildly different combinations of instruction set extensions. Instruction throughput and latency varies significantly. Cache subsystems are different. So code that runs well on one CPU can run sub-optimally on another binary-compatible CPU.
jevinskie 11y ago
The LTOs I know of always operate on an IR like LLVM or GIMPLE, not binary code.

jevinskie 11y ago

Look at things like PIN tool [0], DynamoRIO [1], and Valgrind [2] to do this at runtime or at any of the LLVM based decompilers like dagger [3], libcpu [4], or fracture [5] to do AoT compilation. I'm not sure if QEMU's IR would be a good fit. DynamoRIO and Valgrind IR may also be able to be AoTed if you work hard enough. Of course, stuff like indirect branches and self-modifying code can really throw a wrench in your JITter's gears. [0]: https://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool https://software.intel.com/en-us/articles/pin-a-dynamic-bina... [1]: http://www.dynamorio.org/ http://www.dynamorio.org/ [2]: http://valgrind.org/ http://valgrind.org/ [3]: http://dagger.repzret.org/ http://dagger.repzret.org/ [4]: https://github.com/libcpu/libcpu https://github.com/libcpu/libcpu [5]: https://github.com/draperlaboratory/fracture https://github.com/draperlaboratory/fracture

pag 11y ago

What you're talking about is binary translation. Here are a few pointers: - DynamoRIO: http://www.dynamorio.org/ - Intel PIN: https://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool - Rosetta: https://www.apple.com/asia/rosetta/ - Transmeta Crusoe: http://en.wikipedia.org/wiki/Transmeta_Crusoe - Binary Translation using Peephole Superoptimization: http://theory.stanford.edu/~aiken/publications/papers/osdi08.pdf You might also find program specialization interesting and related: - SynthesisOS: http://valerieaurora.org/synthesis/SynthesisOS/ I've personally created three binary translators, and worked on DynamoRIO as well as a Linux kernel variant of DynamoRIO. It's hard to do well / right, but at the same time it's fun. If you're interested, it might be worth starting with an existing system to give yourself some good ideas of how to structure the system, and perhaps even how not to do it. It might also give you a sense of a niche worth targeting. Your list is interesting, but tackling all that is non-trivial, or at least, tackling all that in a general way is non-trivial. However, if you restrict yourself to some subset of programs / use cases, then you can make an impact. Creating faster code is incredibly tricky. That was the original motivation for things like DynamoRIO (and HP's Dynamo before it), and it's mostly not worth it. You can sometimes do it for specific workloads in a way that is similar to feedback-directed optimization. You can also sometimes do with with inlining / outlining (e.g. moving cold code off the critical path of the icache) / specializing (creating specialized versions of code for specific inputs, use sites, etc.).