lacc離開lacc Source Cead下載

lacc

C#源碼

1.0.0

下載

LACC：一個簡單的自我託管C編譯器

這是我的一個玩具項目，其目的是為C編寫C編譯，該編譯器能夠編譯自身。

特徵

除了以後標準的某些功能外，對C89的完全支持。
目標X86_64彙編GNU語法（-s），二進制ELF對象文件（-c）或純預處理（-e）。
豐富的中間表示形式，為每個函數定義的基本塊建立一個控制流程圖（CFG）。這是基本數據流分析和優化的目標。

安裝

克隆並從源構建，二進制將放置在bin/lacc中。

 git clone https://github.com/larmel/lacc.git
cd lacc
./configure
make
make install

默認配置包括對環境的一些基本探測，以檢測我們正在編譯的機器和LIBC。公認的平台當前包括帶有GLIBC或MUSL的Linux和OpenBSD。

某些標準庫標題，例如stddef.h和stdarg.h ，包含固有特定編譯器的定義，並專門為LIB/下的LACC提供。如果要直接使用bin/lacc而不安裝標頭，則可以通過設置--libdir來覆蓋位置，以直接指向該文件夾。

install目標將將二進制和標題複製到通常的位置，或者按照--prefix或--bindir配置。還有一個設置DESTDIR選項。執行make uninstall以刪除已復制的所有文件。

有關自定義構建和安裝參數的選項，請參見./configure --help 。

用法

命令行接口與GCC和其他編譯器相似，主要使用相同標誌和選項的子集。

 -E         Output preprocessed.
-S         Output GNU style textual x86_64 assembly.
-c         Output x86_64 ELF object file.
-dot       Output intermediate representation in dot format.
-o         Specify output file name. If not speficied, default to input file
           name with suffix changed to '.s', '.o' or '.dot' when compiling
           with -S, -c or -dot, respectively. Otherwise use stdout.
-std=      Specify C standard, valid options are c89, c99, and c11.
-I         Add directory to search for included files.
-w         Disable warnings.
-g         Generate debug information (DWARF).
-O{0..3}   Set optimization level.
-D X[=]    Define macro, optionally with a value. For example -DNDEBUG, or
           -D 'FOO(a)=a*2+1'.
-f[no-]PIC Generate position-independent code.
-v         Print verbose diagnostic information. This will dump a lot of
           internal state during compilation, and can be useful for debugging.
--help     Print help text.

不匹配任何選項的參數是輸入文件。如果未指定彙編模式，LACC將充當系統鏈接器/bin/ld的包裝器。支持一些普通的鏈接標誌。

 -Wl,       Specify linker options, separated by commas.
-L         Add linker include directory.
-l         Add linker library.
-shared    Passed to linker as is.
-rdynamic  Pass -export-dynamic to linker.

作為示例調用，此處是將test/c89/fact.c編譯為對象代碼，然後使用系統鏈接器生成最終的可執行文件。

 bin/lacc -c test/c89/fact.c -o fact.o
bin/lacc fact.o -o fact

該程序是測試套件的一部分，計算5！使用遞歸，然後退出答案。運行./fact然後是echo $?應該打印120 。

執行

編譯器用C89編寫，總計約為19k代碼。除C標準性Libary外，沒有外部依賴性，調用鏈接器所需的一些系統調用。

實施分為四個主要部分；預處理器，解析器，優化器和後端在SRC/下方的目錄中分別在自己的目錄中。通常，每個模塊（通常與定義公共接口的.h文件配對的A .c文件）主要取決於其自己的子樹中的標題。在全球層面上共享的聲明屬於/lacc/。在這裡，您將找到核心數據結構，以及在預處理，解析和代碼生成之間的接口。

預處理器

預處理包括讀取文件，令牌化，宏擴展和指令處理。預處理程序的接口是peek(0) ， peekn(1) ， consume(1) ， try_consume(1)和next(0) ，它查看了預處理的struct token對象的流。這些定義在包括/lacc/token.h中。

輸入處理是完全懶惰的，這是由解析器驅動的，稱這些功能消耗了更多的輸入。預處理令牌的緩衝區保留了lookahead，並在偷看時按需填充。

中間表示

代碼被建模為基本塊的控制流程圖，每個塊都保留了三個地址代碼語句的序列。每個外部變量或函數定義都由一個struct definition對象表示，定義單個struct symbol和持有代碼的CFG。支持中間表示的數據結構可以在Include/lacc/ir.h中找到。

可視化中間表示是一個獨立的輸出目標。如果指定了-dot選項，則會生成一個點格式的文本文件作為輸出。

 bin/lacc -dot -I include src/backend/compile.c -o compile.dot
dot -Tps compile.dot -o compile.ps

下面是從SRC/Backend/Compile.c中找到的函數的一個示例，顯示了完整圖的切片。通過運行顯示的命令，可以將完整的輸出作為郵稿文件生成。

示例中間表示

圖中的每個基本塊都有一個語句列表，最常見的是IR_ASSIGN ，該語句將表達式（ struct expression ）分配給變量（ struct var ）。表達式還包含可變操作數，這些操作數可以高級別編碼內存位置，地址和脫水指針。

DIRECT操作數請參閱*(&symbol + offset)的內存，其中符號是內存中特定位置的變量或臨時位置（例如堆棧）。
ADDRESS操作數準確代表DIRECT操作數的地址，即(&symbol + offset) 。
DEREF操作數是指由符號指向的內存（必須是指針類型）。該表達式為*(symbol + offset) ，它需要兩個負載操作才能映射到組裝。只有DEREF和DIRECT變量才能是分配的目標，也可以是l值。
IMMEDIATE操作數保持恆定數字或字符串。立即操作數的評估會自動持續折疊。

解析器

解析器是手動編碼的遞歸下降，主要部分分為src/parser/neclaration.c，src/parser/initializer.c，src/parser/expression.c和src/parser/statement.c。當前功能控制流程圖和該圖中的當前活動基本塊作為參數傳遞給每個生產。該圖逐漸構造，因為新的三個地址代碼指令被添加到當前塊中。

下面的示例顯示了位或表達式的解析規則，該規則將新的IR_OP_OR操作添加到當前塊中。 eval_expr中的邏輯將確保操作value和block->expr有效，如果發生錯誤，則終止。

 static struct block *inclusive_or_expression(
    struct definition *def,
    struct block *block)
{
    struct var value;

    block = exclusive_or_expression(def, block);
    while (try_consume('|')) {
        value = eval(def, block, block->expr);
        block = exclusive_or_expression(def, block);
        block->expr = eval_or(def, block, value, eval(def, block, block->expr));
    }

    return block;
}

最新的評估結果始終存儲在block->expr中。分支是通過實例化新基本塊和維護指針來完成的。每個基本塊都有一個真實和錯誤的分支指針，指向其他塊，這是對分支和gotos建模的方式。請注意，在沒有任何語法樹結構中。它僅隱含在遞歸中。

優化器

構建控制流程圖的主要動機是能夠進行數據流分析和優化。此處的當前功能仍然有限，但是可以通過其他更高級的分析和優化通行證輕鬆擴展。

Livices分析用於在每個語句中弄清楚哪些符號後來可以讀取。數據流算法是使用用於表示符號的位掩碼實現的，將其編號為1-63。結果，優化僅適用於少於64個變量的函數。該算法也必須非常保守，因為沒有指針別名分析（尚未）。

使用Livices信息，進行死商店消除的轉換通行證可以刪除IR_ASSIGN節點，該節點無能為力，從而減小了生成的代碼的大小。

後端

有三個後端目標：用於中間表示形式的文本彙編代碼，精靈對象文件和點。從解析器產生的每個struct definition都將傳遞給SRC/Backend/Compile.c模塊。在這裡，我們進行了從中間控制流程圖的映射到較低級別的IR，將代碼簡化為直接代表X86_64指令的內容。可以在SRC/Backend/x86_64/encoding.h中找到其定義。

根據程序啟動時設置的功能指針，指令將發送到小精靈後端或文本組件。因此，輸出文本組件的代碼非常簡單，或多或少僅僅是低級IR指令與其GNU語法彙編代碼之間的映射。請參閱src/backend/x86_64/coustmemble.c。

點輸出是一個單獨的管道，不需要生成低級IR。編譯模塊將簡單地將CFG轉發到SRC/Backend/graphviz/dot.c。

正確性

測試是通過比較與LACC和系統編譯器（CC）的程序的運行時輸出來完成的。在測試/目錄下可以找到用於驗證的小型獨立程序的集合。使用Check.SH執行測試，該測試將驗證預處理，組裝和ELF輸出。

 $ test/check.sh bin/lacc test/c89/fact.c
[-E: Ok!] [-S: Ok!] [-c: Ok!] [-c -O1: Ok!] :: test/c89/fact.c

編譯器的完整測試是通過在LACC的自託管版本上瀏覽所有測試用例來完成的。

 make -C test

這將首先使用已經構建的bin/lacc生產bin/bootstrap/lacc ，這又用於構建bin/selfhost/lacc 。在引導程序和自助主機階段之間，比較中間對象文件以保持平等。如果一切正常，這些階段應產生相同的二進製文件。當所有測試都通過二進制二進製文件時，編譯器是“好”。這應該永遠是綠色的。

CSMITH

很難提出涵蓋所有可能情況的良好測試套件。為了淘汰錯誤，我們可以使用CSMITH生成適合驗證的隨機程序。

 ./csmith.sh

CSMITH.SH腳本運行CSMITH以生成無限的隨機程序序列，直到某些東西使測試線束失敗。它通常會在沒有故障的情況下進行數千個測試。

在進行4314個測試後仍然成功

CSMITH生成的程序包含一組全局變量，並在這些變量上產生突變。最後，對所有變量的完整狀態進行了校驗和輸出。然後可以與不同的編譯器進行比較，以查找差異或錯誤。有關CSMITH生成的示例程序，請參見Doc/Random.c，該程序也由LACC正確編譯。

恰當

當發現錯誤時，我們可以使用precure來最少。然後，這將在正常測試套件中成為新的測試用例。

表現

已經為使編譯器本身快速而付出了一些努力（儘管生成的代碼仍然非常不優化）。作為性能基準和正確性測試，我們使用SQLite數據庫引擎。源代碼分佈為單個〜7 MB（7184634字節）大的C文件，該文件跨度超過200 K（包括註釋和Whitespace），非常適合對編譯器進行壓力測試。

以下實驗是在帶有i5-7300U CPU的筆記本電腦上運行的，並編譯了SQLite3的3.20.1版本。測量由編譯到對象代碼（-c）製成。

彙編速度

用LACC編譯文件所需的時間少於200 ms，但是我們沒有時間來查看執行CPU週期和指令的更準確的採樣。硬件性能計數器數據是通過perf stat收集的，並使用valgrind --trace-children=yes收集內存分配。在Valgrind中，我們僅在運行GCC時計算編譯器本身（ cc1可執行文件）的貢獻。

LACC的數字來自由make CC='clang -O3 -DNDEBUG' bin/lacc產生的優化構建。每個編譯器都用參數-c sqlite/sqlite3.c -o foo.o調用。

編譯器	週期	指示	分配	字節分配	結果大小
lacc	412,334,334	619,466,003	49,020	24,244,107	1,590,482
TCC（0.9.27）	245,142,166	397,514,762	2,909	23,020,917	1,409,716
GCC（9.3.0）	9,958,514,599	14,524,274,665	1,546,790	1,111,331,606	1,098,408
clang（10.0.0）	4,351,456,211	5,466,808,426	1,434,072	476,529,342	1,116,992

還需要做一些工作來靠近TCC，這可能是最快的C編譯器之一。儘管如此，我們與TCC性能的合理距離不在合理的距離之內，並且比GCC和Clang更好的數量級。

代碼質量

從上表中，我們可以看到LACC生成的SQLite對象文件的大小大於其他編譯器生成的sqlite對象文件，這表明我們輸出的最佳代碼較少。

為了比較LACC和GCC生成的代碼的相對質量，我們可以查看由Self -Host二進制執行的動態說明數量與GCC構建的二進制指令的數量。我們運行與上面相同的測試，將SQLITE編譯為對象代碼。該測試的目標是GCC生產的默認編譯器構建（ bin/lacc ），以及LACC生產的Self -Host二進制二進制二進制二進制二進製文件（ bin/selfhost/lacc ）。這兩個目標均可產生，而無需啟用任何優化，也沒有定義NDEBUG 。