計(jì)算機(jī)指令系統(tǒng)ppt課件

1、第 9 講計(jì)算機(jī)指令系統(tǒng)數(shù)字邏輯與處置器; MIPS模擬器模擬器 MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì) 一個(gè)排序算法的實(shí)例一個(gè)排序算法的實(shí)例計(jì)算機(jī)指令系統(tǒng)計(jì)算機(jī)指令系統(tǒng)(2);MIPS模擬器模擬器 SPIM SPIM是主要的是主要的MIPS模擬器，可以運(yùn)轉(zhuǎn)和調(diào)模擬器，可以運(yùn)轉(zhuǎn)和調(diào)試試MIPS匯編言語程序匯編言語程序 SPIM支持支持Uinx、Windows等多個(gè)操作系等多個(gè)操作系統(tǒng)平臺(tái)統(tǒng)平臺(tái) /larus/spim.html;MIPS模擬器模擬器存放器窗口存放器窗口正文段正文段數(shù)據(jù)與堆棧段數(shù)據(jù)與堆棧段SPIM音訊音訊;MIPS模擬器模擬器 MARS MAR

2、S 是是MIPS Assembler and Runtime Simulator (MIPS匯編器和運(yùn)轉(zhuǎn)時(shí)模擬器匯編器和運(yùn)轉(zhuǎn)時(shí)模擬器)的縮寫的縮寫 可以運(yùn)轉(zhuǎn)和調(diào)試可以運(yùn)轉(zhuǎn)和調(diào)試MIPS匯編言語程序匯編言語程序 MARS采用采用Java開發(fā)，跨平臺(tái)開發(fā)，跨平臺(tái) /KenVollmar/MARS/;MIPS模擬器模擬器; MIPS的尋址方式的尋址方式 MIPS模擬器模擬器 MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì)計(jì)算機(jī)指令系統(tǒng)計(jì)算機(jī)指令系統(tǒng)(2);MIPS匯編器：語法匯編器：語法 注釋行以注釋行以“#開場(chǎng)；開場(chǎng)； 標(biāo)識(shí)符由字母、下劃線標(biāo)識(shí)符由字母、

3、下劃線_、點(diǎn)、點(diǎn).構(gòu)成，但構(gòu)成，但不能以數(shù)字開頭，指令操作碼是一些保管字，不不能以數(shù)字開頭，指令操作碼是一些保管字，不能用作標(biāo)識(shí)符；能用作標(biāo)識(shí)符； 標(biāo)號(hào)放在行首，后跟冒號(hào)標(biāo)號(hào)放在行首，后跟冒號(hào):，例如，例如 2022-5-198 .data #將子數(shù)據(jù)項(xiàng)，存放到數(shù)據(jù)段中Item: .word 1,2 #將2個(gè)32位數(shù)值送入地址延續(xù)的內(nèi)存字中 .text #將子串即指令或字送入用戶文件段 .global main #必需為全局變量Main: lw $t0, itemMIPS匯編中的命令見Page625;MIPS匯編言語程序設(shè)計(jì)：匯編言語程序設(shè)計(jì)：MIPS匯編言語語句格式匯編言語語句格式指令與偽指

4、令語句指令與偽指令語句Label: Arg1, Arg2, Arg3 #comment匯編命令匯編命令(directive)語句語句Label: .Directive arg1, arg2, . . . #comment;MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì)匯編命令匯編命令directive)匯編器用來定義數(shù)據(jù)段、代碼段以及為數(shù)據(jù)匯編器用來定義數(shù)據(jù)段、代碼段以及為數(shù)據(jù)分配存儲(chǔ)空間分配存儲(chǔ)空間.data address # 定義數(shù)據(jù)段定義數(shù)據(jù)段 # address為可選為可選的地址的地址.text address # 定義正文段定義正文段(即代即代碼段碼段) # address為可選的地址為

5、可選的地址.align n # 以以 2n字節(jié)邊境對(duì)齊數(shù)字節(jié)邊境對(duì)齊數(shù)據(jù)據(jù) # 只能用于數(shù)據(jù)段只能用于數(shù)據(jù)段;MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì)匯編命令匯編命令.ascii # 在內(nèi)存中存放字符串在內(nèi)存中存放字符串.asciiz # 在內(nèi)存中存放在內(nèi)存中存放NULL終了的終了的 # 字符串字符串.word w1, w2, . . . , wn # 在內(nèi)存中存放在內(nèi)存中存放n個(gè)字個(gè)字.half h1, h2, . . . , hn # 在內(nèi)存中存放在內(nèi)存中存放n個(gè)半字個(gè)半字.byte b1, b2, . . . , bn # 在內(nèi)存中存放在內(nèi)存中存放n個(gè)字節(jié)個(gè)字節(jié);MIPS匯編器：存儲(chǔ)器中

6、位置匯編器：存儲(chǔ)器中位置 匯編言語源文件：匯編言語源文件：.s “. MIPS匯編命令標(biāo)識(shí)符匯編命令標(biāo)識(shí)符 “l(fā)abel: label被賦值為當(dāng)前位置的地被賦值為當(dāng)前位置的地址址 Fact = 0 x00400100 編譯時(shí)就確定了編譯時(shí)就確定了 匯編程序在地址匯編程序在地址0 x00400000開場(chǎng)開場(chǎng)2022-5-1912 move $s5, $31 jal fact sw $s0,f($0) .text 0 x00400100 fact: addiu $s0,$0,1 lw $s1, n($0)loop: mul $s0,$s1,$s0 addi $s1,$s1,-1 bnez $s1,

7、loop jr $31.data 0 x10000200n: .word 4f: .word 00 x004000200 x004000240 x004000280 x004001000 x004001040 x004001080 x0040010C0 x004001100 x004001140 x100002000 x10000204;能運(yùn)轉(zhuǎn)的版本能運(yùn)轉(zhuǎn)的版本1：.textmain: ori $s6,$0,0 x1000 sll $s6,$s6,16 addiu $s4,$s6,0 x0200 #$s4=n addiu $s5,$s6,0 x0204 #$s5=f beq $0,$0, fa

8、ct result: sw $s0,0($s5) jr $ra #跳出跳出main2022-5-1913 .text 0 x00400100fact: addiu $s0,$0,1 lw $s1,0($s4) #$s0=n!loop: mul $s0,$s1,$s0addi $s1,$s1,-1bnez $s1,loop #f=n!j result .data 0 x10000200n: .word 4f: .word 0;.data 0 x10000000 .word 4,0.textmain:ori $s6,$0,0 x1000sll $s6,$s6,16addiu $s5,$s6,0 x

9、004fact:addiu $s0,$0,1lw $s1,0($s6)loop: mul $s0,$s1,$s0addi $s1,$s1,-1bnez $s1,loopsw $s0,0($s5)jr $ra14#以下語句行是數(shù)據(jù)代碼行以下語句行是數(shù)據(jù)代碼行#定義了兩個(gè)字型立刻數(shù)定義了兩個(gè)字型立刻數(shù)4和和0#以下語句行是指令代碼行以下語句行是指令代碼行 # 獲得數(shù)據(jù)起始地址獲得數(shù)據(jù)起始地址# $s6=0 x10000000# $s5=0 x10000004# 循環(huán)計(jì)數(shù)器賦初值循環(huán)計(jì)數(shù)器賦初值 # 把把 word型數(shù)型數(shù) 4 載入載入 $s1# $s0=n!, n=4# 對(duì)應(yīng)偽指令對(duì)應(yīng)偽指令 su

10、bu $s1,$s1,1# f=n!=24#根據(jù)根據(jù)ra存放器中的前往地址前往存放器中的前往地址前往能運(yùn)轉(zhuǎn)的版本2;編程指南編程指南1變量變量2分支分支3數(shù)組數(shù)組4過程調(diào)用過程調(diào)用5閱讀、改良程序閱讀、改良程序6設(shè)計(jì)實(shí)例設(shè)計(jì)實(shí)例2022-5-1915單指令計(jì)算機(jī)單指令計(jì)算機(jī);編程指南：編程指南：1變量變量 變量存儲(chǔ)在主存儲(chǔ)器內(nèi)而不是存放器內(nèi)變量存儲(chǔ)在主存儲(chǔ)器內(nèi)而不是存放器內(nèi) 由于我們通常有很多的變量要存，不止由于我們通常有很多的變量要存，不止32個(gè)個(gè) 為了實(shí)現(xiàn)功能為了實(shí)現(xiàn)功能, 用用LW 語句將變量加載到存放器中語句將變量加載到存放器中, 對(duì)存放器進(jìn)展操作對(duì)存放器進(jìn)展操作, 然后再把結(jié)果然后再

11、把結(jié)果SW回去回去 對(duì)于比較長的操作對(duì)于比較長的操作(e.g., loops): 讓變量在存放器中保管時(shí)間越長越好讓變量在存放器中保管時(shí)間越長越好 LW and SW 只在一塊代碼開場(chǎng)和終了時(shí)運(yùn)用只在一塊代碼開場(chǎng)和終了時(shí)運(yùn)用 節(jié)省指令節(jié)省指令 also, 現(xiàn)實(shí)上現(xiàn)實(shí)上LW and SW 比存放器操作要慢得多比存放器操作要慢得多得多！得多！ 由于一條指令只能采用兩個(gè)輸入由于一條指令只能采用兩個(gè)輸入,所以必需采用暫所以必需采用暫時(shí)存放器計(jì)算復(fù)雜的問題時(shí)存放器計(jì)算復(fù)雜的問題e.g., (x+y)+(x-y)2022-5-1916;編程指南：編程指南：1變量變量2022-5-1917.data 0 x

12、10000000 .word 4,0.textmain:addu $s3,$ra,$0ori $s6,$0,0 x1000sll $s6,$s6,16addiu $s5,$s6,4fact:addiu $s0,$0,1lw $s1,0($s6)loop:mul $s0,$s1,$s0addi $s1,$s1,-1bnez $s1,loopsw $s0,0($s5)jr $ra#s1 get 4#s0 hold result#return result in s0lui $s6, 0 x1000在程序起始處保管ra是一種習(xí)慣，目的是防止在程序中有jal指令修正了ra，我們跳不回去了，本程序中沒有

13、用可刪除以節(jié)省存放器和指令數(shù)。;編程指南：編程指南：2分支分支 在符號(hào)匯編語句中在符號(hào)匯編語句中,分支語分支語句的目的位置是用絕對(duì)地址句的目的位置是用絕對(duì)地址方式寫的方式寫的 e.g., beq $0,$0,fact means PC 0 x00400100 不過在實(shí)現(xiàn)中不過在實(shí)現(xiàn)中,要用相對(duì)于要用相對(duì)于PC的地址來定義的地址來定義 e.g., beq $0,$0,0 x3f means PC 0 x0040010018.textmain:addu $s3,$ra,$0 ori $s6,$0,0 x1000 sll $s6,$s6,16 addiu $s4,$s6,0 x0200 addiu

