2020-02-21

Kaleidoscope user defined operator

学习内容

完成对 https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl06.html 的学习。

练习

看懂原网页后，实现同样的功能。

扩展

1 命名时没有限制operator是否能是常规字符(如abc,123等)，会否产生静默的关键字冲突？
2 考虑如何处理两个特殊字符组成的操作符，如==　!=等。
3 示例中的自定义operator是否能作为库使用？如果不能应该如何改进？

进展

完成了原示例自定义binary和unary operator的功能，但是未支持用户定义”unary-“。
尚未支持unary-的原因是为了阻止用户犯错，我们禁止了用户定义使用保护字符（包括内置运算符、分隔符等）的operator。这里的检查规则比较简单，仅仅实现了基于char的比较，实际上过于严格，以至于阻止了用户定义unary-这样的合法要求。后续细化保护规则后(拆分运算符和受保护的字符两种类型，对运算符区分binary和uary类型)，即可支持unary-。

实现

实现过程中发现原示例确实精炼，仅用很少的代码便实现了用户自定义operator的功能。但是，其精炼的代价是该功能仅仅具有演示价值而几乎没有实用价值。
例如，原示例没有在lexer做token分层，parser会直接读取输入的char。这样一来lexer可以非常非常简单。并且，在新增语法功能时，parser由于可以直接穿透处理char，需要新增的配合代码也很少。
但是这样的设计导致代码维护困难，parser中要直接处理token拆分逻辑，一旦语法变复杂，新增功能或更改已有逻辑(直接操作char的地方会很多)就会很困难。
另外，原示例没有错误防护的逻辑，这会导致用户犯错很难定位原因。

实现过程中针对前面扩展中提出的问题，一一进行了改进。详细情况可参考扩展问题一节中的描述。
从实现后的实际情况看，改进引入了相当多的额外代码，工作量较大。作为示例，相较于引入大量的细节流程，原作者使用精简的方案确实是更好的权衡（示例丧失了扩展为真正可实用编译器的潜力，但仍然展现了主要的原理，解决了核心问题）。

扩展问题

1 命名时没有限制operator是否能是常规字符(如abc,123等)，会否产生静默的关键字冲突？
原示例几乎没有对自定义operator做错误防护。这将导致用户错误定义operator，很难察觉和定位到根因。
如下所示，覆盖内置操作符的优先级和语义将导致二义性和混乱。

ready> def binary + 80 (a b) a+b; 
ready> Read function definition:define double @"binary+"(double %a, double %b) {
entry:
  %addtmp = fadd double %a, %b
  ret double %addtmp
}

ready> 1+2*3;
ready> Evaluated to 9.000000

定义保留字符’,’，parser无法理解。

ready> def unary , (a) a+1;
ready> Read function definition:define double @"unary,"(double %a) {
entry:
  %addtmp = fadd double %a, 1.000000e+00
  ret double %addtmp
}
ready> def xy3(a) a+,a;
ready> Error: unknown token when expecting an expression
ready> Error: Unknown variable name

定义保留字符’(‘，parser无法理解。

ready> def unary ( (a) a+1;
ready> Read function definition:define double @"unary("(double %a) {
entry:
  %addtmp = fadd double %a, 1.000000e+00
  ret double %addtmp
}
ready> def xy4(a) a+(1  
ready> ;
Error: expected ')'

为了避免这些错误，在实现时专门针对binary/unary的名称做了正确性校验(verify_operator_sym函数)。
在错误第一现场阻止错误，并给出清晰的提示。

2 考虑如何处理两个特殊字符组成的操作符，如==　!=等。
原示例由于使用了char来作为operator的opcode，实际上就无法支持两字符操作符。但使用单char作为operator的opcode，大大简化了构建operator token的难度。因为只需要在parser中按需读出一个char就可以，无需考虑在lexer中如何正确切分的问题。
为了支持!= 和==等显然有意义的两字符operator，本次实现时在lexer中添加了一个map查找机制，如下所示。

if (cur_token == TOKEN_BINARY || cur_token == TOKEN_UNARY)
{
	if (install_user_defined_operator(input_stream, cur_char))
		return;
}

if (get_user_defined_operator(input_stream, cur_char))
	return;

install_user_defined_operator函数，在binary和unary关键字后识别并注册(就是插入到map中)用户自定义的operator token。
get_user_defined_operator中就可以查找已经注册的用户自定义operator，并给出正确的token类型（用户自定义unary或者binary）。

3 示例中的自定义operator是否能作为库使用？如果不能应该如何改进？
从实现原理上来说，因为operator 也是在proto中解析的，与函数一样。
所以自定义的operator只要遵循先extern申明，再引用的规则，就可以以库的方式正常使用(定义在单独的库文件中，使用时链接二进制文件)。
但是，原示例没有考虑容错问题。
parser在工作时是按照extern声明的优先级工作。如果定义时的优先级和extern时的不一致，则程序的逻辑将静默改变。用户要发现这样的问题可能很困难（这个和C中没有正确包含头文件的情况类似）。
为了解决这个问题，参考C++的方法，把prio作为一个强制信息加入到binary/unary函数的名称中。这样一旦extern声明和def的定义不一致，链接时会找不到函数定义。用户将不能得到可工作（但逻辑错误）的二进制文件。

实现中遇到的问题

1 prototype_tab的key从string切换到string_view后，遇到了内存数据错误的问题。详细记录如下。
使用string_view作为map的key时，我们调用了tab.insert(make_pair(a_string, my_val));。原以为string会自动转为string_view，tab中的key(string_view)数据应该指向a_string。实际发现key的数据指向了一个insert所在的函数栈。
使用下面的小型测试用例即可复现出问题，pair中的key并不是指向我们希望的全局数据。

#include <iostream>
#include <string>
#include <string_view>
using namespace std;
void test_view(pair<string_view, int> p)
{
        cout << "value:"<< p.first.data() << endl;
        cout << "address:" << (void*)p.first.data() << endl;
}

string global("abc");
int main()
{
        cout << "value_global:" << global.data() << endl;
        cout << "address_global:" << (void*)global.data() << endl;
        test_view(make_pair(global,1));
        return 0;
}

使用g++ save-temps -fdump-tree-all-details -std=c++17编译上面的代码，可以比较清楚地看出问题。
这里的核心错误在于：
make_pair是一个模板函数，(为了提供泛型能力)它并不知道（或者提供这个约束）第一个参数应该是string_view。当我们提供一个string作为第一个参数时，test_view(make_pair(global,1));的调用并没有变成我们希望的test_view(make_pair((string_view)global,1))。而是变成了如下的序列。
tmp_pair = make_pair<string, int>(global, 1);
tmp_pair_to_call = pair<string_view, int> (tmp_pair);
test_view(tmp_pair_to_call);
这样传到test_view中pair中的string_view实际上指向栈上创建的临时变量。一旦tmp_pair所在的函数return，string_view中的key就乱掉了（use after free）。

从这次经历看string_view确实是非常容易出错的点，使用时需要特别谨慎。参考 https://alexgaynor.net/2019/apr/21/modern-c++-wont-save-us/ 的如下示例，string_view允许指向临时对象，这确实很容易导致错误，并且很难发现。

int main() {
  std::string s = "Hellooooooooooooooo ";
  std::string_view sv = s + "World\n";
  std::cout << sv;
}

2 切换到clang8编译器后，优化LLVM-IR时程序段错误。
google搜索到了下面的邮件，这是一个gcc/clang的abi兼容性问题。
http://lists.llvm.org/pipermail/llvm-dev/2019-January/129567.html
需要将llvm库用clang重新编译（或者升级到最新的llvm）。
升级到最新的llvm代码后确实解决了该问题。

3 升级到最新的llvm后，遇到了asan报大量indirect leak问题。
仔细检查代码后，发现llvm_optimizer::optimize_function等函数中，
使用了createTargetMachine创建的TargetMachine *。
添加了delete TargetMachine *的语句后，leak告警消失。
老版本为何没报leak，暂时没有进一步核查。