第二章計(jì)算機(jī)的語言

1、Chapter 2Chapter 2指令: 計(jì)算機(jī)的語言Chapter 2 Instructions: Language of the Computer 2指令集指令集n一臺(tái)計(jì)算機(jī)的全部指令n不同計(jì)算機(jī)有不同的指令集n但有許多共同的方面n早期計(jì)算機(jī)有很簡(jiǎn)單的指令集n實(shí)現(xiàn)簡(jiǎn)單n許多現(xiàn)代計(jì)算機(jī)也有簡(jiǎn)單指令集n例如：ARM系列計(jì)算機(jī)（RSIC）2.1 IntroductionChapter 2 Instructions: Language of the Computer 3MIPS指令集指令集n用于編寫書中的例子使用的是MIPS語言n斯坦福大學(xué)的MIPS來自MIPS公司 ()n在嵌入式處理機(jī)市場(chǎng)中占

2、有很大的份額n廣泛地應(yīng)用在家用電器、網(wǎng)絡(luò)/存儲(chǔ)設(shè)備，照相機(jī)，打印機(jī)n許多現(xiàn)代指令集的代表n參見MIPS參考數(shù)據(jù)卡和附錄B和E。Chapter 2 Instructions: Language of the Computer 4算術(shù)運(yùn)算操作算術(shù)運(yùn)算操作n加法和減法，都是三操作數(shù)n兩個(gè)源操作數(shù)，一個(gè)目的操作數(shù)add a, b, c # a = b + cn注釋用#開頭n所有的算術(shù)運(yùn)算都是這樣的形式n設(shè)計(jì)原則一：簡(jiǎn)單源于規(guī)整規(guī)整n規(guī)整使實(shí)現(xiàn)簡(jiǎn)單n簡(jiǎn)單能獲得低成本高性能2.2 Operations of the Computer HardwareChapter 2 Instructions: Lang

3、uage of the Computer 5算術(shù)操作例子算術(shù)操作例子nC 語言的語句:f = (g + h) - (i + j);n編譯成MIPS代碼:add t0, g, h #臨時(shí)變量臨時(shí)變量t0 = g + hadd t1, i, j #臨時(shí)變量臨時(shí)變量t1 = i + jsub f, t0, t1 # f = t0 - t1Chapter 2 Instructions: Language of the Computer 6寄存器操作數(shù)寄存器操作數(shù)n算術(shù)運(yùn)算指令使用寄存器操作nMIPS有32個(gè)32位 寄存器n用于存儲(chǔ)頻繁使用的數(shù)據(jù)n編號(hào)0 到31n32位數(shù)碼稱為一個(gè)字n編譯時(shí)名稱的約定n

4、$t0, $t1, , $t9 表示臨時(shí)寄存器臨時(shí)寄存器n$s0, $s1, , $s7 用于存儲(chǔ)變量n設(shè)計(jì)原則二：越少越快越少越快n對(duì)照主存：數(shù)以百萬計(jì)的存儲(chǔ)位置2.3 Operands of the Computer HardwareChapter 2 Instructions: Language of the Computer 7寄存器操作數(shù)舉例寄存器操作數(shù)舉例nC 語言編寫的代碼:f = (g + h) - (i + j);nf, , j in $s0, , $s4n編譯成MIPS代碼:add $t0, $s1, $s2add $t1, $s3, $s4sub $s0, $t0, $t

5、1Chapter 2 Instructions: Language of the Computer 8存儲(chǔ)器操作數(shù)存儲(chǔ)器操作數(shù)n主存可以存儲(chǔ)復(fù)雜數(shù)據(jù)n數(shù)組，結(jié)構(gòu)，動(dòng)態(tài)數(shù)據(jù)n使用算術(shù)運(yùn)算操作數(shù)n從主存把數(shù)讀入到寄存器n把結(jié)果從寄存器存儲(chǔ)到主存n存儲(chǔ)器按字節(jié)編址n每個(gè)地址表示一個(gè)8位字節(jié)n按字存放在內(nèi)存n每個(gè)地址必須是4個(gè)字節(jié)nMIPS按大端編址n高位存放在低地址n對(duì)照小端模式：低位放到低地址地址偏移大端模式小端模式0 x0012（OP0）34（OP1）0 x0134（OP1）12（OP0）如果將一個(gè)16位的整數(shù)0 x1234存放到一個(gè)短整型變量（short）中。這個(gè)短整型變量在內(nèi)存中的存儲(chǔ)在大小

6、端模式由下表所示。Chapter 2 Instructions: Language of the Computer 9存儲(chǔ)器操作數(shù)舉例存儲(chǔ)器操作數(shù)舉例1nC code:g = h + A8;ng 在 $s1, h 在 $s2, A的基址在 $s3n編譯成MIPS代碼:n小標(biāo)8（數(shù)組第8個(gè)分量）需要32的偏移n每個(gè)字對(duì)應(yīng)4個(gè)字節(jié)lw $t0, 32($s3) # load wordadd $s1, $s2, $t0偏移量offset基址寄存器Base register Chapter 2 Instructions: Language of the Computer 10存儲(chǔ)器操作數(shù)舉例存儲(chǔ)器操作

7、數(shù)舉例2nC code:A12 = h + A8;nh in $s2, base address of A in $s3nCompiled MIPS code:nIndex 8 requires offset of 32lw $t0, 32($s3) # load wordadd $t0, $s2, $t0sw $t0, 48($s3) # store wordChapter 2 Instructions: Language of the Computer 11寄存器和主存儲(chǔ)器寄存器和主存儲(chǔ)器n寄存器的訪問速度比主存快得多n對(duì)主存儲(chǔ)器數(shù)據(jù)的操作要用n取數(shù)指令lw (load word)n存數(shù)指

8、令sw (store word)。n需要執(zhí)行更多的指令n編譯器必須盡量使用寄存器訪問變量必須盡量使用寄存器訪問變量n僅當(dāng)寄存器不夠用時(shí)才把不經(jīng)常使用的變量放到內(nèi)存；n寄存器的高效利用對(duì)系統(tǒng)優(yōu)化非常重要。Chapter 2 Instructions: Language of the Computer 12常數(shù)或立即數(shù)操作數(shù)常數(shù)或立即數(shù)操作數(shù)n指令中使用常數(shù)addi $s3, $s3, 4（immediate）n沒有減去立即數(shù)的減法指令n可以使用負(fù)常數(shù)，即“加負(fù)數(shù)”實(shí)現(xiàn)減法addi $s2, $s1, -1n設(shè)計(jì)規(guī)則三：加速執(zhí)行常用操作n小常數(shù)操作出現(xiàn)的頻率高n立即數(shù)操作不用到內(nèi)存取數(shù)Chapte

9、r 2 Instructions: Language of the Computer 13常數(shù)零常數(shù)零nMIPS寄存器0（$zero）表示常數(shù)0n不能被改寫n在常用的操作中，很有用n例如，可在寄存器之間傳送數(shù)據(jù)add $t2, $s1, $zero常用的尋址方式常用的尋址方式n寄存器型：直接、間接；n存儲(chǔ)器型：直接、間接；n計(jì)算型：相對(duì)、基址、變址；n立即數(shù)型；Chapter 2 Instructions: Language of the Computer 15二進(jìn)制無符號(hào)整數(shù)二進(jìn)制無符號(hào)整數(shù)n給定一個(gè)n位數(shù)00112n2n1n1n2x2x2x2xxn范圍: 0 to +2n 1n舉例n000

10、0 0000 0000 0000 0000 0000 0000 10112= 0 + + 123 + 022 +121 +120= 0 + + 8 + 0 + 2 + 1 = 1110n32位數(shù)n0 to +4,294,967,2952.4 Signed and Unsigned NumbersChapter 2 Instructions: Language of the Computer 16二進(jìn)制補(bǔ)碼表示有符號(hào)整數(shù)二進(jìn)制補(bǔ)碼表示有符號(hào)整數(shù)nx是一個(gè)n位數(shù)00112n2n1n1n2x2x2x2xxn范圍: 2n 1 to +2n 1 1n舉例n1111 1111 1111 1111 1111

11、 1111 1111 11002= 1231 + 1230 + + 122 +021 +020= 2,147,483,648 + 2,147,483,644 = 410n32位數(shù)n2,147,483,648 to +2,147,483,647Chapter 2 Instructions: Language of the Computer 17二進(jìn)制補(bǔ)碼表示有符號(hào)整數(shù)二進(jìn)制補(bǔ)碼表示有符號(hào)整數(shù)n31位是符號(hào)位n1表示負(fù)數(shù)n0表示非負(fù)n(2n 1) 不能表示n非負(fù)數(shù)的無符號(hào)數(shù)和二進(jìn)制補(bǔ)碼是相同的n一些特殊的數(shù)n 0: 0000 0000 0000n1: 1111 1111 1111n絕對(duì)值最大負(fù)數(shù):

12、1000 0000 0000n最大正數(shù):0111 1111 1111Chapter 2 Instructions: Language of the Computer 18有符號(hào)數(shù)（二進(jìn)制補(bǔ)碼）的取反有符號(hào)數(shù)（二進(jìn)制補(bǔ)碼）的取反n取反加1n取反的含義1 0, 0 1x1x11111.111xx2n舉例：對(duì)+2的求反n+2 = 0000 0000 00102n2 = 1111 1111 11012 + 1 = 1111 1111 11102Chapter 2 Instructions: Language of the Computer 19符號(hào)擴(kuò)展符號(hào)擴(kuò)展n使用更多的位表示一個(gè)數(shù)n數(shù)值保持不變n在

13、MIPS指令集中naddi: extend immediate value擴(kuò)展到立即數(shù)nlb, lh: extend loaded byte/halfword 擴(kuò)展到取字節(jié)/半字nbeq, bne: 擴(kuò)展到跳轉(zhuǎn)后的位置extend the displacement 相等/不相等跳轉(zhuǎn)n復(fù)制符號(hào)位到左側(cè)n對(duì)照無符號(hào)數(shù)：用0擴(kuò)充n舉例: 8-bit to 16-bitn+2: 0000 0010 = 0000 0000 0000 0010n2: 1111 1110 = 1111 1111 1111 1110Chapter 2 Instructions: Language of the Compute

14、r 20指令表示指令表示n指令用二進(jìn)制編碼n稱為機(jī)器代碼nMIPS 指令n32位指令字編碼n指令格式中若干字段分別用于表示操作碼, 寄存器編號(hào), n非常規(guī)整n寄存器編號(hào)【參考教材71頁圖2-14】n$t0 $t7 are regs 8 15n$t8 $t9 are regs 24 25n$s0 $s7 are regs 16 232.5 Representing Instructions in the Computer指令格式的演變指令格式的演變n肆地址指令；n三地址指令；n二地址指令；n一地址指令；n零地址指令。n地址的顯式和隱含式Chapter 2 Instructions: Langua

15、ge of the Computer 22MIPS中寄存器指令中寄存器指令n指令字段nop: 操作碼(opcode)nrs: 第一個(gè)源寄存器編號(hào)nrt: 第二個(gè)源寄存器編號(hào)nrd: 目的寄存器編號(hào)nshamt: 移位位數(shù)(00000 表示不移位) nfunct: 功能碼（擴(kuò)展操作碼） (extends opcode)oprsrtrdshamtfunct6 bits6 bits5 bits5 bits5 bits5 bitsChapter 2 Instructions: Language of the Computer 23R-型（寄存器）操作舉例型（寄存器）操作舉例add $t0, $s1,

16、$s2special$s1$s2$t00add01718803200000010001100100100000000100000000000100011001001000000001000002 = 0232402016oprsrtrdshamtfunct6 bits6 bits5 bits5 bits5 bits5 bitsChapter 2 Instructions: Language of the Computer 24十六進(jìn)制十六進(jìn)制n基底是16n二進(jìn)制串的壓縮表示（使用16進(jìn)制的原因）n四位二進(jìn)制組成一個(gè)十六進(jìn)制數(shù)000004010081000c1100100015010191001

17、d11012001060110a1010e11103001170111b1011f1111nExample: eca8 6420n1110 1100 1010 1000 0110 0100 0010 0000Chapter 2 Instructions: Language of the Computer 25MIPS I型（立即數(shù)指令）型（立即數(shù)指令）n立即數(shù)的算術(shù)和讀數(shù)/存數(shù)指令nrt: 目的或源寄存器編號(hào)n常數(shù)的取值范圍: 215 to +215 1n地址：偏移加上rs中的基址n設(shè)計(jì)原則4：優(yōu)秀的設(shè)計(jì)需要適宜的折中方案n不同類型指令采用不同的解碼方式，但都是32位相同的指令長(zhǎng)度n盡可能保持

18、相似的指令格式oprsrtconstant or address6 bits5 bits5 bits16 bits指令格式舉例指令格式舉例1n如果數(shù)組A的基址放在$t1中，h存放在$s2中，這C語言寫的語句：nA300=h+A300編譯成匯編語言，則為：nlw $t0, 1200($t1) # $t0=A300nAdd $t0, $s2, $t0 # $t0=h+A300nSw $t0, 1200($t1) #把h+A300存到原來A300所在的單元。指令格式舉例指令格式舉例1-2oprsrtrdAddress/shamdfunct359812000188803243981200匯編語言編寫的

19、程序匯編語言編寫的程序：lw $t0, 1200($t1) Add $t0, $s2, $t0Sw $t0,1200($t1)變成機(jī)器語言變成機(jī)器語言，如下，如下：寄存器編號(hào)$t0 $t7 are regs 8 15$t8 $t9 are regs 24 25$s0 $s7 are regs 16 23指令格式舉例指令格式舉例1-3oprsrtrdAddress/shamdfunct359812000188803243981200存在存儲(chǔ)器中的形式為上表的存在存儲(chǔ)器中的形式為上表的2進(jìn)制進(jìn)制：oprsrtrdAddress/shamdfunct100011 01001010000000 010

20、0 1011 0000000000 100100100001000 00000100000101011 01001010000000 0100 1011 0000匯編語言編寫的程序匯編語言編寫的程序：lw $t0, 1200($t1) Add $t0, $s2, $t0Sw $t0,1200($t1)Chapter 2 Instructions: Language of the Computer 29存儲(chǔ)程序存儲(chǔ)程序n指令用二進(jìn)制表示，像數(shù)一樣n指令和數(shù)據(jù)存儲(chǔ)在存儲(chǔ)器中n程序可以被其他程序操作n例如，編譯，連接，n“二進(jìn)制兼容”可以讓編譯后的程序運(yùn)行在不同的計(jì)算機(jī)上n標(biāo)準(zhǔn)的ISAs（軟件編程的

21、標(biāo)準(zhǔn)）The BIG PictureThe BIG PictureChapter 2 Instructions: Language of the Computer 30邏輯操作邏輯操作n對(duì)位進(jìn)行處理的指令邏輯操作CJavaMIPS左移srl按位與&and, andi按位或|or, ori按位取反norn用于對(duì)字中的若干 “位位” n打包和拆包的操作2.6 Logical OperationsChapter 2 Instructions: Language of the Computer 31移位操作移位操作nshamt: 移多少位n邏輯左移sllslln左移空位填0n邏輯左移i位相當(dāng)于

22、乘2 2i in邏輯右移srln邏輯右移空位填0n邏輯右移i位相當(dāng)于除2i（僅對(duì)無符號(hào)數(shù)）oprsrtrdshamtfunct6 bits6 bits5 bits5 bits5 bits5 bitsChapter 2 Instructions: Language of the Computer 32“與與”操作操作n可用于一個(gè)字中的掩碼操作n選擇某些位，其他位清零and $t0, $t1, $t20000 0000 0000 0000 0000 1101 1100 00000000 0000 0000 0000 0011 1100 0000 0000$t2$t10000 0000 0000 0

23、000 0000 1100 0000 0000$t0Chapter 2 Instructions: Language of the Computer 33“或或” 操作操作n用于把包含字中的一些位置1，其他位不變or $t0, $t1, $t20000 0000 0000 0000 0000 1101 1100 00000000 0000 0000 0000 0011 1100 0000 0000$t2$t10000 0000 0000 0000 0011 1101 1100 0000$t0Chapter 2 Instructions: Language of the Computer 34按

24、位按位“取反取反”操作操作n用于改變字中的一些位n0變成1,1變成0nMIPS 3-操作數(shù)指令NORna NOR b = NOT ( a OR b ) “或非”nor $t0, $t1, $zero0000 0000 0000 0000 0011 1100 0000 0000$t11111 1111 1111 1111 1100 0011 1111 1111$t0Register 0: always read as zeroChapter 2 Instructions: Language of the Computer 35決策指令決策指令n如果條件為真，跳轉(zhuǎn)到被標(biāo)簽的指令執(zhí)行n否則，繼續(xù)執(zhí)行

25、nbeq rs, rt, L1nif (rs = rt)轉(zhuǎn)到標(biāo)簽為L(zhǎng)1的指令執(zhí)行nbne rs, rt, L1nif (rs != rt)轉(zhuǎn)到標(biāo)簽為L(zhǎng)1的指令執(zhí)行;nj L1n無條件跳轉(zhuǎn)到標(biāo)簽為L(zhǎng)1的指令執(zhí)行2.7 Instructions for Making DecisionsChapter 2 Instructions: Language of the Computer 36編譯編譯IF語句語句nC code:if (i=j) f = g+h; else f = g-h;nf, g, in $s0, $s1, n編譯成MIPS 代碼: bne $s3, $s4, Else add $s0

26、, $s1, $s2 j ExitElse: sub $s0, $s1, $s2Exit: Assembler calculates addressesChapter 2 Instructions: Language of the Computer 37編譯循環(huán)語句編譯循環(huán)語句nC code:while (while (saveisavei = k) = k) i += 1; i += 1;ni in $s3, k in $s5, address of save in $s6nCompiled MIPS code:Loop: Loop: sllsll $t1, $s3, 2 $t1, $s3,

27、 2 add $t1, $t1, $s6 add $t1, $t1, $s6 lwlw $t0, 0($t1) $t0, 0($t1) bnebne $t0, $s5, Exit $t0, $s5, Exit addiaddi $s3, $s3, 1 $s3, $s3, 1 j Loop j LoopExit: Exit: Chapter 2 Instructions: Language of the Computer 38基本塊基本塊n一個(gè)基本塊是一個(gè)指令序列，其中n內(nèi)部沒有跳出的指令（結(jié)束指令除外）n也沒有被跳轉(zhuǎn)到的指令（開始指令除外）n編譯器標(biāo)識(shí)基本快用于優(yōu)化n高級(jí)處理機(jī)能夠加速基本塊的

28、執(zhí)行Chapter 2 Instructions: Language of the Computer 39更多的條件操作更多的條件操作n如果條件為真置1，否則置0nslt rd, rs, rt；小于則置位nif (rs rt) rd = 1; else rd = 0;nslti rt, rs, constantnif (rs constant) rt = 1; else rt = 0;nbeq，bne可以和其他指令結(jié)合使用slt $t0, $s1, $s2 # if ($s1 $s2)$t0=1;bne $t0, $zero, L # $t0 not equal to zero branch

