I added support for the >>> operator to the constant propagation and ran a "make bootstrap". The good news is that all the code passed through the front end and all CFG validation tests. It got to the actual code generation stage and then we encountered a bug in the back-end.
If we're optimistic, all that's left is fixing bugs in the back-end and we should be able to say the bootstrap is complete. Realistically, there will probably be other bugs in other parts of the system, but those will only show up when we try to run our own code.
I will probably spend the rest of the afternoon adding more unit tests to try and make sure we really have our bases covered. Perhaps include some of our own code in a unit test, or try coding a simple parser, to have something more reflective of the code we actually run.
I should also add the /hir, /lir, /asm shell commands because they will probably be very useful debugging tools in the next few days.
- Maxime
Afficher les réponses par date
On 2011-02-18, at 1:32 PM, chevalma@iro.umontreal.ca wrote:
I added support for the >>> operator to the constant propagation and ran a "make bootstrap". The good news is that all the code passed through the front end and all CFG validation tests. It got to the actual code generation stage and then we encountered a bug in the back-end.
If we're optimistic, all that's left is fixing bugs in the back-end and we should be able to say the bootstrap is complete. Realistically, there will probably be other bugs in other parts of the system, but those will only show up when we try to run our own code.
I will probably spend the rest of the afternoon adding more unit tests to try and make sure we really have our bases covered. Perhaps include some of our own code in a unit test, or try coding a simple parser, to have something more reflective of the code we actually run.
That's really good news!
I should also add the /hir, /lir, /asm shell commands because they will probably be very useful debugging tools in the next few days.
Those commands are very handy for simple tests of the code generation. I was quite surprised when I tried to compile 0 (the constant expression 0):
t> /lir 0 box function () [] { entry: ret undefined; }
t> /asm 0 000000 fn: 000000 8b 39 movl (%ecx),%edi 000002 83 ef 02 subl $2,%edi 000005 85 ff testl %edi,%edi 000007 74 3f je L6483 000009 83 ff 00 cmpl $0,%edi 00000c 7f 15 jg L6484 00000e bd 19 00 00 00 movl $25,%ebp 000013 8b 39 movl (%ecx),%edi 000015 83 ff 00 cmpl $0,%edi 000018 0f 4e d5 cmovlel %ebp,%edx 00001b 83 ff 01 cmpl $1,%edi 00001e 0f 4e dd cmovlel %ebp,%ebx 000021 eb 25 jmp L6483 000023 L6484: 000023 89 41 08 movl %eax,8(%ecx) 000026 89 e5 movl %esp,%ebp 000028 83 ef 02 subl $2,%edi 00002b 83 ff 00 cmpl $0,%edi 00002e 7e 18 jle L6483 000030 L6486: 000030 39 e5 cmpl %esp,%ebp 000032 7c 0c jl L6485 000034 8b 45 00 movl (%ebp),%eax 000037 89 44 bd 00 movl %eax,(%ebp + %edi*4) 00003b 83 ed 04 subl $4,%ebp 00003e eb f0 jmp L6486 000040 L6485: 000040 8b 41 08 movl 8(%ecx),%eax 000043 c1 e7 02 sall $2,%edi 000046 01 fc addl %edi,%esp 000048 L6483: 000048 entry: 000048 b8 19 00 00 00 movl $25,%eax 00004d c2 00 00 ret $0 000050
Questions and comments:
1) What is the code before the "entry" label doing? It seems to be testing that nbargs=2, and if nbargs<2 it fills in %edx and %ebx with the undefined value... but the function (as seen in the LIR) expects 0 arguments. So if nbargs>0 there is a simple adjustment to do to the stack (pop ra; sp+=nbargs*4; push ra). Note that the implicit parameter "this" does not count as an argument (it is always passed in the calling convention).
2) The "ret $0" (3 bytes) is equivalent to "ret" (1 byte).
3) The code will be more compact, and perhaps just as fast, if the undefined value is stored in the context. That way the "movl $25,%eax" (5 bytes) can be replaced with "movl undef_offs(%ecx),%eax" (3 bytes). This trick can be used for other frequent constants (such as "true", "false", "null", 0, 1, 2). But there are better suggestions below...
4) Another trick which can reduce the code size and possibly improve speed is to encode the special values ("true", "false", "null", "undefined", ...) using only the 8 low bits of a word (and with the two lowest bits equal to 01). The more significant bits, above the low 8 bits, can be any bit pattern because they ares never used in a test. So instead of "movl $25,%eax" (5 bytes) it would be sufficient to do "movb $25,%al" (2 bytes).
5) Also, if we align the context to a multiple of 2^16, we can use the lower 16 bits to store any constant values (because when we access the slots of the context the offset we use can cancel out the constant we know is in the lower 16 bits). If %ecx contains the context pointer, and we decide that %cl=0 (for simplifying the argument count manipulation), we could decide to store a frequently used special value in %ch, for example the undefined value, so that %ch=25. Comparisons to this value can be done in a 2 byte instruction (i.e. "cmpb %ch,%dl"), instead of 3 bytes (i.e. "cmpb $25,%dl"), note that for the special case of %al there is no gain (i.e. "cmpb $25,%al" is encoded in 2 bytes).
6) Note also that the instruction "movl $N,%reg" (5 bytes), where 0<=N<=255 can be replaced by the two instructions "xorl %reg,%reg ; movb $N,reg_l" (4 bytes), and when N=1 or -1, a inc/dec can be used after the xorl (so it might be efficient to encode the most frequent special value with 1 or -1). Don't think that it will be slower to execute 2 instructions rather than 1... a superscalar processor will probably merge these instructions. It is only by testing that we can tell which is faster.
7) Perhaps we should have a compilation flag for optimization which optimizes for space or time...
If these tricks are used, the main code of the function, i.e. "movl $25,%eax ; ret $0" (8 bytes), is turned into 3 bytes, i.e. "movb $25,%al ; ret", which is a saving of 62.5%!
Marc
- What is the code before the "entry" label doing? It seems to be
testing that nbargs=2, and if nbargs<2 it fills in %edx and %ebx with the undefined value... but the function (as seen in the LIR) expects 0 arguments. So if nbargs>0 there is a simple adjustment to do to the stack (pop ra; sp+=nbargs*4; push ra). Note that the implicit parameter "this" does not count as an argument (it is always passed in the calling convention).
- The "ret $0" (3 bytes) is equivalent to "ret" (1 byte).
I guess you should bring this up at the meeting Wednesday. The return issue should be trivial to implement. The arguments one I don't know.
- The code will be more compact, and perhaps just as fast, if the
undefined value is stored in the context. That way the "movl $25,%eax" (5 bytes) can be replaced with "movl undef_offs(%ecx),%eax" (3 bytes). This trick can be used for other frequent constants (such as "true", "false", "null", 0, 1, 2). But there are better suggestions below...
Isn't moving data from the context to a register loading something from memory? How can that be faster than loading it directly from the (hopefully precached) code stream?
- Another trick which can reduce the code size and possibly improve speed
is to encode the special values ("true", "false", "null", "undefined", ...) using only the 8 low bits of a word (and with the two lowest bits equal to 01). The more significant bits, above the low 8 bits, can be any bit pattern because they ares never used in a test. So instead of "movl $25,%eax" (5 bytes) it would be sufficient to do "movb $25,%al" (2 bytes).
That should be feasible. As I keep saying, we need to keep a big TODO list of all the improvements we want to make after the bootstrap, and some kind of order of priority.
I have a list of improvements I want to make to the IR/front-end myself.
- Maxime
On 2011-02-19, at 12:03 PM, chevalma@iro.umontreal.ca wrote:
- What is the code before the "entry" label doing? It seems to be
testing that nbargs=2, and if nbargs<2 it fills in %edx and %ebx with the undefined value... but the function (as seen in the LIR) expects 0 arguments. So if nbargs>0 there is a simple adjustment to do to the stack (pop ra; sp+=nbargs*4; push ra). Note that the implicit parameter "this" does not count as an argument (it is always passed in the calling convention).
- The "ret $0" (3 bytes) is equivalent to "ret" (1 byte).
I guess you should bring this up at the meeting Wednesday. The return issue should be trivial to implement. The arguments one I don't know.
- The code will be more compact, and perhaps just as fast, if the
undefined value is stored in the context. That way the "movl $25,%eax" (5 bytes) can be replaced with "movl undef_offs(%ecx),%eax" (3 bytes). This trick can be used for other frequent constants (such as "true", "false", "null", 0, 1, 2). But there are better suggestions below...
Isn't moving data from the context to a register loading something from memory? How can that be faster than loading it directly from the (hopefully precached) code stream?
The slots in the context that are accessed frequently should be in the L1 cache (and the probability of this being true will increase if we put all of the frequently accessed ones close together so they fall into the same cache line). The allocation pointer (if not in a register), the argument count (if not in a register), the stack limit pointer, the global object, are probably the most frequently accessed and should be close together. So wether the value is taken from the cached code stream, or the cached context will not matter much for the actual data transfer. However, if the code is more compact it will increase the likelihood that all of the hot parts of the code will be in a cache close to the CPU. But when I say it is "perhaps just as fast", I concede that it will have to be tested to see how the different factors impact the performance.
- Another trick which can reduce the code size and possibly improve speed
is to encode the special values ("true", "false", "null", "undefined", ...) using only the 8 low bits of a word (and with the two lowest bits equal to 01). The more significant bits, above the low 8 bits, can be any bit pattern because they ares never used in a test. So instead of "movl $25,%eax" (5 bytes) it would be sufficient to do "movb $25,%al" (2 bytes).
That should be feasible. As I keep saying, we need to keep a big TODO list of all the improvements we want to make after the bootstrap, and some kind of order of priority.
Well... "after the bootstrap" is going to be in a few days right? ;-)
Marc
Well... "after the bootstrap" is going to be in a few days right? ;-)
Hopefully, but Erick and I stumbled upon a bug in the register allocation that might be hard to fix. He seems to believe that the linear scan algorithm can't handle a particular CFG. We will examine it more in detail Monday.
- Maxime
-
chevalma＠iro.umontreal.ca -
Marc Feeley