📄 8.6.0.htm
字号:
<html>
<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>
<style type="text/css">
<!--
body {font-size:12pt; margin:0;}
td { font-size: 12pt}
.up { left: 0px; top: 0px; clip: rect( ); font-size: small; height: 20px; width: 20px}
.down { font-size: xx-small}
-->
</style>
<STYLE>BODY { MARGIN: 0px}
a{color:#0000ff;text-decoration:none}
a:hover{color:orange;text-decoratin:none}
td{font-size:12pt;color:#000000;border-width:1;border-color:#999999}
</STYLE>
<BODY bgColor=#ffffff>
<table align=center width=726 cellpadding=0 cellspacing=1 border=0 bordercolor=#999999 style="BACKGROUND-COLOR: #ffffff">
<tr>
<td style="BACKGROUND-COLOR: #dedede; BORDER-BOTTOM-COLOR: #999999; BORDER-BOTTOM-WIDTH: 1px; BORDER-LEFT-COLOR: #999999; BORDER-LEFT-WIDTH: 1px; BORDER-RIGHT-COLOR: #999999; BORDER-RIGHT-WIDTH: 1px; BORDER-TOP-COLOR: #999999; BORDER-TOP-WIDTH: 1px; COLOR: #666666; FONT-SIZE: 12pt;
WIDTH:
180px"
align=middle
>
<A href="8.5.2.htm">回到上页</A>
</td>
<td style="BACKGROUND-COLOR: #fcf4e2; BORDER-BOTTOM-COLOR: #999999; BORDER-BOTTOM-WIDTH: 1px; BORDER-LEFT-COLOR: #999999; BORDER-LEFT-WIDTH: 1px; BORDER-RIGHT-COLOR: #999999; BORDER-RIGHT-WIDTH: 1px; BORDER-TOP-COLOR: #999999; BORDER-TOP-WIDTH: 1px; COLOR: #666666; FONT-SIZE: 12pt;
WIDTH:
180px"
align=middle
>
<A href="#end">页末</A>
</td>
<td style="BACKGROUND-COLOR: #dedede; BORDER-BOTTOM-COLOR: #999999; BORDER-BOTTOM-WIDTH: 1px; BORDER-LEFT-COLOR: #999999; BORDER-LEFT-WIDTH: 1px; BORDER-RIGHT-COLOR: #999999; BORDER-RIGHT-WIDTH: 1px; BORDER-TOP-COLOR: #999999; BORDER-TOP-WIDTH: 1px; COLOR: #666666; FONT-SIZE: 12pt;
WIDTH:
180px"
align=middle
>
<A href="8.6.1.htm">进入下页</A>
</td>
<td style="BACKGROUND-COLOR: #dedede; BORDER-BOTTOM-COLOR: #999999; BORDER-BOTTOM-WIDTH: 1px; BORDER-LEFT-COLOR: #999999; BORDER-LEFT-WIDTH: 1px; BORDER-RIGHT-COLOR: #999999; BORDER-RIGHT-WIDTH: 1px; BORDER-TOP-COLOR: #999999; BORDER-TOP-WIDTH: 1px; COLOR: #666666; FONT-SIZE: 12pt;
WIDTH:
179px"
align=middle
>
<A href="c_8.htm">回到首页</A>
</td>
</tr>
</table>
<table width="99%" border="0">
<tr>
<td height="28"><p align="center"><font size="5" style ="COLOR: mediumblue" face=楷体_GB2312>编译原理网上教学版</font></p></td>
</tr>
<tr>
<td><p align="center">北京大学计算机科学与技术系</p> </td>
</tr>
</table>
<TABLE align=center border=1 width="726">
<TBODY>
<TR>
<TD bgColor=#6699cc height=23><strong><FONT style="COLOR: #dedede;
FONT-SIZE: 13pt"
>8．6基本块的dag表示法 </font></b> </div>
</td>
</tr>
<tr>
<td height="190%" colspan="2"> <blockquote>
<p> 本节和下一节讨论如何对基本块内的程序进行某些等价变换，使得从变换后的程序出发，能生成更有效的目标代码，所谓等价，是指不改变程序的运行结果；所谓有效，主要指目标代码运行时间较短，以及占用的存储空间较小。我们通常称这种基本块内的变换为局部优化。对于实现基本块内的变换而言，一种有效的数据结构是有向非循环图，也称无环路有向图，简称dag（directed
acyclic graph的缩写）。本节将介绍基本块的dag表示及dag的应用。</p>
<p> 一个基本块的dag是一种在其结点上带有下述标记的有向非循环图：</p>
<p> 1.图的叶结点由独特的标识符所标记，所谓独特的标识符是指或者是变量名字或者是常数。根据作用到一个名字上的算符，可以决定需要的是一个名字的左-值或是右－值；大多数叶结点代表右-值。叶结点代表名字的初始值，为此，通常我们将其标识符加上角标0，以避免与那些指示名字的当前值的标识符相混淆。</p>
<p> 2．图的内部结点由一个运算符号标记。代表计算出来的值。</p>
<p> 3．图中各个结点可能附加一个或多个标识符，表示这些标识符具有该结点所代表的值。</p>
<p> 要注意的是，dag不同于流图。一个流图的每个结点均可以用一个dag表示，因为流图中的每个结点代表一个基本块。</p>
<p> <b>例8．6</b> 图8．9是相应于图8．8的三地址代码中的基本块B<span class="down">2</span>。为方便起见，语句序号从（1）开始。与该基本块对应的dag见图8.10。dag的构造算法将在下面讨论，可以看到dag的每一个结点都可代表一个由若干个叶结点形成的公式、即在基本块的入口变量具有的值和常数所形成的计算。例如在图8.10中的t<span class="down">1</span>标记的结点代表</p>
<p align="center">4*j</p>
<p>而t<span class="down">2</span>所标记的结点代表</p>
<p align="center">a-4</p>
<p>即从地址a中减去4，其中a表示数组a第一个元素所在的地址,a-4相当公式（7.5）中的base-low<span class="down">1</span>×w。进而t<span class="down">3</span>所标记的结点则代表</p>
<p align="center">t<span class="down">2</span>[t<span class="down">1</span>]</p>
<p>即从地址b－4偏移4*i个字节后所得到的字的值。 <br>
（1）t<span class="down">1</span>:＝4*i <br>
（2）t<span class="down">2</span>:＝a－4 <br>
（3）t<span class="down">3</span>:＝t<span class="down">2</span>[t<span class="down">1</span>]
<br>
（4）t<span class="down">4</span>:＝4*i <br>
（5）t<span class="down">5</span>:＝b－4 <br>
（6）t<span class="down">6</span>:＝t<span class="down">5</span>[t<span class="down">4</span>]
<br>
（7）t<span class="down">7</span>:＝t<span class="down">3</span>*t<span class="down">6</span>
<br>
（8）t<span class="down">8</span>:＝prod＋t<span class="down">7</span> <br>
（9）prod:=t<span class="down">8</span> <br>
（10）t<span class="down">9</span>:＝i＋l <br>
（11）i:＝t<span class="down">9</span> <br>
（12）if i<=20 goto(1)</p>
<p align="center">图8．9基本块B<span class="down">2</span>的三地址代码</p>
<p align="center"><br>
<img src="8.10.gif" width="475" height="304"> <br>
<br>
图8.10 对应图8．9基本块的dag </p></blockquote>
</td>
</tr>
</table>
<p> </p>
<P align=center style="COLOR: #999999">本书由北京大学出版社1990年版《编译程序设计原理》改编，并加了大量演示程序。<BR></P>
<HR>
<P><BR></P>
<table align=center width=726 cellpadding=0 cellspacing=1 border=0 bordercolor=#999999 style="BACKGROUND-COLOR: #ffffff">
<tr>
<td style="BACKGROUND-COLOR: #dedede; BORDER-BOTTOM-COLOR: #999999; BORDER-BOTTOM-WIDTH: 1px; BORDER-LEFT-COLOR: #999999; BORDER-LEFT-WIDTH: 1px; BORDER-RIGHT-COLOR: #999999; BORDER-RIGHT-WIDTH: 1px; BORDER-TOP-COLOR: #999999; BORDER-TOP-WIDTH: 1px; COLOR: #666666; FONT-SIZE: 12pt;
WIDTH:
180px"
align=middle
>
<A href="8.5.2.htm">回到上页</A>
</td>
<td style="BACKGROUND-COLOR: #fcf4e2; BORDER-BOTTOM-COLOR: #999999; BORDER-BOTTOM-WIDTH: 1px; BORDER-LEFT-COLOR: #999999; BORDER-LEFT-WIDTH: 1px; BORDER-RIGHT-COLOR: #999999; BORDER-RIGHT-WIDTH: 1px; BORDER-TOP-COLOR: #999999; BORDER-TOP-WIDTH: 1px; COLOR: #666666; FONT-SIZE: 12pt;
WIDTH:
180px"
align=middle
>
<A href="#top">页首</A>
</td>
<td style="BACKGROUND-COLOR: #dedede; BORDER-BOTTOM-COLOR: #999999; BORDER-BOTTOM-WIDTH: 1px; BORDER-LEFT-COLOR: #999999; BORDER-LEFT-WIDTH: 1px; BORDER-RIGHT-COLOR: #999999; BORDER-RIGHT-WIDTH: 1px; BORDER-TOP-COLOR: #999999; BORDER-TOP-WIDTH: 1px; COLOR: #666666; FONT-SIZE: 12pt;
WIDTH:
180px"
align=middle
>
<A href="8.6.1.htm">进入下页</A>
</td>
</tr>
</table>
<P align=center style="FONT-SIZE: x-small">《编译程序设计原理》网上教程由<a href="http://www.cs.pku.edu.cn">北京大学计算机科学与技术系</a>制作开发。<BR>由96、97、98级部分同学在丁文魁教授的领导下共同制作完成。如果程序或页面存在问题，请与<A href="mailto:jack.stone@263.net">我们</A>联系。</P>
<P><BR></P>
<P> </P>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -