PIC details

Jecel Assumpcao Jr writes:
 > I am interested in the various efforts to add Polymorphic Inline Caches
 > to Squeak, like in
 >
 > > slides - http://www.iam.unibe.ch/~denker/talks/07ICOOLPS/07PICsICOOOLPS.pdf
 >
 > > paper - http://www.hirschfeld.org/misc/media/HauptHirschfeldDenker_2007_TypeFeedbackForBytecodeInterpreters.pdf
 >
 > For this design they just replace the pointer to the symbol in the
 > method's literal frame with a pointer to an object which then points to
 > that symbol and which also adds the needed information (class / compiled
 > method pairs).
 >
 > I plan to browse the Exupery sources to see what its PICs are like, but
 > for now I just took a quick look at the various presentations that are
 > available and saw a thread on this list from October 2008. My impression
 > so far is that PICs are short code fragments with pointers to classes
 > and which are treated mostly like native methods.
 >
 > If there are more details anywhere, it would be very helpful.
 > -- Jecel

Exupery's PICs are still very simple. They are a short sequence of
null instructions that are replaced with cmp reg class, je newMethod
sequences. The PICs are made of two parts a control block with a
little data describing the PIC and a single slot to record any
interpreted classes. The profiler doesn't see primitives so the
PIC records interpreted receivers so primitives from interpreted
methods can be inlined.

The PICs are only used for classes in old space. On a full GC they
are all cleared and set back to all NULLs.

The image can inspect them to see what classes they've seen. The only
information stored is that the class has been seen. The PICs currently
have room for three receivers, if they're full they overwrite the
oldest entry.

The code to populate the PIC is in exuperyPopulatePic:with:receiver:
which is called by exuperySetup:Message:Send:

Here's the send code sequence:


(block 6
 ....
 (mov (address block240) (8 ecx))
 (mov 7 (12 ecx))
 (mov eax (32 ecx))
 (mov ebx (36 ecx))
 (bitTest 0 eax)
 (jnc block241)
 (mov #(#specialObjectsOop) eax)
 (mov (24 eax) eax)
)

(block243
 (mov (picEntry -1313050144) ecx)
 (add 64 esp)
 (pop edi)
 (pop esi)
 (pop ebx)
 (mov ebp esp)
 (pop ebp)
 (pic eax)
 (push ecx)
 (mov 1 eax)
 (push eax)
 (push edx)
 (mov #exuperySetup:Message:Send: eax)
 (call eax)
 (mov esp ebx)
 (add 12 ebx)
 (mov ebx esp)
 (cmp 0 eax)
 (jz block239)
 (jmp eax)
)

(block239
 (mov 1 eax)
 (ret eax)
)

(block241
 (mov (eax) ebx)
 (sar 12 ebx)
 (and 31 ebx)
 (mov 0 ecx)
 (cmp ebx ecx)
 (je block242)
 (mov #(#specialObjectsOop) eax)
 (sub 1 ebx)
 (sal 2 ebx)
 (mov 4 ecx)
 (add ebx ecx)
 (add (116 eax) ecx)
 (mov (ecx) eax)
 (jmp block243)
)

(block242
 (sub 4 eax)
 (mov (eax) eax)
 (and 4294967292 eax)
 (jmp block243)
)

In block 6 first the return address is saved into the context (stored
in ecx here). Then the stack height is saved, it's tracked at compile
time, then the arguments including the receiver are saved. Finally we
check if the receiver is a SmallInteger, if it is then we load the
class SmallInteger from the special objects array.

Block 243 loads the picEntry, the control block for the PIC into ecx
so that we can store it and the receiver if we fall through the PIC.
It then pops out of the C stack enters the PIC, if the PIC falls
through then it re-establishes the C stack frame, calls
exuperySetup:Message:Send: which looks up the method using the same
logic as the interpreter including using the interpreters message
cache. The rest of the block and block 239 either returns to native
code via "jmp eax" or returns back into the interpreter.

Blocks 241 and 242 are decoding the receivers class. Block 241 is
required because of compact classes.

The PIC entries look like:
  (cmp eax classAddress)
  (je newMethod)

Yes there's more than a few inefficiences here that could be removed
with a bit of tuning.

Bryce
_______________________________________________
Exupery mailing list
[hidden email]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/exupery