📄 9.5.7.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.6.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.0.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.5.7 局部的到达_定值</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
如果把所有结点的in集合、out集合都存储起来，要占用很多的存储空间，如何解决呢？可以只保存某些点的信息，其余点的信息在需要时重新计算，这样以时间换数据流信息所要的空间。基本块在全局数据流分析中通常作为一个单元，可以把注意力集中于基本块的开始点。因为点的个数通常远远多于块的个数，这样做可以大大节约空间。当需要时，块中所有点的到达_定值可以用该块开始点的到达_定值计算得到。
</p>
<p>
更详细一点，考虑块B中语句序列S<sub>1</sub>；S<sub>2</sub>；…；S<sub>n</sub>。我们把B的开始点叫做Po，语句S<sub>i</sub>和S<sub>i+1</sub>之间的点叫P<sub>i</sub>，最后一个点叫P<sub>n</sub>。到达Pj点的定值可以从in[B]，用<a href="9.5.3_1.htm">图9.27(2)(b)</a>串联语句的数据流方程，逐个考虑S<sub>1</sub>；S<sub>2</sub>；…；S<sub>j</sub>；而得到。起初，令D=in[B]，当考虑S<sub>i</sub>时，从D中删掉由S<sub>i</sub>注销的定值，加上由S<sub>i</sub>产生的定值。最后，D由到达P<sub>j</sub>的定值组成。
</p>
<p>
举个例子：图9.28的程序给出了7个定值点，由放在定值左边注解中的d1到d7表示。其中语句的gen和kill集合的位向量在图9.29中语法树各结点的左边。这些集合本身的计算是把图9.27(2)的数据流方程作用于语法树结点代表的语句。
</p>
</td>
</tr>
</table>
<a name="9.5.8"></a>
<hr size=2 width=90% align=center color=red><br>
<font class="title2"><b>9.5.8 引用_定值链（ud链）</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
通常，把到达_定值信息存储为引用_定值链是方便的，它是所有能够到达变量的某个引用的定值表。如果在块B中变量a的引用前没有a的无二义定值，那么a的这次引用的ud链是in[B]中a的定值集合。如果在块Ｂ中a的引用前有a的无二义定值，那么只有最后一个a的这种定值在ud链中，in[B]不在这个ud链中。此外，如果有a的二义定值，那么，所有定值，只要在它和a的这次引用之间没有a的无二义定值，都在a的这次引用的ud链中。
</p>
</td>
</tr>
</table>
<p> </p>
<a name="9.5.9"></a>
<hr size=2 width=90% align=center color=red><br>
<font class="title2"><b>9.5.9 计算次序</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
<p>
本节讨论的数据流方程在计算的依赖性方面和第四章提出的属性的语义规则有区别：属性之间的依赖不能有环;而数据流方程中被计算的集合之间可以有环形的依赖性，例如，方程(9.8)中的in[S<sub>1</sub>]和out[S<sub>1</sub>]互相依赖。对到达_定值问题，数据流方程可以重写删掉这种环的依赖性（请把图9.25(2)的无环方程和方程(9.8)比较）。一旦获得无环的说明，可用第四章的语法指导技术来获得数据流方程的快速计算。</p>
<p><font color="#FF0000"> I=J∪O </font> </p>
<p><font color="#FF0000"> O=G∪（I-K） （方程9.8）
</font> </p>
<p>（其中I，O，J，G和K分别对应in[S<sub>1</sub>],out[S<sub>1</sub>],in[S],gen[S<sub>1</sub>]和kill[S<sub>1</sub>]。前两个是变量，其余的是常量。）
</td>
</tr>
</table>
<table align=right width=300>
<tr>
<td>
<img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.5.6.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.0.htm'" ></td>
</tr>
</table>
</BODY>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -