On 2010-07-15, at 10:47 PM, Maxime Chevalier-Boisvert wrote:

I've started a refactoring of the IR instructions code. I implemented a function called GenericInstrMaker, which constructs a closure to be used as an instruction constructor. This is meant to be a quick way to create new "classes" for instructions that follow a generic pattern (eg: all arithmetic, comparison, bitwise, logical operators).

Erick and I have also been discussing introducing some x86 instruction classes into the IR for code generation and register allocation purposes, which made me think it would be nice to have an "X86Instr" class in our instruction class hierarchy. However, this somewhat breaks my current model, because, some x86 instructions will be branch instructions, but these can't have both X86Instr and BranchInstr as their prototype.

Hence, I've been thinking that perhaps, instead of having a BrancInstr class, all instructions should have an "isBranch" boolean flag. I was also thinking that instructions could have other flags, such as a "write" flag, and a "read" flag, to indicate that some instructions have memory access side effects. These side effect flags would be useful for writing an IR optimizer, later on.

I'm not clear on what you are proposing. Are you saying that the IR will contain X86 instructions and "normal" IR instructions at the same time? I'm assuming that in what follows.

At the last meeting I expressed my doubts that having real machine instructions in the IR was a good idea. Here are some more thoughts that lead me to think it is a bad idea:

1) The IR is meant to be a generic representation of the code, that expresses the meaning of the program and that makes program analysis and transformation easy. Obviously the X86 instructions are as low level as possible and specific to the X86 architecture (set of instructions, 2 operand instructions, etc). Mixing these levels is not "clean". It mixes two semantic levels where concepts from one level don't exist or are awkward at the other level. I fear the IR code will become tainted with X86-specific concerns, and that it will be extremely tedious to port the system to a different processor. If there is one important concept in computer-science and programming languages in particular, it is that the complexity of large software systems can be tackled by layering systems (in the case of programming languages, building a virtual machine abstraction). Our IR should be this virtual machine.

2) It is naïve to think that the best X86 instruction can be selected when other parts of the IR aren't yet converted to X86. For example, an integer multiplication can be done with at least 4 different instructions (add, asl, mul, lea). The best one to use will depend on which operands are to be multiplied (memory location, which register class, constant, etc). But the nature of an operand will depend on the instruction which generates its value. For example, consider the 2 IR instructions

(1) t1 := x + y (2) t2 := t1 + 1

The best x86 code to generate for the second IR instruction will depend on which CPU resources t1 and t2 map to. If t1 and t2 are mapped to the same register (because t1 becomes dead after IR instruction 2), say %eax, then the best x86 code will be

inc %eax

If on the other hand t1 and t2 map to 2 different registers, say %eax and %ebx, then the best x86 code will be

lea 1(%ebx),%eax

If on the other hand t1 is in memory, say stack slot 8(%ebp), and t2 is in a registers, say %eax, then the best x86 code will be

mov 8(%ebp),%eax inc %eax

I think it is better to maintain a high-level of abstraction for the IR instructions, and to have an independent pass which translates the IR instructions to x86 code. The x86 specific knowledge can be in this "x86 back-end". As we discussed in the last meeting, to keep things simple, we should use an on-the-fly register allocator to attribute registers/memory locations to the IR temporaries. On-the-fly register allocation requires that the IR instructions are translated to x86 in sequence.

What I recall from early discussions is that Maxime expects the compiler to iteratively modify/refine the IR representation of the program based on newly discovered properties of the program. The hope is that the parts of the IR that have been translated to x86 code do not have to be translated again. But imagine the program above where the second IR instruction has been translated to an "lea" x86 instruction, and now the monitoring system discovers that x and y are always equal to 0 so that t1 is also 0, then the best thing is to translate the second IR instruction into a "mov $1,...". In other words, the non-translated IR instruction needs to be available at all times.

So I fail to see what is gained by mixing the two levels of abstraction (IR and x86).

Marc