{{ $root.errMsg }}

【深入淺出教你寫編譯器(Compiler)】七、優化器(Optimizer)﹣還可以更好

(已刪除)

(已關閉)

(已標記為濫發)

(已保護)


大家好,又見到西杰了。我們之前已經做好了一個簡單的編譯器,可以把 Wescript 編譯成 Wemachine 讀得到的 Wemachine code,理論上編譯器教程也可以算完成了,但世事並不是這麼簡單的,我們雖然已經編譯到一個可以運行的程式,但在這個時間就是金錢的世界中,我們必須爭取每一分每一秒,把程式縮到最精簡,這就是我們這一章要做的工作了。

 

要做優化,我們可以從兩個層面著手,即代碼層面及指令碼層面。例如,我們可以移除一些沒有用過的變數,以減少記憶體的使用,這就屬於代碼層面的優化。又或者我們可以研究程式使用過的 register 並把沒有用的都移除或減少使用,以減少程式的代碼量及加快運行速度。

在實際應用環境中,有數之不盡那麼多種不同的優化技巧,所以在這章教學中,我們會挑選兩種來討論,第一種是移除沒有用過的變數,第二種是 Loop inversion。現在就由第一種開始吧!

移除沒用的變數
首先我們要改寫一下我們的 Analyser,我們要記下哪些變數曾經被使用,那麼我們才可以在生成代碼時避免生成那些未曾使用的變數。

function Analyser(){
    this.vars = {};
    //added for optimization use
    this.unusedVars = {};
}

另外,在 evaluateVariableNode 時,我們需要記下這個變數未被使用,然後在以後的代碼中當這個變數被使用之時我們就要把它從未被使用的 hash map 中剔除掉。

Analyser.prototype.evaluateVariableNode = function (node){
    if (this.vars[node.varName]){
        //this variable has been declared before
        //since we can find it in our variable table
        Errors.push({
            type: Errors.SEMANTIC_ERROR,
            msg: "The variable \"" + node.varName + "\" has been declared already",
            line: node.line
        });
    }else{
        this.vars[node.varName] = node;
        //if we do not use "else", this variable declaration will replace the previous one
        //This may result in wrong data type checking later on
 
        //it is not used at the moment of declaration
        this.unusedVars[node.varName] = true;
    }
 
    ...
}

在使用變數時把它剔出未被使用的名單:

Analyser.prototype.evaluateIdentifierNode = function (node){
    if (! this.vars[node.identifier]){
        Errors.push({
            type: Errors.SEMANTIC_ERROR,
            msg: "Variable \"" + node.identifier + "\" must be declared before using",
            line: node.line
        });
    }else{
        this.unusedVars[node.identifier] = false;
        node.valueType = this.vars[node.identifier].valueType;
    }
}

最後就得出這個樣子了。

var a:int = 3;
		var b:bool = false;
		
		print a;
		
lwi $0,1;
lwi $1,0;
lwi $3,3;
move $2,$3;
move $4,$2;
lwi $6,0;
move $5,$6;
move $7,$4;
print $7;
3

Loop inversion
什麼是 Loop inversion 呢?就是把一個 while-loop 轉換成為一個 if 加一個 do-while-loop,為什麼要這樣做呢?branch 和 jump 一般來說都是消費很大(即用很多時間)的指令,而這個做法就可以幫助我們節省一個 branch,那就可以幫助我們加快程式運行速度了。

先看看這個 while-loop:

var i:int = 3;
 
while (i != 0){
    i--;
}

我們要把它改寫成類似這樣的代碼:

var i:int = 3;
 
if (i != 0){
    do{
        i--;
    }while (i != 0);
}

這個真的能夠幫助我們節省使用 branch 嗎?待會看看你就會明白了,現在先看一下我們如何改寫現在 while loop 生成代碼的寫法。為了更好地模擬現實的機器,我們第一步要做的是在跳轉的時候增加一些睡眠時間 ,因為在現實世界中的機器處理跳轉的時間都比較長,這亦是為什麼這個優化的技巧有用武之地。

在 easyJump 之中加入以下的代碼:

//sleep for 10 ms
var t = + new Date;
while ((+new Date) - t < 10){}

讓程式在跳轉時睡 10 個微秒。

先看看現在 while-loop 生成的代碼執行三十次要用多少時間:

var i:int = 3;

		while (i != 0){
			i--;
		}
lwi $0,1;
lwi $1,0;
lwi $3,3;
move $2,$3;
move $4,$2;
vlabel lbl0;
move $5,$4;
lwi $7,0;
move $6,$7;
move $10,$5;
move $11,$6;
lwi $8,0;
label lbl2;
label lbl4;
add $10,$10,$8;
lwi $9,0;
beq $8,$0,lbl2;
label lbl3;
lwi $9,1;
beq $8,$0,lbl2;
label lbl2;
lwi $8,1;
beq $10,$11,lbl4;
move $5,$9;
beq $5,$1,_lbl1;
move $12,$4;
subi $4,$4,1;
j _lbl0;
vlabel lbl1;

接著我們就要改寫 while-loop 生成的代碼了。我們一開始要先檢查一下條件是否成立,是的話才執行 do-while loop 的內部程式,在執行完內部程式碼之後就要檢查一下條件式是否成立,是的話就跳到內部程式碼的頂端再執行一次,直至條件式不成立為止。

Compiler.prototype.evaluateWhileNode = function (node){
    var whileLbl = this.getNextLabel();
    var endLbl = this.getNextLabel();
 
    var condReg = this.evaluateExpressionNode(node.conditionExpression);
    this.writeln("beq " + condReg + "," + this.falseRegister + "," + "_" + endLbl + ";");
 
    this.writeln("vlabel " + whileLbl + ";");
    this.evaluateExpressionBlockNode(node.expressions);
 
    condReg = this.evaluateExpressionNode(node.conditionExpression);
    this.writeln("beq " + condReg + "," + this.trueRegister + "," + "_" + whileLbl + ";");
    this.writeln("vlabel " + endLbl + ";");
}
		var i:int = 3;

		while (i != 0){
			i--;
		}
		
lwi $0,1;
lwi $1,0;
lwi $3,3;
move $2,$3;
move $4,$2;
move $5,$4;
lwi $7,0;
move $6,$7;
move $10,$5;
move $11,$6;
lwi $8,0;
label lbl2;
label lbl4;
add $10,$10,$8;
lwi $9,0;
beq $8,$0,lbl2;
label lbl3;
lwi $9,1;
beq $8,$0,lbl2;
label lbl2;
lwi $8,1;
beq $10,$11,lbl4;
move $5,$9;
beq $5,$1,_lbl1;
vlabel lbl0;
move $12,$4;
subi $4,$4,1;
move $13,$4;
lwi $15,0;
move $14,$15;
move $18,$13;
move $19,$14;
lwi $16,0;
label lbl5;
label lbl7;
add $18,$18,$16;
lwi $17,0;
beq $16,$0,lbl5;
label lbl6;
lwi $17,1;
beq $16,$0,lbl5;
label lbl5;
lwi $16,1;
beq $18,$19,lbl7;
move $13,$17;
beq $13,$0,_lbl0;
vlabel lbl1;

這一章說的優化技巧其實只是很皮毛而已,如果你還想更深入地探討其他技巧,可以到維基看看,那裏列出了很多種不同的優化技巧,相信要研究都要花一段很長的時間了。

編譯器的教學也來到尾聲了,大家在當中學到了多少東西呢?現在就到你們出手了,把你們一直想做的編譯器做出來吧!

compiler  


{{ ctrl.votes | shortNumber: 0 }}
寫於 {{ '2017-08-14T10:03:56.654Z' | calendarTime }}

{{ $root.errMsg }}