Pynto Design
============

This document is intended to describe the algorithms used for various parts
of the Pynto JIT.  The data structures and high level design are described
in design.txt.  See walkthrough.txt for a more concrete example of the
algorithms from here in use.

Format
======

This is a ReST document, intended to be processed with the Restructured 
Text tool.  I chose this because it is the least intrusive form of markup
I could find.

Table of Contents
=================

1. `Converting from Python Byte Code to our Internal IR`_

Converting from Python Byte Code to our Internal IR
===================================================

The basic idea here is to walk down the byte codes using a simulated stack
to identify which symbols are being read and written.  Temporaries are
generated as needed.  Since the Pynto IR uses non-stack based instructions,
this kind of unwinding is necessary.

The stack is simulated using a list.  Each entry on the list is a symbol.

The complete list of byte codes and a quick description of what they do can
be found in the standard Python module dis's documentation.  That documentation
breaks the opcodes in several useful categories; I will describe how
each opcode is implemented in terms of those categories.

General: These include things like POP_TOP, and ROT_TWO.  These are simple 
stack manipulations that do not generate any instructions in and of themselves.

Unary operations: The top item is removed from the stack.  An appropriate
instruction is generated to perform the opcode required; this instruction will
have one input (the top symbol from the stack) and will create an output
(compiler temporary) which is pushed onto the stack.  Examples of these
kind of operations are "NOT" and "INVERT".

Binary operations and slices: much like unary, but with two or more inputs 
drawn from the stack.

In-place operations: these are a little trickier.  They are like binary 
operations, except that the output is not a compiler temporary, but the input
that we pulled from the stack.  Note that it must be a variable.

Instructions: most of the other opcodes simply pull items from the stack
and do not generate a result.

Optimizations
-------------

As described this would get us pretty plain-vanilla 3-operand form.
In the interest of speed, we can do some transformations on the code as
we generate the instructions.  For example, simple constant propagation
can be done by avoiding generating instructions if the operands to the
instruction are all constants, and instead just pushing the constant result.