29、to LChapter 2 Instructions: Language of the Computer 40分支指令設(shè)計(jì)分支指令設(shè)計(jì)n為什么沒有blt，bge等指令？n硬件執(zhí)行, , 比=, 慢n指令中結(jié)合分支指令包含更多工作，需要更慢的時(shí)鐘n所有指令都受到了影響nBeq和bne是較常用的n這是一個(gè)很好的設(shè)計(jì)折中方案Chapter 2 Instructions: Language of the Computer 41有符號(hào)有符號(hào)數(shù)和數(shù)和無符號(hào)數(shù)無符號(hào)數(shù)對(duì)比對(duì)比n有符號(hào)數(shù)比較: slt, sltin無符號(hào)數(shù)比較: sltu, sltuin舉例n$s0 = 1111 1111 1111 1111

30、 1111 1111 1111 1111n$s1 = 0000 0000 0000 0000 0000 0000 0000 0001nslt $t0, $s0, $s1 # signedn1 +1 $t0 = 0Chapter 2 Instructions: Language of the Computer 42過程調(diào)用過程調(diào)用n遵循步驟1. 將參數(shù)放在過程可以訪問的寄存器里2. 將控制轉(zhuǎn)移給過程3. 獲得過程所需要的存儲(chǔ)資源4. 執(zhí)行過程的操作（請(qǐng)求的任務(wù)）5. 將結(jié)果的值放在調(diào)用程序可以訪問到的寄存器6. 將控制返回到調(diào)用點(diǎn)2.8 Supporting Procedures in Comp

31、uter HardwareChapter 2 Instructions: Language of the Computer 43寄存器的使用寄存器的使用n$a0 $a3: 傳遞參數(shù) (regs 4 7)n$v0, $v1: 返回結(jié)果值 (regs 2 and 3)n$t0 $t9: 臨時(shí)寄存器n可以被調(diào)用者改寫n$s0 $s7: 保存參數(shù)n必須被調(diào)用者保存和恢復(fù)n$gp: 靜態(tài)數(shù)據(jù)的全局指針寄存器(reg 28)nglobal pointer for static data (reg 28)n$sp: 堆棧指針寄存器stack pointer (reg 29)n$fp: 幀指針寄存器(fram

32、e pointer) ，n 保存過程幀的第一個(gè)字 (reg 30)n$ra:返回地址寄存器 return address (reg 31)Chapter 2 Instructions: Language of the Computer 44過程調(diào)用指令過程調(diào)用指令n過程調(diào)用：跳轉(zhuǎn)和鏈接jal ProcedureLabeln下一條指令的地址在寄存器$ra中n跳轉(zhuǎn)到目標(biāo)地址n過程返回:寄存器跳轉(zhuǎn) jump registerjr $ran拷貝$ra到程序計(jì)數(shù)器n也被用于運(yùn)算后跳轉(zhuǎn)n例如用于case/switcg分支語句e.gChapter 2 Instructions: Language of th

33、e Computer 45不調(diào)用其他過程（葉過程）例子不調(diào)用其他過程（葉過程）例子nC code:int leaf_example (int g, h, i, j) int f; f = (g + h) - (i + j); return f;n參數(shù) g, , j 在 $a0, , $a3中nf 在 $s0 (因此，需要存儲(chǔ)$s0到堆棧)n結(jié)果在$v0Chapter 2 Instructions: Language of the Computer 46不調(diào)用其他過程的例子不調(diào)用其他過程的例子nMIPS code:leaf_example: addi $sp, $sp, -4 sw $s0, 0

