📄 8.6.2b.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='8.6.2.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='8.6.2c.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>    </td>
<td class="content">
<P>（5）t<SPAN class=down><sub>6</sub></SPAN>：＝t<SPAN class=down><sub>5</sub></SPAN>[t<SPAN
class=down><sub>1</sub></SPAN>]<br>
在后一语句中我们引用t<SPAN class=down><sub>1</sub></SPAN>而非t<SPAN class=down><sub>4</sub></SPAN>作为变元。因为t<SPAN
class=down><sub>1</sub></SPAN>是我们选择用来保存4*i的值的名字，接下来对附加以t<SPAN class=down><sub>7</sub></SPAN>的结点求值： </P>
<P>（6）t<SPAN class=down><sub>7</sub></SPAN>：＝t<SPAN class=down><sub>3</sub></SPAN>*t<SPAN
class=down><sub>6</sub><br>
</SPAN>然后是对附加以t<SPAN
class=down><sub>8</sub></SPAN>，prod的结点。这里，我们选取prod保留该值，因我们认为prod在基本块外是有用的。和t<SPAN
class=down><sub>4</sub></SPAN>一样，t<SPAN class=down><sub>8</sub></SPAN>不再出现。于是下一条语句为： </P>
<P>（7） prod：＝prod＋t<SPAN class=down><sub>7</sub><br>
</SPAN>类似地，我们选取i而非t<SPAN class=down><sub>9</sub></SPAN>来保存值i＋1，并产生最后两条语句： </P>
<P>（8） i：＝i＋1 </P>
<P>（9） if i<=20 goto（1）<br>
这样，通过利用公用子表达式，图8.9的12条语句已减少为9条语句。 注意，在此例题中的t<sub>4</sub>和t<sub>8</sub>如果在基本块外是有用的，那么在这里生成的第一条语句之后应有语句：<br>
t<SPAN class=down><sub>4</sub></SPAN>:=t<SPAN class=down><sub>1</sub><br>
</SPAN>在第（7）条语句之后应有语句：<br>
t<SPAN class=down><sub>8</sub></SPAN>：＝ prod</P>
<P><font class="definition2">数组、指针和过程调用</font></P>
<P>当基本块中出现有数组、指针和过程调用时，情况就较为复杂。例如，考虑如下的基本块：<br>
x：= a[i] <BR>
a[j]：= y <BR>
z：= a[i]<br>
并假定有关变量名字都是块外可用的。如果我们运用算法8.2来构造上述基本块的dag，那么a[i]将成为一个公用子表达式。而当从dag重新构造基本块时如果不加任何限制的话，则表面上“优化”后的基本块为：<br>
x：= a[i] <BR>
z：= x <BR>
a[j]：= y<br>
然而它与原有的基本块并不等价。不难看到，在i=j并且y≠a[i]
时，这两个基本块所计算出来的z值是不相同的。这是因为在第一个基本块中的第二个语句a[j]：＝y被执行时，将改变a[j]的右-
值，当i＝j时，即将改变a[i]的右-值。这样虽然i并没有变，但其后随的语句z:＝a[i]之中的a[i]的右-值已经发生变化。于是x和
z之值可能是不相同的，因而不能简单地把a[i]看作是一个公用子表达式。第二个基本块就是错误地把a[i]看作是第一个基本块中的一个公用子表达式而得到的，从而也就得到错误的结果。解决的方法是，当我们对数组a的一个元素赋值时，我们“注销“所有标
记为[]、左边的变元是a加上或减去一个常数（也可能是0）的结点。即，我们认为对这样的结点添加附加标识符是非法的，从而以防止把它们错误地当成公用子表达式。因此，我们需要对每一个结点设一个标志位来标记是否已被注销。另外，对每个基本块中引用的数组a,我们可以保存一个结点表，这些结点是当前未被注销但若有对a的一个元素的赋值则必须被注销的结点。</P>
</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='8.6.2.htm'"></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='8.6.2c.htm'"></img></td>
</tr>
</table>
</body>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -