Skip to content

至此,貧道已經展示了零.一版音界咒的分詞、剖析、語義檢查,若程式能通過這些步驟,代表它完全合法。接下來,就可以生成目標碼了,在本指引中,貧道會示範如何生成精五真言(RISC-V)。

變數儲存

熟悉 C 語言的道友想必都曉得,全域變數與區域變數在程序執行時是放在不同位置。全域變數會放在數據段(data section),在整個程序執行的過程都佔用一塊記憶體空間;而區域變數則是則是存放在函式調用時臨時開的棧禎。

零.一版音界咒的變數可以視做全域的,畢竟該版本尚無函式調用的概念。

精五真言的數據段

很容易就能用精五真言設定全域變數,以下是範例數據段.S

assembly
.section .data
甲:
    .word 50         # .word 表示開闢 32 位元的空間,該空間的值為 50

.section .text
.global _start

_start:
    lw t0, 甲         # t0 = *(u32*)甲

    li a7, 93         # RISCV Linux 中 exit 系統呼叫編號是 93
    mv a0, t0         # a0 = t0
    ecall             # 執行系統呼叫 exit(t0)

同樣交叉編譯並以 qemu 模擬

riscv64-unknown-elf-gcc -nostdlib 數據段.S  # 編譯後應得 a.out 檔案
qemu-riscv64 a.out                         # qemu-riscv64 並非單單模擬裸機,還實作了部分系統呼叫
echo $?                                    # 可以看到上一個程序的結束碼是 50

數據段.S 首先在數據段 .section .data.word 開闢 32 位元的空間,前方的是一個標籤,在後續程式段的真言中會被代換為該空間的位址。

再來看 _start 的第一行 lw t0, 甲,lw 是 load word 的縮寫,效果是從位址甲開始讀取 32 位元放進 t0 暫存器。 lw 執行完後, t0 就是 50 了,最後 mv a0, t0 把程序結束碼設為 50。

lw 相對應,sw(store word)能夠將暫存器的值寫入某個記憶體位址,但 sw 要多加一個參數,sw t0, 甲, rtrt 可以是任意通用暫存器。

選讀:為什麼 sw 要三個參數

接三個參數的 sw rd, 標籤, rt 是偽指令,組譯後會變為兩條指令:

auipc rt, 標籤[31:12]
sw rd, 標籤[31:12](rt)

其大概意思是用先把 rt 的值弄成成標籤的位址,再把 rt 所在位址的 32 位元存進 rd 。

那為何 lw rd, 標籤 就不需要額外暫存器來幫忙存位址呢?它也是會編譯成兩條真言的偽指令吧! 因為rd在載入時能重複用。

auipc rd, 標籤[31:12]    # 反正等等 rd 的值等等也要被改了,順便當位址用
lw rd, 標籤[31:12](rd)   # rd 既是記憶體位址,又是要被寫入的暫存器

sw 的 rd 要是重複用,還沒把它的值寫到記憶體,自己就先被汙染了:

auipc rd, 標籤[31:12]    # rd 的值已被汙染
sw rd, 標籤[31:12](rd)   # 把被汙染的值寫到記憶體

所以 sw rd, 標籤, rt 的第三個參數 rt 省不了。

運算

在語法樹中,算式是一棵二元樹,要從樹形轉換為循序、線性的真言並不是一目瞭然的事情。若先將算術二元樹轉換為後序表達式,計算的順序會比較明瞭一些。道友們在煉氣(學習編程基礎、資料結構)時,想必對後序表達式不陌生,後序拜訪二元樹就能得到。

虛擬碼
後序拜訪(樹) {
    後序拜訪(樹.左子樹)
    後序拜訪(樹.右子樹)
    打印(樹.值)
}

舉個例子:

       +
      / \
     *   5
    / \
   3   -
      / \
     4   2

後序拜訪後,會打印出:

3 4 2 - * 5 +

這時計算的順序就很清楚了,由左而右是 - * + ,得到順序後,把每個數字放進一個暫存器,可以生成真言

li t0, 3
li t1, 4
li t2, 2
sub t1, t1, t2
mul t0, t1, t1
li t1, 5
add t0, t1, t1

然而算術樹可能會很高很畸形,導致暫存器的數量不夠用,這時就得把數字放進記憶體暫時儲存了。

道友們煉氣時應該都有印象,藉助資料結構「棧(堆疊)」可以很輕鬆的計算後序表達式,若需要複習,可以看看下方的逐步操作回憶一下:

[3]               # 遇數字 3,壓入棧
[3, 4]            # 遇數字 4,壓入棧
[3, 4, 2]         # 遇數字 2,壓入棧
[3, 2]            # 遇運算 -,計算 4 - 2 = 2,將結果壓入棧
[6]               # 遇運算 *,計算 3 * 2 = 6,將結果壓入棧
[6, 5]            # 遇數字 5,壓入棧
[11]              # 遇運算 +,計算 6 + 5 = 11,將結果壓入棧

把所有運算都存到棧裡是很慢的,畢竟一次記憶體存取可能比是存取暫存器要慢上幾十乃至上百倍,即使快取命中也要好幾個 cycle 才拿得回來,但堆疊機實現起來容易。就先暫且把暫存器分配問題丟到一邊,來看看在精五真言中如何模擬堆疊機。

精五真言棧操作

精五(RISC-V)架構的棧一般來說是從高位址往低位址成長的。棧頂位址由暫存器 sp 記錄,addi sp, sp, -8 可擴大棧,相反地,addi sp, sp, 8會縮小棧。

以下精五真言將數字 3 壓入棧

assembly
addi sp, sp, -8   # 擴大棧 64 位元(8 位元組 = 64 位元)
li t0, 3          # t0 = 3
sd t0, 0(sp)      # sd 將 64 位元 t0 存到棧頂

最後來看上述算術樹轉成堆疊機操作的完整精五真言:

assembly
# 3 入棧
	addi sp, sp, -8
	li t0, 3
	sd t0, 0(sp)
# 4 入棧
	addi sp, sp, -8
	li t0, 4
	sd t0, 0(sp)
# 2 入棧
	addi sp, sp, -8
	li t0, 2
	sd t0, 0(sp)
# 減
	ld t1, 0(sp)     # t1 = 棧頂
	addi sp, sp, 8   # 棧頂縮小 64 位元
	ld t0, 0(sp)     # t0 = 棧頂
	sub t0, t0, t1   # t0 = t0 - t1
	sd t0, 0(sp)     # sd 將 64 位元 t0 存到棧頂
# 乘
	ld t1, 0(sp)
	addi sp, sp, 8
	ld t0, 0(sp)
	mul t0, t0, t1
	sd t0, 0(sp)
# 5 入棧
	addi sp, sp, -8
	li t0, 5
	sd t0, 0(sp)
# 加
	ld t1, 0(sp)
	addi sp, sp, 8
	ld t0, 0(sp)
	add t0, t0, t1
	sd t0, 0(sp)

實作

以下展示一份精五真言生成的實作。

這是生成器的定義,其接收一個語法樹,把精五真言輸入到真言檔。變數集可以在符號檢查時取得。

rust
pub struct O真言生成器 {
    真言檔: File,
    語法樹: O語法樹,
    變數集: HashSet<String>,
}

impl O真言生成器 {

    pub fn 生成(&mut self) -> io::Result<()> {
        self.生成數據段()?;
        self.生成代碼段()
    }

	...
}

真言生成分為「數據段」跟「代碼段」分開實作。

數據段(變數儲存)

數據段的生成頗為簡單,為每個變數在 .section .data 製造一相應的標籤,以 .quad 指定 64 位元空間。

rust
fn 生成數據段(&mut self) -> io::Result<()> {
	writeln!(self.真言檔, ".section .data")?;
	self.生成變數標籤()
}
fn 生成變數標籤(&mut self) -> io::Result<()> {
	for 變數 in &self.變數集 {
		writeln!(self.真言檔, "{}:", 變數)?;
		// 初始值為 0
		// 初始值是多少不重要,通過符號檢查,代表每個變數使用前都會先賦值
		writeln!(self.真言檔, "\t.quad 0")?;
	}
	self.換行()
}

(代碼段)運算

代碼段就相對複雜許多,原理已在前文解釋,道友們可閱讀註解來幫助理解。

這裡並沒有真的先轉換到後序表示法再生成代碼,而是對算術樹做後序遍歷的同時就把代碼給生成了。

rust
fn 生成代碼段(&mut self) -> io::Result<()> {
	writeln!(self.真言檔, ".section .text")?;
	// 編譯器會將某些 .data 段的變數存放到 .sdata 段
	// .sdata 段的數據可以直接用 gp 暫存器的相對位址得到
	// 會快一個指令,但 gp 初始化需要導引
	// 因此此處採用 main 而非 _start
	// gcc 編譯時不加 -nostdlib 參數,讓 gcc 生成 _start 協助引導
	writeln!(self.真言檔, ".global main")?;
	self.換行()?;
	writeln!(self.真言檔, "main:")?;
	let 語法樹 = &self.語法樹;

	forin &語法樹.句 {
		match 句 {
			O句::變數宣告(變數宣告) => Self::賦值(&mut self.真言檔, &變數宣告)?,
			O句::算式(算式) => Self::計算(&mut self.真言檔, &算式)?,
		}
	}
	writeln!(self.真言檔, "# 結束")?;
	writeln!(self.真言檔, "\tli a7, 93")?; // RISCV Linux 中 exit 系統呼叫編號是 93
	writeln!(self.真言檔, "\tmv a0, t0")?; // a0 = t0
	writeln!(self.真言檔, "\tecall")?; // 執行系統呼叫 exit(t0)
	Ok(())
}

fn 賦值(真言檔: &mut File, 變數宣告: &O變數宣告) -> io::Result<()> {
	Self::計算(真言檔, &變數宣告.算式)?;
	writeln!(真言檔, "# 賦值給 {}", &變數宣告.變數名)?;
	writeln!(真言檔, "\tsd t0, {}, s1", &變數宣告.變數名) // 存入變數所在記憶體
}

// 計算結束後,結果置於 t0
fn 計算(真言檔: &mut File, 算式: &O算式) -> io::Result<()> {
	match 算式 {
		O算式::二元運算(二元運算) => {
			Self::計算(真言檔, 二元運算..as_ref())?;
			Self::計算(真言檔, 二元運算..as_ref())?;
			Self::二元運算(真言檔, &二元運算.運算子)
		}
		O算式::數字(數) => Self::數字入棧(真言檔, 數),
		O算式::變數(變數) => Self::變數入棧(真言檔, 變數),
	}
}
// 結束時,t0 = 數
fn 數字入棧(真言檔: &mut File, 數: &i64) -> io::Result<()> {
	writeln!(真言檔, "# {} 入棧", 數)?;

	writeln!(真言檔, "\taddi sp, sp, -8")?; // 增加棧 64 位元的空間
	writeln!(真言檔, "\tli t0, {}", 數)?; // 將 t0 設為「數」
	writeln!(真言檔, "\tsd t0, 0(sp)") // t0 放入棧頂
}
// 結束時,t0 = 變數
fn 變數入棧(真言檔: &mut File, 變數: &String) -> io::Result<()> {
	writeln!(真言檔, "# 變數「{}」入棧", 變數)?;

	writeln!(真言檔, "\taddi sp, sp, -8")?; // 增加棧 64 位元的空間
	writeln!(真言檔, "\tld t0, {}", 變數)?; // t0 = *(i64*)變數
	writeln!(真言檔, "\tsd t0, 0(sp)") // t0 放入棧頂
}
// 結束時,t0 = 二元運算結果
fn 二元運算(真言檔: &mut File, 運算子: &O運算子) -> io::Result<()> {
	writeln!(真言檔, "# {:?}", 運算子)?;

	writeln!(真言檔, "\tld t1, 0(sp)")?; // t1 = 棧頂
	writeln!(真言檔, "\taddi sp, sp, 8")?; // 縮小棧
	writeln!(真言檔, "\tld t0, 0(sp)")?; // t0 = 棧頂

	match 運算子 {
		O運算子::=> {
			writeln!(真言檔, "\tadd t0, t0, t1")?;
		}
		O運算子::=> {
			writeln!(真言檔, "\tsub t0, t0, t1")?;
		}
		O運算子::=> {
			writeln!(真言檔, "\tmul t0, t0, t1")?;
		}
		O運算子::=> {
			writeln!(真言檔, "\tdiv t0, t0, t1")?;
		}
	}

	writeln!(真言檔, "\tsd t0, 0(sp)") // t0 放入棧頂
}

組譯執行

riscv64-unknown-elf-gcc {{target}}.S  # 不加 -nostdlib 參數
qemu-riscv64 a.out