Kaleidoscope mutable variable

学习内容

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

练习

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

扩展

1 使用CreateAlloca在function的头部创建栈空间，是否会导致不必要的额外栈空间占用？

进展

完成了原示例的功能，添加了对应的简单测试。
以库的方式添加了’,’和’!=’等核心的operator，尚未自动添加到源代码中。
一种可行的简单方式是以源代码方式直接把这些operator的def直接include到代码的头部，然后再编译。但是，需要考虑这样操作对源代码行号的干扰。
等待后续生成调试信息的章节一并考虑。

实现

实现时做了如下两个主要的改进:
1 var中变量默认数值设置为0，原示例是在LLVM-IR 生成时构造的。从逻辑上看，这个应该是语法层面的规定，不应该放到codegen的流程中决定。本次实现时，在parser中parse_var时将未初始化的变量value设置为了0。codegen时只管按值生成就可以了。
2 在处理var中的变量shadow前面已定义变量的情况时。原示例为了简单，是直接把var中声明的所有变量都缓冲到了OldBindings中，如果没有shadow，则把nullptr缓冲到OldBindings中。生成完body后，直接把OldBindings中的所有条目写回NamedValues中。如下片段所示。

1
2
3
4
5
6
7
8
  std::vector<AllocaInst *> OldBindings;
  OldBindings.push_back(NamedValues[VarName]);
  // Remember this binding.
  NamedValues[VarName] = Alloca;
....body_gen....
  // Pop all our variables from scope.
  for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
    NamedValues[VarNames[i].first] = OldBindings[i];

本次实现使用了更安全的find来替代[] operator，同时改进了缓存结构。
通过存储named_var中被shadow变量alloca字段的地址，消除了恢复
named_var时的map查找动作，如下片段所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	vector<std::pair<AllocaInst **, AllocaInst *>> saved_name_vec;
....
		if (auto it = named_var.find(var_name); it != named_var.end())
		{
			saved_name_vec.push_back(
				std::make_pair(&(it->second), it->second));
			it->second = var_allocas[i];
		}
		else
			named_var[var_name] = var_allocas[i];
	}
...bodygen....
//恢复named_var
	for (size_t i = 0; i < saved_name_vec.size(); ++i)
	{
		auto old_alloca_addr = saved_name_vec[i].first;
		*old_alloca_addr = saved_name_vec[i].second;
	}

3 实现测试时发现了原示例中存在内存泄漏的可能，如下代码所示。

1
2
3
4
5
6
7
8
9
10
11
Value *IfExprAST::codegen() {
  ....
  // Create blocks for the then and else cases.  Insert the 'then' block at the
  // end of the function.
  BasicBlock *ThenBB = BasicBlock::Create(TheContext, "then", TheFunction);
  BasicBlock *ElseBB = BasicBlock::Create(TheContext, "else");
  BasicBlock *MergeBB = BasicBlock::Create(TheContext, "ifcont");
....
  Value *ThenV = Then->codegen();
  if (!ThenV)
    return nullptr;

上面代码片段中，ElseBB和MergeBB创建后没有立即挂入function的链表中。如果函数在类似于ThenV的异常流程中return了，则没有人能释放掉这两个指针了。我们的实现中也有类似问题。
要比较完整的修复该问题，有两个点需要同时考虑：
首先，BB创建后都立即挂到Function中去是否会有不良影响？如果没有，创建就挂上是最好的解决方案；
如果不能立即挂上，除了在函数内考虑释放资源外，还要考虑 ir_builder.CreateBr(merge_bb);等语句在异常发生时可能引用悬空指针的问题。需要重排对这些指针的引用，将其都放到末尾。

扩展问题

1 使用CreateAlloca在function的头部创建栈空间，是否会导致不必要的额外栈空间占用？
使用如下的c语言片段进行了测试。发现clang生成代码时也会把alloca都放到头部，并且生成的x86-64和mips64的代码也都是一次在头部把sp预留够。
这里的权衡可能是动态扩展栈变量无法节约多少内存，但是会浪费操作sp的指令，另外也使得分析stack frame变得更为困难，得不偿失。

1
2
3
4
5
6
7
8
9
extern int x ;
void test()
{
        char buf[1024] = {2};
        if (x)
        {
                char nb[1024]= {1};
        }
}

实现中遇到的问题

1 map 的operator[]会改写原map
在改写for代码生成流程中，named_var map 记录和恢复idt var的部分时，
注意到了下面一对代码。

1
2
3
4
5
6
7
	auto old_val = named_var[idt_name];
	named_var[idt_name] = idt_var;
.....
	if (old_val != nullptr)
		named_var[idt_name] = old_val;
	else
		named_var.erase(idt_name);

这段逻辑是直接从原示例中拷贝过来的。
重构时注意到named_var[idt_name]的初始值问题。
当idt_name这个key不在map中时，读取其value的语义是比较模糊的。
参考https://en.cppreference.com/w/cpp/container/map/operator_at ， 发现[]这个operator竟然会静默的insert，即使这个operator是用在取右值的动作中。
用下面的示例，可以较为直观展示出这个出人意料的行为。

1
2
3
4
5
6
7
8
9
10
11
12
#include <map>
#include <iostream>
using namespace std;
int main()
{
	map<int, int*> t1;
	cout << "size before access:" << t1.size() << endl;
	cout << "uninitialized pointer is: " << t1[0] << endl;
	cout << "size after access:" << t1.size() << endl;
	cout << "count after access:" << t1.count(0) << endl;
	return 0;
}

这个程序的输出如下。

1
2
3
4
size before access:0
uninitialized pointer is: 0
size after access:1
count after access:1

可以看到使用[]访问map时，确实会有insert的动作，并且当key不在map中时，返回的vale是一个默认初始化的值。
在这样的语义下，原示例的代码片段虽然不会导致严重的逻辑错误，但是仍有两个明显的问题。
第一，引入了冗余的insert动作，拖慢了编译器工作速度。
第二，在退出清理map时，如果初始key不存在就不会erase。这样一来map中会残留一个错误的映射项目idt_var –> nullptr。后续流程如果直接使用count这类存在性接口去测试，会得到错误的结果。这是一个潜在的错误来源。

2 std::move作用于const vector不生效
如下测试代码

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
#include <iostream>
#include <vector>
using namespace std;
class testc_ref
{
public:
    vector<int> inner;
    testc_ref(vector<int>& in) : inner(std::move(in)) {}
};

class testc_move
{
public:
    vector<int> inner;
    testc_move(vector<int> in) : inner(std::move(in)) {}
};

class testc_const_ref
{
public:
    vector<int> inner;
    testc_const_ref(const vector<int>& in) : inner(std::move(in)) {}
};

int main()
{
    vector<int> mytest(100000, 1);
    cout << "org:" << &(mytest[0]) << endl;
    testc_move t1(mytest);
    cout << "t1:"<< &(t1.inner[0]) << endl;
    cout << &(mytest[0]) << endl;

    testc_move t2(std::move(mytest));
    cout << "t2:"<< &(t2.inner[0]) << endl;
    cout << &(mytest[0]) << endl;


    vector<int> mytest1(100000, 1);
    cout << "org:" << &(mytest1[0]) << endl;
    testc_ref t3(mytest1);
    cout << "t3:"<< &(t3.inner[0]) << endl;
    cout << &(mytest1[0]) << endl;

    vector<int> mytest2(100000, 1);
    cout << "org:" << &(mytest2[0]) << endl;
    testc_const_ref t4(mytest2);
    cout << "t4:"<< &(t4.inner[0]) << endl;
    cout << &(mytest2[0]) << endl;

    return 0;
}

上面程序的输出为。

1
2
3
4
5
6
7
8
9
10
11
org:0x7f39d2d5f010
t1:0x7f39d2cfd010
0x7f39d2d5f010
t2:0x7f39d2d5f010
0
org:0x7f39d2c9b010
t3:0x7f39d2c9b010
0
org:0x7f39d2c39010
t4:0x7f39d1e45010
0x7f39d2c39010

==可以看出按值传参时需要在调用点和内部都用move才能避免内存分配。==
==按引用传参时，只需在子函数内move即可。==
==而以const 引用传参时，move不会生效，并且也不会有任何告警。==

3 如何使用string_view作为key来访问string为key的map
需要使用map<string, int, less<>>这样的方式建立map，否则find必须使用string做key。
当使用map<string, int, less<>> 建立map时，调用find实际上是把string_view透传到std:less这个模板中。
后续在find的过程中，less会把map中每一个待比较的string转为string_view，然后进行两个string_view的比较。
如果是调用find的时候，把string_view先转为string再传入，则find内部就不再需要构建临时object。
使用下面的示例进行对比测试，使用string_view的版本由于有string转string_view的过程，其速度要略微慢于string的版本。下面是g++-7 -O2编译的结果。性能差距在1%以内。
./t3 string_view
102400
Time taken by function: 1254672 microseconds
./t4 string版本
102400
Time taken by function: 1243754 microseconds

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
#include <map>
#include <string>
#include <string_view>
#include <iostream>
#include <chrono> 
using namespace std;
using namespace std::chrono; 
int main()
{
    string_view key = "hello";   //string key = "hello"
    map<string, int, less<>> coll;  //map<string, int> coll;
    for (int i=0;i < 102400;i++)
        coll.insert(make_pair(to_string(i),i));
    cout << coll.size()<< endl;
    long unsigned rep = 1024*1024 * 10;
    auto re = coll.find(key);
    auto start = high_resolution_clock::now(); 
    while (rep--)
    {
        re = coll.find(key); // ok
    }
    auto stop = high_resolution_clock::now(); 
    auto duration = duration_cast<microseconds>(stop - start); 
    cout << "Time taken by function: "
        << duration.count() << " microseconds" << endl; 
    return 0;
}