📄 9.6.3.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.6.2bc.htm'" ></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.4.htm'" ></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>9.6.3 活跃变量分析</b></font>
<table>
<tr>
<td>    </td>
<td class="content">
<p>
在<font class = "emphasize">活跃变量</font>分析中，我们希望知道，对变量x和点p，x的值在p点开始的路径上是否引用，如果引用，则称x在p点活跃，否则称x在p点死亡。
</p>
<p>
在生成目标代码时活跃变量信息有重要价值。计算存放在寄存器中的值，在基本块中引用后，如果在块的末尾它是死亡的，那么不必生成它的存储指令。还有，在申请寄存器时,如果所有的寄存器都占用了，此时还需要一个寄存器，此时优先分配存放死亡值的寄存器，因为这个值不必存储。
</p>
<p>
我们定义v_in[B]是在B开始点的活跃变量集合，定义v_out[B]是在B结束点的活跃变量集合。v_def[B]是基本块B中有无二义定值，该定值前在B中没有引用的变量集，v_use[B]是基本块B中可能引用，该引用前在B中没有定值的变量集。那么联系v_def和v_use同未知的v_in和v_out的方程是
</p>
 <font color="#FF0000">        v_in[B]=v_use[B]∪（v_out[B]-v_def[B]） <br>
         v_out[B]= ∪v_in[S]                   （方程9.11） <br>
<font size="2">                     s是B的后继
</font> <br></font>
<p>
第一组方程指出，如果变量在某块中定值前有引用，或者在该块结束点活跃并且没有被该块定值，那么它在该块开始点活跃。第二组方程指出，变量在块的结束点活跃，当且仅当它在该块的某个后继块开始点活跃。
</p>
<p>
应该注意（9.11）和（9.9）的到达_定值方程的联系，它们的in和out的作用互相交换了，v_use和v_def分别代替了gen和kill。如同（9.9），（9.11）方程的解也不必唯一，我们要的也是最小解。用于这个最小解的算法本质上是算法9.3的反向版本。因为检查v_in是否改变的方法类似于算法9.3和9.4检查out是否改变的方法，因而,下面的分析活跃变量的算法中省去了检查v_in是否改变的代码。
</p>
<p>
<font class = "definition">算法9.5 活跃变量分析</font>
</p>
<p>
输入：基本块的v_def和v_use都已计算的流图。
</p>
<p>
输出：v_out[B]，即在流图的每个块B出口的活跃变量集合。
</p>
<p>
方法：执行图9.35的程序
</p>
         <font color="#0000FF">for</font> 每个基本块 B
<font color="#0000FF">do</font> v_in[B]:=Ф <br>
            
<font color="#0000FF">while</font> 任何一个v_in[B]有变化 <font color="#0000FF">do</font> <br>
                
<font color="#0000FF">for</font> 每个基本块 B <font color="#0000FF">do</font>
<font color="#0000FF">begin</font> <br>
                     v_out[B]= ∪v_in[S] <br>
                             <font size="2"> S是B的后继 <br></font>
                     v_in[B]:=v_use[B] ∪（v_out[B]-v_def[B]） <br>
                
<font color="#0000FF">end</font> <br>
<p>                 <b>图9.35   活跃变量计算</b> <br>
</td>
</tr>
</table>
<p>
<table>
<tr>
<td><font class="yanshi">       观看演示 </font></td>
<td><font color=blue onmouseover="javascript:style.cursor='hand'" onclick="javascript:open('applet/9632/Page1.htm','_blank','menu=no,toolbar=no,location=no,directories=no,status=no,scrollbars=yes,resizable=yes,copyhistory=no,left=100,top=100,width=800,height=600')">活跃变量算法演示</font></td>
<td><img src="../images/yanshi.gif"></img></td>
</tr>
</table>
</p>
<table align=right width=300>
<tr>
<td>
<img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.2bc.htm'" ></img></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.6.4.htm'" ></td>
</tr>
</table>
</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -