また夏を追う

最近的笔记

编译原理复习

✏️ 🔧 25 min read

预处理器

这是一个特殊的部分，正常来说他不算在常规的编译范畴内。在源程序被编译器处理之前, 预处理器首先对源程序中的宏进行处理，这些宏是指由预处理命令书写的部分。

预处理命令由#(hash 字符)开头, 它独占一行, #之前只能是空白符. 以#开头的语句就是预处理命令, 不以#开头的语句为 C 中的代码行。

常见的预处理器指令及其作用：

  1. #include 包含一个源代码文件，预处理器做的事情只是简单的去寻找包含的文件，然后复制粘贴到这个地方来，注意 #include是可以包含 .cc, .c文件的，并不是只能包含 .hh, .h文件

  2. #pragma设定编译器的状态或者是指示编译器完成一些特定的动作，它可以用于例如控制编译器的警告信息、优化选项、链接选项等等，用法如下：

    • #pragma GCC optimize("O2") 可以用于告诉 GCC 编译器使用 O2 级别的优化选项（在 OJ 交题时可能会用到，但有些 OJ 会禁止提交包含 #pragma的代码）

    • #pragma once 用于防止头文件被重复包含。它的作用类似于传统的头文件保护宏（例如 #ifndef 和 #define），但是更加简洁和高效。当编译器遇到 #pragma once 指令时，它会检查当前文件是否已经被包含，如果已经被包含，则不会再次包含。需要注意的是，#pragma once 是一个非标准的指令，但是被大多数编译器所支持

    • #pragma pack(n) 可以用于告诉编译器按照 n 字节对齐结构体。

  3. #define 定义一些宏，例如 #define HELLO "HELLO"，预处理器对于这条指令所做的操作就是将后续 C 代码中的所有 HELLO 替换为 `“HELLO”“

  4. #ifdef 用于判断某个宏是否已经被定义。如果该宏已经被定义，则编译器会编译 #ifdef 和 #endif 之间的代码；否则，编译器会忽略这段代码。需要注意的是，#ifdef 和 #ifndef 是一对相反的条件编译指令，它们的作用是相同的，只是判断条件相反。这条指令通常被用来决定是否要产生调试信息，例如：

    #ifndef DEBUG
    #define DEBUG
    #endif
    

    #ifdef DEBUG
    

    // 生成调试信息的代码块
    

    #endif

通过预处理器处理 .c, .cc文件，变为 .i 文件后，进入正式的编译阶段，我们可以通过：

Terminal window
gcc -E -C hello.c -o hello.i

-C 可以让预处理器保留注释，让文件不至于太难懂，例如一个简单的 hello-world.c 文件：

预处理后可以达到 2346 行，main 函数部分变为：

自举 （bootstrap）

编译器的自举意思是，某个语言的编译器是用这个语言写出来的。听起来似乎不可思议，但是 clang 确实是使用 C++ 完成的。

编译器自举一般都是编译器开发的一个里程碑事件，例如Pascal编译器，其第一版编译器是用 Fortran写的，而这也是常见的编译器自举过程的几乎必走的一条路，即最开始使用 X 语言（如Fortran）实现 Y 语言（如Pascal）的编译器，即解决鸡与蛋的问题，之后成熟以后，就可以完全使用已经生成好的编译器来编译出我们的新编译器。

以 Go 为例：Go在 1.0 ～ 1.4 阶段都是使用 C 写的编译器来编译，在 Go 1.5 后完成了自举。自举的过程举例如下：

  1. 首先，通过 C 写了一个最基础的编译器，假定名称为 go compiler 1.0
  2. 我们通过 Go来重写编译的逻辑，得到一个项目，然后使用 go compiler 1.0 来编译这个项目，就得到了一个自举的编译器 go compiler 2.0
  3. 之后，我们就可以通过这个编译器来编译项目，甚至是编译新一代的编译器

能做到这一点的原因是，编译器实际上也只是一个程序而言，这是一个接受一个 ASCII 码文件，然后翻译成机器码文件的程序。

自举的意义在于我们对编译器输出的目标代码的优化，同时可以作为编译器的优化。

前端

前端部分目前已经收敛了，少有优化能做。

其流程一般为：

  1. 词法分析，生成 Token，流向后面的处理

  2. 语法分析，通过解析 Token，根据设计的文法，得到 AST

  3. 语义分析，在前面两步，我们已经构造出了 “符号表”，这里，我们使用 AST 与符号表中的信息来检查源程序是否和语言定义的语义一致，同时，这里也会收集类型信息，将这些信息存放在 AST 与符号表中。检查的一致性包括：

    • 检查标识符的类型和作用域是否正确。

    • 检查表达式的类型是否正确。

    • 检查函数调用的参数是否正确。

    • 检查类型转换是否正确。

    • 检查语句的语义是否正确。

符号表是编译器中的一个重要数据结构，它用于存储程序中的标识符（如变量名、函数名等）以及它们的属性（如类型、作用域等）

需要掌握的内容

词法分析中的：正则表达，NFA 转 DFA

语法分析中的：递归下降，LL(1)，SLR，LALR

语义分析中的：类型检查

关于这部分可以看 编译原理笔记

一些工具

词法分析器：lex 或 flex，基于正则表达式（DFA）的词法分析器

语法分析器：yacc 或 bison，生成的文法为 LALR(1) 文法

LALR 或者说所有的 LR文法都不适合手写，所有教科书都会说明这一点，具体的原因可以看 为什么 LR 文法不适合手写

现代编译器策略

对于 gcc 与 clang 而言，都采取了手写词法分析器与语法分析器的方式，词法分析并没太多的更改，依然是基于正则表达式的匹配方式，但语法分析器都采取了 递归下降 策略。

对于手写语法分析器是否有必要有很大的争论，有人提出可以把文法生成器（bison）中的默认生成文法更改为 GLR，一个使用 GLR 的分析器可以参考这篇文章

GLR分析器可以处理上下文无关文法中的任意语法结构，包括二义性文法和无法用 LR 分析器处理的文法。GLR分析器使用了一种称为“图驱动”的技术，将输入的语法树转换为一个图，并在图上进行分析。

其基本思想是，通过在分析过程中采用穷举方法，对输入语句在所有的可能路径上进行分析，从而实现了对语句的识别与翻译。

显然这种做法的运行时间具有不确定性，一般情况下GLR一产生歧义处理就会增加内存消耗和占用多核心，最后效率总是不如手写，所以知名通用语言很少用GLR来解析。相反，做DSL（domain-specific language）解析，用GLR就比较好，语法规则要求不高，因为支持所有上下文无关语法，对效率又不是要求很高，所以这类情况会用语法生成工具比较多。

中端（也可以属于前端部分）

  1. 中间代码生成
  2. 运行时环境

中间代码生成

运行时环境

主题为：

  1. 存储管理：栈分配、堆管理、垃圾回收
  2. 对变量、数据的访问

存储管理

分为栈分配与堆管理

栈分配

栈分配需要关注的问题：

  1. 活动树
  2. 活动记录
  3. 调用代码序列
  4. 栈中的变长数据

程序运行的所有过程活动可以用树表示，每个结点对应于一个过程活动，根结点对应于main过程的活动 ，过程p的某次活动对应的结点的所有子结点：

  1. 表示此次活动所调用的各个过程活动
  2. 从左向右，表示调用的先后顺序

这棵树又称为调用树，例如下图（并未画完），一个快速排序的调用树：

过程调用 (返回) 序列和活动 树的前序 (后序) 遍历对应

堆管理

堆空间的管理与 CS: APP中内存的管理类似

分配策略为：

  1. Best-fit ：总是将请求的内存分配在满足请求的最小的窗口中
  2. First-fit ：总是将对象放置在第一个能够容纳请求的窗口中

回收策略：当回收一个块时，可以把这个块和相邻的块接合起来，构成更大的块，然而这两种都属于手动管理内存，存在内存泄漏，悬挂指针等内存问题

因此，我们提出了 垃圾回收 来解决这些问题。

垃圾回收

定义：自动回收不可达数据的机制

设计的基本要求：语言必须是类型安全的，也就是说保证回收器能够知道数据元素是否为一个指向某内存块的指针，因此 C/C++不支持垃圾回收

性能目标：

  1. 总体运行时间：不显著增加应用程序的总运行时间
  2. 停顿时间：当垃圾回收机制启动时，可能引起应用程序的停顿，这个停顿应该比较短
  3. 空间使用：最大限度地利用可用内存
  4. 程序局部性：改善空间局部性和时间局部性

Info

关于可达性

可达性就是指一个存储块可以被程序访问到

根集：不需要指针解引用就可以直接访问的数据，例如 Java 中的静态成员、栈中变量

可达性 ：

  1. 根集的成员都是可达的
  2. 对于任意一个对象，如果指向它的一个指针被保存在可达对象的某字段或数组元素中，那么这个对象也是可达的

因此一旦一个对象变得不可达，它就不会再变成可达的

垃圾回收的方法：

  1. 关注不可达： 跟踪相关操作，捕获对象变得不可达的时刻，回收对象占用的空间
  2. 关注可达：在需要时，标记出所有可达对象，回收其它对象

