Compiler 2014: Mail List Summary Phase 3

资料分享

SSA：

http://www.lingcc.com/2011/08/13/11685/

Compiler books：

http://gcc.gnu.org/wiki/ListOfCompilerBooks

Statspim：

https://bitbucket.org/xjia/statspim

垃圾回收编程练习：

https://bitbucket.org/xjia/gccp/src

直接将C语言翻译成MIPS32的工具：

http://www.cnblogs.com/bcxx_qin/archive/2009/08/25/1553429.html

http://www-inst.eecs.berkeley.edu/~cs162/fa10/Nachos/xgcc.html

http://www.linux-mips.org/wiki/Toolchains#Roll-your-own

Dominator Tree：

http://www.cs.princeton.edu/~rwerneck/docs/GWTTA04.pdf

j和jal的区别

jal：Unconditionally jump to the instruction at target. Save the address of the next instruction in register $ra.

寄存器分配spill之后会重新建inference graph，重做寄存器分配，这样做和只做一遍区别大吗

http://acm.sjtu.edu.cn/w/images/b/bf/Register_Allocation_2013-5-3.pdf 58到61页有解释

是不是无论一个var被spill与否，每次def它都需要强制store，第一次用它时也需要插入load

强制store的地方有两处，一：出现了某个function call，二：它被取地址了，别的时候，如果它被分配了寄存器，就不用跟内存打交道了。

被选中spill，需要额外引入新的变量和load。是在哪些地方引入呢？

我们需要”隔离两个寄存器“，比如t1,t2，然后如果遇到有指令使用了spill的var，则load进t1,t2来进行计算

linear scan algorithm需要提供live interval，但是在一个图结构的cfg上什么才算作是live interval呢

live interval跟图结构没什么关系了，图结构是为了活性分析，简单来说，interval的开头就是某个寄存器最早活的一条指令，结束就是最晚活的那条指令。

是不是涉及数组和struct就一定需要先store后load呢

需要这样处理

寄存器分配的理解

有关寄存器的问题你可以这么想：编译器中有两种东西，一种叫做变量，一种叫做常量。变量和常量都需要一个存储或者摆放的地方（因为有可能出现常量过大，导致位数不够，不能直接做ophand的情况）。

于是从最暴力的想法开始，我给所有的东西都存到内存里，不管是栈还是堆。塞进去了之后，每次用都是读然后再写，说白了就是100%spill的情况。

接下来，为了优化性能，所以我们要寄存器分配，寄存器分配不代表有寄存器的东西你就不需要给内存上的空间了，说到底这只是一个临时存东西的地方。

这个地方比较好理解的思路是，先考虑所有都spill的情况，然后把能不spill的调出来，让他不spill。而不是先分配寄存器，发现有些东西分配不了了，再来spill。

两者从结果上虽然是一致的，但是思路上还是有细微的区别的，其实硬要说的话我认为寄存器分配并不是编译器必不可缺的一环，它只是个很重要的优化罢了。

最后评价performance所提到的指令数是指什么

statspim 会统计 xxx.s 运行后执行了多少次所有指令、多少次 load 指令、多少次 store 指令、多少次 jump/branch 指令

因为不同指令在实际 CPU 上运行的代价不一样（比如 load/store 是内存操作，比算术运算要慢），建议助教加权处理

但肯定不是 xxx.s 文件的大小，因为有循环

如果我做编译器的时候char开的空间是4，那我sizeof(char)返回4可以么

sizeof的规定：When applied to an operand that has type char, unsigned char, or signed char, (or a qualified version thereof) the result is 1.

运行时限是多少

没有时限，只有指令条数限制。不过限制肯定会很松的，稍微优化优化就可以过的。

期末测试的数据点就是公布的这些吗

是，就是Normal这些，不会再有大改动了

$at怎么用？貌似spim禁用$at

$at 名正言顺的使用者是 spim，因为它支持自己把（伪）指令拆成两三句话，中间结果就用 $at 存

加一条.set noat就行了

对于比较长的MIPS代码，用statspim可能会出现 “can’t expand text segment”的情况，而QtSpim似乎没有

以statspim为准。建议优化下mips代码（如果qtspim能跑过，那么就开始写优化好了，说不定写完优化之后statspim就能过了）

在qtspim跑对了在spim异常了会是什么事啊

可能是因为你没有分配足够的堆空间，超出了限制，要么动态调用SYSCALL，要么这样修改

.data 0x10000000
.space 0xFFFFF
.data 0x10000000

强制让spim在一开始就把堆分配成1MB，静态分配的部分是会自动扩大的，但是动态的部分正常是要sbrk的，但是这种方法利用了spim对静态分配会自动扩大的特性，就省下了sbrk和判断的指令

八皇后优化真的能从100多万降到20多万吗

图中是我当时对带输出的八皇后的优化过程，估计第一个点是没写寄存器分配的，第二个（80多万）是刚写完寄存器分配的

我一共实现了这样几个优化：

a) 函数内联

b) 无关函数删除

c) 递归展开

d) 常量内联

e) 常量折叠

f) 循环展开

g) 树重写（优化IfExp嵌套的情况）

h) 全局可用表达式

i) 局部复制传播

j) 全局死代码消除

k) 强度削减

l) 窥孔优化

印象里 a c d e f h 对八皇后都有效果，其中 c f 效果最好，但是比较 ad-hoc

此外我花了大量的时间做窥孔优化，效果甚好

此外，我的寄存器分配写的不是很标准

虽然是在普通四元式（而非 SSA）上做最普通的 linear scan（一个变量对应一个长长的 live interval）

但是

(1) 我用了 $at $v0 $v1 $k0 $k1 $sp 这几个寄存器作为普通寄存器；注意 $fp 和 $sp 只要一个就可以了

(2) 经过和王米哈同学的彻夜讨论，我没有完全（他完全没有）按照 MIPS call convention 来实现函数调用，所以不区分 $t* 和 $s*

这样两件事情增加了可用的寄存器数目，但是在实际应用中是使不得的

报告Bonus

报告没亮点也会给，只要认真写个3分至少会给你的

速度Bonus

一周内测三次，每个点会取你三次最快（估计就是最后一次最快吧），然后最后排个序一起给

报告要求

首先页数至少得是1页半A4，字号最大小四，中英文随意，格式随意，你用latex或者word都行，最后给我们pdf。

只要你写够页数了那么苦劳分2分就会给你。

然后的评分就看评你的助教欣不欣赏你的工作了，每篇文章都会由两个助教看，如果分差不大取max。

注意，哪怕你没做什么特殊功能和优化，你只要总结的够清楚（比如一个不懂编译器的人看了你的报告后就会写了），也能获得高分。

而对于做了一些额外功能和优化的同学，应该着重写你们这方面的成果。

评测的deadline是25号，报告是6月1号，把pdf放在你的repo根目录下就行，tag还是finalterm。

说完了，然后是我个人的一些意见，大家随意看看，各位助教也可以补充一下

1.往届的报告很多人喜欢贴一个超大的类图，但我觉得没啥意思，类图大家基本都长一个样，我觉得还不如画个流程图，并说下某些重点class的功能和设计思路。

2.比如我过了两年已经看不懂当年的程序了，所以这个报告除了展示工作，还有一个很大作用就是日后帮你回忆往事。

3.对你用到的外部库应该说明一下用在哪了。

4.对于一个你想重点说的优化，应该说明做在哪一层，怎么做的，举个例子，最后给出前后指令数对比。

5.代码上的一些小trick会令你的报告增色不少。

经验教训

合并分支(我是把master合并到别的)的那次commit打tag似乎是不起作用的，总之，不要用branch代替tag