📄 9.7.7.3.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.7.2b.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.7.3b.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.7.7.3 归纳变量删除算法</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
    <font class = "definition">算法9.13</font> 归纳变量删除 <br>
    输入：循环L，以及相应的到达_定值信息，循环不变计算信息和活跃<Br>
         变量信息。 <br>
    输出：归纳变量删除后的循环。<br>
    方法： <br>
     (1) 考虑每个仅用于条件分支测试的基本归纳变量i,取i族中其三元<br>
       组（i，c，d）中的c和d尽可能简单的某个j（即，c=1和d=0<br>
       者优先），把每个含i的测试中的i用j代替。例如,形式为<br>               if i relop x goto B<br>
       的测试，其中x不是归纳变量,用下面的指令序列 <br>
<p>      r：=c*x <font color="#008000"> /*如果c等于1，r：=x*/</font> <br>
          r：=r+d <font color="#008000"> /*如果d等于0，省略它*/
</font> <br>
          if j relop x goto B <br></p><p></P>
       代替，其中r是新的临时变量。可类似处理<br>
              if x relop i goto B。<br>
       如果测试if i1 relop i2 goto B的i1和i2都是归纳变量，那么<br>
       检查i1和i2是否都能被代替。最简单的情况是,有j1的三元组<br>
       （i1，c1，d1）和j2的三元组（i2，c2，d2），并且c1=c2和<br>
       d1=d2，那么，i1 relop i2等价于j1 relop j2。更复杂的情<br>
       况，测试的替换可能是没有价值的，因为可能要引入两步乘和<br>
       一步加，而删除i1和i2只可能节省两步。 <br>
<p>  最后，当被删掉的归纳变量不再引用时，从循环中删去所有对它的赋值。</P>
<p> (2) 考虑由算法9.12（强度削弱用于归纳变量）引入语句j:=s的每<br>
       个归纳变量j。首先检查在引入的j:=s和任何j的引用之间有没<br>
       有对s赋值，通常是没有。j常常在它定值的块中被引用，这个<br>
       检查可以简化,否则需要用到达_定值信息和加上一些图的分析<br>
       来实现这种检查。然后用引用s代替所有j的引用，并删去语句<br>
       j:=s。<br></p>
<br>
<font class = "example">例9.36</font>
</td>
</tr>
</table>
<table>
<tr>
<td>    </td>
<td class="content">
<p align=center><img src="images/9_40b.gif"></p>
<p> 考虑图9.46（a）的流图。环绕B2的内循环含两个归纳变量i和s2，但是一个也不能删除，因为s2作为计算数组a的下标，i作为外循环的测试。同样，环绕B3的循环含归纳变量j和s4，它们也不能被删除。 <br>
     再让我们把算法9.13用于外循环。当算法9.12建立新变量s2和s4时，s2置于i族，s4置于j族。考虑i族,i的唯一引用是在B4中测循环终止，所以i是算法9.13步骤（1）删除的侯选。B4的测试含两个归纳变量i和j，幸好，i族和j族分别含的归纳变量s2和s4的三元组有同样的常数，因为这两个三元组分别是（i，4，0）和（j，4，0）。于是，测试i>=j可由s2>=s4代替，使得i和j都被删除。 <br>
     算法9.13步骤（2）运用复写传播于新建的变量，用s2和s4分别代替t2和t4。最后的结果如图9.46(b)<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.7.2b.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.7.7.3b.htm'" ></img></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -