Pendulum Instruction Set Architecture

Pendulum Instruction Set Architecture (PISA) is a reversible instruction set architecture. It resembles a cross between standard RISC and PDP-8 with modifications to support reversibility.
== Introduction ==
This section quotes from [1] (Vieri95).
* Memory access is always an exchange. To copy a value, ensure that one register is clear (by exchanging it with an empty memory location if necessary) and add the other register to it in copy <- copy + original where copy is originally clear.
* Control flow operations must appear in identical pairs.
== Example ==
Fibonacci example copied from [1] (Vieri95).
 main: start ; Compute Nth Fibonacci number
 
 addi $1 1 ; $0=0, $1=1, base case
 addi $2 18 ; hold N, loop counter
 neg $2 ; shorthand for (xori $2 0x1ff) + 1
 addi $2 1 ; setup $2 for loop count
 addi $3 bottom ; loop target is top; swapped with bottom
 addi $4 t1 ; entry point
 addi $5 exit ; exit address
 call: bez $4 $7 ; call fib routine
 
 rbez $5 $7 ; return from rcall
 addi $5 -1
 rexit: bez $4 $7
 
 top: bltz $3 $2 ; paired loop branch, could be J
 t1: bez $4 $7
 addi $7 1
 add $0 $1
 xor $0 $1 ; swap $0, $1
 xor $1 $0
 xor $0 $1
 addi $2 1 ; increment counter
 addi $3 -10 ; correct for exchange
 b1: bez $5 $2 ; exit condition
 bottom: bltz $3 $2 ; loop until done
 
 exit: bez $5 $2 ; exit point. top and bottom could
 ; have an unconditional jump
 ;;; Copy output and call the fib generator in reverse
 add $6 $1 ; Result to $6
 addi $4 3 ; $4 points to call, adjust to rexit
 rcall: rbez $5 $2 ; call backwards; goto b1
 bez $5 $7 ; return from rcall
 ;; reclaim other space
 ;; we know $0=0, $1=1, $2=-17, $3=bottom,
 ;; $4=t1, $5=call+1, $6=fib(18), $7=0
 ;; clear out those values
 addi $1 -1
 addi $2 17
 addi $3 -22
 addi $4 -13
 addi $5 -9
 
 end: finish
== Instructions ==
===== Add =====
Format: ADD rsd, rt
ADD 	rsd 	rsd 	rt 	0
01001 	 	 	 	00 0000
5 bits	3 bits	3 bits	3 bits	6 bits
Description: The contents of register rsd and register rt are added to form a 12-bit result. The result is placed in register rsd.
Operation: GPR[rsd] <- GPR[rsd] + GPR[rt]
===== Add Immediate =====
Format: ADDI rsd, immediate
ADDI 	rsd 	rsd 	immediate
00001 	 	 	
5 bits	3 bits	3 bits	9 bits
Description: The 9-bit immediate is sign extended and added to the contents of register rsd. The result is placed in register rsd.
Operation: GPR[rsd] <- (immediate_8)^3 || immediate_{8..0}
===== And Immediate =====
Format: ANDIX rsd, rs, immediate
ANDIX 	rd 	rd 	immediate
10000 	 	 	
5 bits	3 bits	3 bits	9 bits
Description: The 9-bit immediate is sign extended and combined with the contents of register rs in a bit-wise logical AND operation. The result is combined in a logical XOR with the contents of register rd and is placed in register rd.
Operation: GPR[rd] <- (GPR[rs] and (immediate_8)^3 || immediate_{8..0}) xor GPR[rd]
===== And-Xor =====
Format: ANDX rd, rs, rt
ADD 	rd 	rs 	rt 	0
11000 	 	 	 	00 0000
5 bits	3 bits	3 bits	3 bits	6 bits
Description: The contents of register rs and register rt are combined in a bit-wise logical AND operation. The result is combined in a logical XOR with the contents of register rd and is placed in register rd.
Operation: GPR[rsd] <- (GPR[rs] and GPR[rt]) xor GPR[rd]
===== Branch On Equal to Zero =====
Format: BEZ ra, rb
BEZ 	ra 	rb 	0
10100 	 	 	0 0000 0000
5 bits	3 bits	3 bits	9 bits
Description: The contents of register rb are compared to zero. If the contents of the register equal zero, the program branches to the address specified in register ra by exchanging the contents of ra with the value of the program counter.
Operation: 
 if GPR[rb] = 0^12 then
 PC <- GPR[ra]
 GPR[ra] <- PC
 endif
===== Branch On Less Than Zero =====
Format: BLTZ ra, rb
BLTZ 	ra 	rb 	0
10101 	 	 	0 0000 0000
5 bits	3 bits	3 bits	9 bits
Description: If the contents of register rb have the sign bit set the program branches to the address specified in register ra by exchanging the contents of ra with the value of the program counter.
Operation: 
 if GPR[rb]_11 = 1 then
 PC <- GPR[ra]
 GPR[ra] <- PC
 endif
===== Exchange =====
Format: EXCH exch, addr
EXCH 	exch 	addr 	0
10011 	 	 	0 0000 0000
5 bits	3 bits	3 bits	9 bits
Description: The contents of register exch are placed at the data memory location specified by the contents of register addr'. The contents of the data memory location specified by the contents of register addr are placed in register exch.
Operation: 
 GPR[exch] <- MEM[addr]
 MEM[addr] <- GPR[addr]
