Kiến trúc máy tính - Chương 4: Kiến trúc tập lệnh

ộ đế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 NKK-HUT IT3030 8 Bộ đếm chương trình PC  Còn được gọi là con trỏ lệnh IP (Instruction Pointer)  Giữ địa chỉ của lệnh tiếp theo sẽ được nhận vào.  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. LÖnh LÖnh LÖnh kÕ tiÕp LÖnh sÏ ®-îc nhËn vµo LÖnh LÖnh LÖnh PC NKK-HUT IT3030 9 Thanh ghi con trỏ dữ liệu  Chứa địa chỉ của ngăn nhớ dữ liệu mà CPU muốn truy nhập  Thường có một số thanh ghi con trỏ dữ liệu D÷ liÖu D÷ liÖu D÷ liÖu D÷ liÖu D÷ liÖu cÇn ®äc/ghi D÷ liÖu D÷ liÖu D÷ liÖu DP NKK-HUT IT3030 10 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 NKK-HUT IT3030 11 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:  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  Nội dung của SP tăng  Khi ngăn xếp rỗng, SP trỏ vào đáy §¸y Stack §Ønh StackSP NKK-HUT IT3030 12 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 độ lệch địa chỉ giữa ngăn nhớ mà CPU cần truy nhập so với ngăn nhớ cơ sở (chỉ số)  Địa chỉ của ngăn nhớ cần truy nhập = địa chỉ cơ sở + chỉ số 26 May 2012 Ng¨n nhí cÇn truy nhËp Ng¨n nhí c¬ sëThanh ghi c¬ së Thanh ghi chØ sè NKK-HUT IT3030 13 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 NKK-HUT IT3030 14 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 NKK-HUT IT3030 15 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 . NKK-HUT IT3030 16 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 NKK-HUT IT3030 17 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. NKK-HUT IT3030 18 Ví dụ lưu trữ dữ liệu 32-bit 1A 2B 3C 4D 4D 1A 2B 3C little-endian 300 303 302 301 1A 4D 3C 2B big-endian 300 304 302 301 0001 1010 0010 1011 0011 1100 0100 1101 26 May 2012 NKK-HUT IT3030 19 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 NKK-HUT IT3030 20 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ữ NKK-HUT IT3030 21 Các thành phần của lệnh máy  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 M· thao t¸c §Þa chØ cña c¸c to¸n h¹ng 26 May 2012 NKK-HUT IT3030 22 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 NKK-HUT IT3030 23 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 NKK-HUT IT3030 24 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 NKK-HUT IT3030 25 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 NKK-HUT IT3030 26 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 NKK-HUT IT3030 27 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 NKK-HUT IT3030 28 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 NKK-HUT IT3030 29 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 NKK-HUT IT3030 30 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ờ NKK-HUT IT3030 31 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 NKK-HUT IT3030 32 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. NKK-HUT IT3030 33 Các lệnh SHIFT và ROTATE 0 0 0 DÞch tr¸i logic DÞch ph¶i logic DÞch ph¶i sè häc DÞch tr¸i sè häc Quay tr¸i logic Quay ph¶i logic NKK-HUT IT3030 34 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 NKK-HUT IT3030 35 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: NKK-HUT IT3030 36 Lệnh rẽ nhánh không điều kiện  Chuyển tới thực hiện lệnh ở vị trí có địa chỉ XXX: PC  XXX lÖnh lÖnh lÖnh lÖnh lÖnh lÖnh_kÕ_tiÕp lÖnh_rÏ_nh¸nh XXX lÖnh lÖnh XXX . . . NKK-HUT IT3030 37 Lệnh rẽ nhánh có điều kiện  Trong lệnh có kèm theo điều kiện  Kiểm tra điều kiện trong lệnh:  Nếu điều kiện đúng  chuyển tới thực hiện lệnh ở vị trí có địa chỉ XXX PC  XXX  Nếu điều kiện sai  chuyển sang thực hiện lệnh_kế_tiếp  Điều kiện thường được kiểm tra thông qua các cờ  Có nhiều lệnh rẽ nhánh có điều kiện lÖnh lÖnh lÖnh lÖnh lÖnh lÖnh_kÕ_tiÕp lÖnh_rÏ_nh¸nh_®k XXX lÖnh lÖnh XXX . . . NKK-HUT IT3030 38 Lệnh CALL và RETURN  Lệnh gọi chương trình con: lệnh CALL  Cất nội dung PC (chứa địa chỉ của lệnh_kế_tiếp) ra Stack  Nạp vào PC địa chỉ của lệnh đầu 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  Lệnh trở về từ chương trình con: lệnh RETURN  Lấy địa chỉ của lệnh_kế_tiếp được cất ở Stack nạp trả lại cho PC  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 lÖnh lÖnh lÖnh lÖnh lÖnh ®Çu tiªn cña CTCon lÖnh_kÕ_tiÕp CALL CTCon lÖnh lÖnh CTCon . . . RETURN . . . NKK-HUT IT3030 39 Gọi các thủ tục lồng nhau NKK-HUT IT3030 40 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 NKK-HUT IT3030 41 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 NKK-HUT IT3030 42 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 NKK-HUT IT3030 43 Định địa chỉ tức thì  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ế M· thao t¸c To¸n h¹ng NKK-HUT IT3030 44 Định địa chỉ thanh ghi  Toán hạng được chứa trong thanh ghi có tên trong Trường địa chỉ  Ví dụ: ADD R1, R2 ; R1 R1+R2  Số lượng thanh ghi ít  Trường địa chỉ chỉ cần ít bit  Không tham chiếu bộ nhớ  Truy nhập toán hạng nhanh  Tăng số lượng thanh ghi  hiệu quả hơn M· thao t¸c Tªn thanh ghi TËp thanh ghi To¸n h¹ng NKK-HUT IT3030 45 Đị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  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  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 M· thao t¸c §Þa chØ Bé nhí To¸n h¹ng NKK-HUT IT3030 46 Định địa chỉ gián tiếp qua thanh ghi  Toán hạng là ngăn nhớ có địa chỉ nằm trong thanh ghi  Trường địa chỉ cho biết tên thanh ghi đó  Thanh ghi có thể là ngầm định  Thanh ghi này được gọi 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) M· thao t¸c Tªn thanh ghi TËp thanh ghi Bé nhí §Þa chØ To¸n h¹ng NKK-HUT IT3030 47 Đị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 hạng  Có thể gián tiếp nhiều lần  Giống như khái niệm biến 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 để tìm toán hạng  chậm  Vùng nhớ có thể được tham chiếu là lớn M· thao t¸c §Þa chØ Bé nhí To¸n h¹ng §Þa chØ NKK-HUT IT3030 48 Định địa chỉ dịch chuyển  Để xác định toán hạng, Trường địa chỉ chứa hai thành phần:  Tên thanh ghi  Hằng số  Địa chỉ của toán hạng = nội dung thanh ghi + hằng số  Thanh ghi có thể được ngầm định M· thao t¸c Tªn thanh ghi TËp thanh ghi Bé nhí To¸n h¹ng H»ng sè + NKK-HUT IT3030 49 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ố NKK-HUT 4.4. Kiến trúc tập lệnh MIPS IT3030 50 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 51 IT3030 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 52 IT3030 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 53 IT3030 NKK-HUT Slide 54 MIPS Register File T e m p o r a ry va lu e s M o re te m p o ra ri e s O p e ra n d s G lo b a l p o in te r S ta c k p o in te r F ra m e p o in te r R e tu r n a d d re s s S a ve d S a ve d P ro c e d u re a rg u m e n ts S a ve d a c ro s s p ro c e d u r e c a lls P ro c e d u re r e s u lt s R e s e r ve d fo r a s s e m b l e r u s e R e s e r ve d fo r O S (k e rn e l) $0 $1 $2 $3 $4 $5 $6 $7 $8 $9 $10 $11 $12 $13 $14 $15 $16 $17 $18 $19 $20 $21 $22 $23 $24 $25 $26 $27 $28 $29 $30 $31 0 $zero $t0 $t2 $t4 $t6 $t1 $t3 $t5 $t7 $s0 $s2 $s4 $s6 $s1 $s3 $s5 $s7 $t8 $t9 $gp $sp $fp $ra $at $k0 $k1 $v0 $a0 $a2 $v1 $a1 $a3 A d o u b le w o rd s i ts in c o ns e c u tive re g is te rs o r m em o ry lo c a tio ns a c c o rd ing to th e b ig -e nd ian o rd e r (m os t s ig n i fica n t w o rd c om es fi rs t) W h e n lo a d in g a b yte in to a re g is te r , i t g o e s in th e lo w e nd B y te W o r d Do u b lew o r d B yte n u m b e r ing : 0 1 2 3 3 2 1 0 A 4 -b yte w o rd s i ts in c o ns e c u tive m em o ry a d d res s es a c c o rd ing to th e b ig -e nd ian o rd e r (m os t s ig n i fica n t b yte h a s th e lo w es t a d d res s ) IT3030 NKK-HUT Slide 55 Instruction Formats A typical instruction for MIPS and steps in its execution. A s s e m b ly la n g u a g e in s t ru c t io n : M a c h in e la n g u a g e in s t ru c t io n : H ig h -le ve l la n g u a g e s ta te m e n t : 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 ad d $t8 , $s2 , $s1 a = b + c A L U- ty pe in s tr u c tio n Re g is te r 1 8 Re g is te r 1 7 Re g is te r 2 4 Un u s e d A d d it io n o p c o d e A L U In s t ru c t io n fe t c h R e g is te r re a d o u t O p e ra t io n D a ta re a d /s to re R e g is te r w rit e b a c k R e g is te r fi le In s t ru c t io n c a c h e D a ta c a c h e (n o t u s e d ) R e g is te r fi le P C $ 1 7 $ 1 8 $ 2 4 IT3030 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 56 IT3030 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) 57 IT3030 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 58 IT3030 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 59 IT3030 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! 60 IT3030 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 61 IT3030 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 62 IT3030 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 63 IT3030 NKK-HUT IT3030 Slide 64 MIPS Instruction Formats 5 b it s 5 b it s 3 1 2 5 2 0 1 5 0 O p c o d e S o u rc e re g is te r 1 S o u rc e re g is te r 2 o p rs rt R 6 b it s 5 b it s rd 5 b it s s h 6 b it s 1 0 5 fn D e s t in a t io n re g is te r S h ift a m o u n t O p c o d e e x te n s io n Im m e d ia te o p e ra n d o r a d d re s s o f fs e t 3 1 2 5 2 0 1 5 0 O p c o d e D e s t in a t io n o r d a ta S o u rc e o r b a s e o p rs rt o p e ra n d / o ffs e t I 5 b it s 6 b it s 1 6 b it s 5 b it s 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 3 1 0 O p c o d e o p ju m p ta rg e t a d d re s s J M e m o ry w o rd a d d r e s s (b y te a d d r e s s d i vid e d b y 4 ) 2 6 b it s 2 5 6 b it s NKK-HUT MIPS R-format Instructions  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) op rs rt rd shamt funct 6 bits 6 bits 5 bits 5 bits 5 bits 5 bits 65 IT3030 NKK-HUT R-format Example 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 op rs rt rd shamt funct 6 bits 6 bits 5 bits 5 bits 5 bits 5 bits 66 IT3030 NKK-HUT MIPS I-format Instructions  Immediate arithmetic and load/store instructions  rt: destination or source register number  Constant: –215 to +215 – 1  Address: offset added to base address in rs op rs rt constant or address 6 bits 5 bits 5 bits 16 bits 67 IT3030 NKK-HUT Load and Store Instructions 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). 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 x 1 0 0 0 0 0 0 3 1 2 5 2 0 1 5 0 lw = 3 5 s w = 4 3 B a s e re g is te r D a ta re g is te r O f fs e t re l a t i ve to b a s e o p rs r t o p e ra n d / o ffs e t I 1 1 0 0 1 1 1 1 1 A [0 ] A [1 ] A [2 ] A [ i ] A d d re s s in b a s e re g is te r O f fs e t = 4 i . . . M e m o ry E le m e n t i o f a rr a y A N o te o n b a se a n d o ff se t: T h e m e m o ry a d d re s s is t h e s u m o f (r s ) a n d a n im m e d ia te va lu e . C a ll in g o n e o f t h e s e th e b a s e a n d th e o th e r th e o f fs e t is q u ite a rb it r a ry . It w o u ld m a k e p e rfe c t s e n s e to in te rp re t t h e a d d re s s A ( $ s 3 ) a s h a vin g th e b a s e A a n d th e o f fs e t ( $ s 3 ) . H o w e ve r, a 1 6 - b it b a s e c o n fin e s u s to a s m a ll p o rt io n o f m e m o ry s p a c e . lw $t0,40($s3) lw $t0,A($s3) 68 IT3030 NKK-HUT lui Instructions 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 3 1 2 5 2 0 1 5 0 lu i = 1 5 D e s t in a t io n U n u s e d Im m e d ia te o p e ra n d o p rs rt o p e ra n d / o ffs e t I C o n te n t o f $ s 0 a fte r th e in s t ru c t io n is e x e c u te d lui $s0, 61 # The immediate value 61 is # loaded in upper half of $s0 # with lower 16b set to 0s 69 IT3030 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 70 IT3030 NKK-HUT Logical Operations  Instructions for bitwise manipulation Operation C Java MIPS Shift left << << sll Shift right >> >>> srl Bitwise AND & & and, andi Bitwise OR | | or, ori Bitwise NOT ~ ~ nor  Useful for extracting and inserting groups of bits in a word 71 IT3030 NKK-HUT Shift Operations  shamt: how many positions to shift  Shift left logical  Shift left and fill with 0 bits  sll by i bits multiplies by 2i  Shift right logical  Shift right and fill with 0 bits  srl by i bits divides by 2i (unsigned only) op rs rt rd shamt funct 6 bits 6 bits 5 bits 5 bits 5 bits 5 bits 72 IT3030 NKK-HUT AND Operations  Useful to mask bits in a word  Select some bits, clear others to 0 and $t0, $t1, $t2 0000 0000 0000 0000 0000 1101 1100 0000 0000 0000 0000 0000 0011 1100 0000 0000 $t2 $t1 0000 0000 0000 0000 0000 1100 0000 0000 $t0 73 IT3030 NKK-HUT OR Operations  Useful to include bits in a word  Set some bits to 1, leave others unchanged or $t0, $t1, $t2 0000 0000 0000 0000 0000 1101 1100 0000 0000 0000 0000 0000 0011 1100 0000 0000 $t2 $t1 0000 0000 0000 0000 0011 1101 1100 0000 $t0 74 IT3030 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 0000 0000 0000 0000 0011 1100 0000 0000 $t1 1111 1111 1111 1111 1100 0011 1111 1111 $t0 Register 0: always read as zero 75 IT3030 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 76 IT3030 NKK-HUT IT3030 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) 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 3 1 2 5 2 0 1 5 0 b ltz = 1 Z e ro S o u rc e R e la t i ve b r a n c h d is ta n c e in w o rd s o p rs rt o p e ra n d / o ffs e t I 0 1 1 0 0 x 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 3 1 2 5 2 0 1 5 0 b e q = 4 b n e = 5 S o u rc e 2 S o u rc e 1 R e la t i ve b r a n c h d is ta n c e in w o rd s o p rs rt o p e ra n d / o ffs e t I 1 77 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 78 IT3030 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: 79 IT3030 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 80 IT3030 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 81 IT3030 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 1 1 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 3 1 2 5 2 0 1 5 0 A L U in s t ru c t io n S o u rc e 1 re g is te r S o u rc e 2 re g is te r o p rs rt R rd s h 1 0 5 fn D e s t in a t io n U n u s e d s lt = 4 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 3 1 2 5 2 0 1 5 0 s lt i = 1 0 D e s t in a t io n S o u rc e Im m e d ia te o p e ra n d o p rs rt o p e ra n d / o ffs e t I 1 82 IT3030 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 83 IT3030 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 = 1  sltu $t0, $s0, $s1 # unsigned  +4,294,967,295 > +1  $t0 = 0 84 IT3030 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 85 IT3030 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) 86 IT3030 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 87 IT3030 NKK-HUT IT3030 Slide 88 Illustrating a Procedure Call Relationship between the main program and a procedure. jal pr oc jr $ra p r o c S a ve , e t c . R e s to r e P C P re p a re to c o n t in u e P re p a re to c a ll m a i n NKK-HUT IT3030 Slide 89 Nested Procedure Calls jal ab c jr $ra a b c S a ve R e s to r e P C P re p a re to c o n tin u e P re p a re to c a l l m a i n jal xy z jr $ra x y z P ro c e d u re a b c P ro c e d u re x yz 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 90 IT3030 NKK-HUT Leaf Procedure Example  MIPS code: leaf_example: addi $sp, $sp, -4 sw $s0, 0($sp) add $t0, $a0, $a1 add $t1, $a2, $a3 sub $s0, $t0, $t1 add $v0, $s0, $zero lw $s0, 0($sp) addi $sp, $sp, 4 jr $ra Save $s0 on stack Procedure body Restore $s0 Result Return 91 IT3030 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 92 IT3030 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 93 IT3030 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 94 IT3030 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 95 IT3030 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 96 IT3030 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 97 IT3030 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 98 IT3030 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 99 IT3030 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 100 IT3030 NKK-HUT 0000 0000 0111 1101 0000 0000 0000 0000 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 1001 0000 0000 ori $s0, $s0, 2304 101 IT3030 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 102 IT3030 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 103 IT3030 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 = PC3128 : (address × 4) 104 IT3030 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 105 IT3030 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: 106 IT3030 NKK-HUT Addressing Mode Summary 107 IT3030 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 108 IT3030 NKK-HUT Translation and Startup Many compilers produce object modules directly Static linking 109 IT3030 26 May 2012 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 110 IT3030 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 111 IT3030 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 112 IT3030 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 113 IT3030 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 114 IT3030 NKK-HUT Lazy Linkage Indirection table Stub: Loads routine ID, Jump to linker/loader Linker/loader code Dynamically mapped code 115 IT3030 NKK-HUT Starting Java Applications Simple portable instruction set for the JVM Interprets bytecodes Compiles bytecodes of “hot” methods into native code for host machine 116 IT3030 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 117 IT3030 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 118 IT3030 NKK-HUT The Sort Procedure in C  Non-leaf (calls swap) void sort (int v[], int n) { int i, j; for (i = 0; i < n; i += 1) { for (j = i – 1; j >= 0 && v[j] > v[j + 1]; j -= 1) { swap(v,j); } } }  v in $a0, k in $a1, i in $s0, j in $s1 119 IT3030 NKK-HUT The Procedure Body move $s2, $a0 # save $a0 into $s2 move $s3, $a1 # save $a1 into $s3 move $s0, $zero # i = 0 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 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) move $a1, $s1 # 2nd param of swap is j jal swap # call swap procedure addi $s1, $s1, –1 # j –= 1 j for2tst # jump to test of inner loop exit2: addi $s0, $s0, 1 # i += 1 j for1tst # jump to test of outer loop Pass params & call Move params Inner loop Outer loop Inner loop Outer loop 120 IT3030 NKK-HUT 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 The Full Procedure 121 IT3030 NKK-HUT IT3030 Additional Instructions The multiply (mult) and divide (div) instructions of MIPS. 1 0 0 1 1 0 0 fn 0 0 0 0 0 0 0 0 0 0 0 0 x 0 0 1 1 0 0 0 0 0 0 0 0 3 1 2 5 2 0 1 5 0 A L U in s t ru c t io n S o u rc e re g is te r 1 S o u rc e re g is te r 2 o p rs rt R rd s h 1 0 5 U n u s e d U n u s e d m u lt = 2 4 d i v = 2 6 1 0 0 0 0 0 0 1 0 0 fn 0 0 0 0 0 0 0 0 0 0 0 x 0 0 0 0 0 0 0 0 0 0 3 1 2 5 2 0 1 5 0 A L U in s t ru c t io n U n u s e d U n u s e d o p rs rt R rd s h 1 0 5 D e s t in a t io n re g is te r U n u s e d m fh i = 1 6 m flo = 1 8 MIPS instructions for copying the contents of Hi and Lo registers into general registers . MiniMIPS instructions for multiplication and division: mult $s0, $s1 # set Hi,Lo to ($s0)($s1) div $s0, $s1 # set Hi to ($s0)mod($s1) # and Lo to ($s0)/($s1) mfhi $t0 # set $t0 to (Hi) mflo $t0 # set $t0 to (Lo) Reg file Mul/Div unit Hi Lo 122 NKK-HUT IT3030 Slide 123 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 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 124 IT3030 NKK-HUT Example: Clearing and Array clear1(int array[], int size) { int i; for (i = 0; i < size; i += 1) array[i] = 0; } clear2(int *array, int size) { int *p; for (p = &array[0]; p < &array[size]; p = p + 1) *p = 0; } move $t0,$zero # i = 0 loop1: sll $t1,$t0,2 # $t1 = i * 4 add $t2,$a0,$t1 # $t2 = # &array[i] sw $zero, 0($t2) # array[i] = 0 addi $t0,$t0,1 # i = i + 1 slt $t3,$t0,$a1 # $t3 = # (i < size) bne $t3,$zero,loop1 # if () # goto loop1 move $t0,$a0 # p = & array[0] sll $t1,$a1,2 # $t1 = size * 4 add $t2,$a0,$t1 # $t2 = # &array[size] loop2: sw $zero,0($t0) # Memory[p] = 0 addi $t0,$t0,4 # p = p + 4 slt $t3,$t0,$t2 # $t3 = #(p<&array[size]) bne $t3,$zero,loop2 # if () # goto loop2 125 IT3030 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 126 IT3030 NKK-HUT IT3030 The 20 MIPS Instructions Instruction Usage Move from Hi mfhi rd Move from Lo mflo rd Add unsigned addu rd,rs,rt Subtract unsigned subu rd,rs,rt Multiply mult rs,rt Multiply unsigned multu rs,rt Divide div rs,rt Divide unsigned divu rs,rt Add immediate unsigned addiu rs,rt,imm Shift left logical sll rd,rt,sh Shift right logical srl rd,rt,sh Shift right arithmetic sra rd,rt,sh Shift left logical variable sllv rd,rt,rs Shift right logical variable srlv rt,rd,rs Shift right arith variable srav rd,rt,rd Load byte lb rt,imm(rs) Load byte unsigned lbu rt,imm(rs) Store byte sb rt,imm(rs) Jump and link jal L System call syscall Copy Control transfer Shift Arithmetic Memory access op 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 32 36 40 3 0 fn 16 18 33 35 24 25 26 27 0 2 3 4 6 7 12 5 b it s 5 b it s 3 1 2 5 2 0 1 5 0 O p c o d e S o u rc e re g is te r 1 S o u rc e re g is te r 2 o p rs rt R 6 b it s 5 b it s rd 5 b it s s h 6 b it s 1 0 5 fn D e s t in a t io n re g is te r S h ift a m o u n t O p c o d e e x te n s io n Im m e d ia te o p e ra n d o r a d d re s s o f fs e t 3 1 2 5 2 0 1 5 0 O p c o d e D e s t in a t io n o r d a ta S o u rc e o r b a s e o p rs rt o p e ra n d / o ffs e t I 5 b it s 6 b it s 1 6 b it s 5 b it s 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 3 1 0 O p c o d e o p ju m p ta rg e t a d d re s s J M e m o ry w o rd a d d r e s s (b y te a d d r e s s d i vid e d b y 4 ) 2 6 b it s 2 5 6 b it s 127 NKK-HUT IT3030 The 37 + 3 MIPS Instructions Covered So Far Instruction Usage Move from Hi mfhi rd Move from Lo mflo rd Add unsigned addu rd,rs,rt Subtract unsigned subu rd,rs,rt Multiply mult rs,rt Multiply unsigned multu rs,rt Divide div rs,rt Divide unsigned divu rs,rt Add immediate unsigned addiu rs,rt,imm Shift left logical sll rd,rt,sh Shift right logical srl rd,rt,sh Shift right arithmetic sra rd,rt,sh Shift left logical variable sllv rd,rt,rs Shift right logical variable srlv rd,rt,rs Shift right arith variable srav rd,rt,rs Load byte lb rt,imm(rs) Load byte unsigned lbu rt,imm(rs) Store byte sb rt,imm(rs) Jump and link jal L System call syscall Instruction Usage Load upper immediate lui rt,imm Add add rd,rs,rt Subtract sub rd,rs,rt Set less than slt rd,rs,rt Add immediate addi rt,rs,imm Set less than immediate slti rd,rs,imm AND and rd,rs,rt OR or rd,rs,rt XOR xor rd,rs,rt NOR nor rd,rs,rt AND immediate andi rt,rs,imm OR immediate ori rt,rs,imm XOR immediate xori rt,rs,imm Load word lw rt,imm(rs) Store word sw rt,imm(rs) Jump j L Jump register jr rs Branch less than 0 bltz rs,L Branch equal beq rs,rt,L Branch not equal bne rs,rt,L 128 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 129 IT3030 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 130 IT3030 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 131 IT3030 NKK-HUT Basic x86 Registers 132 IT3030 26 May 2012 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  Address = Rbase + 2 scale × Rindex (scale = 0, 1, 2, or 3)  Address = Rbase + 2 scale × Rindex + displacement 133 IT3030 NKK-HUT x86 Instruction Encoding  Variable length encoding  Postfix bytes specify addressing mode  Prefix bytes modify operation  Operand length, repetition, locking, 134 IT3030 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 135 IT3030 NKK-HUT IT3030 136 Hết chương 4