周知aes有限域同构于系数为F2域一元多项式环的商环，其理想由不可约多项式m(x)=x^8+x^4+x^3+x+1生成，即F2^8≌F2[x]/(m(x))。这次进一步用域扩张的观点分析，可以得知F2[x]/(m(x))正是包涵m(x)零点的扩域，设为K。那么如何理解？
令I=(m(x))，则K=F2[x]/I，理解关键是找出m(x)在K上的零点，以及K怎样包涵F2？
1. 零点为~x。这里用~g(x)表示多项式在K中的陪集，即~g(x)=g(x)+I，所以~x=x+I。把~x代入m(x)，根据商环定义的加乘运算，代换结果为m(x)+I=~m(x)=~0（~0是K的零元）。那么还有吗？比如~(x+a)（a非0），~x^2，代入这些得到的陪集代表不等于m(x)，所以不是零点。因此零点是唯一的一次多项式x之陪集
2. 构造映射σ，把0对到K中的零多项式即~0，1对到K中的常数多项式即~1，且σ(0+1)=~1=~0+~1=σ(0)+σ(1)，σ(0*1)=~0=~0*~1=σ(0)*σ(1)，又依多项式比较法则得~0不等于~1，故σ是单同态，K包涵F2
小结：商群、商环、商域类似模同余之剩余系，理解这些结构的关键是深入理解等价类、陪集，进而可理解正规子群、理想，最后就是商X之类的东西
posted @
2023-09-07 06:39 春秋十二月 阅读(78) |
评论 (0) |
编辑 收藏1. 输入：前者是二进制可执行程序，后者是高级语言源程序
2. 优化对象：前者主要是直线型代码区域比如踪迹或超块（热点路径代码），超块类似后者中的扩展块；后者是控制流图，即所有代码块，不限于热点路径代码。超块构造类似后者中的基本块放置和过程放置
3. 优化方法：前者要运行时采集剖析数据比如结点剖析和边剖析，再基于剖析数据形成有利于指令cache局部性的超块，然后在超块上作常量传播、常量折叠、强度削弱、复写传播、死代码消除、公共表达式消除等基本优化，也会作指令重排，但考虑到陷阱处理要恢复精确的客户进程状态，因此比较受限，没有后者中的指令重排自由。后者如果基于剖析作优化，那么效果和前者差不多
4. 寄存器分配：都是基于活跃范围的冲突图着色算法，但前者考虑到陷阱处理会延长相关寄存器的活跃范围，而后者不用
————————————————————————
总结：二进制优化所用的技术和编译优化其实相同，不同的是为陷阱处理所作的改变调整，以及运用在热点代码块而非所有块
posted @
2023-09-06 23:44 春秋十二月 阅读(59) |
评论 (0) |
编辑 收藏1. NFA到DFA：设NFA的状态数为n，根据子集构造法，则至多有2^n个状态转移，对每个状态转移，其状态分量至多有n个状态，每个状态计算它的可达状态集合耗时为O(n^2)，另可达状态集合的并耗时为O(n^2)，故一个转移耗时为n*O(n^2)=O(n^3)，则所有转移总耗时为O(n^3*2^n)。由于实际产生的状态数远小于2^n（通常为n），因此耗时为O(n^3*s)，s为DFA实际具有的状态数
2. DFA到NFA：转化方法是修改转移表，对每个状态转移的目标状态加上集合括号（因NFA对特定输入可能有多个目标状态，故为集合），若转为£-DFA，则还需对每个状态增加对£的转移为空集。该方法耗时为O(n)，n为DFA的状态数
3. DFA到正则表达式：设DFA状态数为n，根据递推公式R(i,j,k)=R(i,j,k-1)+R(i,k,k-1)R(k,k,k-1)^*R(k,j,k-1)（1<=i<=j<=n，0<=k<=n）来逐步构造表达式，最终的表达式就是所有R(1,j,n)的并，其中j为可接受状态。该过程会产生总共n^3+n^2个表达式，每次k递增导致表达式长度增为4倍，故总耗时为O(n^3*4^n)。另一种更快的方法是消除所有除初始和接受状态外的中间状态，每次消除一个，就合并其前驱经过它到其后继的正则表达式和前驱直接到后继的正则表达式，因前驱或后继至多n-2个，则共有(n-2)^2个前驱到后继的直通边，且中间状态至多n-2个，故耗时为O(n^3)；最后合并各接受状态的正则表达式，因接受状态至多n-1个，故耗时为O(n)。故总耗时为O(n^3)
4. 正则表达式到£-NFA：作词法分析，对每个终结符号构建状态结点及转移边，即子£-NFA，特定符号对应用并、连接、闭包、结合之一联合已构建的子£-NFA，耗时为O(n)，n为正则表达式的长度
posted @
2023-09-06 23:42 春秋十二月 阅读(59) |
评论 (0) |
编辑 收藏1. 三条定律：交换律、结合律、吸收律（对于半格是幂等律），吸收律包含了幂等律
2. 上下界：交半格每对元素都有唯一最大下界，并半格每对元素都有唯一最小上界，格每对元素都有唯一最大下界和唯一最小上界
3. 格定义一个偏序，偏序有三个性质：自反性、反对称性、传递性
4. 格与偏序的关系：每个格对应一个偏序，但不是所有偏序都对应一个格，要满足每对元素都有唯一最小上界和（或，对于半格）唯一最大下界。如果集合中的任何一个子集（包括空集）均存在最小上界和最大下界，那么对应一个完备格
5. 任何元素有限的格都是完备格，格中的交运算和并运算对于其定义的偏序来说是单调的
6. 格的乘积、和、提升、映射仍然是格，利用这个性质，可以在已有格的基础上增量地构造描述能力更丰富的格，这种技术称为论域精化，是提高程序静态分析精度的重要指导思想之一
posted @
2023-09-06 23:39 春秋十二月 阅读(443) |
评论 (0) |
编辑 收藏周知cpu为方便乱序执行，内部会使用重命名寄存器技术消除数据依赖（war和waw）。编译器在如下场景也会用到重命名
1. 静态单赋值。过程内的每个变量唯一定义一次，原有相同的则会重命名，包括phi结点的定值
2. bb表调度。为消除反相关依赖即war，可以重命名读操作使用或写操作定义的值，这样能调度产生总时钟周期更少的指令序列，但可能增加寄存器压力导致溢出而新增了长延迟操作（内存加载/存储）并迫使另一轮调度
3. ebb表调度。对于某一ebb的一条路径p，p存在过早退出路径pe，p和pe的公共前缀是基本块b，当调度p时，如果某个操作i向后移动到b，且i定义的值杀死了pe上的同名值，那么需要重命名i的定值。若i的定值被重命名，且其在p的出口处是活跃的，则调度器需要在出口处复制回原来的名字
4. trace表调度。踪迹不同于ebb路径，它允许中间存在多个前驱即入口的基本块，而后者不能。当调度存在多入口的块b的某踪迹t时，t上的某操作i可能前向移动跨越b（t外的代码路径需作补偿），若i杀死了一个活跃范围跨越b的值，则需要重命名i的定值；同理，若i向后移动跨越b且杀死了t上的某值，则需重命名i的定值，这时t外的代码路径补偿可以使用同一名字
posted @
2023-09-06 23:35 春秋十二月 阅读(57) |
评论 (0) |
编辑 收藏1. 不可达代码是指无论输入什么都不会执行的代码，对过程而言，即是从入口基本块到不了（没有路径可达）的那些基本块；死代码是指可达但计算了后面任何可执行路径都不会使用其计算结果的代码，比如死变量和死指令
2. 不可达代码的识别本质是有向图的可达性判定与传递闭包计算问题，一般用DFS法处理。先找到从入口基本块不可达的基本块，再删除（同时改变其前驱和后继基本块的指向），直到找不到为止。死代码的识别可用活跃分析或必要指令标记法，对于活跃分析，删除基本块出口不活跃的变量定值，以及它所使用不活跃操作数的定值；对于标记法，从必要指令出发，根据def-use链和use-def链，不断标记对其操作数有贡献的指令，最后删除没被标记的那些指令
3. 不可达代码和死代码可能来源于程序员，更可能源于编译器的其它一些优化产生，删除优化它们能显著减小代码体积，对执行速度有间接的影响，因为可能改善指令高速缓层的利用率
posted @
2023-09-06 23:33 春秋十二月 阅读(85) |
评论 (0) |
编辑 收藏1. 目的是识别循环中那种在每个迭代都产生相同值的计算，并将它们移到循环之外。注意，如果一个计算出现在嵌套循环内，对外循环的特定迭代而言，内循环的每个迭代都产生相同的值，但外循环的不同迭代产生不同的值，那么这种计算将移到内循环外，而非外循环外
2. 识别循环不变量可以基于数据流分析求得的use-def链，一条指令是循环不变的，当它的每个操作数满足以下条件之一
a）该操作数是常数
b）该操作数的所有到达定值在循环之外。因为若有一个在循环内，则该指令就可能是循环变化的，除非那个定值是循环不变量
c）该操作数只存在一个为循环不变量的到达定值，且该指令之前没有对其左部变量（若有）的使用。因为若有多个这样的定值，则该指令就可能是循环变化的，除非多个定值结果都一样；因为若前面有对其左部变量的使用，则该指令的赋值就杀死了左部变量的初值，这样外提后左部变量第一次迭代就会使用错误的定值
3. 由于以上条件没考虑到控制流分析，不能保证循环不变量在每个迭代中执行，以及循环不变量之左部变量的所有使用都是相同的值。因此为了保证外提后的代码行为正确，还需要满足条件：循环不变量所在基本块必须是循环中所有使用了其左部变量的基本块和所有出口基本块的必经结点。当外提循环不变量后，考虑到循环有可能执行0次即一开始就不满足循环进入条件，可以用是否进入循环的测试条件来保护前置块，即识别终止条件是否一开始就为false，来保护它。这种方法总是安全的，但增加了代码体积。不过若终止条件恒为true或false，则常数传播分析会删除这个冗余测试，如果为false，那么还会删除前置块
posted @
2023-09-06 23:30 春秋十二月 阅读(48) |
评论 (0) |
编辑 收藏叶调用优化与收缩包装
1. 叶调用优化适用于被调者是不调用任何过程的过程之场景，这种过程叫叶过程
2. 有几种可能的优化
a）如果过程的实现使用display数组来寻址非局部变量，那么叶过程可避免在起始代码序列中更新display数组
b）如果叶过程内不使用由被调者保存的寄存器（寄存器分配器应设法优先使用由调用者保存的寄存器），那么可避免起始代码序列中保存代码和收尾代码序列中恢复代码。很小的叶过程很可能不使用到被调者保存的寄存器，只使用部分调用者保存的寄存器的叶过程，那么调用者也可以避免一部分寄存器保存与恢复代码
c）如果调用者有很多次调用叶过程，而且两者代码同时可见，那么叶过程不必自己分配栈帧，由调用者一次性分配好
3. 收缩包装是叶调用优化的一种推广，目的是尽可能去掉过程起始代码序列和收尾代码序列中实际没用的寄存器保存恢复代码。可以先用数据流分析来计算每个基本块的保存寄存器集合（基本块入口可预见但其前驱不可预见且入口不可达的那些寄存器）与恢复寄存器集合（基本块出口可达但其后继不可达且出口不可预见的那些寄存器），再在保存寄存器集合非空的基本块入口处插入save指令（插入点已是最早的合适的位置），恢复寄存器集合非空的基本块出口处插入restore指令（插入点已是最晚的合适的位置）
尾调用优化与尾递归删除
1. 尾调用优化的条件是两个（不同）过程编译时同时可见，比如处于同一编译单元，或调用者有足够多的、使得优化可能发生的关于被调用者的信息
2. 尾调用优化的实现，因为被调者返回后代码序列到调用者收尾代码序列之间不存在有用计算，所以原来标准链接处理要保存的那些寄存器不可能活跃，首先要裁剪调用前代码序列即不保存由调用者保存的寄存器和不压栈返回地址，以及裁剪被调过程的起始代码序列即不保存由被调者保存的寄存器和不分配新栈帧（借用调用者的栈帧，若被调者的栈帧比调用者的大，则需按两者之差扩展栈帧），然后转移到被调者裁剪过的起始代码序列，最后修改被调过程的收尾代码序列：正确释放栈帧，比如用帧指针赋给栈指针，使之直接返回到调用者的调用者（比如o调用p，p调用q，q是尾调用，那么优化后q实际返回到o）。综上可得，尾调用优化减免了压栈返回地址与保存寄存器的开销
3. 尾递归删除是尾调用优化的一种特例，由于调用者和被调者是同一过程，因此不存在扩展栈帧和额外释放栈帧，只须改变参数及跳转到过程入口处即可
posted @
2023-09-06 23:23 春秋十二月 阅读(53) |
评论 (0) |
编辑 收藏1. 数学基础：两者的共同点是都基于数据流值的半格和对组合运算封闭的传递函数，不同点是区域分析算法还要求传递函数是一个半格，不仅支持组合运算，而且支持交汇运算和闭包运算，交汇运算用于把有相同后继的不同执行路径组合起来，闭包运算用于环上（比如循环）执行零到多次的效果
2. 流程：迭代算法由初始化和循环求不动解组成，以前向数据流为例，其中初始化包括初始化入口基本块的out集合为合适值，其它基本块的out集合为半格的顶元素；循环求不动解遍历除入口外（因为入口的out不会变）的每个基本块，计算其out集合，直至所有基本块的out不再改变。区域分析算法由计算层次区域序列、构造区域传递函数和计算各区域入口值组成，计算层次区域序列自底向上，基本块为叶子区域，自然循环分为循环体区域和循环区域，都是内部区域，不是自然循环的整个流图为根区域；区域传递函数有2个，一是R区域入口到其直接子区域S的入口的数据流值传递，记作Fin(R,S)，另一是R区域入口到其直接子区域出口基本块B（可能有多个）出口处的数据流值传递，记作Fout(R,B)，区域传递函数的计算自底向上，对于叶子区域，Fin是恒等函数，Fout和迭代算法的传递函数一样，取决于具体数据流问题；对于更大的区域（非叶子区域），遍历每个子区域，Fin由所有Fout(R,B)交汇而成，B为S在R中的前驱，若R为循环区域，则再求Fout的闭包，遍历S的每个出口基本块B，Fout由Fout(S,B)和Fin(R,S)组合而成。计算各区域入口值自顶向下，根区域的In值等于流图入口的In值，其它区域S的In值等于Fin(R,S)，R为父区域，所有Fin在前一环节已构造好
3. 结果：对同一数据流问题比如到达定值，两种算法求得的数据流值是一样的。为什么区域分析算法是正确的？因为它实际是按照程序控制流来构造传递函数的，包含了所有可能执行路径数据流值传递的效果，这相当于迭代算法求不动解的过程，所以最后只要一个流图的入口值，就能算出各区域的入口值。为什么迭代算法是收敛的？因为半格是单调的且高度有穷。收敛速度取决于遍历基本块的顺序，如果按基本块深度优先排序（逆后序）遍历，那么迭代轮数不超过流图的深度（各条无环路径后退边的最大数）加2
4. 区别：迭代算法用于可归约流图和不可归约流图，区域分析算法仅能用于可归约流图
posted @
2023-09-06 23:18 春秋十二月 阅读(67) |
评论 (0) |
编辑 收藏1. 作为指令高速缓层优化的一种重要技术，它根据CFG流图边的执行频率将频繁执行的基本块排列在一起，并布局那些基本块在下降分支路径，而不在一起的也就是很少执行的基本块布局在转移分支路径。这样做一来可以使取到I-cache中的指令实际被执行的比例较高，二来对于某些体系结构上转移和下降路径延迟不等的分支指令，可以降低跳转延迟
2. 实现过程内代码置放有以下几个环节：
a）获取剖析数据：编译器可以先在基本块出口处插入代码以统计到其后继基本块的执行次数，作为CFG流图边的权重，然后编译生成可执行文件，输入代表性数据运行它，结果输出一个数据文件，用于第二次编译，这次编译实施过程内代码置放优化
b）以链的形式构建热路径：热路径是CFG路径的一个集合，其中包括频繁执行的那些边，每条路径是一个或多个基本块按边的方向构成的链，每个链关联一个优先级，用于布局代码的先后顺序。初始时，每个基本块构成一个只有它本身的链，其优先级为CFG流图边的数量或者更大值；接下来，在CFG中按权重降序遍历每条边<x,y>（x不等于y），若x是某个链a的尾结点且y是某链b的头结点，则把b合并到a后面，更新a的优先级为a原来优先级、b优先级、P三者的最小值，同时递增P，其中P为链合并操作的计数器，用于决定链的相对次序由低到高排列，初值为0。当遍历结束时，所有热路径构建完成
c）进行代码布局：经过前一环节，就得到了链的集合。首先从链集合找出含有入口基本块的链t，将t加入工作表WL；然后从WL移出一个优先级最低的链c，按序（构建链时加入基本块的顺序）遍历c的每个基本块x，把x放在过程可执行代码体的末端，对于边<x,y>，将包含y的链t加入WL（若t不在WL中），重复该过程直至WL为空
posted @
2023-09-06 23:15 春秋十二月 阅读(45) |
评论 (0) |
编辑 收藏