垃圾回收器的种类：

  1. 基于引用计数的垃圾回收：

    1. 每个对象有一个用于存放引用计数的字段，并按如下方式维护

      1. 对象分配：引用计数设为 1
      2. 参数传递：引用计数加 1
      3. 引用赋值：u = v，u 指向的对象引用减 1，v 指向的对象引用加 1
      4. 函数返回：局部变量指向对象的引用计数减 1

    2. 如果一个对象的引用计数为 0，在删除对象之前，此对象中各个指针所指对象的引用计数减 1

    3. 特点：开销较大，但不会引起停顿

    4. 缺陷：无法解决循环引用，例如下图，这三个对象没有来自外部的指针，应该都是垃圾，然而三个对象的引用计数都大于 0（如果熟悉 C++的 weak_ptr应该能很快理解）

  2. 标记-清扫式垃圾回收

    1. 特点 : 一种直接的、全面停顿的算法

    2. 做法 : 分为两个阶段

      1. 标记：从根集开始，跟踪并标记出所有的可达对象
      2. 清扫：遍历整个堆区，释放不可达对象

      如果把数据对象看作结点，引用看作有向边，那么标记的过程实际上是从根集开始的遍历过程

    3. 算法描述如下

      在算法开始前，我们的假设是 所有已分配对象都是不可达状态

      注意在清扫时，使用了 clear_vis，也就是将 o标记为不可达，用于满足下一次标记的前置条件。

      // 标记(bfs)
      auto Unscanned = list; // 根集引用的对象的列表（或者叫集合，保证每个对象唯一出现）
      while(!Unscanned.empty()){
        auto o = Unscanned.front(); // 取出集合中的对象o
        Unscanned.pop();
        // 对于在 o 中引用的每个对象 ref_in_o
        for(auto &ref_in_o : getref(o)){
          if(!is_vis(ref_in_o)){
            set_vis(ref_in_o);
            Unscanned.push(ref_in_o);
          }
        }
      }
      // 清扫
      auto free = Unscanned.copy();
      for(auto& o: list){
        if(!is_vis(o))
          free.push(o);
        else
          clear_vis(o);
      }

​ 优点： 实现简单，无需移动对象 (修改引用地址)

​ 缺点 ：效率堪忧，清扫阶段总是需要遍历所有内存，易产生内存碎片

  1. 标记-复制式垃圾回收

    1. 目标：

      • 只处理可达对象 (减少回收时间)
      • 将可达对象安排到一起 (减少内存碎片)

    2. 做法：

      1. 堆空间被分为两个半区
      2. 应用程序在某个半区内分配存储，当充满这个半区时， 开始垃圾回收
      3. 回收时，复制可达对象到另一个半区 (需修改引用地址)
      4. 回收完成后，两个半区角色对调

      优点 ：只处理可达对象 (减少回收时间) ，将可达对象安排到一起 (减少内存碎片)

      缺点 ：一半预留区域的内存无法使用

  2. 标记-整理式垃圾回收

    1. 定义：对可达对象进行重定位可以消除存储碎片

      • 与标记-复制法将对象移动到预留另一半区不同，标记整理法把可达对象移动到堆区的一端，另一端则是空闲空间

      • 空闲空间合并成单一块，提高分配内存时的效率

    2. 过程：

      1. 标记 (与前述算法相同)
      2. 计算新位置
      3. 移动并设置新的引用

      1. 伪代码：

        // 标记(bfs)
        auto Unscanned = list; // 根集引用的对象的列表（或者叫集合，保证每个对象唯一出现）
        while(!Unscanned.empty()){
          auto o = Unscanned.front(); // 取出集合中的对象o
          Unscanned.pop();
          // 对于在 o 中引用的每个对象 ref_in_o
          for(auto &ref_in_o : getref(o)){
            if(!is_vis(ref_in_o)){
              set_vis(ref_in_o);
              Unscanned.push(ref_in_o);
            }
          }
        }
        // 计算新位置
        auto free代式垃圾回收 = get_heap_begin_addr();
        for(auto& o: get_all_object()){
          if(is_vis(o)){
            NewLocation.insert({o, free});
            free += sizeof(o);
          }
        }
        // 移动并设置新的引用
        for(auto& o: get_all_object()){
          if(is_vis(o)){
            for(auto& ref_in_o: getref(o)){
              ref_in_o.addr = NewLocation.find(ref_in_o)->second;
            }
            memcpy(&o, NewLocation.find(o)->second);
          }
        }

Info

分代式垃圾回收

根据对象生存周期特征进行垃圾回收

  • 大多数对象刚创建不久后就不再使用 (短命)
  • 存在时间越长的对象，通常被回收的几率越小 (命硬)

根据生存周期，对对象分代管理

  • 新创建的对象均放入年轻代区域 (从幼年期开始)
  • 年轻代空间不足时，对该区域执行回收 (标记-复制)
  • 熬过回收的对象移入下一区域 (进化)
  • 老年代空间不足时，对该区域执行回收 (标记-整理)

后端

后端优化：

  1. 常量折叠(Constant Folding)
  2. 常量传播(Constant Propagation)
  3. 死代码消除(Dead Code Elimination)
  4. 循环展开(Loop Unrolling)
  5. 函数内联(Function Inlining)
  6. 公共子表达式消除(Common Subexpression Elimination)
  7. 强度削弱(Strength Reduction)
  8. 指令调度(Instruction Scheduling)
  9. 分支预测优化(Branch Prediction Optimization)
  10. 尾递归(Tail Recursion Optimization)
  11. 逃逸分析(Escape Analysis)
  12. 向量化(Vectorzation)
  13. 无关代码移动(Code Motion)

深度学习编译器

AI 编译器入门

请看：

AI 编译器前端优化

AI 编译器后端优化

PyTorch 2.0 的编译流程

可以参考 PyTorch 编译简介

🕸️ 关系图谱

反向链接