<div dir="ltr">Hey Eliot,<div><br></div><div>I was looking at other code, such as literalVariable access, and I realized it has the same issue as temporaries: a register is used to temporarily store the association, and at the end the association is still in the register but if we have another access to the literal variable it will not reuse it and move again the association to a register.</div><div><br></div><div>I was thinking that we could have a more generic solution.</div><div><br></div><div>The JIT, while compiling, could have a list (of a size which is the number of registers) where it knows a mapping value - register. At the end of each method that access temps, literal variable and co we could mark in the list several values (such as temp, association or the receiver) to be in a given register. When fetching a register for an association or a temp with allocateAnyReg or whatsoever, we could first look if the value is already in a register based on the list, and if so, reuse the register directly, else allocate a new one and put it on the list. When the register allocation needs to find a new register, it would fetch first a register that does not hold a value, if there are none, free a random one which is used in the list but not in the simulated stack, and lastly, if there's still none, spill a register. When allocating a register for another purpose than because the value held is reused, we remove the value - reg entry from the list. Lastly, for interrupt points like sends, we free the list completely as we don't know which values will remain.</div><div><br></div><div>I believe the list could have different values to remember: temporaries, associations, receiver, tempVectors. Maybe more like constants that are used several times by moving them to registers.</div><div><br></div><div>I am not sure I understand what you want to do with the "<span style="font-size:12.8000001907349px">has been read" flag. Maybe I should discuss it with you directly so you can explain me.</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">I think on the short term we should also add mappings for extra registers (unused regs on ARM and x86_64) and change the register allocation so it tries first to allocate those.</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">I think I found the bug in the SistaCogit, it was crashing randomly in different branches (not only #==), and I think the bug is that now that the counters use a random register (based on register allocation) instead of using SendNumArgsReg, and that the mustBeBoolean trampoline, also used for counter tripping, does not save the counterReg whereas it is reused after the trampoline, in the case where counter reg is callerSaved it crashes (and I believe that </span><span style="font-size:12.8000001907349px">SendNumArgsReg was calleeSaved so it worked)</span><span style="font-size:12.8000001907349px">. </span><span style="font-size:12.8000001907349px">I think I should change register allocation to try to allocate a calleeSaved register first so we don't have to do anything across trampolines if possible... </span></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-04-25 18:09 GMT+02:00 Eliot Miranda <span dir="ltr"><<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br><div dir="auto"><div>Hi Clément, Hi All,</div><div><br>On Apr 23, 2015, at 9:08 AM, Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><div><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Apr 23, 2015 at 3:46 AM, Clément Bera <span dir="ltr"><<a href="mailto:bera.clement@gmail.com" target="_blank">bera.clement@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">2015-04-23 1:20 GMT+02:00 Eliot Miranda <span dir="ltr"><<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"> <br><div dir="ltr">Hi Clément,<div><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 22, 2015 at 2:07 AM, Clément Bera <span dir="ltr"><<a href="mailto:bera.clement@gmail.com" target="_blank">bera.clement@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"> <br><div dir="ltr">Eliot here's a good example to stress the register allocation:<div><br></div><div><div>Integer>>#regStress</div><div><span style="white-space:pre-wrap"> </span>| t t2 |</div><div><span style="white-space:pre-wrap"> </span>t := self yourself.</div><div><span style="white-space:pre-wrap"> </span>t2 := self + 1.</div><div><span style="white-space:pre-wrap"> </span>^ { t == t2 . t == t2 . t == t2 . t == t2 . t == t2 . t == t2 . t == t2 }</div></div><div><br></div><div>I think the resulting machine code method is beautiful, it needs to spill only when it runs out of registers :-). Of course it makes sense mainly when you use inlined bytecodes instead of only #==.</div><div><br></div><div>Some extra register moves are done because the JIT does remember if a temporary value is currently in a register (It moves each time the temp t to the same register whereas the register value is not changed). Maybe we should add a feature that remembers if temporaries are currently in a register, and if so, when doing push temp, only push the register directly in the simStack, and in case of temporary store or stack flush the register associated with a temp is not valid anymore somehow...<br></div></div></blockquote><div><br></div><div>Here's a sketch of something that looks to me like it would work.</div><div><br></div><div>A CogSimStackEntry for a temp var is of type SSBaseOffset. Its register field is used to hold the frame pointer. We want to mark it as having its value in a register, so it needs a new field, lets call it allocatedRegOrNil. At start of compilation all SSBaseOffset entries have allocatedRegOrNil nil.</div><div><br></div><div>Whenever popToReg: finds it is popping an SSBaseOffset entry it sets that entry's allocatedRegOrNil to the register.</div><div>Whenever a register is spilled (in ssFlushTo:) the sim stack is also scanned looking for all SSBaseOffset entries whose allocatedRegOrNil equals the register, and simply sets allocatedRegOrNil back to nil.</div><div><br></div><div>On merge, with the current representation we merely set all allocatedRegOrNil fields back to nil. But with the more sophisticated stack copy merge we can preserve allocation for entries whose registers match.</div><div><br></div><div>There are perhaps tricky details in merge (the same register used for different temporaries in different branches, etc) but otherwise it is very simple, no?</div></div></div></div></div></blockquote><div><br></div><div>Yeah something like that would be nice. There are details such as liveRegisters should include those registers. Maybe this logic could be somehow merged with the one of ReceiverResultReg which has currently its own live status and may not need so.</div></div></div></div></blockquote><div><br></div><div>Yes that's a good idea. One would just do popToRequiredReg: ResultReceiverReg on the self stack entry and if ResultReceiverReg currently held the receiver it would be a no-op. Nice.</div></div></div></div></div></blockquote><div><br></div>In thinking about this some more a key issue is that the linear scan register allocator we have is greedy. That is, it allocates registers when parameters are first mentioned, an outside-in order, instead of when parameters are used, an inside-out order. I was thinking about the case if nested loops where one wants to allocate registers to the innermost variables not the outermost, since the innermost change more frequently and hence one ends up with fewer memory writes if the innermost variables are allocated in registers.<div><br></div><div>So if the allocator as described above was to allocate temps in registers we might end up with a situation where we allocated a register for an "outer" temp (a less <span>frequently</span> changing temp) and later reallocated it for an "inner" temp. This is not a problem except if we unnecessarily load <span>the register </span>and write it back unnecessarily to the temp.</div><div><br></div><div>I think this is easy to avoid by adding a "has been read" flag to the temp. Unless a stack entry for the temp-with-allocated-register has actually been popped into a register (& hence potentially had its value changed) there's no need to write it back if we reallocate the register. I<span>f we reallocate the register and its temp hasn't been read</span> merely scan the simstack and delete the allocated register from all occurrences of the temp, and when it is accessed it'll be accessed as a normal temp.</div><div><br></div><div>So a <span>"has been read" flag would allow the allocator to reallocate for innermost temps without having to pay for mistaken greedy allocations earlier-in.</span></div><div><span><br></span></div><div><span>At least that's what I thought yesterday in the car while driving. It might be completely half-baked but I wanted to write down the idea just in case it held water.</span></div><div><div><br></div><div><br><blockquote type="cite"><div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>Btw I changed <span style="font-size:12.8000001907349px">#genStorePop: popBoolean LiteralVariable: litVarIndex so it uses register allocation instead of ReceiverResultReg and ClassReg. There was a flag saying that it could be used in frameless methods if register allocation was used. However I wonder, can you have a ceStoreCheck in a frameless method ? I could work around the need for ReceiverResultReg in the trampoline by adding extra register moves but I am not sure a trampoline can work fine in frameless method.</span></div></div></div></div></blockquote><div><br></div><div>Yes, trampolines can work in any state. They're orthogonal to framelessness. Trampolines call into the C run-time. To do so they must switch stack, saving the hardware stack pointers into stackPointer and framePointer. loading the hardware stack pointers with the C stack, making the call, and on return, switching back to the Smalltalk stack. But it doesn't matter what state Smalltalk is in; the stack pointers referring to the caller method or the callee method makes no difference to the trampoline, only to the code the trampoline calls. With something like the store check, the stack is unexamined; all that happens is that the argument gets added to the remembered table.</div><div><br></div><div>Framelessness occurs in three different forms:</div><div><br></div><div>- One is a method that doesn't contain any sends other than the special selectors #== and #class, doesn't access temporaries beyond the arguments. So for example Interval>>setFrom:to:by:, which contains three inst var assignments and three store checks. </div><div><span><br></span></div><div><span>- Another is a frameless block. This is the same as a frameless method except that block activation implies that the receiver and register arguments will have been pushed, so the stack layout is a little different.</span></div><div><span><br></span></div><div><span>- the final case is a method with a primitive. The code up until a primitive fails is frameless. If a primitive is implemented in machine code then the stack and register arguments are undisturbed; the primitive will access its operands from the registers if that's where they are. If a primitive is implemented in C (an interpreter primitive), or the machine code primitive calls the interpreter primitive when it fails (which allows the machine code to handle the simple common cases, falling back on slower more comprehensive C code), then, like a frameless block, receiver and arguments are pushed on the stack, because interpreter primitives can only get their operands from the stack via stackPointer.</span></div><div><span><br></span></div><div><span>The above implies that the ceStoreCheck trampoline may be called from any of the above frameless forms, as well as from a method with a full frame.</span></div><div><span><br></span></div><div><span>So if you've broken frameless inst var store pop, please fix it ;-). But I doubt you have because the code is explicit:</span></div><div><span><br></span></div><div><span><div>genStorePop: popBoolean ReceiverVariable: slotIndex</div><div><span style="white-space:pre-wrap"> </span><inline: false></div><div><span style="white-space:pre-wrap"> </span>| topReg valueReg constVal |</div><div><span style="white-space:pre-wrap"> </span>needsFrame ifFalse:</div><div><span style="white-space:pre-wrap"> </span>[^self genFramelessStorePop: popBoolean ReceiverVariable: slotIndex].</div><div><span style="white-space:pre-wrap"> </span>self ssFlushUpThroughReceiverVariable: slotIndex.</div><div><span style="white-space:pre-wrap"> </span>"Avoid store check for immediate values"</div><div>...</div><div><br></div></span>so the body of genStorePop:ReceiverVariable: does not have to deal with framelessness. Remember that in a frameless method (and IIRC in a frameless block) ReceiverResultReg /always/ contains self.<span><div><br></div><div>The limitation of the trampolines is that they expect specific register arguments; each one expects its own particular sequence of register arguments that the code generator must use to call them. But that doesn't mean you couldn't for example implement ceStoreCheckReceiverRegTrampoline, ceStoreCheckClassRegTrampoline etc, etc, provided you can handle the complexity.</div><div><br></div><div><br></div></span></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div></div><div>2015-04-22 10:08 GMT+02:00 <span dir="ltr"><<a href="mailto:commits@source.squeak.org" target="_blank">commits@source.squeak.org</a>></span>:<br></div></div><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><br>
Eliot Miranda uploaded a new version of VMMaker to project VM Maker:<br>
<a href="http://source.squeak.org/VMMaker/VMMaker.oscog-cb.1236.mcz" target="_blank">http://source.squeak.org/VMMaker/VMMaker.oscog-cb.1236.mcz</a><br>
<br>
==================== Summary ====================<br>
<br>
Name: VMMaker.oscog-cb.1236<br>
Author: cb<br>
Time: 22 April 2015, 10:07:41.028 am<br>
UUID: cf4af270-9dfa-4f2a-b84c-0cdb3c5f4913<br>
Ancestors: VMMaker.oscog-tpr.1235<br>
<br>
changed the names of register allocation methods for more explict names, for instance, allocateOneReg -> allocateRegForStackTop<br>
<br>
Fixed a bug where not the best register was allocated in #== (was allocating a reg based on stackTop value instead of ssValue: 1)<br>
<br>
=============== Diff against VMMaker.oscog-tpr.1235 ===============<br>
<br>
Item was changed:<br> </blockquote></div></div></blockquote></div></div></div></div></blockquote></div></div></div></blockquote><div> </div><div>deletia</div></div>-- <br><div>best,<div>Eliot</div></div>
</div></div>
</div></blockquote></div></div></div><br></blockquote></div><br></div>