Chinaunix

标题: 鲸书笔记 [打印本页]

作者: prolj 时间: 2008-04-15 09:53
标题: 鲸书笔记
第3章－存储绑定
全局变量和静态存储变量一般存储于内存中，相对于一个基址寄存器（全局指针）的偏移。全局栈变量和栈变量，相对于栈指针、帧指针的偏移。
分配在堆中的变量通过指针访问。
分配伪寄存器来存储栈（全局）变量，以后再染色处理。

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

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

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

作者: freearth 时间: 2008-04-15 14:21
不错

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

作者: prolj 时间: 2008-04-16 18:05

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

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

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

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

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

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

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

作者: mik 时间: 2008-04-19 22:14
不错，加个精支持一把

作者: prolj 时间: 2008-04-21 10:35

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

多谢

作者: prolj 时间: 2008-04-21 12:46
第9章－依赖关系分析
控制依赖，控制流流动的顺序
数据依赖，在并行优化中相当重要，可以说就是中心。又分为真依赖、反依赖、输入/输出依赖
构建依赖图
基本块依赖DAG，基本块中因为没有循环，所以依赖图是DAG
寄存器/存储器依赖，计算依赖关系时，其他条件当作寄存器看待
资源向量是否重叠？交集计算。然而确定有限自动机计算的更快，状态是类似资源的集合，指令是状态转换。这样可以用查表代替循环，前端的理论和技术用上了

构造DAG，按顺序处理每条指令，有冲突的放进conf集合，conf为空的就是root节点，不为空的每条指令都有一条到root的边，权值是等待时间。当然如果能改进这个O(n^2)的算法就太好不过了
有些依赖是循环携带的，有些循环无关
PDG是一种IR，好象是DEC的人提出来的，由一个CDG个DGD组成。PDG的好处在于，对于控制依赖于同一节点的所有节点，没有数据依赖的就可以并行执行。以程序谓词为根节点和中间节点，非谓词为叶节点的DAG，执行中，当谓词被满足才能到达叶节点。
n到出口都经过m，m就是n的后必经节点。
存在一条m到n的控制路径，n是该路径上除m之外的每个节点的后必经节点，并且n不是m的后必经节点，n就控制依赖于m。（想起我的高数老师，给我讲这些存在、唯一什么的，她儿子和我一样大，对我特别好，虽然是课代表但是不太认真学，现在越来越体会到对我恨铁不成钢的用心了）
在CDG上加入区域节点、再增加一个start虚构谓词节点，“Y”边指向入口，“N”边指向出口，然后在此图上构造后必经关系。
区域节点的作用就是把谓词关系和相应节点组合在一起。

作者: prolj 时间: 2008-04-23 19:19
第20章－存储层次优化
硬件预取对于D-Cache和I-Cache都可以用
I-Cache的硬件预取，在Tpref个时钟周期时位置放一条预取指令，Tpref是满足预取需要的时间。是否需要预取一个代码块，取决于该块之前t个周期位置上的一个条件，将预取指令放在需要此代码的路径上那一点回退min(Tpref, t)个时钟周期的位置上。
D-Cache的硬件预取，预取并不会减少从内存到cache的延迟，只是错开这个延迟。但是我们容然希望重复使用已经在cache中的数据来减少延迟，而不仅仅是错开延迟
过程排序，把，callee和caller方在一起，这里假设callee和caller在时间上很近，把频繁使用的以冲突较小的方式放置，LTO，对于现代的模块化开发的优化来说可以提高不少效率。需要profile，如果不能profile就用启发式，就是相互频繁调用的放在一起。
无向静态调用图，每一条弧标有它两端一个调用另一个的次数。两个过程之间可能存在两个方向的调用，并且每个调用相应的有一个返回，所以使用无向图。瓦解之，每一步选一个权值最高的边，合并两个结点为一个，并合并边，两个边的权值之和是新边的权值。链接时，被合并的节点放在一起，权值表示他们的相互顺序。
修改ld，每个子程序放在cache的边界
过程内，把不频繁执行的分支放到外面，拉直代码
区分主要过程和次要过程
内联还是有争议的
ps，记得第一次找工作被人问起profile，说自己只用过一点profile，当时不是很懂也不是很关心优化，现在才明白profile多么重要。
标量替换，用标量替换带下标的变量，从而改善寄存器使用，也叫寄存器流水，寻找重用数组元素的机会，用标量临时变量的引用代替重用，减少访存，对D-Cache也有效果。对嵌套循环也会起到很好的效果。
循环交换和循环合并对标量替换有正面作用，循环交换可以使循环携带的依赖是最内层循环携带的依赖，循环合并把一个或多个数组元素放在一个循环中，从而增加标量替换的机会。

作者: prolj 时间: 2008-04-26 19:43
第10章－别名分析
收集别名，P是一个程序点，即两条语句之间的点，在流图中P标示一条边。enrty+和entry-分别是入口点和出口点。stmt(P)表示流图中唯一先于P的语句。x代表一个标量变量、数组、结构或指针等，memP(x)表示在程序点P和对象x相连的抽象存储单元。star(o)表示由语言对象o占据的静态或动态分配的存储空间。anon(ty)表示类型为ty的对象分配的“匿名”动态存储空间，anon表示过程中所有动态分配的存储空间。
ovrP(x)＝在程序点P可能和x重叠的抽象存储单元集合
ptrP(x)＝x在程序点P可能指向抽象存储单元集合
refP(x)＝在程序点P通过x开始的任意多层引用可能到达的抽象存储单元集合
ref(x)＝通过x开始的任意多层引用可能到达的抽象存储单元集合，程序点无关
C语言14条
别名传播
实在写不下那种式子，别名分析在LLVM中是很重要的一部分，以后会详细分析。

作者: prolj 时间: 2008-04-26 19:45
第12章－前期优化
常数折叠，和词法分析一样，最好作为可以随时别调用的可重入函数，不需要数据流分析，GCC由于某些原因在语法分析的时候顺便把常数折叠就做了。通常不希望前端进行优化，因为一个编译架构总会有不同的前端，我们总是希望优化是集中进行的，而不是混乱的各自为政。
浮点运算总是优化的重要之处，因为现在的CPU都是构建在整数的基础之上的，浮点是加上去的。对于浮点常数折叠必须保证编译时的浮点运算和目标机器一致！模拟是曲线一致。不谈激进，编译起在优化时和不优化时得到的结果应该是一样的，safe不是保守，GCC曾经就有浮点运算的bug，不知道现在的情况如何了。
常数折叠和冗余删除是不一样的，它用一个值代替所有的表达式，编译时确定值，而冗余删除却是在运行时，而且必须有一个表达式被运算。
聚合量标量代替，相当简单，但是有效！最好在优化的早期进行，因为它能够创造更多的优化机会。而且不需数据流分析！
能够使其他优化作用于聚合对象，如C语言的结构。
判断聚合对象哪些分量具有简单的标量值，然后把这些分量赋给和它的类型一样的临时变量。
这种分量就成了寄存器分配、常数和复写传播，以及其他用于标量优化的候选对象。
可以是局部的，也可以在整个过程中进行，区别循环效果更好，因为可能出现符合这种优化条件在循环内满足，全局不满足的情况。
代数化简和重组，不需数据流分析，最好也和词法一样，可调用的函数，灵活使用。而且相当重要。
代数化简，啊哈！消去！我想我最喜欢的算术作业就是可以轻易消去的，虽然我喜欢看起来混乱而复杂的方程。重组，结合律、交换律、分配律，小学的东西也是有用的。这并不表明小学数学对于CPU来说是多么简单。EAC的作者说，遗憾的是很少编译器达到小学数学水平，好象是04年的书，作者希望学生可以修改ORC或GCC加入优化遍或者改进后端移植，令人兴奋的是LLVM支持a+b=b+a诸如此类的变换，还真不容易！
溢出，CPU的极限，在实现的时候要很注意。
地址表达式的代数化简和重组，是一种特殊情况，溢出不会造成计算结果的不同，也很少被使用。97年为止，对地址的运算最重要的是结合律、交换律和分配律组成的重组方法。我们可以肆无忌惮的进行转换，在编译时确定地址计算的常数表达式的值，放大和简化循环不变表达式，并作一些强度削减。
简化地址表达式的一般策略是‘规范化’，把它们转化为乘积之和，然后用交换律把常数部分和循环不变部分‘合并’
化简地址计算表达式施加在树上比LIR上要显得直接，线性IR和树是对应的，和在代码生成部分我提过。
把地址计算的IR收集到一起，成为一棵树，其根代表结果地址，然后对该树进行各种代数变换，使之成为乘积之和的规范形式(其中一项或两项(都)是常数分量之和)，交换律用于收集常数分量(一般位于左节点)
对待当前上下文(循环)中是常数值而更大范围内不是的分量必须小心！
浮点方面不太明朗的规定使得优化难以进行，是一个尚待开发的
值编号，是判定两个计算是否等价并删除其一的N种方法之一，需要数据流分析，和公共子表达式删除、常数传播不同，值编号是从形式上识别等价的表达式，并删除冗余的，减小后续工作的工作量。
基本块内值编号，用hash对要计算的表达式分类，如果表达式的指令如if i+1 goto L1，不是赋值指令，我们将其分解为t1=i+1，if t1 goto L1。表达式都在按hash值分类的序列之中后我们就可以用表达式左端的变量代替表达式。hash和表达式匹配函数要考虑交换律。
如果定义他们的计算的运算符相同(或相同的常数值)，并且操作数相重合(相同类型的)，就称两个变量是相互‘重合的’
全局值编号需要在SSA上运作，并定义成为值图的结果流图，用必经边界方法构造最小SSA，过程的值图是一个带有标志的有向图，节点上的标志是运算符、函数符号或常数，边表示生成赋值，并从运算符或函数指向它的操作数，边上标明的自然数是每一个操作数相对给定函数或运算符的位置。
然后重新定义‘重合’，1它们是相同的节点(SSA中情况)，2它们的标志是常数且内容相同，3运算符相同，且操作数是重合的。
如果两个变量是重合的，并且定义它们的赋值是P点的必经节点，则它们在程序点P是等价的。
计算重合关系为的是对值图所执行的划分处理的最大不动点。开始，假定具有相同表好的所有结合点是重合的，然后根据一个划分各个成员的操作操作数是否重合来重复划分重合类，直到得到一个不动点，这个不动点是最大不动点。EAC的作者Cooper和Simpson的算法施加于SSA的强连通分量，并结合hash和全局方法的有点，还是要参看一下EAC，毕竟是作者在鼎盛时期的著作，又是‘最新’的。
复写传播，也需要数据流分析，对于x=y，以后出现x的地方都用y代替。复写传播和寄存器合并有相似之处，只要是针对已用寄存器代替了标识符的LIR的优化，这两种优化的效果是相同的。但是，寄存器合并使用的是冲突图，而复写传播使用的是数据流分析，复写传播可以在任何级别的IR上进行。
复写传播也可以分为局部和全局的，和尾融合的次序要配合好。复写传播可以再次减少代码量。
稀有条件常数传播，需要数据流分析，是一种转换，x=c，c是常数，以后用常数c代替x，和复写传播如此相似！但更为复杂！因为它要通过利用值为常数的条件判断路径是否会被执行，要做‘符号执行’。
所有的RISC都提供小整数操作指令，常数传播把小整数转移到使用它们的地方，因此对RISC机器是很重要的。MIPS使用寄存器和一个小整数之和的寻址方式，但没有两个寄存器之和的寻址方式，把常数传播到这种地址结构既节省了寄存器也节省了指令。更通常的，常数传播减少了过程需要的寄存器个数，增加其他优化(常数传播、归纳变量、cache优化的依赖关系分析一些转换)的机会。
构造最小SSA，然后用流图的边来传递信息实现程序的‘符号执行’，只有节点的执行条件满足时我们才标识它为可执行的，并且每一步只处理可执行的点。

作者: prolj 时间: 2008-04-26 20:07
看了一个低功耗编译的论文，把概率小的分支降低功耗，前提是CPU提供降频指令。

作者: prolj 时间: 2008-04-27 13:04
第13章－冗余删除
公共子表达式删除和循环不变代码外提的组合将会被部分冗余删除慢慢取代，就像结构分析取代必经节点和迭代分析的组合一样，当然一切取决于你，万事并非绝对，也许你会有更好的理论和算法！
代码提升，又叫统一，寻找在某点之后总是被计算的表达式，并把它们移动到总能被计算的一个最晚点，对于代码的影响取决于它对指令调度、I-Cache或其他什么因素的影响，这是一种人们心理上的改善，但是效果还不明朗。
从一个给定点开始无论什么路径都被计算的表达式被称为在那一点‘非常忙’，需要向后数据流分析，定义EVAL(i)是这种表达式的集合，在基本块i中这些表达式被计算，并且计算位于基本块内对它的赋值操作之前，KILL(i)是被基本块i杀死的表达式集合。
在基本块的入口和出口的非常忙表达式集合VBEin(i)=EVAL(i)U(VBEout(i)-KILL(i)),VBEout(i)=n j属于Succ(i) VBEin(j)
和数据流分析一样，用位向量。
重组能显著增强所有形式的冗余删除的适应性和效果！你总能发现各种分析、优化措施的不同组合会带来很大的惊喜
部分冗余删除结合了全局公共子表达式删除和循环不变代码外提并做一些额外的改进。Cooper把部分冗余删除和全局重组、全局值编号结合在了一起，改善了效果，然后又通过SSA形式对值操作而不是对操作符操作进一步改善了它。
部分冗余删除寻找在流图的某个路径上被多次计算的表达式。现代版本以懒惰代码移动为基础，懒惰总是受欢迎的，减小寄存器压力，在文件系统和存储管理上也很受欢迎。
关键边，是连接一个具有两个以上后继的节点和一个具有两个以上前驱的节点的边。在执行数据流分析之前对流图中的关键边进行了分割，是部分冗余删除收效最大保证。

作者: prolj 时间: 2008-04-27 13:05
第14章－循环优化
对于嵌套循环，从内而外的处理。首先要说消除不必要的边界检查，也可以作用于循环外优化，但优化的机会不如循环内多。简单的说就是while循环变成do循环。
归纳变量，的最简单形式是在程序的某部分(一般是循环)中，其后继形成一个算术级数的变量。归纳变量的效果可以通过常数传播进一步改善。
识别归纳变量，为了更容易识别，分为基本归纳变量和依赖归纳变量。基本归纳变量是循环中每一次迭代显式的加减一个相同的变量，依赖归纳变量是，i是基本归纳变量，N*i+M就是依赖归纳变量。
开始把所有的变量都候选，给找到的每一个归纳变量j确定一个j=b*biv+c的线性方程，biv是基本归纳变量，把j和循环内biv联系起来。其线性方程中具有相同基本归纳变量的归纳变量组成一个类，这个基本归纳变量叫它们的基。依次查看循环体内的指令，寻找在循环中是i=i+d或i=d+i形式的赋值的变量，其线性方程为i=1*i+0，且i是基。接着重复考察每一条指令寻找出现在赋值(诸如j=i*e; j=e*i; j=i+e; j=e+i; j=i-e; j=e-i; j=-i这些形式)左边的j，i是基本归纳变量的话j属于i类，否则传递属于i的基i1的类。对依赖归纳变量还要检查1，对i的赋值和对j的赋值之间没有对i1的赋值，有的话有可能影响j和i1的关系，使j根本不是一个归纳变量。2，i必须没有循环外定值到达j，可用du链检查。
强度削减，就是用加减代替乘除，乘法代替指数之类的。
活跃变量分析，你会发现我们总在为寄存器分析变量的死活。
归纳变量删除和线性函数测试替换，出了对归纳变量削减强度之外我们还能完全删除它们，1作者疏忽，定义了变量却不使用，2转换的副产品，3在一次强度削减中创建，在另一次中变得无用，4变量只用于循环结束的测试，并可以被上下文中其他归纳变量代替，这种情况称为线性函数测试替换。
情况1，简单的del就行了。情况2，发现归纳变量可以删除。情况3，引入tmp变量。情况4,活跃分析。

作者: run_xiao2000 时间: 2008-05-04 11:14
鲸书好厚啊，很难啃啊，LZ啃了多久啊

作者: prolj 时间: 2008-05-05 12:23
看了3遍，一天一章。不干别的，专门看它。

作者: 陈灌溪 时间: 2008-05-05 17:27
lz做什么工作的？有这么多时间？

作者: nicolas.shen 时间: 2008-05-08 17:02
真羡慕你！有那么多时间看书！加油看啊！

作者: prolj 时间: 2008-05-09 20:56

原帖由 陈灌溪 于 2008-5-5 17:27 发表
lz做什么工作的？有这么多时间？

对于你的ID，不予回答。我在菜市场捡剩菜叶子的，你信不？

原帖由 nicolas.shen 于 2008-5-8 17:02 发表
真羡慕你！有那么多时间看书！加油看啊！

最近比较忙，以后把剩下几章补上，比较关键，但不是很难。踏下心来看，谁都可以。
先忙过这一阵子，把Verilog用ISE或Cadence IC编译出来。

作者: 以泪洗面 时间: 2008-05-10 15:55
好贴当留言，嘿嘿！！！

作者: dirtysalt 时间: 2008-05-17 10:25
标题: 回复 #8 prolj 的帖子
看书的不算，写出来才真猛……。哈哈，不过看懂也确实需要一番努力，不过真正编写的时候才会发现很多问题并且加深影响。

LZ又没有看到循环优化，那里面首先就给了一个假设，说for(i)在循环体里面不能修改i
而且里面的MIR也没有考虑到类型。真正编写的时候还有大把问题要考虑啊。
不过作为一本深入具体技术的原理书，这本书不仅算是合格甚至可以说是优秀。

作者: prolj 时间: 2008-05-19 10:47
第15章－过程优化
这个优化就是为了减少过程调用的开销。

尾调用优化，检查一个函数调用另一个函数执行完之后唯一的事情就是返回自己，把两(多)个return合并成一个。有足够的寄存器来保存帧栈，考虑机器的调用决定。
过程集成，就是内联，内联现在都是程序员建议，编译器决定，跨编译单位的内联代价很大，不太值得去做。小过程值得内联，很少被调用（最好是1次）的过程值得内联，内联在循环内被调用的过程可能会创造其他优化的机会，含有1个以上的常数参数的过程内联效果很好。内联主要处理调用约定、命名冲突和静态变量。
过程内嵌，就是内嵌汇编。
叶过程优化，对于一个调用树，叶过程总是占总数一半以上，消除调用，额外的寄存器保存帧栈。

作者: prolj 时间: 2008-05-19 10:48
标题: 回复 #24 dirtysalt 的帖子
循环优化是14章，不过现在循环优化一般软流水效果比较名显。

作者: prolj 时间: 2008-05-22 13:44
标题: 剩下的有个小样，很累，不想写了，看书很容易，喜欢的朋友们用心看啊
第16章－寄存器分配
K类K色，NP。

第17章－代码调度
代码调度对于乱序执行的机器的确不是那么重要了。

分支的时候尽可能用有用的指令填充延时槽，不得已用nop。
超标量，有使用贪婪算法调度的，尽可能用就绪指令填充有效指令槽，Intel的硬件好像有同样的功能。
前瞻，向前看，有些机器有预取指令的指令。
软流水，通常能很明显的改善代码质量！1倍以上！循环展开，大家熟知的。寄存器重命名，对于write after write的冲突也是必要的，。层次归约，用于含有控制结构的循环（这种代码早该优化掉），一部分处理条件，处理循环的那部分从最内层进行，把处理过的循环归约成单个节点。

第18章－控制流和低级优化

第19章－过程间分析与优化
模块化设计，针对程序员习惯的改变而进行的优化。LLVM的强项就在于过程间优化和LTO，LTO需要全局的信息，计算量很大，实现起来非常困难，但是LLVM借助其良好的IR设计在1.0的时候就实现了LTO！
过程间控制流分析，调用图，
过程间数据流分析
过程间常数传播，
过程间别名分析
过程间优化
过程间寄存器分配
全局引用的聚合

作者: prolj 时间: 2008-05-22 16:26
这个也没心思写下去了，其实很简单，一会儿功夫就弄明白了

llv.tar

10 KB, 下载次数: 72

作者: miki922 时间: 2008-05-23 10:22
哎呀。。好东西。。谢谢楼主分享！！！！

作者: prolj 时间: 2008-07-08 23:40
第二遍仔细看lcc了，没时间整理文档了，开了个头，先放在吧。

lcc.tar

10 KB, 下载次数: 74

作者: beepbug 时间: 2008-07-11 06:30

原帖由 prolj 于 2008-4-15 09:53 发表
第3章－存储绑定
全局变量和静态存储变量一般存储于内存中，相对于一个基址寄存器（全局指针）的偏移。全局栈变量和栈变量，相对于栈指针、帧指针的偏移。
分配在堆中的变量通过指针访问。
分配伪寄存器来存 ...

这个“全局栈变量”是什么东东？第一次看见。

作者: prolj 时间: 2008-07-11 08:09
标题: 回复 #31 beepbug 的帖子
我也是第一次见，可能是main的栈或者别的语言吧。

作者: cjaizss 时间: 2008-07-11 09:39

原帖由 beepbug 于 2008-7-11 06:30 发表

这个“全局栈变量”是什么东东？第一次看见。

怀疑是高级语言（自然不是C语言），编译/解释它的时候，把它的一些全局东西放在栈上，是一种编译/解释的手段

作者: lxbkey 时间: 2008-07-21 21:03
来求水了。

作者: arust 时间: 2008-07-31 17:32

原帖由 prolj 于 2008-5-5 12:23 发表
看了3遍，一天一章。不干别的，专门看它。

我要向你学习

作者: gigabyte 时间: 2008-08-01 11:49
没有看过此书，准备买本来看看

作者: c/unix 时间: 2008-12-01 14:45
提示: 作者被禁止或删除内容自动屏蔽

作者: zenglei421 时间: 2009-06-14 21:29
标题: 回复 #37 c/unix 的帖子
什么书呀？

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)