、基本块的表示 可以用一个无环路有向 dag(directed acyclic graph)来 表示一个基本,dag是实现基本块内优化变换的有效 表示,可以决定基本块内的公共子表达式,并删除那 些死代码;可以决定在基本块外定值而在基本块内被 引用的变量名字;可以决定基本块内哪些变量名字的 定值可以在基本块外被引用。 为了描述计算过程,我们在无环路有向图的结点上给 出如下标记或附加标记:
11 二、基本块的dag表示 可以用一个无环路有向dag(directed acyclic graph)来 表示一个基本，dag是实现基本块内优化变换的有效 表示，可以决定基本块内的公共子表达式，并删除那 些死代码；可以决定在基本块外定值而在基本块内被 引用的变量名字；可以决定基本块内哪些变量名字的 定值可以在基本块外被引用。 为了描述计算过程，我们在无环路有向图的结点上给 出如下标记或附加标记：
(1)图的叶结点用标识符标变量名或常数作为唯 标记,表示该结点代表所标记的变量或常数的值。至 于是变量的左一值还是右一值,可由作用于变量名的 算符决定,通常为右一值。叶结点代表变量的初值, 加下标0,以示区别。 (2)图的内部结点用运算符op作为标记,该结点的后 继结点所代表的值,为参于运算的分量,因此该内部 结点表示由它的后继结点代表的运算分量经op运算后 的表达式的结果 (3)图中各结点可能附加一个或多个标识符作为附加 标记,表示这些附加的标记标识符具有该结点所代表 的相同的值。 上述无环路有向图称为描述计算过程的dag,简称为 dag 12
12 (1) 图的叶结点用标识符(标识变量名)或常数作为唯一 标记，表示该结点代表所标记的变量或常数的值。至 于是变量的左一值还是右一值，可由作用于变量名的 算符决定，通常为右一值。叶结点代表变量的初值， 加下标0，以示区别。 (2) 图的内部结点用运算符op作为标记，该结点的后 继结点所代表的值，为参于运算的分量，因此该内部 结点表示由它的后继结点代表的运算分量经op运算后 的表达式的结果。 (3) 图中各结点可能附加一个或多个标识符作为附加 标记，表示这些附加的标记标识符具有该结点所代表 的相同的值。 上述无环路有向图称为描述计算过程的dag，简称为 dag.
三、dag的构造 基本块的dag是通过依次处理它的每一个语句而建立起来的, 这里所说的语句是指的三地址代码。通常的语句形式及它 们所对应的dag表示如图75所示: 如果待处理的语句形如x:=yopz,其处理的步骤为 1)在已建立的dag了图中寻找能代表y、z当前值的结点。 (2)若代表y、z当前值的结点至少有一个标记为非常数,则执 行步骤(3),否则执行下列步骤: 执行yopz,令其结果常数为x0。 ●如果,y或z是执行当前语句x:=yopz时新建立的结点,则删 除它。 如果已建立的dag子图中没有标记为x0的常数叶结点,则建立 新的结点n,它的标记为x0。 如果已建立的子图有标记为x0的叶结点,则令该结点为n 执行步骤(4) 13
13 三、dag的构造 基本块的dag是通过依次处理它的每一个语句而建立起来的， 这里所说的语句是指的三地址代码。通常的语句形式及它 们所对应的dag表示如图7.5所示： 如果待处理的语句形如x:=y op z，其处理的步骤为： (1) 在已建立的dag了图中寻找能代表y、z当前值的结点。 (2) 若代表y、z当前值的结点至少有一个标记为非常数，则执 行步骤(3)，否则执行下列步骤： • 执行y op z，令其结果常数为x0。 • 如果，y或z是执行当前语句x:=y op z时新建立的结点，则删 除它。 • 如果已建立的dag子图中没有标记为x0的常数叶结点，则建立 新的结点n，它的标记为x0。 • 如果已建立的子图有标记为x0的叶结点，则令该结点为n。 • 执行步骤(4)
(3)在已建立的dag子图中寻找这样的结点:它标记为o,它的 左子结点为代表y当前值的结点它的右子结点为代表z当前值的 结点。也有两种可能: 已建立的dag子图中寻找这样的结点:它标记为op,它的左 子结点为代表y当前值的结点,它的右子结点为代表z当前值的 结点。也有两种可能: 在已建立的dag子图中没有这样的结点,则建立一新的内部结 n,它以代表y、z当前值的结点作为它的左右子结点,令它标 记为op 在已建立的子图中存在这样的结点,不妨令它为n (4)对于在步骤(2)或(3)中找到的或新建立的结点n,应将x加入 到该结点的附加标记集中,但在此之前如果x(不是x0已出现在 某个结点的附加标记集中,则应先将x从这个附加标记集中删 除。这表明此时x已重新定值,x的当前值已不是原来的那个x (5)处理下一语句,直至结束。 14
14 (3) 在已建立的dag子图中寻找这样的结点：它标记为op，它的 左子结点为代表y当前值的结点它的右子结点为代表z当前值的 结点。也有两种可能： • 已建立的dag子图中寻找这样的结点：它标记为op，它的左 子结点为代表y当前值的结点，它的右子结点为代表z当前值的 结点。也有两种可能： • 在已建立的dag子图中没有这样的结点，则建立一新的内部结 n，它以代表y、z当前值的结点作为它的左右子结点，令它标 记为op。 • 在已建立的子图中存在这样的结点，不妨令它为n。 (4) 对于在步骤(2)或(3)中找到的或新建立的结点n，应将x加入 到该结点的附加标记集中，但在此之前如果x(不是x0)已出现在 某个结点的附加标记集中，则应先将x从这个附加标记集中删 除。这表明此时x已重新定值，x的当前值已不是原来的那个x 了。 (5) 处理下一语句，直至结束。
例73与下列基本块相应的dag的构造过程如图76 ①pi:=3.l4 ②t1:=2*pi ③t2:=R+r ④A:=t1*t2 ⑤t3:=2pi ⑥t4:=R+r ⑦t5:=t2*t4 ⑧t6:=R-r ⑨t7:=t5*t6 ⑩A:=t7-A 15
15 [例7.3] 与下列基本块相应的dag的构造过程如图7.6。 pi:=3.14 t1:=2*pi t2:=R+r A:=t1*t2 t3:=2*pi t4:=R+r t5:=t2*t4 t6:=R-r t7:=t5*t6 A:=t7-A