14、$s5,$s6,0 x0204 beq $0,$0, fact result: sw $s0,0($s5) addu $ra,$s3,$0 jr $ra .text 0 x00400100fact:sw $ra,0($s7) addiu $s0,$0,1 lw $s1,0($s4) #$s0=n!loop:mul $s0,$s1,$s0addi $s1,$s1,-1bnez $s1,loop #f=n!j result .data 0 x10000200n: .word 4f: .word 0;分支語句中的偏移量的運(yùn)用分支語句中的偏移量的運(yùn)用 偏移量偏移量= 從下一條指令對(duì)應(yīng)的從下一條指令對(duì)應(yīng)

15、的PC開場(chǎng)到標(biāo)號(hào)位置還有多開場(chǎng)到標(biāo)號(hào)位置還有多少條指令少條指令 e.g., beq $0,$0,fact假設(shè)位于地址假設(shè)位于地址0 x00400000 的話的話, word displacement=(target - (+4) / 4 =(0 x00400100-0 x00400004)/4 =0 xfc/4=0 x3f 偏移量為偏移量為0那么表示執(zhí)行下一條指令不產(chǎn)生任何跳轉(zhuǎn)那么表示執(zhí)行下一條指令不產(chǎn)生任何跳轉(zhuǎn) 為什么在代碼中用相對(duì)的偏移量為什么在代碼中用相對(duì)的偏移量? relocatable 代碼代碼(可重新定位的可重新定位的) 分支語句可以在每次被加載到內(nèi)存不同位置的情況下正分支語句可以

16、在每次被加載到內(nèi)存不同位置的情況下正常任務(wù)常任務(wù)2022-5-1919;編程指南：編程指南：2分支分支 分支分支 假設(shè)和假設(shè)和 0比較比較, 那么直接運(yùn)用那么直接運(yùn)用blez,bgez,bltz,bgtz, bnez e.g., loop example before 更復(fù)雜的比較更復(fù)雜的比較, 采用比較指令如采用比較指令如slt, 然后再用然后再用與與0比較比較 Example: if ( x = 0 )y = x;elsey = -x;2022-5-1920;21 .data 0 x10000000.word -6,0.textmain:ori $s6,$0,0 x1000sll $s6,

17、$s6,16addiu $s5,$s6,4lw $s0,0($s6)slt $s2,$0,$s0beqz $s2,elsemove $s1,$s0j doneelse:sub $s1,$0,$s0done: sw $s1,0($s5)jr $ra#x：-6, y：0 #計(jì)算內(nèi)存中數(shù)據(jù)存放地址計(jì)算內(nèi)存中數(shù)據(jù)存放地址#$s6=x， #$s5=y#0 x, $s2=1#$s2=0, 跳到跳到else#$s2=1, 跳到跳到done功能：求絕對(duì)值功能：求絕對(duì)值編程指南編程指南:分支分支 test2;編程指南編程指南:3數(shù)組數(shù)組array 用用 .word來給數(shù)組開辟空間來給數(shù)組開辟空間 在編譯時(shí)靜態(tài)地

18、開辟在編譯時(shí)靜態(tài)地開辟n*4 bytes, (n個(gè)個(gè)32-bit 字字) n=17 運(yùn)用運(yùn)用LW和和SW的的$2和和$4 LW $1, const($2) SW $3, const($4) 將將 const 作為數(shù)組偏移量作為數(shù)組偏移量 將存放器將存放器$2和和$4作為數(shù)組中的開場(chǎng)地址作為數(shù)組中的開場(chǎng)地址(A0)2022-5-1922 ;#編程指南編程指南:3數(shù)組數(shù)組array test3.data 0 x10000000.word 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17.textmain:addu $s7,$ra,$0ori $s5,$0,0 x1

19、000sll $s5,$s5,16 #$s5=A =0 x10000000，addiu $s6,$s5,0 x400 #$s6=B =0 x10000400addiu $s0,$0,0 x11 #Size(A)=Size(B)=0 x11loop:subu $s0,$s0,1 # 計(jì)數(shù)計(jì)數(shù)addiu $s1,$0,4mul $s2,$s1,$s0 # 換算地址換算地址addu $s3,$s2,$s5 #計(jì)算計(jì)算A偏移量偏移量,送到送到$s3lw $s4,0($s3) #讀出讀出A中的值中的值addu $s3,$s2,$s6 #計(jì)算計(jì)算B偏移量偏移量,送到送到$s3sw $s4,0($s3) #

20、寫到寫到B中去中去bnez $s0,loopaddu $ra,$0,$s7 #前往調(diào)用程序前往調(diào)用程序 jr $ra23;編程指南編程指南:3數(shù)組數(shù)組array數(shù)組訪問數(shù)組訪問 SLLV by k 等價(jià)于等價(jià)于 MUL by 2k SRLV by k 等價(jià)于等價(jià)于 DIV by 2k 很有用，由于很有用，由于 MUL 和和DIV普通都比普通都比SLL 和和SRL慢慢 想想怎樣實(shí)現(xiàn)想想怎樣實(shí)現(xiàn)MUL和和DIV 對(duì)于有符號(hào)數(shù)用對(duì)于有符號(hào)數(shù)用 SRA 高位用符號(hào)位填充高位用符號(hào)位填充(在在2的補(bǔ)碼表示情況下的補(bǔ)碼表示情況下) e.g., R1 = -6 = 0b1111010SRL $R1,$R1,

21、1 0b0111101 SRA $R1,$R1,1 0b1111101=-3 想想為什么這樣是對(duì)的想想為什么這樣是對(duì)的 2022-5-1924只對(duì)無符號(hào)數(shù)成立只對(duì)無符號(hào)數(shù)成立;編程指南編程指南:3數(shù)組數(shù)組array數(shù)組訪問數(shù)組訪問25 add $s0,$0,$a2 # i = N loop: subu $s0 $s0,1 # i- addiu $s1,$0,4 # $s1=4 mul $s2,$s1,$s0 # $s2 = i*4 addiu $t0,$0,2 # $t0=2 div $s0,$t0 # 商存放商存放$lo=floor(i/2) mflo $t1 # $t1=floor(i/2

22、) mul $t1,$s1,$t1 # $t1=$t1*4 add $t2,$t1,$a0 # 計(jì)算數(shù)組計(jì)算數(shù)組A地址地址 lw $s4,0($t2) # $s4=Ai/2 add $t3,$s2,$a1 # 計(jì)算數(shù)組計(jì)算數(shù)組B地址地址 sw $s4,0($t3) # Bi =$s4 bnez $s0,loop # while(i!=0) loopdone: 數(shù)組數(shù)組A的基地址存放在的基地址存放在$a0中中取對(duì)應(yīng)的數(shù)組元素取對(duì)應(yīng)的數(shù)組元素?cái)?shù)組數(shù)組B的基地址存放在的基地址存放在$a1中中數(shù)組長度數(shù)組長度N = 0 x100，存放在，存放在$a2中中數(shù)組長度計(jì)數(shù)器數(shù)組長度計(jì)數(shù)器$s0計(jì)算計(jì)算4字節(jié)

