📄 9.7.4c.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.7.4b.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.5.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.7.4 代码外提</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
找出循环不变计算的语句后，可对其中的一些实施代码外提的优化，即把这些语句移到循环的前置结点中。下面三个条件保证代码外提不会改变程序的计算。之所以用这些条件是因为它们易检查和易用到实际程序中，后面还讨论放宽这些条件的可能性。
</p>
<p>
语句s：x:=y+z的条件是：
</p>
<p>
(1)含s的块是循环所有出口结点的必经结点，出口结点指的是有不在循环中的后继结点。
</p>
<p>
(2)循环中没有其它语句对x 定值。如果x是只是赋值一次的临时变量，这个条件肯定满足，不必检查。
</p>
<p>
(3)循环中x的引用仅由s到达，如果x是临时变量，一般也满足这个条件。
</p>
<p>
下面三个例子分别说明要求上面三个条件。
</p>
<table>
<tr>
<td class="content">
<font class = "example">例9.31</font>
<p> 把循环不变计算移到循环外，可能改变程序的计算，如图9.42。这个例子引出条件（1），因为只要不陷入无限循环，所有出口的必经语句一定会执行。 </p>
<p> 考察图9.42（a）的流图，B2，B3和B4形成一个循环，B2是首结点。B3的语句i:=2显然是循环不变的，但是B3不是出口B4的必经块。若把i:=2外提到新的前置块B6中，如果不执行B3的话,如图9.42（b），可能改变B5中j的赋值。
</p>
<p align=center><img src="images/9_37.gif" align = center></td>
</tr>
</table>
<table>
<tr>
<td class="content">
<font class = "example">例9.32</font>
<p align=center><img src="images\9_38.gif" align=center>
<p>当循环中有多于一个对x赋值时,要求条件(2)。图9.43的流图结构和图9.42(a)是一样的，并且也和图9.42(b)那样建立前置结点B6。 </p>
<p>因为B2是出口结点B4的必经结点,所以,条件(1)无法阻挡把i:=3外提到前置块B6中。但是，如果我们这样做，只要B3执行，i的值就是2，这个值会到达B5，即使执行的序列是B2→B3→B4→B2→B4→B5。可是，若没有外提，这个序列的执行使i=3到达B5。
<br>
</td>
</tr>
</table>
<table>
<tr>
<td class="content" valign="top">
<font class = "example">例9.33</font>
<p>现在考虑条件(3)。图9.44流图的基本块B4中i的引用由B1中的i:=1到达，也由B3中的i:=2到达。所以不能外提i:=2到前置块中，因为若u>=v,到达B5的K值会改变。 </td>
<td><p><img src="images\9_39.gif"> </p></td>
<td width="20%">  </td>
</tr>
</table>
<p>
<font class = "definition"><a name="A9.8"></a>算法9.10 代码外提</font>
</p>
<p>
输入: 具有ud链和必经结点信息的一个循环L。
</p>
<p>
输出: 循环的修改版本，增加了前置块，可能有一些语句外提到前置<br>
    块中。
</p>
<p>
方法:
</p>
<p>
  (1) 用算法9．9找循环不变语句;<br></p>
<p>  (2) 为(1)找到的每个x定值语句s，检查：</p>
<p>   (a) s所在块是L所有出口的必经块;<br>
    (b) x在L的其它地方没有定值;<br>
    (c) L中所有x的引用只有s的x定值才能到达。<br></p>
<p>  (3) 按算法9．9找出的次序，把(1)找出的且满足(2)三个条件的<br>
        每个语句移到新的前置块。但是，若S的运算对象在L中定值<br>
        (由算法9．9的(3)找出这种s)，那么只有这种对象的定值语句<br>
        外提到前置块后，才能外提s。
</p>
<p>
上述算法的条件(2)(a)和(2)(b)保证在s计算的x值必定是L任何出口的x值，当把s外提到前置块时，s仍然是到达L任何出口的x的定值。条件(2)(c）保证L中任何x的引用在外提前后都引用s计算的x值。
</p>
<p>
为了明白为什么变换不会增加程序的运行时间，只需注意条件2（a），它保证控制每次进入循环L，s至少执行一次。代码外提后，它在前置块仅执行一次，控制进入L时，它根本不再执行。
</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='9.7.4b.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.5.htm'" ></img></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -