chap3

Report
第三章
電腦的語言:指令
計算機組織與設計
蔡昌隆
學貫行銷股份有限公司
學習目標
•瞭解高階語言和低階語言的區別
•瞭解控制電腦硬體實際運作的機器語言
•瞭解電腦硬體如何執行運算
•瞭解組合語言(MIPS)的定址法和程式設
計
前
言
• 電腦溝通的語言,其單字即為指令,而字彙就是
指令集,將很多指令集彙集編成一個可以命令電
腦去執行並達成計畫目標的就叫做程式。
• 主程式(main program):顧名思義即為最主要
的程式或者說是程式的主體部分,為一個完整可
以執行的指令集。
• 副程式或副常式(subroutine):涵蓋在主程式
中的一小部分獨立的迴圈或疊代處理的程式或是
獨立於主程式之外,可透過主程式的程序呼叫去
執行主程式所交付的任務。
•一般程式語言主要區分為高階程式語言和低階程
式語言(包括組合語言與機器語言等),這些語言
都是我們和電腦溝通所使用的工具,它們的功能
屬性各有不同,而使用高階語言來撰寫程式的好
處是可以避免使用標籤來執行跳躍的動作,因為
那會增加程式預測所需付出的作業時脈週期。
程式語言
程式語言的分類
類
別 功
能
屬
性 執 行 效 能 優
高階語言
須經轉換成低階語言、
機器語言方能交由微處
理器執行的語言;如應
用程式軟體或C++、
Fortran和Java等
低階語言
屬於和機器硬體溝通的
語言
組合語言
可被轉換成機器可以執
行的二進位的符號語言, 執行速度快
如MIPS或Assembly
機器語言
直接與微處理溝通並執
行實際工作的語言
執行速度相對
較慢
執行速度快
執行速度最快
點 缺
點
程式發展與修改快;
容易閱讀和維護; 占記憶體
可攜性高;試窗系 空間較大
統互動性良好
不易閱讀和維護
略占記憶
體空間
可獲得儲存空間和 占記憶體
執行時間上的效益。 空間較小
由系統程式直接轉
換語言,不須維護
程式語言的發展
• 真空管時期(1946~1954年期間):為美軍委託賓
州大學研成ENIAC計算機後所使用的語言,含機
器語言和組合語言。
• 電晶體時期(1955~1964年期間):為因應美國
AT&T貝爾實驗室(Bell Laboratory)發明電晶體
後,新一代使用電晶體的電腦問市後所使用的程
式語言含COBOL、LISP和FORTRAN等。
•積體電路(IC,Integrated Circuit)時期
(1965~1974年期間):為因應德州儀器開發出積體
電路後,IBM S/360等電腦所使用的程式語言,以
BASIC為主。
•超大型積體電路(VLSI,Very Large Scale
Integrated Circuit)時期(1975迄今):在Intel
公司推出4004微處理器以後所使用的程式語言,
含PL/1、PASCAL、C、MIPS、Ada、C++和Java等等。
•未來程式語言的發展主要朝向問題導向和程序導
向,應屬結合平行處理和人工智慧的產品。
• 雖然我們使用很多的多媒體或文書編譯軟體,其
實它們都是透過高階程式語言或低階程式語言所
開發出來的,透過這些方便的介面,讓我們駕馭
電腦去完成任務更顯得輕鬆方便又有效率。
• 在計算機組織系統中比較重要而經常探討的便是
MIPS組合語言(含MIPS-32和MIPS-64),它是1980
年代的產品,目前有超過上億的處理器使用MIPS
組合語言。
硬體運算元
•電腦中數值的運算都是透過邏輯電路來執行計算
的,它會將你所輸入的資料放到暫存器裡面,再
把它輸入算術邏輯運算單元去做處理,最後送出
答案給你,其中暫存器的大小會直接的影響到你
所能計算的數值的最大或最小值,而暫存器的數
量多寡則會影響到運算的效率,然而並不是越多
的暫存器就會執行越快,因為過多的暫存器會增
長時脈週期的時間,如此一來反而降低執行效能,
一般電腦的暫存器多為32個。
•電腦亦據此以32位元或64位元為基做計算,而計
算的基本單位通常為字組(word),即1個字組為32
位元,而MIPS組合語言系統對字組有定位排列的
限制(alignment restriction),所以程式執行
所使用的暫存器都必須使用4的倍數當起始的位址。
每當執行一個指令,程式計數器便會累加1,然後
擷取下一行的指令,而下一行的指令其對應儲存
在指令記憶體中的位址便是按4的倍數排列(如下
圖),這即是MIPS系統的對應規則。
硬體運算元
暫存器
高位址
4的倍數
資料
8
資料
4
資料
低位址0
• Intel公司最初所推出的8位元處理器,其資料暫存器僅有
A、B、C和D等四個;其後的16位元處理器的暫存器定名為
AX、BX、CX和DX,再透過H(high)和L(low)來表示屬
於高位元或低位元,例如AH或AL。隨著32位元處理器的問
市,IA-32系統則使用EAX、EBX、ECX和EDX來代表暫存器,
其前面加上的“E”表示延伸或擴展
高位元31
AX
0低位元
16
EAX
AH
AL
ECX
CH
CL
EDX
DH
DL
EBX
BH
BL
副程式的執行步驟
•
•
•
•
•
•
參數需儲存在副程式可以讀取或儲存的位址。
由副程式控制執行工作。
副程式擷(讀)取所需的儲存資料。
執行運算。
運算結果回傳給呼叫副程式可以儲存的位址。
副程式將控制權交回給主程式。
MIPS暫存器
•MIPS系統中執行運算的暫存器有32個
•編號0:$zero(零值暫存器)
•編號1:$at(組譯器使用的暫存器)
•編號2~3:$v0~$v1(回傳值暫存器)
•編號4~7:$a0~$a3(參數暫存器,argument
pointer)
•編號8~15:$t0~$t7(暫時暫存器,temporary
pointer)
MIPS暫存器
• 編號16~23:$s0~$s7(儲存暫存器,saved
pointer)
• 編號24~25:$t8~$t9(暫時暫存器)
• 編號26~27:$k0~$k1(作業系統使用的暫存器)
• 編號28:$gp(全域性指標暫存器,global
pointer):為儲存指引靜態資料區塊位址的暫存
器。
• 編號29:$sp(堆疊指標暫存器,stack pointer)
• 編號30:$fp(框指標暫存器,frame pointer) :
為儲存指引到程序框第一個字組位址的暫存器。
• 編號31:$ra(回傳位址暫存器,return
address) :為儲存指引返回原來位址的暫存器。
• $s0~$s7和$ra屬於堆疊指標位址以上的記憶體,
在程序呼叫時,被呼叫者”必須”暫時儲存這些
暫存器的資料;而$t0~$t9、$a0~$a3和$v0~$v1
則為堆疊指標位址以下的記憶體,在程序呼叫時,
被呼叫者”不需”暫時儲存這些暫存器的資料
• 例題:撰寫MIPS程式將堆疊中空出三個暫存器來儲存資料
• 說明:
步驟一:空出堆疊空間,可以使用立即加法指令
addi $sp, $sp, -12
空出三個儲存空間
等於是撥出3*4=12個位址
所以將堆疊指標-12
步驟二:將空出的空間儲存資料
sw
$s0, $0($sp) 將$s0儲存到堆疊中
sw
$s1, $4($sp) 將$s1儲存到堆疊中
sw $s2, $8($sp) 將$s2儲存到堆疊中
• 執行程序呼叫的時候,會使用堆疊指標來標定堆疊資料的
起始位址,而程序結構指標或框架指標(frame pointer)
則指引到程序或副程式的第一個字組
$fp
$sp
$fp
程序呼叫
前的指標
指引情形
因尚未開
始堆疊資
料,所以
$sp指到
堆疊最上
面
$fp
$sp
參數
暫存器
回傳位址
暫存器
儲存
暫存器
區隔性的
$sp 陣列與結構
堆疊指標
程序呼叫時的
指標指引情形
完成程序
呼叫後,
指標會返
回原來的
指引位置
•
•
•
位址:好比家裡的地址,可以清楚的指引郵差
送信到該地址;而該位址裡所存放的資料,就
好比家裡的設備配備等等。
呼叫者(caller):啟動程序或副程式並給予相
關的參數交給被呼叫者去執行。
被呼叫者(callee):根據呼叫者提供的資訊
(如指令和參數)來執行相關作業,當作業執行
完畢後會立即將控制權交還給呼叫者。
•
•
程式計數器(PC,program counter):用來標定
執行中的指令是儲存在指令暫存器的那一個位址,
以便讀取該位址相應的指令碼來執行後續的工作。
MIPS組合語言系統只提供$a0~$a3四個暫存器給
參數使用,若是超過四個以上的參數時,超過的
參數部分會被放在程序框指標上方的堆疊;通常
程式執行時,程序會預測前四個參數是放在
$a0~$a3並自動擷取,而其他的參數則由$fp指標
來指出它們在記憶體中所對應的位址。
記憶體最下層的部分是保留區塊,依序往上為儲存程式機器
碼的本文區塊(text segment),再往上為放置靜態變數和常
數部分的靜態資料的儲存區塊(static data segment),最
上層的部分則市儲存動態變數的動態資料區塊
記憶體
指標$sp
堆疊
位址
7fff fffc
動態資料區塊
指標$gp
靜態資料區塊
程式碼
本文區塊
程式計數$pc
起始
保留區塊
1000 8000
1000 0000
0040 0000
0000 0000
•例題1:使用暫存器來編撰C程式為x=i+j;
•說明:
步驟一:先指定暫存器給變數
將i存在來源暫存器1=$s1
j存在來源暫存器2=$s2
運算結果值x儲存在目的地暫存器=$t0
步驟二:編撰MIPS程式
add $t0, $s1, $s2
•例題2:使用暫存器來編撰C程式為x=(i+j)-k;
•說明:
步驟一:先指定暫存器給變數
將i存在暫存器$s1
j存在暫存器$s2
k存在暫存器$s3
運算的結果值x儲存在目的地暫存器=$t0
步驟二:編撰MIPS程式
add $t0, $s1, $s2
完成i+j
sub $t0, $t0, $s3
完成i+j-k
• 例題3:假設X陣列的基底位址為$s1,變數Y對應暫存器
$t0,使用暫存器來編撰C程式為X〔100〕= X〔100〕+ Y;
• 說明:
步驟一:先指定暫存器給變數
X〔100〕的值存在暫存器$s1,位址為400
運算後的和存在暫存器$t1
步驟二:編撰MIPS程式
lw $t1, 400($s1) 暫存器$t1存放X〔1〕的值
add $t1, $t0, $t1
 X〔100〕+ Y
