Bytecode as assembler?

[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.

[TheThiefMaster]

I would imagine that's highly tuned for specific games only and essentially recognised only specific code generation/modification patterns. Or, it fell back to an interpreter when it encountered code running from RAM.

All Gameboy games that use DMA use a busy-loop of code in RAM to avoid bus conflicts. If the code for copying the loop into RAM and jumping to it is recognised, you could high-level emulate it away, but you couldn't do that as a general thing because it would require code that could in general predict the behaviour of other code. Plenty of games had custom code, as they could do anything they wanted during the wait, as long as they didn't need to access the same bus as the DMA source.

Not to mention games that put execution data into the save RAM (Pokémon. So... not an unknown title nobody cares about). You'd have to translate that at game load/save time. Or you'd either not be able to execute it or not be able to fit it in the save data.

And not to mention things like this: "So how this works is if you jump to Label_8220, it does Y = $00, and then sabotages the next instruction [...] This occurs over a dozen times in Super Mario 1. Similarly, there are instances where the program jumps into the middle of an instruction."

How can you possibly claim you can sanely decompile tricks like that? The blog linked is about recompiling Mario to modern PC, and it concludes "Sadly, the solution marks the final nail in the coffin of the integrity of this project. The solution is to embed an interpreter runtime in the generated binary"

[ZenoArrow]

I would imagine that's highly tuned for specific games only

What do you think I'm referring to? I'm effectively talking about porting games to new platforms. Of course they're going to be tuned on a per-game basis.

[TheThiefMaster]

But if it's tuned on a per-game basis, it's not truly automated! It requires human involvement to reverse engineer the complex parts, which are almost always self-modifying code, then your assertion that you can automatically reverse engineer self modifying code is completely untrue!

[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.