📄 9.6.1b.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.6.1.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.2a.htm'" ></img></td>
</tr>
</table>
<br><br>
<table>
<tr>
<td>    </td>
<td class="content">
            <font color="#008000"> /*假定对所有B,in[B]=ф,给out置初值*/
</font> <br>
         (1) <font color="#0000FF"> <b>for</b></font> 每个基本块 B
<font color="#0000FF"> <b>do</b></font> out[B]：=get[B]<br>
         (2) change：=<b><font color="#0000FF">true</font></b>;
<font color="#008000">/*使while循环可连续*/</font><br>
         (3) <b>
<font color="#0000FF">while</font></b> change <font color="#0000FF"><b>do begin
</b></font> <br>
         (4)     change：=<font color="#0000FF"><b>false;</b></font><br>
         (5)    
<b><font color="#0000FF">for</font></b> 每个基本块 B <font color="#0000FF"><b>do begin</b></font><br>
         (6)         in[B]：=∪out[P]；<br>
                            <font size="2"> P是B的前驱</font><br>
         (7)         oldout：=out[B];<br>
         (8)         out[B]：=get[B]∪(in[B]-kill[B]);<br>
         (9)        
<b><font color="#0000FF">if</font></b> out[B]≠oldout <b><font color="#0000FF">then</font></b> change：=<b><font color="#0000FF">true</font></b><br>
                
<b><font color="#0000FF">end</font></b><br>
             <b>
<font color="#0000FF">end</font></b><br>
                 <b>图9.30 计算in和out的算法</b><br>
<p>
直观上，算法9.3传播定值到尽可能远的地方，只要它们没有被注销，从某种意义上说，模拟程序所有可能的执行。
</p>
<p>
可以看出该算法最终总会停止，因为任何B的out[B]的大小不会减小；一旦加入一个定值，它便永远留在这个集合中。因为所有定值集合是有限的，最终总有一遍<b>while</b>循环的结果使得第（9）行每个B的oldout=out[B]，change仍为<b>false</b>，算法终止，终止是安全的，因为out没有改变，那么下一遍的in也不会改变。如果in不变，所有以后的遍都不会有任何改变。
</p>
<p>
可以证明，<b>while</b>循环次数的上界是流图中的结点数。直观上的理由是，如果一个定值到达一点，那么沿着无环的路径它可能到达其它点，流图中结点数目是无环路径结点数的上界。每次<b>while</b>循环，定值至少沿着该路径传播一个结点。
</p>
<p>
事实上，如果对第（5）行的<b>for</b>循环中指示的块进行适当地排序，经验证明实际程序的迭代次数低于5。因为集合可以用位向量表示，这些集合的操作可以由位向量的逻辑运算完成。算法9.3在实际应用中效率很高。
</p>
<p>
这里，我们通过（看演示）来学习算法9.3
</p>
</td>
</tr>
</table>
<p>
<table>
<tr>
<td><font class="yanshi">       观看演示 </font></td>
<td><font color=blue onmouseover="javascript:style.cursor='hand'" onclick="javascript:open('applet/9611/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>
<table align=right width=300 height="30">
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.1.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.2a.htm'" ></img></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -