機器語言, 組合語言, 與編譯器 參考: β 文件; 實驗 #5B; C 語言講議 當我在我的程式碼中發現一堆 麻煩時, 朋友和同事跟我說了 很久很久以前,我仍記得我是如何瞧不起 記憶術… 而且我知道我可以玩BSim遊戲與處 理一些巨集好一陣子, 只要我有操作碼 的名字. 但是6.004課程的每一堂課都令我打顫. 新來壞消息, 我無法再讀一個規格. 我無法記憶當我試著最佳化階乘, 但在我的Beta死去的那天, 有些東西觸 動了我討人厭的傲慢, 於是我唱… 當我在我的程式碼中發現一堆 麻煩時, 朋友和同事跟我說了 一句名言, “用C來寫吧” 參考: β 文件; 實驗 #5B; C 語言講議 6.004 – Fall 2002 10/22/0

β 機器語言: 32-bit 指令 How can we improve the programmability of the Beta? 運算: ADD, SUB, MUL, DIV 比較: CMPEQ, CMPLT, CMPLE 布林: AND, OR, XOR 位移: SHL, SHR, SAR Ra 及 Rb 是操作區域, Rc 是目的地. R31 為 0, 不被寫入指令改變 二的補數的16位元常數, 表示從 –32768 到 32767 的數字; 使用前將它延伸符號至32位元. 運算: ADDC, SUBC, MULC, DIVC 比較: CMPEQC, CMPLTC, CMPLEC 布林: ANDC, ORC, XORC 位移: SHLC, SHRC, SARC 分流: BNE/BT, BEQ/BF (const = 從 PCNEXT轉移的字組(word)數) 跳躍: JMP (const not used) 記憶體存取: LD, ST (const = 從Reg[ra]偏移的位元組(byte)數) How can we improve the programmability of the Beta? 6.004 – Fall 2002 10/22/0

編碼二進位指令 32-bit (4-byte) ADD 指令: OpCode Rc Ra Rb (unused) 對BETA來說, 表示 Reg[4] = Reg[2] + Reg[3] 但, 我們通常喜歡寫成 ADD(R2, R3, R4) (組合語言) 或, 再更好一點, a = b+c; (高階語言) 軟體達成方法: 解譯, 編譯 6.004 – Fall 2002 10/22/0

解譯 Turing的解譯模型: 解譯的“層級” : • 通常我們可以使用多個解譯層級來達到想要的行為, 例如: • 從某個”不易寫程式”的通用電腦, 稱之M1, 開始 • 寫一個小的M1程式來模仿一個比較容易的電腦, 稱之M2 結果: 一個”虛擬”的M2 解譯的“層級” : • 通常我們可以使用多個解譯層級來達到想要的行為, 例如: • X86 (Pentium), 執行 • 系統(Scheme), 執行 • 應用程式, 解譯 • 資料. 6.004 – Fall 2002 10/22/0

編譯 編譯模型: • 給定某個”不易寫程式”的電腦, 稱之 M1... • 找到某個”容易寫程式”的語言 L2 • 建立一個翻譯器(編譯器) 可以將程式從M2語言翻譯成M1語言. 可以在M1, M2, 或其他的電腦上執行. 解譯 & 編譯: 兩種幫助加強可程式性的工具 ... • 兩者都可以改變程式模型 • 兩者都提供與平台(如, 處理器)無關的程式應用 • 兩者都在現代電腦系統中被廣泛使用! 6.004 – Fall 2002 10/22/0

解譯 與 編譯 之比較 這兩個強力的工具之間有一些特性上的差異... 解譯 編譯 計算 x+2 產生一個程式來計算x+2 何時發生 執行時 執行前 哪裡複雜/慢 程式執行 程式建構 何時做決定 執行時間 編譯時間 我們會重覆看到旳主要的設計選項: 在編譯時間或執行時間做? 6.004 – Fall 2002 10/22/0

軟體: 抽象對策 第一步: 編譯工具 接下來的步驟: 解譯工具 隱藏: 位元級的表示式, 16進位位址, 二進位數值 組合器 (UASM): 第一步: 編譯工具 組合器 (UASM): 機器語言的符號表示式 編譯器 (C): 演算法的符號表示式 接下來的步驟: 解譯工具 作業系統 應用程式 (例如: 瀏覽器) 隱藏: 位元級的表示式, 16進位位址, 二進位數值 隱藏: 機器指令, 暫存器, 機器架構 隱藏: 資源 (記憶體, CPU, I/O) 限制及細節 隱藏: 網路; 位址; 區域參數 6.004 – Fall 2002 10/22/0

2. 一個程式 (“組合器” = 簡易的編譯器), 將 UASM來源翻譯成二進位檔. 抽象步驟 1: 一個寫程式的程式 UASM - 6.004 (巨集) 使用的組合語言 將被載入記憶體的位元組串流 UASM 翻譯程式 二進位 機器語言 符號表示之來源文字檔 UASM: 1. 一個符號表示的語言, 用以表示字元串 2. 一個程式 (“組合器” = 簡易的編譯器), 將 UASM來源翻譯成二進位檔. 6.004 – Fall 2002 10/22/0

UASM 原始語言 一個 UASM 原始檔包含了, 符號表示的文字, 將被載入記憶體的連續位元組的數值... 例如: 以下列的格式 十進位(預設); 二進位 (按: 使用“0b”字頭表示); 十六進位 (按: 使用“0x”字頭表示); 數值也可以是運算表示式; 例如, 原始檔 產生4位元組的二進位輸出, 每一個都表示數值23! 6.004 – Fall 2002 10/22/0

符號表示之手勢 我們也可以在原始檔中定義”符號”來使用: 特殊變數 “.” (句點) 表示下一個將被填入的位元組位址: | 組合成 100 “直線” 代表一段註解的開始… 它的後面直到行末都是被忽略的 一個變數位址 另一個變數 暫存器的符號名稱: 特殊變數 “.” (句點) 表示下一個將被填入的位元組位址: | 組合成 100 | 符號 “five” 是 0x104 | 掠過 16 個位元組 6.004 – Fall 2002 10/22/0

標籤(表示位址的符號) 標籤是表示記憶體位址的符號. 它們可以透過以下的特殊語法來設定: x: 是 “x = .” 的縮寫 例子 -- 主記憶體 6.004 – Fall 2002 10/22/0

強而有力的微指令 巨集乃是參數化的縮寫, 或簡寫 會有如下的效果: 37 38 39 40 | 產生四個連續位元組的巨集: .macro consec(n) n n+1 n+2 n+3 | 呼叫上述的巨集: consec(37) 會有如下的效果: 37 38 39 40 以下示範巨集如何將多位元組的資料型式以一個位元組來表示 | 組合little-endian的位元組: .macro WORD(x) x % 256 (x/256) % 256 .macro LONG(x) WORD(x) WORD(x >> 16) =0x100 LONG(0xdeadbeef) 會有如下的效果: 6.004 – Fall 2002 10/22/0

指令之組合語言 組合 Beta 的 op 指令 組合 Beta 的 opc 指令 For Example: “.align 4” 確保指令會在字組(word)的邊緣開始 (例如 address = 0 mod 4) 組合 Beta 的 opc 指令 組合 Beta 的 branch 指令 For Example: ADDC(R15, -32768, R0) --> betaopc(0x31,15,-32768,0) 6.004 – Fall 2002 10/22/0

最後, Beta 指令 (採自 beta.uasm) 方便的巨集. 因此我們不需要指定R31暫存器… 6.004 – Fall 2002 10/22/0

