麻省理工学院 电气工程与计算机科学 6.035,2005年软 分爱资料10—练习测试2 11月11日，星期五 1对优化命名 对于基本块： a-l b-2 c-3 d同+x e=bec f-e g寸 g-dty amb+c 对执行上面优化的下面基本块进行表运： ●常熟传播折叠 ●复制传播 ●通用子表达式消除 ●死代码消除 (ak=I b-2 =3 d-atx embtc f=e g-diy a-b+e b)a-1 b=2 c-3 d-a+x
麻省理工学院 电气工程与计算机科学 6.035，2005 年秋 分发资料 10——练习 测试 2 11 月 11 日，星期五 1.对优化命名 对于基本块： a=1 b=2 c=3 d=a+x e=b+c f=e g=f g=d+y a=b+c 对执行上面优化的下面基本块进行表述： ● 常熟传播/折叠 ● 复制传播 ● 通用子表达式消除 ● 死代码消除 (a)a=1 b=2 c=3 d=a+x e=b+c f=e g=d+y a=b+c (b) )a=1 b=2 c=3 d=a+x
e=bte f-e 多寸 g-dty a-1 (c))=l b-2 c-3 d中1+x e-5 f-5 g=5 8-diy a=5 (da】 b=2 c-3 d-a+x e=btc f-e g℃ g-dty a-bic 2.死变量分析 对于每个程序点，死代码分析决定了围饶在给定控别流图计算不再需要的一系列变量，死变 量即在违背重新指银值之前不会再用到的变量，可以假设所有的变量都是局部的并且死变量 从CFG中退出. (a)死变量分析是散向还是后向的题据流可题？ (b)N和OUT集表示哪些成员？集成员是零或者一，意味着什么？ (c)初始化条件是什么？(N或OUT相似的初始值) (d)什么是交汇操作数？
e=b+c f=e g=f g=d+y a=t1 (c) )a=1 b=2 c=3 d=1+x e=5 f=5 g=5 g=d+y a=5 (d) )a=1 b=2 c=3 d=a+x e=b+c f=e g=e g=d+y a=b+c 2.死变量分析 对于每个程序点，死代码分析决定了围绕在给定控制流图计算不再需要的一系列变量。死变 量即在违背重新指派值之前不会再用到的变量。可以假设所有的变量都是局部的并且死变量 从 CFG 中退出。 （a）死变量分析是前向还是后向的数据流问题？ （b）IN 和 OUT 集表示哪些成员？集成员是零或者一，意味着什么？ （c）初始化条件是什么？（IN 或 OUT 相似的初始值） （d）什么是交汇操作数？
(©)对于表1中基本块，什么是GEN和KL集？ GEN KILL B1 B2 B3 Bi B5 B6 3.定点 你己经到了最终期限了，F心boz2Co.Ie的第一版，FlatheadCC预计在下周设发布，对于Bem Bisdiddle幸运的是，他不知柯故的休假了(Flateads从来不是好经理)并且正在夏成夷晒 太阳。对于你不幸的是。程序控制流图的代码有些月愿。偶然情况下，你发现一个边缘在招 摆：你知道这个边缘从何面米，但是你不能分辨它希里指门的基本块。 时 44e0 444 时
（e）对于表 1 中基本块，什么是 GEN 和 KILL 集？ 3.定点 你已经到了最终期限了。FrobozzCo. Inc 的第一版，FlatheadCC 预计在下周就发布。对于 Ben Bitdiddle 幸运的是，他不知何故的休假了（Flateads 从来都不是好经理）并且正在夏威夷晒 太阳。对于你不幸的是，程序控制流图的代码有些问题。偶然情况下，你发现一个边缘在摇 摆；你知道这个边缘从何而来，但是你不能分辨它希望指向的基本块
为了解决这个问题，你如何改编下面到达定义分析的程序？你可以假设在任何指明的C下G 中只存在一个边缘。注意，下面程序从作为参数摇摆的网点中获得。参数称为。你还 可以假设预处理阶段已经修政了之前何之后的函数，可以忽略摇摆边界。 4.全局数据流和代码提升 如何不论从程序点P取哪条路径，符号e都在P处调用领繁，则e需要在其任何操作数定义 之前进行计算。进一步的 ●这是反向数据流分析。 ●比特集成员表述了可能被顿繁调川的符号。 ●OUT集雷要初始化为全零。 ●交汇会合操作数为交江点。 ●如果学生对符号赋以如下顺序的比特数据：a+bc-a.b*d.e+1)和(ad则表一中的 GEN和KILL集如下 GEN KILL B1 00000 11101 B2 10000 01101 B3 00100 0010I B 10010 00111 B 11000 10110 B6 00100 11101 执行表一中指出的全局常被调用符号分析。在分析完成时，每个块的N最算的值是什么？ N BI B2 B3 B4 B5 B6
为了解决这个问题，你如何改编下面到达定义分析的程序？你可以假设在任何指明的 CFG 中只存在一个边缘。注意，下面程序从作为参数摇摆的网点中获得。参数称为 dagle。你还 可以假设预处理阶段已经修改了之前何之后的函数，可以忽略摇摆边界。 4.全局数据流和代码提升 如何不论从程序点 p 取哪条路径，符号 e 都在 p 处调用频繁，则 e 需要在其任何操作数定义 之前进行计算。进一步的： ● 这是反向数据流分析。 ● 比特集成员表述了可能被频繁调用的符号。 ● OUT 集需要初始化为全零。 ● 交汇/会合操作数为交汇点。 ● 如果学生对符号赋以如下顺序的比特数据：(a+b),(c-a),(b*d),(e+1)和(a-d)，则表一中的 GEN 和 KILL 集如下 执行表一中指出的全局常被调用符号分析。在分析完成时，每个块的 IN 最终的值是什么？
Entry Bl: (1)a■1 2)b■2 B2: (3)e·a+b (4)d=e-a -B3 (5)d·b·d BG: (8)b■a+b (9)e=c-a B (6)d"n+b BG: (10)a■b*4 (7)0■0+1 (11)b■a-d Exit 表一：CFG程序
表一 ：CFG 程序