Here are my notes for x86 code generation for some of the IR primitives. Note that the code generation logic contains optimizations (for example testing equality with 0, moving a register to itself, etc) and also some required tests (in sub_ovf the case where the destination register is the same as the second operand, to avoid clobbering the second operand).
Marc
------------------------------------------------------------------------------- rptr $t_1 = get_ctx;
no-op. register allocator should assign context register to $t_1
------------------------------------------------------------------------------- box $t_1 = load_box $t_2, K;
movq K( %REG($t_2) ), %REG($t_1)
------------------------------------------------------------------------------- i64 $t_1 = and_box_i64 $t_2, K;
if K = 0 then
xorq %REG($t_1), %REG($t_1)
else
if %REG($t_1) != %REG($t_2) then
movq %REG($t_2), %REG($t_1)
endif
andq $K, %REG($t_1)
endif
------------------------------------------------------------------------------- i64 $t_1 = and_box_i64 $t_2, $t_3;
if %REG($t_2) = %REG($t_3) then
if %REG($t_1) != %REG($t_2) then
movq %REG($t_2), %REG($t_1)
endif
elsif %REG($t_1) = %REG($t_2) then
andq %REG($t_3), %REG($t_1)
elseif %REG($t_1) = %REG($t_3) then
andq %REG($t_2), %REG($t_1)
else
movq %REG($t_2), %REG($t_1) andq %REG($t_3), %REG($t_1)
endif
------------------------------------------------------------------------------- i8 $t_1 = eq_i64 $t_2, K;
if K = 0 then
testq %REG($t_2), %REG($t_2)
else
cmpq $K, %REG($t_2)
endif
movb $0, %REG($t_1) cmoveb $1, %REG($t_1)
------------------------------------------------------------------------------- i8 $t_1 = eq_i64 $t_2, $t_3;
cmpq %REG($t_2), %REG($t_3) movb $0, %REG($t_1) cmoveb $1, %REG($t_1)
------------------------------------------------------------------------------- if_i8 $t_1 then lbl1 else lbl2;
testb %REG($t_1), %REG($t_1)
if the if_i8 instruction is immediately followed by lbl1 then
je lbl2
elsif the if_i8 instruction is immediately followed by lbl2 then
jne lbl1
else
jne lbl1 jmp lbl2
endif
------------------------------------------------------------------------------- box $t_1 = add_ovf $t_2, K normal lbl1 overflow lbl2;
if %REG($t_1) != %REG($t_2) then
movq %REG($t_2), %REG($t_1)
endif
if K = 1 then
incq %REG($t_1)
else
addq $K, %REG($t_1)
endif
if the add_ovf instruction is immediately followed by lbl1 then
jo lbl2
elsif the add_ovf instruction is immediately followed by lbl2 then
jno lbl1
else
jno lbl1 jmp lbl2
endif
------------------------------------------------------------------------------- box $t_1 = add_ovf $t_2, $t_3 normal lbl1 overflow lbl2;
if %REG($t_1) != %REG($t_2) then
movq %REG($t_2), %REG($t_1)
endif
addq %REG($t_3), %REG($t_1)
if the add_ovf instruction is immediately followed by lbl1 then
jo lbl2
elsif the add_ovf instruction is immediately followed by lbl2 then
jno lbl1
else
jno lbl1 jmp lbl2
endif
------------------------------------------------------------------------------- box $t_1 = sub_ovf $t_2, K normal lbl1 overflow lbl2;
if %REG($t_1) != %REG($t_2) then
movq %REG($t_2), %REG($t_1)
endif
if K = 1 then
decq %REG($t_1)
else
subq $K, %REG($t_1)
endif
if the sub_ovf instruction is immediately followed by lbl1 then
jo lbl2
elsif the sub_ovf instruction is immediately followed by lbl2 then
jno lbl1
else
jno lbl1 jmp lbl2
endif
------------------------------------------------------------------------------- box $t_1 = sub_ovf $t_2, $t_3 normal lbl1 overflow lbl2;
if %REG($t_2) = %REG($t_3) then
xorq %REG($t_1), %REG($t_1)
else
if %REG($t_1) = %REG($t_3) then
movq %REG($t_3), %TEMP movq %REG($t_2), %REG($t_1) subq %TEMP, %REG($t_1)
// note: %TEMP can be a free register, stack or context slot
else
if %REG($t_1) != %REG($t_2) then
movq %REG($t_2), %REG($t_1)
endif
subq %REG($t_3), %REG($t_1)
endif
if the sub_ovf instruction is immediately followed by lbl1 then
jo lbl2
elsif the sub_ovf instruction is immediately followed by lbl2 then
jno lbl1
else
jno lbl1 jmp lbl2
endif
endif
-------------------------------------------------------------------------------
Afficher les réponses par date
I made some small changes to the IR and renamed the gte, lte and neq instructions as suggested today. If you do a checkout of my latest commit, doing a make run will show the updated mnemonics.
However, if I may, I would have a suggestion for the code generation. Instead of using mnemonics, we should probably "install" code generation functions on the instruction classes. For example:
AddInstr.prototype.genCode = function (...) { ... }
This will avoid relying on mnemonic names, and having redundant code for many variants of the same instruction. The code generation code can then find out the type of the operands by using this.uses[i].type, which refers to an IRType object. It can also find its own expected output type by using this.type.
Also, following todays discussion, I'm pondering whether or not I should have completely distinct HIR/MIR instructions. Right now, the add on boxed values, for example, has the semantic of a call to the add() primitive function (a JavaScript add), whereas the same add instruction on i64 values represents the machine word add instruction. The icast instructions are then needed if we want to directly perform a machine add on boxed values without doing any shifting, to indicate that we want to perform an integer add.
It would be possible to, instead, have HIRAdd and MIRAdd instructions. The HIRAdd instructions would then be translated either into a call or into an MIRAdd which would represent the machine instruction add, depending on the types of the input arguments supplied. This would make it possible to eliminate the cast instructions in this case, and directly perform an MIRAdd on boxed values. It would have the disadvantage that arithmetic, bitwise and comparison instruction classes would be duplicated for the two possible semantics, however.
- Maxime
On 2010-09-22, at 4:24 PM, chevalma@iro.umontreal.ca wrote:
I made some small changes to the IR and renamed the gte, lte and neq instructions as suggested today. If you do a checkout of my latest commit, doing a make run will show the updated mnemonics.
However, if I may, I would have a suggestion for the code generation. Instead of using mnemonics, we should probably "install" code generation functions on the instruction classes. For example:
AddInstr.prototype.genCode = function (...) { ... }
This will avoid relying on mnemonic names, and having redundant code for many variants of the same instruction. The code generation code can then find out the type of the operands by using this.uses[i].type, which refers to an IRType object. It can also find its own expected output type by using this.type.
Also, following todays discussion, I'm pondering whether or not I should have completely distinct HIR/MIR instructions. Right now, the add on boxed values, for example, has the semantic of a call to the add() primitive function (a JavaScript add), whereas the same add instruction on i64 values represents the machine word add instruction. The icast instructions are then needed if we want to directly perform a machine add on boxed values without doing any shifting, to indicate that we want to perform an integer add.
It would be possible to, instead, have HIRAdd and MIRAdd instructions. The HIRAdd instructions would then be translated either into a call or into an MIRAdd which would represent the machine instruction add, depending on the types of the input arguments supplied. This would make it possible to eliminate the cast instructions in this case, and directly perform an MIRAdd on boxed values. It would have the disadvantage that arithmetic, bitwise and comparison instruction classes would be duplicated for the two possible semantics, however.
This sounds like an interesting idea. It is in line with my position about having more abstract operations (which for example abstract the data representation). I'm not sure you have to call them HIRAdd and MIRAdd... it might be appropriate to mix both types of adds at the same IR level. I prefer to have families of related "add" operation that operate on different data representations. The families would differ on the *semantics* of the operation (i.e. what is the relation between the input and output). So
Add 2 JavaScript numbers to yield a JavaScript number:
add_js: (boxed,boxed) -> boxed
Add 2 integers with wraparound (operations that are useful if no overflow is possible, by design or program analysis):
iadd_wrap: (fixnum,fixnum) -> fixnum iadd_wrap: (int32,int32) -> int32 iadd_wrap: (int64,int64) -> int64
Add 2 integers with overflow detection (operations useful to implement add_js):
iadd_ovf: (fixnum,fixnum) -> fixnum normal: lbl1 overflow: lbl2 iadd_ovf: (int32,int32) -> int32 normal: lbl1 overflow: lbl2 iadd_ovf: (int64,int64) -> int64 normal: lbl1 overflow: lbl2
Add 2 floating point numbers (operations useful to implement add_js):
fadd: (flonum,flonum) -> flonum fadd: (float64,float64) -> float64
Marc
I've given this more thought and I think that we can possibly get rid of the HIR instructions completely. At the moment, the AST->IR translation inserts "HIR" instructions, such as add, and these will get replaced by calls to the corresponding primitive later, in a subsequent pass which also does inlining. However, what I could do is issue the calls directly. This would completely eliminate many of the instruction classes.
When an add between boxed values is encountered in the AST translation, this would issue a call to the add primitive function (which could later be inlined). Adds between typed values (such as adds between i64s) would instead be translated directly to the add instruction. Then, in the primitive code, if one wishes to use the machine add to add two boxed values without shifting, one could do iir.add(v1, v2). This instruction would never be replaced, and so the back-end would receive it directly.
Following Marc's suggestion, we could add a second type parameter to the load and store instructions to allow them to perform integer casts. In this way, it becomes possible to load an i32 value directly into an i64 value (load_i32_i64), or to store an i64 value into an i32 in memory. This also would minimize the need for casts in the implementation of primitives.
Note that the icast instruction would still be useful, however, if we ever wish to unbox an integer value, or convert a raw pointer into a boxed value (it's a convenient way of indicating the change in type at the IR level).
- Maxime
On 10-09-22 05:41 PM, Marc Feeley wrote:
On 2010-09-22, at 4:24 PM, chevalma@iro.umontreal.ca wrote:
I made some small changes to the IR and renamed the gte, lte and neq instructions as suggested today. If you do a checkout of my latest commit, doing a make run will show the updated mnemonics.
However, if I may, I would have a suggestion for the code generation. Instead of using mnemonics, we should probably "install" code generation functions on the instruction classes. For example:
AddInstr.prototype.genCode = function (...) { ... }
This will avoid relying on mnemonic names, and having redundant code for many variants of the same instruction. The code generation code can then find out the type of the operands by using this.uses[i].type, which refers to an IRType object. It can also find its own expected output type by using this.type.
Also, following todays discussion, I'm pondering whether or not I should have completely distinct HIR/MIR instructions. Right now, the add on boxed values, for example, has the semantic of a call to the add() primitive function (a JavaScript add), whereas the same add instruction on i64 values represents the machine word add instruction. The icast instructions are then needed if we want to directly perform a machine add on boxed values without doing any shifting, to indicate that we want to perform an integer add.
It would be possible to, instead, have HIRAdd and MIRAdd instructions. The HIRAdd instructions would then be translated either into a call or into an MIRAdd which would represent the machine instruction add, depending on the types of the input arguments supplied. This would make it possible to eliminate the cast instructions in this case, and directly perform an MIRAdd on boxed values. It would have the disadvantage that arithmetic, bitwise and comparison instruction classes would be duplicated for the two possible semantics, however.
This sounds like an interesting idea. It is in line with my position about having more abstract operations (which for example abstract the data representation). I'm not sure you have to call them HIRAdd and MIRAdd... it might be appropriate to mix both types of adds at the same IR level. I prefer to have families of related "add" operation that operate on different data representations. The families would differ on the *semantics* of the operation (i.e. what is the relation between the input and output). So
Add 2 JavaScript numbers to yield a JavaScript number:
add_js: (boxed,boxed) -> boxedAdd 2 integers with wraparound (operations that are useful if no overflow is possible, by design or program analysis):
iadd_wrap: (fixnum,fixnum) -> fixnum iadd_wrap: (int32,int32) -> int32 iadd_wrap: (int64,int64) -> int64Add 2 integers with overflow detection (operations useful to implement add_js):
iadd_ovf: (fixnum,fixnum) -> fixnum normal: lbl1 overflow: lbl2 iadd_ovf: (int32,int32) -> int32 normal: lbl1 overflow: lbl2 iadd_ovf: (int64,int64) -> int64 normal: lbl1 overflow: lbl2Add 2 floating point numbers (operations useful to implement add_js):
fadd: (flonum,flonum) -> flonum fadd: (float64,float64) -> float64Marc
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
An important milestone has been reached!
After putting many many hours of work into the back-end, Erick just showed me that he now has a basic version of fibonacci compiling from the IR. If you're curious to see the code generation source, you can look source/codegen/ir-to-asm-x86.js in the master branch of our repository.
This version currently only supports the minimum number of IR instructions necessary to get fibonacci working. The next steps will be to increase the number of instructions we support so as to make the system more flexible, implement other tests, and prepare for an eventual early "bootstrap". I will be helping Erick with this work.
I should also note that some primitives have been simplified for this version, and that the fibonacci unit test currently does not perform IR lowering (inlining/optimization). If I have time this weekend, I will try enabling IR lowering in this unit test to verify that the back-end supports this, and perhaps try implementing some instructions in there myself.
Have a nice day,
- Maxime
Yay!
Since we now have a "working" compiler, we should think of a performance benchmark suite so that we can easily evaluate the performance of the code generated by the compiler. Of course "fib" is the first benchmark! With this suite we can track the performance as the project progresses. It will give a concrete objective function of the "quality" of the system and help guide us in flattening the tallest mountains...
Marc
On 2010-10-01, at 4:21 PM, Maxime Chevalier-Boisvert wrote:
An important milestone has been reached!
After putting many many hours of work into the back-end, Erick just showed me that he now has a basic version of fibonacci compiling from the IR. If you're curious to see the code generation source, you can look source/codegen/ir-to-asm-x86.js in the master branch of our repository.
This version currently only supports the minimum number of IR instructions necessary to get fibonacci working. The next steps will be to increase the number of instructions we support so as to make the system more flexible, implement other tests, and prepare for an eventual early "bootstrap". I will be helping Erick with this work.
I should also note that some primitives have been simplified for this version, and that the fibonacci unit test currently does not perform IR lowering (inlining/optimization). If I have time this weekend, I will try enabling IR lowering in this unit test to verify that the back-end supports this, and perhaps try implementing some instructions in there myself.
Have a nice day,
- Maxime
Congratulations to everyone on reaching this very important milestone!
Bruno
On 2010-10-01, at 16:21 , Maxime Chevalier-Boisvert wrote:
An important milestone has been reached!
After putting many many hours of work into the back-end, Erick just showed me that he now has a basic version of fibonacci compiling from the IR. If you're curious to see the code generation source, you can look source/codegen/ir-to-asm-x86.js in the master branch of our repository.
This version currently only supports the minimum number of IR instructions necessary to get fibonacci working. The next steps will be to increase the number of instructions we support so as to make the system more flexible, implement other tests, and prepare for an eventual early "bootstrap". I will be helping Erick with this work.
I should also note that some primitives have been simplified for this version, and that the fibonacci unit test currently does not perform IR lowering (inlining/optimization). If I have time this weekend, I will try enabling IR lowering in this unit test to verify that the back-end supports this, and perhaps try implementing some instructions in there myself.
Have a nice day,
- Maxime
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
I'm looking at the code for lt and eq, and I'm not sure what's going on exactly. The lt instruction between two registers is implemented as follows:
tltor.asm.cmp(opnds[1], opnds[0]);
tltor.asm. mov($(immFalse), dest). cmovl(tltor.ctxImmTrue, dest);
And ctxImmTrue is defined as follows:
that.ctxImmTrue = mem(1 * that.REG_BYTE_WIDTH, irToAsm.config.context); that.ctxImmFalse = mem(2 * that.REG_BYTE_WIDTH, irToAsm.config.context);
My understanding is that cmovl can't move an immediate value into a register. I'm not sure what that definition for ctxImmTrue does. Is it allocating some memory location for the constant? Where is the actual value of the constant actually being set?
I'd like to actually change this code to use 1 for true and 0 for false.
- Maxime
Le 10-10-01 23:31 , chevalma@iro.umontreal.ca a écrit :
I'm looking at the code for lt and eq, and I'm not sure what's going on exactly. The lt instruction between two registers is implemented as follows:
tltor.asm.cmp(opnds[1], opnds[0]);
cmp compares the two values and set the flags according to their relative values. Note that testing for opnds[0] < opnds[1] must be written cmp(opnds[1], opnds[0]), i.e. reversed, because we are using the AT&T operand order instead of the Intel one.
tltor.asm. mov($(immFalse), dest). cmovl(tltor.ctxImmTrue, dest);And ctxImmTrue is defined as follows:
that.ctxImmTrue = mem(1 * that.REG_BYTE_WIDTH, irToAsm.config.context); that.ctxImmFalse = mem(2 * that.REG_BYTE_WIDTH, irToAsm.config.context);My understanding is that cmovl can't move an immediate value into a register. I'm not sure what that definition for ctxImmTrue does. Is it allocating some memory location for the constant? Where is the actual value of the constant actually being set?
Contrary to what Marc wrote, cmove effectively cannot move an immediate value in a register, only a register or a memory value. Therefore I chose to put a true and a false value on the context object, respectively in the 2nd and 3rd slot, to have them handy.
mem(offset, register) accesses memory at the address contained in register + offset.
ctxImmTrue and ctxImmFalse and memory objects stored on translator to be used as operands for cmov.
The above code copies the false value in the destination register and overwrite this value with the true value stored in the context, only if opnds[0] < opnds[1].
The constant value is being set in dump_context_object(), which reserves space in the code stream for the context object and preassign some slots, for true and false values.
I'd like to actually change this code to use 1 for true and 0 for false.
You'll need to change the true and false value stored in the context object (see dump_context_object) and the immTrue and immFalse values used in the code. The only gotcha is that you should use a javascript number when directly generating a byte in the code stream using genXX:
tltor.asm.gen32(0); // passing the false value
but you should use an immediate value object when passing a constant as an operand for an instruction:
tltor.asm.mov($(0), dest); // using an immediate false value
Erick
- Maxime
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
The constant value is being set in dump_context_object(), which reserves space in the code stream for the context object and preassign some slots, for true and false values.
Reading memory every time you need the true/false values sounds rather ineffective. We might be better off using a label and a jump. Does your system resolve name collisions for labels?
- Maxime
I wrote this bit of code instead:
var trueLabel = tltor.asm.labelObj();
tltor.asm. mov($(1), dest). jl(trueLabel). mov($(0), dest). label(trueLabel)
- Maxime
The constant value is being set in dump_context_object(), which reserves space in the code stream for the context object and preassign some slots, for true and false values.
Reading memory every time you need the true/false values sounds rather ineffective. We might be better off using a label and a jump. Does your system resolve name collisions for labels?
- Maxime
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
Ok. I added some tentative code for ne, icast, and construct (same as call), which I committed on the master branch. The fib test seems to run fine as-is, but if I try to enable IR lowering (see commented lowerIRFunc call in programs/tests/fib), I get incorrect return value. I also seem to get some compilation errors when I try to modify the boxToBool primitive (needed by the code after lowering).
- Maxime
I wrote this bit of code instead:
var trueLabel = tltor.asm.labelObj(); tltor.asm. mov($(1), dest). jl(trueLabel). mov($(0), dest). label(trueLabel)
- Maxime
The constant value is being set in dump_context_object(), which reserves space in the code stream for the context object and preassign some slots, for true and false values.
Reading memory every time you need the true/false values sounds rather ineffective. We might be better off using a label and a jump. Does your system resolve name collisions for labels?
- Maxime
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
On 2010-10-02, at 12:06 PM, chevalma@iro.umontreal.ca wrote:
I wrote this bit of code instead:
var trueLabel = tltor.asm.labelObj();
tltor.asm. mov($(1), dest). jl(trueLabel). mov($(0), dest). label(trueLabel)
Jumps are to be avoided. They cause branch prediction problems, and in this case they take more code memory. I agree that using a memory load is also to be avoided in general. So the conditional move with a register is a better solution. Note that we know the content of the context register and we also know it is non-zero. So we can use it as a non-false value, and 0 as the false value. The code would then be:
mov $0, dest_reg cmovl ctx_reg, dest_reg
and the conditional jump would test for non-zero:
test dest_reg, dest_reg jne true_branch
Marc
-
Bruno Dufour -
chevalma＠iro.umontreal.ca -
Erick Lavoie -
Marc Feeley -
Maxime Chevalier-Boisvert