📄 9.7.3.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.7.2c.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.4.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.7.3 寻找循环不变计算</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
一、概念：
</p>
<p>
<font class = "definition2">循环不变计算</font>：即只要控制不离开循环，它的值就不改变。这样的计算叫循环不变计算。
</p>
<p>
二、寻找循环不变计算：
</p>
<p>
我们用ud链来发掘循环不变计算。9.4节已讨论过，循环由一组基本块组成，它的首结点是所有其它块的必经块，所以进入循环只能通过首结点。我们还要求从循环中的任何块至少有一路径回到首结点。
</p>
<p>
如果循环中有赋值x:=y+z，而y和z所有可能的定值都在循环外面（包括y和/或z是常数的特殊情况），那么y+z是循环不变计算，因为只要控制不离开循环，每次碰到的y+z的值都一样。所有这种赋值可以从ud链找到，ud链即所有到达定值x:=y+z的y和z的定值点表。
</p>
<p>
有了x:=y+z计算的x值在循环中不变后，如果循环中有另一语句v:=x+w，其中w也只可能在循环外定值，那么x+w也是循环不变计算。
</p>
<p>
根据上面的想法，可以对循环多遍扫描，找出越来越多的循环不变计算。如果有ud和du链，甚至不需要重复扫描。定值x:=y+z的du链告诉我们x的定值在哪儿引用;通过ud链,只要检查循环中的这些x引用，看它的运算对象是不是常量,其全部到达_定值点都在循环之外。这些循环不变计算可以移到前置块。下面给出寻找循环不变计算的算法。
</p>
<p>
<font class = "definition"><a name="A9.7"></a>算法9.9 寻找循环不变计算</font>
</p>
<p>
输入：由一组基本块构成的循环L，ud链可用于循环中的每个三地址<br>
        语句。</p>
<p>
输出:循环不变计算的三地址语句。
</p>
<p>
方法：我们只给出算法的非形式说明，说清它的原理。
</p>
<p>
(1) 对所有下列语句标记为"不变"；它们的运算对象或是常数，或<br>
        所有的到达_定值点在循环外。
</p>
<p>
(2) 重复（3），直到没有新的语句可被标记为"不变"为止。
</p>
<p>
(3) 给下面的语句标记"不变"：它们先前没有标记，所有的运算对象<br>
       是常数,或到达_定值点都在循环外，或者只有一个到达_定值点，<br>
       这个定值点是循环中已标记为"不变"的语句。
</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.2c.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.4.htm'" ></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -