鲸书笔记

prolj

第3章－存储绑定
全局变量和静态存储变量一般存储于内存中，相对于一个基址寄存器（全局指针）的偏移。全局栈变量和栈变量，相对于栈指针、帧指针的偏移。
分配在堆中的变量通过指针访问。
分配伪寄存器来存储栈（全局）变量，以后再染色处理。

对齐，重排序变量，可以提高访问速度。
先分配小的，并对齐。占用空间会大一些，但是可以以较小的偏移访问变量，提高访问速度。
存储大型数据，如数组，把数组放在中间（或其他什么位置），把指向数组的指针存储在偏移较小的地方，虽然访问数组会多一次取数操作，但是对于多次访问数组来说这种一次性开销还是很值得，尤其是数组在循环中被频繁使用的情况。

局部寄存器分配，如果变量在寄存器内就不必再load，如果类型不符就可以mov而非load，store也推迟到基本块结束或寄存器用完时进行。
基本块有单一前驱，前驱的出口就是基本块的入口，活跃的变量继续拥有寄存器。有多个前驱，取交集。对于if－else相当有效，对循环几乎无效，因为循环的前驱之一是循环自身。
或者在代码生成时使用全局寄存器分配。
给每一个符号表增加表示作用域层数和用哪个寄存器（非fp或gp的寄存器）来访问其内部变量的属性，就可以很容易的为导入到当前作用域中的闭作用域的变量生成存取指令。

prolj

第3章－符号表
hash表，hash值指向一个符号表项，符号表项用尾指针解决hash值冲突，用作用域层数计数值记录作用域。排列顺序如：［符号，作用域层数计数值，尾指针］。
一个符号栈，有新符号就压栈，每一项就是一个符号表项。
一个块（作用域）栈，用于记录新作用域的起始位置，每一项指向符号表中新一层作用域的起始位置。每进入一个新作用域，就压入一个新作用域的地址，然后设置新作用域的符号表项的作用域层数，如果当前作用域未定义新符号，就把前一作用域的符号表项的作用域层数＋1。退出作用域时－1，若为0就可以从符号表中删除符号表项。

freearth

不错
似乎少了一部分关于pic的。
符号表有一部分我自己没有看明白，什么时候给我讲讲吧。

prolj

原帖由 freearth 于 2008-4-15 14:21 发表
不错
似乎少了一部分关于pic的。
符号表有一部分我自己没有看明白，什么时候给我讲讲吧。

如果我说引用计数，你能明白符号表吗？也可以改成标记清除的。

prolj

第5章

栈指针、帧指针、动态链（指向运行栈中前一帧的开始；或没有使用栈帧指针，指向前一栈帧的末尾；用于当前过程返回时重建调用者的栈帧。或者是一个表示当前栈帧和前一栈帧距离的整数）、静态链（指向最近一次调用的栈帧，用于访问非局部变量，C和Fortran中不需要）、全局偏移表指针（用于多个进程之间共享代码的一个表，以建立和访问外部变量的私有（每个进程的）副本，没有这种情况就不需要）、参数、返回值、频繁使用的变量、临时变量，“竞争”使用寄存器。

局部栈帧的扩展是用alloca()重新分配一块更大的空间，然后把东西都拷过去。这意味着相对sp访问的变量不能由用户寻址，并且这些变量必须是只在拥有该栈帧的过程被另一过程调用悬挂期间所需要的变量。于是相对sp寻址一般用于短期活跃变量、转送给其他过程的参数、跨调用保护的寄存器以及返回值。我们支持alloca()就要用sp和fp，多用了一个寄存器但是指令开销降低，在函数入口只需：1，保存老栈帧在新栈帧中，2，把新栈帧设置为老栈帧的值，3，增加当前栈帧的长度到栈指针。出口相反。

静态链访问非局部变量访存次数多，如果非局部变量访问普遍的话，嵌套层次显示表，把静态链的全部或部分存在寄存器或数组中，前者多使用寄存器达到和访问局部变量相同的速度，后者每个引用多花一个load来读入希望的栈帧指针。如何单独或混合使用又涉及到寄存器分配。
参数传递。传结果，out参数，返回时被调用者向调用者传。传值得结果，inout，双向。传名字，历史了，不再使用。

函数调用过程
调用，1计算每个参数（求值和求址）并放进寄存器或栈，2确定代码的地址（大多数在编译或链接时可以确定），3保存现场（寄存器保存到内存中），4需要的话计算静态链，5返回地址放在某个寄存器中，然后就执行被调用代码。
入口，1保存老栈帧指针，老栈帧指针变成新栈帧指针，重新计算新栈指针，2保存此过程要使用并需要保护的寄存器到内存，3如果需要嵌套层次显示表就构建。
执行被调用代码
出口，1恢复由被调用者保存的寄存器，2有返回值的话就保存到适当的地方，3恢复老栈帧指针，4return
返回之后，1恢复环境，2使用返回值。

参数传递，寄存器，栈，寄存器窗口

PIC，插桩，解析桩。stub。把桩组织成过程链接表，PLT，保留第一个用于调用链接器，第二个标识共享对象，其他桩构造对应子程序的重定位信息。懒惰解析，用到了再解析。

多态，因为要在代码运行时根据参数的类型确定具体的调用，所以多态会增大函数调用的开销。RISC机器一般通过提供分支链接指令和在寄存器中传递参数的办法实现快速调用，并在多数情况下提供了根据一个或多个参数的类型决定分支的快速方法，把一个参数的类型放在一个寄存器中，并转换为相应大小的偏移，再用分支开关表转移到实现对应类型的函数代码。

prolj

第6章－代码生成
语法制导、语义制导，用于生成中间代码比较合适，不要求代码质量多高，尽快emit正确的就行，还顺便类型检查。
树模式匹配的重写和动态规划，twing。其实就是label：pattern［｛cost｝］［＝｛action｝］。无论twing这种top－down还是BURS那种buttom－up。其实LCC的BURS很强大，很优雅，这也是我认为LCC最大的可取之处，当然看那个免费的论文就不用买书了。匹配模式，计算cost，局部最优，重写（覆盖），还有窥孔呢，没事。GCC的RTL也是这么pattern，还有更好的模式，更好的中间表示。
注意，线性代码和树（包括DAG）之间很容易相互转换，所以适用于对方的算法也同样适用于彼方。比如线性代码，操作符是根节点，操作数是字节点，很容易构造森林，扩展成更大的树也很容易。树变成线性很简单了，直接遍历emit就行。

prolj

第7章－控制流分析
控制流分析就是要编译器“理解”程序的控制流
扩展基本块，除入口之外不含其他汇合节点，可以理解为以入口为根的一棵树，对于指令调度，在扩展基本块上的效果往往比基本块上的效果好
后必经节点，必经节点是从前（入口）算，后必经节点是从出口算，从后算。用于迭代分析。
循环首节点之前放一个空节点用于循环不变外提
规约，可规约，就像高数一样，有些运算可以代到一个式子里，从而用更简单的标示来表示该运算。一般来说乱goto是不可规约的

结构分析，区间分析用极大连通区间，而结构分析用极小连通区间。同样构造控制树，把控制流都规约起来，不可规约的区间作为一个节点“规约”（其实只是形式上的规约）。结构分析就是构造控制流图的深度优先树，然后以后序顺序考察各个节点，规约，并蜕化掉边。
对n>=3的区域序列来说，在区域形成之前注意着这个序列的两端，一步就可以蜕化成一块，而每一步只检查第一块，然后追踪前驱或后继，就需要n-1步把他蜕化成n-1块组成的层次。

prolj

第8章－数据流分析
计算in，out等集合，即使看在基本块的入口和出口哪些变量还活着，直接影响寄存器分配
结构分析，配合控制流的结构分析，就是向前或向后计算in、out集合。
我想结构分析用于SSA上效果会更好。

SSA是一种IR形式，而不是优化，插如PHI函数，SSA我觉得EAC讲的最好，手上没拿着书，凭记忆回想，记得是见一个变量就来一个PHI的话会作太多无用功，还是影响其他部分的正常工作。最小SSA是理想情况，代价太大，不合算。剪枝SSA是计算“全局变量”集合，就是个基本块之间存活的变量。半剪枝SSA是剪枝和最小的折衷，不用计算“全局变量”集合，只在每个基本块出入口活着的就插入PHI，虽然某些情况下会造成一些垃圾，但代价很小，还是最实用的形式。SSA转换回来的时候，会产生错误拷贝和交叉引用的情况，解决的方法是检测，引入临界边，加入用于保证正确结果的拷贝，乃至引入临时变量。

mik

不错，加个精支持一把

prolj

原帖由 mik 于 2008-4-19 22:14 发表
不错，加个精支持一把

多谢