[pypy-dev] jit-targets

[Hakan Ardo]

Hi,
the idea behind the jit-targets branch is to generalize the concept of
unrolling into something that makes sens for bridges aswell. Below I
try to describe the goals of this intention. The jit-targets branch
will be a first step towards this goal.

First, we need a new way to model traces. A trace now consists of
several parts separated by a new ResOperation called LABEL. Labels are
inserted into the trace at strategic places (different startegies
could be inverstigated). The label has a TargetToken descr that
describes the place at which it is inserted. It includes

  * A list of all live variables (the label arguments)
  * A VirtualState describing the live virtuals
  * A short preamble that can be inlined to jump to the label

A JUMP ResOperation now has a TargetToken as a descr and it will
always jump to the label with the same TargetToken. Such a jump is
only legal if the VirtualState at the jump matches the VirtualState of
the TargetToken and the short preamble has been inlined. Each
JitCellToken will contain a list of TargeTokens that corresponds to
the same greenkey (but with different VirtualStates).

When we produce a new trace, we will trace until we discover a
JitCell with a JitCellToken. The VirtualState at the end of the trace
is comapred to the VirtualState of all the TargetTokens listed. If one
of them matches, it's short preamble is inlined to produce a jump to
it. If none matches we insert a label into the trace and continue
tracing. To handle traces that loop back on themselfs we make
sure that a label is inserted at the merge point.

For loops this will produce the same effect as unrolling, but with
twice as much tracing as both the first and second iterations are
traced. We can however detect such loops and inline the produced trace
instead of continue traceing without chaning this new concept. Also it
will make it straight forward to unroll into more than 2 iterations if
that would make sens.

The optimizeopt optimizer will be passed trace parts that can start
and/or end with a label, but there with be no intermediate labels. If
the trace-part ends with a label, the state of the optimizer that
would previously be passed from the preamble to the loop will now
instead be saved on this label. If the trace-part starts with a label
the corresponding state will be imported from it. If a box produced in
one trace-part is reused in the following trace-part it will be added
as an argument to the intermediate label. Also resops to produce the
box will be added to the short preamble of that label. The logic here
on how to import boxes from previous trace-parts is the same as what
was previous used to import boxes from the preamble into the loop.

The jit-targets branch implementes the framework described above. To
not make it too big a leap from where we are today it then uses a
policy of where to insert labels and when to force virtuals that will
make it produce as similiar results as possible to what we have
today. That becomes a somewhat complex policy. I do however believe
that simpler policies (such as what's hinted about above) will be even
more effective here. That would allow for things to be simplified and
cleaned up a bit. Also, experimenting with inserting labels at say the
first jit_merge_point discovered when tracing a bridge would allow us
to join the controllflows of a loop with lots of paths back together.
That will however probably be the topic of future branches...


-- 
Håkan Ardö