📄 9.5.4.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.5.3b_2.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.5.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.5.4 数据流信息的稳妥估计</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
在图9.27(2)计算gen和kill的规则中，已出现一些微妙的问题。在建立这些规则时，作出了这样的假定：对于if和do_while语句中两个分支中的任一个，总存在着某种程序输入，使控制流过那个路径。换种说法，即认为流图中的任一条路径都是一条<font class = "definition2">执行路径</font>,尽管情况并不总是这样。
</p>
<p>
当我们把计算的gen和"真正的"gen相比，会发现真正的gen总是计算的gen的子集。另一方面，真正的kill总是计算的kill的超集。即使考虑图9.27(2)的其它规则，这种关系仍然保持。例如：若do-while语句的E决不为假，那么我们决不会走出此循环，这时真正的gen是φ，而每个定值都被此循环注销。对图9.27(2)（b）串联语句的情况，也应考虑S1或S2的无限循环使得控制不能走出这些语句的情况。
</p>
<p>
很自然会提出这样的问题，真正的和计算的gen和kill集合的区别是否给数据流分析产生严重的障碍，答案依赖于数据如何使用。在到达_定值这种情况下，通常使用这种信息去推断变量x的值在某点是否限于某种较少的可能性。例如：若只有x:=1这样的定值点到达x的某个引用点，那么该点的引用x可改为引用1。
</p>
<p>
过高估计到达某一点的定值集合，不会引起什么问题，只不过可能失去某些优化的机会。相反，过低估计到达某一点的定值集合是一个致命的错误，它可能引起改变程序计算结果的变换。例如，我们可能认为所有x的到达_定值给出的x值都是1，因而用1代替x，但是还有一个没有发现的到达_定值，x的值是2。所以对到达_定值，如果估计的集合是真正的到达_定值集合的超集（不必是真超集），我们称定值集合是<font class = "definition2">安全</font>的或<font class = "definition2">稳妥</font>的。否则，估计是<font class = "definition2">不安全</font>的。
</p>
<p>
对每一个数据流问题，必须检查不安全估计引起的程序改变的影响。我们通常接受的是安全的策略，尽管可能丢失某些优化机会，而不接受不安全的策略，虽然它们能引起某些"优化"，但这些优化不能保持住外部看到的程序行为。究竟是真正集合的子集还是超集是安全的，取决于具体的数据流问题。
</p>
<p>
回到到达_定值的gen 和kill估计问题，超集对gen是安全的，子集对kill是安全的。直观上，增大gen即加大了可到达某点的定值集合，但不会漏掉真正会到达该点的任何定值。同样，减小kill也只会增大到达某点的定值集合。
</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.5.3b_2.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.5.htm'" ></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -