[pypy-dev] Re: Greetings

[Bengt Richter]

At 15:49 2003-07-10 +0200, you (Armin Rigo) wrote:
>Hello Jonathan,
>
>On Wed, Jul 09, 2003 at 03:40:21PM -0500, Jonathan David Riehl wrote:
>> I actually didn't bother to schedule the DAG's (I didn't know anything
>> about that topic at the time) and ended up emitting the basic blocks by
>> simply inlining calls to the Python API.
>
>This looks similar to what we want to do here, and have started working on in 
>the annotation object space. We build information about the code by 
>interpreting it somehow. What is nice with having a whole interpreter already 
>here in the first place is that we can reuse it for this analysis. Constant 
>folding is indeed completely trivial.
>
>> thing about the representation was it's functional representation
>> (iterative loops would translate to recursive functions), since I still
>> don't know much about elimination of recursion on the back end.
>
>This too is the point here. The analysis essentially produces a functional
>representation. It is probably a good thing to have. Modern compilers tend to
>use this representation too (they call it SSA, Single-Step Assignment), which
>is that disregarding a source code variable name all assignments essentially
>create a new variable. The remaining question is how you close loops, i.e. how

Your SSA description makes me wonder again about a question that's occurred to
me in the past: If all program values were stored-to and retrieved-from fifo pipes,
what would be the minimum number of pipes needed to implement a given program,
and what would be their various minimum capacities? E.g., the rhs of an assignment
in a loop generates a sequence of fifo reads (maybe from different fifos or the same)
and the lhs (maybe also some reads here if target expression) a write (or possibly writes).

IIRC I've used a limited version of this in hand-optimizing PDP-11/45 (ok, some time ago ;-)
assembler in a loop, so as to have all [reg]++ addressing modulo the memory fifo spaces.
(IIRC some values were pointers for indirect [reg] access elsewhere, so it wasn't a truly
pure piped variable-value thing). Hm, need to think how this affects modern CPU cache logic
though...OTOH, sequential access is good for interleaved memory. Hm, wonder if a limited
set of fast hardware fifos could do any good, or how big a set you'd need...

>the new variable created by assignment inside the loop should be identified
>with the old variable of the same name when we jump back. At this point using
>recursive functions is only one solution; if you are targeting a low-level
>language (like C with gotos) all you need to do is copy values back into the
>original variables (i.e. merge the end-of-loop state with the start-of-loop
>state), and jump back.
IIRC, I wound up with a "pipe" ready to be emptied, so I didn't need to "copy values back."
(I may also have arranged it so the pipe length was more than the size a useful struct
(pre-c assembler offsets equiv) and I was also guaranteed that a final "pipe" read access
address was the base address for a non-wrapped contiguous image of the struct too.
No holds barred in those days ;-) Don't know if there's anything useful to you in the above,
but I thought I'd share the reminiscence ;-)

>As we plan to target Pyrex first we will need to think about this, as Pyrex
>has neither gotos nor good (tail-end) recursion. If someone comes up with an
>algorithm to translate an arbitrary bunch of code with gotos back into nested
>ifs and while loops he's most welcome :-)

I guess there's always a state machine that can implement arbitrary spaghetti.
Is that what you have in mind?

Regards,
Bengt Richter