📄 9.3.1.htm
字号:
<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.2.4.3.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.3.3.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.3 基本块的优化</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
本节系统总结一下如何用dag实现基本块的优化。回忆第八章所讲的，在dag中，对基本块中出现的变量的初值都有一个结点，对每个语句s都有一个结点n和它对应。n的子结点对应到这样一些语句所对应的结点，它们是s的运算对象的先于s的最后一个定值。结点n由s所用的算符标记，连到n的还有一张变量表，这些变量在该块中的最后一次定值就在这里。我们还要注意那些在块的出口是活跃的值，它们所在结点是输出结点。<br>
</p>
</td>
</tr>
</table>
<hr size=2 width=90% align=center color=red><br>
<font class="title2"><b>9.3.1 用dag删除公共子表达式</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
发现公共子表达式是在新结点m将要加入的时候，检查是否存在结点n，n和m有同样的后代，它们有同样的次序，并且算符也一样。如果存在，n和m计算同样的值，n就可以作为m，而不必加入新结点。<br></p>
<p><font class = "example">例9.5</font> 基本块
</p>
</td>
</tr>
</table>
<table>
<tr>
<td>    </td>
<td class="content">
a：= b + c<br>
b：= a - d<br>
c：= b + c<br>
d：= a - d （基本块1）<br>
</td>
</tr>
</table>
<table>
<tr>
<td>    </td>
<td class="content">
<p><img ALIGN=RIGHT src="images/9_14.gif">
的dag显示在图9.14上，当为第三个语句构造结点时，我们知道b+c中b的引用是右图中标记为-的结点，因为它是b的最近定义。因此，不能混淆第一和第三两个语句计算的值。<br>
然而，对应第四个语句的结点有算符-，它的子结点是a和d<sub>0</sub>，因为这完全同于第二个语句对应的结点，因此不创建新结点，只是把d加到标记为-的结点的定义表中。<br>
显然，因为图9.14中的dag只有三个结点，块1可能用仅含三个语句的块代替。如果b或d在块出口不活跃，那么就不需要计算这个不活跃变量，用另一个活跃变量来接受图9.14中标记为-的结点值。例如，如果b在出口不活跃，可以用<br>
a := b + c<br>
d := a - d<br>
c := d + c<br>
代替块1。不过，如果b和d在出口都活跃，那么仍需第四个语句，不过是一个复写语句。<br>
<p>
有一点需要我们注意，在寻找公共子表达式时，我们找的是肯定计算同样值的表达式，而不管它是怎样计算的。这样，dag方法会漏掉序列
</p>
</td>
</tr>
</table>
<table>
<tr>
<td>    </td>
<td class="content">
a := b + c <br>
b := b - d <br>
c := c + d <br>
e := b + c （基本块2） <br></td>
</tr>
</table>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
<img ALIGN=RIGHT src="images/9_15.gif">
<p>中第一和第四语句计算同样表达式这个事实。不过，下面讨论的代数恒等可以揭示出这个等价。这个序列的dag见右图9.15。
</p></p>
</td>
</tr>
</table>
<p>
<br>
</p>
<table align=right width=300>
<tr>
<td>
<img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.2.4.3.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.3.3.htm'" ></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -