Hợp ngữ MIPS

Hợp ngữ (Assembly language) là ngôn ngữ có khả năng chuyển đổi 1-1 sang ngôn ngữ máy. Bài viết này sẽ trình bày hợp ngữ dành cho các dòng máy có kiến trúc MIPS.

Để lập trình và chạy hợp ngữ MIPS, có thể dùng Mars: courses.missouristate.edu/KenVollmar/mars/

CISC và RISC

Hợp ngữ và kiến trúc máy tính được chi làm 2 loại: CICS và RISC. Đại diện tiêu biểu cho CISC là x86 - được sử dụng trên các máy tính cá nhân và server. Đại diện cho RISC là ARM và MIPS. ARM được sử dụng trong các thiết bị di động và MIPS được sử dụng trong một số siêu máy tính, và các thiết bị như router, Nintendo 64, Sony Playstation 2.

Khác biệt giữa CISC và RISC:

CISC là Complex insrtuction set computer và RICS là Reduced instruction set computer. Hợp ngữ của CISC rất phức tạp và ngược lại RISC thì đơn giản hơn, vì vậy các máy CISC tiêu tốn điện năng nhiều hơn các máy RISC.

Các bạn có thể đọc thêm về so sánh CISC và RISC ở đây: cs.stanford.edu/people/eroberts/courses/soco/projects/risc/risccisc/

Thanh ghi

MIPS có tổng cộng 32 thanh ghi (register) để lưu giá trị, được đánh số từ 0 đến 31. Để truy cập và thao tác trên một thanh ghi, ta dùng cú pháp $ + số thứ tự thanh ghi. Ví dụ: $0, $1, $10,…

Ngoài ra, MIPS có quy ước mục đích sử dụng của mỗi thanh ghi, khi lập trình nên tuân thủ các quy ước này. Vì thế, người ta thường truy cập thanh ghi thông qua tên của chúng:

MIPS có tư tưởng register-to-register - load/store, nghĩa là các lệnh đều thao tác trên thanh ghi. Khi cần sử dụng bộ nhớ, ta sẽ có các lệnh riêng để nạp dữ liệu từ bộ nhớ vào thanh ghi.

Mỗi thanh ghi lưu trữ một giá trị 32-bit. Không như khái niệm biến ngôn ngữ lập trình cấp cao, thanh ghi trong hợp ngữ không có kiểu dữ liệu, cách ta sử dụng thanh ghi sẽ quyết định kiểu dữ liệu là gì.

Các cấu trúc lệnh của MIPS

Phần này trình bày cấu trúc của các lệnh hợp ngữ khi được dịch sang ngôn ngữ máy. Mỗi lệnh trong MIPS đều có độ dài là 32 bit.

Có thể xem mỗi lệnh như một hàm trong ngôn ngữ lập trình. Vì vậy, ta cần có tên lệnh, các tham số truyền vào và kiểu của các tham số truyền vào - trong trường hợp này là kích thước của mỗi tham số truyền vào (vì không có khái niệm kiểu dữ liệu trong hợp ngữ).

MIPS chú trọng tính đơn giản của tập lệnh, vì vậy chỉ có 3 kiểu lệnh chính: R-format, I-format, J-format.

R-format

R-format có 6 tham số:

Giải thích:

• op: opcode, trường này sẽ cho máy biết lệnh này là lệnh nào. Trong trường hợp R-format thì các lệnh đều dùng chung opcode là 0.
• rs, rt: source register và destination register, 2 thanh ghi cần thực hiện tính toán.
• rd: register destination, thanh ghi lưu kết quả của lệnh.
• shamt: shift amount, số bit cần dịch trong lệnh dịch trái và dịch phải.
• funct: Vì các lệnh R-format đều có chung opcode bằng 0 nên ta thêm trường này để cho máy biết cần thực hiện lệnh nào.

I-format

Lệnh I-format dùng cho thao tác giữa thanh ghi và một hằng số được lưu sẵn trong lệnh. Cấu trúc như sau:

Giải thích:

• op: opcode, cho máy biết đây là lệnh gì. Vì I-format không có trường funct nên các lệnh I-format không dùng chung opcode như các lệnh R-format.
• rs, rt: source register và target register.
• immediate: Một giá trị hằng số mà lệnh sử dụng.

J-format

J-format dành cho các lệnh nhảy (goto trong C), có cấu trúc:

Giải thích:

• op: opcode, cho máy biết đây là lệnh gì.
• target address: Địa chỉ rút gọn của lệnh cần nhảy đến, địa chỉ gốc có 32 bit, ta rút gọn 6 bit như sau:
  • Xóa 2 bit thấp nhất của địa chỉ. Vì địa chỉ của các lệnh trong MIPS luôn chia hết cho 4 nên 2 bit thấp nhất luôn bằng 0.
  • 4 bit cao nhất xem như bằng với 4 bit cao nhất của lệnh hiện tại.

Các lệnh tính toán

Lệnh cộng và trừ

4 lệnh add, sub, addu, subu dùng để cộng/trừ giá trị của 2 thanh ghi, và lưu kết quả vào thanh ghi đích. Cú pháp:

<tên lệnh> <thanh ghi đích>, <thanh ghi 1>, <thanh ghi 2>

2 lệnh addi, addiu dùng để cộng một thanh ghi với 1 hằng số, rồi lưu vào thanh ghi đích. Cú pháp:

<tên lệnh> <thanh ghi đích>, <thanh ghi>, <hằng số>

Ví dụ:

add $s0, $s1, $s2 # $s0 = $s1 + $s2
sub $s0, $s1, $s2 # $s0 = $s1 - $s2 
addi $s0, $s0, 123 # $s0 = $s0 + 123
addi $s0, $s2, -123 # $s0 = $s2 - 123

Khác biệt giữa addu và add: add sẽ báo lỗi khi có tràn số, còn addu thì không. Tương tự với các lệnh có u và không có u khác.

Các lệnh tính toán logic

Có 3 lệnh: and, or, nor. NOR là thao tác “NOT OR”: A nor B = not (A or B). Cú pháp của 3 lệnh này tương tự như lệnh add ở trên.

Tương tự, ta cũng có lệnh andi và ori để tính AND/OR của một thanh ghi với một hằng số.

Các phép toán logic khác có thể được tính từ 3 phép trên:

not A = A nor 0
A xor B = (A or B) and (not A or not B) = (A and not B) or (not A and B)

Tính toán với các hằng số 32 bit

Dễ thấy các lệnh thao tác với hằng số ở trên đều có giới hạn 16 bit cho hằng số. Để giải quyết vấn đề này, MIPS cung cấp lệnh lui (load upper immediate) với chức năng ghi một hằng số 16-bit vào 2 byte cao của thanh ghi, 2 byte thấp sẽ được gán bằng 0.

Ví dụ, ta cần cộng $s0 cho giá trị 0x12345678:

lui $t0, 0x1234
ori $t0, $t0, 0x5678
add $s0, $s0, $t0

Lệnh dịch

2 lệnh sll và srl dùng để dịch trái và dịch phải. Đây là dịch logic, các giá trị trống sau khi dịch luôn là 0.

Cú pháp tương tự như addi ở trên, tuy nhiên số bit cần dịch luôn là một số không âm từ 0 đến 31.

Các lệnh thao tác bộ nhớ

Mô hình bộ nhớ của MIPS

Khi cần tính toán với các giá trị được lưu trên RAM, ta phải nạp giá trị lên thanh ghi trước khi tính, sau đó lưu lại kết quả vào RAM (nếu cần).

Đơn vị nhớ nhỏ nhất mà MIPS có thể xử lý là byte (8 bit). MIPS cung cấp các lệng load/store với các kích thước 1, 2 và 4 byte. Tuy nhiên có quy tắc Alignment Restriction sau: “Địa chỉ vùng nhớ cần truy cập phải chia hết cho kích thước cần truy cập”. Ví dụ, đọc 4 byte bắt đầu từ ô nhớ có địa chỉ 10 là không hợp lệ.

Ngoài ra, MIPS lưu trữ dữ liệu theo dạng Big Endian, tức là byte cao sẽ được lưu ở địa chỉ thấp. Ví dụ, số 12345678h (thập lục phân) khi được lưu trong bộ nhớ thì byte đầu tiên sẽ là 12h, byte tiếp theo là 34,…

Lệnh load/store

Cú pháp:

tên lệnh r1, offset(r2)

Trong đó:

• r1: thanh ghi cần nạp dữ liệu vào / lấy dữ liệu ra.
• r2: thanh ghi lưu địa chỉ gốc.
• offset: hằng số nguyên (16 bit), giá trị này sẽ được cộng với giá trị của r2 để được địa chỉ cần nạp vào / lấy ra.

Tên các lệnh:

• lw (load word), lh (load halfword), lb (load byte): Đọc 4/2/1 byte. Đối với lh và lb, vì thanh ghi có độ dài 4 byte, nhiều hơn lượng dữ liệu đọc được nên các bit trống sẽ được gán bằng bit dấu của số đọc được.
• lhu (load halfword unsigned), lbu (load byte unsigned): tương tự như trên, tuy nhiên các bit trống được gán bằng 0.
• sw (store word), sh (store halfword), sb (store byte): lưu 4/2/1 byte dữ liệu trong thanh ghi vào bộ nhớ.

Ví dụ, ta có một mảng int *x được lưu trong $s0:

lw $s1, 0($s0) # $s1 = *x
lw $s1, 4($s0) # $s1 = x[1]
sw $s1, 8($s0) # x[2] = $s1

Một số lưu ý:

• Các lệnh trên đều phải tuân theo quy tắc Alignment Restriction ở trên.
• Đối với sh và sb sẽ lưu các byte thấp trong thanh ghi vào bộ nhớ.
• Dữ liệu trong thanh ghi và bộ nhớ đều tuân theo quy tắc Big Endian.

Các lệnh điều khiển

Khi chương trình được thực thi, máy sẽ nạp chương trình lên bộ nhớ, đồng thời có một thanh ghi dành riêng để lưu địa chỉ của lệnh đang được thực thi, đây gọi là thanh ghi PC (program counter). Mỗi lần thực hiện xong một lệnh, mặc định PC sẽ được tự động tăng lên để chuyển sang lệnh tiếp theo.

Công việc của các lệnh điều khiển như nhảy, rẽ nhánh là gán lại địa chỉ của thanh ghi PC, để chương trình chuyển sang một đoạn khác.

Lệnh nhảy

Lệnh nhảy tương tự như goto trong C, có 2 lệnh nhảy là j và jr, ngoài ra còn có jal nhưng ta sẽ tìm hiểu lệnh này sau.

Cú pháp lệnh j:

j <đỉa chỉ cần nhảy tới hoặc nhãn>

Thông thường, khi viết hợp ngữ ta chỉ cần dùng nhãn, trình dịch hợp ngữ sẽ tự chuyển đổi sang địa chỉ, ví dụ:

loop:
    addi $s0, $s0, 1
    j loop

Đoạn chương trình tên là một vòng lặp vô hạn.

jr cũng tương tự như j, tuy nhiên ta đọc địa chỉ lệnh cần nhảy đến trong một thanh ghi. Ví dụ:

jr $ra

Cách hoạt động của lệnh nhảy:

• Lệnh jr sẽ gán PC bằng với thanh ghi được chỉ định
• Ở lệnh j vì, tham số truyền vào chỉ có 26 bit, mà PC lại có đến 32 bit nên ta tính lại PC như sau: PC = (PC & 0xf0000000) | (imm << 2), với imm là tham số truyền vào.

Lệnh rẽ nhánh

Lệnh rẽ nhánh sẽ thực hiện 2 thao tác: so sánh và nhảy khi thỏa điều kiện.

Có 2 lệnh rẽ nhánh là beq (branch if equal) và bne (branch if not equal). Cú pháp:

<Tên lệnh> <thanh ghi 1>, <thanh ghi 2>, <địa chỉ hoặc nhãn>

