VM – New Object Descriptor

I drafted this new Object Descriptor. What I do here is heavy bit-fiddling that I in general will not recommend. We will be reading this from Flash that is 2-3 times slower than SRAM, but I think this will be ok since these extensions will not be used often.

E=1 means we have extensions. The first bit on the extension head is a C-Continue bit that indicate if it is more extensions – the last tag will have C=0. Each Tag have a fixed size or indicator of fixed size. I have also drafted Tag’s for extended offset in case we need larger data areas sometime and indexing of arrays.

VM – Dropping the stack

Do I actually need a separate stack in the VM?

The current draft use 2 memory areas – one for variables and one for the stack. This is influenced by legacy CPU design. But. the reality is that Plain do not allow dynamic memory so the variable area is static size and can be estimated exactly. The only dynamic memory we have is actually the stack that can fit on top of that rather than using a separate memory buffer.

This would simplify the VM quite a lot, but I need to walk through instructions and re-visit binding to C code to see if this Works out.

VM – Extended Object Descriptor

I mentioned the possibility to embed expressions into If, Call, Raise, While etc to avoid having a Plain Assembly that split into several instructions. This is a 1st draft where I truncate the Data-Type flag in the Object Descriptor and use the MSB to flag an Extended Object Descriptor.

The Extension here contain a Tag indicating that this is a math table and number of entries to follow. The math entry is 10 bytes “as is”, so I will look into ways of truncating the Object Descriptor. One idea is to drop Size and truncate Type to 4 bits. Size is actually known since all build-in types have a fixed size and I can add another Tag entry to specify non-standard extensions. I am even considering truncating Data Offset to 10 bits (1K) and have a Tag extension to address larger offsets. 1K is actually quite a lot of data for an embedded design, so a majority of instructions would work perfectly with the truncated descriptor. This would reduce the Object Descriptor from 4 to 2 bytes and math entry from 10 to 6.

The Tag also allow me to add things like table indexing and actually address data larger than 64Kb if we need to.

Truncated 16 bit Object Descriptor:

  • 1 Extension bit flag.
  • 4 Type bits. This leaves us 16 build- in data types (Bit, Byte, int16,uint16,int32,uint32,real32,real64,string, number) + 6 spare codes.
  • 1 Stack/Data bit so we can differ between stack and data offset,
  • 10 Data Offset bits to address 1Kb

The price I pay for this is extra coding in the VM (larger footprint) + we are digging into binary decoding of structures that will reduce performance a little bit. I like the idea, so lets see if it stick or if we can come up with a better one.

VM – Raise

The introduction of the 32 bit Object Descriptor bloat the instruction set, but we currently only have 12 high-level instructions left in the VM – This is Assign, Call, Decode, Encode, End, Exit, For, If, NOP, Raise, While and Switch. Just for the record – this is actual instructions, not keywords supported by the Assembler syntax.

I have to walk through the details of all of them, but the one that currently have my focus is Raise and how it will behave on the stack together with a Call..On..End sequence. Lets do a few examples and see if we can get this to work:

Example 1:

Foo MyFunc
            Raise Error
Event Error

Call MyFunc

In this case we call MyFunc that return with the event Error – which will call the default and do nothing. (1) Call create a stack entry, (2) raise re-use that stack entry and (3) End consume the stack entry.

Example 2:

Foo MyFunc
            Raise Error
Event Error

Call MyFunc
On Error
            println "Error"

This is a bit more tricky as we now override the Error event, but how will Raise know which Error to call? The answer is that the Assembler need to create an event table for the call – this is by default the one for the function, but in this case with an overridden Error event. It also means we need to modify Raise to use an enumerated event code (generated by the Assembler) to indirect index the Event body. As raise in this case call Error and println it reach End that consume the stack entry.

 Example 3:

 Foo MyFunc
            Raise Timeout
Event Timeout
            Raise Error
Event Error

Call MyFunc
On Error
            println "Error"

In this case I cascade the events – (1) we Call MyFunc creating the stack entry, (2) Raise Timeout that re-use the stack entry, (3) Raise Error that is overridden and run into End that consume the stack entry.

Example 4:

Foo MyFunc
            Raise Timeout
Event Timeout
            println "Timeout"
Event Error

Call MyFunc
On Error
            println "Error"

In this case we Raise Timeout that run into a “Event” – basically terminating with an hidden End that will consume the stack entry and jump to after Call..On..End.

I need to extend the Call instruction to include the event table + modify the Raise instruction, but that seems to be it.

VM – New Stack

The previous stack design was to store only data descriptors on the stack – not data itself. The side-effect of this is that everything becomes global data. The alternative to pass a copy also have a side effect if I pass an object + passing an auto-decided combination of data and references is not nice either. We also need to look at details on restoring stack after a function return as well as how do we return Event parameters? And all of this should happen automatically as I don’t want the developer to worry about the stack at all.

I want to keep the design with pushing and popping references – Object References this time. As the reference point to actual data we can either point to the global copy or a new, local copy depending on what we want. “Reference” is a good keyword prefix for a new variable type that only point to data.

In the same way as we used the index top for stack we use the 64kb area for stack variables. We create a separate stack index for 32 bit Object Descriptors and a separate SRAM buffer for stack temporary storage. In the real buffer table we might use 1Kb for data and 1Kb for stack carefully calculated by the Assembler.

This figure illustrate our modified Stack. As with data we create a buffer for the VM and use of this for each module. The two buffers are arranged so data is the lower part and stack the higher forming a max of 64Kb. Size of data can be calculated, size of stack need to be estimated.

