›
›

Bài giảng Kiến trúc máy tính - Chương 4: Kiến trúc tập lệnh - Nguyễn Kim Khánh

pdf 136 trang phuongnguyen 2380
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kiến trúc máy tính - Chương 4: Kiến trúc tập lệnh - Nguyễn Kim Khánh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_kien_truc_may_tinh_chuong_4_kien_truc_tap_lenh_ngu.pdf

Nội dung text: Bài giảng Kiến trúc máy tính - Chương 4: Kiến trúc tập lệnh - Nguyễn Kim Khánh

  1. NKK-HUT Kiến trỳc mỏy tớnh Chương 4 KIẾN TRÚC TẬP LỆNH (Instruction Set Architecture) Nguyễn Kim Khỏnh Trường Đại học Bỏch khoa Hà Nội IT3030 1
  2. NKK-HUT Nội dung học phần  Chương 1. Giới thiệu chung  Chương 2. Cơ bản về logic số  Chương 3. Hệ thống mỏy tớnh  Chương 4. Kiến trỳc tập lệnh  Chương 5. Số học mỏy tớnh  Chương 6. Bộ xử lý  Chương 7. Bộ nhớ  Chương 8. Vào-ra  Chương 9. Kiến trỳc mỏy tớnh tiờn tiến 26 May 2012 IT3030 2
  3. NKK-HUT Nội dung của chương 4 4.1. Giới thiệu chung kiến trỳc tập lệnh 4.2. Cỏc kiểu thao tỏc 4.3. Cỏc phương phỏp định địa chỉ 4.4. Kiến trỳc tập lệnh MIPS 4.5. Kiến trỳc tập lệnh Intel x86 IT3030 3
  4. NKK-HUT 4.1. Giới thiệu chung về kiến trỳc tập lệnh Mụ hỡnh lập trỡnh của mỏy tớnh IT3030 4
  5. NKK-HUT Tập thanh ghi  Chức năng và đặc điểm:  Chứa cỏc thụng tin tạm thời phục vụ cho hoạt động ở thời điểm hiện tại của CPU  Được coi là mức đầu tiờn của hệ thống nhớ  Số lượng thanh ghi nhiều tăng hiệu năng của CPU  Cú hai loại thanh ghi:  Cỏc thanh ghi lập trỡnh được  Cỏc thanh ghi khụng lập trỡnh được IT3030 5
  6. NKK-HUT Phõn loại thanh ghi theo chức năng  Thanh ghi địa chỉ: quản lý địa chỉ của ngăn nhớ hay cổng vào-ra.  Thanh ghi dữ liệu: chứa tạm thời cỏc dữ liệu.  Thanh ghi đa năng: cú thể chứa địa chỉ hoặc dữ liệu.  Thanh ghi điều khiển/trạng thỏi: chứa cỏc thụng tin điều khiển và trạng thỏi của CPU.  Thanh ghi lệnh: chứa lệnh đang được thực hiện. IT3030 6
  7. NKK-HUT Một số thanh ghi điển hỡnh  Cỏc thanh ghi địa chỉ  Bộ đếm chương trỡnh PC (Program Counter)  Con trỏ dữ liệu DP (Data Pointer)  Con trỏ ngăn xếp SP (Stack Pointer)  Thanh ghi cơ sở và Thanh ghi chỉ số (Base Register & Index Register)  Cỏc thanh ghi dữ liệu  Thanh ghi trạng thỏi IT3030 7
  8. NKK-HUT Bộ đếm chương trỡnh PC  Cũn được gọi là con trỏ lệnh IP (Instruction Lệnh Pointer) Lệnh Lệnh  Giữ địa chỉ của lệnh PC Lệnh sẽ đ•ợc nhận vào tiếp theo sẽ được nhận Lệnh kế tiếp vào. Lệnh Lệnh  Sau khi một lệnh được nhận vào, nội dung PC tự động tăng để trỏ sang lệnh kế tiếp. IT3030 8
  9. NKK-HUT Thanh ghi con trỏ dữ liệu  Chứa địa chỉ của Dữ liệu ngăn nhớ dữ liệu mà Dữ liệu CPU muốn truy nhập Dữ liệu DP Dữ liệu cần đọc/ghi  Thường cú một số thanh ghi con trỏ dữ Dữ liệu liệu Dữ liệu Dữ liệu Dữ liệu IT3030 9
  10. NKK-HUT Ngăn xếp (Stack)  Ngăn xếp là vựng nhớ cú cấu trỳc LIFO (Last In - First Out)  Ngăn xếp thường dựng để phục vụ cho chương trỡnh con  Đỏy ngăn xếp là một ngăn nhớ xỏc định  Đỉnh ngăn xếp là thụng tin nằm ở vị trớ trờn cựng trong ngăn xếp  Đỉnh ngăn xếp cú thể bị thay đổi IT3030 10
  11. NKK-HUT Con trỏ ngăn xếp SP (Stack Pointer)  Chứa địa chỉ của ngăn nhớ đỉnh ngăn xếp  Khi cất một thụng tin vào ngăn xếp: SP Đỉnh Stack  Nội dung của SP giảm  Thụng tin được cất vào ngăn nhớ được trỏ bởi SP  Khi lấy một thụng tin ra khỏi ngăn xếp:  Thụng tin được đọc từ ngăn nhớ được trỏ bởi SP Đáy Stack  Nội dung của SP tăng  Khi ngăn xếp rỗng, SP trỏ vào đỏy IT3030 11
  12. NKK-HUT Thanh ghi cơ sở và thanh ghi chỉ số  Thanh ghi cơ sở: chứa địa chỉ của ngăn nhớ cơ sở (địa chỉ cơ sở)  Thanh ghi chỉ số: chứa độ Thanh ghi cơ sở Ngăn nhớ cơ sở lệch địa chỉ giữa ngăn nhớ mà CPU cần truy nhập so với ngăn nhớ cơ Thanh ghi chỉ số sở (chỉ số)  Địa chỉ của ngăn nhớ cần truy nhập = địa chỉ cơ sở Ngăn nhớ cần truy nhập + chỉ số 26 May 2012 IT3030 12
  13. NKK-HUT Cỏc thanh ghi dữ liệu  Chứa cỏc dữ liệu tạm thời hoặc cỏc kết quả trung gian  Cần cú nhiều thanh ghi dữ liệu  Cỏc thanh ghi số nguyờn: 8, 16, 32, 64 bit  Cỏc thanh ghi số dấu phẩy động IT3030 13
  14. NKK-HUT Thanh ghi trạng thỏi (Status Register)  Cũn gọi là thanh ghi cờ (Flag Register)  Chứa cỏc thụng tin trạng thỏi của CPU  Cỏc cờ phộp toỏn: bỏo hiệu trạng thỏi của kết quả phộp toỏn  Cỏc cờ điều khiển: biểu thị trạng thỏi điều khiển của CPU IT3030 14
  15. NKK-HUT Vớ dụ cờ phộp toỏn  Cờ Zero (cờ rỗng): được thiết lập lờn 1 khi kết quả của phộp toỏn bằng 0.  Cờ Sign (cờ dấu): được thiết lập lờn 1 khi kết quả phộp toỏn nhỏ hơn 0  Cờ Carry (cờ nhớ): được thiết lập lờn 1 nếu phộp toỏn cú nhớ ra ngoài bit cao nhất cờ bỏo tràn với số khụng dấu.  Cờ Overflow (cờ tràn): được thiết lập lờn 1 nếu cộng hai số nguyờn cựng dấu mà kết quả cú dấu ngược lại cờ bỏo tràn với số cú dấu . IT3030 15
  16. NKK-HUT Vớ dụ cờ điều khiển  Cờ Interrupt (Cờ cho phộp ngắt):  Nếu IF = 1 CPU ở trạng thỏi cho phộp ngắt với tớn hiệu yờu cầu ngắt từ bờn ngoài gửi tới  Nếu IF = 0 CPU ở trạng thỏi cấm ngắt với tớn hiệu yờu cầu ngắt từ bờn ngoài gửi tới IT3030 16
  17. NKK-HUT Thứ tự lưu trữ cỏc byte trong bộ nhớ chớnh  Bộ nhớ chớnh thường đỏnh địa chỉ theo byte  Hai cỏch lưu trữ thụng tin nhiều byte:  Đầu nhỏ (Little-endian): Byte cú ý nghĩa thấp được lưu trữ ở ngăn nhớ cú địa chỉ nhỏ, byte cú ý nghĩa cao được lưu trữ ở ngăn nhớ cú địa chỉ lớn.  Đầu to (Big-endian): Byte cú ý nghĩa cao được lưu trữ ở ngăn nhớ cú địa chỉ nhỏ, byte cú ý nghĩa thấp được lưu trữ ở ngăn nhớ cú địa chỉ lớn. IT3030 17
  18. NKK-HUT Vớ dụ lưu trữ dữ liệu 32-bit 0001 1010 0010 1011 0011 1100 0100 1101 1A 2B 3C 4D 4D 300 1A 300 3C 301 2B 301 2B 302 3C 302 1A 303 4D 304 little-endian big-endian 26 May 2012 IT3030 18
  19. NKK-HUT Lưu trữ của cỏc bộ xử lý điển hỡnh  Intel 80x86 và cỏc Pentium: little-endian  Motorola 680x0, MIPS, SunSPARC: big-endian  Power PC, Itanium: bi-endian 26 May 2012 IT3030 19
  20. NKK-HUT Giới thiệu chung về tập lệnh  Mỗi bộ xử lý cú một tập lệnh xỏc định  Tập lệnh thường cú hàng chục đến hàng trăm lệnh  Mỗi lệnh là một chuỗi số nhị phõn mà bộ xử lý hiểu được để thực hiện một thao tỏc xỏc định.  Cỏc lệnh được mụ tả bằng cỏc ký hiệu gợi nhớ dạng text chớnh là cỏc lệnh của hợp ngữ IT3030 20
  21. NKK-HUT Cỏc thành phần của lệnh mỏy Mã thao tác Địa chỉ của các toán hạng  Mó thao tỏc (operation code opcode): mó húa cho thao tỏc mà bộ xử lý phải thực hiện  Địa chỉ toỏn hạng: chỉ ra nơi chứa cỏc toỏn hạng mà thao tỏc sẽ tỏc động  Toỏn hạng nguồn: dữ liệu vào của thao tỏc  Toỏn hạng đớch: dữ liệu ra của thao tỏc 26 May 2012 IT3030 21
  22. NKK-HUT Số lượng địa chỉ toỏn hạng trong lệnh (1)  Ba địa chỉ toỏn hạng:  2 toỏn hạng nguồn, 1 toỏn hạng đớch  c = a + b  Từ lệnh dài vỡ phải mó hoỏ địa chỉ cho cả ba toỏn hạng  Được sử dụng trờn cỏc bộ xử lý tiờn tiến IT3030 22
  23. NKK-HUT Số lượng địa chỉ toỏn hạng trong lệnh (2)  Hai địa chỉ toỏn hạng:  Một toỏn hạng vừa là toỏn hạng nguồn vừa là toỏn hạng đớch; toỏn hạng cũn lại là toỏn hạng nguồn  a = a + b  Giỏ trị cũ của 1 toỏn hạng nguồn bị mất vỡ phải chứa kết quả  Rỳt gọn độ dài từ lệnh  Phổ biến IT3030 23
  24. NKK-HUT Số lượng địa chỉ toỏn hạng trong lệnh (3)  Một địa chỉ toỏn hạng:  Một toỏn hạng được chỉ ra trong lệnh  Một toỏn hạng là ngầm định thường là thanh ghi (thanh chứa –accumulator)  Được sử dụng trờn cỏc mỏy ở cỏc thế hệ trước IT3030 24
  25. NKK-HUT Số lượng địa chỉ toỏn hạng trong lệnh (4)  0 địa chỉ toỏn hạng:  Cỏc toỏn hạng đều được ngầm định  Sử dụng Stack  Vớ dụ: push a push b add pop c cú nghĩa là : c = a+b  khụng thụng dụng IT3030 25
  26. NKK-HUT Mỏy tớnh với tập lệnh thu gọn: RISC  CISC và RISC  CISC Complex Instruction Set Computer:  Mỏy tớnh với tập lệnh phức tạp  Cỏc bộ xử lý truyền thống: Intel x86, Motorola 680x0  RISC Reduced Instruction Set Computer:  Mỏy tớnh với tập lệnh thu gọn  SunSPARC, Power PC, MIPS, ARM  RISC đối nghịch với CISC IT3030 26
  27. NKK-HUT Cỏc đặc trưng của RISC  Số lượng lệnh ớt  Hầu hết cỏc lệnh truy nhập toỏn hạng ở cỏc thanh ghi  Truy nhập bộ nhớ bằng cỏc lệnh LOAD/STORE  Thời gian thực hiện lệnh là một chu kỳ mỏy  Cỏc lệnh cú độ dài cố định (32 bit)  Số lượng khuụn dạng lệnh ớt (<=4)  CPU cú tập thanh ghi lớn  Cú ớt phương phỏp định địa chỉ toỏn hạng(<=4)  Hỗ trợ cỏc thao tỏc của ngụn ngữ bậc cao IT3030 27
  28. NKK-HUT 4.2. Cỏc kiểu thao tỏc của lệnh  Chuyển dữ liệu  Xử lý số học  Xử lý logic  Điều khiển vào-ra  Chuyển điều khiển (rẽ nhỏnh)  Điều khiển hệ thống IT3030 28
  29. NKK-HUT Cỏc lệnh chuyển dữ liệu  MOVE Copy dữ liệu từ nguồn đến đớch  LOAD Nạp dữ liệu từ bộ nhớ đến bộ xử lý  STORE Cất dữ liệu từ bộ xử lý đến bộ nhớ  EXCHANGE Trao đổi nội dung của nguồn và đớch  CLEAR Chuyển cỏc bit 0 vào toỏn hạng đớch  SET Chuyển cỏc bit 1 vào toỏn hạng đớch  PUSH Cất nội dung toỏn hạng nguồn vào ngăn xếp  POP Lấy nội dung đỉnh ngăn xếp đưa đến toỏn hạng đớch IT3030 29
  30. NKK-HUT Cỏc lệnh số học  ADD Cộng hai toỏn hạng  SUBTRACT Trừ hai toỏn hạng  MULTIPLY Nhõn hai toỏn hạng  DIVIDE Chia hai toỏn hạng  NEGATE Đổi dấu toỏn hạng (lấy bự 2)  INCREMENT Tăng toỏn hạng thờm 1  DECREMENT Giảm toỏn hạng đi 1  COMPARE Trừ hai toỏn hạng để lập cờ IT3030 30
  31. NKK-HUT Cỏc lệnh logic  AND Thực hiện phộp AND hai toỏn hạng  OR Thực hiện phộp OR hai toỏn hạng  XOR Thực hiện phộp XOR hai toỏn hạng  NOT Đảo bit của toỏn hạng (lấy bự 1)  TEST Thực hiện phộp AND hai toỏn hạng để lập cờ  SHIFT Lệnh dịch bit  ROTATE Lệnh quay bit IT3030 31
  32. NKK-HUT Minh hoạ cỏc lệnh AND, OR, XOR  Giả sử cú hai thanh ghi chứa dữ liệu như sau: (R1) = 1010 1010 (R2) = 0000 1111  R1  (R1) AND (R2) = 0000 1010 Phộp toỏn AND dựng để xoỏ một số bit và giữ nguyờn một số bit cũn lại của toỏn hạng.  R1  (R1) OR (R2) = 1010 1111 Phộp toỏn OR dựng để thiết lập một số bit và giữ nguyờn một số bit cũn lại của toỏn hạng.  R1  (R1) XOR (R2) = 1010 0101 Phộp toỏn XOR dựng để đảo một số bit và giữ nguyờn một số bit cũn lại của toỏn hạng. IT3030 32
  33. NKK-HUT Cỏc lệnh SHIFT và ROTATE Dịch trái logic 0 Dịch phải logic 0 Dịch trái số học 0 Dịch phải số học Quay trái logic Quay phải logic IT3030 33
  34. NKK-HUT Cỏc lệnh vào ra chuyờn dụng  INPUT Copy dữ liệu từ một cổng xỏc định đến toỏn hạng đớch  OUTPUT Copy dữ liệu từ toỏn hạng nguồn đến một cổng xỏc định IT3030 34
  35. NKK-HUT Cỏc lệnh chuyển điều khiển  JUMP (BRANCH) Lệnh nhảy khụng điều kiện  JUMP CONDITIONAL Lệnh nhảy cú điều kiện  CALL Lệnh gọi chương trỡnh con  RETURN Lệnh trở về từ chương trỡnh con: IT3030 35
  36. NKK-HUT Lệnh rẽ nhỏnh khụng điều kiện lệnh lệnh  Chuyển tới thực hiện lệnh ở vị trớ cú địa chỉ XXX: lệnh_rẽ_nhánh XXX lệnh_kế_tiếp PC  XXX lệnh lệnh . . . XXX lệnh lệnh lệnh IT3030 36
  37. NKK-HUT Lệnh rẽ nhỏnh cú điều kiện  Trong lệnh cú kốm theo điều kiện lệnh  Kiểm tra điều kiện trong lệnh lệnh: lệnh_rẽ_nhánh_đk XXX  Nếu điều kiện đỳng chuyển lệnh_kế_tiếp tới thực hiện lệnh ở vị trớ cú lệnh địa chỉ XXX lệnh PC  XXX . . .  Nếu điều kiện sai chuyển sang thực hiện lệnh_kế_tiếp XXX lệnh  Điều kiện thường được kiểm lệnh tra thụng qua cỏc cờ lệnh  Cú nhiều lệnh rẽ nhỏnh cú điều kiện IT3030 37
  38. NKK-HUT Lệnh CALL và RETURN  Lệnh gọi chương trỡnh con: lệnh lệnh CALL lệnh CALL CTCon  Cất nội dung PC (chứa địa chỉ của lệnh_kế_tiếp) ra Stack lệnh_kế_tiếp lệnh  Nạp vào PC địa chỉ của lệnh đầu lệnh tiờn của chương trỡnh con được gọi Bộ xử lý được chuyển sang thực . . . hiện chương trỡnh con tương ứng CTCon lệnh đầu tiên của CTCon  Lệnh trở về từ chương trỡnh lệnh con: lệnh RETURN lệnh  Lấy địa chỉ của lệnh_kế_tiếp được . . . cất ở Stack nạp trả lại cho PC RETURN Bộ xử lý được điều khiển quay trở về thực hiện tiếp lệnh nằm sau lệnh CALL IT3030 38
  39. NKK-HUT Gọi cỏc thủ tục lồng nhau IT3030 39
  40. NKK-HUT Cỏc lệnh điều khiển hệ thống  HALT Dừng thực hiện chương trỡnh  WAIT Tạm dừng thực hiện chương trỡnh, lặp kiểm tra điều kiện cho đến khi thoả món thỡ tiếp tục thực hiện  NO OPERATION Khụng thực hiện gỡ cả  LOCK Cấm khụng cho xin chuyển nhượng bus  UNLOCK Cho phộp xin chuyển nhượng bus IT3030 40
  41. NKK-HUT 4.3. Cỏc phương phỏp định địa chỉ toỏn hạng Khỏi niệm về định địa chỉ (addressing)  Toỏn hạng của lệnh cú thể là:  Một giỏ trị cụ thể nằm ngay trong lệnh  Nội dung của thanh ghi  Nội dung của ngăn nhớ hoặc cổng vào-ra  Phương phỏp định địa chỉ (addressing modes) là cỏch thức địa chỉ húa trong trường địa chỉ của lệnh để xỏc định nơi chứa toỏn hạng IT3030 41
  42. NKK-HUT Cỏc phương phỏp định địa chỉ thụng dụng  Định địa chỉ tức thỡ  Định địa chỉ thanh ghi  Định địa chỉ trực tiếp  Định địa chỉ giỏn tiếp qua thanh ghi  Định địa chỉ giỏn tiếp qua ngăn nhớ  Định địa chỉ dịch chuyển IT3030 42
  43. NKK-HUT Định địa chỉ tức thỡ Mã thao tác Toán hạng  Toỏn hạng nằm ngay trong Trường địa chỉ của lệnh  Chỉ cú thể là toỏn hạng nguồn  Vớ dụ: ADD R1, 5 ; R1 R1+5  Khụng tham chiếu bộ nhớ  Truy nhập toỏn hạng rất nhanh  Dải giỏ trị của toỏn hạng bị hạn chế IT3030 43
  44. NKK-HUT Định địa chỉ thanh ghi  Toỏn hạng được chứa trong thanh ghi cú tờn trong Trường Mã thao tác Tên thanh ghi địa chỉ  Vớ dụ: ADD R1, R2 ; R1 R1+R2 Tập thanh ghi  Số lượng thanh ghi ớt Trường địa chỉ chỉ cần ớt bit  Khụng tham chiếu bộ nhớ Toán hạng  Truy nhập toỏn hạng nhanh  Tăng số lượng thanh ghi hiệu quả hơn IT3030 44
  45. NKK-HUT Định địa chỉ trực tiếp  Toỏn hạng là ngăn nhớ cú địa chỉ được chỉ ra trực tiếp trong Trường địa chỉ của lệnh Mã thao tác Địa chỉ Bộ nhớ  Vớ dụ: ADD R1, A ;R1  R1 + (A)  Cộng nội dung thanh ghi R1 với nội dung của ngăn nhớ cú địa chỉ là A Toán hạng  Tỡm toỏn hạng trong bộ nhớ ở địa chỉ A  CPU tham chiếu bộ nhớ một lần để truy nhập dữ liệu IT3030 45
  46. NKK-HUT Định địa chỉ giỏn tiếp qua thanh ghi  Toỏn hạng là ngăn nhớ cú địa chỉ nằm trong Mã thao tác Tên thanh ghi thanh ghi  Trường địa chỉ cho biết Bộ nhớ tờn thanh ghi đú Tập thanh ghi  Thanh ghi cú thể là ngầm định Địa chỉ  Thanh ghi này được gọi Toán hạng là thanh ghi con trỏ  Vựng nhớ cú thể được tham chiếu là lớn (2n), (với n là độ dài của thanh ghi) IT3030 46
  47. NKK-HUT Định địa chỉ giỏn tiếp qua ngăn nhớ  Ngăn nhớ được trỏ bởi Trường địa chỉ của lệnh chứa địa chỉ của toỏn Mã thao tác Địa chỉ hạng Bộ nhớ  Cú thể giỏn tiếp nhiều lần  Giống như khỏi niệm biến Địa chỉ con trỏ và biến động trong lập trỡnh  CPU phải thực hiện tham chiếu bộ nhớ nhiều lần để Toán hạng tỡm toỏn hạng chậm  Vựng nhớ cú thể được tham chiếu là lớn IT3030 47
  48. NKK-HUT Định địa chỉ dịch chuyển  Để xỏc định toỏn hạng, Trường địa Mã thao tác Tên thanh ghi Hằng số chỉ chứa hai thành phần: Bộ nhớ Tập thanh ghi  Tờn thanh ghi  Hằng số  Địa chỉ của toỏn + Toán hạng hạng = nội dung thanh ghi + hằng số  Thanh ghi cú thể được ngầm định IT3030 48
  49. NKK-HUT Cỏc dạng của định địa chỉ dịch chuyển  Địa chỉ hoỏ tương đối với PC  Thanh ghi là Bộ đếm chương trỡnh PC  Toỏn hạng cú địa chỉ cỏch ngăn nhớ được trỏ bởi PC một độ lệch xỏc định  Định địa chỉ cơ sở  Thanh ghi chứa địa chỉ cơ sở  Hằng số là chỉ số  Định địa chỉ chỉ số  Hằng số là địa chỉ cơ sở  Thanh ghi chứa chỉ số IT3030 49
  50. NKK-HUT 4.4. Kiến trỳc tập lệnh MIPS IT3030 50
  51. NKK-HUT MIPS  MIPS- Microprocessor without Interlocked Pipeline Stages  Stanford MIPS commercialized by MIPS Technologies (www.mips.com)  Large share of embedded core market  Applications in consumer electronics, network/storage equipment, cameras, printers,  Typical of many modern ISAs IT3030 51
  52. NKK-HUT Arithmetic Operations  Add and subtract, three operands  Two sources and one destination add a, b, c # a gets b + c  All arithmetic operations have this form IT3030 52
  53. NKK-HUT Register Operands  Arithmetic instructions use register operands  MIPS has a 32 ì 32-bit register file  Use for frequently accessed data  Numbered 0 to 31  32-bit data called a “word”  Assembler names  $t0, $t1, , $t9 for temporary values  $s0, $s1, , $s7 for saved variables IT3030 53
  54. NKK-HUT $0 0 $zero A 4 -b yte word 3 $1 $at Reserved for assembler use sits in consecutive 2 $2 $v0 m em ory addresses Procedure results $3 $v1 according to the 1 $4 $a0 b ig -endian order 0 MIPS $5 $a1 P ro c e d u re (m os t significant S a ve d byte has the $6 $a2 a rg u m e n t s lo w es t a d d res s ) Register File $7 $a3 $8 $t0 Byte num bering: $9 $t1 3 2 1 0 $10 $t2 When loading T e m p o r a ry $11 $t3 a byte into a $12 $t4 va lu e s re g is te r, it g o e s in the low end $13 $t5 B y te $14 $t6 $15 $t7 W o r d $16 $s0 Do u b lew o r d $17 $s1 $18 $s2 S a ve d $19 $s3 a c ro s s O p e ra n d s $20 $s4 p ro c e d u r e $21 $s5 c a lls $22 $s6 $23 $s7 A doubleword M o re $24 $t8 sits in consecutive $25 $t9 temporaries re g is te rs o r $26 $k0 m em ory locations $27 $k1 Reserved for OS (kernel) according to the $28 $gp Global pointer b ig -endian order (m os t significant $29 $sp Stack pointer S a ve d w o rd c om es firs t) $30 $fp Fram e pointer $31 $ra Return address IT3030 Slide 54
  55. NKK-HUT Instruction Formats H ig h -level language statement: a = b + c Assembly language instruction: add $t8, $s2, $s1 Machine language instruction: 000000 10010 10001 11000 00000 100000 ALU- ty pe Re g is te r Re g is te r Re g is te r A d d itio n instruction 18 17 24 Un u s e d o p c o d e R e g is t e r R e g is t e r Instruction file D a t a c a c h e file c a c h e (n o t u s e d ) P $17 ALU C $18 $24 Instruction R e g is t e r D a t a R e g is t e r O p e ra t io n fe t c h re a d o u t re a d / s t o re w rit e b a c k A typical instruction for MIPS and steps in its execution. IT3030 Slide 55
  56. NKK-HUT Register Operand Example  C code: f = (g + h) - (i + j);  f, g, h, i, j in $s0, $s1, $s2, $s3, $s4  Compiled MIPS code: add $t0, $s1, $s2 # $t0  $s1+$s2 add $t1, $s3, $s4 # $t1  $s3+$s4 sub $s0, $t0, $t1 # $s0  $t0-$t1 IT3030 56
  57. NKK-HUT Memory Operands  Main memory used for composite data  Arrays, structures, dynamic data  To apply arithmetic operations  Load values from memory into registers  Store result from register to memory  Memory is byte addressed  Each address identifies an 8-bit byte  Words are aligned in memory  Address must be a multiple of 4  MIPS is Big Endian  Most-significant byte at least address of a word  ( Little Endian: least-significant byte at least address) IT3030 57
  58. NKK-HUT Memory Operand Example 1  C code: g = h + A[8];  g in $s1, h in $s2, base address of A in $s3  Compiled MIPS code:  Index 8 requires offset of 32 (index from 0)  4 bytes per word lw $t0, 32($s3) # load word add $s1, $s2, $t0 offset base register IT3030 58
  59. NKK-HUT Memory Operand Example 2  C code: A[12] = h + A[8];  h in $s2, base address of A in $s3  Compiled MIPS code:  Index 8 requires offset of 32 lw $t0, 32($s3) # load word add $t0, $s2, $t0 sw $t0, 48($s3) # store word IT3030 59
  60. NKK-HUT Registers vs. Memory  Registers are faster to access than memory  Operating on memory data requires loads and stores  More instructions to be executed  Compiler must use registers for variables as much as possible  Only spill to memory for less frequently used variables  Register optimization is important! IT3030 60
  61. NKK-HUT Immediate Operands  Constant data specified in an instruction addi $s3, $s3, 4 # $s3  $s3+4  No subtract immediate instruction  Just use a negative constant addi $s2, $s1, -1 IT3030 61
  62. NKK-HUT The Constant Zero  MIPS register 0 ($zero) is the constant 0  Cannot be overwritten  Useful for common operations  E.g., move between registers add $t2, $s1, $zero IT3030 62
  63. NKK-HUT Representing Instructions  Instructions are encoded in binary  Called machine code  MIPS instructions  Encoded as 32-bit instruction words  Small number of formats encoding operation code (opcode), register numbers,  Register numbers  $t0 – $t7 are reg’s 8 – 15  $t8 – $t9 are reg’s 24 – 25  $s0 – $s7 are reg’s 16 – 23 IT3030 63
  64. NKK-HUT MIPS Instruction Formats op rs rt rd sh fn 31 25 20 15 10 5 0 R 6 b its 5 b its 5 b its 5 b its 5 b its 6 b its O p c o d e S o u rc e S o u rc e Destination S h ift O p c o d e re g is te r 1 re g is te r 2 re g is te r a m o u n t e x te n s io n op rs rt operand / offset 31 25 20 15 0 I 6 b its 5 b its 5 b its 1 6 b its O p c o d e S o u rc e Destination Imm ediate operand o r b a s e o r d a ta o r address offset op ju m p target address 31 25 0 J 6 b its 1 0 0 0 0 0 0 0 0 0 0 0 2 60 b0 its 0 0 0 0 0 0 1 1 1 1 0 1 O p c o d e Memory word address (byte address divided by 4) IT3030 Slide 64
  65. NKK-HUT MIPS R-format Instructions op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits  Instruction fields  op: operation code (opcode)  rs: first source register number  rt: second source register number  rd: destination register number  shamt: shift amount (00000 for now)  funct: function code (extends opcode) IT3030 65
  66. NKK-HUT R-format Example op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits add $t0, $s1, $s2 special $s1 $s2 $t0 0 add 0 17 18 8 0 32 000000 10001 10010 01000 00000 100000 0000 0010 0011 0010 0100 0000 0010 00002 = 0232402016 IT3030 66
  67. NKK-HUT MIPS I-format Instructions op rs rt constant or address 6 bits 5 bits 5 bits 16 bits  Immediate arithmetic and load/store instructions  rt: destination or source register number 15 15  Constant: –2 to +2 – 1  Address: offset added to base address in rs IT3030 67
  68. NKK-HUT Load and Store Instructions op rs rt operand / offset 31 25 20 15 0 I 1 0 x 0 1 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 lw = 3 5 B a s e D a t a Offset relative to base s w = 4 3 re g is t e r re g is t e r lw $t0,40($s3) Note on base and offset: M e m o ry lw $t0,A($s3) The memory address is the sum o f (rs) and an imm ediate value. A d d re s s in Calling one of these the base A [ 0 ] base register A [ 1 ] a n d t h e o ther the offset is quite arbitrary. It would m ake perfect A [ 2 ] sense to interpret the address . A($s3) as having the base A . Offset = 4 i . and the offs e t ($s3). However, a 1 6 - b it b a s e c o n fin e s u s t o a A[i] E le m e n t i o f a rr a y A small portion of m emory space. MIPS lw and sw instructions and their memory addressing convention that allows for simple access to array elements via a base address and an offset (offset = 4i leads us to the i th word). IT3030 68
  69. NKK-HUT lui Instructions lui $s0, 61 # The immediate value 61 is # loaded in upper half of $s0 # with lower 16b set to 0s op rs rt o p e ra n d / o ffs e t 31 25 20 15 0 I 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 lu i = 1 5 U n u s e d Destination Imm ediate operand 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Content of $s0 after the instruction is executed IT3030 69
  70. NKK-HUT Stored Program Computers  Instructions represented in binary, just like data  Instructions and data stored in memory  Programs can operate on programs  e.g., compilers, linkers,  Binary compatibility allows compiled programs to work on different computers  Standardized ISAs IT3030 70
  71. NKK-HUT Logical Operations  Instructions for bitwise manipulation Operation C Java MIPS Shift left > >>> srl Bitwise AND & & and, andi Bitwise OR | | or, ori Bitwise NOT ~ ~ nor  Useful for extracting and inserting groups of bits in a word IT3030 71
  72. NKK-HUT Shift Operations op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits  shamt: how many positions to shift  Shift left logical  Shift left and fill with 0 bits i  sll by i bits multiplies by 2  Shift right logical  Shift right and fill with 0 bits i  srl by i bits divides by 2 (unsigned only) IT3030 72
  73. NKK-HUT AND Operations  Useful to mask bits in a word  Select some bits, clear others to 0 and $t0, $t1, $t2 $t2 0000 0000 0000 0000 0000 1101 1100 0000 $t1 0000 0000 0000 0000 0011 1100 0000 0000 $t0 0000 0000 0000 0000 0000 1100 0000 0000 IT3030 73
  74. NKK-HUT OR Operations  Useful to include bits in a word  Set some bits to 1, leave others unchanged or $t0, $t1, $t2 $t2 0000 0000 0000 0000 0000 1101 1100 0000 $t1 0000 0000 0000 0000 0011 1100 0000 0000 $t0 0000 0000 0000 0000 0011 1101 1100 0000 IT3030 74
  75. NKK-HUT NOT Operations  Useful to invert bits in a word  Change 0 to 1, and 1 to 0  MIPS has NOR 3-operand instruction  a NOR b == NOT ( a OR b ) nor $t0, $t1, $zero Register 0: always read as zero $t1 0000 0000 0000 0000 0011 1100 0000 0000 $t0 1111 1111 1111 1111 1100 0011 1111 1111 IT3030 75
  76. NKK-HUT Conditional Operations  Branch to a labeled instruction if a condition is true  Otherwise, continue sequentially  bltz rs,L1  if (rs < 0) branch to instruction labeled L1;  beq rs, rt, L1  if (rs == rt) branch to instruction labeled L1;  bne rs, rt, L1  if (rs != rt) branch to instruction labeled L1;  j L1  unconditional jump to instruction labeled L1 IT3030 76
  77. NKK-HUT Example Conditional branches use PC-relative addressing bltz $s1,L # branch on ($s1)< 0 beq $s1,$s2,L # branch on ($s1)=($s2) bne $s1,$s2,L # branch on ($s1) ($s2) op rs rt operand / offset 31 25 20 15 0 I 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 b ltz = 1 S o u rc e Z e ro Relative branch distance in w o rd s op rs rt operand / offset 31 25 20 15 0 I 0 0 0 1 0 x 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 b e q = 4 S o u rc e 1 S o u rc e 2 Relative branch distance in w o rd s b n e = 5 IT3030 77
  78. NKK-HUT Compiling If Statements  C code: if (i==j) f = g+h; else f = g-h;  f, g, h, i, j in $s0, $s1, $s2, $s3, $s4  Compiled MIPS code: bne $s3, $s4, Else add $s0, $s1, $s2 j Exit Else: sub $s0, $s1, $s2 Exit: Assembler calculates addresses IT3030 78
  79. NKK-HUT Compiling Loop Statements  C code: while (save[i] == k) i += 1;  i in $s3, k in $s5, address of save in $s6  Compiled MIPS code: Loop: sll $t1, $s3, 2 add $t1, $t1, $s6 lw $t0, 0($t1) bne $t0, $s5, Exit addi $s3, $s3, 1 j Loop Exit: IT3030 79
  80. NKK-HUT Basic Blocks  A basic block is a sequence of instructions with  No embedded branches (except at end)  No branch targets (except at beginning)  A compiler identifies basic blocks for optimization  An advanced processor can accelerate execution of basic blocks IT3030 80
  81. NKK-HUT More Conditional Operations  Set result to 1 if a condition is true  Otherwise, set to 0  slt rd, rs, rt  if (rs < rt) rd = 1; else rd = 0;  slti rt, rs, constant  if (rs < constant) rt = 1; else rt = 0;  Use in combination with beq, bne slt $t0, $s1, $s2 # if ($s1 < $s2) bne $t0, $zero, L # branch to L IT3030 81
  82. NKK-HUT Example slt $s1,$s2,$s3 # if ($s2)<($s3), set $s1 to 1 # else set $s1 to 0; # often followed by beq/bne slti $s1,$s2,61 # if ($s2)<61, set $s1 to 1 # else set $s1 to 0 op rs rt rd sh fn 31 25 20 15 10 5 0 R 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 A L U S o u rc e 1 S o u rc e 2 Destination U n u s e d s lt = 4 2 instruction re g is te r re g is te r op rs rt o p e ra n d / o ffs e t 31 25 20 15 0 I 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 s lti = 1 0 S o u rc e Destination Imm ediate operand IT3030 82
  83. NKK-HUT Branch Instruction Design  Why not blt, bge, etc?  Hardware for <, ≥, slower than =, ≠  Combining with branch involves more work per instruction, requiring a slower clock  All instructions penalized!  beq and bne are the common case  This is a good design compromise IT3030 83
  84. NKK-HUT Signed vs. Unsigned  Signed comparison: slt, slti  Unsigned comparison: sltu, sltui  Example  $s0 = 1111 1111 1111 1111 1111 1111 1111 1111  $s1 = 0000 0000 0000 0000 0000 0000 0000 0001  slt $t0, $s0, $s1 # signed  –1 +1 $t0 = 0 IT3030 84
  85. NKK-HUT Procedure Calling  Steps required 1. Place parameters in registers 2. Transfer control to procedure 3. Acquire storage for procedure 4. Perform procedure’s operations 5. Place result in register for caller 6. Return to place of call IT3030 85
  86. NKK-HUT Register Usage  $a0 – $a3: arguments (reg’s 4 – 7)  $v0, $v1: result values (reg’s 2 and 3)  $t0 – $t9: temporaries  Can be overwritten by callee  $s0 – $s7: saved  Must be saved/restored by callee  $gp: global pointer for static data (reg 28)  $sp: stack pointer (reg 29)  $fp: frame pointer (reg 30)  $ra: return address (reg 31) IT3030 86
  87. NKK-HUT Procedure Call Instructions  Procedure call: jump and link jal ProcedureLabel  Address of following instruction put in $ra  Jumps to target address  Procedure return: jump register jr $ra  Copies $ra to program counter  Can also be used for computed jumps  e.g., for case/switch statements IT3030 87
  88. NKK-HUT Illustrating a Procedure Call main P re p a re t o c a ll PC j a l p r o c P re p a re to continue proc S a ve , e t c . R e s t o r e j r $ra Relationship between the main program and a procedure. IT3030 Slide 88
  89. NKK-HUT Nested Procedure Calls main P re p a re to c a ll PC j a l a b c P ro c e d u re P re p a re abc to continue abc P ro c e d u re S a ve x yz xyz j a l x y z R e s t o r e j r $ra j r $ra IT3030 Slide 89
  90. NKK-HUT Leaf Procedure Example  C code: int leaf_example (int g, h, i, j) { int f; f = (g + h) - (i + j); return f; }  Arguments g, h, i, j in $a0, $a1, $a2, $a3  f in $s0 (hence, need to save $s0 on stack)  Result in $v0 IT3030 90
  91. NKK-HUT Leaf Procedure Example  MIPS code: leaf_example: addi $sp, $sp, -4 sw $s0, 0($sp) Save $s0 on stack add $t0, $a0, $a1 add $t1, $a2, $a3 Procedure body sub $s0, $t0, $t1 add $v0, $s0, $zero Result lw $s0, 0($sp) addi $sp, $sp, 4 Restore $s0 jr $ra Return IT3030 91
  92. NKK-HUT Non-Leaf Procedures  Procedures that call other procedures  For nested call, caller needs to save on the stack:  Its return address  Any arguments and temporaries needed after the call  Restore from the stack after the call IT3030 92
  93. NKK-HUT Non-Leaf Procedure Example  C code: int fact (int n) { if (n < 1) return (1); else return n * fact(n - 1); }  Argument n in $a0  Result in $v0 IT3030 93
  94. NKK-HUT Non-Leaf Procedure Example  MIPS code: fact: addi $sp, $sp, -8 # adjust stack for 2 items sw $ra, 4($sp) # save return address sw $a0, 0($sp) # save argument slti $t0, $a0, 1 # test for n < 1 beq $t0, $zero, L1 addi $v0, $zero, 1 # if so, result is 1 addi $sp, $sp, 8 # pop 2 items from stack jr $ra # and return L1: addi $a0, $a0, -1 # else decrement n jal fact # recursive call lw $a0, 0($sp) # restore original n lw $ra, 4($sp) # and return address addi $sp, $sp, 8 # pop 2 items from stack mul $v0, $a0, $v0 # multiply to get result jr $ra # and return IT3030 94
  95. NKK-HUT Local Data on the Stack  Local data allocated by callee  e.g., C automatic variables  Procedure frame (activation record)  Used by some compilers to manage stack storage IT3030 95
  96. NKK-HUT Memory Layout  Text: program code  Static data: global variables  e.g., static variables in C, constant arrays and strings  $gp initialized to address allowing ±offsets into this segment  Dynamic data: heap  E.g., malloc in C, new in Java  Stack: automatic storage IT3030 96
  97. NKK-HUT Character Data  Byte-encoded character sets  ASCII: 128 characters  95 graphic, 33 control  Latin-1: 256 characters  ASCII, +96 more graphic characters  Unicode: 32-bit character set  Used in Java, C++ wide characters,  Most of the world’s alphabets, plus symbols  UTF-8, UTF-16: variable-length encodings IT3030 97
  98. NKK-HUT Byte/Halfword Operations  Could use bitwise operations  MIPS byte/halfword load/store  String processing is a common case lb rt, offset(rs) lh rt, offset(rs)  Sign extend to 32 bits in rt lbu rt, offset(rs) lhu rt, offset(rs)  Zero extend to 32 bits in rt sb rt, offset(rs) sh rt, offset(rs)  Store just rightmost byte/halfword IT3030 98
  99. NKK-HUT String Copy Example  C code (naùve):  Null-terminated string void strcpy (char x[], char y[]) { int i; i = 0; while ((x[i]=y[i])!='\0') i += 1; }  Addresses of x, y in $a0, $a1  i in $s0 IT3030 99
  100. NKK-HUT String Copy Example  MIPS code: strcpy: addi $sp, $sp, -4 # adjust stack for 1 item sw $s0, 0($sp) # save $s0 add $s0, $zero, $zero # i = 0 L1: add $t1, $s0, $a1 # addr of y[i] in $t1 lbu $t2, 0($t1) # $t2 = y[i] add $t3, $s0, $a0 # addr of x[i] in $t3 sb $t2, 0($t3) # x[i] = y[i] beq $t2, $zero, L2 # exit loop if y[i] == 0 addi $s0, $s0, 1 # i = i + 1 j L1 # next iteration of loop L2: lw $s0, 0($sp) # restore saved $s0 addi $sp, $sp, 4 # pop 1 item from stack jr $ra # and return IT3030 100
  101. NKK-HUT 32-bit Constants  Most constants are small  16-bit immediate is sufficient  For the occasional 32-bit constant lui rt, constant  Copies 16-bit constant to left 16 bits of rt  Clears right 16 bits of rt to 0 lui $s0, 61 0000 0000 0111 1101 0000 0000 0000 0000 ori $s0, $s0, 2304 0000 0000 0111 1101 0000 1001 0000 0000 IT3030 101
  102. NKK-HUT Initializing a Register Example Show how each of these bit patterns can be loaded into $s0: 0010 0001 0001 0000 0000 0000 0011 1101 1111 1111 1111 1111 1111 1111 1111 1111 Solution The first bit pattern has the hex representation: 0x2110003d lui $s0,0x2110 # put the upper half in $s0 ori $s0,0x003d # put the lower half in $s0 Same can be done, with immediate values changed to 0xffff for the second bit pattern. But, the following is simpler and faster: nor $s0,$zero,$zero # because (0  0) = 1 IT3030 102
  103. NKK-HUT Branch Addressing  Branch instructions specify  Opcode, two registers, target address  Most branch targets are near branch  Forward or backward op rs rt constant or address 6 bits 5 bits 5 bits 16 bits  PC-relative addressing  Target address = PC + offset ì 4  PC already incremented by 4 by this time IT3030 103
  104. NKK-HUT Jump Addressing  Jump (j and jal) targets could be anywhere in text segment  Encode full address in instruction op address 6 bits 26 bits  (Pseudo)Direct jump addressing  Target address = PC31 28 : (address ì 4) IT3030 104
  105. NKK-HUT Target Addressing Example  Loop code from earlier example  Assume Loop at location 80000 Loop: sll $t1, $s3, 2 80000 0 0 19 9 4 0 add $t1, $t1, $s6 80004 0 9 22 9 0 32 lw $t0, 0($t1) 80008 35 9 8 0 bne $t0, $s5, Exit 80012 5 8 21 2 addi $s3, $s3, 1 80016 8 19 19 1 j Loop 80020 2 20000 Exit: 80024 IT3030 105
  106. NKK-HUT Branching Far Away  If branch target is too far to encode with 16-bit offset, assembler rewrites the code  Example beq $s0,$s1, L1 ↓ bne $s0,$s1, L2 j L1 L2: IT3030 106
  107. NKK-HUT Addressing Mode Summary IT3030 107
  108. NKK-HUT Synchronization in MIPS  Load linked: ll rt, offset(rs)  Store conditional: sc rt, offset(rs)  Succeeds if location not changed since the ll  Returns 1 in rt  Fails if location is changed  Returns 0 in rt  Example: atomic swap (to test/set lock variable) try: add $t0,$zero,$s4 ;copy exchange value ll $t1,0($s1) ;load linked sc $t0,0($s1) ;store conditional beq $t0,$zero,try ;branch store fails add $s4,$zero,$t1 ;put load value in $s4 IT3030 108
  109. NKK-HUT Translation and Startup Many compilers produce object modules directly Static linking 26 May 2012 IT3030 109
  110. NKK-HUT Assembler Pseudoinstructions  Most assembler instructions represent machine instructions one-to-one  Pseudoinstructions: figments of the assembler’s imagination move $t0, $t1 → add $t0, $zero, $t1 blt $t0, $t1, L → slt $at, $t0, $t1 bne $at, $zero, L  $at (register 1): assembler temporary IT3030 110
  111. NKK-HUT Producing an Object Module  Assembler (or compiler) translates program into machine instructions  Provides information for building a complete program from the pieces  Header: described contents of object module  Text segment: translated instructions  Static data segment: data allocated for the life of the program  Relocation info: for contents that depend on absolute location of loaded program  Symbol table: global definitions and external refs  Debug info: for associating with source code IT3030 111
  112. NKK-HUT Linking Object Modules  Produces an executable image 1. Merges segments 2. Resolve labels (determine their addresses) 3. Patch location-dependent and external refs  Could leave location dependencies for fixing by a relocating loader  But with virtual memory, no need to do this  Program can be loaded into absolute location in virtual memory space IT3030 112
  113. NKK-HUT Loading a Program  Load from image file on disk into memory 1. Read header to determine segment sizes 2. Create virtual address space 3. Copy text and initialized data into memory  Or set page table entries so they can be faulted in 4. Set up arguments on stack 5. Initialize registers (including $sp, $fp, $gp) 6. Jump to startup routine  Copies arguments to $a0, and calls main  When main returns, do exit syscall IT3030 113
  114. NKK-HUT Dynamic Linking  Only link/load library procedure when it is called  Requires procedure code to be relocatable  Avoids image bloat caused by static linking of all (transitively) referenced libraries  Automatically picks up new library versions IT3030 114
  115. NKK-HUT Lazy Linkage Indirection table Stub: Loads routine ID, Jump to linker/loader Linker/loader code Dynamically mapped code IT3030 115
  116. NKK-HUT Starting Java Applications Simple portable instruction set for the JVM Compiles Interprets bytecodes of bytecodes “hot” methods into native code for host machine IT3030 116
  117. NKK-HUT C Sort Example  Illustrates use of assembly instructions for a C bubble sort function  Swap procedure (leaf) void swap(int v[], int k) { int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; }  v in $a0, k in $a1, temp in $t0 IT3030 117
  118. NKK-HUT The Procedure Swap swap: sll $t1, $a1, 2 # $t1 = k * 4 add $t1, $a0, $t1 # $t1 = v+(k*4) # (address of v[k]) lw $t0, 0($t1) # $t0 (temp) = v[k] lw $t2, 4($t1) # $t2 = v[k+1] sw $t2, 0($t1) # v[k] = $t2 (v[k+1]) sw $t0, 4($t1) # v[k+1] = $t0 (temp) jr $ra # return to calling routine IT3030 118
  119. NKK-HUT The Sort Procedure in C  Non-leaf (calls swap) void sort (int v[], int n) { int i, j; for (i = 0; i = 0 && v[j] > v[j + 1]; j -= 1) { swap(v,j); } } }  v in $a0, k in $a1, i in $s0, j in $s1 IT3030 119
  120. NKK-HUT The Procedure Body move $s2, $a0 # save $a0 into $s2 Move move $s3, $a1 # save $a1 into $s3 params move $s0, $zero # i = 0 Outer loop for1tst: slt $t0, $s0, $s3 # $t0 = 0 if $s0 ≥ $s3 (i ≥ n) beq $t0, $zero, exit1 # go to exit1 if $s0 ≥ $s3 (i ≥ n) addi $s1, $s0, –1 # j = i – 1 for2tst: slti $t0, $s1, 0 # $t0 = 1 if $s1 < 0 (j < 0) bne $t0, $zero, exit2 # go to exit2 if $s1 < 0 (j < 0) sll $t1, $s1, 2 # $t1 = j * 4 Inner loop add $t2, $s2, $t1 # $t2 = v + (j * 4) lw $t3, 0($t2) # $t3 = v[j] lw $t4, 4($t2) # $t4 = v[j + 1] slt $t0, $t4, $t3 # $t0 = 0 if $t4 ≥ $t3 beq $t0, $zero, exit2 # go to exit2 if $t4 ≥ $t3 move $a0, $s2 # 1st param of swap is v (old $a0) Pass move $a1, $s1 # 2nd param of swap is j params jal swap # call swap procedure & call addi $s1, $s1, –1 # j –= 1 Inner loop j for2tst # jump to test of inner loop exit2: addi $s0, $s0, 1 # i += 1 Outer loop j for1tst # jump to test of outer loop IT3030 120
  121. NKK-HUT The Full Procedure sort: addi $sp,$sp, –20 # make room on stack for 5 registers sw $ra, 16($sp) # save $ra on stack sw $s3,12($sp) # save $s3 on stack sw $s2, 8($sp) # save $s2 on stack sw $s1, 4($sp) # save $s1 on stack sw $s0, 0($sp) # save $s0 on stack # procedure body exit1: lw $s0, 0($sp) # restore $s0 from stack lw $s1, 4($sp) # restore $s1 from stack lw $s2, 8($sp) # restore $s2 from stack lw $s3,12($sp) # restore $s3 from stack lw $ra,16($sp) # restore $ra from stack addi $sp,$sp, 20 # restore stack pointer jr $ra # return to calling routine IT3030 121
  122. NKK-HUT Additional Instructions MiniMIPS instructions for multiplication and division: Reg mult $s0, $s1 # set Hi,Lo to ($s0) ($s1) file div $s0, $s1 # set Hi to ($s0)mod($s1) Mul/Div # and Lo to ($s0)/($s1) unit mfhi $t0 # set $t0 to (Hi) Hi Lo mflo $t0 # set $t0 to (Lo) op rs rt rd sh fn 31 25 20 15 10 5 0 R 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 x 0 A L U S o u rc e S o u rc e U n u s e d U n u s e d m u lt = 2 4 instruction re g is te r 1 re g is te r 2 d i v = 2 6 The multiply (mult) and divide (div) instructions of MIPS. op rs rt rd sh fn 31 25 20 15 10 5 0 R 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 x 0 A L U U n u s e d U n u s e d Destination U n u s e d m fh i = 1 6 instruction re g is te r m flo = 1 8 MIPS instructions for copying the contents of Hi and Lo registers into general registers . IT3030 122
  123. NKK-HUT Unsigned Arithmetic Instructions addu $t0,$s0,$s1 # set $t0 to ($s0)+($s1) subu $t0,$s0,$s1 # set $t0 to ($s0)–($s1) multu $s0,$s1 # set Hi,Lo to ($s0) ($s1) divu $s0,$s1 # set Hi to ($s0)mod($s1) # and Lo to ($s0)/($s1) addiu $t0,$s0,61 # set $t0 to ($s0)+61; # the immediate operand is # sign extended IT3030 Slide 123
  124. NKK-HUT Arrays vs. Pointers  Array indexing involves  Multiplying index by element size  Adding to array base address  Pointers correspond directly to memory addresses  Can avoid indexing complexity IT3030 124
  125. NKK-HUT Example: Clearing and Array clear1(int array[], int size) { clear2(int *array, int size) { int i; int *p; for (i = 0; i < size; i += 1) for (p = &array[0]; p < &array[size]; array[i] = 0; p = p + 1) } *p = 0; } move $t0,$zero # i = 0 move $t0,$a0 # p = & array[0] loop1: sll $t1,$t0,2 # $t1 = i * 4 sll $t1,$a1,2 # $t1 = size * 4 add $t2,$a0,$t1 # $t2 = add $t2,$a0,$t1 # $t2 = # &array[i] # &array[size] sw $zero, 0($t2) # array[i] = 0 loop2: sw $zero,0($t0) # Memory[p] = 0 addi $t0,$t0,1 # i = i + 1 addi $t0,$t0,4 # p = p + 4 slt $t3,$t0,$a1 # $t3 = slt $t3,$t0,$t2 # $t3 = # (i < size) #(p<&array[size]) bne $t3,$zero,loop1 # if ( ) bne $t3,$zero,loop2 # if ( ) # goto loop1 # goto loop2 IT3030 125
  126. NKK-HUT Comparison of Array vs. Ptr  Multiply “strength reduced” to shift  Array version requires shift to be inside loop  Part of index calculation for incremented i  c.f. incrementing pointer  Compiler can achieve same effect as manual use of pointers  Induction variable elimination  Better to make program clearer and safer IT3030 126
  127. NKK-HUT Instruction Usage op fn The 20 MIPS Move from Hi mfhi rd 0 16 Copy Move from Lo mflo rd 0 18 Instructions Add unsigned addu rd,rs,rt 0 33 Subtract unsigned subu rd,rs,rt 0 35 Multiply mult rs,rt 0 24 Arithmetic Multiply unsigned multu rs,rt 0 25 Divide div rs,rt 0 26 Divide unsigned divu rs,rt 0 27 Add immediate unsigned addiu rs,rt,imm 9 Shift left logical sll rd,rt,sh 0 0 op rs rt rd sh fn 31 25 20 15 10 5 0 R 6 b its 5 b its 5 b its 5 b its 5 b its 6 b its Shift right logical srl rd,rt,sh 0 2 O p c o d e S o u rc e S o u rc e Destination S h ift O p c o d e re g is te r 1 re g is te r 2 re g is te r a m o u n t e x te n s io n Shift right arithmetic sra rd,rt,sh 0 3 op rs rt operand / offset 31 25 20 15 0 Shift I 6 b its 5 b its 5 b its 1 6 b its Shift left logical variable sllv rd,rt,rs 0 4 O p c o d e S o u rc e Destination Imm ediate operand o r b a s e o r d a ta o r address offset Shift right logical variable srlv rt,rd,rs 0 6 op ju m p target address 31 25 0 J 6 b its 1 0 0 0 0 0 0 0 0 0 0 0 2 60 b0 its 0 0 0 0 0 0 1 1 1 1 0 1 Shift right arith variable srav rd,rt,rd 0 7 O p c o d e Memory word address (byte address divided by 4) Load byte lb rt,imm(rs) 32 Memory access Load byte unsigned lbu rt,imm(rs) 36 Store byte sb rt,imm(rs) 40 Jump and link jal L 3 Control transfer System call syscall 0 12 IT3030 127
  128. NKK-HUT The 37 + 3 MIPS Instructions Covered So Far Instruction Usage Instruction Usage Load upper immediate lui rt,imm Move from Hi mfhi rd Add add rd,rs,rt Move from Lo mflo rd Subtract sub rd,rs,rt Add unsigned addu rd,rs,rt Set less than slt rd,rs,rt Subtract unsigned subu rd,rs,rt Add immediate addi rt,rs,imm Multiply mult rs,rt Set less than immediate slti rd,rs,imm Multiply unsigned multu rs,rt AND and rd,rs,rt Divide div rs,rt OR or rd,rs,rt Divide unsigned divu rs,rt XOR xor rd,rs,rt Add immediate unsigned addiu rs,rt,imm NOR nor rd,rs,rt Shift left logical sll rd,rt,sh AND immediate andi rt,rs,imm Shift right logical srl rd,rt,sh OR immediate ori rt,rs,imm Shift right arithmetic sra rd,rt,sh XOR immediate xori rt,rs,imm Shift left logical variable sllv rd,rt,rs Load word lw rt,imm(rs) Shift right logical variable srlv rd,rt,rs Store word sw rt,imm(rs) Shift right arith variable srav rd,rt,rs Jump j L Load byte lb rt,imm(rs) Jump register jr rs Load byte unsigned lbu rt,imm(rs) Branch less than 0 bltz rs,L Store byte sb rt,imm(rs) Branch equal beq rs,rt,L Jump and link jal L Branch not equal bne rs,rt,L System call syscall IT3030 128
  129. NKK-HUT 4.6. Kiến trỳc tập lệnh Intel x86  Evolution with backward compatibility  8080 (1974): 8-bit microprocessor  Accumulator, plus 3 index-register pairs  8086 (1978): 16-bit extension to 8080  Complex instruction set (CISC)  8087 (1980): floating-point coprocessor  Adds FP instructions and register stack  80286 (1982): 24-bit addresses, MMU  Segmented memory mapping and protection  80386 (1985): 32-bit extension (now IA-32)  Additional addressing modes and operations  Paged memory mapping as well as segments IT3030 129
  130. NKK-HUT The Intel x86 ISA  Further evolution  i486 (1989): pipelined, on-chip caches and FPU  Compatible competitors: AMD, Cyrix,  Pentium (1993): superscalar, 64-bit datapath  Later versions added MMX (Multi-Media eXtension) instructions  The infamous FDIV bug  Pentium Pro (1995), Pentium II (1997)  New microarchitecture (see Colwell, The Pentium Chronicles)  Pentium III (1999)  Added SSE (Streaming SIMD Extensions) and associated registers  Pentium 4 (2001)  New microarchitecture  Added SSE2 instructions IT3030 130
  131. NKK-HUT The Intel x86 ISA  And further  AMD64 (2003): extended architecture to 64 bits  EM64T – Extended Memory 64 Technology (2004)  AMD64 adopted by Intel (with refinements)  Added SSE3 instructions  Intel Core (2006)  Added SSE4 instructions, virtual machine support  AMD64 (announced 2007): SSE5 instructions  Intel declined to follow, instead  Advanced Vector Extension (announced 2008)  Longer SSE registers, more instructions  If Intel didn’t extend with compatibility, its competitors would!  Technical elegance ≠ market success IT3030 131
  132. NKK-HUT Basic x86 Registers 26 May 2012 IT3030 132
  133. NKK-HUT Basic x86 Addressing Modes  Two operands per instruction Source/dest operand Second source operand Register Register Register Immediate Register Memory Memory Register Memory Immediate  Memory addressing modes  Address in register  Address = Rbase + displacement scale  Address = Rbase + 2 ì Rindex (scale = 0, 1, 2, or 3) scale  Address = Rbase + 2 ì Rindex + displacement IT3030 133
  134. NKK-HUT x86 Instruction Encoding  Variable length encoding  Postfix bytes specify addressing mode  Prefix bytes modify operation  Operand length, repetition, locking, IT3030 134
  135. NKK-HUT Implementing IA-32  Complex instruction set makes implementation difficult  Hardware translates instructions to simpler microoperations  Simple instructions: 1–1  Complex instructions: 1–many  Microengine similar to RISC  Market share makes this economically viable  Comparable performance to RISC  Compilers avoid complex instructions IT3030 135
  136. NKK-HUT Hết chương 4 IT3030 136