《编译原理之美》笔记——后端部分

我们使用的语言抽象程度越来越高，每一次抽象对下一层的复杂性做了屏蔽，因此使用起来越来越友好。而编译技术，则帮你一层层地还原这个抽象过程，重新转换成复杂的底层实现。

程序和操作系统的关系

程序视角的堆栈结构

操作系统加载可执行文件到内存的，并且定位到代码区里程序的入口开始执行。操作系统看到的是一个个指令 和 一个个内存地址

为什么会有一块动态内存区域？os 启动的时候， 一波三折， 不停的往内存加载更大的程序， 第一波占用的内存第二波就干别的用了。c 语言手动malloc 和 free，其实微观上，汇编语言也是在字节层面上不停地malloc和free。

os 提供systemcall malloc 内存，但没有提供 systemcall malloc 一个heap 或 stack 出来。

做完语义分析以后，编译器这时可以直接生成目标代码，因为编译器已经完全理解了程序的含义，并把它表示成了带有语义信息的 AST、符号表等数据结构。生成目标代码的工作，叫做后端工作。做这项工作有一个前提，就是编译器需要懂得目标语言，也就是懂得目标语言的词法、语法和语义，这样才能保证翻译的准确性。通常来说，目标代码指的是汇编代码，它是汇编器（Assembler）所能理解的语言，跟机器码有直接的对应关系。汇编器能够将汇编代码转换成机器码。

熟练掌握汇编代码对于初学者来说会有一定的难度。但更麻烦的是，对于不同架构的 CPU，还需要生成不同的汇编代码，这使得我们的工作量更大。所以，我们通常要在这个时候增加一个环节：先翻译成中间代码（Intermediate Representation，IR）。

遍历 AST 手工生成汇编代码

AST 的每个节点有各种属性，遍历节点时，针对节点属性类型做相应处理。生成汇编代码的过程，基本上就是基于 AST 拼接字符串

case PlayScriptParser.ADD:
    // 为加法运算申请一个临时的存储位置，可以是寄存器和栈
    address = allocForExpression(ctx);
    bodyAsm.append("\tmovl\t").append(left).append(", ").append(address).append("\n");  //把左边节点拷贝到存储空间
    bodyAsm.append("\taddl\t").append(right).append(", ").append(address).append("\n");  //把右边节点加上去
    break;

翻译程序的入口generate

1. 生成一个.section 伪指令，表明这是一个放文本的代码段。
2. 遍历 AST 中的所有函数，调用 generateProcedure() 方法为每个函数生成一段汇编代码，再接着生成一个主程序的入口。

3. 在一个新的 section 中，声明一些全局的常量（字面量）

   public String generate() { StringBuffer sb = new StringBuffer();

    // 1.代码段的头
    sb.append("\t.section  __TEXT,__text,regular,pure_instructions\n");
   
    // 2.生成函数的代码
    for (Type type : at.types) {
        if (type instanceof Function) {
            Function function = (Function) type;
            FunctionDeclarationContext fdc = (FunctionDeclarationContext) function.ctx;
            visitFunctionDeclaration(fdc); // 遍历，代码生成到bodyAsm中了
            generateProcedure(function.name, sb);
        }
    }
   
    // 3.对主程序生成_main函数
    visitProg((ProgContext) at.ast);
    generateProcedure("main", sb);
   
    // 4.文本字面量
    sb.append("\n# 字符串字面量\n");
    sb.append("\t.section  __TEXT,__cstring,cstring_literals\n");
    for(int i = 0; i< stringLiterals.size(); i++){
        sb.append("L.str." + i + ":\n");
        sb.append("\t.asciz\t\"").append(stringLiterals.get(i)).append("\"\n");
    }
   
    // 5.重置全局的一些临时变量
    stringLiterals.clear();
       
    return sb.toString();  }

generateProcedure() 方法把函数转换成汇编代码

1. 生成函数标签、序曲部分的代码、设置栈顶指针、保护寄存器原有的值等。
2. 接着是函数体，比如本地变量初始化、做加法运算等。

