鲸书笔记

prolj

第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

第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

第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

第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

看了一个低功耗编译的论文，把概率小的分支降低功耗，前提是CPU提供降频指令。

prolj

第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

第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

鲸书好厚啊，很难啃啊，LZ啃了多久啊

prolj

看了3遍，一天一章。不干别的，专门看它。

陈灌溪

lz做什么工作的？有这么多时间？