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 。