sw $t1, 400($s1)  X〔100〕+ Y的值儲存到X
〔100〕
※註:X〔100〕的位址為4*100=400。
• 例題6:撰寫常數10和暫存器$s2相加的MIPS程式
• 說明:
1. 解法一:使用立即加法,格式如下
程式碼為
addi $s2, $s2, 4
 $s2=$s2+4;
2. 解法二:使用加法
lw $t0, 4
 將常數載入$t0暫存器
add $s2, $s2, $t0  執行$s2+4
程式
執行碼
來源暫存
器rs
來源暫存
器rt
6欄位
5欄位
5欄位
常數
或位址
16欄位
電腦硬體的運算
• 電腦運算不外乎加、減、乘、除和資料的交換應
用,本節將以例題說明的方式來闡述電腦中硬體
的運算。
• 以MIPS執行運算為例,其指令相對應的欄位內容
概略如下:
程式
執行碼
來源暫存
器rs
來源暫存
器rt
目的地暫
存器
6欄位
5欄位
5欄位
5欄位
位移量
5欄位
函數
功能
6欄位
• 例題1:將MIPS指令add $t0, $s1, $s2轉譯成機器碼
• 說明:
1. 步驟一:$t0=8(目的地暫存器)
$s1=17(來源暫存器1)
$s2=18(來源暫存器2)
將暫存器內儲存的值以十進位數值表示如下:
0
17
18
8
0
32
2.步驟二:轉換成二進位的機器碼如下:
000000
10001
10010
01000
00000
3.步驟三:轉換成十六進位後的數值為
000000100011001001000000001000002=0232402016
100000
• 例題2:請問機器碼0253982016的意義
• 說明:
1. 步驟一:將16進位機器碼02539820轉換成2進位
轉換後的數值為
000000100101001110001000001000002
2. 步驟二:依MIPS指令格式的欄位劃分32位元的2
進位數值如下:
程式碼 來源暫存器1 來源暫存器1 目的地暫存器 位移量 函式
000000
10010
10011
10001
00000 100000
18=$s2
19=$s3
17=$s1
所以轉換後的MIPS程式碼為
add $s1, $s2, $s3
•資料交換為程式撰寫中常用的一部分
•C程式語言中,我們常用的資料交換程式內容概下:
Temp = X;
X = Y;
Y = Temp;
如此即完成X和Y的資料交換。
•例題3:以MIPS語言撰寫暫存器中資料的交換
•說明:假設X存在暫存器$s0中,而Y存在暫存器
$s1
將X和Y的資料交換,程式如下:
lw $t0, X
 將X存到暫時的暫存器$t0
