用1500 行建構可自我編譯的 C 編譯器 - 翁敏維

# 用1500 行建構可自我編譯的 C 編譯器 - 翁敏維 {%hackmd tGp8pt49Q2aT5cD5TFyaIA %} --- ==[投影片](https://drive.google.com/file/d/1-0QGf2JSni-CwYigaEORW6JUehS8LS79/view)== # Agenda * Purpose * Self-host * What is AMaCC? * How AMaCC works * IR (Intermediate representation) * ELF header * Output of AMaCC --- ## Purpose 可以自我編譯的編譯器代表在編譯自己的過程中可以不需要借助其他的toolchain, 但要完成這樣的編譯器並不是一件容易的事情..... (尤其是只需要1500行) [AMaCC](https://github.com/jserv/amacc) 辦到了究竟AMaCC怎麼樣用不到1500 行辦到? 讓我們看下去... --- # Introduce AMaCC ### Who implements AMaCC 由成功大學師生[黃敬群(jserv)](http://wiki.csie.ncku.edu.tw/User/jserv)、陳建霖、梁穎睿等人開發的self-compiling的C語言編譯器 ### What is AMaCC - self-compiling - `amacc.c` 所編譯出來的執行檔可用來編譯 `amacc.c`, 後者產生出來的執行檔一樣具備編譯 `amacc.c` 的能力 - 可以產生 ELF 格式、32-bit Arm 架構執行檔 - JIT的compiler - AMaCC是怎麼簡化code generation的過程的? - 透過dlsym來呼叫系統本身的library, 例如 `dlsym(0, "open")` - 一般來說, source code會先經過編譯器->組譯器->連結器, 最後產生執行檔, 而==AMaCC是直接產生執行檔== --- # 預備知識 - C語言 - self-hosting - IR (Intermediate representation) - Dynamic linking - relocation - symbol table - AMaCC是怎麼對offset作relocation的? - ELF header - AMaCC是怎麼填表的? - 我們用readelf來看看amacc的產出 --- # self-host? ## 為什麼需要self-host? 假如有一個語言X, 他的compiler不能編譯X語言, 那要怎麼驗證compiler? 但是語言X的第一個compiler產生之前, 要怎麼編譯出語言X的第一個compiler? 這個就是 bootstrapping problem 有三種方法: <ol> <li>徒手把machine code打出來</li> <li>用另外一個語言寫出來的compiler來compile</li> <li>透過 interpreter 建立 translator</li> </ol> --- # IR (Intermediate representation) ## What is IR? ## 為什麼IR很重要? ## AMaCC在IR這件事上是怎麼處理的? - 先parse C的source code (透過next) - 轉成IR的opcode - 在產生執行檔的過程中, 是怎麼轉成IR的? - 這些opcode會轉成對應的machine code (透過codegen) - 轉成machine code後, 最後作relocation的計算, 取得真正的address ```shell qemu-arm -L /usr/arm-linux-gnueabihf ./amacc -s tests/hello.c 1: #include <stdio.h> 2: 3: int main() 4: { 5: printf("hello, world\n"); ENT 0 IMM -161644536 PSH PRTF ADJ 1 6: return 0; IMM 0 LEV 7: } LEV ``` - add/sub/mul 指令編碼 - 為何要 pop {r1}? --- # ELF header * Program header * Section header * Segment, section ## Program header ```shell $ arm-linux-gnueabihf-readelf -l ./elf/amacc Elf file type is EXEC (Executable file) Entry point 0xb73ab0b4 There are 4 program headers, starting at offset 52 Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align LOAD 0x000000 0xb73ab000 0xb73ab000 0x125a0 0x125a0 R E 0x1000 LOAD 0x013008 0xb746d008 0xb746d008 0x00f36 0x00f36 RW 0x1000 INTERP 0x013cb8 0xb746dcb8 0xb746dcb8 0x00019 0x00019 R 0x1 [Requesting program interpreter: /lib/ld-linux-armhf.so.3] DYNAMIC 0x013c48 0xb746dc48 0xb746dc48 0x00070 0x00070 RW 0x4 Section to Segment mapping: Segment Sections... 00 .text .rel.plt .plt 01 .data .dynstr .dynsym .dynamic .interp .got 02 .interp 03 .dynamic ``` ## Section header ```shell $ arm-linux-gnueabihf-readelf -s ./elf/amacc Symbol table '.dynsym' contains 19 entries: Num: Value Size Type Bind Vis Ndx Name 0: 00000000 0 NOTYPE LOCAL DEFAULT UND 1: 00000000 0 FUNC GLOBAL DEFAULT UND open 2: 00000000 0 FUNC GLOBAL DEFAULT UND read 3: 00000000 0 FUNC GLOBAL DEFAULT UND write 4: 00000000 0 FUNC GLOBAL DEFAULT UND close 5: 00000000 0 FUNC GLOBAL DEFAULT UND printf 6: 00000000 0 FUNC GLOBAL DEFAULT UND malloc 7: 00000000 0 FUNC GLOBAL DEFAULT UND free 8: 00000000 0 FUNC GLOBAL DEFAULT UND memset 9: 00000000 0 FUNC GLOBAL DEFAULT UND memcmp 10: 00000000 0 FUNC GLOBAL DEFAULT UND memcpy 11: 00000000 0 FUNC GLOBAL DEFAULT UND strcmp 12: 00000000 0 FUNC GLOBAL DEFAULT UND mmap 13: 00000000 0 FUNC GLOBAL DEFAULT UND dlsym 14: 00000000 0 FUNC GLOBAL DEFAULT UND bsearch 15: 00000000 0 FUNC GLOBAL DEFAULT UND strlen 16: 00000000 0 FUNC GLOBAL DEFAULT UND __clear_cache 17: 00000000 0 FUNC GLOBAL DEFAULT UND __libc_start_main 18: 00000000 0 FUNC GLOBAL DEFAULT UND exit ``` ## Segment, section --- ### Program header - PT_LOAD - .text - .data - PT_INTERP - PT_DYNAMIC --- ### Section header - .text - .rodata - .rel.plt - .dynsym - .symtab - What is sh_flags? - What's the different between .dynsym and .symtab? --- ### Segment, Section - Segment and section is different --- # Relocation ## What is reloc_imm for? ## 0xeb000000是怎麼來的? - BL opcode ## 將offset計算成address的計算方式 - R_ARM_THM_CALL[[aaelf]](http://infocenter.arm.com/help/topic/com.arm.doc.ihi0044f/IHI0044F_aaelf.pdf#page=26) * Static relocations * Thumb32: class of the relocation * Operation: ((S + A) | T) – P * A: -4[[aaelf]](http://infocenter.arm.com/help/topic/com.arm.doc.ihi0044f/IHI0044F_aaelf.pdf#page=25) <table> <tr> <td>((S + A) | T) – P</td> <td> S:function的位址 A:addend T: P:address of the place being relocated </td> </td></tr> </table> --- # Output of AMaCC - Program header - Section header - .dynsym section - .rel.plt --- # Overview source code of AMaCC - Program header - PT_LOAD - PT_INTERP - PT_DYNAMIC - Section header - .text - .rel.plt - .dynsym - .symtab - libc_start_main --- ## Reference * [手把手教你建構 C 語言編譯器](https://github.com/lotabout/write-a-C-interpreter) * [Clang Successfully Self-Hosts!](http://blog.llvm.org/2010/02/clang-successfully-self-hosts.html), Feb 2010 / [clang 首度公開釋出於 Sep 2007](https://en.wikipedia.org/wiki/Clang) * [How A Compiler Works: GNU Toolchain](https://www.slideshare.net/jserv/how-a-compiler-works-gnu-toolchain) * [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/s/Hy72937Me) * [親手打造 Dynamic Library Loader](http://blog.linux.org.tw/~jserv/archives/002120.html) * [ld.so, ld-linux.so - dynamic linker/loader](http://man7.org/linux/man-pages/man8/ld.so.8.html) * [AMaCC](https://github.com/jserv/amacc/) * [ELF for the ARM Architecture](http://infocenter.arm.com/help/topic/com.arm.doc.ihi0044f/IHI0044F_aaelf.pdf) * [Procedure Call Standard for the ARM Architecture](http://infocenter.arm.com/help/topic/com.arm.doc.ihi0042f/IHI0042F_aapcs.pdf) * [ARM Architecture Reference Manual ARMv7-A and ARMv7-R edition](https://static.docs.arm.com/ddi0406/c/DDI0406C_C_arm_architecture_reference_manual.pdf) * [Compiler Design - Semantic Analysis ](https://www.tutorialspoint.com/compiler_design/compiler_design_semantic_analysis.htm) ###### tags: `COSCUP2018` `source` `AMaCC` `ARMv7-a` `Encoding A1` `ELF` `arm` `armv7-a` `dynamic linker`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.