owned this note   changed 2 years ago  
Linked with GitHub

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

歡迎來到 https://hackmd.io/c/COSCUP2018 共筆 :mega:
點擊本頁上方的 開始用 Markdown 一起寫筆記！
手機版請點選上方 按鈕展開議程列表。

投影片

Agenda

  • Purpose
  • Self-host
  • What is AMaCC?
  • How AMaCC works
  • IR (Intermediate representation)
  • ELF header
  • Output of AMaCC

Purpose

可以自我編譯的編譯器代表在編譯自己的過程中
可以不需要借助其他的toolchain,
但要完成這樣的編譯器並不是一件容易的事情…
(尤其是只需要1500行)

AMaCC 辦到了

究竟AMaCC怎麼樣用不到1500 行辦到?

讓我們看下去…

Introduce AMaCC

Who implements AMaCC

由成功大學師生黃敬群(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
有三種方法:

  1. 徒手把machine code打出來
  2. 用另外一個語言寫出來的compiler來compile
  3. 透過 interpreter 建立 translator

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
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

$ 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

$ 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]
    • Static relocations
    • Thumb32: class of the relocation
    • Operation: ((S + A) | T) – P
    • A: -4[aaelf]
((S + A) | T) – P S:function的位址
A:addend
T:
P:address of the place being relocated

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

tags: COSCUP2018 source AMaCC ARMv7-a Encoding A1 ELF arm armv7-a dynamic linker
Select a repo