Actions

Difference between revisions of "Design of sxgo"

From Just in Time

 
(55 intermediate revisions by the same user not shown)
Line 1: Line 1:
This page describes the main design ideas behind [[sxgo]]. The implementation of this microcontroller emulator revolves around a few main ideas:
+
[[Sxgo]] constists of a core emulator library, a graphical UI and, alternatively, a set of Python bindings. This page describes the design of the core emulator. The implementation of this emulator revolves around a few main ideas:
* separation of instruction decoder and instruction implementation
+
 
 +
* a class that emulates the state of an SX, with member functions for each SX instruction.
 
* a meta-programmed list of instructions
 
* a meta-programmed list of instructions
* using metaprogramming to create a fast instruction decoder
+
* using meta programming to create a binary decision tree of those instructions for use in an instruction decoder.
* precompilation of instructions into 'function pointers'. Actually these would also contain bound arguments (in a similar way to boost.bind).
+
* precompilation of instructions into 'function pointers'.  
  
 
I presume that the reader is familiar with the C++ programming language. Note that sxgo makes use of [http://en.wikipedia.org/wiki/Template_metaprogramming Template metaprogramming] wherever suitable. Readers that are not familiar with MP may want to look through some of the examples in the wikipedia link...
 
I presume that the reader is familiar with the C++ programming language. Note that sxgo makes use of [http://en.wikipedia.org/wiki/Template_metaprogramming Template metaprogramming] wherever suitable. Readers that are not familiar with MP may want to look through some of the examples in the wikipedia link...
Line 9: Line 10:
 
==Instruction Implementation==
 
==Instruction Implementation==
 
===implementation of the SX emulator===
 
===implementation of the SX emulator===
The idea is to have one class that consists of an SX 'state' (ram, rom, special registers, program counter) and that implements the instruction set. See the snippet (of file ''sx_controller.hpp'')below:
+
The idea is to have one class that consists of an SX 'state' (ram, rom, special registers, program counter) and that implements the instruction set. See the snippet (of file [https://github.com/DannyHavenith/sxsim/blob/master/sxsim/sx_controller.hpp sx_controller.hpp])below:
  
 
<source lang="cpp">
 
<source lang="cpp">
 +
 +
struct clr_fr      { /*...*/ };
 +
struct clr_w        { /*...*/ };
 +
struct mov_w_not_fr { /*...*/ };
 +
// etc...
 +
 
struct sx_controller_impl  
 
struct sx_controller_impl  
 
{
 
{
Line 36: Line 43:
 
</source>
 
</source>
  
As you can see, most instructions become very simple member functions and their implementation is quite readable. You may notice one oddity in the implementation of the instructions: instead of having member functions called ''clr_frw'' or ''clr_w'', the sx controller implementation has a set of overloads of a single member function called ''execute'' that takes some--otherwise ignored--first argument of some type with names like ''clr_frw''. The reason for this is best explained after some explanation of the implementation of the [[#Instruction set|instruction set]] and the [[#Instruction decoder|instruction decoder]]. It has all to do with the fact that the instruction set is defined independently of it's implementaton and in fact there is more than one implementation of the instructions.
+
In C++ terms, this means that an implementation of the SX instruction set needs to ''model'' the [http://en.wikipedia.org/wiki/Concepts_%28C%2B%2B%29 Concept] of SXImplementation. Where (informally) the concept of SXImplementation is any class that implements one of the following member functions for each of the tags that are in the SX instruction set.
 +
<source lang="cpp">
 +
void execute( const tag &);
 +
void execute( const tag &, int arg);
 +
void execute( const tag &, int arg, int arg);
 +
</source>
 +
This concept is important, because as we shall see there are more models of this concept ('implementations of this interface') than just the sx emulator itself. We shall see that any class that models this concept can be used as the target of an instruction decoder, so that we can feed SX instruction words to a decoder and the decoder will call the correct overload of the ''execute'' function for such a class.
 +
 
 
===Alternative instruction implementations===
 
===Alternative instruction implementations===
 
Once we've decided the interface for SX instruction implementations, it becomes relatively easy to make different implementations. Sxgo defines several implementations, such as one implementation that does nothing more than return a string representation of the instructions (a disassembler), or one that 'compiles' instructions into a representation that will execute faster (a precompiler). All of these implementations can be fed through a single instruction decoder implementation.
 
Once we've decided the interface for SX instruction implementations, it becomes relatively easy to make different implementations. Sxgo defines several implementations, such as one implementation that does nothing more than return a string representation of the instructions (a disassembler), or one that 'compiles' instructions into a representation that will execute faster (a precompiler). All of these implementations can be fed through a single instruction decoder implementation.
Line 46: Line 60:
 
As could be seen in the previous Section, the implementation of the sx instruction set was all in terms of an ''execute'' method that is overloaded for several types, each type representing one instruction. Defining the instruction set becomes therefore a matter of defining a set of types, one for each instruction. These are the ''instruction tag types'' and the execute method is similar to  a technique called ''[http://www.boost.org/community/generic_programming.html#tag_dispatching tag dispatching]''.
 
As could be seen in the previous Section, the implementation of the sx instruction set was all in terms of an ''execute'' method that is overloaded for several types, each type representing one instruction. Defining the instruction set becomes therefore a matter of defining a set of types, one for each instruction. These are the ''instruction tag types'' and the execute method is similar to  a technique called ''[http://www.boost.org/community/generic_programming.html#tag_dispatching tag dispatching]''.
  
In order to facilitate instruction decoding, the instruction types will be enhanced with information about their bit-patterns. This is in contrast with normal tag dispatching, where the tag types are completely empty types. The instruction list for sxgo can be found in ''sx_instruction_list.hpp'' and has the following form:
+
In order to facilitate instruction decoding, the instruction types will be enhanced with information about their bit-patterns. This is in contrast with normal tag dispatching, where the tag types are completely empty types. The instruction list for sxgo can be found in [https://github.com/DannyHavenith/sxsim/blob/master/sxsim/sx_instruction_list.hpp sx_instruction_list.hpp] and has the following form:
 
<source lang="cpp">
 
<source lang="cpp">
 
// ...
 
// ...
Line 87: Line 101:
  
 
==Instruction decoder==
 
==Instruction decoder==
As stated before, it is the task of the instruction decoder to take an instruction word (a number) and based on the value of that word, call and ''execute'' function with the right parameters. SX instructions are all 12 bits, and those bits are typically divided in a number of opcode bits (the instruction) and some operand bits (the arguments). The number of opcode bits is not the same for every instruction. The opcode for "''jmp''" for instance has only three bits (and they have the values '''''101'''''), the other nine bits are reserved for the 9-bit address to jump to.
+
An instruction decoder is essentially a function that takes an instruction word and a reference to an SXImplementation and that will determine from the instruction word which ''execute'' overload needs to be called and subsequently call that member function with the right arguments. In sxgo, this function is a static member function of a template class:
 +
 
 +
<source lang="cpp">
 +
    template<typename instruction_list, typename implementation_type>
 +
    struct instruction_decoder {
 +
        // ...
 +
        static void feed( instruction_type word, implementation_type &implementation);
 +
        // ...
 +
    };
 +
</source>
 +
 
 +
SX instructions are all 12 bits, and those bits are typically divided in a number of opcode bits (the instruction) and some operand bits (the arguments). The number of opcode bits is not the same for every instruction. The opcode for "''jmp''" for instance has only three bits (and they have the values '''''101'''''), the other nine bits are reserved for the 9-bit address to jump to.
  
 
There are several ways to go about implementing an instruction decoder. One could group all instructions according to opcode size and start checking for the shortest opcodes first, and then, if no opcode was recognized start looking in the next group of opcodes, etc. This would look somewhat like this:
 
There are several ways to go about implementing an instruction decoder. One could group all instructions according to opcode size and start checking for the shortest opcodes first, and then, if no opcode was recognized start looking in the next group of opcodes, etc. This would look somewhat like this:
 
<source lang="cpp">
 
<source lang="cpp">
void decode( int instruction, implementation &impl)
+
void feed( instruction_type instruction, implementation_type &impl)
 
{
 
{
 
     switch (instruction & 0xf00) // look at top 4 bits
 
     switch (instruction & 0xf00) // look at top 4 bits
Line 109: Line 134:
  
 
===Decision tree===
 
===Decision tree===
However, since I explicitly do not want to write the decoder by hand and case statements like the above one are hard to produce with template metaprogramming, I've chosen a slightly less efficient, but otherwise very similar approach: a binary decision tree. The implementation resembles the one above. Instead of creating nested case-statements, the binary decision tree will test one bit at a time and as soon as it reached a decision, it will call the right member function.
+
However, since I explicitly do not want to write the decoder by hand and case statements like the above one are hard to produce with template metaprogramming, I've chosen a slightly less efficient, but otherwise very similar approach: a binary decision tree. The implementation resembles the one above. Instead of creating nested case-statements, nested if-statements will test one bit at a time and as soon as a decision can be reached, the right member function will be called.
  
For example, suppose we have a simple microcontroller that uses three-bit instruction words and that nows only three instructions:
+
For example, suppose we have a simple microcontroller that uses three-bit instruction words and that knows only three instructions:
 
{| border="1"
 
{| border="1"
 
|-
 
|-
Line 129: Line 154:
 
Then a decision tree in the form of if-statements would look like this:
 
Then a decision tree in the form of if-statements would look like this:
 
<source lang="cpp">
 
<source lang="cpp">
void decode( int instruction, implementation &imp)
+
void feed( instruction_type instruction, implementation_type &imp)
 
{
 
{
 
     if (instruction & 4) // test bit 2
 
     if (instruction & 4) // test bit 2
Line 155: Line 180:
 
The algorithm recursively splits up the instruction set and works as follows:
 
The algorithm recursively splits up the instruction set and works as follows:
 
# start decoding at bit number ''d'' (discriminator) = 11 (the most significant bit) and the full instruction set
 
# start decoding at bit number ''d'' (discriminator) = 11 (the most significant bit) and the full instruction set
# for a given bit number, ''d'', partition the instruction set into those instructions that have a '1' at position ''d'', and those that have a '0'. This is done in ''instruction_decoder.hpp'' in the following lines:
+
# for a given bit number, ''d'', partition the instruction set into those instructions that have a '1' at position ''d'', and those that have a '0'. This is done in [https://github.com/DannyHavenith/sxsim/blob/master/sxsim/instruction_decoder.hpp instruction_decoder.hpp] in the following lines:
 
<source lang="cpp">
 
<source lang="cpp">
 
     // split the instructions into two sets: the ones that have a zero at bit 'discriminating_bit' and the
 
     // split the instructions into two sets: the ones that have a zero at bit 'discriminating_bit' and the
Line 167: Line 192:
 
<li> The recursion ends when the instruction set contains only one instruction, we don't have to examine any more bits to determine which instruction to call. For such an instruction set, the algorithm will return a ''call_node''.
 
<li> The recursion ends when the instruction set contains only one instruction, we don't have to examine any more bits to determine which instruction to call. For such an instruction set, the algorithm will return a ''call_node''.
 
</ol>
 
</ol>
For the simple example given previously, this creates a datastructure that looks like the following:
+
For the simple three-instruction microcontroller of the previous example, this creates a datastructure that looks like the following:
 
<source lang="cpp">
 
<source lang="cpp">
 
   decide_node< 2, decide_node< 1, call_node<reset>, call_node<set> >, call_node< store> >;
 
   decide_node< 2, decide_node< 1, call_node<reset>, call_node<set> >, call_node< store> >;
 
</source>
 
</source>
 +
[[File:Sx instruction decision tree.png|400px|right|thumb|link=Sx instruction decision tree|Decision tree for the SX instruction decoder, click for larger image]]
  
===From meta program to actual function calls===
+
So, after all of this, the instruction decoder has a single typedef, ''instruction_tree'' that defines a decision tree type that would look pretty much like the one above. Only for the full SX instruction set, the tree contains 53 instructions--and one BREAKPOINT instruction that I added myself--as. The typedef can be found near the bottom of file ''instruction_decoder.hpp'' and looks like this:
So, after all of this, the instruction decoder has a single typedef, ''instruction_tree'' that defines a decision tree type that would look pretty much like the one above. Only for the full SX instruction set, the tree contains 53 instructions. This typedef can be found near the bottom of file ''instruction_decoder.hpp'' and looks like this:
 
 
 
 
<source lang="cpp">
 
<source lang="cpp">
typedef typename make_tree< typename instruction_list::instructions, 11, 0>::type instruction_tree;
+
typedef typename make_tree<  
 +
typename instruction_list::instructions,  
 +
11,  
 +
0 >::type instruction_tree;
 
</source>
 
</source>
  
Once we have such a tree, decoding an instruction becomes reasonably easy, we only need a function, ''decode_and_call'' that takes a ''decide_node'', examines the bit at the position mentioned in that decide_node, and delegates further decoding to either the left or the right branch of the tree, depending of the value of the examined bit:
+
The picture on the right shows a graphical representation of the SX instruction tree. It shows for instance that an instruction that starts with '101' (has '101' as the left-most digits) is a jmp-instruction (follow the tree from left to right along the path '1'->'0'->'1'). If the decoder encounters the pattern '100' it still needs to examine an extra bit to determine whether it is dealing with a ''call'' or a ''retw'' instruction.
 +
 
 +
===From meta program to actual function calls===
 +
Once we have such a tree, decoding an instruction becomes reasonably easy, we only need a function template, ''decode_and_call'' that takes a ''decide_node'' instance, examines the bit at the position mentioned in that decide_node, and delegates further decoding to either the left or the right branch of the tree, depending of the value of the examined bit:
  
 
<source lang="cpp">
 
<source lang="cpp">
Line 203: Line 233:
 
}
 
}
 
</source>
 
</source>
Of course there is an overload to end the recursion when a ''call_node'' is reached. This overload will finally call a member function that is supposed to imlement the instruction:
+
Of course there is an overload to end the recursion when a ''call_node'' is reached. This overload will finally call a member function that is supposed to implement the instruction:
 
<source lang="cpp">
 
<source lang="cpp">
 
//
 
//
Line 217: Line 247:
 
}
 
}
 
</source>
 
</source>
 +
An optimizing compiler will inline most of these function calls, resulting in one big function, comprised of many if-statements.
 +
 +
==Precompilation==
 +
The emulator spends a considerable amount of time in figuring out what instruction to execute, given the instruction word. It does this every time an instruction word at a given ROM location is executed, even though that instruction word will never change! It does make sense to try to do the instruction decoding once for every rom location before running the program.
 +
 +
Sxgos precompilation feature does just that: when a new rom is loaded, the emulator precompiles every instruction and puts the precompiled instruction in a shadow rom. The original rom contents are preserved for instructions like ''iread'' to do their work. Then, when executing a program, instructions are fetched from the precompiled shadow rom and executed.
 +
 +
Due to the generic way the instruction decoder was implemented, we shall see that this can be implemented with just a few hundred lines of code (approximately 300 LOC to be precise).
 +
 +
The shadow rom is filled with precompiled instructions and this is what one such compiled instruction looks like:
 +
<source lang="cpp">
 +
template< typename implementation>
 +
struct compiled_instruction
 +
{
 +
    // typedef for the function interface of the 'precompiled' functions.
 +
    typedef void (function_type)( unsigned short, unsigned short, implementation *);
 +
 +
compiled_instruction()
 +
:f(0),a1(0), a2(0)
 +
{
 +
}
 +
 +
explicit compiled_instruction( function_type *interface_, unsigned short arg1 = 0, unsigned short arg2 = 0)
 +
:f(interface_),a1(arg1), a2( arg2)
 +
{
 +
}
 +
 +
void execute( implementation *imp) const
 +
{
 +
f( a1, a2, imp);
 +
}
 +
 +
    bool points_to( function_type *comp) const
 +
    {
 +
        return f == comp;
 +
    }
 +
 +
private:
 +
function_type *f;
 +
unsigned short a1;
 +
unsigned short a2;
 +
};
 +
 +
</source>
 +
As you can see by looking at the data members of this struct, an instruction is nothing more than a pointer to a function and two instruction arguments (the operands). Executing an instruction is nothing more than invoking the function pointer with the two stored arguments, ''a1'' and ''a2'' and a pointer to an ''implementation'' of the sx instruction set. The function ''f'' will then take care that the right member function is called on the implementation object.
 +
 +
At this point, you can probably imagine that there are function implementations for every instruction in the SX instruction set. Having to write those functions for every instruction would be quite cumbersome. Luckily, we can employ some template trickery to significantly limit the amount of work (as always). Sxgo implements the functions by defining only three template functions: one for nullary instructions (having no arguments), one for instructions with one argument and one for instructions with two arguments. These functions are implemented as static member functions of a template class. Below, you can see the implementation for instructions with one argument. This implementation will ignore the second argument call and pass the first argument to an implementation of an SX emulator.
 +
 +
The actual instruction that this object represents is determined by the ''tag'' template argument.
 +
 +
<source lang="cpp">
 +
template< typename implementation, typename tag>
 +
struct ins1
 +
{
 +
static void execute( unsigned short arg1, unsigned short, implementation *imp)
 +
{
 +
imp->execute( tag(), arg1);
 +
}
 +
};
 +
</source>
 +
 +
Note now, that the following pointer declaration:
 +
 +
<source lang="cpp">
 +
    &ins1<sx_emulator, clr_fr>::execute;
 +
</source>
 +
 +
is a pointer to a free function that takes two integer arguments and a pointer to an instance of the sx_emulator class, and that will call the ''clr_fr'' overload of the member function ''execute'' on the sx_emulator, with the first integer argument. Also note that this function pointer is of exactly the right type to be stored in the ''f'' data member of the ''compiled_instruction'' class...
 +
 +
Now that we have the ''compiled_instruction'' and the functions that these compiled instructions point to defined, it's time to show the full code of the compiler. Warning: don't blink, thi