組合語言的例子 以RA=R3, C=1234, RC=R17 展開 ADDC 巨集 以OP=0x30, RA=R3, CC=1234, RC=R17 展開 beta 的 opc 巨集 以X=0xC22304D2展開 LONG 巨集 以X=0xC22304D2 展開第一個 WORD 巨集 計算表示式, 並以X=0xC223 展開第二個 WORD 巨集 計算表示式 6.004 – Fall 2002 10/22/0

找不到指令? 假造一個! (採自 beta.uasm) 方便的巨集可以用來延伸我們的組個語言: 6.004 – Fall 2002 10/22/0

抽象步驟 2: 高階語言 參考: C 講義 (6.004 網頁) 大部分的演算法是以高階的語言來表示. 例如以下的演算法: 我們用了 (並將會繼續在6.004課中使用) C語言. 它是一個”成熟”而且常見的系統. 較新 常用的代替語言有: C++, Java, Python, 以及很多其他的. 為什麼不用組合語言而要用這個呢? • 可讀性 • 簡潔 • 清楚, 不會模稜兩可 • 可攜帶 (演算法經常存活地比硬體平台來得 久) • 可靠 (資料型態檢查, 等等) 參考: C 講義 (6.004 網頁) 6.004 – Fall 2002 10/22/0

編譯器 所做的事 並不 全是 那麼地 複雜. 編譯器是如何運作的呢? 當化的編譯器遠比UASM的巨集延伸還做的更多. 它們 • 執行精細的原始碼分析 • 使用特定的演算法來產生給目 的電腦用的有效率的程式碼 • 對原始碼及目的程式碼都採行 “最佳化” 程序, 以得到較好的執行時間效能. 編譯一個未最佳化的程式碼是很直接的... 以下是一些簡短的介紹. 編譯器 所做的事 並不 全是 那麼地 複雜. (至少, 原則上) 6.004 – Fall 2002 10/22/0

編譯表示式 C 語言碼: Beta 組合語言碼: 變數 被指定為記憶體位置, 並透過 LD 或 ST 來存取 • 操作 翻譯成 ALU 指令 • 大常數 翻譯成 初始化的變數 6.004 – Fall 2002 10/22/0

資料結構: 陣列 記憶體: C 原始碼 可能翻譯成: 位址: 常數為基底的位址 + 由索引計算得到的變數偏移量 6.004 – Fall 2002 10/22/0

資料結構: 結構 記憶體: 可能翻譯成: 位址: 變數為基底的位址 + 常數的元件偏移量 x 元件的偏移量 y 元件的偏移量 6.004 – Fall 2002 10/22/0

條件式 Beta assembly: C code: Beta 組合語言: C code: Beta 組合語言: 編譯成: 編譯條件碼區塊時, 有一些小小的技巧. 舉例來說, 以下的表示式: C code: Beta 組合語言: 並沒有 >32 這樣的指令! 編譯成: 6.004 – Fall 2002 10/22/0

把這個測試式移到迴圈的後面並且第一次在這裡跳到那個測試式… 這樣可以省一個分流指令 Beta 組合語言: 替代的 Beta 組合語言: C 程式碼: 編譯器要花上許多的時間把迴圈裡面和週遭最佳化. - 把所有可能的計算移到迴圈外面 - 展開迴圈來減少分流指令產生的效能消耗 - 化簡表式示對“迴圈變數”的依賴度 6.004 – Fall 2002 10/22/0

最佳化 我們最愛的階乘程式 loop: done: 聰明之處: 沒有… 直接了當地編譯 (迴圈中有11個指令...) 6.004 – Fall 2002 10/22/0

最佳化 聰明之處: 把LD與ST指令移到 迴圈外面! (在迴圈中還有 5 個指 令...) 6.004 – Fall 2002 10/22/0

完成最佳化… 不幸地, 聰明之處: 避免了條件判斷式的消耗! (現在迴圈中只剩 3個指令...) 6.004 – Fall 2002 10/22/0

下回: 程序 及 堆疊 6.004 – Fall 2002 10/22/0