- 1、本文档共57页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2、 基本块的DAG表示及其应用 Ⅰ、0型四元式:后继结点个数为0。 n1 A B n1 (S) n1 op B n2 A a) A:=B b) goto (S) A:=op B Ⅱ、1型四元式:有一个后继结点。 2、 基本块的DAG表示及其应用 Ⅲ、2型四元式:有两个后继结点。 n1 op B n3 A n2 C n1 =[] B n3 A n2 C n1 rop B n3 (S) n2 C a) A:= B op C b) A:= B[C] c) if B rop C goto (S) 2、 基本块的DAG表示及其应用 Ⅳ、3型四元式:有三个后继结点。 D[C] :=B n1 []= D n4 B n2 C n3 2、 基本块的DAG表示及其应用 (3)仅含0,1,2 型中间代码的基本块DAG构造算法 我们规定:用大写字母(如A、B等)表示四元式中的变量名(或常数);用函数Node(A)表示A在DAG中的相应结点,其值可为n或者无定义,并用n表示DAG中的一个结点值。 开始,DAG为空。对基本块中每一条中间代码式,依次执行以下步骤。 Ⅰ、如果NODE(B)无定义,则构造一标记为B的叶结点并定义NODE ( B)为这个结点。 ①若当前四元式是0型, 则记Node(B)的值为n, 转Ⅳ。 ②若当前四元式是1型, 则转Ⅱ①。 ③若当前四元式是2型, 则: i.若Node(C)无定义,则构造一标记为C的叶结点, 并定义 Node(C)为该结点; ii.转Ⅱ②。 2、 基本块的DAG表示及其应用 Ⅱ ①若Node(B)是以常数标记的叶结点,则转Ⅱ③,否则转Ⅲ①。 ②若Node(B)和Node(C)都是以常数标记的叶结点,则转Ⅱ④,否则转Ⅲ②。 ③执行op B(即合并已知量),令得到的新常 数为P。 若Node(B)是处理当前四元式时新建立的结点,则删除它; 若Node(P)无定义,则构造一个用P做标记的叶结点n,并置Node(P)= n;转Ⅳ。 ④执行B op C(即合并已知量),令得到的新常数为P。 若Node(B)或Node(C)是处理当前四元式时新建立的结点则删除它; 若Node(P)无定义,则构造一用P标记的叶结点n,并置Node(P)= n;转Ⅳ。 2、 基本块的DAG表示及其应用 Ⅲ ①检查DAG中是否有标记为op且以Node(B)为唯一后继的结点。 若有则把已有的结点作为它的结点,并设该结点为n; 若没有,则构造一个新结点;转Ⅳ。 ②检查DAG中是否有标记为op且其左后继为Node(B)、右后继为Node(C)的结点(即查找公共子表达式)。 若有,则把已有的结点作为它的结点,并设该结点为n; 若没有,则构造一个新结点;转Ⅳ。 Ⅳ 若Node(A)无定义,则把A附加在结点n上,并令Node(A)= n;否则,先从Node(A)的附加标识符集中将A删去(若Node(A)是叶结点,则不能将A删去),然后再把A附加到新结点 n上,并令Node(A)=n。转处理下一代码。 2、 基本块的DAG表示及其应用 (4)构造DAG实例 【例 8.4】 试构造以下基本块G的DAG: (1) T0=3.14 (2) T1:=2*T0 (3)T2:=R+r (4) A: =T1*T2 (5) B: =A (6) T3:=2*T0 (7) T4:=R+r (8) T5:=T3*T4 (9}T6:=R-r (10) B:=T5*T6 2、 基本块的DAG表示及其应用 n1 3.14 T0 n2 6.28 n3 R n4 r T1 (1) T0:=3.14 (2) T1:= 2*T0 (3) T2:=R+r (4) A:= T1* T2 (5) B:=A (6) T3:= 2*T0 (7) T4:=R+r (8) T5:= T3* T4 (9) T6:=R-r (10) B:= T5* T6 n5 + T2 n6 * A ,B ,T3 ,T4 ,T5 n7 - T6 n8 * B 2、 基本块的DAG表示及其应用 (5)利用DAG进行基本块的优化 利用DAG进行基本块优化的基本思想:首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG,然后按构造结点的次序将DAG还原成四元式序列。由于在构造DAG的同时已作了局部优化,所以最后所得到的是优化过的四元式序列。 例如,上例四元式序列经优化后得G?如下: 2、 基本块的DAG表示及其应用 (1) ?T0:=3.14 (2) ?T1:=6.28 (3) ?T3:=6.28
您可能关注的文档
最近下载
- 德国服装进口企业90个(带联系人、邮箱等详细信息).doc
- 云南作家协会入会申请表.doc
- 五年级上册数学试题-期末测试卷人教版(含答案).docx VIP
- 专题15 磁场-2020-2024年五年高考物理真题分类汇编(解析版).docx
- 2024年高考评析-新结构-新思想-新导向.pdf VIP
- 2024年全国各地中考语文名著阅读真题汇编(55题有解析有答).doc
- 时序器sh108产品检验报告.pdf VIP
- 储能行业研究框架:新能源周期核心品种,行业最具成长的主线之一.docx VIP
- 中信建投-电力设备行业每周观察-中东光储市场详细梳理.pdf VIP
- 全自动下卸料离心机PGZ1250说明书.pdf
文档评论(0)