Overview of R1 chip

R1 chip structure

Instruction Set

R1 chip runs the machine code called I-code. I-code is a form of “byte-code”, each instruction occupies one byte if it has no argument. I-code instruction is stack-based, means that instead of having general purpose registers to store data between computation, I-code use a stack, which resides in the memory to store data. Each instruction operates mainly on the stack therefore it does not require “addressing”, for example the instruction Add just takes two items from top of the stack and add them and put the result back to the stack. The table below shows the full set of I-code :

Table of I-code encoding

	0	1	2	3	4	5	6	7
0	Lit	Lval	Lvalg	Rval	Rvalg	Fetch	Set	Index
8	Jmp	Jz	Call	Func	Proc	Ret0	Ret1	Stop
16	Add	Sub	Mul	Div	Minus	Not	And	Or
24	Lt	Le	Eq	Ne	Ge	Gt	Print	Printch
32	Send	Receive	Signal	Nop	TmSend	TmRec	TmWait	Delay
40	Gettime

Memory space

The memory space of I-code contains three areas : Code segment, Data segment and Stack segment. All of which is addressable from all instructions. Code segment stores the executable code (program). Data segment stores global variables. Stack segment stores the stack, the main data structure that is used in computation. The ability to uniformly access all these areas from one addressing space is called “single address space” or “flat address space” which simplify the programming model.

I-code format

There are 4 formats : zero operand, one and two and three operands (all operands are 16 bits).

[ Ic ] Arithmetic op, Logical op, etc.

[ Ic #ref ] Literal, Lval, Rval, Jump, Wait, etc.

[ Ic #nparam #nlocal ] function call

[ Ic #pid #nparam #nlocal ] process call

Operational semantic of I-code

Notation for describing the operational semantic of I-code,
CS[i] code segment at the address i.
DS[i] data segment at the address i.
SS[i] stack segment at the address i. Both data segment and stack segment resided in the same address space and can be denoted by M[i] memory contained DS and SS, at the address i. Some operations take operand(s) from stack and leave a result on the stack. The state of stack can be described by a notation that indicates the values in the stack (before an operation – after an operation ) when the top of stack is the left most item, the “...” denotes the items that are of no interested to us.

Push(x) is defined as Sp = Sp + 1, SS[Sp] = x
x = Pop is defined as x = SS[Sp], Sp = Sp - 1

Literal
push the constant into the stack
[Literal #n ] push( n ) ( ... – n )

Variables access

Lvalue, push the address of that variable. If the variable is global its reference is its address. If the variable is global, its address is the address of that variable in the current frame. Rvalue, push the value of that variable.

[Lvalueg #ref ] push( ref ) ( ... – ref )

[Lvalue #i ] push( Fp-i ) ( ... – ads )

[Rvalueg #ref ] push( DS[ref] ) ( ... – value )

[Rvalue #i ] push( SS[Fp-i] ) ( ... – value )

Fetch, get the value of the variable which its address is on the stack. Set, store a value to an address, both value and address are on the stack. Index, which is used to access an array variable, calculates the address of that element of the array and leaves the result on the stack.

[Fetch] push( M[ pop ] ) (ads – value)

[Set] M[ pop1 ] = pop2 (ads, value – ...)

[Index] push( base_ads + index ) ( base, index – ads )

Transfer of control

Jmp, Jz, jump to a location, without and with condition (Jz is jump if the top of stack is zero).

[Jmp #ads ] Ip = ads

[Jz #ads ] if pop = 0 then Ip = ads ( bool – ...)

Call, push the return value and jump to that address to continue with the execution of a subprogram (a function or a process). For a function, a new stack frame is created, the parameters are passed (by overlap stack frame) and the current state of computation (of the caller) is saved, the execution is continue with the code of that function. For a process, a new process descriptor is created, its state of computation is initialised and the process is awaked. Stop, terminate a process by removing its process descriptor from the ready list. (discussion about process is in the next section). Return has two varieties : Ret0, and Ret1. Both instructions remove the current stack frame, restore the previous state of computation (which is stored in the current frame). For Ret1, a value will be returned to the caller’s stack.

[Call #ads ] push( Ip ), Ip = ads ( ... – return_ads )

[Func #nparam #nlocal ] save state, new stack frame, pass parameters

[Proc #pid #npara #nlocal] new process descriptor, initialise state, awake

[Ret0] remove stack frame, restore state

[Ret1] remove stack frame, restore state, return a value

[Stop] terminate the process

(Note that nparam + nlocal = total number of local variables of that function or process)

Arithmetic and Logic operators

Binary arithmetic operators (Aop) are Add, Sub, Mul, Div. They will take 2 operands from the stack and return the result. These are arithmetic on integer. Unary operators (Uop) are Minus and Not, will take one operand from the stack and return the result. Binary logic operators (Lop) are LT, LE, EQ, NE, GE, GT, And, Or. They are similar to arithmetic operators except the result is boolean.

[Aop] push ( pop1 Aop pop2 ) ( a, b – result as integer )

[Lop] push ( pop1 Lop pop2 ) ( a, b– result as boolean )

[Uop] push ( Uop pop ) ( a – result )

Output

Print, take an operand from stack and print it out as an integer. Printch is similar and print as a character.

[Print ] print an integer ( a – ... )

[Printch ] print a character ( c – ... )