書きかけの記事もあるけど、ちょいとOISC ( One Instruction set computer) の１つ、subleqで遊んでみよう。
TL;DR : 異なるCPUアーキテクチャに触れると、今まで気が付かなかった当たり前のことにも、きちんと感謝ができる
- 変数のメモリ上での位置を考えるのは、コンパイラ様がやってくれている。ありがとうございます！
- 定数を加算する処理は、cpu自体が持っていることが多い。ありがとうございます！
- 実行部分とデータ部分のメモリ空間が分かれていることで、当然メモリ破壊もしにくい（ちゃんと作れば）ありがとうございます！！
われわれは、複雑化しすぎた命令セットに振り回され過ぎていないだろうか？
ソフトウェアエンジニア、とくに組み込みエンジニアは「SIMDだ」「AVXだ」「FP16だ」「Vector Extensionだ」などと、複雑化しすぎた命令セットに振り回されがちではないだろうか？コンパイラが全部よしなにしてくれるかもしれないが、だが、CPUの性能を最大限発揮するためには避けては通れないのだ。きっと。
さて、大学のコンピュータアーキテクチャ講義で、「単一命令セットコンピュータ」。つまり、命令が１つしかないコンピュータというものは理論上作れる、という話は聞いたことはないだろうか？ つい最近、こんな面白ニュースが飛び込んできた。
SubRISC+では、データからの異常検出やデータ探索をする軽量アルゴリズムをリアルタイムに処理し、警告などのかぎられたデータのみ送信する用途を想定。命令数を4つに限定することで小型/低消費電力化を図った。一方でチューリング完全であり、これらの用途以外の汎用プログラムも処理できるとしている。
命令数が4つ…！！！ これはロマンあふれる！！ とはいえ、現物は当然ないので手元でテストもできない。
だったら、命令数の少ない命令セットの１つである、subleqを動かしてみようという気持ちになってみた。今回はこんな感じ。
subleqって何？
シンプルにいうと、１命令しかない命令セット、もしくは当該命令セットを実行するCPUですね。
subleq a, b, c ; Mem[b] = Mem[b] - Mem[a]
; if (Mem[b] ≤ 0) goto c
ここに記載はされていないが、 Mem[b] > 0 であれば、次の命令を実行する。
ただし…… 日本語の情報が無い/間違っている
2021/3/14現在、日本のWikipediaの記載は間違っているように思われます。参考にするならば、en版のwikipediaか、https://esolangs.org/wiki/Subleqですね。
- https://ja.wikipedia.org/wiki/OISC
- https://en.wikipedia.org/wiki/One-instruction_set_computer#Subtract_and_branch_if_not_equal_to_zero
- https://esolangs.org/wiki/Subleq
subleqのメモリモデル・制約
では、subleqのメモリモデルや制約などを簡単にまとめていく。
- メモリ長さは、無限長である
- （現実的ではないので適当に切る）
- 1要素は、無限幅のsigbed integer
- (現実的ではないので適当にint32_t や int64_t)
- なお、足し算をしたりする都合上、配列要素はunsignedではなくsignedが望ましい。
- ロード時に内容が読み込まれなかったメモリは、内容を0とする。
- メモリ先端位置0番地から実行を開始する。
- subleq命令において、第1引数、第2引数、第3引数が負の数である場合、不正命令となる（原則）
- プログラムでは、第２引数に-1が指定されたら、第1引数で指定されているアドレスの内容を10進数で表示している。
- プログラムでは、第２引数に-2が指定されたら、第2引数で指定されているアドレスの内容を文字として表示している。
ARMやx86との違いは……
- レジスタという概念がありません。
- 直接メモリのアドレスを指定するだけです。
- addやmovなど、普通ある命令も全部subleq命令に置き換えなければなりません。
- プログラムが自分自体の内容を書き換えられる。
- 例えば、あるアドレスの内容を参照したい場合、Operandで読み出す先を指定しているアドレスを直接書き換えます。
subleqをちょっと動かしてみよう
プログラムを終了してみよう
これは標準的な命令ではないので機能拡張で。
subleq -1 -1 0
Mem[-1] はOut of boundaryなメモリアクセスなので、これをプログラム終了コードとする。
データを格納してみよう
通常のプログラムだと、.textやら.bssやら、メモリ用とでメモリがいくつかのブロックに分割されている。
subleqにはそのような複雑な機構はない。プログラム部分も全部データとして使える！！（メモリ破壊できる...)
0d1000 : subleq 0 0 1003 ; Mem[0] = 0, Mem[1] = 0, Mem[3] = 1003
メモリ内容をmov/copyしてみよう
アドレスTの内容を、アドレスXにコピーする場合は一度アドレス[A]を踏み台にして…
0d1000 : subleq A A 1003 ; mem[A] = 0
0d1000 : subleq T A 1006 ; mem[A] = mem[A] - mem[T] = -mem[T]
0d1000 : subleq X X 1009 ; mem[X] = 0
0d1000 : subleq A X 1012 ; mem[X] = mem[X] - mem[A] = mem[T]
メモリ内容をincrement/decrementしてみよう
+1, -1だったら、dataにそれを持たせるのが簡単。レジスタが存在しないので、直接加算・減算するイメージ。
0d1000 : subleq A A 1006 ; mem[A] = 0
0d1003 : subleq -1 +1 0 ; data
0d1006 : subleq 1003 A 1009 ; mem[X] = mem[X] - mem[1003] = mem[X] + 1
0d1006 : subleq 1004 A 1012 ; mem[X] = mem[X] - mem[1004] = mem[X] - 1
2つのアドレス内容に応じて、処理を分岐してみよう
0d0000 : subleq 0 0 6 ; _mainまでのジャンプ
; Variable A,B にも流用
0d0003 : subleq 0 1 2 ; Data X=0,Y=1,Z=2
0d0006 : subleq 0 0 9 ; mem[A] = 0
0d0009 : subleq 3 0 12 ; mem[A] = mem[A]-mem[X] = -mem[X]
0d0012 : subleq 1 1 15 ; mem[B] = 0
0d0015 : subleq 0 1 18 ; mem[B] = mem[B]-mem[A] = mem[X]
0d0018 : subleq 4 1 36 ; mem[B] = mem[B]-mem[Y] = mem[X]-mem[Y]
; mem[B]が0以下ならば36から実行
0d0021 : subleq 0 0 24 ; mem[A] = 0
0d0024 : subleq 3 0 27 ; mem[A] = mem[A]-mem[X] = -mem[X]
0d0027 : subleq 5 5 30 ; mem[Z] = mem[Z]-mem[Z] = 0
0d0030 : subleq 0 5 33 ; mem[Z] = mem[Z]-mem[A] = mem[X]
0d0033 : subleq 0 0 48 ; goto _END
0d0036 : subleq 0 0 39 ; mem[A] = 0
0d0039 : subleq 4 0 42 ; mem[A] = mem[A]-mem[Y] = -mem[Y]
0d0042 : subleq 5 5 45 ; mem[Z] = mem[Z]-mem[Z] = 0
0d0045 : subleq 0 5 48 ; mem[Z] = mem[Z]-mem[A] = mem[Y]
0d0048 : subleq 5 -1 51 ; mem[Z] を出力
0d0051 : subleq -1 -1 0 ; 終了
(1)実行結果(X=2,Y=1->Z=2を期待)
Iter 0 : PC=0 Operand = [0 0 6 ]Result = {0 0 6 2 1 2 }
Iter 1 : PC=6 Operand = [0 0 9 ]Result = {0 0 6 2 1 2 }
Iter 2 : PC=9 Operand = [3 0 12 ]Result = {-2 0 6 2 1 2 }
Iter 3 : PC=12 Operand = [1 1 15 ]Result = {-2 0 6 2 1 2 }
Iter 4 : PC=15 Operand = [0 1 18 ]Result = {-2 2 6 2 1 2 }
Iter 5 : PC=18 Operand = [4 1 36 ]Result = {-2 1 6 2 1 2 }
Iter 6 : PC=21 Operand = [0 0 24 ]Result = {0 1 6 2 1 2 }
Iter 7 : PC=24 Operand = [3 0 27 ]Result = {-2 1 6 2 1 2 }
Iter 8 : PC=27 Operand = [5 5 30 ]Result = {-2 1 6 2 1 0 }
Iter 9 : PC=30 Operand = [0 5 33 ]Result = {-2 1 6 2 1 2 }
Iter 10 : PC=33 Operand = [0 0 48 ]Result = {0 1 6 2 1 2 }
Iter 11 : PC=48 Operand = [5 -1 51 ][2]Result = {0 1 6 2 1 2 }
Iter 12 : PC=51 Operand = [-1 -1 0 ]Result = {0 1 6 2 1 2 }... END
-> oMem[5] が 2になっている
(2)実行結果(X=0,Y=1->Z=1を期待)
Iter 0 : PC=0 Operand = [0 0 6 ]Result = {0 0 6 0 1 2 }
Iter 1 : PC=6 Operand = [0 0 9 ]Result = {0 0 6 0 1 2 }
Iter 2 : PC=9 Operand = [3 0 12 ]Result = {0 0 6 0 1 2 }
Iter 3 : PC=12 Operand = [1 1 15 ]Result = {0 0 6 0 1 2 }
Iter 4 : PC=15 Operand = [0 1 18 ]Result = {0 0 6 0 1 2 }
Iter 5 : PC=18 Operand = [4 1 36 ]Result = {0 -1 6 0 1 2 }
Iter 6 : PC=36 Operand = [0 0 39 ]Result = {0 -1 6 0 1 2 }
Iter 7 : PC=39 Operand = [4 0 42 ]Result = {-1 -1 6 0 1 2 }
Iter 8 : PC=42 Operand = [5 5 45 ]Result = {-1 -1 6 0 1 0 }
Iter 9 : PC=45 Operand = [0 5 48 ]Result = {-1 -1 6 0 1 1 }
Iter 10 : PC=48 Operand = [5 -1 51 ][1]Result = {-1 -1 6 0 1 1 }
Iter 11 : PC=51 Operand = [-1 -1 0 ]Result = {-1 -1 6 0 1 1 }... END
-> oMem[5] が 5になっている
うごかしてみた感想
われわれは、どれだけcpu様やコンパイラ様に助けてもらっていたんだろうか…… 感謝しかないですね。
- 変数のメモリ上での位置を考えるのは、コンパイラ様がやってくれている。ありがとうございます！
- 定数を加算する処理は、cpu自体が持っていることが多い。ありがとうございます！
- 実行部分とデータ部分のメモリ空間が分かれていることで、当然メモリ破壊もしにくい（ちゃんと作れば）ありがとうございます！！
ソースコード
subleq.h
#ifndef SUBLEQ_H_
#define SUBLEQ_H_
#include <map>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
class Subleq {
private:
const static int mMemSize = 65536;
int64_t mMem[mMemSize];
int64_t mPC;
map<string,string> mAlias;
public:
Subleq();
virtual ~Subleq();
void load(string fname);
void run(int _iter);
bool iter();
void cont(int _iter);
int64_t get(const int n) const { return mMem[n]; }
int64_t getPC() const { return mPC; }
};
#endif /* SUBLEQ_H_ */
subleq.cpp
#include "Subleq.h"
using namespace std;
Subleq::Subleq():mPC(0)
{
for(auto &it : mMem){
it = 0;
}
}
Subleq::~Subleq() {
}
void Subleq::load (string _fname){
ifstream ifs(_fname);
int index = 0;
int line_num = 0;
mPC = 0;
string line;
while (getline(ifs,line)){
istringstream ist(line);
string oOperand;
ist >> oOperand;
if ( oOperand == "alias") {
string oName, oAddress;
ist >> oName >> oAddress;
mAlias[oName] = oAddress;
}else if ( oOperand == "subleq") {
string oOP1, oOP2, oOP3;
ist >> oOP1;
oOP2 = oOP1;
oOP3 = to_string( index + 3 );
if ( ist.eof() == false) {
ist >> oOP2;
}
if ( ist.eof() == false) {
ist >> oOP3;
}
if ( mAlias.find(oOP1) != mAlias.end() ){
oOP1 = mAlias[oOP1];
}
if ( mAlias.find(oOP2) != mAlias.end() ){
oOP2 = mAlias[oOP2];
}
if ( mAlias.find(oOP3) != mAlias.end() ){
oOP3 = mAlias[oOP3];
}
mMem[index++] = atoll( oOP1.c_str() );
mMem[index++] = atoll( oOP2.c_str() );
mMem[index++] = atoll( oOP3.c_str() );
cout << line_num << ":" << oOP1 << " "<< oOP2 << " " << oOP3 << endl;
line_num += 1;
}else{
string oOP1, oOP2, oOP3;
oOP1 = oOperand;
ist >> oOP2 >> oOP3;
mMem[index++] = atoll( oOP1.c_str() );
mMem[index++] = atoll( oOP2.c_str() );
mMem[index++] = atoll( oOP3.c_str() );
cout << line_num << ":" << oOP1 << " "<< oOP2 << " " << oOP3 << endl;
line_num += 1;
}
}
}
bool Subleq::iter (){
int64_t oA, oB, oC, t = -1;
oA = mMem [ mPC ] ;
oB = mMem [ mPC + 1 ] ;
oC = mMem [ mPC + 2 ] ;
if ( oA < 0 ) {
return false ;
}
/*
* subleq A -1
* -> Aのアドレス内容を 10進数表示
* subleq A -2
* -> Aのアドレス内容を 文字表示
*/
if ( oB == -1 ) {
t = -1;
cout << "[" << mMem[ oA ] << "]" ;
}else if ( oB == -2 ) {
char c = (mMem[oA]) & 0xFF;
t = -1;
cout << "[" << mMem[ oA ] << "]" ;
cout << "'" << c << "'" ;
}else if ( oB < 0 ){
cout << "END-PROCESS";
return false;
}else{
t = mMem [oB] - mMem [oA];
mMem [oB] = t;
}
if ( t <= 0 ) {
mPC = oC;
}else{
mPC += 3;
}
return true;
}
void Subleq::cont (int _iter){
for(int i = 0 ; i < _iter ; i++ ){
bool ret;
cout << "Iter " << i << " : PC=" << mPC << " ";
cout << "Operand = [" ;
cout << mMem[mPC] << " " << mMem[mPC+1] << " " << mMem[mPC+2] << " " ;
cout << "]" ;
ret = iter();
cout << "Result = {" ;
for(int j=0;j < 6 ; j++ ){
cout << mMem[j] << " " ;
}
cout << "}" ;
if ( ret == false ) {
cout << "... END" << endl;
break;
}
cout << "" << endl;
}
}
void Subleq::run (int _iter){
mPC = 0;
cont(_iter);
}