プログラムがコンピュータで動く仕組み （ ハードウェア記述言語・CPUアーキテクチャ・アセンブラ・コンパイラ超入門）

# はじめに
コロナ禍の間に本を2冊出版しました．そのうちの1冊を紹介します．
* [プログラムがコンピュータで動く仕組み - ハードウェア記述言語・CPUアーキテクチャ・アセンブラ・コンパイラ超入門](https://www.coronasha.co.jp/np/isbn/9784339029222/)
本書の冒頭の引用です．

>本書は，「プログラムがどのような仕組みでコンピュータ上で動いているのか？」という疑問になるべく簡単に答えるのを目的としている．実際に使われているプログラム言語とコンピュータは複雑すぎるため，これらを用いてこの疑問に答えるのには多大な時間と労力を必要とする．そこで本書では，必要最小限のごく小さなコンピュータとごく小さなC言語風プログラミング言語を題材に，この疑問に答える．なるべく少ない時間と努力でプログラムがコンピュータで動作する仕組みの本質を理解するのが目的である．

>多くの人がC言語などのプログラミングを学び，実際にプログラミングを行っている．しかし，プログラムがどのようにコンピュータ上で動作するのか理解した上でプログラムを作成している人は少ないであろう．プログラムの字面をみてその動作を追っている場合がほとんどであると思われる．プログラム開発者が記述したC言語プログラムは，コンパイラとアセンブラにより機械語プログラムに変換され，コンピュータのCPU上で動作する．どのような機械語に変換されるのかということを意識することにより，プログラム開発者はより効率の良いプログラムを書けようになることが期待できる．

>本書では，プログラムがコンピュータで動作する仕組みを短時間で理解するために，ごく小さなCPUのTinyCPUを設計し，そのCPU上で直接実行できる機械語プログラムの動作シミュレーションを行う．また，TinyCPUの機械語プログラムに変換することを想定したアセンブリ言語TinyASMを導入し，TinyASMプログラムを機械語プログラムに変換するアセンブラを設計する．さらには，C言語風プログラミング言語TinyCを導入し，TinyCプログラムをTinyASMプログラムに変換するコンパイラを設計する．以上により，コンパイラを用いてC言語風のTinyCプログラムをTinyASMプログラムに変換し，アセンブラを用いて機械語プログラムに変換すれば，TinyCPU上で動作させることができる．

本書は，CQ出版のデザインウェーブ誌に約2年間にわたり15回掲載された「基礎から学ぶVerilog HDL＆FPGA設計」を基に，大幅に改定・再構成してまとめたものです．情報系の学生が2単位分（15回×90分の授業，アセンブラ，コンパイラも含めると4単位）で学べる内容として，プロセッサアーキテクチャ，アセンブラ，コンパイラの導入部分を短時間で効率よく学習できるように，これらのコアとなる部分を選び出し，コンパクトにまとめました．ハードウェアに直接関わることがないソフトウェア技術者にも，「プログラムがコンピュータで動作する仕組み」の基本的な理解を得るのに適した内容となっています．


# TinyCPU
TinyCPUはスタックアーキテクチャのごく小さな16ビットCPUでVerilog HDLで記述されています．
* 完全なスタックアーキテクチャ
* データ１６ビット，アドレス１２ビット（４０９６ワード）
* サポートする命令：ロード，即値ロード，ストア，分岐，条件分岐，入出力(FPGAボード上のスイッチからの入力と，LCDへの１６進表示）
* サポートする算術論理演算：加減乗算（+，-，*），符号反転（-），ビットシフト（>>,<<），ビットごとの論理和・論理積・XOR・否定(|，&，^，~)，論理和・論理積・論理否定（||，&&，!），等号（=），不等号（!=），大小比較（<，>，<=，>=）

* 全モジュールをあわせても200行以下

![cpu-arch.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3742233/f2b1013e-3dba-8e45-50c7-8df9a2a8983b.png)

# TinyASM
TinyCPU向けアセンブリ言語をTinyCPUの機械語命令に変換するプログラム．Perlの28行のスクリプトで記述
* 9種類の制御命令: HALT, PUSHI, PUSH, POP, JMP, JZ, JNZ, IN, OUT
* 19種類の算術演算命令：ADD, SUB, MUL, SHL, SHR, BAND, BOR, BXOR, AND, OR, EQ, NE, GE LE, GT, LT, NEG, BNOT NOT


# TinyC
C言語風プログラミング言語とそのコンパイラです．
* データ型：16ビット整数intのみ
* 代入文と基本算術演算を用いた式
* if文, while文, do文

字句解析にflex，構文解析にbisonを用いています．そのソースコードはflexが26行，bisonは76行です．

# TinyCのプログラム例
コラッツの予想の計算を行うTinyCのプログラム例です．コラッツの予想とは自然数$n$に対して，$n$が偶数のとき2で割り，奇数のとき3倍して1を足すという操作を繰り返すと，必ず1になるという未解決の命題です．この計算を行うプログラムです．
```
n=in;
while(n>1){
  out(n);
  if(n&1){
   n= n*3+1;
  } else {
   n = n>>1;
  }
 }
out(n);
halt;
int n;
```
これをコンパイルすると次のアセンブリ言語プログラムが得られます．
```
       IN
       POP n
_001T:
       PUSH n
       PUSHI 1
       GT
       JZ _001F
       PUSH n
       OUT
       PUSH n
       PUSHI 1
       BAND
       JZ _002F
       PUSH n
       PUSHI 3
       MUL
       PUSHI 1
       ADD
       POP n
       JMP _002T
_002F:
       PUSH n
       PUSHI 1
       SHR
       POP n
_002T:
       JMP _001T
_001F:
       PUSH n
       OUT
       HALT
n: 0
```
このアセンブリ言語プログラムをコンパイルすると次の機械語プログラムが得られます．
```
*** LABEL LIST ***
_001F   018
_001T   002
_002F   013
_002T   017
n       01B

*** MACHINE PROGRAM ***
000:D000                IN
001:301B                POP n
                _001T:
002:201B                PUSH n
003:1001                PUSHI 1
004:F00E                GT
005:5018                JZ _001F
006:201B                PUSH n
007:E000                OUT
008:201B                PUSH n
009:1001                PUSHI 1
00A:F005                BAND
00B:5013                JZ _002F
00C:201B                PUSH n
00D:1003                PUSHI 3
00E:F002                MUL
00F:1001                PUSHI 1
010:F000                ADD
011:301B                POP n
012:4017                JMP _002T
                _002F:
013:201B                PUSH n
014:1001                PUSHI 1
015:F004                SHR
016:301B                POP n
                _002T:
017:4002                JMP _001T
                _001F:
018:201B                PUSH n
019:E000                OUT
01A:0000                HALT
01B:0000        n: 0
```
# 関連授業
TinyCPUを題材に，現在，以下の授業を実施しています．
* **プログラムが動く仕組み**（学部2年生向け，2単位）：この授業では，デジタル回路設計の基礎知識を前提として，Verilog HDLを使用して論理ゲート，組み合わせ回路，順序回路の設計方法を学びます．最終的に，TinyCPUの設計とアセンブリ言語プログラミングを実施します．動作の確認には、Verilogシミュレータの[Icarus Verilog](https://bleyer.org/icarus/)を利用します．
* **情報科学部の演習科目**（学部3年生向け，1単位相当）：この科目では，TinyCPUに対するアセンブリ言語プログラミングの実践を通じて，学んだ知識を深めます．また，FPGAボードを使用してプログラムの動作確認を行います．
* **Embedded Systems**（大学院生向け，2単位）：この授業では，FPGAを使用して簡単なVerilog HDLによる回路設計から始め，段階的に知識を深めていきます．最終的には、TinyCPUをFPGAで動作させることが目標です．

# 参考資料等
* プログラムがコンピュータで動く仕組み - ハードウェア記述言語・CPUアーキテクチャ・アセンブラ・コンパイラ超入門
 ([コロナ社のページ](https://www.coronasha.co.jp/np/isbn/9784339029222/), [Amazonのページ](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%81%8C%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%81%A7%E5%8B%95%E3%81%8F%E4%BB%95%E7%B5%84%E3%81%BF-%E3%83%8F%E3%83%BC%E3%83%89%E3%82%A6%E3%82%A7%E3%82%A2%E8%A8%98%E8%BF%B0%E8%A8%80%E8%AA%9E%E3%83%BBCPU%E3%82%A2%E3%83%BC%E3%82%AD%E3%83%86%E3%82%AF%E3%83%81%E3%83%A3%E3%83%BB%E3%82%A2%E3%82%BB%E3%83%B3%E3%83%96%E3%83%A9%E3%83%BB%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E8%B6%85%E5%85%A5%E9%96%80-%E4%B8%AD%E9%87%8E-%E6%B5%A9%E5%97%A3/dp/433902922X))
 * デジタル回路設計入門 - FPGA時代の論理回路設計 - : 上の本はデジタル回路設計の基礎知識を前提としており，その知識を学ぶことを想定して書いた本です([コロナ社のページ](https://www.coronasha.co.jp/np/isbn/9784339009439/), [Amazonのページ](https://www.amazon.co.jp/%E3%83%87%E3%82%B8%E3%82%BF%E3%83%AB%E5%9B%9E%E8%B7%AF%E8%A8%AD%E8%A8%88%E5%85%A5%E9%96%80-FPGA%E6%99%82%E4%BB%A3%E3%81%AE%E8%AB%96%E7%90%86%E5%9B%9E%E8%B7%AF%E8%A8%AD%E8%A8%88-%E4%B8%AD%E9%87%8E-%E6%B5%A9%E5%97%A3/dp/4339009431))
 * [TinyCPU Wiki](https://www.cs.hiroshima-u.ac.jp/~nakano/wiki/): デザインウェーブでの連載一覧や，Verilog HDL, Flex, Bisonのソースコードを公開しています．
 * [デザインウェーブでの連載１回目](https://www.cqpub.co.jp/dwm/contents/dwm0113i.htm)
 * 論文：Koji Nakano, Yasuaki Ito, Processor, assembler, and compiler design education using an FPGA,  _Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS_, Pages 723 - 728, 2008. ([DOI](https://doi.org/10.1109/ICPADS.2008.71))
* Computer Architecture An Embedded Approach [Amazonのページ](https://www.amazon.co.jp/-/en/dp/125902556X): Section 8 CPU Design (pages:369-417)でTinyCPUについて詳しく紹介されています．