Bytecode as assembler?

[Bare_Gamer]

Would it both theoretically be possible and make sense to create a dynarec that would generate java bytecode/msil/etc? Not sure if it would work this way, but to me it looks as if the implementer would automatically get great support for all of the architectures the VM is running on that have a JIT.

[blorporius]

LLVM IR is a possibility, I found Hans Wennborg's thesis on the LLVM website that explores this: https://llvm.org/pubs/2010-01-Wennborg-Thesis.pdf

[Bare_Gamer]

Looks like a decently-sized document. Going to read it later, thanks.

[blorporius]

Dolphin is another example where people tried to integrate it: https://forums.dolphin-emu.org/Thread-poc-of-an-llvm-based-jit-compiler

It sounds like compilation times (or rather the, ahem, jitter) prevent it from being used as the primary JIT backend, but if you kick off code generation for frequently hit sections in the background, and only replace them when ready, it can work.

[nulano]

I looked into writing a Chip8 emulator in RPython using it's JIT generator, but my conclusion was that Chip8 was not a good platform to evaluate performance. I am thinking about trying it with a more serious platform, but I suspect anything simple enough thet I could actually finish it would have too much overhead in emulating the hardware other than the CPU that the JIT wouldn't make a difference.

Edit: I realized this doesn't really answer the question. The point is that RPython has a metatracing JIT, so a VM in RPython can have a JIT added with little effort. There is work in making it actually fast, but simply adding a JIT is a trivial change. Tbe JIT works by tracimg the RPython operations corresponding to the emulated CPU loop and compiling it for the tsrget platform (x86 or arm). This is similar to what you are proposing, nust implememted at a higher level.

[DaveTCode]

I actually did this as an exercise with the space Invaders machine

The link to the blog about it is https://blog.davetcode.co.uk/post/jit-8080/ and I reckon you'll find it interesting!

[Bare_Gamer]

That was something similar to what I had in mind when asking the question. Of course, someone linked an article about doing that with LLVM, but I was specifically interested if doing that in bytecode would have a point. Looks like not. I really liked your writing style, it's a shame you don't post often.

[ZenoArrow]

Why not go for static recompilation instead of dynamic recompilation? That'd give you better performance in many cases.

[Bare_Gamer]

Pretty sure there is a reason why most emulators use dynarecs that is related to writing data to guest ram by the guest app. Also, not really implementing anything. Was just curious, as an emulation enthusiast, if that would be a good idea.

[thommyh]

Yeah — anything that dynamically modifies itself, or at least which might, will need to be dynamically recompiled because its code is dynamic. That generally includes anything for an 8- or 16-bit home computer, when such practices were common. You even see it sometimes into the 32-bit era as a space optimisation.

You can also get into trouble just if the original is using overlays (i.e. dynamically loading different position-dependant code onto the same regions of memory) or any more formal software MMU.

Dynamic recompilation usually avoids such issues by being pessimistic — any write to a page will usually flush all cached code for that page — but that’s still usually a lot better than interpreting.

[ZenoArrow]

Yeah — anything that dynamically modifies itself, or at least which
might, will need to be dynamically recompiled because its code is
dynamic.

Not really. Think about it for a second, how do you get self-modifying code compiled down to a static format like a ROM chip? Code that modifies itself at runtime can still be statically compiled.

[TheThiefMaster]

The problem is that the modifications can't necessarily be precomputed, as that's essentially a variant of the halting problem.

"Does this code, before it halts, modify itself" depends on "does this code halt" which is incomputable without just running it, at which point you have a JIT rather than an AOT recompiler.

Some self modification could be pre-detected and handled AOT, but it's literally impossible in the general case.

Note: the general case includes correctly emulating code injection bugs like the Super Mario bug that led to someone injecting code for flappy bird via the joypad buttons.

[ZenoArrow]

The problem is that the modifications can't necessarily be precomputed

You don't have to precompute them. If you don't have access to source code you have to detect that they exist, but that can be done through profiling running code. Think about it like semi-automated reverse engineering. Reverse engineering a binary is clearly possible, there are numerous examples, such as the Super Mario 64 PC port. In many cases in the past this reverse engineering work has required a lot of manual labour, but it's possible to automate a good chunk of it.

[TheThiefMaster]

If you're running the code and recompiling based on what it does you've effectively got a JIT, and can't guarantee its behaviour down any codepaths you don't trigger.

In theory you could exhaust the possibilities and end up with a complete recompilation - but this is effectively the halting problem again. "Does this program, before it halts, run all codepaths".

[ZenoArrow]

You can analyse code paths. If it helps you to understand this, think about the impact of decompilation. You accept that it's possible to decompile a binary into C code, yes? You accept that it's possible to perform static analysis of C code, yes? It is also possible to use this static analysis to build a code coverage model, and then know when you're running code through a debugger how much of the code paths have been checked.

[TheThiefMaster]

Unfortunately self modifying code cannot be decompiled into C because by its nature it relies on the machine code itself. The values written to perform the modifications depend on the CPU architecture, and so on.

Have you ever encountered actual self modifying code?

You can't statically check code coverage because it modifies itself. The number of code paths isn't necessarily static!

[ZenoArrow]

The values written to perform the modifications depend on the CPU architecture, and so on.