34、($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存儲(chǔ) $s0 到堆棧i+j-t1 過程體(g + h) - (i + j)恢復(fù) $s0結(jié)果 (s0-v0)返回參數(shù) g, , j 在 $a0, , $a3中;f 在 $s0 (因此，需要存儲(chǔ)$s0到堆棧);結(jié)果在$v0g+h-t0Chapter 2 Instructions: Language of the Computer 47嵌套過程嵌套過程非葉過程非葉過程

35、( (Non-LeafNon-Leaf Procedures) Procedures)n過程調(diào)用其他過程n對(duì)于嵌套調(diào)用，調(diào)用者需要存儲(chǔ)到堆棧的信息:n它的返回地址n調(diào)用后還需要用的任何參數(shù)寄存器和臨時(shí)寄存器n調(diào)用后返回，寄存器會(huì)從堆棧中恢復(fù)Chapter 2 Instructions: Language of the Computer 48嵌套過程舉例嵌套過程舉例 Non-Leaf Procedure ExampleNon-Leaf Procedure ExamplenC code:int fact (int n) if (n 1) return f; else return n * fact

36、(n - 1);n參數(shù)n放在 $a0n結(jié)果放在 $v0Chapter 2 Instructions: Language of the Computer 49嵌套過程舉例嵌套過程舉例 Non-LeafNon-Leaf Procedure Example Procedure ExamplenMIPS code:fact: addi $sp, $sp, -8 # adjust stack for 2 items sw $ra, 4($sp) # save return address sw $a0, 0($sp) # save argument（存參數(shù)） slti $t0, $a0, 1 # tes

37、t 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 returnL1: addi $a0, $a0, -1 # else decrement n jal fact # recursive call(遞歸調(diào)用) lw $a0, 0($sp) # restore original n lw $ra, 4($sp) # and return address addi $sp, $sp, 8 # pop 2

38、items from stack mul $v0, $a0, $v0 # multiply to get result jr $ra # and returnChapter 2 Instructions: Language of the Computer 50堆棧中的局部數(shù)據(jù)堆棧中的局部數(shù)據(jù) Local Data on the StackLocal Data on the Stackn局部數(shù)據(jù)有調(diào)用者分配ne.g., C 自動(dòng)分配變量n過程幀（活動(dòng)記錄）n被一些編譯器使用控制堆棧存儲(chǔ)Chapter 2 Instructions: Language of the Computer 51內(nèi)存布局內(nèi)

39、存布局Memory Layoutn正文：程序代碼n靜態(tài)數(shù)據(jù)：全局變量ne.g., C語言靜態(tài)變量，常數(shù)數(shù)組和字符串n$gp 初始化地址，允許段內(nèi)的 偏移n動(dòng)態(tài)數(shù)據(jù)：堆n堆棧：自動(dòng)存儲(chǔ)Chapter 2 Instructions: Language of the Computer 52字符數(shù)據(jù)字符數(shù)據(jù) （包括漢字）（包括漢字）n字節(jié)編碼的字符集nASCII: 128 個(gè)n95 graphic, 33 controlnLatin-1: 256 個(gè)nASCII, +96 more graphic charactersnUnicode: 32位字符集nUsed in Java, C+ wide cha

40、racters, n寬字符世界上大多數(shù)字母表nUTF-8, UTF-16: 可變長(zhǎng)度編碼2.9 Communicating with PeopleChapter 2 Instructions: Language of the Computer 53字節(jié)字節(jié)/ /半字操作半字操作 Byte/Byte/HalfwordHalfword Operations Operationsn使用位操作nMIPS字節(jié)/半字 讀取/存儲(chǔ) n字符串處理是較常用的方式lb rt, offset(rs) lh rt, offset(rs)nSign extend to 32 bits in rtlbu rt, offs

41、et(rs) lhu rt, offset(rs)nZero extend to 32 bits in rtsb rt, offset(rs) sh rt, offset(rs)n存儲(chǔ)恰恰是字節(jié)或半子的形式Chapter 2 Instructions: Language of the Computer 54字符串拷貝舉例字符串拷貝舉例 String Copy ExampleString Copy ExamplenC code (nave):n非終止字符串Null-terminated stringvoid strcpy (char x, char y) int i; i = 0; while

42、(xi=yi)!=0) i += 1; n假定x, y 基地址在 $a0, $a1中；ni 在 $s0 中。Chapter 2 Instructions: Language of the Computer 55字符串拷貝字符串拷貝String Copy ExamplenMIPS code:strcpy: addi $sp, $sp, -4 # 為保存i調(diào)整堆棧指針， sw $s0, 0($sp) # 把i送棧中【i在 $s0 中】 add $s0, $zero, $zero # 將i置“0”， 【i = 0+0】 L1: add $t1, $s0, $a1 # addr of yi in $t

43、1 lbu $t2, 0($t1) # $t2 = yi add $t3, $s0, $a0 # addr of xi in $t3 sb $t2, 0($t3) # xi = yi beq $t2, $zero, L2 # exit loop if yi = 0 addi $s0, $s0, 1 # i = i + 1 j L1 # next iteration of loopL2: lw $s0, 0($sp) # restore saved $s0 addi $sp, $sp, 4 # pop 1 item from stack jr $ra # and return假定x, y 基地址

44、在 $a0, $a1中, i 在 $s0 中Chapter 2 Instructions: Language of the Computer 560000 0000 0011 1101 0000 0000 0000 000032位常數(shù)位常數(shù) 32-bit Constantsn大部分常數(shù)都比較小，16位表示立即數(shù)足夠了，偶爾使用32位常數(shù)。nlui rt, constantn取立即數(shù)并放到高16位lui $s0, 610000 0000 0111 1101 0000 1001 0000 0000ori $s0, $s0, 23042.10 MIPS Addressing for 32-Bit I

45、mmediates and AddressesOri立即數(shù)或， $s0與常數(shù)2304“或”，結(jié)果放在$s0形成一個(gè)32位的常數(shù)Chapter 2 Instructions: Language of the Computer 57分支地址分支地址 Branch Addressingn分支指令說明n操作嗎，兩個(gè)寄存器，兩個(gè)地址n大多數(shù)跳轉(zhuǎn)目標(biāo)離跳出的位置較近n向前或向后oprsrtconstant or address6 bits5 bits5 bits16 bitsnPC相對(duì)尋址n目標(biāo)地址 = PC + offset 4n此時(shí)PC的增加量是4的倍數(shù)Chapter 2 Instructions:

