Kiến trúc MIPS-32 bit

▪ Nhiệm vụ cơ bản nhất của CPU là phải thực hiện các lệnh được yêu cầu, gọi là instruction
▪ Các CPU sẽ sử dụng các tập lệnh (instruction set) khác nhau để có thể giao tiếp với nó

Kích thước lệnh

▪ Kích thước lệnh bị ảnh hưởng bởi:
- Cấu trúc đường truyền bus
- Kích thước và tổ chức bộ nhớ
- Tốc độ CPU
▪ Giải pháp tối ưu lệnh:
- Dùng lệnh có kích thước ngắn, mỗi lệnh chỉ nên được thực thi trong đúng 1 chu kỳ CPU
- Dùng bộ nhớ cache

Bộ lệnh MIPS

▪ Chúng ta sẽ làm quen với tập lệnh cho kiến trúc MIPS (PlayStation 1, 2; PSP; Windows CE, Routers…)
▪ Được xây dựng theo kiến trúc (RISC) với 4 nguyên tắc:
- Càng đơn giản, càng ổn định
- Càng nhỏ gọn, xử lý càng nhanh
- Tăng tốc xử lý cho những trường hợp thường xuyên xảy ra
- Thiết kế đòi hỏi sự thỏa hiệp tốt

Cấu trúc cơ bản của 1 chương trình hợp ngữ trên MIPS

Hello.asm

Bộ lệnh MIPS – Thanh ghi

▪ Là đơn vị lưu trữ data duy nhất trong CPU
▪ Trong kiến trúc MIPS:
- Có tổng cộng 32 thanh ghi đánh số từ $0 ⇒ $31
+ Càng ít càng dễ quản lý, tính toán càng nhanh
+ Có thể truy xuất thanh ghi qua tên của nó (slide sau)
- Mỗi thanh ghi có kích thước cố định 32 bit
+ Bị giới hạn bởi khả năng tính toán của chip xử lý
+ Kích thước toán hạng trong các câu lệnh MIPS bị giới hạn ở 32 bit, nhóm 32 bit gọi là từ (word)

Thanh ghi toán hạng

▪ Ngôn ngữ cấp cao (C, Java…): toán hạng = biến (variable)
- Các biến lưu trong bộ nhớ chính
▪ Ngôn ngữ cấp thấp (Hợp ngữ): toán hạng chứa trong các thanh ghi
- Thanh ghi không có kiểu dữ liệu
- Kiểu dữ liệu thanh ghi được quyết định bởi thao tác trên thanh ghi
▪ So sánh:
- Ưu: Thanh ghi truy xuất nhanh hơn nhiều bộ nhớ chính
- Khuyết: Không như bộ nhớ chính, thanh ghi là phần cứng có số lượng giới hạn và cố định ⇒ Phải tính toán kỹ khi sử dụng

Một số thanh ghi toán hạng quan tâm

▪ Save register:
- MIPS lấy ra 8 thanh ghi ($16 - $23) dùng để thực hiện các phép tính số học, được đặt tên tương ứng là $s0 - $s7
- Tương ứng trong C, để chứa giá trị biến (variable)
▪ Temporary register:
- MIPS lấy ra 8 thanh ghi ($8 - $15) dùng để chứa kết quả trung gian, được đặt tên tương ứng là $t0 - $t7
- Tương ứng trong C, để chứa giá trị biến tạm (temporary variable)

Bảnh danh sách thanh ghi MIPS. Thanh ghi 1 ($at) để dành cho assembler. Thanh ghi 26 – 27 ($k0 - $k1) để dành cho OS

Bộ lệnh MIPS – 4 thao tác chính
▪ Phần 1: Phép toán số học (Arithmetic)
▪ Phần 2: Di chuyển dữ liệu (Data transfer)
▪ Phần 3: Thao tác luận lý (Logical)
▪ Phần 4: Rẽ nhánh (Un/Conditional branch)

Phần 1: Phép toán số học
▪ Cú pháp: opt opr, opr1, opr2
- opt (operator): Tên thao tác (toán tử, tác tử)
- opr (operand): Thanh ghi (toán hạng, tác tố đích) chứa kết quả
- opr1 (operand 1): Thanh ghi (toán hạng nguồn 1)
- opr2 (operand 2): Thanh ghi / hằng số (toán hạng nguồn 2)

▪ Giả sử xét câu lệnh sau: add a, b, c
- Chỉ thị cho CPU thực hiện phép cộng a ← b+c
- a, b, c được gọi là thanh ghi toán hạng
- Phép toán trên chỉ có thể thực hiện với đúng 3 toán hạng (không nhiều cũng không ít hơn)

Cộng, trừ số nguyên

▪ Cộng (Add):
- Cộng có dấu: add $s0, $s1, $s2
- Cộng không dấu: addu $s0, $s1, $s2(u: unsigned)
- Diễn giải: $s0 ← $s1 + $s2 . C/C++: (a = b + c)

▪ Trừ (Subtract):
- Trừ có dấu: sub $s0, $s1, $s2
- Trừ không dấu: subu $s0, $s1, $s2
- Diễn giải: (u: unsigned) $s0 ← $s1 - $s2
C/C++: (a = b - c)

Nhận xét

▪ Toán hạng trong các lệnh trên phải là thanh ghi
▪ Trong MIPS, lệnh thao tác với số nguyên có dấu được biểu diễn dưới dạng bù 2
▪ Làm sao biết 1 phép toán được biên dịch từ C (ví dụ a = b + c) là thao tác có dấu hay không dấu? ⇒ Dựa vào trình biên dịch
▪ Có thể dùng 1 toán hạng vừa là nguồn vừa là đích add $s0, $s0, $s1
▪ Cộng, trừ với hằng số? ⇒ $s2 sẽ đóng vai trò là hằng số
- Cộng: addi $s0, $s1, 3 (addi = add immediate)

Ví dụ 1

▪ Chuyển thành lệnh MIPS từ lệnh C: a = b + c + d –e
▪ Chia nhỏ thành nhiều lệnh MIPS:

▪ Tại sao dùng nhiều lệnh hơn C?
⇒ Bị giới hạn bởi số lượng cổng mạch toán tử và thiết kế bên trong cổng mạch
▪ Ký tự “#” dùng để chú thích trong hợp ngữ cho MIPS

Ví dụ 2

▪ Chuyển thành lệnh MIPS từ lệnh C: f = (g + h) – (i + j)
▪ Chia nhỏ thành nhiều lệnh MIPS:

Lưu ý: Phép gán ?
▪ Kiến trúc MIPS không có cổng mạch dành riêng cho phép gán
⇒ Giải pháp: Dùng thanh ghi zero ($0 hay $zero) luôn mang giá trị 0
▪ Ví dụ: add $s0, $s1, $zero
Tương đương: $s0 = $s1 + 0 = $s1 (gán)
▪ Lệnh “add $zero, $zero, $s0” có hợp lệ ?

Phép nhân, chia số nguyên
▪ Thao tác nhân / chia của MIPS có kết quả chứa trong cặp 2 thanh ghi tên là $hi và $lo Bit 0-31 thuộc $lo và 32-63 thuộc $hi

Phép nhân

▪ Cú pháp: mult $s0, $s1
▪ Kết quả (64 bit) chứa trong 2 thanh ghi
- $lo (32 bit) = (($s0 * $s1) << 32) >> 32
- $hi (32 bit) = ($s0 * $s1) >> 32
▪ Câu hỏi: Làm sao truy xuất giá trị 2 thanh ghi $lo và $hi?
⇒ Dùng 2 cặp lệnh mflo (move from lo), mfhi (move from hi) - mtlo (move to lo), mthi (move to high)
- mflo $s0 ($s0 = $lo)
- mfhi $s0 ($s0 = $hi)

Phép chia
▪ Cú pháp: div $s0, $s1
▪ Kết quả (64 bit) chứa trong 2 thanh ghi
- $lo (32 bit) = $s0 / $s1 (thương)
- $hi (32 bit) = $s0 % $s1 (số dư)

Thao tác số dấu chấm động
▪ MIPS sử dụng 32 thanh ghi dấu phẩy động để biểu diễn độ chính xác đơn của số thực.
Các thanh ghi này có tên là : $f0 – $f31.
▪ Để biểu diễn độ chính xác kép (double precision) thì MIPS sử dụng sự ghép đôi của 2 thanh ghi có độ chính xác đơn.

Vấn đề tràn số
▪ Kết quả phép tính vượt qua miền giá trị cho phép ⇒ Tràn số xảy ra
▪ Một số ngôn ngữ có khả năng phát hiện tràn số (Ada), một số không (C)
▪ MIPS cung cấp 2 loại lệnh số học:
- add, addi, sub: Phát hiện tràn số
- addu, addiu, subu: Không phát hiện tràn số
▪ Trình biên dịch sẽ lựa chọn các lệnh số học tương ứng
- Trình biên dịch C trên kiến trúc MIPS sử dụng addu, addiu, subu

Phần 2: Di chuyển dữ liệu

▪ Một số nhận xét:
- Ngoài các biến đơn, còn có các biến phức tạp thể hiện nhiều kiểu cấu trúc dữ liệu khác nhau, ví dụ như array
- Các cấu trúc dữ liệu phức tạp có số phần tử dữ liệu nhiều hơn số thanh ghi của CPU ⇒ làm sao lưu ??
⇒ Lưu phần nhiều data trong RAM, chỉ load 1 ít vào thanh ghi của CPU khi cần xử lý
- Vấn đề lưu chuyển dữ liệu giữa thanh ghi và bộ nhớ ?
⇒ Nhóm lệnh lưu chuyển dữ liệu (data transfer)

Bộ nhớ chính
▪ Có thể được xem như là array 1 chiều rất lớn, mỗi phần tử là 1 ô nhớ có kích thước bằng nhau
▪ Các ô nhớ được đánh số thứ tự từ 0 trở đi
⇒ Gọi là địa chỉ (address) ô nhớ
▪ Để truy xuất dữ liệu trong ô nhớ cần phải cung cấp địa chỉ ô nhớ đó

Cấu trúc lệnh
▪ Cú pháp: opt opr, opr1 (opr2)
- opt (operator): Tên thao tác (Load / Save)
- opr (operand): Thanh ghi lưu từ nhớ (word)
- opr1 (operand 1): Hằng số nguyên
- opr2 (operand 2): Thanh ghi chứa địa chỉ vùng nhớ cơ sở (địa chỉ nền)

Hai thao tác chính
▪ lw: Nạp 1 từ dữ liệu, từ bộ nhớ, vào 1 thanh ghi trên CPU (Load Word - lw).

lw $t0, 12 ($s0)

Nạp từ nhớ có địa chỉ ($s0 + 12) chứa vào thanh ghi $t0

▪ sw: Lưu 1 từ dữ liệu, từ thanh ghi trên CPU, ra bộ nhớ (Store Word – sw)

sw $t0, 12 ($s0)

Lưu giá trị trong thanh ghi $t0 vào ô nhớ có địa chỉ ($s0 + 12)

Lưu ý

▪ $s0 được gọi là thanh ghi cơ sở (base register) thường dùng để lưu địa chỉ bắt đầu của mảng / cấu trúc
▪ 12 gọi là độ dời (offset) thường dùng để truy cập các phần tử mảng hay cấu trúc

▪ Một thanh ghi có lưu bất kỳ giá trị 32 bit nào, có thể là số nguyên (có dấu / không dấu), có thể là địa chỉ của 1 vùng nhớ trên RAM
▪ Ví dụ:
- add $t2, $t1, $t0 ⇒ $t0, $t1 lưu giá trị
- lw $t2, 4 ($t0) ⇒ $t0 lưu địa chỉ (C: con trỏ)

▪ Số biến cần dùng của chương trình nếu nhiều hơn số thanh ghi của CPU?
▪ Giải pháp:
- Thanh ghi chỉ chứa các biến đang xử lý hiện hành và các biến thường sử dụng
- Kỹ thuật spilling register

Ví dụ 1

▪ Giả sử A là 1 array gồm 100 từ với địa chỉ bắt đầu (địa chỉ nền – base address) chứa trong thanh ghi $s3. Giá trị các biến g, h lần lượt chứa trong các thanh ghi $s1 và $s2
▪ Hãy chuyển thành mã hợp ngữ MIPS: g = h + A[8]
▪ Trả lời:

lw $t0, 32($s3) # Chứa A[8] vào $t0

add $s1, $s2, $t0

Ví dụ 2
▪ Hãy chuyển thành mã hợp ngữ MIPS: A[12] = h - A[8]
▪ Trả lời:

lw $t0, 32($s3) # Chứa A[8] vào $t0

sub $t0, $s2, $t0

sw $t0, 48($s3) # Kết quả vào A[12]

Nguyên tắc lưu dữ liệu trong bộ nhớ
▪ MIPS thao tác và lưu trữ dữ liệu trong bộ nhớ theo 2 nguyên tắc:
- Alignment Restriction
- Big Endian

Alignment Restriction-
MIPS lưu dữ liệu trong bộ nhớ theo nguyên tắc Alignment Restriction
- Các đối tượng lưu trong bộ nhớ (từ nhớ) phải bắt đầu tại địa chỉ là bội số của kích thước đối tượng
- Mà mỗi từ nhớ có kích thước là 32 bit = 4 byte = kích thước lưu trữ của 1 thanh ghi trong CPU
⇒ Như vậy, từ nhớ phải bắt đầu tại địa chỉ là bội số của 4

Big Endian
▪ MIPS lưu trữ thứ tự các byte trong 1 word trong bộ nhớ theo nguyên tắc Big Endian (Kiến trúc x86 sử dụng
Little Endian)
▪ Ví dụ: Lưu trữ giá trị 4 byte: 12345678h trong bộ nhớ

Lưu ý
▪ Để truy xuất vào 1 từ nhớ sau 1 từ nhớ thì cần tăng 1 lượng 4 byte chứ không phải 1 byte
▪ Do đó luôn nhớ rằng các lệnh lw và sw thì độ dời (offset) phải là bội số của 4
▪ Tuy nhiên bộ nhớ các máy tính cá nhân ngày nay lại được đánh địa chỉ theo từng byte (8 bit)

Mở rộng: Load, Save 1 byte
▪ Ngoài việc hỗ trợ load, save 1 từ (lw, sw), MIPS còn hỗ trợ load, save từng byte (ASCII)
- Load byte: lb
- Save byte: sb
- Cú pháp lệnh tương tự lw, sw
▪ Ví dụ: lb $s0, 3 ($s1)
Lệnh này nạp giá trị byte nhớ có địa chỉ ($s1 + 3) vào byte thấp của thanh ghi $s0

Nguyên tắc
▪ Giả sử nạp 1 byte có giá trị xzzz zzzz vào thanh ghi trên CPU (x: bit dấu của byte đó)
▪ Giá trị thanh ghi trên CPU (32 bit) sau khi nạp có dạng: xxxx xxxx xxxx xxxx xxxx xxxx xzzz zzzz
⇒ Tất cả các bit từ phải sang sẽ có giá trị = bit dấu của giá trị 1 byte vừa nạp (sign-extended)
⇒ Nếu muốn các bit còn lại từ phải sang có giá trị không theo bit dấu (=0) thì dùng lệnh: lbu (load byte unsigned)

▪ MIPS còn hỗ trợ load, save 1/2 word (2 byte) (Unicode)
- Load half: lh (nạp 2 byte nhớ vào 2 byte thấp của thanh ghi $s0)
- Store half: sh
- Cú pháp lệnh tương tự lw, sw
▪ Ví dụ: lh $s0, 3 ($s1)
Lệnh này nạp giá trị 2 byte nhớ có địa chỉ ($s1 + 3) vào 2 byte thấp của thanh ghi $s0

Phần 3: Thao tác luận lý

▪ Chúng ta đã xem xét các thao tác số học (+, -, *, /)
- Dữ liệu trên thanh ghi như 1 giá trị đơn (số nguyên có dấu / không dấu)
▪ Cần thao tác trên từng bit của dữ liệu ⇒ Thao tác luận lý
- Các thao tác luận lý xem dữ liệu trong thanh ghi là dãy 32 bit riêng lẻ thay vì 1 giá trị đơn
▪ Có 2 loại thao tác luận lý:
- Phép toán luận lý
- Phép dịch luận lý

Phép toán luận lý
▪ Cú pháp: opt opr, opr1, opr2
- opt (operator): Tên thao tác
- opr (operand): Thanh ghi (toán hạng đích) chứa kết quả
- opr1 (operand 1): Thanh ghi (toán hạng nguồn 1)
- opr2 (operand 2): Thanh ghi / hằng số (toán hạng nguồn 2)

▪ MIPS hỗ trợ 2 nhóm lệnh cho các phép toán luận lý trên bit:
- and, or, nor: Toán hạng nguồn thứ 2 (opr2) phải là thanh ghi
- andi, ori: Toán hạng nguồn thứ 2 (opr2) là hằng số
▪ Lưu ý: MIPS không hỗ trợ lệnh cho các phép luận lý NOT, XOR, NAND…
▪ Lý do: Vì với 3 phép toán luận lý and, or, nor ta có thể tạo ra tất cả các phép luận lý khác ⇒ Tiết kiệm thiết kế cổng mạch
▪ Ví dụ: not (A) = not (A or 0) = A nor 0

Phép dịch luận lý

▪ Cú pháp: opt opr, opr1, opr2
- opt (operator): Tên thao tác
- opr (operand): Thanh ghi (toán hạng đích) chứa kết quả
- opr1 (operand 1): Thanh ghi (toán hạng nguồn 1)
- opr2 (operand 2): Hằng số < 32 (Số bit dịch)

▪ MIPS hỗ trợ 2 nhóm lệnh cho các phép dịch luận lý trên bit:
- Dịch luận lý
+ Dịch trái (sll – shift left logical): Thêm vào các bit 0 bên phải
+ Dịch phải (srl – shift right logical): Thêm vào các bit 0 bên trái
- Dịch số học
+ Không có dịch trái số học
+ Dịch phải (sra – shift right arithmetic): Thêm các bit = giá trị bit dấu bên trái

Ví dụ

▪ sll $s1, $s2, 2 # dịch trái luận lý $s2 2 bit

$s2 = 0000 0000 0000 0000 0000 0000 0101 0101 = 85

$s1 = 0000 0000 0000 0000 0000 0001 0101 0100 = 340
▪ srl $s1, $s2, 2 (85 * 2 ² )
# dịch phải luận lý $s2 2 bit

$s2 = 0000 0000 0000 0000 0000 0000 0101 0101 = 85

$s1 = 0000 0000 0000 0000 0000 0000 0001 0101 = 21 (85 / 2 ² )
▪ sra $s1, $s2, 2 # dịch phải số học $s2 2 bit

$s2 = 1111 1111 1111 1111 1111 1111 1111 0000 = -16

$s1 = 1111 1111 1111 1111 1111 1111 1111 1100 = -4 (-16 /2 ² )

Phần 4: Rẽ nhánh

▪ Tương tự lệnh if trong C: Có 2 loại
- if (condition) clause
- if (condition) clause1 else clause2
▪ Lệnh if thứ 2 có thể diễn giải như sau:

if (condition) goto L1 // if ⇒ Làm clause1

clause2 // else ⇒ Làm clause2

goto L2 // Làm tiếp các lệnh khác
L1: clause1
L2:

Rẽ nhánh trong MIPS
▪ Rẽ nhánh có điều kiện
- beq opr1, opr2, label
+ beq: Branch if (register are) equal
+ if (opr1 == opr2) goto label
- bne opr1, opr2, label
+ bne: Branch if (register are) not equal
+ if (opr1 != opr2) goto label
▪ Rẽ nhánh không điều kiện
- j label
+ Jump to label
+ Tương ứng trong C: goto label
+ Có thể viết lại thành: beq $0, $0, label

Ví dụ
▪ Biên dịch câu lệnh sau trong C thành lệnh hợp ngữ MIPS: if (i == j) f = g + h; else f = g – h;
▪ Ánh xạ biến f, g, h, i, j tương ứng vào các thanh ghi: $s0, $s1, $s2, $s3, $s4
▪ Lệnh hợp ngữ MIPS:

Xử lý vòng lặp

▪ Xét mảng int A[]. Giả sử ta có vòng lặp trong C:

do { g = g + A[i]; i = i + j;
} while (i != h);
▪ Ta có thể viết lại:
Loop: g = g + A[i]; i = i + j; if (i != h) goto Loop;
⇒ Sử dụng lệnh rẽ có điều kiện để biểu diễn vòng lặp!

▪ Ánh xạ biến vào các thanh ghi như sau:

▪ Trong ví dụ trên có thể viết lại thành lệnh MIPS như sau:

▪ Tương tự cho các vòng lặp phổ biến khác trong C:
- while
- for
- do…while
▪ Nguyên tắc chung:
- Viết lại vòng lặp dưới dạng goto
- Sử dụng các lệnh MIPS rẽ nhánh có điều kiện

So sánh không bằng ?
▪ beq và bne được sử dùng để so sánh bằng (== và != trong C)
⇒ Muốn so sánh lớn hơn hay nhỏ hơn?
▪ MIPS hỗ trợ lệnh so sánh không bằng:
- slt opr1, opr2, opr3
- slt: Set on Less Than
- if (opr2 < opr3) opr1 = 1; else opr1 = 0;

▪ Trong C, câu lệnh sau: if (g < h) goto Less; # g: $s0, h: $s1
▪ Được chuyển thành lệnh MIPS như sau:

▪ Nhận xét: Thanh ghi $0 luôn chứa giá trị 0, nên lệnh bne và bep thường dùng để so sánh sau lệnh slt

▪ Các phép so sánh còn lại như >, ≥, ≤ thì sao?
▪ MIPS không trực tiếp hỗ trợ cho các phép so sánh trên, tuy nhiên dựa vào các lệnh slt, bne, beq ta hoàn toàn có thể biểu diễn chúng!

Nhận xét
▪ So sánh == ⇒ Dùng lệnh beq
▪ So sánh != ⇒ Dùng lệnh bne
▪ So sánh < và > ⇒ Dùng cặp lệnh (slt ⇒ bne)
▪ So sánh ≤ và ≥ ⇒ Dùng cặp lệnh (slt ⇒ beq)

So sánh với hằng số
▪ So sánh bằng: beq / bne
▪ So sánh không bằng: MIPS hỗ trợ sẵn lệnh slti
- slti opr, opr1, const
- Thường dùng cho switch…case, vòng lặp for

Ví dụ: switch…case trong C

Chuyển thành lệnh hợp ngữ MIPS:

Trình con (Thủ tục)
▪ Hàm (fucntion) trong C ⇒ (Biên dịch) ⇒ Trình con (Thủ tục) trong hợp ngữ
▪ Giả sử trong C, ta viết như sau:

• Hàm được chuyển thành lệnh hợp ngữ như thế nào ?
• Dữ liệu được lưu trữ ra sao ?

Thanh ghi lưu trữ dữ liệu trong thủ tục

▪ MIPS hỗ trợ 1 số thanh ghi để lưu trữ dữ liệu cho thủ tục:
- Đối số input (argument input): $a0 $a1 $a2 $a3
- Kết quả trả về (return …): $v0 $v1
- Biến cục bộ trong thủ tục: $s0 $s1 …
- Địa chỉ quay về (return address): $s7 $ra
▪ Nếu có nhu cầu lưu nhiều dữ liệu (đối số, kết quả trả về, biến cục bộ) hơn số lượng thanh ghi kể trên?
⇒ Bao nhiêu thanh ghi là đủ ?
⇒ Sử dụng ngăn xếp (stack)

Các lệnh nhảy mới
▪ jr (jump register)
- Cú pháp: jr register
- Diễn giải: Nhảy đến địa chỉ nằm trong thanh ghi register thay vì nhảy đến 1 nhãn như lệnh j (jump)
▪ jal (jump and link)
- Cú pháp:
- Diễn giải: Thực hiện 2 bước: jal label
+ Bước 1 (link): Lưu địa chỉ của lệnh kế tiếp vào thanh ghi $ra (Tại sao không phải là địa chỉ của lệnh hiện tại ?)
+ Bước 2 (jump): Nhảy đến nhãn label
Hai lệnh này được sử dụng hiệu quả trong thủ tục
- jal: tự động lưu địa chỉ quay về chương trình chính vào thanh ghi $ra và nhảy đến thủ tục con
- jr $ra: Quay lại thân chương trình chính bằng cách nhảy đến địa chỉ đã được lưu trước đó trong 67 $ra

Ngăn xếp (Stack)

▪ Là ngăn xếp gồm nhiều ô nhớ kết hợp (vùng nhớ) nằm trong bộ nhớ chính
▪ Cấu trúc dữ liệu lý tưởng để chứa tạm các giá trị trong thanh ghi
- Thường chứa địa chỉ trả về, các biến cục bộ của trình con, nhất là các biến có cấu trúc (array, list…) không chứa vừa trong các thanh ghi trong CPU
▪ Được định vị và quản lý bởi stack pointer
▪ Có 2 tác vụ hoạt động cơ bản:
- push: Đưa dữ liệu từ thanh ghi vào stack
- pop: Lấy dữ liệu từ stack chép vào thanh ghi
▪ Trong MIPS dành sẵn 1 thanh ghi $sp để lưu trữ stack pointer
▪ Để sử dụng Stack, cần khai báo kích vùng Stack bằng cách tăng (push) giá trị con trỏ ngăn xếp stack pointer (lưu trữ trong thanh ghi $sp)
- Lưu ý: Stack pointer tăng theo chiều giảm địa chỉ

Tổng quát: Thao tác với stack
▪ Khởi tạo stack (init)
▪ Lưu trữ tạm các dữ liệu cần thiết vào stack (push)
▪ Gán các đối số (nếu có)
▪ Gọi lệnh jal để nhảy đến các thủ tục con
▪ Khôi phục các dữ liệu đã lưu tạm từ stack (pop)
▪ Khôi phục bộ nhớ, kết thúc stack (free)

Một số nguyên tắc khi thực thi thủ tục
▪ Nhảy đến thủ tục bằng lệnh jal và quay về nơi trước đó đã gọi nó bằng lệnh jr $ra
▪ 4 thanh ghi chứa đối số của thủ tục: $a0, $a1, $a2, $a3
▪ Kết quả trả về của thủ tục chứa trong thanh ghi $v0 (và $v1 nếu cần)
▪ Phải tuân theo nguyên tắc sử dụng các thanh ghi (register conventions)

Nguyên tắc sử dụng thanh ghi
▪ $0: (Không thay đổi) Luôn bằng 0
▪ $s0 - $s7: (Khôi phục lại nếu thay đổi) Rất quan trọng, nếu thủ tục được gọi (callee) thay đổi các thanh ghi này thì nó phải khôi phục lại giá trị các thanh ghi này trước khi kết thúc
▪ $sp: (Khôi phục lại nếu thay đổi) Thanh ghi con trỏ stack phải có giá trị không đổi trước và sau khi gọi lệnh “jal”, nếu không thủ tục gọi (caller) sẽ không quay về được.
▪ Tip: Tất cả các thanh ghi này đều bắt đầu bằng ký tự s !

▪ $ra: (Có thể thay đổi) Khi gọi lệnh “jal” sẽ làm thay đổi giá trị thanh ghi này. Thủ tục gọi (caller) lưu lại (backup) giá trị của thanh ghi $ra vào stack nếu cần
▪ $v0 - $v1: (Có thể thay đổi) Chứa kết quả trả về của thủ tục
▪ $a0 - $a1: (Có thể thay đổi) Chứa đối số của thủ tục
▪ $t0 - $t9: (Có thể thay đổi) Đây là các thanh ghi tạm nên có thể bị thay đổi bất cứ lúc nào

▪ Nếu thủ tục R gọi thủ tục E:
- R phải lưu vào stack các thanh ghi tạm có thể bị sử dụng trong E trước khi gọi lệnh jal E (goto E)
- E phải lưu lại giá trị các thanh ghi lưu trữ ($s0 - $s7) nếu nó muốn sử dụng các thanh ghi này ⇒ trước khi kết thúc E sẽ khôi phục lại giá trị của chúng
- Nhớ: Thủ tục gọi R (caller) và Thủ tục được gọi E (callee) chỉ cần lưu các thanh ghi tạm / thanh ghi lưu trữ mà nó muốn dùng, không phải tất cả các thanh ghi!

Hello.asm

Phụ lục 1: 40 lệnh cơ bản MIPS

Phụ lục 2: Pseudo Instructions
▪ “Lệnh giả”: Mặc định không được hỗ trợ bởi MIPS
▪ Là những lệnh cần phải biên dịch thành rất nhiều câu lệnh thật trước khi được thực hiện bởi phần cứng
⇒ Lệnh giả = Thủ tục
▪ Dùng để hỗ trợ lập trình viên thao tác nhanh chóng với những thao tác phức tạp gồm nhiều bước

Ví dụ: Tính $s1 = |$s0|
▪ Để tính được trị tuyết đối của $s0 ⇒ $s1, ta có lệnh giả là: abs $s1, $s0
▪ Thực sự MIPS không có lệnh này, khi chạy sẽ biên dịch lệnh này thành các lệnh thật sau:

Một số lệnh giả phổ biến của MIPS

Phụ lục 3: Biểu diễn lệnh trong ngôn ngữ máy

▪ Chúng ta đã học 1 số nhóm lệnh hợp ngữ thao tác trên CPU tuy nhiên…
▪ CPU có hiểu các lệnh hợp ngữ đã học này không?
⇒ Tất nhiên là không vì nó chỉ hiểu được ngôn ngữ máy gồm toàn bit 0 và 1
▪ Dãy bit đó gọi là lệnh máy (machine language instruction)
▪ Mỗi lệnh máy có kích thước 32 bit, được chia thành các nhóm bit, gọi là trường (fiedld), mỗi nhóm có 1 vai trò trong lệnh máy
▪ Lệnh máy có 1 cấu trúc xác định gọi là cấu trúc lệnh (Instruction Format)

MIPS Instruction Format

▪ Có 3 format lệnh trong MIPS:
- R-format: Dùng trong các lệnh tính toán số học (add, sub, and, or, nor, sll, srl, sra…)
- I-format: Dùng trong các lệnh thao tác với hằng số, chuyển dữ liệu với bộ nhớ, rẽ nhánh
- J-format: Dùng trong các lệnh nhảy (jump – C: goto)

R-format

- opcode (operation code): mã thao tác, cho biết lệnh làm gì
- funct (function code): kết hợp với opcode để xác định lệnh làm gì (trường hợp các lệnh có cùng mã thao tác với opcode)
- rs (source register): thanh ghi nguồn, thường chứa toán hạng nguồn thứ 1
- rt (target register): thanh ghi nguồn, thường chứa toán hạng nguồn thứ 2
- rd (destination register): thanh ghi đích, thường chứa kết quả lệnh
- shamt: chứa số bit cần dịch trong các lệnh dịch, nếu không phải lệnh dịch thì trường này có giá trị 0

▪ Các trường lưu địa chỉ thanh ghi rs, rt, rd có kích thước 5 bit
⇒ Có khả năng biểu diễn các số từ 0 đến 31
⇒ Đủ để biểu diễn 32 thanh ghi của MIPS
▪ Trường lưu số bit cần dịch shamt có kích thước 5 bit
⇒ Có khả năng biểu diễn các số từ 0 đến 31
⇒ Đủ để dịch hết 32 bit lưu trữ của 1 thanh ghi

▪ Biểu diễn machine code của lệnh: add $t0, $t1, $t2
▪ Biểu diễn lệnh với R-format theo từng trường:

▪ Làm sao giải quyết trường hợp nếu câu lệnh đòi hỏi trường dành cho toán hạng phải lớn hơn 5 bit?
▪ Ví dụ:
- Lệnh addi cộng giá trị thanh ghi với 1 hằng số, nếu giới hạn trường hằng số ở 5 bit
⇒ hằng số không thể lớn hơn 2 5 = 32
⇒ Giới hạn khả năng tính toán số học!
- Lệnh lw, sw cần biểu diễn 2 thanh ghi và 1 hằng số offset, nếu giới hạn ở 5 bit
⇒ Giới hạn khả năng truy xuất dữ liệu trong bộ nhớ
- Lệnh beq, bne cần biểu diễn 2 thanh ghi và 1 hằng số chứa địa chỉ (nhãn) cần nhảy, nếu giới hạn ở 5 bit
⇒ Giới hạn lưu trữ chương trình trong bộ nhớ
▪ Giải pháp: Dùng I-format cho các lệnh thao tác hằng số, truy xuất dữ liệu bộ nhớ và rẽ nhánh

I-format

▪ opcode (operation code): mã thao tác, cho biết lệnh làm gì (tương tự opcode của R-format, chỉ khác không cần thêm trường funct). Đây cũng là lý do tại sao R-format có 2 trường 6 bit để xác định lệnh làm gì thay vì 1 trường 12 bit ⇒ Để nhất quán với các cấu trúc lệnh khác (I-format) trong khi kích thước mỗi trường vẫn hợp lý

▪ rs (source register): thanh ghi nguồn, thường chứa toán hạng nguồn thứ 1
▪ rt (target register): thanh ghi đích, thường chứa kết quả lệnh
▪ immediate: 16 bit, có thể biểu diễn số nguyên từ -2 15 đến (2 15 – 1)
▪ I-format đã có thể lưu hằng số 16 bit (thay vì 5 bit như R-format)

▪ Biểu diễn machine code của lệnh: addi $s0, $s1, 10
▪ Biểu diễn lệnh với R-format theo từng trường: opcode rs rt immediate

▪ opcode = 8: Xác định thao tác cộng hằng số
▪ rs = 17 (toán hạng nguồn thứ 1 là $s1 ~ $17)
▪ rt = 16 (toán hạng đích là $s0 ~ $16)
▪ immediate = 10 (toán hạng nguồn thứ 2 = hằng số = 10)

▪ Trường hằng số (immediate) có kích thước 16 bit
▪ Nếu muốn thao tác với các hằng số 32 bit?
⇒ Tăng kích thước trường immediate thành 32 bit?
⇒ Tăng kích thước các lệnh thao tác với hằng số có cấu trúc I-format
⇒ Phá vỡ cấu trúc lệnh 32 bit của MIPS

▪ Giải pháp: MIPS cung cấp lệnh mới “lui”
- lui register, immediate
- Load Upper Immediate
- Đưa hằng số 16 bit vào 2 byte cao của 1 thanh ghi
- Giá trị 2 byte thấp của thanh ghi đó gán = 0
- Lệnh này có cấu trúc I-format

Vấn đề rẽ nhánh có điều kiện trong I-format

▪ Các lệnh rẽ nhánh có điều kiện có cấu trúc I-format

▪ opcode: xác định lệnh beq hay bne
▪ rs, rt: chứa các giá trị của thanh ghi cần so sánh
▪ immediate chứa địa chỉ (nhãn) cần nhảy tới?
- immediate chỉ có 16 bit ⇒ chỉ có thể nhảy tới địa chỉ từ 0 – 2 ¹⁶ (65535) ?
⇒ Chương trình bị giới hạn không gian rất nhiều
▪ Câu trả lời: immediate KHÔNG phải chứa địa chỉ cần nhảy tới

▪ Trong MIPS, thanh ghi PC (Program Counter) sẽ chứa địa chỉ của lệnh đang được thực hiện
▪ immediate: số có dấu, chứa khoảng cách so với địa chỉ lệnh đang thực hiện nằm trong thanh ghi PC
- immediate + PC ⇒ địa chỉ cần nhảy tới
▪ Cách xác định địa chỉ này gọi là PC-Relative Addressing (định vị theo thanh ghi PC)
- Xem slide “Addressing Mode” (phần sau) để biết thêm về các Addressing mode trong MIPS

▪ Mỗi lệnh trong MIPS có kích thước 32 bit (1 word – 1 từ nhớ)
▪ MIPS truy xuất bộ nhớ theo nguyên tắc Alignment Restriction
⇒ Đơn vị của immediate, khoảng cách so với PC, là từ nhớ (word = 4 byte) chứ không phải là byte
⇒ Các lệnh rẽ nhánh có thể nhảy tới các địa chỉ có khoảng cách ± 2 ¹⁵ word tính từ địa chỉ lưu trong PC (±2 ¹⁷ byte)

▪ Cách tính địa chỉ rẽ nhánh:
- Nếu không rẽ nhánh:
PC = PC + 4 = địa chỉ lệnh kế tiếp trong bộ nhớ
- Nếu thực hiện rẽ nhánh:
PC = (PC + 4) + (immediate * 4)
▪ Vì sao cộng immediate với (PC + 4) thay vì PC? ⇒ Khi rẽ nhánh bị delayed 1 lệnh kề với lệnh rẽ nhánh
▪ Nhận xét: immediate cho biết số lệnh cần nhảy qua để đến được nhãn

Ví dụ I-format

Vấn đề I-format
▪ Mỗi lệnh trong MIPS có kích thước 32 bit
▪ Mong muốn: Có thể nhảy đến bất kỳ lệnh nào (MIPS hỗ trợ các hàm nhảy không điều kiện như j)
⇒ Nhảy trong khoảng 2 32 (4 GB) bộ nhớ
⇒ I-format bị hạn chế giới hạn vùng nhảy
⇒ Dùng J-format
▪ Tuy nhiên, dù format nào cũng phải cần tối thiểu 6 bit cho opcode để nhất quán lệnh với các format khác
⇒ J-format chỉ có thể dùng 32 – 6 = 26 bit để biểu diễn khoảng cách nhảy

J-format

▪ opcode (operation code): mã thao tác, cho biết lệnh làm gì (tương tự opcode của R-format và I-format) Để nhất quán với các cấu trúc lệnh khác (R-format và I-format)

▪ target address: Lưu địa chỉ đích của lệnh nhảy Tương tự lệnh rẽ nhánh, địa chỉ đích của lệnh nhảy tính theo đơn vị word

Nhận xét
▪ Trong J-format, các lệnh nhảy có thể nhảy tới các lệnh có địa chỉ trong khoảng 2 ²⁶
▪ Muốn nhảy tới các lệnh có địa chỉ lớn hơn từ 2 ²⁷ đến 2 ³² ?
- MIPS hỗ trợ lệnh jr (đọc trong phần thủ tục)
- Tuy nhiên nhu cầu này không cần thiết lắm vì chương trình thường không quá lớn như vậy

Bảng tóm tắt Format

Tài liệu toán

Toán cấp 2

Tài liệu toán 10

Minh họa CTDL & GT