The Object Index is not a real table as this is embedded into the instructions as they access parameters, but we need an actual Stack Entry Table to hold data for each call. As we make a call we add an entry to this table – as we execute End we remove the entry and free the stack back to the previous Free Stack Offset.

The only issue that is not covered is Raise. I will get back to that later – we will have a few try and fails before we get this going…

VM – Object Index

The new Object Descriptor. Notice that we now offset data rather than indexing into an array.

This illustration show how a Assign would look like with a 32 bit Object Descriptor. We don’t need a descriptor on TIX since the type will follow math rules. The fields marked yellow are those who expand from 16 bit to 32 bit. Testing a few instructions we can expect a 50% increase in instruction size if we go down this path.

This last illustration shows how Object Descriptors link into a Module SRAM Buffer that is part of a VM SRAM Buffer.

Looking at a 100 line Plain Assembly program we can estimate that we grow from 800 byte to 1200 byte if we extend the instructions with Object Descriptors. Using a 16 bit index and an additional lookup table will save ca 280 bytes, but I will only use this if Module size becomes a major issue.

VM – Objects

Implementing an Object Index to replace the current 32 bit register array can be done in at least two ways.

Firstly I need to use a SRAM buffer to hold objects rather than the current 32 bit register array, and I need to replace the 16 bit index in the Data Descriptor with a 16 bit Offset. This gives us a maximum of 64Kb data range per module, but that is more than I need. We should probably rename the Data Descriptor to Object Descriptor ?

I can now replace the 16 bit register index with a 32 bit data descriptor everywhere in the instructions, or I can use a 16 bit Object Index and implement a Object Index table. The first will use more flash, but I am a bit concerned about performance on the last one. If I use a lookup table in Flash we will be reading an instruction that will need to lookup multiple data descriptors – and reading from flash is slow. We could of cause move the table to SRAM as this is very small table (40 bytes on 10 variables).

I think I will prefer to just use 32 bit Data Descriptors on the instruction set to keep things simple, but I need to do some math over Flash/SRAM usage and think through the full impact.

VM – Call & Raise

Obsolete 21.feb.2017 – New design.

The Call & Raise instructions are identical in design, it is only the op-code that differs. I re-use the extended length option from Assign and add an array of 32 bit Data Descriptors to define the parameters.

Moving on I have several unsolved design questions with the VM:

One is the details around the stack as we enter and leave a function + the details of how we return an event. I have loose ends here I need to dig into.

The second is that parameters in a call can be expressions. My initial thought was to let the assembler split this into a sequence of Assign and a Call if required, but it is fully possible to embed the P-Code directly as a sub-table to a special “type”. The Win on this is that we move back to a 1:1 between Assembler and Instructions as we can also do this on If and While. The VM actually have 6 different If instructions that we could replace with one if we embed the expression P-Code directly.

The third issue is how to handle different data types during math. If we add a uint32 with a float32 the VM need to convert one of them meaning the VM need to know what types they are. Using the 32 bit Data Descriptor solves this, but that would bloat the instructions as every register reference now becomes 32 bits rather than 16. The alternative that I was planning was to use 8 bits extra on each register – if I go down this path I will be using more SRAM.

Another related question is if we should ditch the 32 bit register part and only use Objects? We have the objects anyway and having a generic 32 bit register array in addition complicate things. My original idea was to let the VM only use 32 bit values + it was a bit of influence from legacy Modbus/CAN – But, what if we change this to become a 64K index of objects and let even simple data values be objects … I need to think this one through and calculate on SRAM impact.

As mentioned before – work in progress –

Plain – Algebraic Expression Parser

Dealing with math it is quite handy to use a standard algebraic expression format. But, to do so we need a parser that translate the expression into a sequence of simple math instructions. In this case we expect the Assembler to “compile” the expression into P-Code that we later execute as part of the VM’s Assign instruction. The Parser is a C++ class library used by Plain Assembler. The module was actually created prior to Plain as part of a different project.

The parser logic is quite simple

  1.  You parse 1st sequence consisting of start parenthesis, value, end parenthesis and an operator. End of Expression is also an “operator” in this sence.
  2. You parse 2nd sequence.
  3. You evaluate 1st and 2nd priority. if 1-op has higher pri than 2-op, you compute 1 by generating a output table entry (P-Code).
  4. Repeat from 2.

Example 1:  3 + 4 * 5

This is the classic example to test priority as we know that 4 * 5 must be computed before 3 + … The parser will build a tree as listed below:

0 :          3 +
1 :          4 *                 // + lower pri than * so continue
2 :   5 END                  // 'END' is lowest pri

This will generate the following P Code:

T1 = 4 * 5                  
T0 = 3 + T1               

In this case we could end up with an Assign instruction with 2 P-Code table entries. I say ‘could’ because the actual parser will in this case detect that it is only constants and pre-calculate the value 20.

VM – Assign

I don’t intend to describe all instructions in detail here, but I will draft the more critical ones. Assign is one of those because it contains a small micro-VM of it’s own dealing with mathematical expressions.

The instruction format is illustrated above. It contains a standard op-code, but we now also add a rule that if Length=0x3F we fetch the real length from the 3rd entry. This is to allow larger expression tables if they are needed. The reality is that I don’t expect to see this extended format in use, but I don’t like limitations on issues like this.

The last part of the instruction is P-Code table adapted to our Plain VM. The Expression Parser have computed a list of mathematical operations that if executed in sequence top-down will provide a correct result. P1 & P2 RIX are Register IX. P1 & P2 are flags indicating if this is a Register (0 0) or a TIX ( 0 1). TIX is Temporary Index and refer to the internal, temporary stack on the Assign. TIX=0 is the same as the resulting RIX. I will dig up some old work and describe the Expression Parser next…