Lệnh beq sẽ so sánh giá trị trong 2 thanh ghi, nếu bằng nhau thì nhảy đến nhãn chỉ định. Lệnh bne thì ngược lại, nhảy khi 2 giá trị khác nhau. Khi không nhảy, chương trình sẽ thực hiện lệnh tiếp theo.

Địa chỉ truyền vào là địa chỉ tương đối và có dấu, PC sẽ được tính lại như sau: PC = PC + 4 + imm, với imm là địa chỉ truyền vào.

Để so sánh lớn hơn/bé hơn, MIPS đưa thêm lệnh slt (set on less than). Cú pháp:

slt rt, rs, rd

Với rt, rs, rd là các thanh ghi. Lệnh này sẽ gán rt bằng 1 khi rs < rd, bằng 0 trong trường hợp ngược lại.

So sánh trong lệnh trên là so sánh có dấu (bù 2). Để so sánh không dấu, MIPS hỗ trợ lệnh stlu, cách dùng tương tự như trên.

Ngoài ra, cũng có lệnh để so sánh với một hằng số, là slti và sltiu. Cú pháp tương tự như các lệnh tính toán với hằng số ở trên.

Kết hợp các lệnh đã tìm hiểu, ta có thể dịch đoạn chương trình C sau sang hợp ngữ MIPS:

int n = 1000;
int s = 0;
for (int i=1; i<n; i++) s += i;

addi $s0, $0, 1000 # n = 1000
addi $s1, $0, 0    # s = 0
addi $s2, $0, 1    # i = 1
FOR:
slt $t0, $s2, $s0  # $t0 = i < n?
bne $t0, $0, END   # if !(i < n) goto END
add $s1, $s1, $s2  # s = s + i
addi $s2, $s2, 1   # i = i + 1
j FOR
END:

Thủ tục trong hợp ngữ

Trong hợp ngữ, sử dụng thủ thục thực chất là nhảy đến đoạn code của thủ tục đó. Tuy nhiên có một số vấn đề phát sinh:

• Làm thế nào để biết lệnh nào được thực thi sau khi kết thúc thủ tục?
• Truyền các tham số vào thủ tục như thế nào?
• Thanh ghi nào để lưu giá trị trả về?
• Quản lý việc sử dụng thanh ghi giữa các thủ tục như thế nào? Vì thủ tục được gọi có thể thay đổi các thanh ghi được dùng trong thủ tục gọi.

MIPS giải quyết các vấn đề này bằng một số quy ước, khi lập trình ta nên tuân thủ theo các quy ước này để code có tính tái sử dụng cao và hạn chế sai lầm từ người lập trình.

Vị trí quay về

Ví dụ đoạn code C sau được dịch sang hợp ngữ ở dưới:

void die() {
    int x = 0xffffffff;
}

void man() {
    die();
    int x = 0;
}

die:
    nor $s0, $0, $0
    j L1

man:
    j die
    L1:
    or $s0, $0, $0

Sau khi thực hiện xong hàm die thì chương trình sẽ nhảy về L1 để tiếp tục thực thi hàm man. Nhưng chuyện xảy ra nếu có một hàm khác cũng gọi die:

void woman() {
    die();
    int x = 0x0000ffff;
}

Ta thấy nếu hàm woman gọi die thì địa chỉ nhảy về sẽ khác với khi man gọi die.

Để giải quyết vấn đề này, MIPS cung cấp lệnh jal (jump and link). jal sẽ gán giá trị thanh ghi $ra bằng với địa chỉ của lệnh tiếp theo trước khi thực hiện nhảy. Như vậy, sau khi thực hiện xong, hàm được gọi chỉ cần jr $ra để nhảy về đúng lệnh cần nhảy:

die:
    nor $s0, $0, $0
    jr $ra

man:
    jal die
    or $s0, $0, $0

woman:
    jal die
    lui $t0, 0x0000
    ori $s0, $t0, 0xffff

$sp - Bộ nhớ stack

Giả sử có 3 hàm gọi nhau, sử dụng $ra như trên:

void baz() {
    int x = 0;
}
void bar() {
    int x = 1;
    baz();
    int y = x > 0;
}
void foo() {
    int x = 2;
    bar();
}

baz:
    ori $s0, $0, 0
    jr $ra
