📄 9.6.2bc.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.2bb.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.3.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.6.2 可用表达式（二）</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
可以用类似于计算到达_定值集合的方式寻找可用表达式。假定U是程序中出现在语句右部的所有表达式集合。对每个基本块B，令e_in[B]是在B开始点的可用表达式集合，令e_out[B]是在B结束点的可用表达式集合，定义e-gen[B]是B生成的可用表达式集合，定义e-kill[B]是U中被B注销的表达式集合。e_in，e_out，e-gen，e-kill可以用位向量表示。下列方程把未知的e_in和e_out同已知的e-gen和e-kill联系起来。
</p>
<font color="#FF0000">         e_out[B]=e_in[B]－e-kill[B]∪e-gen[B] <br>
         e_in[B]=∩e_out[P] (B不是开始块) <br>
<font size="2">                   P是B的前驱 </font><br>
         e_in[B1]=Ф (B1不是开始块)           (方程9.10)
</font> <br>
<p>
方程（9.10）看起来和方程<a href="9.6.2b_1.htm">（9.9）</a>的到达_定值方程几乎一样。第一个区别是开始块的in处理为特殊情况。这是基于程序从开始块刚开始执行时，没有任何东西可用，即使某些表达式沿着从程序的其他地方到达开始结点的所有路径都可用。因为，若不强置in[B1]为空，可能会错误地推断出某些表达式在程序启动前可用。
</p>
<p>
第二个也是更重要的区别是，合流算符是交而不是并。应该是这样，因为一个表达式在块的开始点可用，只有当它在该块的所有前驱块的结束点可用。与此相反，一个定值到达块的开始点，只要它能到达该块的某个前驱的结束点。
</p>
<p>
对可用表达式，如果它对x或y赋值（或可能赋值），并且随后没有重新计算x+y，我们就说基本块注销表达式x+y。
</p>
<p>
∩而不是∪的使用使方程（9.10）的行为和（9.9）有区别。虽然两种方程的解都不唯一，但对（9.9），求的是对应于到达_定值的最小解，为得到这个解，由假设没有任何东西到达任何地方开始，并逐步增大到这个解。按这种方式，我们决不会让定值d到达点p，除非真能找到路径把d传播到p。相反，对方程（9.10），我们想要得是最大可能解，所以从足够大的近似开始，并逐步减小。
</p>
<p>
我们从假定任何东西，即集合U，在任何地方都可用开始，并且仅删掉那些表达式，对于它们，我们可以找到一条路径，在这条路径上它们不可用，最后到达真正的可用表达式集合。在可用表达式情况下，得到精确的可用表达式集合的子集是稳妥的办法，我们用方程（9.10）所能得的正是这样的子集。子集之所以稳妥的原因是：我们利用这些信息是为了把先前计算的值代替可用表达式的计算，不知道一个表达式可用仅仅禁止了我们进行这种代换。
</p>
<p>
<font class = "example">例9.25</font> 我们集中于下面图中基本块B2来说明in[B2]的初值对out[B2]的影响。令G和K分别是gen[B2]和kill[B2]的缩写，B2的数据流方程是
</p>
 <font color="#FF0000">        in[B2]=out[B1]∩out[B2] <br>
         out[B2]=G∪(in[B2]-K) </font> <br>
这些方程已重写在图中，用I<sup>j</sup>和O<sup>j</sup>分别表示in[B2]和out[B2]的第j次近似。图中还给出，用I<sup>0</sup>=Ф开始，得到O<sup>1</sup>=O<sup>2</sup>=G，而用I<sup>0</sup>=U开始，得到较大的O<sup>2</sup>集合。在两种情况下，out[B2]都等于O<sup>2</sup>，因为它们都收敛在一点。<br>
<p align=center><img src="images/9_33.gif"></p>
<p>
直观上，以I<sup>0</sup>=U开始，用
</p>
 <font color="#FF0000">        out[B2]=G∪(outB1]-K)
</font> <br>
得到的解是我们想要的，因为它正确反映了这个事实，out[B1]中没有被B2注销的表达式在B2的结束点可用，如同B2产生的表达式那样。
<p>
下面我们给出求可用表达式的算法。
</p>
<font class = "definition"><p>算法9.4 可用表达式<br></font>
<p>输入：流图G，每块B的e-kill[B]和e-gen[B]已计算，开始块是B1。<br>
<p>输出：每块B的e_in[B]集合。<br>
<p>方法：执行图9.34的算法，每步的解释和算法9.3类似。<br>
<br>
e_in[B1] := Φ;<br>
e_out[B1] := e-gen[B1]; <font color="#008000">/*对初始结点B1，<br>
in和out决不会改变*/</font><br>
<font color="#0000FF">
<b>for</b></font> B ≠ B1 <b><font color="#0000FF">do</font></b> <br>
e_out[B] := U - e-kill[B];
<font size="3" color="#008000">/*初始估计值取最大*/</font><br>
change := <b><font color="#0000FF">true</font></b>;<br>
<b><font color="#0000FF">while</font></b> change <b><font color="#0000FF">do</font></b>
<font color="#0000FF"><b>begin</b></font><br>
change := <b><font color="#0000FF">false</font></b>;<br>
<b><font color="#0000FF">for</font></b> B ≠ B1 <b><font color="#0000FF">do</font></b> <b>
<font color="#0000FF">begin</font></b><br>
e_in[B] := ∩ e_out[P];<br>
    <font size="2">P是B的前驱<br></font>
oldout := e_out[B];<br>
e_out[B] := e-gen[B] ∪ (e_in[B] - e-kill[B]);<br>
<b><font color="#0000FF">if</font></b> out[B] ≠ oldout <b><font color="#0000FF">then</font></b> change :=
<font color="#0000FF"><b>true</b></font><br>
<b><font color="#0000FF">end</font></b><br>
<b><font color="#0000FF">end</font></b><br>
<center><b>图9.34    可用表达式计算算法</b></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.2bb.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.3.htm'" ></img></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -