quasiceo / 深入浅出教你... / 【深入淺出教你寫編譯器(Compiler)】七...

分享

   

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

2017-10-23  quasiceo

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

May 17, 2012 西杰 編程, 3

Fb-Button

大家好,又見到西杰了。我們之前已經做好了一個簡單的編譯器,可以把 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;
	}
}

最後就得出這個樣子了。

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 生成的代碼執行三十次要用多少時間:

接著我們就要改寫 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 + ";");
}

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

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

Fb-Button

, , , , , , , , , , , , 

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

  1. hi, 西杰,非常感谢你的文章,写的真好。Great job!
    我目前正好做项目需要使用javascript做一个语法解释器,想法是直接将用户写的简单的源代码(而不是编译后的代码)进行解释运算,得出结果。如:
    if(a) return b + c;
    请问这样的做法性能如何?有什么弊端?

    • 要談及性能的話,javascript 寫的解釋器性能一定不會太好,因為 javascript 本來就已經是解釋型語言嘛(雖然 Chrome 是做得挺不錯,但其他瀏覽器還是差太遠)
      比較好的做法是先把代碼編譯為 javascript 代碼,那就可以用瀏覽器的優化機制(例如 Chrome 可以再把你編譯出來的 javascript 再編譯一下)
      如果目標是要做 DSL(Domain specific language)的話,還是有一定的發展空間的(可以參考一下 Processing.js)

Leave a Reply

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>