OSDev.org

The CIL bytecode (aka MSIL) used in .NET assemblies is actually really nicely designed. It is sufficiently high-level as to allow the Just-In-Time compiler the most possible freedom (e.g. to optimize), while at the same time smaller than most instructions in real machine code. Contrary to what tjmonk15 says, there is no one-to-one correspondence between CIL instructions and machine code. However, naturally, the basic arithmetic, comparison, jump and bitwise instructions (add, cmp, br, xor) are present in allmost all instruction sets, including CIL.

CIL is a stack-based language: most operands are put on the (imaginary) evaluation stack. This saves a lot of space in the instruction encoding, since those operands are implicit. For example, a method might have the following CIL content:
This method has a bytecode content of just 4 bytes. The first two instructions push a value on the evaluation stack, the third pops two values and pushes a new one, and the last one pops a value and returns it from the method. It is not very hard to convert stack-based bytecode to something that uses registers.

In CIL an opcode consists of one or two bytes. If the first byte is one of the reserved values, then a second byte follows. This is mostly used to encode a short and a long variant of the same instruction. There is also space for one or more explicit operands. For example:
If you want to know more about CIL bytecode, I suggest you read ECMA 335. It is a very readable specification. The instructions are in section III.

Afaik, it's relatively hard to convert from stack based (CIL, Java) bytecode to 3-address machine code (x86, arm); that's one of the reasons why Dis is 3-address bytecode.

dozniak wrote:Afaik, it's relatively hard to convert from stack based (CIL, Java) bytecode to 3-address machine code (x86, arm); that's one of the reasons why Dis is 3-address bytecode.

Nonsense. Both stack and register machines are translated to SSA using similar mechanisms.

If I was using LLVM, I'd be very tempted to just alloc one real stack location per stack slot/virtual register and then use LLVM's mem2reg pass to lift the code into SSA form where possible.

To convert stack-based bytecode to register-based bytecode, you do the following:

1. Make an evaluation stack-like class that can push, pop and can return a virtual register associated with each stack slot. E.g. %slot0, %slot1, ...
2. Split the bytecode of a method into basic blocks (blocks of code for which control flow only ever enters at the first instruction and leaves at the last).
3. Get the content of the evaluation stack from one of the preceding blocks, or an empty stack if it is the first basic block.
4. For each instruction:
   1. For each incoming stack operand: get the corresponding register by asking the stack-like class for the register associated with the top-most element, and then pop that from the stack.
   2. For each outgoing stack operand: push it on the stack-like class.

Short example:

1. ldc.i4 10 pushes an integer on the stack. The top-most stack slot now has register %slot0.
2. ldc.i4 5 pushes another integer on the stack. The top-most stack slot now has register %slot1.
3. ceq would take the top two values from the stack. So it takes a look: %slot1 is the top-most register. Pop it. %slot0 is now the top-most register. Pop it. Push an integer. The top-most stack slot is %slot0.
4. ret looks at the stack: %slot0 is the top-most register. Pop it.
5. Done!

So the result as register-based pseudo-bytecode (op dest <- src1, src2) would be: Now all that's left is assigning the unlimited virtual registers to the limited pool of physical machine registers in the most efficient manner possible.

Nice! Thanks guys, learned something new today!