Can machine code be translated to a different architecture?

So this is kind of related to a question about running a Windows server on ARM. So the premise of my question is, can machine code be translated from one architecture to another in order to execute a binary on an architecture different than the one it was compiled to run on.

QEMU and other emulators can translate the instructions on the fly, and therefore run an executable on a computer it wasn't compiled for. Why not do this translation ahead of time, instead of on the fly in order to speed up the process? From my somewhat limited knowledge of assembly, most of the instructions like MOV, ADD and others should be portable across architectures.

Anything that's doesn't have a direct mapping could be mapped to some other set of instructions, since all machines are Turing Complete. Would doing this be too complicated? Would it not work at all for some reason I'm unfamiliar with? Would it work, but yield no better results than using an emulator?

Solution 1:

The short answer: You can't translate a compiled, linked executable. While technically possible, it's highly improbable to accomplish (see below). However, if you have the assembly source file (containing the instructions and labels), it is very possible to do (although if you somehow obtain the assembly source, unless the program is written in assembly, you should have the original program source code as well, so you'd be better off compiling it for the different architecture to begin with).

The long answer:

QEMU and other emulators can translate the instructions on the fly, and therefore run an executable on a computer it wasn't compiled for. Why not do this translation ahead of time, instead of on the fly in order to speed up the process?

I know it might seem easy in principle, but in practice, it's nearly impossible for a few main reasons. To start, different instruction sets use largely different addressing modes, different opcode structures, different word sizes, and some don't even have the instructions you need.

Let's say you needed to replace instruction XYZ with two more instructions, ABC and DEF. Now you've effectively shifted all of the relative/offset addresses in the entire program from that point on, so you would need to analyze and go through the entire program and update the offsets (both before and after the change). Now, let's say one of the offsets changes significantly - now you need to change addressing modes, which might change the size of the address. This will again force you to re-scan the entire file and re-compute all of the addresses, and so on and so fourth.

When you write assembly programs, you might use labels, but the CPU doesn't - when the file is assembled, all of the labels are calculated to be relative, absolute, or offset locations. You can see why this quickly becomes a non-trivial task, and next to impossible. Replacing a single instruction might require you to pass through the entire program hundreds times before moving on.

From my somewhat limited knowledge of assembly, most of the instructions like MOV, ADD and others should be portable across architectures.

Yes, but look at the issues I outlined above. What about the machine's word size? Address length? Does it even have the same addressing modes? Again, you can't just "find and replace" instructions. Every segment of a program has a specifically defined address. Jumps to other labels are replaced with literal or offset memory addresses when a program is assembled.

Anything that's doesn't have a direct mapping could be mapped to some other set of instructions, since all machines are Turing Complete. Would doing this be too complicated? Would it not work at all for some reason I'm unfamiliar with? Would it work, but yield no better results than using an emulator?

You're 100% correct that it is both possible, and would be a lot faster. However, writing a program to accomplish this is incredibly difficult and highly improbable, if not for anything except the issues I outlined above.

If you had the actual assembly source code, it would be trivial to translate the machine code to another instruction set architecture. Machine code itself, however, is assembled, so without the assembly source (which contains various labels used to compute memory addresses), it becomes incredibly difficult. Again, changing a single instruction might change memory offsets in the entire program, and require hundreds of passes to re-compute the addresses.

Doing this for a program with a few thousand instructions would require tens if not hundreds of thousands of passes. For relatively small programs, this may be possible, but remember that the number of passes will exponentially increase with the number of machine instructions in the program. For any program of a decent enough size, it's near impossible.

Solution 2:

Yes, what you suggest can be and has been done. It's not too common, and I don't know of any current systems that use the technique, but it's definitely well within the realm of technical feasibility.

It used to be done a lot to enable the porting of code from one system to another, before anyone had achieved the even crude "portability" we have now. It required complex analysis of the "source" and could be stymied by code modification and other oddball practices, but it was still done.

More recently, systems like the IBM System/38 -- iSeries -- System i have taken advantage of the portability of intermediate code (similar to Java bytecodes) stored with compiled programs to enable portability between incompatible instruction set architectures.