bar:
    ori $s0, $0, 1
    jal baz
    slt $s1, $0, $s0
    jr $ra
foo:
    ori $s0, $0, 2
    jal bar
    jr $ra

Ta thấy ngay 2 vấn đề:

• Thanh ghi $ra sẽ bị thay đổi khi bar gọi baz, vì vậy sau đó bar sẽ không trả về đúng địa chỉ nữa.
• Thanh ghi $s0 bị thay đổi trong hàm khác, vì thế code sẽ không chạy đúng như mong muốn nữa.

Để giải quyết vấn đề này, MIPS đưa ra một số thỏa hiệp giữa hàm gọi (caller - R) và hàm được gọi (callee - E):

• Đối với các thanh ghi $s0 - $s7 và $sp, E phải khôi phục lại đúng giá trị ban đầu sau khi thực thi xong.
• Đối với các thanh ghi khác: $t, $v, $a, $ra, E có quyền thay đổi giá trị các thanh ghi này, vì vậy R có trách nhiệm sao lưu và khôi phục lại các thanh ghi này trước và sau khi gọi E (nếu cần sử dụng).

Để quản lý sao lưu / khôi phục các thanh ghi như yêu cầu ở trên, ta dùng bộ nhớ stack.

Trong MIPS, thanh ghi $sp có giá trị trỏ tới đỉnh stack. Ở đầu hàm, ta lưu các biến cần sao lưu vào stack, sau đó ở cuối hàm, ta khôi phục lại các biến đó. Viết lại đoạn chương trình trên như sau:

baz:
    addi $sp, $sp, -4 # Mở rộng stack để sử dụng
    sw $s0, 0($sp)    # Lưu $s0 vào stack
    ori $s0, $0, 0    # Thay đổi $s0
    lw $s0, 0($sp)    # Khôi phục lại $s0 như ban đầu
    addi $sp, $sp, 4  # Khôi phục lại $sp
    jr $ra

bar:
    addi $sp, $sp, -12 # Vì có 3 thanh ghi cần lưu nên ta mở rộng stack 12 bytes
    sw $ra, 0($sp)     # Lưu $ra
    sw $s0, 4($sp)     # Lưu $s0
    sw $s1, 8($sp)     # Lưu $s1
    ori $s0, $0, 1     # Thay đổi $s0
    jal baz            # Gọi baz, $ra bị thay đổi
    slt $s1, $0, $s0   # Thay đổi $s1
    lw $s1, 8($sp)     # Khôi phục $s1
    lw $s0, 4($sp)     # Khôi phục $s0
    lw $ra, 0($sp)     # Khôi phục $ra
    addi $sp, $sp, 12  # Khôi phục $sp
    jr $ra

foo:
    addi $sp, $sp, -8
    sw $ra, 0($sp)
    sw $s0, 4($sp)
    ori $s0, $0, 2
    jal bar
    lw $s0, 4($sp)
    lw $ra, 0($sp)
    addi $sp, $sp, 8
    jr $ra

Truyền tham số - giá trị trả về

4 thanh ghi $a0 đến $a3 được quy ước dùng riêng cho các tham số truyền vào. Và 2 thanh ghi $v0, $v1 được dùng cho giá trị trả về. Ví dụ:

int sub(int a, int b) {
    return a - b;
}
int calc(int a, int b) {
    return sub(b, a) + b;
}

sub:
    sub $v0, $a0, $a1
    jr $ra

calc:
    addi $sp, $sp, -8
    sw $ra, 0($sp)
    sw $a1, 4($sp)    # Lưu lại $a1 vì ta cần dùng nó sau khi gọi hàm sub

    or $t0, $0, $a0   #
    or $a0, $0, $a1   # Hoán đổi giá trị $a0 và $a1, dùng biến tạm $t0
    or $a1, $0, $t0   #

    jal sub
    lw $a1, 4($sp)    # Khôi phục lại $a1
    add $v0, $v0, $a1
    lw $ra, 0($sp)
    addi $sp, $sp, 8
    jr $ra

Kham khảo thêm

• https://en.wikibooks.org/wiki/MIPS_Assembly