3. 最后是一系列收尾工作，包括恢复被保护的寄存器的值、恢复栈顶指针，以及尾声部分的代码。

   private void generateProcedure(String name, StringBuffer sb) { // 1.函数标签 sb.append(“\n## 过程:”).append(name).append(“\n”); sb.append(“\t.globl ”).append(name).append(“\n”); sb.append(“”).append(name).append(“:\n”); // 2.序曲 sb.append(“\n\t# 序曲\n”); sb.append(“\tpushq\t%rbp\n”); sb.append(“\tmovq\t%rsp, %rbp\n”); // 3.设置栈顶 // 16字节对齐 if ((rspOffset % 16) != 0) { rspOffset = (rspOffset / 16 + 1) * 16; } sb.append(“\n\t# 设置栈顶\n”); sb.append(“\tsubq\t$”).append(rspOffset).append(“, %rsp\n”); // 4.保存用到的寄存器的值 saveRegisters(); // 5.函数体 sb.append(“\n\t# 过程体\n”); sb.append(bodyAsm); // 6.恢复受保护的寄存器的值 restoreRegisters(); // 7.恢复栈顶 sb.append(“\n\t# 恢复栈顶\n”); sb.append(“\taddq\t$”).append(rspOffset).append(“, %rsp\n”); // 8.如果是main函数，设置返回值为0 if (name.equals(“main”)) { sb.append(“\n\t# 返回值\n”); sb.append(“\txorl\t%eax, %eax\n”); } // 9.尾声 sb.append(“\n\t# 尾声\n”); sb.append(“\tpopq\t%rbp\n”); sb.append(“\tretq\n”);

    // 10.重置临时变量
    rspOffset = 0;
    localVars.clear();
    tempVars.clear();
    bodyAsm = new StringBuffer();  }

二进制文件格式和链接

汇编器可以把每一个汇编文件都编译生成一个二进制的目标文件，或者叫做一个模块。在一个文件中调用另一个文件的函数时，并不知道函数的地址。所以，汇编器把这个任务推迟，交给链接器去解决。就好比你去饭店排队吃饭，首先要拿个号（函数的标签），但不知道具体坐哪桌。等叫到你的号的时候（链接过程），服务员才会给你安排一个确定的桌子（函数的地址）。

链接可以被分为编译时链接、加载时链接，以及运行时链接三种类型。

1. “静态链接”中的“静态”，实际上是指在用户准备执行这个程序前，它正常运行所依赖的全部代码实现便已经“静静地躺在那里”，成为了整个可执行文件的一部分。
2. 使用动态链接编译的程序，编译器只会为这些依赖代码在可执行程序文件中留下用于临时占位的“槽”。而只有当用户开始调用程序时，相关代码才会被真正加载到内存。 通常来说，在编译程序时，我们会对那些基础且常见的公有代码库（如 libc、libm、libthread 等）采用动态链接。这些系统库已经成为支持现代操作系统正常运作的一部分，因此在大多数情况下它们都不可或缺。而对于应用程序独有的那部分实现，我们一般采用静态链接，让它们能够直接成为二进制可执行文件的一部分。

Linux 平台上的 .o 目标文件实际上是一种被称为“可重定位文件”的 ELF 文件类型。每一个可重定位目标文件内都存在有一个符号表，它包含了该文件对应源码内使用到的所有全局变量和函数信息。

1. 符号解析，是指为每一个外部符号引用，找到一个与之关联的符号定义。当有重名的多个符号定义存在时，链接器会按照一定规则来选择适用的版本。如果链接器在搜索完所有输入的目标文件后，仍存在无法被解析的符号，它便会终止程序处理，并抛出类似 “undefined reference to symbol” 的错误信息。
2. 重定位，
   1. 链接器会将输入的多个目标文件的同类型 Section 进行合并
   2. 并为它们和所有程序使用到的符号分配运行时的 VAS 地址。
   3. 借助重定位表中的信息，链接器可以对上一步中得到的外部符号，进行地址及值上的修正（链接前，由于尚不清楚这些符号定义的真实所在位置，因此会使用默认值（比如 0）来作为它们在机器代码中的地址占位符。）。

在 Linux 下，目标文件、共享对象文件、二进制文件，都是采用 ELF 格式。这些二进制文件的格式跟加载到内存中的程序的格式是很相似的。这样有什么好处呢？它可以迅速被操作系统读取，并加载到内存中去，加载速度越快，也就相当于程序的启动速度越快。

在 ELF 格式中，代码和数据也是分开的。这样做的好处是，程序的代码部分，可以在多个进程中共享，不需要在内存里放多份。放一份，然后映射到每个进程的代码区就行了。而数据部分，则是每个进程都不一样的，所以要为每个进程加载一份。

IR中间表达式

前文通过 从 AST 生成汇编代码 的过程是比较机械的。

IR 在高级语言和汇编语言的中间，与高级语言相比，IR 丢弃了大部分高级语言的语法特征和语义特征，比如循环语句、if 语句、作用域、面向对象等等，它更像高层次的汇编语言；而相比真正的汇编语言，它又不会有那么多琐碎的、与具体硬件相关的细节。

IR看做是一种高层次的汇编语言，主要体现在：

1. 它可以使用寄存器，但寄存器的数量没有限制；
2. 控制结构也跟汇编语言比较像，比如有跳转语句，分成多个程序块，用标签来标识程序块等；
3. 使用相当于汇编指令的操作码。这些操作码可以一对一地翻译成汇编代码，但有时一个操作码会对应多个汇编指令。

1. 三地址代码，学习用途

2. LLVM 的 IR，工业级

   1. 静态单赋值（SSA），也就是每个变量（地址）最多被赋值一次，它这种特性有利于运行代码优化算法；
   2. 有更多的细节信息。比如整型变量的字长、内存对齐方式等等
   3. LLVM 汇编则带有一个类型系统。它能避免不安全的数据操作，并且有助于优化算法。
   4. 在 LLVM 汇编中可以声明全局变量、常量

int fun1(int a, int b){
    int c = 10;
    return a + b + c;
}

前端工具 Clang生成 LLVM 的汇编码clang -emit-llvm -S fun1.c -o fun1.ll

LLVM优化后的编码clang -emit-llvm -S -O2 fun1.c -o fun1.ll

define i32 @fun1(i32, i32) local_unnamed_addr #0 {
    %3 = add i32 %0, 10
    %4 = add i32 %3, %1
    ret i32 %4
}

LLVM IR对象模型

LLVM提供了代表 LLVM IR 的一组对象模型，我们只要生成这些对象，就相当于生成了 IR，比通过字符串拼接来生成 LLVM 的 IR方便。

int fun1(int a, int b){
    return a+b;
}

直接从 fun1() 函数生成 IR

Module *mod = new Module("fun1.ll", TheModule);
//函数原型
vector<Type *> argTypes(2, Type::getInt32Ty(TheContext));
FunctionType *fun1Type = FunctionType::get(Type::getInt32Ty(TheContext), //返回值是整数
    argTypes, //两个整型参数
    false);   //不是变长参数
//函数对象
Function *fun = Function::Create(fun1Type, 
    Function::ExternalLinkage,   //链接类型
    "fun1",                      //函数名称
    TheModule.get());            //所在模块
//设置参数名称
string argNames[2] = {"a", "b"};
unsigned i = 0;
for (auto &arg : fun->args()){
    arg.setName(argNames[i++]);
}
//创建一个基本块
BasicBlock *BB = BasicBlock::Create(TheContext,//上下文
            "",     //基本块名称
            fun);  //所在函数
Builder.SetInsertPoint(BB);   //设置指令的插入点
//把参数变量存到NamedValues里面备用
NamedValues.clear();
for (auto &Arg : fun->args())
    NamedValues[Arg.getName()] = &Arg;
//做加法
Value *L = NamedValues["a"];
Value *R = NamedValues["b"];
Value *addtmp = Builder.CreateAdd(L, R);
//返回值
Builder.CreateRet(addtmp);
//验证函数的正确性
verifyFunction(*fun);
Function *fun1 = codegen_fun1();     //在模块中生成Function对象
TheModule->print(errs(), nullptr);   //在终端输出IR

1. 代码优化的目标，是优化程序对计算机资源的使用。我们平常最关心的就是 CPU 资源，有时候还会有其他目标，比如代码大小、内存占用大小、磁盘访问次数、网络通讯次数等等。

2. 从代码优化的对象看，大多数的代码优化都是在 IR 上做的，而不是在前一阶段的 AST 和后一阶段汇编代码上进行的

   1. 在 AST 上也能做一些优化，但它抽象层次太高，含有的硬件架构信息太少，难以执行很多优化算法。
   2. 在汇编代码上进行优化会让算法跟机器相关，当换一个目标机器的时候，还要重新编写优化代码。

3. 优化的范围

   1. 本地优化，针对代码基本块的优化
   2. 全局优化，超越基本块的范围进行分析，我们需要用到控制流图CFG ，是一种有向图，它体现了基本块之前的指令流转关系。一个函数（或过程）里如果包含多个基本块，可以表达为一个 CFG。这种针对一个函数、基于 CFG 的优化，叫做全局优化
   3. 过程间优化，跨越函数的边界，对多个函数之间的关系进行优化

独立于机器的优化

一些优化的场景

1. 代数优化, x:=x*8 ==> x:=x<<3
2. 常数折叠, x:=20*3 ==> x:=60
3. 删除不可达的基本块, 比如 if 2<0
4. 删除公共子表达式, x:=a+b;y:=a+b ==> x:=a+b;y:=x 减少一次a+b计算
5. 拷贝传播和常数传播
6. 死代码删除
7. 内联, person.getName() 正常翻译涉及到函数调用 ==> 跳过方法的调用，直接根据对象的地址计算出 name 属性的地址，然后直接从内存取值就行

在做全局优化时，情况就要复杂一些：代码不是在一个基本块里简单地顺序执行，而可能经过控制流图（CFG）中的多条路径。如果没有循环，属于有向无环图。否则，就是一个有向有环图。我们对其进行数据流分析，便有机会去除其中的无效变量，甚至直接删掉某个分支的代码。PS：这便是让数学中的图、“半格”理论有了用武之地。

依赖于机器的优化

代码生成部分 主要考虑三点：

1. 指令的选择。同样一个功能，可以用不同的指令或指令序列来完成，而我们需要选择比较优化的方案：生成更简短的代码；从多种可能的指令中选择最优的。==> 树覆盖算法
2. 寄存器分配。每款 CPU 的寄存器都是有限的，我们要有效地利用它。==> 寄存器共享原则 ==> 图染色算法
3. 指令重排序。计算执行的次序会影响所生成的代码的效率。在不影响运行结果的情况下，我们要通过代码重排序获得更高的效率。 算法排序的关键点，是要找出代码之间的数据依赖关系 ==> 数据的依赖图，给图中的每个节点再加上两个属性：一是操作类型，因为这涉及它所需要的功能单元；二是时延属性，也就是每条指令所需的时钟周期。==> List Scheduling算法

我们通常会把 CPU 看做一个整体，把 CPU 执行指令的过程想象成，依此检票进站的过程，改变不同乘客的次序，并不会加快检票的速度。所以，我们会自然而然地认为改变顺序并不会改变总时间。但当我们进入 CPU 内部，会看到 CPU 是由多个功能部件构成的。一条指令执行时要依次用到多个功能部件，分成多个阶段，虽然每条指令是顺序执行的，但每个部件的工作完成以后，就可以服务于下一条指令。在执行指令的阶段，不同的指令也会由不同的单元负责。所以在同一时刻，不同的功能单元其实可以服务于不同的指令。

当然了，不是所有的指令都可以并行，导致无法并行的原因有几个：

1. 数据依赖约束，如果后一条指令要用到前一条指令的结果，那必须排在它后面。如果有因为使用同一个存储位置，而导致不能并行的，可以用重命名变量的方式消除，这类约束被叫做伪约束，比如

   1. 先写再写：如果指令 A 写一个寄存器或内存位置，B 也写同一个位置，就不能改变 A 和 B 的执行顺序，不过我们可以修改程序，让 A 和 B 写不同的位置。
   2. 先读后写：如果 A 必须在 B 写某个位置之前读某个位置，那么不能改变 A 和 B 的执行顺序。除非能够通过重命名让它们使用不同的位置。
2. 1. 功能部件约束，如果只有一个乘法计算器，那么一次只能执行一条乘法运算。
   2. 指令流出约束，指令流出部件一次流出 n 条指令。
   3. 寄存器约束，寄存器数量有限，指令并行时使用的寄存器不可以超标。

在我国大力促进芯片研发的背景下，如果现在有一个新的 CPU 架构，新芯片需要编译器的支持才可以。你要实现各种指令选择的算法、寄存器分配的算法、指令排序的算法来反映这款 CPU 的特点。对于这个难度颇高的任务，LLVM 的 TableGen 模块会给你提供很大的帮助。这个模块能够帮助你为某个新的 CPU 架构快速生成后端。你可以用一系列配置文件定义你的 CPU 架构的特征，比如寄存器的数量、指令集等等。一旦你定义了这些信息，TableGen 模块就能根据这些配置信息，生成各种算法，如指令选择器、指令排序器、一些优化算法等等。这就像编译器前段工具可以帮你生成词法分析器，和语法分析器一样，能够大大降低开发一个新后端的工作量，所以说，把 LLVM 研究透彻，会有助于你在这样的重大项目中发挥重要作用。

把每次只处理一个数据的指令，叫做 SISD（Single Instruction Single Data），一次只处理一个数据的计算，叫做标量计算。对应的有一类叫做 SIMD（Single Instruction Multiple Data）的指令，一次可以同时处理多个数据的计算，叫做矢量计算。它在一个寄存器里可以并排摆下 4 个、8 个甚至更多标量，构成一个矢量。比如寄存器是 256 位的，可以支持同时做 4 个 64 位数的计算。平常写的程序，编译器也会优化成，尽量使用 SIMD 指令来提高性能。

在代码里，我们会用到寄存器，并且还会用专门的寄存器分配的算法来优化寄存器。可是对于高速缓存，我们没有办法直接控制。那我们有什么办法呢？答案是提高程序的局部性（locality），这个局部性又分为两个：

1. 时间局部性。一个数据一旦被加载到高速缓存甚至寄存器，我们后序的代码都能集中访问这个数据，别等着这个数据失效了再访问，那就又需要从低级别的存储中加载一次。
2. 空间局部性。当我们访问了一条数据之后，很可能马上访问跟这个数据挨着的其他数据。CPU 在一次读入数据的时候，会把相邻的数据都加载到高速缓存，这样会增加后面代码在高速缓存中命中的概率。

提高局部性这件事情，更多的是程序员的责任，编译器能做的事情不多。不过，有一种编译优化技术，叫做循环互换优化（loop interchange optimization）可以让程序更好地利用高速缓存和寄存器。

即时编译JIT

JIT Compilation 的全称为 “Just-In-Time Compilation”，翻译过来为“即时编译”。其最显著的特征是代码的编译过程发生在程序的执行期间，而非执行之前。

传统的 JIT 编译器在实际动态生成机器码前，会首先对原始代码或其相应的 IR 中间代码进行一系列的分析（profiling）。通过这些分析过程，编译器能够找到可以通过 JIT 编译进行性能优化的“关键代码路径”。这里的取舍重点在于：对这些代码进行运行时优化而得到的性能提升收益，需要高于进行优化时所产生的性能开销。

即时编译JIT的场景之一——提升系统性能：在第一次编译时，你可以让 LLVM，仅运行少量的优化算法，这样编译速度比较快，马上就可以运行。而对于被多次调用的函数，你可以让 LLVM 执行更多的优化算法，生成更优化版本的目标代码。而运行时所收集的某些信息，可以作为某些优化算法的输入，像 Java 和 JavaScript 都带有这种多次生成目标代码的功能。PS：代码最终是一段机器码，如果某一个部分被经常使用，那么这部分机器码可以被拎出来进行深度优化替换掉原来的机器码。这个特点应用到 rpc 就是：如果让我们刚启动的应用就承担像停机前一样的流量，这会使应用在启动之初就处于高负载状态，从而导致调用方过来的请求可能出现大面积超时，进而对线上业务产生损害行为，所以要启动预热。

IT Compilation：一种特殊的程序执行方式其流程可大致总结为（不同文章例子不同，仅辅助理解）：

1. 读入源代码（包含 ASCII 形式的指令序列）；
2. 调用 bfJITCompile 函数，将源代码编译为机器码；这些生成的二进制机器码将被存放在一个 std::vector 对象中以备后续使用。
3. 调用 allocateExecMem 函数，将机器码动态分配在可执行的内存段上；

    uint8_t* allocateExecMem(size_t size) {
        // mmap 函数是一个由 C 标准库提供的系统调用，通过该函数，我们可以在当前进程的 VAS（Virtual Address Space）中创建一个映射。这个映射可以指向一个具体的文件、或者是一个匿名空间。
        return static_cast<uint8_t*>(
            mmap(
            NULL,
            size, 
            PROT_READ | PROT_WRITE | PROT_EXEC,     // PROT_EXEC将这段申请的匿名内存空间标记为“可执行”
            MAP_PRIVATE | MAP_ANONYMOUS, 
            -1,
            0));
    }
   

4. 调用 VM::exec 函数，通过 OSR 转移执行流程；将程序的指令执行流程转移至这段内存的起始位置处
5. 代码执行完毕后再次转移回主流程；
6. 执行一些清理善后工作。

动态申请内存，加载目标代码到内存，并赋予内存可执行的权限。jit.cpp

/*
 * 机器码，对应下面函数的功能：
 * int foo(int a){
 *     return a + 2;
 * }
 */
uint8_t machine_code[] = {
        0x55, 0x48, 0x89, 0xe5,
        0x8d, 0x47, 0x02, 0x5d, 0xc3
};
// 执行动态生成的机器码。
int main(int argc, char **argv) {
    //分配一块内存，设置权限为读和写
    void *mem = mmap(NULL, sizeof(machine_code), PROT_READ | PROT_WRITE,
                     MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
    if (mem == MAP_FAILED) {
        perror("mmap");
        return 1;
    }
    //把机器码写到刚才的内存中
    memcpy(mem, machine_code, sizeof(machine_code));
    //把这块内存的权限改为读和执行。从安全角度出发，操作系统给每个内存区域，设置了不同的权限，代码区具备可执行权限，所以我们才能运行程序。
    if (mprotect(mem, sizeof(machine_code), PROT_READ | PROT_EXEC) == -1) {
        perror("mprotect");
        return 2;
    }
    //用一个函数指针指向这块内存，并执行它
    int32_t(*fn)(int32_t) = (int32_t(*)(int32_t)) mem;
    int32_t result = fn(1);
    printf("result = %d\n", result);
    //释放这块内存
    if (munmap(mem, sizeof(machine_code)) == -1) {
        perror("munmap");
        return 3;
    }
    return 0;
}

从某种意义上看，从计算机诞生到现在，我们编写程序的方式一直没有太大的进步。最早，是通过在纸带或卡片上打孔，来写程序；后来产生了汇编语言和高级语言。但是，写程序的本质没有变化，我们只是在用更高级的方式打孔。

云计算改变编程模式

当一个软件服务 1 万个用户的时候，增加一个功能可能需要 100 人天的话；针对服务于 1 百万用户的系统，增加同样的功能，可能需要几千到上万人天。同样的，如果功能不变，只是用户规模增加，你同样要花费很多人天来修改系统。那么你可以看出，整体的复杂性是多个因素相乘的结果，而不是简单相加。云计算最早承诺，当我们需要更多计算资源的时候，简单增加一下就行了。然而，现有软件的架构，其实离这个目标还很远。那有没有可能把这些复杂性解耦，使得复杂性的增长变成线性或多项式级别（这里是借助算法复杂性的理论）的呢？

1. 基础设施的复杂性，队列、分库分表、负载均衡、服务注册发现、监控等
2. 部署复杂性，代码、分支、编译、测试、配置、灰度发布、回滚等
3. API 的复杂性，能否让 API 调用跟普通语言的函数调用一样简单

编程环境会逐渐跟云平台结合起来，让 API 调用跟普通语言的函数调用一样简单，让开发平台来处理上述复杂性。根据计算机语言的发展规律，我们总是会想办法建立更高的抽象层次，把复杂性隐藏在下层。就像高级语言隐藏了寄存器和内存管理的复杂性一样。要求新的编程语言从更高的一个抽象层次上，做编译、转换和优化。我们只需要编写业务逻辑就可以了，当应用规模扩大时，真的只需要增加计算资源就行了；当应用需求变化时，也只需要修改业务逻辑，而不会引起技术细节上的很多工作量。能解决这些问题的软件，就是云原生的编程语言及其基础设施。

还可能实现编程环境本身的云化，电脑只负责代码编辑的工作，代码本身放在云上，编译过程以及所需的类库也放在云上。

编译原理要把计算机组成、数据结构、算法、操作系统，以及离散数学中的某些知识都用上。

1. 指令选择、寄存器分配和指令排序，都是NP Complete的。这个时候，如果提前已经知道什么是NP Complete，那么马上就对这类算法有概念，也马上想到可以用什么样的方式来对待这类问题。
2. 编译原理中很多算法都是基于树和图的，所以对这两个数据结构的理解也会有帮助。
3. 至于计算机组成原理，跟后端技术的关联很密切。
4. 程序运行时的环境，内存管理等内容，则跟操作系统有关。

编程语言是自举的，指的是说，我们能用自己写出来的程序编译自己。但是自举，并不要求这门语言的第一个编译器就是用自己写的。比如，这里说到的 Go，先是有了 Go 语言，我们通过 C++ 写了编译器 A。然后呢，我们就可以用这个编译器 A，来编译 Go 语言的程序。接着，我们再用 Go 语言写一个编译器程序 B，然后用 A 去编译 B，就得到了 Go 语言写好的编译器的可执行文件了。这个之后，我们就可以一直用 B 来编译未来的 Go 语言程序，这也就实现了所谓的自举了。所以，即使是自举，也通常是先有了别的语言写好的编译器，然后再用自己来写自己语言的编译器。