Stack machine to state machine 
Author Message
 Stack machine to state machine

Hello,

My apologies if the question is off-topic.
I need to know how can I convert stack machine program to a 'usual',
i.e. state machine. I suppose it's possible, since both of them
computationally equivalent to Turing machine.
What I have is an interpreter which has an instruction queue and a data
stack. The instruction set basically consists of arithmetic
manipulations over the data stack and conditional jump within
instruction queue.
The point of conversion is to gain speedup of original program using a
third-party optimizing compiler. Straightforward macro translator with
an explicit stack is not satisfactory, since it doesn't lefts place for
compiler's peephole optimizations.

Any tips or references will be greatly appreciated. Online sources
preferrable, as I haven't a rich university library nearby.

Regards,
  Eugene.

P.S. This is not a homework assignment.



Sat, 23 Mar 2002 03:00:00 GMT  
 Stack machine to state machine
[snip]
Quote:
> My apologies if the question is off-topic.
> I need to know how can I convert stack machine program to a 'usual',
> i.e. state machine. I suppose it's possible, since both of them
> computationally equivalent to Turing machine.
> What I have is an interpreter which has an instruction queue and a data
> stack. The instruction set basically consists of arithmetic
> manipulations over the data stack and conditional jump within
> instruction queue.

[snip]

Well, the easy way is to make every conditional jump, along with all
of the unconditional statements before it, into the instructions for
one state, with the two branches for the condition as the
possibilities for the next state.  I'm not certain about this, but
that may be the best you can do without any more specific information
about the program or problem in question...

Andru
--
--------------------------------------------------------------------------
| Andru Luvisi                 | http://libweb.sonoma.edu/                 |
| Programmer/Analyst           |   Library Resources Online              |
| Ruben Salazar Library        |-----------------------------------------|
| Sonoma State University      | http://www.belleprovence.com/                 |

--------------------------------------------------------------------------



Sat, 23 Mar 2002 03:00:00 GMT  
 Stack machine to state machine

Quote:

>I need to know how can I convert stack machine program to a 'usual',
>i.e. state machine. I suppose it's possible, since both of them
>computationally equivalent to Turing machine.

In the formal sense, neither a (single-)stack machine nor a
(finite-)state machine are Turing-complete. Nor are they equivalent,
with state machines being weaker than stack machines.

Quote:
>What I have is an interpreter which has an instruction queue and a data
>stack. The instruction set basically consists of arithmetic
>manipulations over the data stack and conditional jump within
>instruction queue.
>The point of conversion is to gain speedup of original program using a
>third-party optimizing compiler. Straightforward macro translator with
>an explicit stack is not satisfactory, since it doesn't lefts place for
>compiler's peephole optimizations.

What you seem to be after is a way of converting a stack machine to a
register machine. With a finite number of registers, this isn't
possible either, but if the stack is of limited size, it is possible.
Alternatively, you can use a mixture of registers and stack in the
translation, so you use the stack if there are not enough registers.

The simplest idea is to say that you will always keep the top N
elements in registers, where N is a constant (e.g., 4) and keep the
remainder in a run-time stack. You use the N registers as a cyclic
buffer for stack elements: You keep (at compile-time) two pointers
into this buffer, one to the first element free element and one to the
last occupied element. Initially, the buffer is empty (as the stack is
empty) which is indicated by the "last" pointer being one smaller than
the "first" pointer (modulo N). When the stack-machine pushed a
register, you instead store it in the cyclic buffer by generating code
that puts the value in the register pointed to by the "first" pointer
and incrementing the latter (modulo N). If the stack-machine pops the
stack, you just decrement the "first" pointer (modulo N). However,
this only works if pushes are done on non-full buffers and pops on
non-empty buffers.

If the buffer is full before a push (which can be seen by the "first"
and "last" pointers being equal), you must first generate code that
pushes the element at the "last" pointer onto the run-time stack and
increments the "last" pointer (modulo N). The you do as described
above.

If the buffer is empty before a pop (the "last" pointer is one smaller
than the "first" pointer (modulo N)), you just pop the run-time stack
without changing the buffer.

If you do an operation that uses the top stack element, you must first
ensure that this is in the buffer. If the buffer is non-empty, this is
the case, but otherwise you must (generate code to) pop it from the
run-time stack into the buffer. This is done by incrementing the
"last" pointer (modulo N) and (generate code for) storing the value
where it points. If, similarly, the element below the stack-top is
needed and the buffer has less than two elements, values must be
transferred from the run-time stack to the buffer (as described above)
to make it have at least 2 elements. The same generalizes to any k
elements, where k is less than or equal to N.

For example, a stack-machine ADD instruction that pops two elements
and pushes the sum of these is translated as follows (using C-style
notation):

if (first == (last+1)%N) /* buffer is empty */
  { last = (last+N-1)%N; generate("pop to register %d",last); }
if (first == (last+2)%N) /* only one element in buffer */
  { last = (last+N-1)%N; generate("pop to register %d",last); }
generate("register %d := register %d + register %d",
         (first+N-1)%N, (first+N-2)%N, (first+N-1)%N);
first = (first+N-1)%N;

This all works very well as long as there are no jumps. If there are
jumps, you might get to a case where the buffer looks different at a
jump than the code expects at the target of the jump. There are (at
least) three solutions to this:

 1) Make sure the buffer is empty before every jump by pushing buffer
    elements to the run-time stack.

 2) If the code already generated expects a different buffer than what
    you have, then first generate code that moves values between
    registers and to/from the stack so the current buffer-state is
    transformed into the expected state. Then generate the jump
    instruction.

 3) If the code already generated expects a different buffer than what
    you have, then generate a new version of the code for the branch
    target using the new buffer state. This means that there can be
    several slightly different versions of target code for the same
    piece of source code. Since there are only a finite number of
    different buffer states, it will be finite, though.

A buffer state is determined by the values of the "first and "last"
pointers. There are hence N^2 possible buffer states. Typically, there
will, however, be much less code duplication than that if strategy 3
is chosen. Still, if code size is important you should choose one of
the two first. Of these, number 1 is the simplest. It simply states
that every basic block (branch target) starts with an empty buffer. It
is, however, not very efficient as you don't exploit registers very
well. Option 2 is the most complicated as the compiler needs to be
able to convert any buffer state into any other.




Sun, 24 Mar 2002 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Help with large state machine design (62 states)

2. State Machine - State Definition Question

3. finite state machines, state cad

4. OE Backup (move from machine to machine)

5. Lisp Based Machine Code (Simulators) [was Re: Lisp Machines]

6. SIMPEL Virtual Machine (a toy machine and assembler)

7. Connection Machine-compatible fortran for other machines?

8. Reading binary file generated from 32-bit machine using 64-bit machine

9. Lisp Based Machine Code (Simulators) [was Re: Lisp Machines]

10. Nested state machines design problem

11. Musings on state machines.

12. state-machine class: solved..friend classes ?????

 

 
Powered by phpBB® Forum Software