编译器入门

编译器(compiler)就是一个翻译其他程序的程序而已。传统的编译器将源代码翻译为计算机能够理解的可执行机器代码(有一些编译器将源代码翻译为另一种编程语言。这些编译器叫做从源码到源码的翻译器,source-to-source translators or transpilers)。LLVM 是一个广泛使用的编译器项目,它包含了许多模块化的编译器工具。传统编译器涉及包含了三个部分:

traditional compiler design

  • 前端(frontend)将源代码翻译为一个中间表示(intermediate representation, IR)。clang 是 LLVM 中 C 系语言的前端。
  • 优化器(optimizer)会对 IR 进行分析,并将其翻译成一个更高效的形式。opt 是 LLVM 的优化器工具。
  • 后端(backend)通过将 IR 映射为目标硬件的指令集生成机器码。llc 是 LLVM 的后端工具。

LLVM IR 是一个类似汇编语言的低级语言。但是,它将针对特定硬件的信息抽象了出去。

Hello, Compiler

下面是一个简单的 C 程序,它只是向标准输出打印出 “Hello, Compiler!”。虽然人类可以读懂 C 语言的语法,但是机器并不认识它。我将通过三个编译步骤,使得机器能够执行这个程序。

// compile_me.c
// Wave to the compiler. The world can wait.

#include <stdio.h>

int main() {
  printf("Hello, Compiler!\n");
  return 0;
}

The Frontend

正如我上面提到的,clang 是 LLVM C 系语言的前端。clang 包含了一个 C 预处理器(preprocessor),词法分析器(lexer),语法分析器(parser),semantic analyzer(语义分析器)和中间表示生成器(IR generator)。

  • C 预处理器 在翻译成 IR 之前对源代码进行修改。预处理器会将外部文件包含进来,比如上面的#include <stdio.h>。它会用 C 标准库文件 stdio.h 的所有内容替换 #include <stdio.h> 这一行,stdio.h 包含了 printf 函数的声明。

通过执行下列命令来查看预处理器步骤的输出:

clang -E compile_me.c -o preprocessed.i
  • 词法分析器(lexer, 或者叫 scanner 或 tokenizer) 将一串字符转换成一串词。每个词,或者叫 token (记号),被分配到 5 个句法的类别:punctuation(标点符号),keyword(关键词),identifier(标识符),literal(常量) 或 comment(注释)。

compile_me.c 的 tokenization:

tokennizaiton

  • 语法分析器决定了由词法分析器生成的一串词是否包含了源语言中的有效句。在分析完词的语法以后,它输出了一个抽象语法树(abstract syntax tree, AST)。一个 Clang AST 中的节点表示 declaration,statement, type.

compile_me.c 的 AST:

AST

  • 语义分析器遍历 AST,判定代码句的涵义是否有效。这个阶段会检查类型错误。如果 compile_me.c 中的 main 函数返回了 "zero" 而不是 0, 语义分析器就会抛出一个错误,因为 "zero" 不是 int 类型。
  • IR 生成器 将 AST 翻译为 IR。

在 compile_me.c 上运行 clang 前端来生成 LLVM IR:

clang -S -emit-llvm -o llvm_ir.ll compile_me.c

在 llvm_ir.ll 中的 main 函数:

; llvm_ir.ll

@.str = private unnamed_addr constant [18 x i8] c"Hello, Compiler!\0A\00", align 1

define i32 @main() {
  %1 = alloca i32, align 4 ; <- memory allocated on the stack
  store i32 0, i32* %1, align 4
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}

declare i32 @printf(i8*, ...)

优化器

优化器的任务是,基于对程序运行时行为的理解,提升代码的效率。优化器的输入为 IR,输出为优化后的 IR。LLVM 的优化器工具,opt,将会使用 -O2 (大写字母 o,2)标志优化处理器速度,-Os (大写字母 o,s)优化生成目标的大小。

来看一下优化器优化之前的 LLVM IR 代码和优化后的代码:

opt -O2 llvm_ir.ll -o optimized.ll

optimized.ll 的 main 函数:

; optimized.ll

@str = private unnamed_addr constant [17 x i8] c"Hello, Compiler!\00"

define i32 @main() {
  %puts = tail call i32 @puts(i8* getelementptr inbounds ([17 x i8], [17 x i8]* @str, i64 0, i64 0))
  ret i32 0
}

declare i32 @puts(i8* nocapture readonly)

在优化后的版本中,main 没有在栈(stack)上分配内存,因为它没有使用任何内存。优化后的代码也没有调用 printf, 而是调用了 puts,因为它没有用到 printf 的任何格式化功能。

当然了,优化器知道的不仅仅是什么时候该用 puts 代替 printf. 优化器也会对循环进行展开,内联简单计算的结果。考虑下面的代码,它将两个数加起来并打印结果:

// add.c
#include <stdio.h>

int main() {
  int a = 5, b = 10, c = a + b;
  printf("%i + %i = %i\n", a, b, c);
}

这是未优化的 LLVM IR:

@.str = private unnamed_addr constant [14 x i8] c"%i + %i = %i\0A\00", align 1

define i32 @main() {
  %1 = alloca i32, align 4 ; <- allocate stack space for var a
  %2 = alloca i32, align 4 ; <- allocate stack space for var b
  %3 = alloca i32, align 4 ; <- allocate stack space for var c
  store i32 5, i32* %1, align 4  ; <- store 5 at memory location %1
  store i32 10, i32* %2, align 4 ; <- store 10 at memory location %2
  %4 = load i32, i32* %1, align 4 ; <- load the value at memory address %1 into register %4
  %5 = load i32, i32* %2, align 4 ; <- load the value at memory address %2 into register %5
  %6 = add nsw i32 %4, %5 ; <- add the values in registers %4 and %5. put the result in register %6
  store i32 %6, i32* %3, align 4 ; <- put the value of register %6 into memory address %3
  %7 = load i32, i32* %1, align 4 ; <- load the value at memory address %1 into register %7
  %8 = load i32, i32* %2, align 4 ; <- load the value at memory address %2 into register %8
  %9 = load i32, i32* %3, align 4 ; <- load the value at memory address %3 into register %9
  %10 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i32 0, i32 0), i32 %7, i32 %8, i32 %9)
  ret i32 0
}

declare i32 @printf(i8*, ...)

这是优化后的 LLVM IR:

@.str = private unnamed_addr constant [14 x i8] c"%i + %i = %i\0A\00", align 1

define i32 @main() {
  %1 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i64 0, i64 0), i32 5, i32 10, i32 15)
  ret i32 0
}

declare i32 @printf(i8* nocapture readonly, ...)

优化后的 main 函数,本质上就是未优化版本的 17 和 18 行将变量进行内联。opt 对加法进行了计算,因为所有的变量都是常量。很酷,是吧?

The Backend

LLVM 的后端工具是 llc.从 LLVM IR 输入生成机器码,它经历了三个阶段:

  • 指令选取(instruction selection) 是从 IR 指令到目标机器指令集的映射。这一步使用了虚拟寄存器一个无限的命令空间。
  • 寄存器分配(register allocation) 是从虚拟寄存器到目标架构上真实寄存器的映射。我的 CPU 是 x86 架构,也就是说只能使用 16 个寄存器。但是,编译器会选择尽可能少地使用寄存器。
  • 指令调度(instruction scheduling) 是对操作的重新安排,它反映了目标机器上的性能限制。

执行下面的命令将会产生一些机器码!

llc -o compiled-assembly.s optimized.ll
_main:
    pushq   %rbp
    movq    %rsp, %rbp
    leaq    L_str(%rip), %rdi
    callq   _puts
    xorl    %eax, %eax
    popq    %rbp
    retq
L_str:
    .asciz  "Hello, Compiler!"

这个程序是 x86 汇编语言,它是目标机器能够读懂的语言的一个“人类表示”。目标机器只能读懂 0 和 1,汇编语言是将 0 1 代码用人类能够读懂的方式表达了出来。相信肯定会有人懂的:).

资源:

  1. Engineering a compiler
  2. Getting Started with LLVM Core Libraries

本文译自:An Intro to Compilers

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏王小雷

SAS进阶《深入解析SAS》之开发多语言支持的SAS程序

SAS进阶《深入解析SAS》之开发多语言支持的SAS程序 1. 多语言支持的应用程序是指该程序在世界给第使用时,其能够处理的数据,以及处理数据的方式、信息展现的...

2079
来自专栏web前端教室

JavaScript ES6 新特性之 Generator

(昨天晚上喝多了没更新,6瓶雪花淡爽,我就醉了~~) 今儿个学习下ES6 的生成器 Generator,这玩艺的名字挺唬人的,我刚一看的时候还以为能for循环似...

1918
来自专栏Golang语言社区

一起用golang之Go程序的套路

系统性地介绍golang基础的资料实在太多了,这里不再一一赘述。本文的思路是从另一个角度来由浅入深地探究下Go程序的套路。毕竟纸上得来终觉浅,所以,能动手就不要...

2752
来自专栏流媒体

Json海量数据解析Json海量数据解析

​ 在android开发中,app和服务器进行数据传输时大多数会用到json。在解析json中通常会用到以下几种主流的解析库:jackson、gson、fa...

1322
来自专栏LEo的网络日志

数据结构学习之队列(queue)

34013
来自专栏DOTNET

.Net多线程编程—同步机制

1.简介 新的轻量级同步原语:Barrier,CountdownEvent,ManualResetEventSlim,SemaphoreSlim,SpinLoc...

3105
来自专栏walterlv - 吕毅的博客

迫不及待地体验了一把 C#8.0 中的可空引用类型(Nullable Reference)

发布于 2017-12-18 13:41 更新于 2017-12...

992
来自专栏JAVA后端开发

flowable实现多实例节点的自由跳转

最近弃用activiti,改用flowable,发现在实现多节点实例自由跳转时,有很大区别。 自由跳转整理如下:

5452
来自专栏铭毅天下

干货 | Elasticsearch Nested类型深入详解

本文通过一个例子将Nested类型适合解决的问题、应用场景、使用方法串起来, 文中所有的DSL都在Elasticsearch6.X+验证通过。

1983
来自专栏数据小魔方

Python可视化笔记之folium交互地图

leftlet给R语言提供了很好用的交互式动态地图接口,其在Python中得API接口包名为folium(不知道包作者为何这样起名字,和leaflet已经扯不上...

4214

扫码关注云+社区