sw $s0, Y
 將Y存到$s0
sw $s1, $t0  將X由$t0轉存到$s1完成資
料交換
•組合語言:
move $t0, $s0  將X存到暫時的暫存器$t0
move $s0, $s1  將Y存到$s0
move $s1, $t0  將X由$t0轉存到$s1
算術邏輯單元控制器
•通常算術邏輯單
元(ALU)的運
算會由一個控制
器來主導其執行
內容,該控制器
有4條訊號線,
其控制算術邏輯
單元的參照表如
右:
訊號線功能參照表
控制器
4條訊號線的內容
算術邏輯單元
執行功能
0000
及運算(and)
0001
或運算(or)
0010
加法(add)
0110
減法(sub)
0111
小於時設定(set
on less than)
1100
反或運算(nor)
MIPS組合語言
• 語言架構、邏輯運算、決策指令:將C程式語言轉
譯成MIPS組合語言的主要工作是由編譯器所負責
的,按MIPS-32指令集架構(ISA;Instruction
Set Architecture)所設計的指令都是以32位元
模式執行
• 處理暫存器:
1. 32個32位元的一般用途暫存器(GPRs,general
propose register),其中R0設定永遠為0。
2. 16個雙倍精準度和32個單倍精準度的浮點數用途
暫存器(FPRs,floating-point propose
register)。
3. 浮點狀態暫存器支援比較和例外功能。
4. 此外尚有其他特殊用途的暫存器。
• 資料型態:包含有8位元組、16位元半字元、32
位元整數字元、32位元單倍精準度浮點數、64
位元雙倍精準度浮點數。
• 讀取和儲存型式的指令集:
1. 資料位址包含立即和索引2種模式。
2. 分節(跳躍)位址包含程式計數相對和暫存器非
直接對應模式。
3. 陣列位元組資料載入和儲存的位址表示法
MIPS組合語言的基本格式
• 算數邏輯運算(ALU)
程式
執行碼
6欄位
來源暫
存器rs
5欄位
來源暫
存器rt
5欄位
目的地
暫存器
5欄位
函數
功能
5欄位 6欄位
0
• 算數邏輯立即運算(ALUi)
程式
執行碼
來源暫
存器rs
來源暫
存器rt
6欄位
5欄位
5欄位
立即
immediate
16欄位
• 記憶體(Mem)的操作
程式
執行碼
來源暫
存器rs
來源暫
存器rt
6欄位
5欄位
5欄位
差量
displaceme
nt
16欄位
• 條件式的跳躍(beqz和bnez)
程式
執行碼
來源暫
存器rs
6欄位
5欄位
補償
offset
5欄位
16欄位
• 非條件式的非直接跳躍(jr和jalr)
程式
執行碼
來源暫
存器rs
6欄位
5欄位
5欄位
16欄位
• 非條件式的絕對跳躍(j和jal)
程式
執行碼
6欄位
補償
offset
26欄位
• MIPS組合語言程式執行時的五個工作程序
1. 擷取(讀)程式碼(指令)。
2. 解碼(瞭解指令所要執行的工作及要讀取的暫
存器所儲存的資料)。
3. 邏輯運算(交給ALU單元執行運算工作)。
4. 記憶體作業(可選擇)。
5. 寫回(write back)並計算下一個指令的位址。
MIPS組合語言常用指令
•
1.
2.
3.
4.
5.
資料的讀取(載入)指令:
讀取位元組lb(load byte)
讀取無號的位元組lbu(load byte unsigned)
讀取半字組lh(load half)
讀取字元組lw (load word)
立即讀取上半部的高位元資料lui
•例題1:lw $s1, $s2
•說明:將暫存器$s2位址中所儲存的資料放到暫
存器$s1位址上。
•例題2:lw $s1,10
•說明:將常數值10放到暫存器$s1位址上。
•
1.
2.
3.
4.
資料的儲存指令
儲存位元組sb(save byte)
儲存無號的位元組sbu(save byte unsigned)
儲存半字組sh(save half)
儲存字元組sw (save word)
•例題1:sw $s1, $s2
•說明:將暫存器$s2位址的資料儲存到暫存器$
s1位址中。
•例題2:sw $s1, 10
•說明:將常數值10儲存至暫存器$s1位址中。
加減乘除的計算
• 加法的計算:指令add $s1, $s2, $s3
• 立即加法的計算:指令addi $s1, $s2,
constant(常數值)
• 例題1:add $s1, $s2, $s3
• 說明:將暫存器$s2位址所儲存的資料和暫存器
$s3位址所儲存的資料相加後,儲存到暫存器$
s1的位址上。
• 例題2:addi $s1, $s2, 10
• 說明:將暫存器$s2位址所儲存的資料和常數值
10相加後,儲存到暫存器$s1的位址上。
•減法計算:指令sub $s1, $s2, $s3
•例題1:sub $s1, $s2, $s3
•說明:將暫存器$s2位址所儲存的數值和暫存器
$s3位址所儲存的數值相減($s2-$s3)後,儲
存到暫存器$s1的位址上。
•例題2:暫存器$s2位址所儲存的資料減去常數值
10後,儲存到暫存器$s1的位址上
•說明:
sw $t0, 10 將常數10存到暫時暫存器$t0;
也可以使用lw $t0, 10的程式寫法
sub $s1, $s2, $t0 $s2暫存器所儲存的
數值減去$t0暫存器所儲存的數值(常數10),
所得的差儲存到$s1暫存器
•因為C和Java程式語言不常使用負值的常數來執行
運算,因需求不多,所以MIPS組合語言中沒有立
即減法的指令設計;而若要處理負值的常數計算,
可使用立即定址法的指令格式來撰寫程式,只需
將負值的常數放在立即值的欄位即可
程式
執行碼
來源暫存器
rs
來源暫存器
rt
6欄位
5欄位
5欄位
立即欄位
(負的常數值)
16欄位
•乘法計算:指令mult $s1, $s2, $s3
•例題1:mult $s1, $s2, $s3
•說明:將暫存器$s2位址所儲存的數值和暫存器
$s3位址所儲存的數值資料相乘($s2*$s3)
後,儲存到暫存器$s1的位址上。
•例題2:將暫存器$s2位址所儲存的數值乘上常數
值10後,儲存到暫存器$s1的位址上
•說明:
sw
$t0, 10 將常數10存到暫時暫存器$t0
mult $s1, $s2, $t0 $s2暫存器所儲存的
數值乘上$t0暫存器所儲存的數值(常數10),
所得的積儲存到$s1暫存器
•除法計算:指令div $s1, $s2, $s3
•例題1:div $s1, $s2, $s3
•說明:將暫存器$s2位址所儲存的數值除以暫存
器$s3位址所儲存的數值($s2/$s3)後,所得
到的商數儲存到暫存器$s1的位址上。
•例題2:將暫存器$s2位址所儲存的資料除以常數
值5後所得到的商數儲存到暫存器$s1的位址上
•說明:
sw $t0, 10 將常數10存到暫時暫存器$t0
div $s1, $s2, $t0 $s2暫存器所儲存的
數值除以$t0暫存器所儲存的數值(常數5),所
得的商數儲存到$s1暫存器
• 數值的比較
1.小於時設定slt(set on less than)
2.小於時立即slti(set on less than)
3.無號值小於時sltu
4.無號值小於時立即sltiu
• 例題1:slti $s1, $s2, 8
• 說明:假如暫存器$s2位址所儲存的數值小於常數8
時,設定暫存器$s1位址所儲存的數值為1,若是大
於或等於常數8時則將暫存器$s1位址所儲存的數值
為0。
本例子相當於C程式
if ( $s2 < 10 )
$s1=1;
else $s1=0
•例題2:slt $s1, $s2, $s3
•說明:假如暫存器$s2位址所儲存的數值小於暫
存器$s3位址所儲存的數值時,設定暫存器$s1
位址所儲存的數值為1,若是大於或等於常數10時
則將暫存器$s1位址所儲存的數值為0。
本例子相當於C程式
if ($s2 < $s3 )
$s1=1;
else $s1=0;
•
1.
2.
•
•
•
•
資料的移位(shift)
資料向左移位sll(shift left logic)指令(亦即C或
Java程式中的”<<”運算)
資料向右移位srl(shift right logic)指令(亦即C
或Java程式中的”>>”運算)
例題1:sll $s1, $s2, 8
說明:將暫存器$s2位址所儲存的數值向左移位8個位
元後所得的新值儲存到暫存器$s2的位址上。
例題2:srl $s1, $s2, 6
說明:將暫存器$s2位址所儲存的數值向右移位6個位
元後所得的新值儲存到暫存器$s2的位址上。
•
1.
2.
3.
4.
5.
邏輯運算
或的運算or指令
及的運算and指令
反的運算not指令
非或的運算nor (not or)指令
立即執行及的運算andi (and immediate)指
令
6. 立即執行或的運算ori (or immediate)指令
•例題1:or $s1, $s2, $s3 (亦即$s1 = $
s2 | $s3)
•說明:將暫存器$s2位址所儲存的數值和暫存器
$s3位址所儲存的數值執行“或”的運算後所得
到的新值儲存到暫存器$s1的位址上。
•例題2:and $s1, $s2, $s3
(亦即$s1 =
$s2 & $s3)
•說明:將暫存器$s2位址所儲存的數值和暫存器
$s3位址所儲存的數值執行“及”的運算後所得
到的新值儲存到暫存器$s1的位址上。
•例題3:nor $s1, $s2, $s3 (亦即$s1 = ~
($s2 | $s3))
•說明:將暫存器$s2位址所儲存的數值和暫存器
$s3位址所儲存的數值執行“非或”的運算後所
得到的新值儲存到暫存器$s1的位址上。
• 條件式控制或決策指令:如同C++程式中所使用
的 goto或if-then-elseif等的程式敘述:
1. 等於時跳躍到分節(或分支)標籤beq(branch
if equal)指令
2. 等於零時跳躍到分節標籤beqz(branch if
equal zero)指令
3. 不等於時跳躍到分支標籤bne(branch if not
equal)指令
4. 不等於零時跳躍到分支標籤bnez(branch if
not equal zero)指令
•例題1:be $s1, $s2, loop
•說明:當暫存器$s1位址所儲存的數值和暫存器
$s2位址所儲存的數值相等時跳躍到loop執行。
•例題2:bne $s1, $s2,loop
•說明:當暫存器$s1位址所儲存的數值和暫存器
$s2位址所儲存的數值不相等時跳躍到loop執行。
•
1.
2.
3.
•
•
•
•
•
•
無條件式控制或決策指令
跳躍j(jump)指令—相當於C程式中goto的指令
依據暫存器跳躍jr (jump register)指令
跳躍並且連結jal (jump and link)指令
例題1:j loop
說明:跳躍到標籤為loop的指令位置執行後續的
程式。
例題2:jr $ra
說明:跳躍到回傳暫存器所儲存的位址。
例題3:jal swap
說明:跳躍到swap程序,執行資料交換處理作業
的副程式。
• 例題4:C程式內容為if (i==j) X=Y+Z; else X=Y-Z;
請以MIPS程式語言改寫上述程式內容
• 說明:
步驟一:畫出流程圖
yes
X=Y+Z
If
i==j
no
X=Y-Z
步驟二:編撰程式(可以使用beq或bne的方式來執行)將
C程式中的五個變數對應到五個暫存器
i對應$s0、j對應$s1、X對應$s2、Y對應$s3、Z對
應$s4
解法一:使用beq撰寫程式
beq $s0, $s1, else  i=j時跳躍到else
i≠j時執行下一行指令
sub $s2, $s3, $s4  X=Y-Z
j exit
 jump跳躍到exit
else: add $s2, $s3, $s4  X=Y+Z
exit
 結束程式
解法二:使用bne撰寫程式
bne $s0, $s1, else  i≠j時跳躍到else
i=j時執行下一行指令
add $s2, $s3, $s4  X=Y+Z
j exit
 jump跳躍到exit
else: sub $s2, $s3, $s4
 X=Y-Z
exit
 結束程式
迴圈控制
• C程式語言中經常會使用迴圈來執行副程式或程序的呼叫
作業,然MIPS組合語言中並無相關的指令,在MIPS程式中
主賴跳躍的指令來完成迴圈的運算。
• 例題1:C程式內容 while (X〔i〕==j)
i+=1;
請以MIPS程式語言改寫上 述程式內容
• 說明:步驟一:畫出流程圖
I=1
yes
while
X[i]=
=j
no
i=i+1
• 步驟二:編撰程式(可以使用beq或bne的方式來執行)
將C程式中的變數給予相對應的暫存器
X陣列的基底為暫存器$s0、i對應$s1、j對應$s2
loop: sll $t0, $s1, 2 為表示X陣列第i個數值
的位址,使用向左位移2
個位元(等於乘4)來計
算,$t0=4*i
add $t0, $t0, $s0
將X〔i〕的位址存到$t0
lw $t1, 0($t0)
 $t1=X〔i〕
