[Vm-dev] Re: Revising the map data for exotic sends

[Eliot Miranda]

On Fri, Apr 3, 2015 at 12:03 PM, Eliot Miranda <eliot.miranda at gmail.com>
wrote:

>
>
> On Fri, Apr 3, 2015 at 11:18 AM, Eliot Miranda <eliot.miranda at gmail.com>
> wrote:
>
>> Hi Ryan, Hi Tim, Hi Clément, and anyone else interested in Cogit arcana,
>>
>>    Sista needs a directed super send bytecode.  A normal super bytecode
>> takes the class above which to start the lookup implicitly from the method
>> class (the last literal in a method).  A directed super send takes
>> the class above which to start the lookup as an explicit parameter.  In
>> Ssta's case we're pushing the class association on the stack immediately
>> before the super send bytecode, and marking the super send bytecode as
>> directed using a flag bit in one of the extensions.
>>
>> Compiling a directed super is trivial; simply make the literal variable
>> that was notionally pushed on the stack an argument of a new
>> ceSendDirectedSuper trampoline.  But this implies that when a linked
>> directed super send bytecode is unlinked (e.g. method redefinition or
>> method zone compaction) we can map back to this ceSendDirectedSuper
>> tramp[oline.
>>
>> Up until now, the different send trampolines have been identified by
>> looking at the alignment of the linked call instruction; every different
>> kind of send needs a different entry point in the target method at a
>> different alignment.  This worked well when there were only self and super
>> sends.  It also meant that there was only a single method map type for
>> sends, which kept the method metadata small.  Now Newspeak has two more
>> send types; Sista will use three.  On x86 each alignment can be generated
>> by adding a 1 byte nop in the right place.  Methods themselves are aligned
>> on 8-byte boundaries, so the scheme would extend to 8 different send types
>> at a pinch on x86.  Of course on ARM this doesn't work well at all;
>> instructions are 4 bytes, and so 8 byte alignment gives only two different
>> alignments, and we were planning to extend the method alignment to e.g. 16
>> bytes.
>>
>> But all this puts extra code in the entry sequence albeit only in the
>> form of nops.  But unlinking is extremely rare so we're letting the tail
>> wag the dog.  Instead, I'm going to revise the method metadata scheme so
>> there's a modifier byte we can use to further distinguish send types.  We
>> can still distinguish checked sends from unchecked sends based on
>> alignment.  But we can distinguish between the different checked sends and
>> the different unchecked send types by using one map code to code for a
>> prefix.
>>
>> A map byte has a 5 bit displacement (the distance in machine code units
>> to the next map byte's target), and a 3 bit code in the most significant
>> bits.  Here's the existing assignments:
>>
>> IsSendCall := 7.
>> IsRelativeCall := 6.
>> HasBytecodePC := 5.
>> IsAbsPCReference := 4.
>> IsObjectReference := 3.
>> IsNSSendCall := NewspeakVM ifTrue: [2].
>> IsDisplacementX2N := 1.
>> IsDisplacement := 0.
>> AnnotationShift := 5.
>>
>> So if we nuke IsNSSendCall we can do e.g.
>> AnnotationExtension := 2
>> interpret the displacement of an AnnotationExtension as 0, and use the
>> 5-bit field to extend the type of the subsequent map byte. We then use
>> two map bytes for exotic sends, suddenly making lots of send types possible
>> without contortions.
>> --
>> best,
>> Eliot
>>
>
> And this is an example of how the simulator makes life so easy.  10
> minutes work to derive dynamic frequencies of all annotations including the
> displacement ones that are excluded from the extant mapFor:do:
>
> | dynamicFrequencies |
> dynamicFrequencies := Bag new.
> methodZone methodsDo:
> [:m|
> self mapFor: m
> performAllMapEntriesUntil:
> #withAnnotation:pc:evaluate:
> arg: [:annotation :pc| dynamicFrequencies add: annotation. false]].
> dynamicFrequencies sortedCounts collect:
> [:assoc|
> assoc key -> (self class annotationConstantNames at: assoc value + 1)]
>  {5867->#IsSendCall . 3139->#HasBytecodePC . 2700->#IsDisplacementX2N .
> 2307->#IsRelativeCall . 1568->#IsAbsPCReference . 1120->#IsObjectReference}
>
> Looks like IsDisplacement is surplus to requirements.
> --
> best,
> Eliot
>

and this tells us that using alignment to distinguish super sends is not
worth it; super sends are just too rare, 0.65% of all sends in one
particular run of a Squeak image:

| dynamicFrequencies nSends nSuperSends nLinked nUnlinked |
dynamicFrequencies := Bag new.
nSends := nSuperSends := nLinked := nUnlinked := 0.
methodZone methodsDo:
[:m|
self mapFor: m
performAllMapEntriesUntil:
#withAnnotation:pc:evaluate:
arg: [:annotation :mcpc| | entryPoint |
dynamicFrequencies add: annotation.
annotation >= IsSendCall ifTrue:
[entryPoint := backEnd callTargetFromReturnAddress: mcpc.
 entryPoint >= methodZoneBase
ifTrue:
[nLinked := nLinked + 1.
 self targetMethodAndSendTableFor: entryPoint into:
[:table :target|
 table == superSendTrampolines
ifTrue: [nSuperSends := nSuperSends + 1]
ifFalse: [nSends := nSends + 1]]]
ifFalse:
[nUnlinked := nUnlinked + 1.
 entryPoint >= (superSendTrampolines at: 0)
ifTrue: [nSuperSends := nSuperSends + 1]
ifFalse: [nSends := nSends + 1]]].
false]].
{ dynamicFrequencies sortedCounts collect:
[:assoc|
assoc key -> (self class annotationConstantNames at: assoc value + 1)].
nSends. nSuperSends. nLinked. nUnlinked } {{5867->#IsSendCall .
3139->#HasBytecodePC . 2700->#IsDisplacementX2N . 2307->#IsRelativeCall .
1568->#IsAbsPCReference . 1120->#IsObjectReference} . 5829 . 38 . 3065 .
2802}


-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20150403/6d327e7e/attachment-0001.htm