基于代碼優化的“編譯原理”課程實踐教學研究

王峰 閻娟 張浩軍

關鍵詞：編譯原理；代碼優化；實踐教學

1引言

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

該課程中的代碼優化主要是針對編譯器，但大部分由編譯器執行的優化僅涉及控制流程的簡化和變量的訪問方式等，并且由于大部分學生畢業后并不會從事編譯器的設計工作，因此很多學生會覺得相關理論知識的作用不大。同時，隨著計算機硬件技術的飛速發展，計算機的計算能力日益增強，因此學生在學習程序設計語言的時候將更多的精力放在了程序邏輯的實現上，而忽略了代碼優化，從而導致學生對優化相關知識的重要性認識不足。實際上，代碼優化在軟件開發過程中，特別是在嵌入式等對實時性要求較高的系統開發中的作用是非常大的。本文針對工程型和應用型人才培養的目標，以圖像處理中將RGB格式的彩色圖像轉換為灰度圖像為例，探討編譯原理中代碼優化相關技術在實際工程中的應用，以加深學生對編譯理論知識的理解，建立理論和實際的聯系，強化實踐動手能力，從而提高學生的編程能力和綜合素質。

2代碼優化概述

代碼優化是編譯程序中的一個重要環節，其實質是對代碼進行等價變換，目的是提高由編譯程序生成的目標程序的質量，即加快目標程序的運行速度或減少目標程序所占的存儲空間，或兩者兼具[5-7]。

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

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

3代碼優化實踐教學

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

3.1問題描述

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

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

3.2優化實踐

為實現上述功能，首先，定義如下數據結構：

步驟1：變換循環控制條件

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

步驟2：數據結構優化

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

經上述優化后，函數的運行時間下降為9.80ms。

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

上述代碼循環內存在無用賦值的情況，刪除多余變量和對應的賦值語句，合并已知量，即得：優化后函數的運行時間變為9.06ms。

步驟4：代數變換

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

步驟5：強度削弱（移位實現除法）

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

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

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

在此基礎上，循環內的每個像素不須計算便可直接通過查找表的方法快速實現灰度轉換

顯然，這也是一種以犧牲內存為代價節省計算時間的方法，經過此優化后，函數運行時間進一步降低為1.93ms。

步驟7：循環展開

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

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

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

4結束語

針對“編譯原理”課程教學中的代碼優化，本文在簡要介紹其原理和相關優化技術的基礎上，重點從實踐教學的角度，以圖像模式識別工程中的圖像格式轉換為例，探討了相關編譯優化技術在實際工程中的應用。通過面向實際應用的優化實踐教學，有助于提高學生對課程的重視程度，調動學生的積極性和主動性，培養學生的實踐創新能力，幫助學生在深入了解編譯器工作原理和優化技術的基礎上，提高代碼編寫的質量。同時，也能將編譯原理和程序設計語言、操作系統等課程的相關知識聯系起來，從而可以從多角度提高學生的綜合應用能力，切實有效地提高學生的專業素質，并在實踐中取得較好的教學效果。