===== Or Immediate-Xor =====
Format: ORIX rd, rs, immediate
ORIX 	rd 	rs 	immediate
10001 	 	 	
5 bits	3 bits	3 bits	9 bits
Description: The 9-bit immediate is sign extended and combined with the contents of register rs in a bit-wise logical OR operation. The result is combined in a logical XOR with the contents of register rd and is placed in register rd.
Operation: GPR[rd] <- (GPR[rs] or (immediate_8)^3 || immediate_{8..0}) xor GPR[rd]
===== Or Xor =====
Format: ORX rd, rs, rt
ORX 	rd 	rs 	rt 	0
11001 	 	 	 	00 0000
5 bits	3 bits	3 bits	3 bits	6 bits
Description: The contents of register rs and register rt are combined in a bit-wise logical OR operation. The result is combined in a logical XOR with the contents of register rd and is placed in register rd.
Operation: GPR[rd] <- (GPR[rs] or GPR[rt]) xor GPR[rd]
===== Reverse Direction, Branch On Equal to Zero =====
Format: RBEZ ra, rb
RBEZ 	ra 	rb 	0
10110 	 	 	0 0000 0000
5 bits	3 bits	3 bits	9 bits
Description: The contents of register rb are compared to zero. If the contents of the register equal zero, the program branches to the address specified in register ra by exchanging the contents of ra with the value of the program counter. The global direction bit is also toggled when this instruction is executed.
Operation:
 if GPR[rb] = 0^12 then
 PC <- GPR[ra]
 GPR[ra] <- PC
 direction <- !direction
 endif
===== Reverse Direction, Branch On Less Than Zero =====
Format: RBLTZ ra, rb
RBLTZ 	ra 	rb 	0
10111 	 	 	0 0000 0000
5 bits	3 bits	3 bits	9 bits
Description: If the contents of register rb have the sign bit set the program branches to the address specified in register ra by exchanging the contents of ra with the value of the program counter. The global direction bit is also toggled when this instruction is executed.
Operation:
 if GPR[rb]_11 = 1 then
 PC <- GPR[ra]
 GPR[ra] <- PC
 direction <- !direction
 endif
===== Rotate Left =====
Format: RL rsd
RL 	rsd 	rsd 	0 	0
00100 	 	 	000 	00 0000
5 bits	3 bits	3 bits	3 bits	6 bits
Description: The contents of register rsd are rotated left one bit. The result is placed in register rsd.
Operation: GPR[rsd] <- GPR[rsd]_{10..0} || GPR[rsd]_11
===== Rotate Right =====
Format: RR rsd
RR 	rsd 	rsd 	0 	0
00101 	 	 	000 	00 0000
5 bits	3 bits	3 bits	3 bits	6 bits
Description: The contents of register rsd are rotated right one bit. The result is placed in register rsd.
Operation: GPR[rsd] <- GPR[rsd]_0 || GPR[rsd]_{11..1}
===== Shift Left Logical-Xor =====
Format: SLLX rd, rs
SLLX 	rd 	rs 	0 	0
11100 	 	 	 	00 0000
5 bits	3 bits	3 bits	3 bits	6 bits
Description: The contents of register rs are shifted left by one bit, inserting zero into the lower order bit. The result is combined in a logical XOR with the contents of register rd and is placed in register rd.
Operation: GPR[rd] <- (GPR[rs]_{10..0} || 0) xor GPR[rd]
===== Shift Right Arithmetic-Xor =====
Format: SRAX rd, rs
SRAX 	rd 	rs 	0 	0
11110 	 	 	 	00 0000
5 bits	3 bits	3 bits	3 bits	6 bits
Description: The contents of register rs are shifted right by one bit, sign extending the high order bit. The result is combined in a logical XOR with the contents of register rd and is placed in register rd.
Operation: GPR[rd] <- (GPR[rs]_11 || GPR[rs]_{11..1}) xor GPR[rd]
===== Exclusive Or =====
Format: XOR rsd, rs
XOR 	rsd 	rsd 	rs 	0
01010 	 	 	 	00 0000
5 bits	3 bits	3 bits	3 bits	6 bits
Description: The contents of register rsd and register rs' are combined in a bit-wise logical exclusive OR operation. The result is placed in register rsd.
Operation: GPR[rsd] <- GPR[rsd] xor GPR[rs]
===== Xor Immediate =====
Format: XORI rsd, immediate
XOR 	rsd 	rsd 	immediate
00010 	 	 	
5 bits	3 bits	3 bits	9 bits
Description: The 9-bit immediate is sign extended and combined with the contents of register rsd in a bit-wise logical XOR operation. The result is placed in register rsd.
Operation: GPR[rsd] <- GPR[rsd] xor (immediate_8)^3 || immediate_{8..0}
== Sources ==
* [1] Pendulum: A Reversible Computer Architecture by Carlin James Vieri - 1995
== External resources ==
* PISA Assembler
* An Introduction to Reversible Computing Using PhPISA - Includes a tutorial PDF
* Pendulum VM simulator
* C PendVM implementation
Category:Low-level
Category:Reversible computing
Category:Languages
Category:2014