Common byte code sequences

Ian Piumarta piumarta at prof.inria.fr
Wed Jan 21 14:10:24 UTC 1998


Andreas,

> While looking around in the DynamicTranslators documentation category I
> noticed that you've documented a number of common byte code sequences.
> Where do these come from? Are this just "good guesses" or did you analyze
> the control flow?

They came from a combination of three sources.

Some are just "obvious".  Things like "pushInteger {add,sub,mul}" occur
all over the place.

Some were spotted just by looking through the bytecodes generated by
pieces of typical Smalltalk -- e.g. the "loopStep" opcode and those like
"push{True,False} jumpIf{False,True}" (which occur whenever you use #and:
or #or:).

Some were the result of analysing the control flow (I suspect this is
what you wanted to hear ;-).  Some unexpected ones popped out of this
analysis -- and sure enough, implementing them noticably improved the
overall performance.

> If so, how did you do this?

I modified the VM to print out the index of the opcode that it was
dispatching.  I generated (from Smalltalk) a C header file containing a
map from the opcode indices onto opcode names, and then wrote a C program
to extract and print all sequences of N opcodes that did not contain a
branch (or send or return) in the middle.  The output of this program was
fed through an appropriate combination of "sort" and "uniq" to generate
tables of the most popular sequences.

If you (or anyone else) is interested in this, I can place the raw data
file (which contains a trace of something like 730 million opcodes taken
while the VM regenerated itself from Smalltalk source), the analysis
program, a script for processing the output and some pre-generated lists
of common sequences, in alix's FTP area.

FWIW, I've appended the five most common sequences for lengths 2 to 5 for
the first 4 million opcodes in the trace.  (The time to process this
stuff goes up exponentially because of the several sorting steps
involved: processing just the first 4 million opcodes required about 10
minutes "per length" on the fastest machine to which I have access.)

Regards,

Ian

length 2
 191220 PushReceiverVariable PushTemporaryVariable
 151178 PushTemporaryVariable Send
 104733 PushReceiver Send
  70731 PushReceiverVariable Send
  61065 PushTemporaryVariable PrimPointX

length 3
  58745 PushReceiverVariable PushTemporaryVariable PrimPointX
  55108 PushReceiverVariable PushTemporaryVariable PrimPointY
  35651 StoreTemporaryVariable PushReceiverVariable PushTemporaryVariable
  28760 PushConstant PrimEquivalent LongJumpIfTrue
  28074 PushTemporaryVariable StoreReceiverVariable ReturnReceiver

length 4
  35590 StoreTemporaryVariable PushReceiverVariable PushTemporaryVariable PrimPointX
  23285 MacroMoveTempRcvr PushTemporaryVariable StoreReceiverVariable ReturnReceiver
  20445 PushTemporaryVariable PushConstant PrimEquivalent LongJumpIfTrue
  18516 PushTemporaryVariable PrimPointY PrimAdd SpecialPrimitive
  18516 PushReceiverVariable PushTemporaryVariable PrimPointY PrimAdd

length 5
  18516 StoreTemporaryVariable PushReceiverVariable PushTemporaryVariable PrimPointX PrimAdd
  18512 PushTemporaryVariable PrimPointX PrimAdd PushReceiverVariable PushTemporaryVariable
  18512 PushReceiverVariable PushTemporaryVariable PrimPointY PrimAdd SpecialPrimitive
  18512 PushReceiverVariable PushTemporaryVariable PrimPointX PrimAdd PushReceiverVariable
  18512 PrimPointX PrimAdd PushReceiverVariable PushTemporaryVariable PrimPointY





More information about the Squeak-dev mailing list