bne $t1, $s2, exit  當X〔i〕=k跳躍到exit
addi $s1, $s1, 1
 i=i+1
exit
 結束程式
• 浮點運算指令
1. 加法:add.s/add.d
2. 減法:sub.s/sub.d
3. 乘法:mul.s/mul.d
4. 除法:div.s/div.d
5. 條件跳躍:
(1)bclt(成立狀況下跳躍)
(2)bclf(不成立狀況下跳躍)
• 在32位元的微處理器中,有關IA-32的算數邏輯
運算大概區分如下:
1. 資料搬移:常用的指令有move、pop和push,另
有字串的搬移(movw、movs、movsl 、les、lods、
cbw)和字串的比較。
2. 算數邏輯運算:指令包括有比較(cmp)、測試
(test)、邏輯運算(or、xor、)、移位(shl
左移、shr右移、rcr右移並進位)整數和十進位
的計算(add、sub)。
3. 控制(迴圈loop或決策)指令:包含有“條件式”
跳躍(jnz、jz)和“無條件式”的跳躍(jmp)
以及程序呼叫(call)和返回(ret)程式主體
的控制指令等等。
MIPS定址法
IA-32的定址法
定址模式
暫存器定址法
定址函式
EA=暫存器
組譯的程式語法
reg
立即定址法
運算元=數值
value
暫存器間接
定址法
EA=〔暫存器〕
〔reg〕
直接定址法
EA=位置
location
具差量之基底
定址法
EA=〔暫存器〕+差量
具差量之索引
定址法
EA=〔暫存器〕*索引+差量
具索引之基底
定址法
EA=〔暫存器1〕+〔暫存器2〕*索引
〔reg1+reg2*index〕
具索引與差量之基
底定址法
EA=〔暫存器1〕+〔暫存器2〕*索引
+差量
〔reg1+reg2*index+
displacement〕
〔reg+displacement〕
〔reg*index+
displacement〕
• 暫存器定址法:使用暫存器來當作運算元的指令
格式
程式碼
rs
rt
rd
…
funct
暫存器
• 例如: add $s0, $s1, $s2
• 說明:表示該程式要執行的內容是:將暫存器$
s1位址上的數值資料與$s2位址上的數值資料相
加後所得到的和(值),儲存到$s0位址上。其
中,add即是opcode,$s1即是rs,$s2即是rt,
$s0即是rd。
• 基底(base)或差量(displacement)定址法:
運算元儲存在記憶體中,將暫存器和指令中的常
數相加後所得的值(和),即為所要計算的位址
程式碼
rs
rt
Displacement(差量)
• 例如:M[(rs)+displacement]
• 說明:記憶體M要記錄的資料是存在位址rs加上
差量的和的位址。
• 立即定址法:運算元即是指令當中的常數
程式碼
rs
rt
immediate(立即)
• 程式計數器(PC;program counter)相對定址
法:將程式計數器和指令中的常數相加所得的
“和”,即為所要計算的位址
程式碼
rs
rt
程式
計數
位址
記憶體
• 虛擬直接(pseudo-direct)定址法:
將指令欄位中的26個位元和程式計數器
中的高位元結合後所得到的值即所要跳
躍的位址
程式碼
位址
程式
計數
記憶體
程式編譯與執行(最佳化)
• 處理高階程式語言最佳化的關鍵在編譯器,亦即
編譯器必須將原始程式碼正確的轉換成執行速度
較快的機器語言程式碼
• 高階的部分可以採取程序整合—即將程序置入和
迴圈轉換整合考量的處理,是以程序主體來取代
程序呼叫的執行方式
1. 程序置入(procedure inlining):亦即使用函式
的主體來取代函式的呼叫以及利用程式或副程式
的參數來取代呼叫者的引數。
2. 迴圈轉換:減少迴圈中累贅或不必要的額外動作、
減少讀取和儲存記憶體所需的動作和充分有效的
應用硬體以節省執行所需的時間。
• 區域的最佳化(屬於單一基本區塊的處理)
1. 多使用常數,少使用變數來代表常數。
2. 當執行二個相同的計算時,可以採用個別數值
複製的方法來作業,以縮短指令重覆執行所需
的時間。
3. 降低堆疊高度(stack height reduction):將
樹模表示式(expression tree)重新排序來減少
執行計算所需的時間或降低相關資源的耗費。
• 全域的最佳化:涵蓋多個基本區塊的處理,部分
處理方法與區域最佳化相同
• 迴圈部分的處理:
1. 修改、移動程式碼(code motion)或刪除不必要
的程式碼(dead code elimination):例如執行
程序呼叫或副程式時,每次都會重覆執行迴圈當
中相同數值的計算,該程式碼可另安排於適當的
位置,不必重覆累贅的計算工作。
2. 刪除不必要的變數或引數(induction variable
elimination):
(1)使用指標存取的方式來減少迴圈執行時陣列索引
的額外動作。
(2)簡化副程式當中執行迴圈工作時所遭遇到的陣列
位址的計算。
• 刪除一般的次層或次級表示式(common
subexpression elimination):例如程式碼為
address[i]=address[i]+40,其中address[i]位
址的計算出現二次,因此可以使用計算過的結果
• 刪除不必要的儲存(dead store elimination)。
• 使用常數替換或常數傳播(constant
propagation)方法或是採用一個固定的變數(X)
來取代所有被指定為某個多次使用的數值(V)。
• 採取跨越跳躍的執行方式。
• 採用複製替代或複製傳播(copy propagation)的
程式撰寫方式
• 改變指令執行的順序或將管線化作業有效率的排
程,以提高執行效能
• 在條件式跳躍的方面,給予補償或差量的最佳化,
以提供到達目的地最短的差量。
• 以加法計算和移位(shift0的方式來處理乘法的
計算。
• 使用簡易的計算來代替複雜度較高的計算。
程式編譯最佳化的處理
檢查程式語
言的相依性
前端處理
程序整合
處理
高階最佳
化處理
區域性最
佳化處理
全域性最
佳化處理
有效配置
暫存器
產生轉換
的程式碼
組譯器的
最佳化
• 除了最佳化的處理外,在執行程式設計的時候,
我們尚可經由部分方法來改善執行效能:
1. 程式儘量簡潔、清晰和容易閱讀。
2. 程式設計宜有一致性,以方便程式修改和維護。
3. 經常性的計算或事件可採用副程式或程序呼叫的
方法來撰寫。
4. MIPS-32系統只有32個暫存器,應該有效的予以
利用;另外程式計數相對定址法可以獲得條件式
跳躍較嘉的處理結果,而立即定址法對常數運算
特別有效率,這些都是程式設計時可以考慮應用
以提昇效能的方法。
5. 程式設計應保留彈性,調適性或適應性較佳的程
式,總是對編撰程式較有幫助。

similar documents