23、地址偏移量字節(jié)地址偏移量;Side Note #1: 用移位替代乘法用移位替代乘法對(duì)無符號(hào)數(shù)對(duì)無符號(hào)數(shù)SLL by k 等價(jià)于等價(jià)于 MUL by 2kSRL by k 等價(jià)于等價(jià)于 DIV by 2k對(duì)于有符號(hào)數(shù)用對(duì)于有符號(hào)數(shù)用 SRA高位用符號(hào)位填充高位用符號(hào)位填充(在在2的補(bǔ)碼表示情況下的補(bǔ)碼表示情況下)2022-5-1926 add $s0,$0,$a2 # i = Nloop: subu $s0 $s0,1 # i- sll $s2,$s0,2 # dest = i*4 sra $t1,$s0,1 # $t1=floor(i/2) sll $t1,$t1,2 # $t1=$t1*4

24、add $t2,$t1,$a0 lw $s4,0($t2) # $s4=Ai/2 add $t3,$s2,$a1 sw $s4,0($t3) # Bi = $s4 bnez $s0,loop # while(i!=0) loopdone: 編程指南編程指南:3數(shù)組數(shù)組array數(shù)組訪問數(shù)組訪問;編程指南編程指南:4過程調(diào)用過程調(diào)用 用匯編寫程序時(shí)需求明確闡明每一次的調(diào)用和前往用匯編寫程序時(shí)需求明確闡明每一次的調(diào)用和前往 Why？為什么用？為什么用C編寫程序時(shí)不需求了解子程序被編寫程序時(shí)不需求了解子程序被調(diào)用的詳細(xì)細(xì)節(jié)？調(diào)用的詳細(xì)細(xì)節(jié)？ 大多數(shù)有關(guān)過程調(diào)用的記錄集中在一個(gè)叫做過程調(diào)大多數(shù)有關(guān)過程

25、調(diào)用的記錄集中在一個(gè)叫做過程調(diào)用幀的內(nèi)存塊中，實(shí)現(xiàn)：用幀的內(nèi)存塊中，實(shí)現(xiàn)： 以參數(shù)方式保管調(diào)用值以參數(shù)方式保管調(diào)用值 保管主調(diào)過程的運(yùn)轉(zhuǎn)現(xiàn)場(chǎng)存放器保管主調(diào)過程的運(yùn)轉(zhuǎn)現(xiàn)場(chǎng)存放器 為程序的變量提供足夠的內(nèi)存空間部分變量、暫為程序的變量提供足夠的內(nèi)存空間部分變量、暫時(shí)變量時(shí)變量 程序的調(diào)用和前往嚴(yán)厲服從后進(jìn)先出程序的調(diào)用和前往嚴(yán)厲服從后進(jìn)先出LIFO原那原那么么2022-5-1927編譯程序替他做了！編譯程序替他做了！;編程指南編程指南:4過程調(diào)用過程調(diào)用我們需求存儲(chǔ)我們需求存儲(chǔ):前往地址前往地址(old ra) 參數(shù)參數(shù) n in fact(n)暫時(shí)暫時(shí)/部分的變量部分的變量 在在f執(zhí)行執(zhí)行過程中

26、過程中被破壞的存放器被破壞的存放器想法想法: 存在棧里存在棧里!增長增長(PUSH 進(jìn)去進(jìn)去) 棧，每棧，每次調(diào)用函數(shù)時(shí)次調(diào)用函數(shù)時(shí)縮減?？s減棧(POP 出來出來) 每次前每次前往時(shí)往時(shí)每次調(diào)用都有本人的每次調(diào)用都有本人的“棧框?？蚣芗?022-5-1928unused主存儲(chǔ)器主存儲(chǔ)器unused地址減小方向地址減小方向int fact( int n ) if (n 0) return fact( n-1 ) * n; else return 1 ;unusedunusedunusedunusedunusedunused例如例如調(diào)用調(diào)用fact(2);運(yùn)用棧：棧框架運(yùn)用棧：?？蚣芪覀冃枨蟠鎯?chǔ)我

