MLIR编译框架的使用与探索

资源下载地址：https://download.csdn.net/download/sheziqiong/86784192
资源下载地址：https://download.csdn.net/download/sheziqiong/86784192

MLIR 编译框架的使用与探索

实验环境

• 虚拟机软件：VirtualBox 6.1.32
• 操作系统：Ubuntu 20.04
• 内核版本：Linux kernel 5.13.0-35-generic
• 软件：
  • Git 2.25.1
  • cmake 3.16.3
  • clang 10.0.0-4ubuntu1
    • Target: x86_64-pc-linux-gnu
    • Thread model: posix
  • lld
  • ninja 1.10.0

实验过程

构建实验环境

前置工具

• Git，cmake，clang，lld，ninja
• 在 /home/username 目录下安装
  • 我的 username 为 thousanrance 。

sudo apt install git
sudo apt install cmake
sudo apt-get install clang lld
sudo apt install ninja-build
1
2
3
4

安装 MLIR

• 下载 MLIR 项目文件

git clone https://github.com/Jason048/llvm-project.git
mkdir llvm-project/build
cd llvm-project/build
cmake -G Ninja ../llvm \
   -DLLVM_ENABLE_PROJECTS=mlir \
   -DLLVM_BUILD_EXAMPLES=ON \
   -DLLVM_TARGETS_TO_BUILD="X86;NVPTX;AMDGPU" \
   -DCMAKE_BUILD_TYPE=Release \
   -DLLVM_ENABLE_ASSERTIONS=ON \
   -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++ -DLLVM_ENABLE_LLD=ON
1
2
3
4
5
6
7
8
9
10

• 编译 MLIR

cmake --build . --target check-mlir
1

安装 tiny_project

• 下载 tiny_project 项目文件

git clone https://github.com/Jason048/tiny_project.git
mkdir build  
cd build

# 将下面的三行命令在build目录下执行
LLVM_DIR=/home/username/llvm-project/build/lib/cmake/llvm \
MLIR_DIR=/home/username/llvm-project/build/lib/cmake/mlir \
cmake -G Ninja ..
1
2
3
4
5
6
7
8

基础部分：词法分析与语法分析

词法分析器

• 对关键词和变量名进行分析。

• 文件路径：/tiny_project/tiny/include/tiny/Lexer.h

• 在 Lexer.h 搜索 “TODO”，可以看到需要补充的代码位置。 实现以下功能：

  • 能够识别“return”、“def”和“var”三个关键字
  • 按照如下要求识别变量名：
    • 变量名以字母开头
    • 变量名由字母、数字和下划线组成
    • 变量名中有数字时，数字应该位于变量名末尾
    • 例如：有效的变量名可以是 a123, b_4, placeholder 等。

具体实现

• 在枚举类型 Token 中添加 tok_invalid_identifier 来代表不合法的变量名。（已用 //basic part 注释）

enum Token : int {
  tok_semicolon = ';',
  tok_parenthese_open = '(',
  tok_parenthese_close = ')',
  tok_bracket_open = '{',
  tok_bracket_close = '}',
  tok_sbracket_open = '[',
  tok_sbracket_close = ']',

  tok_eof = -1,

  // commands
  tok_return = -2,
  tok_var = -3,
  tok_def = -4,
  tok_struct = -5,

  // primary
  tok_identifier = -6,
  tok_number = -7,
  
  //basic part
  tok_invalid_identifier = -8,
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• TODO：识别变量名与关键字
  • 读入第一个字母【isalpha()】时开始进行变量名与关键字的识别。
  • identifierStr 用来记录这个关键字或变量名。
  • 接下来读入的字符只要是字母或者数字【isalnum()】，就拼在 identifierStr 后。
  • 布尔型变量 containDigit 用来记录 identifierStr 里是否含有数字；invalid 用来记录变量名是否不合法。两者都初始化为 false。
  • 在读入字符的过程中，如果读入的字符是数字，将 containDigit 置为 true。
  • 在读入字符的过程中，如果 containDigit 为 true，且新读入的字符是字母或下划线，则将 invalid 置为 true。因为这意味着在数字之后又出现了字母或者下划线，说明数字没有位于变量名末尾，是不合法的变量名。
  • 如果读到不是字母、数字、下划线的字符，则结束继续读入字符，对当前已经读入的字符串进行判断。
  • 如果是关键字 return、var、def 中的某一个，则返回其对应的枚举类型。
  • 如果关键字，则为变量名。检查 invalid，返回 合法 / 非法 变量名对应的枚举类型。

语法分析器

• 基础部分：词法分析与语法分析

• 文件路径：/tiny_project/tiny/include/tiny/Parser.h

• 在 Parser.h 搜索"TODO"，可以看到需要补充的代码位置。 实现以下功能：

  • 语法变量必须以“var”开头，后面为变量名及类型，最后为变量的初始化
  • 语法分析器已支持以下两种初始化形式，以一个二维矩阵为例：
    • var a = [[1, 2, 3], [4, 5, 6]]
    • var a<2,3> = [1, 2, 3, 4, 5, 6]
  • 需要额外支持第三种新的形式：
    • var a[2][3]= [1, 2, 3, 4, 5, 6]

具体实现

• TODO：额外支持第三种新的形式。

  • 如果当前 Token 不是 ‘<’ 或 ‘[’ 则提示错误信息。
  • 如果是，则分情况讨论。
  • 如果是 ‘<’，照搬原代码。
  • 如果是 ‘[’，与上一种情况不同的地方是，分隔两个数字的 Token 不是一个逗号 ‘,’，而是两个 Token —— ‘]’ 和 ‘[’ 。所以在读入第一个 ‘]’ 后，还要再尝试读入一个 Token，并且希望它是 ‘[’ ，所以要用布尔变量 ismedium（初始化为 true）记录读入的 ‘]’ 是否是在数字中间。只有 ismedium 为 true 时，才会尝试读入下一个 Token。
  • 读入第一个 ‘]’ 后会将 ismedium 置为 false，当再次读到 ‘]’ 时，因为 ismedium 为 flase，所以不会再尝试读入下一个 Token，而是直接跳出循环，去进行 type 的结尾检查，因为实际上这个 ‘]’ 是 type 的结尾。

• TODO：语法变量必须以“var”开头，后面为变量名及类型，最后为变量的初始化

  • 检查当前 Token 是否是关键字 var 对应的枚举类型，如果不是就输出错误信息，如果是就读入下一个 Token。
  • 已经确定以"var" 开头正确，检查当前 Token 是否是合法变量名 identifier 对应的枚举类型，如果不是就输出错误信息。

• TODO：额外支持第三种新的形式。

  • 已经确定以“var”开头正确，后接变量名正确，开始检查类型。
  • 如果当前 Token 是 ‘<’ 或 ‘[’，则调用 parseType()函数（即上一个函数）对类型进行语法分析。

// Parse a variable declaration, 
// 1. it starts with a `var` keyword, followed by a variable name and initialization
// 2. Two methods of initialization have been supported:
//    (1) var a = [[1, 2, 3], [4, 5, 6]];
//    (2) var a <2,3> = [1, 2, 3, 4, 5, 6];
// You need to support the third method:
//    (3) var a [2][3] = [1, 2, 3, 4, 5, 6];
// Some functions may be useful:  getLastLocation(); getNextToken();
std::unique_ptr
  parseVarDeclaration(bool requiresInitializer) {

    // TODO: check to see if this is a 'var' declaration 
    //       If not, report the error with 'parseError', otherwise eat 'var'  
    /* Write your code here. */
    if (lexer.getCurToken() != tok_var)
    {
    	return parseError("var", "to begin declaration");
    }
    auto loc = lexer.getLastLocation();
    lexer.getNextToken(); // eat var
    /* Write your code above */

    // TODO: check to see if this is a variable name 
    //       If not, report the error with 'parseError'
    /* Write your code here. */
    if(lexer.getCurToken() != tok_identifier)
    {
    	return parseError("identified", "after 'var' declaration");
    }
    /* Write your code above */
    
    // eat the variable name
    std::string id(lexer.getId());
    lexer.getNextToken(); // eat id

    std::unique_ptr type; 
    // TODO: modify code to additionally support the third method: var a[][] = ... 
    if (lexer.getCurToken() == '<' || lexer.getCurToken() == '[') {
      type = parseType();
      if (!type)
        return nullptr;
    }
    if (!type)
      type = std::make_unique();

    std::unique_ptr expr;
    if (requiresInitializer) {
      lexer.consume(Token('='));
      expr = parseExpression();
    }
    return std::make_unique(std::move(loc), std::move(id),
                                            std::move(*type), std::move(expr));
  }
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

进阶部分：代码优化

• 进行冗余代码的消除：Tiny 语言内置的 transpose 函数会对矩阵进行转置操作。然而，对同一个矩阵进行两次转置运算会得到原本的矩阵，相当于没有转置。矩阵的转置运算是通过嵌套 for 循环实现的，而嵌套循环是影响程序运行速度的重要因素。因此，侦测到这种冗余代码并进行消除是十分必要的。
• 文件路径：/tiny_project/tiny/mlir/TinyCombine.cpp
• 在 TinyCombine.cpp 搜索"TODO"，可以看到需要补充的代码位置。实现以下功能：
  • 将 tiny dialect 的冗余转置代码优化 pass 补充完整。最终实现冗余代码的消除。

具体实现

• TODO：实现冗余代码的消除
  • 获取当前转置操作输入的操作数。
  • 如果当前输入的操作数不是转置，说明没有冗余转置，则返回匹配失败，表达式不同进行优化。
  • 如果输入的操作数是转置，说明有冗余转置，所以重写表达式，消除冗余转置，最后返回匹配成功。

实验结果

词法分析器验证

• test_1 - test_4
• 以 test_1 为例： build tiny 并执行下面测试用例以验证词法分析器是否能够检测出错误的词法单元。

# 在/home/username/tiny_project/build 目录下开始执行
cmake --build . --target tiny
cd ../
build/bin/tiny test/tiny/parser/test_1.tiny -emit=ast
1
2
3
4

语法分析器验证

• test_5 - test_6
• 测试 test_5: 验证语法分析器能否识别出三种声明及初始化方式，输出 AST（-emit=ast）：

build/bin/tiny test/tiny/parser/test_5.tiny -emit=ast
1

• 执行结果：

第三种类型 —— d[2][3] ——已成功识别。

• 测试 test_6: 执行以下指令查看输入程序的运行结果（-emit=jit）：

build/bin/tiny test/tiny/parser/test_6.tiny -emit=jit
1

• 执行结果：

代码优化验证

• 对于 test_7 中的例子：

def transpose_transpose(x) {
  return transpose(transpose(x));
}

def main() {
  var a<2, 3> = [[1, 2, 3], [4, 5, 6]];
  var b = transpose_transpose(a);
  print(b);
}
1
2
3
4
5
6
7
8
9

• 执行以下指令，输出转换后的 tiny dialect（即转换后的代码表示）， 查看输出结果可判断是否成功消除冗余转置：

build/bin/tiny test/tiny/parser/test_7.tiny -emit=mlir -opt
1

• 执行结果：已消除转置操作。
• 注释掉刚刚在 TinyCombine.cpp 中添加的代码，执行指令查看未优化的输出，对比优化前后输出的差异：

build/bin/tiny test/tiny/parser/test_7.tiny -emit=mlir -opt
1

• 执行结果：存在冗余转置
• 此外，还可以利用不同指令，输出此测试用例在编译过程中出现的多种形式：

# 将.tiny文件转换为抽象语法树AST：
build/bin/tiny test/tiny/parser/test_7.tiny -emit=ast

# 或直接得到tiny程序的运行结果，是否进行消除冗余不会影响运行结果
build/bin/tiny test/tiny/parser/test_7.tiny -emit=jit
1
2
3
4
5

资源下载地址：https://download.csdn.net/download/sheziqiong/86784192
资源下载地址：https://download.csdn.net/download/sheziqiong/86784192