📄 9.13.6.htm
字号:
<html>
<head>
<title>9.6的解答</title>
</head>
<body background="../images/background.gif">
<p>解：本题程序的程序流图如图9.6(1)所示。
<p align = "center"><img src="images/e9.6a.gif" width="371" height="296"></p>
<p>（1）计算各基本块的到达-定值集IN[B]。公式为：<p><font face="宋体">
</font>IN[B] = <font face="宋体">∪ OUT[P]<br>
<font size="2"> <sup>P∈P[B]</sup></font></font><p><font face="宋体">
OUT[B] = GEN[B] ∪ ( IN[B] - KILL[B] )</font><p><font face="宋体">
GEN[B]和KILL[B]由程序流图直接求出，显示在表9.6(1)中。</font><p><font face="宋体">表9.6(1)</font><table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width=550 id="AutoNumber1" >
<tr>
<td width="10%" align="center">基本块</td>
<td width="25%" align="center">GEN[B]</td>
<td width="20%" align="center">位向量</td>
<td width="25%" align="center">KILL[B]</td>
<td width="20%" align="center">位向量</td>
</tr>
<tr>
<td width="20%" align="center">B<sub>1</sub></td>
<td width="20%" align="center">{ d<sub>1</sub>, d<sub>2</sub> }</td>
<td width="20%" align="center">11000000</td>
<td width="20%" align="center">{ d<sub>3</sub>, d<sub>4, </sub>d<sub>6 </sub>
}</td>
<td width="20%" align="center">00110100</td>
</tr>
<tr>
<td width="20%" align="center">B<sub>2</sub></td>
<td width="20%" align="center">{ d<sub>3</sub>, d<sub>4</sub> }</td>
<td width="20%" align="center">00110000</td>
<td width="20%" align="center">{ d<sub>1</sub>, d<sub>2, </sub>d<sub>6 </sub>
}</td>
<td width="20%" align="center">11000100</td>
</tr>
<tr>
<td width="20%" align="center">B<sub>3</sub></td>
<td width="20%" align="center">{ d<sub>6</sub> }</td>
<td width="20%" align="center">00000100</td>
<td width="20%" align="center">{ d<sub>1</sub>, d<sub>4 </sub>}</td>
<td width="20%" align="center">10010000</td>
</tr>
<tr>
<td width="20%" align="center">B<sub>4</sub></td>
<td width="20%" align="center">{ }</td>
<td width="20%" align="center">00000000</td>
<td width="20%" align="center">{ }</td>
<td width="20%" align="center">00000000</td>
</tr>
</table>
<p> 求各基本块到达-定值的初值及各遍的执行结果显示在表9.6(2)中。</p>
<p>表9.6(2)</p>
<table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="75%" id="AutoNumber2" height="117">
<tr>
<td width="1%" rowspan="2" height="37">基本块</td>
<td width="26%" colspan="2" height="19" align=center>初值</td>
<td width="24%" colspan="2" height="19" align=center>第一遍后</td>
<td width="24%" colspan="2" height="19" align=center>第二遍后</td>
<td width="34%" colspan="2" height="19" align=center>第三遍后</td>
</tr>
<tr>
<td width="11%" height="19">IN[B]</td>
<td width="11%" height="19">OUT[B]</td>
<td width="11%" height="19">IN[B]</td>
<td width="11%" height="19">OUT[B]</td>
<td width="11%" height="19">IN[B]</td>
<td width="11%" height="19">OUT[B]</td>
<td width="12%" height="19">IN[B]</td>
<td width="12%" height="19">OUT[B]</td>
</tr>
<tr>
<td width="10%" align="center" height="19">B<sub>1</sub></td>
<td width="11%" height="19">00000000</td>
<td width="11%" height="19">11000000</td>
<td width="11%" height="19">00000000</td>
<td width="11%" height="19">11000000</td>
<td width="11%" height="19">00000000</td>
<td width="11%" height="19">11000000</td>
<td width="12%" height="19">00000000</td>
<td width="12%" height="19">11000000</td>
</tr>
<tr>
<td width="10%" align="center" height="20">B<sub>2</sub></td>
<td width="11%" height="20">00000000</td>
<td width="11%" height="20">00110000</td>
<td width="11%" height="20">11000100</td>
<td width="11%" height="20">00110000</td>
<td width="11%" height="20">11100100</td>
<td width="11%" height="20">00110000</td>
<td width="12%" height="20">11100100</td>
<td width="12%" height="20">00110000</td>
</tr>
<tr>
<td width="10%" align="center" height="20">B<sub>3</sub></td>
<td width="11%" height="20">00000000</td>
<td width="11%" height="20">00000100</td>
<td width="11%" height="20">00110000</td>
<td width="11%" height="20">00100100</td>
<td width="11%" height="20">00110000</td>
<td width="11%" height="20">00100100</td>
<td width="12%" height="20">00110000</td>
<td width="12%" height="20">00100100</td>
</tr>
<tr>
<td width="10%" align="center" height="20">B<sub>4</sub></td>
<td width="11%" height="20">00000000</td>
<td width="11%" height="20">00000000</td>
<td width="11%" height="20">00110000</td>
<td width="11%" height="20">00110000</td>
<td width="11%" height="20">00110000</td>
<td width="11%" height="20">00110000</td>
<td width="12%" height="20">00110000</td>
<td width="12%" height="20">00110000</td>
</tr>
</table>
<p align = "left">（2）求各基本块中各变量引用点的ud链：</p>
<p align = "left">
假设在程序中某点u引用了变量a，则把能到达u的a的所有定值点，称为a在引用点u的引用-定值链（简称ud链）。可以利用到达-定值信息来计算各个变量在任何引用点的ud链。</p>
<p align = "left"> 由图9.6(1)的程序流图可知，I的引用点是d<sub>3</sub>、d<sub>5</sub>和d<sub>6</sub>，J的引用点是d<sub>3</sub>和d<sub>8</sub>。</p>
<p align = "left"> B2中I和J的引用点d<sub>3</sub>前面没有对I和J的定值点，其ud链在IN[B<sub>2</sub>]={
d<sub>1</sub>, d<sub>2</sub>, d<sub>3</sub>, d<sub>6</sub> }中，所以I在引用点d<sub>3</sub>的ud链是{
d<sub>1</sub>, d<sub>6</sub> }；J在引用点d<sub>3</sub>的ud链是{ d<sub>2</sub>, d<sub>3</sub>
}。</p>
<p align = "left"> 在B<sub>2</sub>中I的引用点d<sub>5</sub>前面有I的定值点d<sub>4</sub>，且在d<sub>4</sub>定值后到达d<sub>5</sub>，所以I在引用点d<sub>5</sub>的ud链是{
d<sub>4</sub> }。</p>
<p align = "left"> B<sub>3</sub>中I的引用点d<sub>6</sub>前面没有I的定值点，其ud链是IN[B<sub>3</sub>]中I的所有定值点，所以是{
d<sub>4</sub> }。</p>
<p align = "left"> B<sub>4</sub>中J的引用点d<sub>8</sub>前面没有对J的定值点，其ud链是IN[B<sub>4</sub>]中J的所有定值点。已知IN[B<sub>4</sub>]
= { d<sub>3</sub>, d<sub>4</sub> }，所以，J的引用点d<sub>8</sub>的ud链是{ d<sub>3</sub>
}。</p>
<p align = "left">（3）各基本块出口的活跃变量集v-OUT[B]：</p>
<p align = "left">
对程序中某变量a和某点P，如果存在一条从P开始的道路，其中引用了a在P点的值，则称a在点P是活跃的。计算公式如下：</p>
<p align = "left">
V_IN[B] = USE[B] <font face="宋体">∪ ( V_OUT[B] - DEF[B] )</font></p>
<p align = "left"><font face="宋体">
V_OUT[B] = ∪ V_IN[S]<br>
<font size="2">
<sup>S∈S[B]</sup></font></font></p>
<p align = "left"><font face="宋体">其中，S[B]是B的所有后继块组成的集合。</font></p>
<p align = "left"><font face="宋体"> DEF[B]和USE[B]可以从给定流图直接求出。从图9.6(1)的流图中求出的各基本块的DEF[B]和USE[B]显示在表9.6(3)中。</font></p>
<font face="宋体">表9.6(3)</font>
<table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="54%" id="AutoNumber3" >
<tr>
<td width="21%" align="center">基本块</td>
<td width="39%" align="center">USE[B]</td>
<td width="40%" align="center">DEF[B]</td>
</tr>
<tr>
<td width="1%" align="center" height="19">B<sub>1</sub></td>
<td width="39%" align="center"><font face="宋体">Φ</font></td>
<td width="40%" align="center">{ I, J }</td>
</tr>
<tr>
<td width="1%" align="center" height="20">B<sub>2</sub></td>
<td width="39%" align="center">{ I, J }</td>
<td width="40%" align="center"><font face="宋体">Φ</font></td>
</tr>
<tr>
<td width="1%" align="center" height="20">B<sub>3</sub></td>
<td width="39%" align="center">{ I }</td>
<td width="40%" align="center"><font face="宋体">Φ</font></td>
</tr>
<tr>
<td width="1%" align="center" height="20">B<sub>4</sub></td>
<td width="39%" align="center">{ J }</td>
<td width="40%" align="center"><font face="宋体">Φ</font></td>
</tr>
</table></table>
<p>    计算次序为B<sub>4</sub>, B<sub>3</sub>, B<sub>2</sub>, B<sub>1</sub>，各次迭代结果显示在表9.6(4)中。</p>
表9.6(4)
<table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111" width="95%" id="AutoNumber4" height="117">
<tr>
<td width="10%" align="center" rowspan="2" height="37">基本块</td>
<td width="25%" height="19" colspan="2" align="center">第一次迭代后</td>
<td width="28%" height="19" colspan="2" align="center">第二次迭代后</td>
<td width="28%" height="19" colspan="2" align="center">第三次迭代后</td>
</tr>
<tr>
<td width="14%" align="center" height="19">V_IN[B]</td>
<td width="14%" height="19" align="center">V_OUT[B]</td>
<td width="15%" align="center" height="19">V_IN[B]</td>
<td width="15%" height="19" align="center">V_OUT[B]</td>
<td width="15%" align="center" height="19">V_IN[B]</td>
<td width="15%" height="19" align="center">V_OUT[B]</td>
</tr>
<tr>
<td width="1%" align="center" height="19">B<sub>1</sub></td>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -