我花了一个长周末读完 LLVM MLIR 教程的全部七章。教程实现了一门用于张量运算的简单语言,恰好与我之后计划开展的项目有关。原教程比较精炼,默认读者已经熟悉 LLVM 和编译器,因此我想分享学习过程中的一些体会,希望能为你提供参考。
这篇文章聚焦第 1 章。虽然还没有涉及 MLIR,但它有助于从整体上理解编译器前端。
语言
我们要实现一门名为 Toy 的玩具语言,因此先要理解它的语法。它的风格类似 Python,但使用花括号,或许更像 JavaScript。为简化实现,我们设定以下约束:
- 张量的秩不超过 2。
- 所有张量元素都是 float64。
- 值不可变,所有定义的变量本质上都是常量。
def main() {
# Define a variable `a` with shape <2, 3>, initialized with the literal value.
# The shape is inferred from the supplied literal.
var a = [[1, 2, 3], [4, 5, 6]];
# b is identical to a, the literal tensor is implicitly reshaped: defining new
# variables is the way to reshape tensors (element count must match).
var b<2, 3> = [1, 2, 3, 4, 5, 6];
# transpose() and print() are the only builtin, the following will transpose
# a and b and perform an element-wise multiplication before printing the result.
print(transpose(a) * transpose(b));
}
这门语言有趣的一点是类型推导。函数参数是泛型的,张量的形状在编译期推导出来,这称为“函数特化”。
def multiply_transpose(a, b) {
return transpose(a) * transpose(b);
}
项目结构如下:
- Ch1
- include
- toy
- AST.h
- Lexer.h
- Parser.h
- parser
- AST.cpp
- CMakeLists.txt
- toyc.cpp
构建词法分析器(Lexer.h)
程序本质上是字符串。词法分析器将字符串切分为 token,之后用它们构建 AST。整个词法分析器都在 Lexer.h 中实现。
首先定义 Toy 语言的保留关键字。
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,
// primary
tok_identifier = -5,
tok_number = -6,
};
词法分析的核心逻辑位于 getToc 函数中。它不断读取字符,直到当前 token 结束,再返回完整的 token。
Token getTok() {
// Skip any whitespace.
while (isspace(lastChar))
lastChar = Token(getNextChar());
// Save the current location before reading the token characters.
lastLocation.line = curLineNum;
lastLocation.col = curCol;
// Identifier: [a-zA-Z][a-zA-Z0-9_]*
if (isalpha(lastChar)) {
identifierStr = (char)lastChar;
while (isalnum((lastChar = Token(getNextChar()))) || lastChar == '_')
// read until the identifier is complete (broken by punctuations, white spaces, etc)
identifierStr += (char)lastChar;
if (identifierStr == "return")
return tok_return;
if (identifierStr == "def")
return tok_def;
if (identifierStr == "var")
return tok_var;
return tok_identifier;
}
// Number: [0-9.]+
if (isdigit(lastChar) || lastChar == '.') {
std::string numStr;
do {
numStr += lastChar;
lastChar = Token(getNextChar());
} while (isdigit(lastChar) || lastChar == '.');
numVal = strtod(numStr.c_str(), nullptr);
return tok_number;
}
if (lastChar == '#') {
// Comment until end of line.
do {
lastChar = Token(getNextChar());
} while (lastChar != EOF && lastChar != '\n' && lastChar != '\r');
if (lastChar != EOF)
return getTok();
}
// Check for end of file. Don't eat the EOF.
if (lastChar == EOF)
return tok_eof;
// Otherwise, just return the character as its ascii value.
Token thisChar = Token(lastChar);
lastChar = Token(getNextChar());
return thisChar;
}
构建语法分析器(Parser.h)
接下来使用语法分析器将 token 转换为 AST。语法分析器初始化时接收一个词法分析器,并随着后者不断生成 token 而构建 AST。
下面是语法分析器的公共接口,入口是 parseModule。首先预热词法分析器,即初始化 curToken;随后不断解析函数定义,直到文件结束;最后用解析出的函数构造 ModuleAST。
class Parser {
public:
/// Create a Parser for the supplied lexer.
Parser(Lexer &lexer) : lexer(lexer) {}
/// Parse a full Module. A module is a list of function definitions.
std::unique_ptr<ModuleAST> parseModule() {
lexer.getNextToken(); // prime the lexer
// Parse functions one at a time and accumulate in this vector.
std::vector<FunctionAST> functions;
while (auto f = parseDefinition()) {
functions.push_back(std::move(*f));
if (lexer.getCurToken() == tok_eof)
break;
}
// If we didn't reach EOF, there was an error during parsing
if (lexer.getCurToken() != tok_eof)
return parseError<ModuleAST>("nothing", "at end of module");
return std::make_unique<ModuleAST>(std::move(functions));
}
//...
}
parseDefinition 首先调用 parsePrototype。函数原型基本就是函数签名。我们依次解析 def、函数名、(、参数列表和 )。注意,std::vector<std::unique_ptr<VariableExprAST>> args; 将所有参数标识符存储为 VariableExprAST。
std::unique_ptr<FunctionAST> parseDefinition() {
auto proto = parsePrototype();
if (!proto)
return nullptr;
if (auto block = parseBlock())
return std::make_unique<FunctionAST>(std::move(proto), std::move(block));
return nullptr;
}
std::unique_ptr<PrototypeAST> parsePrototype() {
auto loc = lexer.getLastLocation();
if (lexer.getCurToken() != tok_def)
return parseError<PrototypeAST>("def", "in prototype");
lexer.consume(tok_def);
if (lexer.getCurToken() != tok_identifier)
return parseError<PrototypeAST>("function name", "in prototype");
std::string fnName(lexer.getId());
lexer.consume(tok_identifier);
if (lexer.getCurToken() != '(')
return parseError<PrototypeAST>("(", "in prototype");
lexer.consume(Token('('));
std::vector<std::unique_ptr<VariableExprAST>> args;
if (lexer.getCurToken() != ')') {
do {
std::string name(lexer.getId());
auto loc = lexer.getLastLocation();
lexer.consume(tok_identifier);
auto decl = std::make_unique<VariableExprAST>(std::move(loc), name);
args.push_back(std::move(decl));
if (lexer.getCurToken() != ',')
break;
lexer.consume(Token(','));
if (lexer.getCurToken() != tok_identifier)
return parseError<PrototypeAST>(
"identifier", "after ',' in function parameter list");
} while (true);
}
if (lexer.getCurToken() != ')')
return parseError<PrototypeAST>(")", "to end function prototype");
// success.
lexer.consume(Token(')'));
return std::make_unique<PrototypeAST>(std::move(loc), fnName,
std::move(args));
}
接着使用 parseBlock 解析函数体。它返回由 ExprASTList 表示的表达式列表,并根据 token 类型分派到不同处理函数:变量声明、返回语句或普通表达式。
std::unique_ptr<ExprASTList> parseBlock() {
if (lexer.getCurToken() != '{')
return parseError<ExprASTList>("{", "to begin block");
lexer.consume(Token('{'));
auto exprList = std::make_unique<ExprASTList>();
// Ignore empty expressions: swallow sequences of semicolons.
while (lexer.getCurToken() == ';')
lexer.consume(Token(';'));
while (lexer.getCurToken() != '}' && lexer.getCurToken() != tok_eof) {
if (lexer.getCurToken() == tok_var) {
// Variable declaration
auto varDecl = parseDeclaration();
if (!varDecl)
return nullptr;
exprList->push_back(std::move(varDecl));
} else if (lexer.getCurToken() == tok_return) {
// Return statement
auto ret = parseReturn();
if (!ret)
return nullptr;
exprList->push_back(std::move(ret));
} else {
// General expression
auto expr = parseExpression();
if (!expr)
return nullptr;
exprList->push_back(std::move(expr));
}
// Ensure that elements are separated by a semicolon.
if (lexer.getCurToken() != ';')
return parseError<ExprASTList>(";", "after expression");
// Ignore empty expressions: swallow sequences of semicolons.
while (lexer.getCurToken() == ';')
lexer.consume(Token(';'));
}
if (lexer.getCurToken() != '}')
return parseError<ExprASTList>("}", "to close block");
lexer.consume(Token('}'));
return exprList;
}
表达式种类很多。我们先解析第一个基本表达式,即标识符、数字、括号表达式或张量字面量,再递归解析嵌套二元运算的右侧,例如 a + b * c。这里必须考虑运算符优先级。例如,a + b * c 应当构建为:
+
/ \
a *
/ \
b c
先组合 b 和 c,再与 a 组合。
std::unique_ptr<ExprAST> parseExpression() {
auto lhs = parsePrimary();
if (!lhs)
return nullptr;
return parseBinOpRHS(0, std::move(lhs));
}
std::unique_ptr<ExprAST> parseBinOpRHS(int exprPrec,
std::unique_ptr<ExprAST> lhs) {
// If this is a binop, find its precedence.
while (true) {
int tokPrec = getTokPrecedence();
// If this is a binop that binds at least as tightly as the current binop,
// consume it, otherwise we are done.
if (tokPrec < exprPrec)
return lhs;
// Okay, we know this is a binop.
int binOp = lexer.getCurToken();
lexer.consume(Token(binOp));
auto loc = lexer.getLastLocation();
// Parse the primary expression after the binary operator.
auto rhs = parsePrimary();
if (!rhs)
return parseError<ExprAST>("expression", "to complete binary operator");
// If BinOp binds less tightly with rhs than the operator after rhs, let
// the pending operator take rhs as its lhs.
int nextPrec = getTokPrecedence();
if (tokPrec < nextPrec) {
rhs = parseBinOpRHS(tokPrec + 1, std::move(rhs));
if (!rhs)
return nullptr;
}
// Merge lhs/RHS.
lhs = std::make_unique<BinaryExprAST>(std::move(loc), binOp,
std::move(lhs), std::move(rhs));
}
词法分析器和语法分析器要处理许多边界情况,写起来颇为繁琐。最终我们得到了 AST,下一章将把它转换为 MLIR。
Module:
Function
Proto 'multiply_transpose' @test/Examples/Toy/Ch1/ast.toy:4:1
Params: [a, b]
Block {
Return
BinOp: * @test/Examples/Toy/Ch1/ast.toy:5:25
Call 'transpose' [ @test/Examples/Toy/Ch1/ast.toy:5:10
var: a @test/Examples/Toy/Ch1/ast.toy:5:20
]
Call 'transpose' [ @test/Examples/Toy/Ch1/ast.toy:5:25
var: b @test/Examples/Toy/Ch1/ast.toy:5:35
]
} // Block
Function
Proto 'main' @test/Examples/Toy/Ch1/ast.toy:8:1
Params: []
Block {
VarDecl a<> @test/Examples/Toy/Ch1/ast.toy:11:3
Literal: <2, 3>[ <3>[ 1.000000e+00, 2.000000e+00, 3.000000e+00], <3>[ 4.000000e+00, 5.000000e+00, 6.000000e+00]] @test/Examples/Toy/Ch1/ast.toy:11:11
VarDecl b<2, 3> @test/Examples/Toy/Ch1/ast.toy:15:3
Literal: <6>[ 1.000000e+00, 2.000000e+00, 3.000000e+00, 4.000000e+00, 5.000000e+00, 6.000000e+00] @test/Examples/Toy/Ch1/ast.toy:15:17
VarDecl c<> @test/Examples/Toy/Ch1/ast.toy:19:3
Call 'multiply_transpose' [ @test/Examples/Toy/Ch1/ast.toy:19:11
var: a @test/Examples/Toy/Ch1/ast.toy:19:30
var: b @test/Examples/Toy/Ch1/ast.toy:19:33
]
VarDecl d<> @test/Examples/Toy/Ch1/ast.toy:22:3
Call 'multiply_transpose' [ @test/Examples/Toy/Ch1/ast.toy:22:11
var: b @test/Examples/Toy/Ch1/ast.toy:22:30
var: a @test/Examples/Toy/Ch1/ast.toy:22:33
]
VarDecl e<> @test/Examples/Toy/Ch1/ast.toy:25:3
Call 'multiply_transpose' [ @test/Examples/Toy/Ch1/ast.toy:25:11
var: c @test/Examples/Toy/Ch1/ast.toy:25:30
var: d @test/Examples/Toy/Ch1/ast.toy:25:33
]
VarDecl f<> @test/Examples/Toy/Ch1/ast.toy:28:3
Call 'multiply_transpose' [ @test/Examples/Toy/Ch1/ast.toy:28:11
var: a @test/Examples/Toy/Ch1/ast.toy:28:30
var: c @test/Examples/Toy/Ch1/ast.toy:28:33
]
} // Block