27、們需求存儲(chǔ):前往地址前往地址(old ra)參數(shù)參數(shù) n in fact(n)暫時(shí)暫時(shí)/部分的變量部分的變量 在在f執(zhí)行執(zhí)行過程中過程中被破壞的存放器被破壞的存放器想法想法: 存在棧里存在棧里!增長增長(PUSH 進(jìn)去進(jìn)去) 棧，每棧，每次調(diào)用函數(shù)時(shí)次調(diào)用函數(shù)時(shí)縮減?？s減棧(POP 出來出來) 每次前每次前往時(shí)往時(shí)每次調(diào)用都有本人的每次調(diào)用都有本人的“棧框?？蚣芗?022-5-1929主存儲(chǔ)器主存儲(chǔ)器地址減小方向地址減小方向int fact( int n ) if (n 0) return fact( n-1 ) * n; else return 1 ;例如例如調(diào)用調(diào)用fact(2)2retu

28、rn addrtemp varsunusedunusedfact(2)s的棧框架的棧框架unusedunusedunused;運(yùn)用棧：?？蚣苓\(yùn)用棧：?？蚣芪覀冃枨蟠鎯?chǔ)我們需求存儲(chǔ):前往地址前往地址(old ra)參數(shù)參數(shù) n in fact(n)暫時(shí)暫時(shí)/部分的變量部分的變量 在在f執(zhí)行執(zhí)行過程中過程中被破壞的存放器被破壞的存放器想法想法: 存在棧里存在棧里!增長增長(PUSH 進(jìn)去進(jìn)去) 棧，每棧，每次調(diào)用函數(shù)時(shí)次調(diào)用函數(shù)時(shí)縮減棧縮減棧(POP 出來出來) 每次前每次前往時(shí)往時(shí)每次調(diào)用都有本人的每次調(diào)用都有本人的“?？驐？蚣芗?022-5-1930主存儲(chǔ)器主存儲(chǔ)器地址減小方向地址減小方向in

29、t fact( int n ) if (n 0) return fact( n-1 ) * n; else return 1 ;例如例如調(diào)用調(diào)用fact(2)2return addrtemp vars 1unusedunusedreturn addrtemp varsfact(2)s?？蚣軛？蚣躥act(1)s?？蚣軛？蚣?運(yùn)用棧：棧框架運(yùn)用棧：?？蚣芪覀冃枨蟠鎯?chǔ)我們需求存儲(chǔ):前往地址前往地址(old ra)參數(shù)參數(shù) n in fact(n)暫時(shí)暫時(shí)/部分的變量部分的變量 在在f執(zhí)行執(zhí)行過程中過程中被破壞的存放器被破壞的存放器想法想法: 存在棧里存在棧里!增長增長(PUSH 進(jìn)去進(jìn)去) 棧，每

30、棧，每次調(diào)用函數(shù)時(shí)次調(diào)用函數(shù)時(shí)縮減?？s減棧(POP 出來出來) 每次前每次前往時(shí)往時(shí)每次調(diào)用都有本人的每次調(diào)用都有本人的“?？驐？蚣芗?022-5-1931主存儲(chǔ)器主存儲(chǔ)器地址減小方向地址減小方向int fact( int n ) if (n 0) return fact( n-1 ) * n; else return 1 ;例如例如調(diào)用調(diào)用fact(2)2return addrtemp vars 1return addrtemp varsfact(2)s框架框架fact(1)s框架框架 0return addrtemp varsfact(0)s框架框架;運(yùn)用棧：?？蚣苓\(yùn)用棧：棧框架我們需求存

31、儲(chǔ)我們需求存儲(chǔ):前往地址前往地址(old ra)參數(shù)參數(shù) n in fact(n)暫時(shí)暫時(shí)/部分的變量部分的變量 在在f執(zhí)行執(zhí)行過程中過程中被破壞的存放器被破壞的存放器想法想法: 存在棧里存在棧里!增長增長(PUSH 進(jìn)去進(jìn)去) 棧，每棧，每次調(diào)用函數(shù)時(shí)次調(diào)用函數(shù)時(shí)縮減?？s減棧(POP 出來出來) 每次前每次前往時(shí)往時(shí)每次調(diào)用都有本人的每次調(diào)用都有本人的“棧框?？蚣芗?022-5-1932主存儲(chǔ)器主存儲(chǔ)器地址減小方向地址減小方向int fact( int n ) if (n 0) return fact( n-1 ) * n; else return 1 ;例如例如調(diào)用調(diào)用fact(2)2re

32、turn addrtemp vars 1unusedunusedreturn addrtemp varsfact(2)s?？蚣軛？蚣躥act(1)s?？蚣軛？蚣?運(yùn)用棧：棧框架運(yùn)用棧：?？蚣芪覀冃枨蟠鎯?chǔ)我們需求存儲(chǔ):前往地址前往地址(old ra)參數(shù)參數(shù) n in fact(n)暫時(shí)暫時(shí)/部分的變量部分的變量 在在f執(zhí)行執(zhí)行過程中過程中被破壞的存放器被破壞的存放器想法想法: 存在棧里存在棧里!增長增長(PUSH 進(jìn)去進(jìn)去) 棧，每棧，每次調(diào)用函數(shù)時(shí)次調(diào)用函數(shù)時(shí)縮減棧縮減棧(POP 出來出來) 每次前每次前往時(shí)往時(shí)每次調(diào)用都有本人的每次調(diào)用都有本人的“?？驐？蚣芗?022-5-1933主存儲(chǔ)器