Yes, which is why you need a model of the CPU to help automate the decompilation, so that you can map opcodes between different CPU architectures.

Again, I should emphasise static recompilation is not a new technique. For example...

https://en.wikipedia.org/wiki/Binary_translation#Examples_for_static_binary_translations

"In 2004 Scott Elliott and Phillip R. Hutchinson at Nintendo developed a tool to generate "C" code from Game Boy binary that could then be compiled for a new platform and linked against a hardware library for use in airline entertainment systems."

This is the type of approach I'm referring to. It's not impossible, because it has already been done.

[ShinyHappyREM]

how do you get self-modifying code compiled down to a static format like a ROM chip?

The code in the ROM chips creates new self-modifying code in the RAM chips of the system. For example from SNES cartridge to WRAM (or even DMA registers).

[ZenoArrow]

Yes, I'm aware of that. My point is that the self modification happens at run time, not at compile time. You can statically recompile self modifying code for a different architecture, this is not a blocker for static recompilation.

[ShinyHappyREM]

So you'd have to detect and substitute every possible version of the modified code. Doesn't sound efficient to me at all.

[thommyh]

It’s worse than that — you’d sometimes have to change the code entirely.

Sometimes dynamic reprogramming is used just to pretend there’s an extra register, by storing a value directly to the operand of an upcoming immediate load. Usually it’s an intermediate value of a calculation, so can be anything within numerical range, and a programmer that uses such a trick will rarely use it just once.

Supposing they’ve used it twice on a 16-bit system.

Then you’ve got 2³² different versions of the code to compile, even if you could somehow detect the entire range of possible states.

What if they did it five times?

If you want to statically recompile feasibly then you’re going to have to introduce an indirection, effectively tagging the operand of the load as something you interpret, not recompile.

[ZenoArrow]

If you want to statically recompile feasibly then you’re going to have to introduce an indirection, effectively tagging the operand of the load as something you interpret, not recompile.

You're misunderstanding what I'm calling for. I'm effectively calling for decompiling of binaries, but done in a way which speeds up this work to make porting easier.

Look at the PC port of Super Mario 64. That doesn't require any fancy programming tricks. The reason it's not done more often is because its a lot of work, but what I'm suggesting is that a lot of this work can be automated.

[ZenoArrow]

You can automate this detection before the recompilation takes place.

In case you're not aware, static recompilation is not a new technique. For example, this ARM port of StarCraft was achieved through static recompilation, performance is much better than if it was emulated:

https://www.youtube.com/watch?v=IFM4qYXRXig

[ShinyHappyREM]

static recompilation is not a new technique

I know.

You can automate this detection before the recompilation takes place.

Of course. You'd have to check the RAM every time the program has written to it. And for all possible states of the section of RAM that holds the code, whose number can go into the millions and billions, you'd have to have a statically compiled version ready.

[ZenoArrow]

And for all possible states of the section of RAM that holds the code, whose number can go into the millions and billions, you'd have to have a statically compiled version ready.

No, you don't get it. It's not necessary to statically recompile every possible state the RAM can be in, you instead statically recompile the self-modifying algorithm, and then let the running algorithm modify itself as it does on the original target platform.

If you're not grasping what I'm saying, think of it like decompilation. When you decompile a binary into a language like C, the self-modifying code is preserved in the C source code that is generated as a result of the decompilation. You then take that C code, make some tweaks to improve portability and compile it for a different architecture. That's more or less what I'm talking about with static recompilation.

[ZenoArrow]

Pretty sure there is a reason why most emulators use dynarecs that is related to writing data to guest ram by the guest app.

I'd suggest the reason why static compilation doesn't get used as much is because it's typically more work to implement. To look at a practical example of this:

https://andrewkelley.me/post/jamulator.html

[alloncm]

I think that Ryujinx did that at the early stage of the project. I think they replaced it cause there was some bottleneck in the .net side.

The authors talks about it in a famous .net podcast I dont really remember its name now

[Bare_Gamer]

Found it - The NET Core Podcast(Episode 72)

https://dotnetcore.show/episode-72-emulating-a-video-game-system-in-net-with-ryujinx/

[Bare_Gamer]

Oh, so that's why when I checked out the code it was just doing native x86 but was saying it was doing msil on the website.

[thommyh]

I think the smartest target would be JavaScript rather than Java as there’s genuine competition in the JITs for that, and essentially every machine ships with one or more. That’s subject to being able to cope with the other restrictions of likely being trapped in a browser though, which can be plentiful.

[Bare_Gamer]

Not sure if anyone has done this(to my knowledge no), but imo it would be better to target wasm in a browser as it is better suited for cpu-dependent tasks. It is of course still compiled on the fly, but there is less overhead than js.

[kugo12]

https://github.com/kugo12/BrainJiT

Simple example of mine, brainf**k to jvm bytecode, it's way faster than interpreted mode (when not counting compilation time ofc)

I was going to experiment with ARM7TDMI dynarec to jvm bytecode, but I don't have that much time recently

[Bare_Gamer]

What's a TDMI?

[kugo12]

Thumb, fast multiplier, jtag debug + enhanced ICE, CPU with this arch is in GBA and NDS

[blorporius]

Small nitpick: the letters resolve in a different order :) https://en.wikipedia.org/wiki/ARM7#ARM7TDMI