46、Language of the Computer 58跳轉(zhuǎn)地址跳轉(zhuǎn)地址Jump Addressingn跳轉(zhuǎn)（j和jal）的目標(biāo)地址可以在代碼段的任何位置n指令除op外，指令其它字段都是地址opaddress6 bits26 bitsn直接跳轉(zhuǎn)到地址nTarget address = PC3128 : (address 4)28位4位Chapter 2 Instructions: Language of the Computer 59目標(biāo)地址目標(biāo)地址 Target Addressing Examplen早期例子的循環(huán)代碼n設(shè)循環(huán)的起始地址是8000 Loop: sll $t1, $s3, 280

47、0000019920 add $t1, $t1, $s68000409229032 lw $t0, 0($t1)8000835980 bne $t0, $s5, Exit8001258212 addi $s3, $s3, 180016819191 j Loop80020220000Exit: 80024Chapter 2 Instructions: Language of the Computer 60遠(yuǎn)程分支遠(yuǎn)程分支Branching Far Awayn如果跳轉(zhuǎn)對(duì)象地址太大無法用16位的偏移表示，匯編將重寫代碼n【把短跳轉(zhuǎn)（216 范圍）n 變成長(zhǎng)跳轉(zhuǎn)（2 22626 范圍）】nExampl

48、ebeq $s0,$s1, L1bne $s0,$s1, L2j L1L2: Chapter 2 Instructions: Language of the Computer 61地址模式總結(jié)地址模式總結(jié) Addressing Mode SummaryAddressing Mode SummaryChapter 2 Instructions: Language of the Computer 622.11并行與指令：同步并行與指令：同步n處理器共享存儲(chǔ)器同一區(qū)域nP1 寫, P2 讀n（任務(wù)1寫的結(jié)果是任務(wù)2要讀取得值）n如果P1和P2不同步，將發(fā)生數(shù)據(jù)競(jìng)爭(zhēng)n結(jié)果由訪問次序決定n依賴硬件提供同

49、步指令n（例如：lock和unlock指令，控制一個(gè)“互斥區(qū)”）n多核處理器的情況下：n任務(wù)1 Sw $t0,0($s0)n任務(wù)2 Lw $t1,0($s0)n此時(shí)，任務(wù)2和任務(wù)1必須同步，否則，無法判斷$t1中讀取的是$t0,還是0（$s0）單元以前的數(shù)值。2.11 Parallelism and Instructions: SynchronizationChapter 2 Instructions: Language of the Computer 632.11并行與指令：同步并行與指令：同步n原子讀原子讀/ /寫內(nèi)存操作寫內(nèi)存操作n在讀和寫之間，不再允許對(duì)該空間的其他操作n可以是單一的指

50、令n例如寄存器和內(nèi)存之間的原子交換n或者指令的原子配對(duì)2.11 Parallelism and Instructions: SynchronizationChapter 2 Instructions: Language of the Computer 64MIPS中的同步中的同步Synchronization in MIPS n鏈接取數(shù)(Load linked) nll rt, offset(rs)n條件存數(shù)(Store conditional) nsc rt, offset(rs)n如果ll指令沒改變?cè)摰刂穬?nèi)容則成功，rt返回1；n如果被改變了，則失敗，rt返回0；n例如：atomic sw

51、ap (檢測(cè)和設(shè)置鎖變量)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 $s4Chapter 2 Instructions: Language of the Computer 65編譯并執(zhí)行程序編譯并執(zhí)行程序 Translation and StartupTranslation and

52、Startup許多編譯器直接產(chǎn)生目標(biāo)模塊靜態(tài)鏈接2.12 Translating and Starting a ProgramChapter 2 Instructions: Language of the Computer 66匯編偽指令匯編偽指令 Assembler Pseudo InstructionsAssembler Pseudo Instructionsn大多數(shù)匯編指令和機(jī)器指令是一對(duì)一的n特殊的是偽指令n偽指令：匯編指令的變種nmove $t0, $t1move $t0, $t1add $t0, $zero, $t1bltblt $t0, $t1, L $t0, $t1, L sl

53、t $at, $t0, $t1bne $at, $zero, Ln$at (register 1): 匯編程序的臨時(shí)寄存器（使用匯編語言時(shí)候的硬件額外的開銷）Chapter 2 Instructions: Language of the Computer 67生成目標(biāo)模塊生成目標(biāo)模塊Producing an Object ModuleProducing an Object Modulen匯編器（或編譯器）把程序翻譯成機(jī)器語言n提供從部分構(gòu)建完整程序的信息n 目標(biāo)文件頭：描述目標(biāo)文件其他部分的大小和位置n正文段：翻譯后的指令，包含機(jī)器語言代碼n靜態(tài)數(shù)據(jù)段：包含在程序生命周期內(nèi)分配的數(shù)據(jù)n重定位信