33、主存儲(chǔ)器地址減小方向地址減小方向int fact( int n ) if (n 0) return fact( n-1 ) * n; else return 1 ;例如例如調(diào)用調(diào)用fact(2)2return addrtemp varsunusedunusedfact(2)s的?？蚣艿臈？蚣躸nusedunusedunused;運(yùn)用棧：?？蚣苓\(yùn)用棧：?？蚣芪覀冃枨蟠鎯?chǔ)我們需求存儲(chǔ):前往地址前往地址(old ra)參數(shù)參數(shù) n in fact(n)暫時(shí)暫時(shí)/部分的變量部分的變量 在在f執(zhí)行執(zhí)行過程中過程中被破壞的存放器被破壞的存放器想法想法: 存在棧里存在棧里!增長增長(PUSH 進(jìn)去進(jìn)去) 棧

34、，每棧，每次調(diào)用函數(shù)時(shí)次調(diào)用函數(shù)時(shí)縮減棧縮減棧(POP 出來出來) 每次前每次前往時(shí)往時(shí)每次調(diào)用都有本人的每次調(diào)用都有本人的“?？驐？蚣芗?022-5-1934unused主存儲(chǔ)器主存儲(chǔ)器unused地址減小方向地址減小方向int fact( int n ) if (n 0) return fact( n-1 ) * n; else return 1 ;unusedunusedunusedunusedunusedunused例如例如調(diào)用調(diào)用fact(2);棧的規(guī)定棧的規(guī)定 主調(diào)過程將調(diào)用后還需求運(yùn)用的參數(shù)存放器主調(diào)過程將調(diào)用后還需求運(yùn)用的參數(shù)存放器$a0$a3和暫和暫時(shí)存放器時(shí)存放器$t0$t

35、9壓棧壓棧 被調(diào)過程將前往地址存放器和在被調(diào)過程中修正了的保管被調(diào)過程將前往地址存放器和在被調(diào)過程中修正了的保管存放器存放器$s0$s7壓棧壓棧2022-5-1935;MIPS計(jì)算機(jī)硬件對(duì)過程的支持計(jì)算機(jī)硬件對(duì)過程的支持 為新數(shù)據(jù)分配空間為新數(shù)據(jù)分配空間 利用堆棧存儲(chǔ)過程中不適宜用存放器保管利用堆棧存儲(chǔ)過程中不適宜用存放器保管的部分變量如部分?jǐn)?shù)組、或構(gòu)造的部分變量如部分?jǐn)?shù)組、或構(gòu)造 過程框架：也叫活動(dòng)記錄，是指包含了過過程框架：也叫活動(dòng)記錄，是指包含了過程保管的存放器和部分變量的堆棧段。程保管的存放器和部分變量的堆棧段。 經(jīng)過下例了解過程調(diào)用之前、之中和之后經(jīng)過下例了解過程調(diào)用之前、之中和之后

36、的堆棧形狀的堆棧形狀36;MIPS 程序和數(shù)據(jù)的程序和數(shù)據(jù)的存儲(chǔ)器空間運(yùn)用商定存儲(chǔ)器空間運(yùn)用商定 從頂端開場(chǎng)，對(duì)棧指針初始化為從頂端開場(chǎng)，對(duì)棧指針初始化為7fffffff，并向下向數(shù)據(jù)段增長；，并向下向數(shù)據(jù)段增長； 在底端，程序代碼文本開場(chǎng)于在底端，程序代碼文本開場(chǎng)于00400000； 靜態(tài)數(shù)據(jù)開場(chǎng)于靜態(tài)數(shù)據(jù)開場(chǎng)于10000000； 緊接著是由緊接著是由C中中malloc進(jìn)展存儲(chǔ)器分進(jìn)展存儲(chǔ)器分配的動(dòng)態(tài)數(shù)據(jù)，朝堆棧段向上增長配的動(dòng)態(tài)數(shù)據(jù)，朝堆棧段向上增長37$sp$gp0040 0000hex01000 0000hexTextStatic dataDynamic dataStack7fff f

37、fffhex1000 8000hex pcReserved全局指針被設(shè)定為易于訪問數(shù)據(jù)的地址，以便運(yùn)用相對(duì)于$gp的16位偏移量10000000hex-1000ffffhex;數(shù)據(jù)存在哪？數(shù)據(jù)存在哪？2022-5-1938.data 0 x10000000 .word 4,0.textmain:addu $s7,$ra,$0ori $s6,$0,0 x1000sll $s6,$s6,16addiu $s5,$s6,4fact:addiu $s0,$0,1lw $s1,0($s6)loop:mul $s0,$s1,$s0subu $s1,$s1,1bnez $s1,loopsw $s0,0($s

38、5)addu $ra,$0,$s7jr $ra #s1 get 4#s0 hold result#return result in s0;嵌套過程調(diào)用嵌套過程調(diào)用 計(jì)算計(jì)算n! fact:addi $sp, $sp, -8sw $ra, 4($sp)sw$a0, 0($sp)slti $t0, $a0, 1beq$t0, $zero, L1addi $v0, $zero, 1addi $sp, $sp, 8jr $raL1:addi $a0, $a0, -1jalfactlw $a0, 0($sp)lw$ra, 4($sp)addi $sp, $sp, 8mul $v0, $a0, $v0jr

39、 $ra ;為新數(shù)據(jù)分配空間為新數(shù)據(jù)分配空間 框架指針框架指針$fp指向框架的第一個(gè)字，通常是保管指向框架的第一個(gè)字，通常是保管的參數(shù)存放器；的參數(shù)存放器； 棧指針棧指針$sp指向棧頂，在程序執(zhí)行的過程中棧指指向棧頂，在程序執(zhí)行的過程中棧指針有能夠改動(dòng)；針有能夠改動(dòng)； 因此經(jīng)過固定的框架指針來訪問變量要比用棧指因此經(jīng)過固定的框架指針來訪問變量要比用棧指針更簡(jiǎn)便。針更簡(jiǎn)便。 假設(shè)一個(gè)過程的棧中沒有部分變量，編譯器將不假設(shè)一個(gè)過程的棧中沒有部分變量，編譯器將不設(shè)置和恢復(fù)框架指針，以節(jié)省時(shí)間。設(shè)置和恢復(fù)框架指針，以節(jié)省時(shí)間。 當(dāng)需求框架指針時(shí)，以調(diào)用時(shí)的當(dāng)需求框架指針時(shí)，以調(diào)用時(shí)的$sp值作為框架值

40、作為框架指針的初值，調(diào)用前往時(shí)，根據(jù)指針的初值，調(diào)用前往時(shí)，根據(jù)$fp恢復(fù)恢復(fù)$sp值值40;編程指南編程指南1變量變量2分支分支3數(shù)組數(shù)組4過程調(diào)用過程調(diào)用5閱讀、改良程序閱讀、改良程序6設(shè)計(jì)實(shí)例設(shè)計(jì)實(shí)例2022-5-1941單指令計(jì)算機(jī)單指令計(jì)算機(jī);編程指南編程指南: 5閱讀、改良匯編代碼閱讀、改良匯編代碼 這段程序干了啥這段程序干了啥?2022-5-1942 .data#xs address stored in $a0# fs address stored in $a1 .text move $s1,$0 move $s2,$s1 addiu $s3,$0,1 lw $s4,0($a0)

41、 loop: subu $s4,$s4,1 beqz $s4,done move $s1,$s2 move $s2,$s3 addu $s3,$s2,$s1 j loopdone: sw $s3,0($a1) ;閱讀匯編代碼閱讀匯編代碼 這段程序干了啥這段程序干了啥?2022-5-1943 .data#xs address stored in $a0# fs address stored in $a1 .text move $s1,$0 move $s2,$s1 addiu $s3,$0,1 lw $s4,0($a0) loop: subu $s4,$s4,1 beqz $s4,done mo

42、ve $s1,$s2 move $s2,$s3 addu $s3,$s2,$s1 j loopdone: sw $s3,0($a1) #$s1=0#$s2=$s1#$s3=1#$s4=x#$s4=$s4-1#if($s4=0)done#$s1=$s2#$s2=$s3#$s3=$s2+$s1#goto loop#store result in f;閱讀匯編代碼閱讀匯編代碼這段程序干了啥這段程序干了啥?a = 0; / a = s1b = a; / b = r2res = 1;i = x;while ( -i != 0 ) / decrease i then check if 0 a=b; b=r

43、es; res=a+b;f = res; / note x itself isnt changedx = 1 2 3 4 5 6 7 8 9 10f =2022-5-1944 .data#xs address stored in $a0# fs address stored in $a1 .text move $s1,$0 move $s2,$s1 addiu $s3,$0,1 lw $s4,0($a0) loop: subu $s4,$s4,1 beqz $s4,done move $s1,$s2 move $s2,$s3 addu $s3,$s2,$s1 j loopdone: sw $s

44、3,0($a1) #$s1=0#$s2=$s1#$s3=1#$s4=x#$s4=$s4-1#if($s4=0)done#$s1=$s2#$s2=$s3#$s3=$s2+$s1#goto loop#store result in f;a = 0; / a = s1b = a; / b = s2res = 1;i = x;while ( -i != 0 ) / decrease i then check if 0 a=b; b=res; res=a+b;f = res; / note x itself isnt changedx = 1 2 3 4 5 6 7 8 9 10f = 1 1 2 3

45、5 8 13 21 34 55f = fib(x) (for x 0) (Fibonacci)2022-5-1945閱讀匯編代碼閱讀匯編代碼 .data#xs address stored in $a0# fs address stored in $a1 .text move $s1,$0 move $s2,$s1 addiu $s3,$0,1 lw $s4,0($a0) loop: addi $s4,$s4,-1 beqz $s4,done move $s1,$s2 move $s2,$s3 addu $s3,$s2,$s1 j loopdone: sw $s3,0($a1) #$s1=0#

46、$s2=$s1#$s3=1#$s4=x#$s4=$s4-1#if($s4=0)done#$s1=$s2#$s2=$s3#$s3=$s2+$s1#goto loop#store result in f前兩項(xiàng)均為前兩項(xiàng)均為1，從第三項(xiàng)起，每一項(xiàng)都，從第三項(xiàng)起，每一項(xiàng)都是其前兩項(xiàng)的和是其前兩項(xiàng)的和 這段程序干了啥？這段程序干了啥？;優(yōu)化代碼優(yōu)化代碼 如何使本部分如何使本部分代碼運(yùn)轉(zhuǎn)更快代碼運(yùn)轉(zhuǎn)更快? 目前運(yùn)轉(zhuǎn)時(shí)間：目前運(yùn)轉(zhuǎn)時(shí)間：= const + 6x 能否到達(dá)能否到達(dá) const + 5x?46 .data#x: $a0#f: $a1 .text move $s1,$0 move $s2,$s1

