XChy's Blog

本章博客将介绍一种消除程序代码冗余的编译器代码优化技术 --- 懒惰代码移动算法

什么是冗余消除

冗余消除就是要尽量减少表达式求值的次数，避免形如\(x+y\)的表达式在之后的代码中多次计算，影响性能。

冗余的来源主要有以下三种：

1. 公共子表达式 (Common Expression)
2. 循环不变表达式 (Loop Invariant)
3. 部分冗余表达式 (Partial Redundancy Expression)

2023.9.21修改：LLVM的patch以及完全迁移到Github PR上，本篇文章有关Phabricator的操作已经out-of-dated。

为什么要参与LLVM的开源？

由于一直以来对编译器后端特别感兴趣，又曾用LLVM作为后端为自己的语言进行AOT的编译， 我对LLVM的内部十分好奇，于是想通过为LLVM贡献代码的方式了解LLVM，并了解编译器优化的流程。

于是我参考了一位LLVM Member的文章: How to contribute to llvm?

以下则是我从编译到提交patch的全流程。

编译

要为LLVM贡献代码，那首先能在本地编译LLVM库。

那么我们首先要clone LLVM的git仓库，或者自己fork了llvm-project后再clone到本地。二者区别不大，我按照github的开源习惯选了后者。

clone完之后我们开始编译，这边要注意的是：由于计算机编译速度的限制，我们一边建议进行Release编译。否则一次编译链接要长达几小时的时间。 以下是cmake的模板：

1
2
3
4
5
6
7

cmake -GNinja -Bbuild -Hllvm \
    -DLLVM_ENABLE_PROJECTS="clang" \
    -DLLVM_TARGETS_TO_BUILD="all" \
    -DCMAKE_BUILD_TYPE=Release \
    -DLLVM_ENABLE_ASSERTIONS=true \
    -DLLVM_CCACHE_BUILD=true \
    -DLLVM_USE_LINKER=lld

其中Debug可通过-debug flag来进行，你可以在对应的代码位置用errs() << something进行输出。

而ninja的编译速度相对较快，所以以下有构建和测试的shell：

1
2
3
4
5
6
7
8
9

# Build LLVM
ninja -Cbuild

# Run all LLVM tests
ninja -Cbuild check-llvm

# Run tests in a specific directory.
# -v will print additional information for failures.
build/bin/llvm-lit -v llvm/test/Transforms/InstCombine

选Issue

由于我是LLVM领域的新手，不太可能一上来就砍大龙，所以我挑了个简单的任务。

Waiting to complete

参考了 Java 中的对象模型 我决定把 XSharp 中的 数组(Array) 的模型设计为以下形式： [ 8 bytes ] object header as length of array [ 4 or 8 bytes ] pointer p to a sequential memory (for elements)

故对以下 XSharp 代码

1

i64[] a = new i64[100]

在 64 位系统上，我们将会在栈上分配 8 + 4 字节的内存，由于 align 的要求我们再加上 4 字节的 padding， 一共 16 字节，并为 100 个 i64 元素在堆上分配 100 * 8 字节的内存

而每次执行a[i]这样的操作时，我们会对取 a 的地址 并加上 8，得到指向对应连续内存的指针 p ， 再对 p + i _ sizeof(i64) 对应的地址指向读/写操作

对应到 LLVM 的 CodeGen，我们则需要定义形如StructType<i64,PointerTo<xxx>>这样的类型， 并用getelementptr inbound和getelementptr指令获得某个元素的地址

这样设计的好处则是将长度 length 放到栈上，不需要在堆分配和取元素时进行额外的计算， 也不需要 align 来保证 cache friendly，同时也方便优化。

而相较于 C 语言风格的数组，我们的数组主体始终放在堆上，故内存的管理不够精细， 但经过了封装，其易用性更胜一筹，基于这些限制，其优化也更容易实现。

手工实现 Parser 常用递归下降法(Recusive Descent)，XSharp 的 Parser 也采用了递归下降的主体结构。

一般来说递归下降法适用于自上而下的结构，更容易解析开头有标识符的语言，如：

1
2
3

if () {}
while () {}
class {}

但也由于同样的原因，递归下降法处理表达式非常吃力。Parser 在读到表达式开头的时候，无法知道自己身处哪种表达式之中，这是因为操作符往往在表达式的中间位置（甚至结尾），比如加法运算的+、函数调用的()。为了能自顶向下地解析表达式，你需要将每一种操作符 优先级(priority) 都单独作为一个层级，为其编写解析函数，并手动处理 结合性(associativity) ，因此解析函数会比较多、比较复杂。

所以在重构 XSharp 的 Parser 时，我选择了 Pratt Parsing 作为表达式的算法

笔者参考了 Pratt Parsing 知乎 和 Pratt Parsing Rust 进行了有关代码的重构

核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

ASTNode* lhs = operand();

while (true) {
    if (isStopwords(current, stopwords)) return lhs;

    if (current->type != Operator)
        throw XSharpError("No operator matched after operand");

    if (priority(current->value) <= ctxPriority) break;

    XString op = current->value;

    forward();
    auto right_binding_power =
        assoc(op) == LeftToRight ? priority(op) : priority(op) - 1;
    auto rhs = expression(stopwords, right_binding_power);

    auto new_lhs = new BinaryOperatorNode;
    new_lhs->setOperatorStr(op);
    new_lhs->setLeft(lhs);
    new_lhs->setRight(rhs);
    lhs = new_lhs;
}

return lhs;

为什么需要 Mutable Variable?

由于 LLVM 内部优化等原因，LLVM IR 中的寄存器必须遵循SSA原则，即每个寄存器在 SSA 中仅被赋值一次。

但由于 XSharp 需要支持同个变量的多次引用，我们不能直接使用寄存器作为变量的存储单元。

幸运的是，LLVM 并不强制要求栈上的变量保持SSA，所以我们可以考虑将所有变量存放在栈上，

然后再通过 LLVM 提供的 Mem2Reg 工具或者 Pass 进行栈上内存的数据流分析，尽可能地将栈上的变量转换至寄存器上。

原文档在此:LLVM Mutable Variable

而针对 XSharp,我们可以写出如下代码

在使用 Neovim 进行 C/C++的开发时，我们常常使用 clangd 作为 lsp 提供语法高亮/重构等语言服务

其中 clangd 根据自动推断宏的功能也是十分有效，搭配CMake可以达到更加好的效果(如支持 CMake 内置宏，支持自动 include CMake 配置的头文件)

下面提供简要的集成 clangd 与 cmake 的方法

一般来说clangd可以自动识别CMake生成的compile_commands.json来进行头文件的识别与宏的分析

但 compile_commands.json 不会自动生产，故我们可以通过以下命令实现 compile_commands 的自动生产

1

cmake . -G -DCMAKE_EXPORT_COMPILE_COMMANDS=ON

其中 -DCMAKE_EXPORT_COMPILE_COMMANDS=ON 是用于导出编译命令的 flag

故我常常会在项目目录下建立一个 build.sh 来构建项目:

1
2

cmake . -G -DCMAKE_EXPORT_COMPILE_COMMANDS=ON
make

构建时只需要输入 build.sh

一个好的编程语言需要有一个好的类型系统

笔者计划为 XSharp 开发一个静态且可拓展的类型系统，其中支持基本类型(如i32,i64)，数组，函数，Closure，类等类型及其复合

而复合的需求就意味着类型必须是多层次，且多种类型的形式，而树这种数据结构正好符合要求

于是TypeNode出现了

我们社设计具体类型的类型相关设置，从而构建不同的类型结构，如 ArrayType 有 elementType 的子类型，FunctionType 有 paramTypes 的子节点列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class TypeNode;

//arrayDimension指的是数组类型的维度
//而elementType则是元素类型的TypeNode指针
struct ArrayType {
    uint arrayDimension;
    TypeNode* elementType;
};

//paramTypes指的是参数的类型
//returnValueType则是返回值的类型
struct FunctionType {
    std::vector<TypeNode*> paramTypes;
    TypeNode* returnValueType;
};

使用 Lua 配置 Neovim，并设置自己的 workflow

结合命令行工具

我在编码时常常有使用 git 的需求，但又不想总是在命令行中敲命令

于是我利用与 ToggleTerm 把命令行工具 lazygit 嵌入至 Neovim 中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

local Terminal = require('toggleterm.terminal').Terminal

local lazygit = Terminal:new({ cmd = "lazygit", direction = 'float', hidden = true })
local top = Terminal:new({ cmd = "top", direction = 'float', hidden = true })


-- lazygit
vim.api.nvim_create_user_command("LazyGit",
    function()
        lazygit:toggle()
    end,
    { nargs = 0 })

-- top
vim.api.nvim_create_user_command("Top",
    function()
        top:toggle()
    end,
    { nargs = 0 })

作为大一新生,每天都要为了数学作业焦头烂额，为了解决这个问题，聪慧的我想到了利用数学工具 Mathematica 来解决这个问题

于是我先用南大邮箱获得了 mma，并在 Ubuntu 上安装了 mma 及其依赖

下面记录有关求极限，求微分，以及求积分的几个模板