54、息，標(biāo)記了一些程序加載進(jìn)內(nèi)存時(shí)依賴于絕對(duì)地址的指令和數(shù)據(jù)n符號(hào)表，全局定義和外部引用n調(diào)試信息：用于關(guān)聯(lián)源文件Chapter 2 Instructions: Language of the Computer 68鏈接目標(biāo)模塊鏈接目標(biāo)模塊 Linking Object Modulesn產(chǎn)生一個(gè)可執(zhí)行的映像1. 合并段（代碼和數(shù)據(jù)數(shù)據(jù)庫象征性放入內(nèi)存）2. 決定數(shù)據(jù)和指令標(biāo)簽的地址3. 修補(bǔ)引用（內(nèi)部和外部引用）n可以留下依靠重定位程序修復(fù)的部分n但虛擬內(nèi)存，不需要做這些n虛擬內(nèi)存空間，程序必須以絕對(duì)地址裝入Chapter 2 Instructions: Language of the Compu

55、ter 69加載程序加載程序Loading a Programn把待執(zhí)行的程序從硬盤的鏡像文件讀入內(nèi)存1. 讀取可執(zhí)行文件頭來確定正文段和數(shù)據(jù)段的大小2. 為正文和數(shù)據(jù)創(chuàng)建一個(gè)足夠大的地址空間3. 把指令和初始數(shù)據(jù)拷貝到內(nèi)存或者設(shè)置頁表項(xiàng),使它們可用4. 把主程序的參數(shù)復(fù)制到棧頂5. 初始化寄存器（包括堆棧指針$sp, 幀指針$fp, 全局指針$gp ）6. 跳轉(zhuǎn)到啟動(dòng)進(jìn)程n復(fù)制參數(shù)到寄存器并調(diào)用主函數(shù)mainn主函數(shù)返回時(shí)，通過系統(tǒng)調(diào)用exit終止程序Chapter 2 Instructions: Language of the Computer 70動(dòng)態(tài)鏈接庫動(dòng)態(tài)鏈接庫Dynamic Li

56、nkingDynamic Linkingn調(diào)用時(shí)，只是連接或裝入庫文件n過程代碼重定位；n避免所有程序中出現(xiàn)的鏈接庫；但是這些庫的信息是一次性代入內(nèi)存，占用內(nèi)存空間。只是在用到的時(shí)候才鏈接該庫；n自動(dòng)裝入最新的編譯器中的版本的動(dòng)態(tài)庫。Chapter 2 Instructions: Language of the Computer 71晚過程連接晚過程連接 Lazy Linkage（只是在用到的時(shí)候才鏈接該庫只是在用到的時(shí)候才鏈接該庫）Indirection tableStub: Loads routine ID,Jump to linker/loaderLinker/loader codeDy

57、namicallymapped codeChapter 2 Instructions: Language of the Computer 72啟動(dòng)一個(gè)啟動(dòng)一個(gè)Java程序程序 Starting Java ApplicationsSimple portable instruction set for the JVMInterprets bytecodesCompiles bytecodes of “hot” methods into native code for host machineChapter 2 Instructions: Language of the Computer 73C S

58、ort Examplen使用匯編指令的冒泡排序n（交換內(nèi)存中兩個(gè)位置所存的值）nSwap procedure (leaf)void swap(int v, int k) int temp; temp = vk; vk = vk+1; vk+1 = temp;nv in $a0, k in $a1, temp in $t02.13 A C Sort Example to Put It All TogetherChapter 2 Instructions: Language of the Computer 74SwapSwap過程過程 The Procedure SwapThe Procedure

59、 Swapswap: sll $t1, $a1, 2 # $t1 = k * 4 （按照字節(jié)編址） add $t1, $a0, $t1 # $t1 = v+(k*4) # (address of vk) lw $t0, 0($t1) # $t0 (temp) = vk lw $t2, 4($t1) # $t2 = vk+1 sw $t2, 0($t1) # vk = $t2 (vk+1) sw $t0, 4($t1) # vk+1 = $t0 (temp) jr $ra # return to calling routineC代碼 （按照字編址） MIPS代碼（按照字節(jié)編址）1、為程序變量分配

60、寄存器； 【v in $a0, k in $a1, temp in $t0】2、為過程體生成匯編代碼；3、保存過程調(diào)用間的寄存器（本例中沒有用到，因?yàn)楸纠且粋€(gè)葉過程）；Chapter 2 Instructions: Language of the Computer 75編譯優(yōu)化的影響編譯優(yōu)化的影響 Effect of Compiler OptimizationEffect of Compiler Optimization1、編譯時(shí)間2、指令數(shù)；3、時(shí)鐘周期4、CPI5、算法執(zhí)行時(shí)間是準(zhǔn)確衡量程序性能的唯一標(biāo)準(zhǔn)Chapter 2 Instructions: Language of the Computer 76經(jīng)驗(yàn)教訓(xùn)經(jīng)驗(yàn)教訓(xùn) Lessons Lea