47、addiu $s3,$0,1 lw $s4,0($a0) loop: addi $s4,$s4,-1 beqz $s4,done move $s1,$s2 move $s2,$s3 addu $s3,$s2,$s1 j loopdone: sw $s3,0($a1) #$s1=0#$s2=0#$s3=1#$s4=x#計(jì)數(shù)器計(jì)數(shù)器$s4減減1#if($s4=0)done#$s1=0#$s2=1#$s3=$s2+$s1#goto loop#store result in f;Optimizing Codel 運(yùn)轉(zhuǎn)時(shí)間從運(yùn)轉(zhuǎn)時(shí)間從 const+6x 到到const+5xl Trick: 將將 SUB

48、U和和BNEZ移到后面，減掉額外的分移到后面，減掉額外的分支指令支指令l 當(dāng)當(dāng)x比較大時(shí)，減少了運(yùn)比較大時(shí)，減少了運(yùn)轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間constant有所添有所添加加l 目前的編譯器普通都可以目前的編譯器普通都可以支持這類優(yōu)化支持這類優(yōu)化2022-5-1947 move $s1,$0 #$s1=0 move $s2,$s1 #$s2=$s1 addiu $s3,$0,1 #$s3=1 lw $s4,0($a0) #$s4=x subu $s4,$s4,1 #$s4=$s4-1 beqz $s4,done #if($s4=0)doneloop: move $s1,$s2 #$s1=$s2 move $

49、s2,$s3 #$s2=$s3 addu $s3,$s2,$s1 addi $s4,$s4,1 #$s4=$s4-1 bnez $s4,loop #while($s4!=0)goto loopdone: sw $s3,0($a1) #store result in f ;編程指南編程指南1變量變量2分支分支3數(shù)組數(shù)組4過程調(diào)用過程調(diào)用5閱讀、改良程序閱讀、改良程序6設(shè)計(jì)實(shí)例設(shè)計(jì)實(shí)例2022-5-1948單指令計(jì)算機(jī)單指令計(jì)算機(jī);MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì) Hello world.textmain:la$a0, strli $v0, 4syscall# print stringli

50、$v0, 10syscall# exit.datastr: .asciiz Hello world.;MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì)系統(tǒng)調(diào)用系統(tǒng)調(diào)用MIPS模擬器提供了經(jīng)過系統(tǒng)調(diào)用指令模擬器提供了經(jīng)過系統(tǒng)調(diào)用指令(syscall) 提供了一組類似操作系統(tǒng)的效力提供了一組類似操作系統(tǒng)的效力調(diào)用方法：調(diào)用方法：將系統(tǒng)調(diào)用代碼裝入將系統(tǒng)調(diào)用代碼裝入$v0($2)存放器存放器將參數(shù)將參數(shù)(假設(shè)有假設(shè)有)裝入裝入$a0($4)$a3($7)或或$f12存放器存放器 Syscall前往值保管在前往值保管在$v0($2)或或$f0存放器中存放器中;MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì)系統(tǒng)調(diào)用系

51、統(tǒng)調(diào)用代碼代碼系統(tǒng)調(diào)用系統(tǒng)調(diào)用參數(shù)參數(shù)結(jié)果結(jié)果1print integer$a02print float$f123print double$f124print string$a0 5read integerinteger in $v06read floatfloat in $f07read doubledouble in $f08read string$a0=buffer, $a1=length9sbrk$a0=amountaddress in $v010exit;MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì)系統(tǒng)調(diào)用系統(tǒng)調(diào)用代碼代碼系統(tǒng)調(diào)用系統(tǒng)調(diào)用參數(shù)參數(shù)結(jié)果結(jié)果11print char$a012

52、read charchar in $v013open$a0=file name(string), $a1=flags, $a2=modefile descriptor (fd) in $v014read$a0 =fd, $a1=buffer, $a2=lengthnum chars read in $v015write$a0 =fd, $a1=buffer, $a2=lengthnum chars write in $v016close$a0 =fd17exit2$a0=result;MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì)棧動(dòng)態(tài)數(shù)據(jù)(堆)靜態(tài)數(shù)據(jù)正文 (指令)保管系統(tǒng)內(nèi)存區(qū).textmain

53、:la$a0, strli $v0, 4syscallli$v0, 10syscall.datastr: .asciiz Hello world.7fffeffc100400001001000000400000MARS商定商定;MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì) 從鍵盤輸入兩個(gè)數(shù)，計(jì)算并輸出這兩個(gè)數(shù)的和從鍵盤輸入兩個(gè)數(shù)，計(jì)算并輸出這兩個(gè)數(shù)的和.datastr1: .asciiz Enter 2 numbers:str2: .asciiz The sum is .text main: li $v0, 4la $a0, str1 syscall li $v0, 5 syscall add $

54、t0, $v0, $zero li $v0, 5 syscall add $t1, $v0, $zero li $v0, 4 la $a0, str2 syscall li $v0, 1 add $a0, $t1, $t0 syscall;MIPS匯編言語程序設(shè)計(jì)匯編言語程序設(shè)計(jì) 計(jì)算計(jì)算12+22+1002.textmain:li$t0, 1li$t8, 0loop:mul$t7, $t0, $t0add$t8, $t8, $t7addi$t0, $t0, 1ble$t0, 100, loopla$a0, strli $v0, 4syscallli $v0, 1move$a0, $t8syscallli$v0, 10syscall.data.align 2str:.asciiz The sum of square from 1 to 100 is ;一個(gè)排序算法的實(shí)例一個(gè)排序算法的實(shí)例void s