麻省理工学院 电气工程与计算机科学 6.035,2004年秋 测试3 11月23日.星期二 姓名 请将你的姓名写在上面，并在每页的页首也写下姓名。共有3个月题：学生有50分钟时间 米完成测试，请尽量完整清渐的问答问题。模制和难以理解的答案只会得到很少的分数甚至 没有分数。 分数 满分 阅卷者 1 25 2 25 3 50 总计 100 1.支配点125分1 (a)15分1 回想一下网点d时网点i的支配点，从i的每条路径都包含d。请西出表一中支配树的C下G 图。 (b)110分 除了支配点，另外一个有用的概念是后支配关系。我们说屑点p后支配网点：的意思是从 的退出任何路径都包含p.请西出表一的后支配树的CG阁
麻省理工学院 电气工程与计算机科学 6.035，2004 年秋 测试 3 11 月 23 日，星期二 姓名： 请将你的姓名写在上面，并在每页的页首也写下姓名。共有 3 个问题；学生有 50 分钟时间 来完成测试。请尽量完整清晰的回答问题。模糊和难以理解的答案只会得到很少的分数甚至 没有分数。 分数 满分 阅卷者 1 25 2 25 3 50 总计 100 1.支配点[25 分] （a）[15 分] 回想一下网点 d 时网点 i 的支配点，从 i 的每条路径都包含 d。请画出表一中支配树的 CFG 图。 （b）[10 分] 除了支配点，另外一个有用的概念是后支配关系。我们说网点 p 后支配网点 i 的意思是从 i 的退出任何路径都包含 p。请画出表一的后支配树的 CFG 图
Entry B1 2 B3 84 5 B6 B7 Exit 表一：付置1的控制流图 2.循环不变代码动作25分1 对于下面的每个式子，请标明该指令是否是表二CG图中的循环不变量，如果指令不是循 环不变量，则简要解释原因。假设校鱼的变量在退出陆环时仍然是要用到的。 (a)q-r+s (by+2 Ca-bie (dk-d+l (e=+1
表一：问题 1 的控制流图 2.循环不变代码动作[25 分] 对于下面的每个式子，请标明该指令是否是表二 CFG 图中的循环不变量。如果指令不是循 环不变量，则简要解释原因。假设梭鱼的变量在退出循环时仍然是要用到的。 (a) q=r+s (b)x=y+z ©a=b+c (d)i=d+1 (e)d=i+1
d=0 qr+8 x"了卡2 a b c 98+1 i=d+1 d=i+1 表二：问题二的控制流图 3.寄存器分配50分1 考虑下面的函数： int直imx.my) inta.b.c.d.e. ax+1: b=a*3 c-atbiy. b-c; d-a2. forfe-0i<l0e++) b=b+d:
表二：问题二的控制流图 3.寄存器分配[50 分] 考虑下面的函数： int f(int x, int y ) { int a,b,c,d,e; a=x+1; b=a*3 c=a+b+y; b=c; d=a/2; for(e=0;i<10;e++){ b=b+d; }
心-tt2 retum a+b-c-d: 假设变量初角化已经进行了合适的死代码清除。 (a》请面出函登体的c上us图。并指出活跃边界网格。 (h)周出函效的交互图。 (©》考虑行四个寄存器的食处理器：找折计印和进川寄存器r1,2和3。联酸每个操 作军：可以使用寄存器和存储器中的值，羽用惯例是将x找入山，y线入2，筒盛值返回到山 中。选择溢出代价最小的网格溢出。使用静态近拟值来估算带环执行0次的时间，并且假 定黛入和存储执行执行时问是一样的。对「中的每个变量分配寄存器。标明郑个变量溢出。 《d)假设备存垂分配器可以分割同格并且使用简单贪梦自发式算法来角定分制都个网 格。请展示分配暑汇分割哪个网格并面出新的文互图
c=a+2; return a+b=c=d; } 假设变量初始化已经进行了合适的死代码清除。 （a）请画出函数体的 def-use 图，并指出活跃边界网格。 （b）画出函数的交互图。 （c）考虑有四个寄存器的微处理器：栈指针 sp 和通用寄存器 r1，r2 和 r3。假设每个操 作都可以使用寄存器和存储器中的值，调用惯例是将 x 载入 r1，y 载入 r2，函数值返回到 r1 中。选择溢出代价最小的网格溢出。使用静态近似值来估算循环执行 10 次的时间，并且假 定载入和存储执行执行时间是一样的。对 f 中的每个变量分配寄存器。标明那个变量溢出。 （d）假设寄存器分配器可以分割网格并且使用简单贪婪启发式算法来确定分割那个网 格。请展示分配器汇分割哪个网格并画出新的交互图