基于代碼優(yōu)化的“編譯原理”課程實踐教學(xué)研究

王峰 閻娟 張浩軍

關(guān)鍵詞：編譯原理；代碼優(yōu)化；實踐教學(xué)

1引言

“編譯原理”是一門重要的計算機(jī)專業(yè)課程，通過該課程的學(xué)習(xí)和實踐，既可加深學(xué)生對程序設(shè)計語言的設(shè)計與實現(xiàn)等知識的綜合理解，又可多角度地提高實踐動手能力及綜合應(yīng)用能力[1-3]。特別是，“編譯原理”課程與計算思維具有緊密的聯(lián)系，為培養(yǎng)學(xué)生的計算思維能力提供了一個良好的平臺[4]。但“編譯原理”具有內(nèi)容多、概念多、理論性強、高度抽象等特點，被普遍認(rèn)為是一門既難教又難學(xué)的課程。

該課程中的代碼優(yōu)化主要是針對編譯器，但大部分由編譯器執(zhí)行的優(yōu)化僅涉及控制流程的簡化和變量的訪問方式等，并且由于大部分學(xué)生畢業(yè)后并不會從事編譯器的設(shè)計工作，因此很多學(xué)生會覺得相關(guān)理論知識的作用不大。同時，隨著計算機(jī)硬件技術(shù)的飛速發(fā)展，計算機(jī)的計算能力日益增強，因此學(xué)生在學(xué)習(xí)程序設(shè)計語言的時候?qū)⒏嗟木Ψ旁诹顺绦蜻壿嫷膶崿F(xiàn)上，而忽略了代碼優(yōu)化，從而導(dǎo)致學(xué)生對優(yōu)化相關(guān)知識的重要性認(rèn)識不足。實際上，代碼優(yōu)化在軟件開發(fā)過程中，特別是在嵌入式等對實時性要求較高的系統(tǒng)開發(fā)中的作用是非常大的。本文針對工程型和應(yīng)用型人才培養(yǎng)的目標(biāo)，以圖像處理中將RGB格式的彩色圖像轉(zhuǎn)換為灰度圖像為例，探討編譯原理中代碼優(yōu)化相關(guān)技術(shù)在實際工程中的應(yīng)用，以加深學(xué)生對編譯理論知識的理解，建立理論和實際的聯(lián)系，強化實踐動手能力，從而提高學(xué)生的編程能力和綜合素質(zhì)。

2代碼優(yōu)化概述

代碼優(yōu)化是編譯程序中的一個重要環(huán)節(jié)，其實質(zhì)是對代碼進(jìn)行等價變換，目的是提高由編譯程序生成的目標(biāo)程序的質(zhì)量，即加快目標(biāo)程序的運行速度或減少目標(biāo)程序所占的存儲空間，或兩者兼具[5-7]。

代碼優(yōu)化是為了編寫出更高效的代碼，故在進(jìn)行代碼優(yōu)化時須遵循三個原則：（1）等價原則，即優(yōu)化不能改變程序的運行結(jié)果；（2）有效原則，即優(yōu)化后的代碼應(yīng)比未優(yōu)化代碼具有更高的時空效率；（3）盈利或合算原則，即優(yōu)化帶來的利益應(yīng)大于優(yōu)化工作所付出的代價。

按照與機(jī)器的關(guān)系，代碼優(yōu)化可分為與機(jī)器無關(guān)的優(yōu)化和與機(jī)器相關(guān)的優(yōu)化，二者在編譯程序中所處的階段是不一樣的，前者是在源程序或中間代碼上進(jìn)行優(yōu)化：后者是在目標(biāo)代碼上進(jìn)行優(yōu)化。在與機(jī)器無關(guān)的優(yōu)化中，根據(jù)它所涉及的程序范圍可分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個不同的級別。局部優(yōu)化是在基本塊內(nèi)的優(yōu)化，循環(huán)優(yōu)化是對循環(huán)中的代碼進(jìn)行優(yōu)化，而全局優(yōu)化則是在整個程序范圍內(nèi)的優(yōu)化。優(yōu)化方法包括數(shù)據(jù)流分析、控制流分析和程序變換等。代碼優(yōu)化的不同分類及相關(guān)優(yōu)化技術(shù)如表1所列。

3代碼優(yōu)化實踐教學(xué)

“編譯原理”課程中的代碼優(yōu)化都是針對編譯程序的中間代碼和目標(biāo)代碼進(jìn)行的，而學(xué)生平常接觸更多的是源代碼，并且將來也更多的是從事源代碼的開發(fā)工作。因此，學(xué)生對相關(guān)理論知識在實際工程中的應(yīng)用缺乏了解，從而對相關(guān)優(yōu)化知識的掌握不夠深入，也較難將相關(guān)優(yōu)化知識應(yīng)用于實際編程中。實際上，在嵌入式系統(tǒng)等實時性要求較高的應(yīng)用中，代碼優(yōu)化是一個非常重要的環(huán)節(jié)。本節(jié)以圖像處理中最基本的彩色圖像轉(zhuǎn)換為灰度圖像為例，討論相關(guān)編譯優(yōu)化知識在實際工程中的應(yīng)用，以增進(jìn)學(xué)生對編譯優(yōu)化知識的了解，提高學(xué)生的編程能力。

3.1問題描述

在圖像模式識別工程中，為了便于處理和識別，經(jīng)常需要將RGB格式的彩色圖像轉(zhuǎn)換為灰度圖像，圖像轉(zhuǎn)換公式[8]為：

其中，R，G，B分別代表每個像素在RGB顏色空間中的紅、綠和藍(lán)三個顏色分量，Y為變換后所得灰度圖像中像素的灰度級，其取值均為[0，255]的整數(shù)。本節(jié)中圖像大小為720*576*24bit。

3.2優(yōu)化實踐

為實現(xiàn)上述功能，首先，定義如下數(shù)據(jù)結(jié)構(gòu)：

步驟1：變換循環(huán)控制條件

上述代碼是按照“先列后行”的順序來對二維數(shù)組進(jìn)行遍歷的，而在C語言中，一個二維數(shù)組在計算機(jī)中存儲時，是按照“先行后列”的順序依次存儲的。因此，“先列后行”遍歷發(fā)生的頁面交換次數(shù)要比“先行后列”多，且cache命中率相對較低。所以，通過調(diào)整語句順序，變換循環(huán)控制條件，可以將上述函數(shù)修改為：

步驟2：數(shù)據(jù)結(jié)構(gòu)優(yōu)化

因圖像為二維數(shù)據(jù)，故直接采用二維數(shù)組來存儲圖像數(shù)據(jù)，代碼較直觀、可讀性強。但編譯器處理二維數(shù)組的效率低于一維數(shù)組，因此可改用一維數(shù)組來存儲圖像數(shù)據(jù)，即將變量定義為：

經(jīng)上述優(yōu)化后，函數(shù)的運行時間下降為9.80ms。

步驟3：合并已知量，刪除無用代碼

上述代碼循環(huán)內(nèi)存在無用賦值的情況，刪除多余變量和對應(yīng)的賦值語句，合并已知量，即得：優(yōu)化后函數(shù)的運行時間變?yōu)?.06ms。

步驟4：代數(shù)變換

上述代碼中最主要的運算在于對每個像素點利用公式（1）進(jìn)行的浮點數(shù)運算。顯然，計算機(jī)對整數(shù)的運算速度要快于浮點運算，因此應(yīng)用代數(shù)變換可將此操作改為整數(shù)運算，經(jīng)此優(yōu)化后，函數(shù)的運行日寸間進(jìn)一步縮短為3.37ms。

步驟5：強度削弱（移位實現(xiàn)除法）

由于計算機(jī)的移位操作速度快于除法，因此可以利用移位操作來實現(xiàn)上述除法運算，從而降低運算強度，即將上述代碼改為：經(jīng)此優(yōu)化后，函數(shù)的運行時間進(jìn)一步減少為2.82ms。

步驟6：強度削弱（查表）

在上述代碼中，每個像素的R，G和B值都需要進(jìn)行乘法運算，由于這三個變量的取值范圍均為[0，255]，因此可以通過在外定義查找表的方法來減少計算量，即將此范圍內(nèi)的值分別乘以306、601和1 17并進(jìn)行移位操作，然后將計算得到的值用三個數(shù)組分別加以存儲．即：

在此基礎(chǔ)上，循環(huán)內(nèi)的每個像素不須計算便可直接通過查找表的方法快速實現(xiàn)灰度轉(zhuǎn)換

顯然，這也是一種以犧牲內(nèi)存為代價節(jié)省計算時間的方法，經(jīng)過此優(yōu)化后，函數(shù)運行時間進(jìn)一步降低為1.93ms。

步驟7：循環(huán)展開

在上述代碼的循環(huán)體內(nèi)，因各像素的轉(zhuǎn)換是獨立進(jìn)行的，不存在數(shù)據(jù)依賴，故可以進(jìn)行循環(huán)展開，減少循環(huán)迭代次數(shù)，有利于CPU的流水線工作，從而提高運行速度。比如，將函數(shù)改為：

上文各步驟優(yōu)化后的函數(shù)運行時間變化如圖1所示。從圖1可以看出，經(jīng)過上述各步驟的優(yōu)化后，函數(shù)運行時間從優(yōu)化前的21.96ms下降為1.63ms，優(yōu)化效果非常明顯。

上述優(yōu)化實例中包含局部優(yōu)化、循環(huán)優(yōu)化、與機(jī)器無關(guān)的優(yōu)化和與機(jī)器相關(guān)的優(yōu)化等知識。同時，為進(jìn)一步增強學(xué)生的工程應(yīng)用能力，在教學(xué)中還補充了對相關(guān)程序分析工具的介紹。在大型實際開發(fā)項目中，可以利用GProf和dotTrace等工具來發(fā)現(xiàn)程序中的瓶頸，并有針對性地進(jìn)行代碼優(yōu)化，從而提高系統(tǒng)的運行效率。

4結(jié)束語

針對“編譯原理”課程教學(xué)中的代碼優(yōu)化，本文在簡要介紹其原理和相關(guān)優(yōu)化技術(shù)的基礎(chǔ)上，重點從實踐教學(xué)的角度，以圖像模式識別工程中的圖像格式轉(zhuǎn)換為例，探討了相關(guān)編譯優(yōu)化技術(shù)在實際工程中的應(yīng)用。通過面向?qū)嶋H應(yīng)用的優(yōu)化實踐教學(xué)，有助于提高學(xué)生對課程的重視程度，調(diào)動學(xué)生的積極性和主動性，培養(yǎng)學(xué)生的實踐創(chuàng)新能力，幫助學(xué)生在深入了解編譯器工作原理和優(yōu)化技術(shù)的基礎(chǔ)上，提高代碼編寫的質(zhì)量。同時，也能將編譯原理和程序設(shè)計語言、操作系統(tǒng)等課程的相關(guān)知識聯(lián)系起來，從而可以從多角度提高學(xué)生的綜合應(yīng)用能力，切實有效地提高學(xué)生的專業(yè)素質(zhì)，并在實踐中取得較好的教學(xué)效果。