<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif;" dir="ltr">
<div id="divtagdefaultwrapper" dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<p><span style="font-size:12pt">Hi Levente, hi Eliot,</span><br>
</p>
<p><span style="font-size:12pt"><br>
</span></p>
<p><span style="font-size:12pt">> </span><span style="font-size:12pt">What if the value of x is nil?</span><span style="font-size:12pt"></span></p>
<div>> [...]</div>
<div>> What if there are multiple branches with the same "key"?</div>
<div>> What if some "keys" are not literals?</div>
<div><br>
</div>
<div>In these three cases, we just can reuse the existing linear dispatching. I only thought of optimizing the case if all keys are distinct SmallIntegers (and their number is greater than two).</div>
<div><br>
</div>
<div><span>> What if the branches are not sorted by "key"?</span><br>
</div>
<div><span><br>
</span></div>
<div><span>Then we can sort them, or would this be a problem?</span></div>
<p></p>
<div dir="ltr">
<div id="x_divtagdefaultwrapper" dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<p><br>
</p>
<p>Eliot, what is your idea of indexed jumps more in detail?</p>
<p>Actually I thought of simply converting the "conditional heap" structure you can find in #<span>interpretNextV3ClosuresInstructionFor: into bytecodes. Something like:</span></p>
<p><span><br>
</span></p>
<p></p>
<ol style="margin-bottom:0px; margin-top:0px">
<ol>
<li><span>pushTempVar: #x</span></li><li><span>dup</span></li><li><span><span style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols; font-size:16px">pushLit: </span>2</span></li><li><span>send: #<=</span></li><li><span>jumpIfFalse: 18</span></li><li><span>dup</span></li><li><span><span style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols; font-size:16px">pushLit: </span>1</span></li><li><span>send: #=</span></li><li><span>jumpIfFalse: 23</span></li><li><span>pop</span></li><li><span>push: #one</span></li><li><span>jump: 25</span></li><li><span>pushLit: 2</span></li><li><span>send: #=</span></li><li><span>jumpIfFalse: 23</span></li><li><span>push: #two</span></li><li><span>jump: 25</span></li><li><span><span style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols; font-size:16px">pushLit: </span>3</span></li><li><span>send: #=</span></li><li><span>jumpIfFalse: 23</span></li><li><span>push: #three</span></li><li><span>jump: 25</span></li><li>pushReceiver</li><li>send: #caseError</li><li>...</li></ol>
</ol>
<div><br>
</div>
<div>for:</div>
<div><br>
</div>
</div>
</div>
</div>
<blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;">
<div dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<div dir="ltr">
<div dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<div>x caseOf: {[1]->[#one]. [2]->[#two]. [3]->[#three]}</div>
</div>
</div>
</div>
</blockquote>
<div dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<div dir="ltr">
<div dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<div><br>
</div>
<div>Can you follow me? How would you think of this approach? :)</div>
<div><br>
</div>
<div>> <span>So the second thought, which applies both to the existing implementation and a binary dispatch is that we *badly* need to fix the debugger to not step through the case dispatch but instead step directly to the block that the case selects is to
the otherwise:</span></div>
<div><span><br>
</span></div>
<div><span>What do you mean by this? At the moment, the debugger halts at each case key block, and there is another halt that is invisible (unless you use the BytecodeDebugger) before sending #caseError. I think this is quite convenient when debugging a #caseOf:otherwise:
message?</span></div>
<div><span><br>
</span></div>
<div><span>Best,</span></div>
<div><span>Christoph</span></div>
<p></p>
<p><br>
</p>
<div id="x_Signature">
<div id="x_divtagdefaultwrapper" dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<div name="x_divtagdefaultwrapper" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:; margin:0">
<div>
<div class="x__rp_T4" id="x_Item.MessagePartBody">
<div class="x__rp_U4 x_ms-font-weight-regular x_ms-font-color-neutralDark x_rpHighlightAllClass x_rpHighlightBodyClass" id="x_Item.MessageUniqueBody" style="font-family:wf_segoe-ui_normal,"Segoe UI","Segoe WP",Tahoma,Arial,sans-serif,serif,EmojiFont">
<div dir="ltr">
<div id="x_divtagdefaultwrapper"><font face="Calibri,Helvetica,sans-serif,EmojiFont,Apple Color Emoji,Segoe UI Emoji,NotoColorEmoji,Segoe UI Symbol,Android Emoji,EmojiSymbols">
<div id="x_Signature">
<div style="margin:0px"><font style="font-family:Calibri,Arial,Helvetica,sans-serif,serif,EmojiFont"></font></div>
</div>
</font></div>
</div>
</div>
</div>
</div>
<div><font size="2" color="#808080"></font></div>
</div>
</div>
</div>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>Von:</b> Squeak-dev <squeak-dev-bounces@lists.squeakfoundation.org> im Auftrag von Eliot Miranda <eliot.miranda@gmail.com><br>
<b>Gesendet:</b> Sonntag, 23. Februar 2020 18:38:15<br>
<b>An:</b> The general-purpose Squeak developers list<br>
<b>Betreff:</b> Re: [squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages</font>
<div> </div>
</div>
</div>
<font size="2"><span style="font-size:10pt">
<div class="PlainText">Hi Levente,<br>
<br>
> On Feb 22, 2020, at 3:19 PM, Levente Uzonyi <leves@caesar.elte.hu> wrote:<br>
> <br>
> On Sat, 22 Feb 2020, Thiede, Christoph wrote:<br>
> <br>
>> > If you already analyzed it, I trust you, you are more advanced than me on the subject :)<br>
>> I would not say that I have an overview of the entire compiler system at the moment. Someone else should definitively review this before. :)<br>
>> > Fixing the Decompiler might be a bit more involved the way it is written now... > But with your fast progress and fearless diving in lower level details, I think you can do it :)<br>
>> Hm, maybe this could be some of my next adventures :-)<br>
>> (At the moment I'm trying to optimize #caseOf: to use binary search if appropriate, let's see what will come of it ^^)<br>
> <br>
> When is it appropriate to use binary search there?<br>
<br>
I like this thought! It made me think of two things. One would be how to implement properly a bytecode for case dispatch. I thought of indexing a literal array of bytecode PCs. But better is I think doing an indexed jump into a sequence of maximally sized
jumps. So one would go romething like<br>
<br>
bytecodes to compute an index on top of stack<br>
computedJump<br>
jump L0<br>
jump L1<br>
...<br>
jump LN<br>
bytecodes to dispatch case error<br>
<br>
But I think binary dispatch is much more compelling than introducing a bytecode for a very rare case (excuse the pun).<br>
<br>
So the second thought, which applies both to the existing implementation and a binary dispatch is that we *badly* need to fix the debugger to not step through the case dispatch but instead step directly to the block that the case selects is to the otherwise:.
It’s tedious to step through the huge case in instruction generation in the JIT, and stepping though in binary dispatch order would be confusing, albeit much shorter.<br>
<br>
> <br>
> Levente<br>
> <br>
>> Best,<br>
>> Christoph<br>
>> __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________<br>
>> Von: Squeak-dev <squeak-dev-bounces@lists.squeakfoundation.org> im Auftrag von Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com><br>
>> Gesendet: Samstag, 22. Februar 2020 18:50:26<br>
>> An: The general-purpose Squeak developers list<br>
>> Betreff: Re: [squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages
<br>
>> It was just a wild guess, because I did not look at the code nor any other detail.<br>
>> If you already analyzed it, I trust you, you are more advanced than me on the subject :)<br>
>> Fixing the Decompiler might be a bit more involved the way it is written now...<br>
>> But with your fast progress and fearless diving in lower level details, I think you can do it :)<br>
>> Le sam. 22 févr. 2020 à 18:44, Thiede, Christoph <Christoph.Thiede@student.hpi.uni-potsdam.de> a écrit :<br>
>> <br>
>> Hi Nicolas,<br>
>> <br>
>> > could it be for the case when there is no otherwise?<br>
>> In this case, a "self caseError" will be generated (though this is no correct behavior either IMO, see Problems with #caseError). I don't see how this should affect the jumps or returns before the otherwise part ...<br>
>> Best,<br>
>> Christoph<br>
>> __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________<br>
>> Von: Squeak-dev <squeak-dev-bounces@lists.squeakfoundation.org> im Auftrag von Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com><br>
>> Gesendet: Samstag, 22. Februar 2020 18:36:01<br>
>> An: The general-purpose Squeak developers list<br>
>> Betreff: Re: [squeak-dev] Question regarding compilation of #caseOf:[otherwise:] messages
<br>
>> Hi Christoph,<br>
>> could it be for the case when there is no otherwise?<br>
>> Le sam. 22 févr. 2020 à 18:24, Thiede, Christoph <Christoph.Thiede@student.hpi.uni-potsdam.de> a écrit :<br>
>> <br>
>> Hi all,<br>
>> <br>
>> this a question regarding the Compiler's implementation. I spent some time on it but could not yet find a satisfying explanation. Maybe someone of you can help me?<br>
>> <br>
>> Let's look into MessageNode >> #emitCodeForCase:encoder:value:, which contains the following passage:<br>
>> <br>
>> (isLast and: [allReturn]) ifTrue:<br>
>> [self emitCodeForJump: elseSize encoder: encoder]<br>
>> Btw, the equivalent in #sizeCodeForCase:value: is:<br>
>> <br>
>> (isLast and: [allReturn]) ifTrue: [thenSize := thenSize + (self sizeCode: encoder forJump: elseSize)].<br>
>> In the bytecode of a method, this will look like this:<br>
>> <br>
>> 89 <23> pushConstant: 2<br>
>> 90 <88> dup<br>
>> 91 <76> pushConstant: 1<br>
>> 92 <B6> send: =<br>
>> 93 <9A> jumpFalse: 97<br>
>> 94 <87> pop<br>
>> 95 <22> pushConstant: #one<br>
>> 96 <7C> returnTop<br>
>> 97 <77> pushConstant: 2<br>
>> 98 <B6> send: =<br>
>> 99 <9A> jumpFalse: 103<br>
>> 100 <21> pushConstant: #two<br>
>> 101 <7C> returnTop<br>
>> 102 <90> jumpTo: 104 "here!"<br>
>> 103 <20> pushConstant: 42<br>
>> 104 <87> pop<br>
>> I cannot see when this jump would be ever reached.<br>
>> Case 1: Any case is selected, and because allReturn is true, its inlined value block is guaranteed to #returnTop and thus not to reach the last jump (in the above example, this happens in pc101).<br>
>> Case 2: No case is selected, so the execution will jump straightly to the inlined otherwiseBlock (this is pc99 in the example).<br>
>> For what purpose do we need this jump (ex: pc102)? Should we maybe remove it?<br>
>> Are there any special situations in which #returns is true but there is any code path that does *not* return? Some weird exception handling trick, for example?<br>
>> Or was the dubious jump just designed as a fallback to catch any hypothetic failures in any other component of the compiler system?<br>
>> I removed the generation of this jump for testing and could not investigate any anomalies so far. All compiler tests are passing - except of a number of Decompiler tests, which probably would need to be updated as well.<br>
>> Please find a minimum changeset in the attachment that demonstrates my question.<br>
>> I am looking forward to your replies!<br>
>> Best,<br>
>> Christoph<br>
> <br>
<br>
</div>
</span></font></div>
</div>
</body>
</html>