<div dir="ltr">> Hi Ralph,<br>> <br>> On Sun, Nov 2, 2014 at 9:48 PM, Ralph Boland <<a href="mailto:rpboland@gmail.com">rpboland@gmail.com</a>> wrote:<br>> <br>> ><br>> > >><br>> > >> I am working on a parser generator tool (a replacement for SmaCC) and<br>> > >> one of the things I a m interested in is the direct translation of<br>> > >> language specifications into the virtual machine code (SmaCC and my<br>> > >> current version of it use Squeak as the target language).<br>> > >><br>> ><br>> > > First, a different approach than compiling to Smalltalk is to compile to<br>> > a<br>> > > parse tree. We do this in the pseudo JavaScript compiler we've<br>> > implemented<br>> > > at Cadence, translating an AST into a Squeak compiler parse tree for code<br>> > > generation. Targeting a parse tree gives you much more freedom; you can<br>> > > express things that aren't expressible in Smalltalk. And if you target<br>> > > bytecodes you can do even more.<br>> ><br>> ><br>> > I never considered using a parse tree as the target. An interesting idea<br>> > which in many instances may be the best approach. But for my regular<br>> > expression<br>> > example I would still want to generate byte codes. In any case I wouldn't<br>> > want to<br>> > restrict users of my parser generator tool to any one of the three options<br>> > (Smalltalk code,<br>> > parse tree, byte code). It is my responsibility to make all three options<br>> > as easy and<br>> > efficient as reasonably possible for users of the parser generator tool.<br>> > Haven't put<br>> > much thought into this yet though. So far Smalltalk (Squeak) is the only<br>> > option.<br>> ><br>> ><br>> > >> One of the problems I have is that, for some languages, the natural<br>> > >> translation<br>> > >> into VM code uses computed gotos.<br>> > >> There are two scenarios here:<br>> > >><br>> > >> 1) goto X where X is a variable.<br>> > >> 2) goto (coll at: y) where coll is a Collection.<br>> > >><br>> ><br>> > > There are several ways of implementing this without computed bytecodes in<br>> > > the instruction set, but there is also the possibility of implementing it<br>> > > directly in the instruction set.<br>> ><br>> > > Off the top of my head one could<br>> ><br>> > > - map to perform: using some mangled selector. Yes this is problematic<br>> > > because one has to split the scope between the two methods, so in general<br>> > > it's not a solution<br>> ><br>> > Doesn't appeal to me.<br>> ><br>> > > - map to a case statement, which is what Squeak does. Just map it to a<br>> > > sequence of compare and branches. Or better still, to a binary tree.<br>> > > Coincidentally this is used by the JIT to implement block dispatch in<br>> > > methods that contain more than one block. I know of other VM<br>> > > implementations using it for PIC dispatch with really good performance.<br>> ><br>> > I don't know what you mean my Squeak mapping to a case statement since<br>> > there is no case statement in Squeak/Smalltalk and I can't off hand think<br>> > of<br>> > where one is needed (some Squeak users might feel they need one but that<br>> > is a<br>> > different matter).<br>> ><br>> <br>> But there is. And it is very convenient when one doesn't want to spread a<br>> case over different classes, or when the cases distribute over values of<br>> the same class (e.g. integer values). People often claim that a case<br>> statement isn't necessary because one has polymorphism, but unless the<br>> language supports singletons (which of course Smalltalk does not) a case<br>> statement is much more readable than e.g. an if-then-else tree or a<br>> "Dictionary mapping values to blocks or selectors" solution.<br>> <br>> Since you're unaware of the case statement I suggest you browse senders of<br>> caseOf: and caseOf:otherwise: in Squeak trunk (which includes selectors of<br>> optimized selectors that end up not being sent) or caseError, which is sent<br>> when there's no otherwise clause. Here's an example:<br>> <br>> menuHook: aMenu named: aSymbol shifted: aBool<br>> "Enhance aMenu with registered services."<br>> aSymbol<br>> caseOf:<br>> { [ #classListMenu ] -> [ ServiceGui browser: self classMenu: aMenu ].<br>> [ #codePaneMenu ] -> [ ServiceGui browser: self codePaneMenu: aMenu ].<br>> [ #messageCategoryMenu] -> [ ServiceGui browser: self messageCategoryMenu:<br>> aMenu ].<br>> [ #messageListMenu ] -> [ ServiceGui browser: self messageListMenu: aMenu ].<br>> [ #systemCategoryMenu ] -> [ ServiceGui browser: self classCategoryMenu:<br>> aMenu ] }<br>> otherwise: [ "do nothing" ]<br>> <br>> This compiles down to a sequence of comparisons.<br><br>I was aware of caseOf: in Squeak. I always found it awkward to use and<br>felt a true case statement would be simpler. Alas, it's impossible to<br>have a true case statement added to Smalltalk now I think.<br><br>caseOf: is user code and thus, in principle, outside the scope of the VM.<br>For example, if I didn't want the sequential search of caseOf: I could<br>implement a method doBlockAt: method in class Dictionary that assumes<br>the values stored in the dictionary are blocks and invokes the block<br>found by performing at: on the arg of doBlockAt:.<br>But the code for both caseOf: and doBlockAt: are written by users so the<br>VM can't optimize it, is forced to have the overhead of using blocks,<br>and must be locked in to the search algorithm the user has chosen (for<br>better or for worse).<br><br>> > The use of compare and branches might be OK in some cases<br>> > but a mess for the finite state machines generated from regular<br>> > expressions.<br>> > Actually, even with computed gotos FSMs are somewhat messy but without<br>> > them<br>> > it's worse. I don't know what 'PIC dispatch' is.<br>> ><br>> <br>> Polymorphic inline cache dispatch. In JIT VMs such as Cog polymorphic send<br>> sites are optimized using jump tables, one jump for each class encountered<br>> at the send site, up tio some small limit such as 6 cases. Right now in<br>> Cog these jump tables are sequential comparisons. But in some VMs, where<br>> the degree of polymorphism may be much higher (think prototype languages<br>> such as JavaScript) a binary tree may be much miore efficient, if harder to<br>> organize.<br>> <br>> To use a binary tree don't I need some kind of computed goto for when I<br>> > reach<br>> > a leaf of the tree????<br>> ><br>> <br>> No. Once you're at the leaf you just include the bytecodes. So for<br>> example take the following case statement:<br>> <br>> quickPrimitiveGeneratorFor: aQuickPrimitiveIndex<br>> <api><br>> <returnTypeC: 'int (*quickPrimitiveGeneratorFor(sqInt<br>> aQuickPrimitiveIndex))(void)'><br>> ^aQuickPrimitiveIndex<br>> caseOf: {<br>> [256] -> [#genQuickReturnSelf].<br>> [257] -> [#genQuickReturnConstNil].<br>> [258] -> [#genQuickReturnConstTrue].<br>> [259] -> [#genQuickReturnConstFalse].<br>> [260] -> [#genQuickReturnConstMinusOne].<br>> [261] -> [#genQuickReturnConstZero].<br>> [262] -> [#genQuickReturnConstOne].<br>> [263] -> [#genQuickReturnConstTwo] }<br>> otherwise: [#genQuickReturnInstVar]<br>> <br>> This is compiled in the current Squeak compiler as<br>> <br>> 61 <10> pushTemp: 0<br>> 62 <88> dup<br>> 63 <2A> pushConstant: 256<br>> 64 <B6> send: =<br>> 65 <9B> jumpFalse: 70<br>> 66 <87> pop<br>> 67 <29> pushConstant: #genQuickReturnSelf<br>> 68 <A4 35> jumpTo: 123<br>> 70 <88> dup<br>> 71 <28> pushConstant: 257<br>> 72 <B6> send: =<br>> 73 <9B> jumpFalse: 78<br>> 74 <87> pop<br>> 75 <21> pushConstant: #genQuickReturnConstNil<br>> 76 <A4 2D> jumpTo: 123<br>> ...<br>> 117 <22> pushConstant: 263<br>> 118 <B6> send: =<br>> 119 <99> jumpFalse: 122<br>> 120 <21> pushConstant: #genQuickReturnConstTwo<br>> 121 <90> jumpTo: 123<br>> 122 <20> pushConstant: #genQuickReturnInstVar<br>> 123 <7C> returnTop<br>> <br>> but it could be more efficient if the code were<br>> <br>> pushTemp: 0<br>> dup<br>> pushConstant: 256<br>> send: <<br>> jumpFalse: L1<br>> dup<br>> pushConstant: 260<br>> send: <<br>> jumpFalse: L2<br>> dup<br>> pushConstant: 258<br>> send: <<br>> jumpFalse: L3<br>> dup<br>> pushConstant: 257<br>> send: <<br>> jumpFalse: L4<br>> pushConstant: #genQuickReturnSelf<br>> jumpTo: L0<br>> pushConstant: #genQuickReturnConstNil<br>> jumpTo: L0<br>> ...<br>> L1:<br>> pushConstant: #genQuickReturnInstVar<br>> L0:<br>> returnTop<br><br>I have no problem with this code per say; if Squeak, the language,<br>had a case statement it could be implemented this way.<br>But I wouldn't want to be forced to implement my FSMs this way.<br>It might be acceptable for small FSMs.<br>I want to avoid sequential search and<br> even binary search might be rather expensive.<br>I look at computed gotos as the solution but,<br>as you pointed out, computed gotos pose problems for JIT.<br>Admittedly, for large FSM's, it might be best or necessary to<br>use a FSM simulator anyway, as I do now.<br><br>> > - use thisContext pc: value.<br>> ><br>> > This would be a possibility for me to experiment with for now. When I<br>> > have a working<br>> > parser generator tool I could campaign for my computed goto instructions<br>> > to be added<br>> > to the VM.<br>> ><br>> > > This /should/ be fine in the stack VM, but<br>> > > slooooow in the JIT because internally mapping bytecode pcs to machine<br>> > code<br>> > > pcs is slow, and currently slower still because the frame will be<br>> > converted<br>> > > to a pure context and then converted back into a frame on the return from<br>> > > pc:. But this solution isn't to be rejected out-of-hand. It can be<br>> > > optimized to avoid the frame conversion and the JIT might be able to<br>> > > optimize it.<br>> ><br>> > I assume that if computed gotos were used the translation to machine code<br>> > would require a direct<br>> > mapping of (virtually labeled) bytecode locations to machine code<br>> > locations. I think this can be done<br>> > in a reasonable amount of time but others such as yourself clearly<br>> > understand the issues far better than<br>> > I do. The dirty solution to start would be to simply not JIT the code<br>> > that uses computed gotos.<br>> ><br>> <br>> Yes, it could be. The JIT would generate a jump table from the literal<br>> containing the bytecoded pcs, and there would be no conversion; only<br>> indexing the jump table and jumping. Again, organizing that table as a<br>> binary switch may well be faster on modern architectures. Indirect jumps<br>> typically involve pipeline stalls, whereas binary jump trees don't.<br>> <br>> > The main problem is the compiler has no support for labels so<br>> > > there would be work here.<br>> ><br>> > I don't mind doing the work but to my way of thinking "goto X" is pretty<br>> > basic<br>> > and is thus best handled at the VM/byte code level. Anything else is doing<br>> > in a complicated way something that is fairly simple. Of course changing<br>> > the VM/byte codes by even a single byte code is a major deal unless done<br>> > when the VM/byte codes are initially created. Alas I must deal with what<br>> > already exists. Even so, my preference is to work with the VM if at all<br>> > possible.<br>> ><br>> ><br>> > >> For example, one such language is that of regular expressions, which I<br>> > >> wish to translate into finite state machines implemented in VM code.<br>> > >> In this case I need case 2) gotos where coll is a collection of<br>> > >> associations, possibly a<br>> > >> Dictionary. I also plan to write a debugger for this (and other<br>> > languages)<br>> > >> but that is another story.<br>> > >><br>> > >> I realize that the Cog VM is being built for Smalltalk (Squeak? Pharo?)<br>> > >> for which the goto instructions are not needed and thus I assume<br>> > >> unavailable. But there is something to<br>> > >> viewing a virtual machine as general purpose and thus the target of<br>> > >> multiple languages as is<br>> > >> the case for the Java virtual machine.<br>> > >> If the Cog VM is viewed this way then I argue there is a need for my<br>> > goto<br>> > >> instructions<br>> > >> because some languages have need for them.<br>> > >> For example, many languages have case statements. (I am all for object<br>> > >> oriented<br>> > >> but I would be willing to accept a case statement in Smalltalk too; the<br>> > >> Squeak code<br>> > >> implemented one in Squeak doesn't cut it).<br>> > ><br>> ><br>> > > I've occasionally thought about this for many years. A computed jump<br>> > might<br>> > > be nice. Eg index an Array literal of pcs with the integer on top of<br>> > > stack, falling through on bad type or out of range.<br>> ><br>> > This is the way I am thinking. If there are other reasons for a computed<br>> > jumpTo<br>> > as well all the better.<br>> ><br>> > >> Anyway, I am not arguing to Change Squeak or Smalltalk but I am arguing<br>> > >> to have my goto instructions in Cog VM. Is there any chance of this?????<br>> > >><br>> ><br>> > > There's no chance of me spending time implementing this any time soon. I<br>> > > have too much high-priority tasks to tackle this. But I want to<br>> > encourage<br>> > > you or others to have a go implementing it. It's fun!<br>> ><br>> > I understand and am willing to be the one to add one or more computed jump<br>> > instructions, including working on the JIT code generator if needed.<br>> > As you say it should be fun (and also educational). But<br>> > 1) I am pretty busy now too and probably won't get to this for a year.<br>> > 2) If I am to do this it would be great if someone can write a<br>> > specification as to<br>> > what is to be done. If someone can write this now that would be<br>> > great but<br>> > if they write it when I post that I am ready to do the work that<br>> > would also<br>> > be fine.<br>> > 3) I don't want to just have my own private VM/byte codes. I want<br>> > users of my<br>> > parser generator tool to be able to load it into a standard<br>> > version of Squeak<br>> > and run it there including the possible generation of compilers<br>> > for compiling<br>> > their domain specific language programs into byte codes if desired.<br>> ><br>> <br>> Sure. Get back to me when you're ready to work on it and I'll write the<br>> specification, and help you with whatever info you need. There should be<br>> room in the bytecode sets we'll likely be using next year.<br><br><br>WILL DO. SHOULD BE FUN.<br>WILL DO. SHOULD BE FUN.<br>WILL DO. SHOULD BE FUN.<br><br><br>> <br>> ><br>> > >> I don't know the Squeak VM or the Cog VM either but I assume these<br>> > >> instructions don't exist because I see no need of them when the source<br>> > >> language is<br>> > >> Squeak or any version of Smalltalk for that matter. I also assume that<br>> > >> there is already<br>> > >> a full list of 256 instructions in the Cog VM and thus no room for my<br>> > goto<br>> > >> instructions<br>> > >> unless some instructions are removed.<br>> > >><br>> > >> Are there Cog VM instructions that are so rarely used that they could be<br>> > >> removed without<br>> > >> unreasonably slowing down the Cog VM interpretation of byte codes<br>> > >> generated from Squeak source code?????<br>> > >><br>> ><br>> > > The current set has 3 unused bytecodes, one of which Spur uses, so<br>> > > effectively there are two unused bytecodes.<br>> ><br>> > Levente Uzonyi in his posting pointed out that only one instruction is<br>> > needed.<br>> > I don't like having to push the address to jump to onto the stack,<br>> > preferring a byte<br>> > code with an argument, but I could live with his solution if that is what<br>> > is decided.<br>> > In the case of goto coll at: X the address is likely to end up on top<br>> > of the stack<br>> > anyway so Levente's jumpToTop instruction looks good in any case.<br>> ><br>> <br>> If the bytecode is one that takes an integer on top of stack, and an Array<br>> literal containing bytecode pcs, falling through on out of range, then<br>> nothing other than the index need be pushed on top of stack. That would be<br>> my preference.<br>> <br><br>Again, for my FSM, case this would often be considered to be good.<br>But if the state transition tables are sparse then Dictionaries<br>might be preferable to Arrays.<br>My expection is that at: be sent to the collection object<br> to get the address to go to. Knowing that the collection<br>is an array though makes it easier for the compiler/VM to<br>ensure that the addresses stored in the collection are valid.<br>Actually, the compiler will be generating the addresses.<br>Does the VM have absolute trust in the compiler to generate valid addresses?<br>What if the compiler is generated by my parser generator tool?<br><br><br>> > The Cog VMs support multiple bytecode sets. If you look at the<br>> > > BytecodeSets package on VMMaker you can read the class comments of the<br>> > > BytecodeEncoder subclasses such as EncoderForSistaV1. These bytecode<br>> > sets<br>> > > have a few more unused bytecodes. This multiple bytecode set support is<br>> > > better implemented in Spur where there is only one compiled method header<br>> > > format and support for 64k literals. So let me encourage you to move to<br>> > > Spur and to look at the Sista set. The class comment of each encoder<br>> > class<br>> > > specifies the instruction set it targets.<br>> ><br>> > I am prepared to work with Spur and the Sista set. I am looking for<br>> > someone to<br>> > say that if I do this work that incorporating the work into Spur will be<br>> > seriously<br>> > considered.<br>> ><br>> <br>> I can say that, yes. I will seriously consider adding it. I think its a<br>> useful thing in the bytecode set, precisely to allow compiling other<br>> languages to the VM.<br><br><br>GLAD TO HEAR THIS.<br><br><br>> <br>> <br>> <br>> ><br>> > Ralph Boland<br>> ><br>> ><br>> ><br>> <br>> <br>> --<br>> best,<br>> Eliot<br><br><br>Ralph<br></div><div class="gmail_extra"><br><div class="gmail_quote">On 3 November 2014 12:34, <span dir="ltr"><<a href="mailto:vm-dev-request@lists.squeakfoundation.org" target="_blank">vm-dev-request@lists.squeakfoundation.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Send Vm-dev mailing list submissions to<br>
<a href="mailto:vm-dev@lists.squeakfoundation.org">vm-dev@lists.squeakfoundation.org</a><br>
<br>
To subscribe or unsubscribe via the World Wide Web, visit<br>
<a href="http://lists.squeakfoundation.org/mailman/listinfo/vm-dev" target="_blank">http://lists.squeakfoundation.org/mailman/listinfo/vm-dev</a><br>
or, via email, send a message with subject or body 'help' to<br>
<a href="mailto:vm-dev-request@lists.squeakfoundation.org">vm-dev-request@lists.squeakfoundation.org</a><br>
<br>
You can reach the person managing the list at<br>
<a href="mailto:vm-dev-owner@lists.squeakfoundation.org">vm-dev-owner@lists.squeakfoundation.org</a><br>
<br>
When replying, please edit your Subject line so it is more specific<br>
than "Re: Contents of Vm-dev digest..."<br>
<br>
<br>
Today's Topics:<br>
<br>
1. Re: goto instruction with Cog VM (Eliot Miranda)<br>
<br>
<br>
----------------------------------------------------------------------<br>
<br>
Message: 1<br>
Date: Mon, 3 Nov 2014 11:34:48 -0800<br>
From: Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>><br>
Subject: Re: [Vm-dev] goto instruction with Cog VM<br>
To: Squeak Virtual Machine Development Discussion<br>
<<a href="mailto:vm-dev@lists.squeakfoundation.org">vm-dev@lists.squeakfoundation.org</a>><br>
Message-ID:<br>
<<a href="mailto:CAC20JE1RduKQW_EdMsfah156QnTbR8USt9dEb4mj1rb15rndqA@mail.gmail.com">CAC20JE1RduKQW_EdMsfah156QnTbR8USt9dEb4mj1rb15rndqA@mail.gmail.com</a>><br>
Content-Type: text/plain; charset="utf-8"<br>
<br>
Hi Ralph,<br>
<br>
On Sun, Nov 2, 2014 at 9:48 PM, Ralph Boland <<a href="mailto:rpboland@gmail.com">rpboland@gmail.com</a>> wrote:<br>
<br>
><br>
> >><br>
> >> I am working on a parser generator tool (a replacement for SmaCC) and<br>
> >> one of the things I a m interested in is the direct translation of<br>
> >> language specifications into the virtual machine code (SmaCC and my<br>
> >> current version of it use Squeak as the target language).<br>
> >><br>
><br>
> > First, a different approach than compiling to Smalltalk is to compile to<br>
> a<br>
> > parse tree. We do this in the pseudo JavaScript compiler we've<br>
> implemented<br>
> > at Cadence, translating an AST into a Squeak compiler parse tree for code<br>
> > generation. Targeting a parse tree gives you much more freedom; you can<br>
> > express things that aren't expressible in Smalltalk. And if you target<br>
> > bytecodes you can do even more.<br>
><br>
><br>
> I never considered using a parse tree as the target. An interesting idea<br>
> which in many instances may be the best approach. But for my regular<br>
> expression<br>
> example I would still want to generate byte codes. In any case I wouldn't<br>
> want to<br>
> restrict users of my parser generator tool to any one of the three options<br>
> (Smalltalk code,<br>
> parse tree, byte code). It is my responsibility to make all three options<br>
> as easy and<br>
> efficient as reasonably possible for users of the parser generator tool.<br>
> Haven't put<br>
> much thought into this yet though. So far Smalltalk (Squeak) is the only<br>
> option.<br>
><br>
><br>
> >> One of the problems I have is that, for some languages, the natural<br>
> >> translation<br>
> >> into VM code uses computed gotos.<br>
> >> There are two scenarios here:<br>
> >><br>
> >> 1) goto X where X is a variable.<br>
> >> 2) goto (coll at: y) where coll is a Collection.<br>
> >><br>
><br>
> > There are several ways of implementing this without computed bytecodes in<br>
> > the instruction set, but there is also the possibility of implementing it<br>
> > directly in the instruction set.<br>
><br>
> > Off the top of my head one could<br>
><br>
> > - map to perform: using some mangled selector. Yes this is problematic<br>
> > because one has to split the scope between the two methods, so in general<br>
> > it's not a solution<br>
><br>
> Doesn't appeal to me.<br>
><br>
> > - map to a case statement, which is what Squeak does. Just map it to a<br>
> > sequence of compare and branches. Or better still, to a binary tree.<br>
> > Coincidentally this is used by the JIT to implement block dispatch in<br>
> > methods that contain more than one block. I know of other VM<br>
> > implementations using it for PIC dispatch with really good performance.<br>
><br>
> I don't know what you mean my Squeak mapping to a case statement since<br>
> there is no case statement in Squeak/Smalltalk and I can't off hand think<br>
> of<br>
> where one is needed (some Squeak users might feel they need one but that<br>
> is a<br>
> different matter).<br>
><br>
<br>
But there is. And it is very convenient when one doesn't want to spread a<br>
case over different classes, or when the cases distribute over values of<br>
the same class (e.g. integer values). People often claim that a case<br>
statement isn't necessary because one has polymorphism, but unless the<br>
language supports singletons (which of course Smalltalk does not) a case<br>
statement is much more readable than e.g. an if-then-else tree or a<br>
"Dictionary mapping values to blocks or selectors" solution.<br>
<br>
Since you're unaware of the case statement I suggest you browse senders of<br>
caseOf: and caseOf:otherwise: in Squeak trunk (which includes selectors of<br>
optimized selectors that end up not being sent) or caseError, which is sent<br>
when there's no otherwise clause. Here's an example:<br>
<br>
menuHook: aMenu named: aSymbol shifted: aBool<br>
"Enhance aMenu with registered services."<br>
aSymbol<br>
caseOf:<br>
{ [ #classListMenu ] -> [ ServiceGui browser: self classMenu: aMenu ].<br>
[ #codePaneMenu ] -> [ ServiceGui browser: self codePaneMenu: aMenu ].<br>
[ #messageCategoryMenu] -> [ ServiceGui browser: self messageCategoryMenu:<br>
aMenu ].<br>
[ #messageListMenu ] -> [ ServiceGui browser: self messageListMenu: aMenu ].<br>
[ #systemCategoryMenu ] -> [ ServiceGui browser: self classCategoryMenu:<br>
aMenu ] }<br>
otherwise: [ "do nothing" ]<br>
<br>
This compiles down to a sequence of comparisons.<br>
<br>
The use of compare and branches might be OK in some cases<br>
> but a mess for the finite state machines generated from regular<br>
> expressions.<br>
> Actually, even with computed gotos FSMs are somewhat messy but without<br>
> them<br>
> it's worse. I don't know what 'PIC dispatch' is.<br>
><br>
<br>
Polymorphic inline cache dispatch. In JIT VMs such as Cog polymorphic send<br>
sites are optimized using jump tables, one jump for each class encountered<br>
at the send site, up tio some small limit such as 6 cases. Right now in<br>
Cog these jump tables are sequential comparisons. But in some VMs, where<br>
the degree of polymorphism may be much higher (think prototype languages<br>
such as JavaScript) a binary tree may be much miore efficient, if harder to<br>
organize.<br>
<br>
To use a binary tree don't I need some kind of computed goto for when I<br>
> reach<br>
> a leaf of the tree????<br>
><br>
<br>
No. Once you're at the leaf you just include the bytecodes. So for<br>
example take the following case statement:<br>
<br>
quickPrimitiveGeneratorFor: aQuickPrimitiveIndex<br>
<api><br>
<returnTypeC: 'int (*quickPrimitiveGeneratorFor(sqInt<br>
aQuickPrimitiveIndex))(void)'><br>
^aQuickPrimitiveIndex<br>
caseOf: {<br>
[256] -> [#genQuickReturnSelf].<br>
[257] -> [#genQuickReturnConstNil].<br>
[258] -> [#genQuickReturnConstTrue].<br>
[259] -> [#genQuickReturnConstFalse].<br>
[260] -> [#genQuickReturnConstMinusOne].<br>
[261] -> [#genQuickReturnConstZero].<br>
[262] -> [#genQuickReturnConstOne].<br>
[263] -> [#genQuickReturnConstTwo] }<br>
otherwise: [#genQuickReturnInstVar]<br>
<br>
This is compiled in the current Squeak compiler as<br>
<br>
61 <10> pushTemp: 0<br>
62 <88> dup<br>
63 <2A> pushConstant: 256<br>
64 <B6> send: =<br>
65 <9B> jumpFalse: 70<br>
66 <87> pop<br>
67 <29> pushConstant: #genQuickReturnSelf<br>
68 <A4 35> jumpTo: 123<br>
70 <88> dup<br>
71 <28> pushConstant: 257<br>
72 <B6> send: =<br>
73 <9B> jumpFalse: 78<br>
74 <87> pop<br>
75 <21> pushConstant: #genQuickReturnConstNil<br>
76 <A4 2D> jumpTo: 123<br>
...<br>
117 <22> pushConstant: 263<br>
118 <B6> send: =<br>
119 <99> jumpFalse: 122<br>
120 <21> pushConstant: #genQuickReturnConstTwo<br>
121 <90> jumpTo: 123<br>
122 <20> pushConstant: #genQuickReturnInstVar<br>
123 <7C> returnTop<br>
<br>
but it could be more efficient if the code were<br>
<br>
pushTemp: 0<br>
dup<br>
pushConstant: 256<br>
send: <<br>
jumpFalse: L1<br>
dup<br>
pushConstant: 260<br>
send: <<br>
jumpFalse: L2<br>
dup<br>
pushConstant: 258<br>
send: <<br>
jumpFalse: L3<br>
dup<br>
pushConstant: 257<br>
send: <<br>
jumpFalse: L4<br>
pushConstant: #genQuickReturnSelf<br>
jumpTo: L0<br>
pushConstant: #genQuickReturnConstNil<br>
jumpTo: L0<br>
...<br>
L1:<br>
pushConstant: #genQuickReturnInstVar<br>
L0:<br>
returnTop<br>
<br>
> - use thisContext pc: value.<br>
><br>
> This would be a possibility for me to experiment with for now. When I<br>
> have a working<br>
> parser generator tool I could campaign for my computed goto instructions<br>
> to be added<br>
> to the VM.<br>
><br>
> > This /should/ be fine in the stack VM, but<br>
> > slooooow in the JIT because internally mapping bytecode pcs to machine<br>
> code<br>
> > pcs is slow, and currently slower still because the frame will be<br>
> converted<br>
> > to a pure context and then converted back into a frame on the return from<br>
> > pc:. But this solution isn't to be rejected out-of-hand. It can be<br>
> > optimized to avoid the frame conversion and the JIT might be able to<br>
> > optimize it.<br>
><br>
> I assume that if computed gotos were used the translation to machine code<br>
> would require a direct<br>
> mapping of (virtually labeled) bytecode locations to machine code<br>
> locations. I think this can be done<br>
> in a reasonable amount of time but others such as yourself clearly<br>
> understand the issues far better than<br>
> I do. The dirty solution to start would be to simply not JIT the code<br>
> that uses computed gotos.<br>
><br>
<br>
Yes, it could be. The JIT would generate a jump table from the literal<br>
containing the bytecoded pcs, and there would be no conversion; only<br>
indexing the jump table and jumping. Again, organizing that table as a<br>
binary switch may well be faster on modern architectures. Indirect jumps<br>
typically involve pipeline stalls, whereas binary jump trees don't.<br>
<br>
> The main problem is the compiler has no support for labels so<br>
> > there would be work here.<br>
><br>
> I don't mind doing the work but to my way of thinking "goto X" is pretty<br>
> basic<br>
> and is thus best handled at the VM/byte code level. Anything else is doing<br>
> in a complicated way something that is fairly simple. Of course changing<br>
> the VM/byte codes by even a single byte code is a major deal unless done<br>
> when the VM/byte codes are initially created. Alas I must deal with what<br>
> already exists. Even so, my preference is to work with the VM if at all<br>
> possible.<br>
><br>
><br>
> >> For example, one such language is that of regular expressions, which I<br>
> >> wish to translate into finite state machines implemented in VM code.<br>
> >> In this case I need case 2) gotos where coll is a collection of<br>
> >> associations, possibly a<br>
> >> Dictionary. I also plan to write a debugger for this (and other<br>
> languages)<br>
> >> but that is another story.<br>
> >><br>
> >> I realize that the Cog VM is being built for Smalltalk (Squeak? Pharo?)<br>
> >> for which the goto instructions are not needed and thus I assume<br>
> >> unavailable. But there is something to<br>
> >> viewing a virtual machine as general purpose and thus the target of<br>
> >> multiple languages as is<br>
> >> the case for the Java virtual machine.<br>
> >> If the Cog VM is viewed this way then I argue there is a need for my<br>
> goto<br>
> >> instructions<br>
> >> because some languages have need for them.<br>
> >> For example, many languages have case statements. (I am all for object<br>
> >> oriented<br>
> >> but I would be willing to accept a case statement in Smalltalk too; the<br>
> >> Squeak code<br>
> >> implemented one in Squeak doesn't cut it).<br>
> ><br>
><br>
> > I've occasionally thought about this for many years. A computed jump<br>
> might<br>
> > be nice. Eg index an Array literal of pcs with the integer on top of<br>
> > stack, falling through on bad type or out of range.<br>
><br>
> This is the way I am thinking. If there are other reasons for a computed<br>
> jumpTo<br>
> as well all the better.<br>
><br>
> >> Anyway, I am not arguing to Change Squeak or Smalltalk but I am arguing<br>
> >> to have my goto instructions in Cog VM. Is there any chance of this?????<br>
> >><br>
><br>
> > There's no chance of me spending time implementing this any time soon. I<br>
> > have too much high-priority tasks to tackle this. But I want to<br>
> encourage<br>
> > you or others to have a go implementing it. It's fun!<br>
><br>
> I understand and am willing to be the one to add one or more computed jump<br>
> instructions, including working on the JIT code generator if needed.<br>
> As you say it should be fun (and also educational). But<br>
> 1) I am pretty busy now too and probably won't get to this for a year.<br>
> 2) If I am to do this it would be great if someone can write a<br>
> specification as to<br>
> what is to be done. If someone can write this now that would be<br>
> great but<br>
> if they write it when I post that I am ready to do the work that<br>
> would also<br>
> be fine.<br>
> 3) I don't want to just have my own private VM/byte codes. I want<br>
> users of my<br>
> parser generator tool to be able to load it into a standard<br>
> version of Squeak<br>
> and run it there including the possible generation of compilers<br>
> for compiling<br>
> their domain specific language programs into byte codes if desired.<br>
><br>
<br>
Sure. Get back to me when you're ready to work on it and I'll write the<br>
specification, and help you with whatever info you need. There should be<br>
room in the bytecode sets we'll likely be using next year.<br>
<br>
<br>
><br>
> >> I don't know the Squeak VM or the Cog VM either but I assume these<br>
> >> instructions don't exist because I see no need of them when the source<br>
> >> language is<br>
> >> Squeak or any version of Smalltalk for that matter. I also assume that<br>
> >> there is already<br>
> >> a full list of 256 instructions in the Cog VM and thus no room for my<br>
> goto<br>
> >> instructions<br>
> >> unless some instructions are removed.<br>
> >><br>
> >> Are there Cog VM instructions that are so rarely used that they could be<br>
> >> removed without<br>
> >> unreasonably slowing down the Cog VM interpretation of byte codes<br>
> >> generated from Squeak source code?????<br>
> >><br>
><br>
> > The current set has 3 unused bytecodes, one of which Spur uses, so<br>
> > effectively there are two unused bytecodes.<br>
><br>
> Levente Uzonyi in his posting pointed out that only one instruction is<br>
> needed.<br>
> I don't like having to push the address to jump to onto the stack,<br>
> preferring a byte<br>
> code with an argument, but I could live with his solution if that is what<br>
> is decided.<br>
> In the case of goto coll at: X the address is likely to end up on top<br>
> of the stack<br>
> anyway so Levente's jumpToTop instruction looks good in any case.<br>
><br>
<br>
If the bytecode is one that takes an integer on top of stack, and an Array<br>
literal containing bytecode pcs, falling through on out of range, then<br>
nothing other than the index need be pushed on top of stack. That would be<br>
my preference.<br>
<br>
> The Cog VMs support multiple bytecode sets. If you look at the<br>
> > BytecodeSets package on VMMaker you can read the class comments of the<br>
> > BytecodeEncoder subclasses such as EncoderForSistaV1. These bytecode<br>
> sets<br>
> > have a few more unused bytecodes. This multiple bytecode set support is<br>
> > better implemented in Spur where there is only one compiled method header<br>
> > format and support for 64k literals. So let me encourage you to move to<br>
> > Spur and to look at the Sista set. The class comment of each encoder<br>
> class<br>
> > specifies the instruction set it targets.<br>
><br>
> I am prepared to work with Spur and the Sista set. I am looking for<br>
> someone to<br>
> say that if I do this work that incorporating the work into Spur will be<br>
> seriously<br>
> considered.<br>
><br>
<br>
I can say that, yes. I will seriously consider adding it. I think its a<br>
useful thing in the bytecode set, precisely to allow compiling other<br>
languages to the VM.<br>
<br>
<br>
<br>
><br>
> Ralph Boland<br>
><br>
><br>
><br>
<br>
<br>
--<br>
best,<br>
Eliot<br>
-------------- next part --------------<br>
An HTML attachment was scrubbed...<br>
URL: <a href="http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20141103/469369c9/attachment.htm" target="_blank">http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20141103/469369c9/attachment.htm</a><br>
<br>
------------------------------<br>
<br>
_______________________________________________<br>
Vm-dev mailing list<br>
<a href="mailto:Vm-dev@lists.squeakfoundation.org">Vm-dev@lists.squeakfoundation.org</a><br>
<a href="http://lists.squeakfoundation.org/mailman/listinfo/vm-dev" target="_blank">http://lists.squeakfoundation.org/mailman/listinfo/vm-dev</a><br>
<br>
<br>
End of Vm-dev Digest, Vol 101, Issue 7<br>
**************************************<br>
</blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature"><div dir="ltr"><h1>-- Those who can make you believe absurdities, can make you commit atrocities -- Voltaire</h1></div></div>
</div>