📄 9.7.1.htm.bak
字号:
<html>
<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<BODY>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.6.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.2.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.7 优化的实现</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
     代码优化的实现依赖于数据流信息。上两节，讨论了怎样收集这些信息。本节考虑优化的实现,包括公共子表达式删除，复写传播，循环优化。循环优化又分为循环不变计算外提，强度削弱和归纳变量删除。对许多语言，循环优化可使程序的运行速度有很大提高。在编译器的实现中，代码的不同优化措施可以一起完成，但本节的讨论是基于单个的优化措施。 <br>
     本节强调的是使用从程序整体获得信息的全局变换。正如上两节所见，全局数据流分析通常不关心基本块中的点，因此全局变换代替不了局部变换，两者都必须实施。例如，当执行全局公共子表达式删除时，我们只关心一个表达式是否由基本块生成，而不关心它在块中重新计算几次。<br>
</td>
</tr>
</table>
<hr size=2 width=90% align=center color=red><br>
<font class="title2"><b>9.7.1 公共子表达式删除</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
     上节讨论的可用表达式数据流问题允许我们判断一个表达式在流图的P点是否为公共子表达式。下面的算法形式化9.2节提出的公共子表达式删除的直观概念。 <br>
<p><font class = "definition">算法9.7 全局公共子表达式删除 </font><br>
     输入：有可用表达式信息的流图。 <br>
     输出：修改后的流图。 <br>
     方法：对每个形式为x:=y+z的语句s（仍用+代表一般的算符），如<br>
         果y+z在s所在块的开始点可用，在该块中s前没有y或z的<br>
          定值,执行下面 的步骤: <br>
     (1) 为了寻找到达s所在块中的y+z的计算，我们顺着流图的边，从<br>
         该块开始反向搜索，但是不穿过任何计算y+z的块。在遇到y+z<br>
         的每个块中，最后一个y+z是到达s的y+z。 <br>
     (2) 建立新变量u。 <br>
     (3) 把（1）找到的每个语句w:=y+z用 <br>
         u:= y+z <br>
         w:= u <br>
        代替。 <br></p>
     我们可通过（看演示）来学习算法。<br>
<p>
<table>
<tr>
<td><font class="yanshi">    观看演示 </font></td>
<td><font color=blue onmouseover="javascript:style.cursor='hand'" onclick="javascript:open('applet/9212/Page1.htm','_blank','menu=no,toolbar=no,location=no,directories=no,status=no,scrollbars=yes,resizable=yes,copyhistory=no,left=100,top=100,width=800,height=600')">公共子表达式删除概念演示</font></td>
<td><img src="../images/yanshi.gif"></img></td>
</tr>
</table>
</p>
     关于该算法的一些评论如下： <br>
     1、 步骤（1）的寻找到达s的y+z的计算也可以形式化为一个数据流分析问题。但是，为所有的表达式y+z和所有的语句或基本块解这个问题没有意义，因为收集了许多无关的信息。我们宁可在流图上搜索有关的语句和表达式。 <br>
     2、 由算法9.7完成的变化并非都是改进。我们可能需要限制在步骤（1）发现的到达s的不同计算的个数，很可能限制到1。不过，下面讨论的复写传播在几个y+z的计算到达s时也能获得益处。 <br>
     3、 算法9.7将漏掉a*z和c*z在下面情况下是等价的这个事实。 <br>
         a:= x+y 和 c:= x+y <br>
         b:= a*z   d:= c*z <br>
     因为处理公共子表达式的这种简单方法仅考虑字面表达式，而不是表达式计算的值。Kildall提出了一种方法，在一遍扫描中抓住这样的等价。但是，用算法9.7多遍扫描也能抓住它们，可以考虑重复算法9.7直到没有新的公共子表达式为止。如果a和c是临时变量，它们在块外不再引用，那么，对临时变量作专门处理，可使公共子表达式（x+y）*z被抓住，见下面的例9.28。 <br>
     <font class = "example">例9.28</font> 假定在下面图9.40（a）流图中对数组a没有赋值，我们可以安全地认为a[t2]和a[t6]是公共子表达式。问题是怎样删除这个公共子表达式。<br>
</td>
</tr>
</table>
<p align=center><img src="images/9_34.gif"></p>
<table>
<tr>
<td>    </td>
<td class="content">
     图9.40(a)的公共子表达式4*i在图(b)中已删除。发现a[t2]和a[t6]也是公共子表达式的一种办法是用复写传播把t2和t6改成u(下一小节讨论)，两个表达式都成了a[u]，再次使用算法9.7可以删除。注意，同样的新值u插入在图9.40(b)的两块中，所以局部的复写传播足以把a[t2]和a[t6]变成a[u]。 <br>
     还有另一种办法，它考虑这样一个事实：临时变量是由编译器插入的，并仅在它们出现的块中使用。如果仔细地观察表达式的表示方法，能够看到：不同的临时变量代表同样的表达式。表示表达式集合的一种广为采用的方法是为每个表达式赋一个序号，用第i位代表序号为i的表达式的位向量。<br>
     更详细地说，如果使用编号而不是用临时变量,设4* i的编号是15，表达式a[t2]和a[t6]将得到同样的编号，比如是18，那么第18位在数据流分析期间既代表a[t2]又代表a[t6]，可以断定a[t6]是可用的并加以删除。使用编号的结果代码显示在图9.40(c)中。<br>
</td>
</tr>
</table>
<br>
<table align=right width=300>
<tr>
<td>
<img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.6.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.2.htm'" ></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -