至此,貧道已經展示了零.一版音界咒的分詞、剖析、語義檢查,若程式能通過這些步驟,代表它完全合法。接下來,就可以生成目標碼了,在本指引中,貧道會示範如何生成精五真言(RISC-V)。
變數儲存
熟悉 C 語言的道友想必都曉得,全域變數與區域變數在程序執行時是放在不同位置。全域變數會放在數據段(data section),在整個程序執行的過程都佔用一塊記憶體空間;而區域變數則是則是存放在函式調用時臨時開的棧禎。
零.一版音界咒的變數可以視做全域的,畢竟該版本尚無函式調用的概念。
精五真言的數據段
很容易就能用精五真言設定全域變數,以下是範例數據段.S
:
.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, 甲, rt
, rt
可以是任意通用暫存器。
選讀:為什麼 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 壓入棧
addi sp, sp, -8 # 擴大棧 64 位元(8 位元組 = 64 位元)
li t0, 3 # t0 = 3
sd t0, 0(sp) # sd 將 64 位元 t0 存到棧頂
最後來看上述算術樹轉成堆疊機操作的完整精五真言:
# 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)
實作
以下展示一份精五真言生成的實作。
這是生成器的定義,其接收一個語法樹,把精五真言輸入到真言檔。變數集可以在符號檢查時取得。
pub struct O真言生成器 {
真言檔: File,
語法樹: O語法樹,
變數集: HashSet<String>,
}
impl O真言生成器 {
pub fn 生成(&mut self) -> io::Result<()> {
self.生成數據段()?;
self.生成代碼段()
}
...
}
真言生成分為「數據段」跟「代碼段」分開實作。
數據段(變數儲存)
數據段的生成頗為簡單,為每個變數在 .section .data
製造一相應的標籤,以 .quad
指定 64 位元空間。
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.換行()
}
(代碼段)運算
代碼段就相對複雜許多,原理已在前文解釋,道友們可閱讀註解來幫助理解。
這裡並沒有真的先轉換到後序表示法再生成代碼,而是對算術樹做後序遍歷的同時就把代碼給生成了。
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.語法樹;
for 句 in &語法樹.句 {
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