メモリ操作の基礎
$sp（スタックポインタ）
スタックポインタは「今スタックのどこにいるか」を示すレジスタ。
スタックはアドレスが小さい方向に伸びる：
アドレス大的 ┌─────────────┐
│ まだ使えない │
├─────────────┤ ← $sp（現在のトップ）
│ 空き領域 │
├─────────────┤
│ データ3 │ ← 以前pushしたもの
├─────────────┤
│ データ2 │
├─────────────┤
│ データ1 │
└─────────────┘
アドレス小的
push/pop の動き：
【push 5】 【pop】
$sp -= 4 $t0 = 0($sp) ← 5を読み取り
0($sp) = 5 $sp += 4 ← $spを戻す
sw と lw（メモリ書き込み・読み出し）
| 命令 | 意味 | 例 |
|---|---|---|
| sw | Store Word：メモリに書き込む | sw $ra, 0($sp) |
| lw | Load Word：メモリから読み出す | lw $ra, 0($sp) |
構文：sw レジスタ, オフセット(ベースレジスタ)
sw $ra, 0($sp) # $raの中身を、$spが指すアドレスに書き込む
lw $ra, 0($sp) # $spが指すアドレスの中身を、$raに読み込む
1ワード = 4バイトなので、次のデータは +4 の位置：
sw $ra, 0($sp) # アドレス $sp+0 に $ra を保存
sw $a0, 4($sp) # アドレス $sp+4 に $a0 を保存
lw $ra, 0($sp) # $sp+0 から $ra に復元
lw $a0, 4($sp) # $sp+4 から $a0 に復元
フレームとは
フレーム = 1つの関数が使うスタックの領域。
mainのフレーム fact(4)のフレーム
┌─────────────┐ ┌─────────────┐
│ $ra │ ← mainの │ $ra │ ← fact(4)の
│ │ リターン先 │ │ リターン先
│ 局所変数 │ │ 引数n=4 │
└─────────────┘ └─────────────┘
↓ ↓
$sp（現在地） $sp（現在地）
関数呼び出しのたびにフレームが積み重なる：
main() → fact(4) → fact(3) → fact(2) → fact(1)
スタックの状態：
┌─────────────┐
│ fact(1) │ ← $sp（一番上）
├─────────────┤
│ fact(2) │
├─────────────┤
│ fact(3) │
├─────────────┤
│ fact(4) │
├─────────────┤
│ main │ ← 最初に積まれたもの
└─────────────┘
リターンするたびにフレームが消える。fact(1)がリターン→fact(1)のフレーム削除、fact(2)がリターン→fact(2)のフレーム削除、…と順番に元に戻る。
なぜ退避が必要か
レジスタは関数ごとに使い回される。呼び出し先で $a0 が書き換えられたら、元の値がわからなくなる。
main: li $a0, 4 # $a0 = 4（factの引数）
jal fact # fact(4)を呼ぶ
# ここで $a0 は fact の中で壊されている
退避 = 一旦メモリに保存しておいて、後で戻す：
sw $a0, 0($sp) # 保存（push）
... 中で $a0 が壊されてもOK ...
lw $a0, 0($sp) # 復元（pop）
レジスタ退避のルール
callee-save レジスタ（$s0〜$s7、$ra）
関数の入口で退避 → 出口で復元（1回ずつ）。
┌─ 関数入口 ─┐ ┌─ 関数出口 ─┐
│ sw $s0,.. │ │ lw $s0,.. │
│ sw $ra,.. │ ←対→ │ lw $ra,.. │
└────────────┘ └────────────┘
呼び出し元がこのレジスタを使っている可能性があるため、元の値を壊さないように守る。
caller-save レジスタ（$t0〜$t9、$a0〜$a3、$v0〜$v1）
jal のたびに退避・復元する。
main:
sw $t0, 0($sp) # 保存（jal前）
li $a0, 1
jal fun # $t0 が壊れる
lw $t0, 0($sp) # 復元（jal後）
呼び出し先がこのレジスタを自由に使ってもいいルール。
まとめ
| レジスタ | タイプ | 退避タイミング |
|---|---|---|
$s0〜$s7 | callee | 関数入口/出口（1回ずつ） |
$ra | callee | 関数入口/出口（1回ずつ） |
$t0〜$t9 | caller | jal のたびに |
$a0〜$a3 | caller | jal のたびに |
$v0〜$v1 | caller | jal のたびに |
関数呼び出しの基本
引数と返値の受け渡し
- 引数：
$a0〜$a3に順に入れる（5引数目以降はスタックにpush） - 返値：
$v0に入れて返す
関数の入口・出口テンプレート
関数名:
# === 入口（フレーム作成 + 退避） ===
addi $sp, $sp, -8 # フレーム確保
sw $ra, 4($sp) # $ra を退避（jalを使うから）
sw $a0, 0($sp) # 引数nを退避（後で使うから）
# === 関数本体 ===
...
jal 他の関数
...
# === 出口（復元 + フレーム解放） ===
lw $a0, 0($sp) # 引数nを復元
lw $ra, 4($sp) # $ra を復元
addi $sp, $sp, 8 # フレーム解放
jr $ra # リターン絶対に守るルール：
- 入口で退避したら、必ず出口で復元
$spを-Nしたら、出口では+Nして戻す- 入口と出口の
$spの操作は必ず対になる
関数呼び出しによる文字列コピー
C言語の元のコード
void my_strcpy(char *q, char *p) {
while ((*q++ = *p++) != '\0');
}
char from[4], to[4];
int main(void) {
fgets(from, 4, stdin);
my_strcpy(to, from);
printf("%s\n", to);
}関数定義（呼び出し側とは独立）
my_strcpy: # q=$a0（コピー先）, p=$a1（コピー元）
loop:
lb $t0, 0($a1) # pから1バイト読み込み → $t0
sb $t0, 0($a0) # $t0 を q に書き込み
addi $a1, $a1, 1 # p++
addi $a0, $a0, 1 # q++
bne $t0, 0, loop # \0 じゃなければループ
jr $ramy_strcopyはフレームが不要。関数内で他の関数を呼ばないため $ra の保護が不要で、$s も使わないため退避も不要。
呼び出し側（main）
.text
.globl main
main:
# 入口（$ra退避）
addi $sp, $sp, -4
sw $ra, 0($sp)
# fgets相当：fromの先頭アドレスを$a0に
la $a0, from
li $a1, 4
jal read_str
# my_strcpy相当：to と from を渡す
la $a0, to
la $a1, from
jal my_strcpy
# printf相当：to を渡す
la $a0, to
jal print_str
# 出口（$ra復元）
lw $ra, 0($sp)
addi $sp, $sp, 4
jr $ra
.data
from: .space 4
to: .space 4mainのフレーム：
┌─────────────┐
│ $ra │ ← $sp+0（リターン先を保存）
└─────────────┘
$sp ← -4 して確保
from と to は .data にある大域変数なので la でアドレスを取得。局所配列にする場合はスタック上に確保する（add $a0, $sp, $zero でアドレスを計算）。
局所配列版のフレーム
main のフレーム（局所配列版）：
┌─────────────┐
│ $ra │ ← $sp+8
├─────────────┤
│ to[0-3] │ ← $sp+4
├─────────────┤
│ from[0-3] │ ← $sp+0
└─────────────┘
$sp ← -12 して確保
main:
addi $sp, $sp, -12 # 3ワード分確保（4+4+4）
sw $ra, 8($sp) # $ra を退避
add $a0, $sp, $zero # from の先頭アドレス
li $a1, 4
jal read_str
addi $a0, $sp, 4 # to の先頭アドレス
add $a1, $sp, $zero # from の先頭アドレス
jal my_strcpy
addi $a0, $sp, 4 # to の先頭アドレス
jal print_str
lw $ra, 8($sp)
addi $sp, $sp, 12
jr $ra再帰呼び出し
階乗 n! の再帰版
int fact(int n) {
if (n == 1) return 1;
else return n * fact(n - 1);
}再帰も普通の関数呼び出しと同じ。特別なことは何もない。
fact:
# 入口
addi $sp, $sp, -8 # 2ワード確保
sw $ra, 4($sp) # リターンアドレス退避
li $t0, 1
bne $a0, $t0, else # n != 1 なら分岐
# n == 1 の場合
move $v0, $t0 # 返値 = 1
j exit
else:
sw $a0, 0($sp) # 引数nを退避
addi $a0, $a0, -1 # n-1 を引数に設定
jal fact # fact(n-1) を呼ぶ
lw $a0, 0($sp) # n を復元
mul $v0, $a0, $v0 # 返値 = n * fact(n-1)
exit:
# 出口
lw $ra, 4($sp) # リターンアドレス復元
addi $sp, $sp, 8 # フレーム解放
jr $raなぜ $a0 を退避するのか
fact(3) を呼んだ場合の流れ：
fact(3) 実行中
├── $a0 = 3（今の引数）
├── sw $a0, 0($sp) ← 3 を退避
├── $a0 = 2 にして jal fact
│ ├── fact(2) 実行中
│ │ ├── $a0 = 2（今の引数）
│ │ ├── sw $a0, 0($sp) ← 2 を退避
│ │ ├── $a0 = 1 にして jal fact
│ │ │ ├── fact(1) → 返値1
│ │ │ └── return 1
│ │ ├── lw $a0, 0($sp) ← 2 を復元！
│ │ └── mul $v0, 2, 1 = 2
│ └── return 2
├── lw $a0, 0($sp) ← 3 を復元！
└── mul $v0, 3, 2 = 6
退避しなかった場合：jal fact の後 $a0 は fact の中で 1 に変わってしまう。n * fact(n-1) の n がわからなくなる。
fact(3) 実行中のスタック
┌─────────────┐
│ fact(1) │ $ra と $a0=1
├─────────────┤
│ fact(2) │ $ra と $a0=2
├─────────────┤
│ fact(3) │ $ra と $a0=3
├─────────────┤
│ main │ $ra
└─────────────┘
$sp
各フレームに別々の $a0 が保存されている。これが再帰の仕組み。
再帰の核心
再帰 ＝ 関数が自分自身を呼ぶ
→ 普通の関数呼び出しと同じ
→ フレームが積み重なる
→ 各フレームに引数の退避値が残る
→ リターンするたびにフレームが消えて、前の引数に戻る
偶奇判定（再帰版）
C言語のコード
int even(int n) {
if (n == 0) return 1; // 0は偶数
else return odd(n - 1); // n-1が偶数ならnも偶数
}
int odd(int n) {
if (n == 0) return 0; // 0は奇数じゃない
else return even(n - 1); // n-1が奇数ならnも奇数
}even が odd を呼び、odd が even を呼ぶ。お互いに呼び合いながら 1 ずつ減っていく。
アセンブリ（通常版）
even:
bne $a0, $zero, else1 # n != 0 なら分岐
li $v0, 1 # n == 0 → return 1（偶数）
jr $ra
else1:
addi $sp, $sp, -4 # フレーム確保
sw $ra, 0($sp) # $ra 退避
addi $a0, $a0, -1 # n-1 を引数に
jal odd # odd(n-1) を呼ぶ
lw $ra, 0($sp) # $ra 復元
addi $sp, $sp, 4 # フレーム解放
jr $ra # odd の返値をそのまま返す
odd:
bne $a0, $zero, else2
li $v0, 0 # n == 0 → return 0（奇数じゃない）
jr $ra
else2:
addi $sp, $sp, -4
sw $ra, 0($sp)
addi $a0, $a0, -1
jal even
lw $ra, 0($sp)
addi $sp, $sp, 4
jr $raodd(3) の呼び出しと帰還の流れ
odd(3) を呼ぶ
├── $a0 = 3, 3 ≠ 0 なので else2 へ
├── $a0-- → 2, jal even
│ even(2)
│ ├── $a0 = 2, 2 ≠ 0 なので else1 へ
│ ├── $a0-- → 1, jal odd
│ │ odd(1)
│ │ ├── $a0 = 1, 1 ≠ 0 なので else2 へ
│ │ ├── $a0-- → 0, jal even
│ │ │ even(0)
│ │ │ └── return 1 ← 基底ケース（0は偶数）
│ │ │ odd(1) は even の返値をそのまま返す → return 1
│ │ └── return 1
│ │ even(2) は odd の返値をそのまま返す → return 1
│ └── return 1
│ odd(3) は even の返値をそのまま返す → return 1
└── odd(3) の返値 = 1（＝ 3は奇数）
odd(2) の場合は最終的に even(0) → return 1 → odd(1) で return 0 → even(2) で return 0 → odd(2) の返値 = 0（＝ 2は奇数じゃない）。
返値がそのまま伝わる理由
odd も even も、呼び出し先の返値をいじらずにそのまま返している。
「3は奇数？」→「2は偶数？」→「1は奇数？」→「0は偶数？」→「はい」
その「はい」が一番上まで伝わっていく。比喩的に言えば、問い合わせが一番下まで届き、答えがそのまま戻ってくる。
| 入力 | even の返値 | odd の返値 | 意味 |
|---|---|---|---|
| 0 | 1 | 0 | 0は偶数、奇数じゃない |
| 1 | 0 | 1 | 1は奇数、偶数じゃない |
| 2 | 1 | 0 | 2は偶数、奇数じゃない |
| 3 | 0 | 1 | 3は奇数、偶数じゃない |
fact(3) 実行中のスタック
通常版では各呼び出しのたびにフレームが積み重なる：
┌──────────────┐
│ odd(1) のframe │ ← $sp
├──────────────┤
│ even(2)のframe │
├──────────────┤
│ odd(3) のframe │
├──────────────┤
│ main の frame │
└──────────────┘
末尾呼び出しの除去
通常版の問題点
jal + jr $ra のペアが毎回発生 → スタックが n に比例して伸びる。
除去版：jal → j に置き換える
even:
bne $a0, $zero, else1
li $v0, 1
jr $ra
else1:
addi $a0, $a0, -1
j odd # jal → j に変更
odd:
bne $a0, $zero, else2
li $v0, 0
jr $ra
else2:
addi $a0, $a0, -1
j even # jal → j に変更なぜ jal → j で OK か
通常版では jal で飛び、jr $ra で戻ってからすぐに jr $ra する。つまり戻った直後にリターンするだけのパターン。この場合、jal を j（一飛び）に置き換え、jr $ra を省略できる。
除去版では even と odd の間を j でループする。実質的にスタックを使わないループと同じ。
| 通常版 | 除去版 | |
|---|---|---|
| 命令 | jal + jr $ra | j のみ |
| スタック消費 | n に比例 | なし |
| フレーム数 | n 個 | 0 個 |
odd(3) の除去版の流れ：
odd(3) → j even(2) → j odd(1) → j even(0) → return 1
odd(1) は even の返値をそのまま返す → 1
even(2) は odd の返値をそのまま返す → 1
odd(3) は even の返値をそのまま返す → 1
スタックが一切増えない。even と odd の間をループしているだけ。
局所配列とスタック
大域変数 vs 局所配列
配列をメモリに置く方法は2種類ある：
大域変数（.data） | 局所配列（スタック） | |
|---|---|---|
| 定義場所 | .data セグメント | 関数のフレーム内 |
| アドレス取得 | la $a0, from | add $a0, $sp, $zero |
| ライフサイクル | プログラム全体 | 関数呼び出し中のみ |
| 再帰で使える？ | 使えない（上書きされる） | 使える（各フレームに個別） |
大域変数版
.data
from: .space 4
to: .space 4
main:
addi $sp, $sp, -4
sw $ra, 0($sp)
la $a0, from # from の先頭アドレスを取得
li $a1, 4
jal read_str
la $a0, to
la $a1, from
jal my_strcpy
la $a0, to
jal print_str
lw $ra, 0($sp)
addi $sp, $sp, 4
jr $ra局所配列版
main:
addi $sp, $sp, -12 # 3ワード分確保（from + to + $ra）
sw $ra, 8($sp) # $ra を退避
add $a0, $sp, $zero # from の先頭アドレス（$sp+0）
li $a1, 4
jal read_str
addi $a0, $sp, 4 # to の先頭アドレス（$sp+4）
add $a1, $sp, $zero # from の先頭アドレス（$sp+0）
jal my_strcpy
addi $a0, $sp, 4 # to の先頭アドレス（$sp+4）
jal print_str
lw $ra, 8($sp) # $ra 復元
addi $sp, $sp, 12 # フレーム解放
jr $raフレームの構造
局所配列版の main のフレーム：
$sp+8 ┌─────────────┐
│ $ra │ ← リターンアドレス
$sp+4 ├─────────────┤
│ to[0-3] │ ← コピー先配列（4バイト）
$sp+0 ├─────────────┤
│ from[0-3] │ ← コピー元配列（4バイト）
└─────────────┘
$sp
ポイント：
laではなくaddでアドレスを計算する（$spからオフセットを足す）- 局所配列はデータセグメントではなくスタックメモリに配置
- もし配列の範囲を超えて書き込むと、
$raが壊れてリターン先がわからなくなる
再帰で局所配列が重要的な理由
大域変数は程序全体で1つだけ。再帰呼び出しで上書きされてしまう：
fact(3) が from を使う → fact(2) も from を使う → 上書き！
局所配列なら各フレームに個別に存在する：
fact(3) のフレーム → from が $sp+0 にある
fact(2) のフレーム → from が別の $sp+0 にある（別物）
このため、再帰的な関数では局所変数をスタック上に配置する必要がある。
ここからがペーパーテストの範囲
ノイマン型計算機
- プログラム内蔵方式
- 逐次実行方式
- 1つのプロセッサとメモリ
- 逐次実行の関係でほとんどの回路が休むことになってしまう
古典的なRISC型CPUのステージ
- 命令フェッチ(IFステージ)
- メインメモリ/キャッシュメモリから命令を読み出す
- 命令デコード/レジスタフェッチ(IDステージ)
- 命令でコードとソースオペランドレジスタの読み出しを並行して行う
- 実行(EXステージ)
- 演算の実行もしくは実行アドレス/分岐アドレスの計算、分岐条件の判定のいずれか、プログラムカウンタの設定も行う
- メモリアクセス(MAステージ)
- road/storeにおける実行アドレスのオペランドデータにアクセスする
- レジスタへのライトバック(WBステージ)
- 結果をレジスタへ格納する。次のクロックでレジスタフェッチ可能
lw $t0,4($sp)の場合
- 命令を読み出す
- lwを認識、
$spをフェッチ $sp+4を計算- メモリから値を読み出す
$t0に値を格納
sw $t0,4($sp)の場合
- 命令を読み出す
- swを認識、
$spと$t0をフェッチ $sp+4を計算- メモリに書き込む
- 未使用
add $t0,$t1,$t2の場合
- 命令を読み出す
- addを認識、
$t1と$t2をフェッチ $t1+$t2を計算（加算実行）- 未使用（演算結果をWBへ素通り）
$t0に格納
beq $t0,$t1,loopの場合
- 命令を読み出す
- beqを認識、
$t0と$t1をフェッチ $t0と$t1を比較し、条件成立ならPCに分岐先アドレスをセット- 未使用
- 未使用
シングルクロック方式では最も実行時間の長い命令に合わせてクロックサイクルを決定する
マルチサイクル方式の場合は最も長いステージに合わせてクロックサイクルを決定する