DAG图的应用 ·公共子表达式:构造中,寻找是否有标记为op 且子节点为node(x),node(y)的节点时,自然完 成了公共子表达式的寻找。 在基本块中,其值被引用的标识符:构造了叶 子节点的标识符 结果能够在基本块外被引用的四元式 op Z 设它对应的节点为n,如果DAG图构造结束的 时候,n的标志符表不为空
DAG图的应用 • 公共子表达式：构造中，寻找是否有标记为op 且子节点为node(x), node(y)的节点时，自然完 成了公共子表达式的寻找。 • 在基本块中，其值被引用的标识符：构造了叶 子节点的标识符。 • 结果能够在基本块外被引用的四元式op x y z。 设它对应的节点为n，如果DAG图构造结束的 时候，n的标志符表不为空
Ⅱ=和&=运算符的处理 = A ·对数组的赋值需要特别的处理,这是因为数组的下标是变量。 对于数组元素的赋值可能改变数组中任何一个元素的值 []A1 tI A t2 &= y t2 t2 A A[并不是公共子表达式 在处理对数组A的元素的赋值四元式的时候,应该注销所有以 =为标记,A为左节点的节点。从而不可能在此节点的标识符 表中再附上其他的标识符 处理对指针所指空间的赋值的时候,同样要注销相应的节点, 如果不能确定指针指向的范围,那么,需要注销所有的节点
[]=和&=运算符的处理 • 对数组的赋值需要特别的处理，这是因为数组的下标是变量。 对于数组元素的赋值可能改变数组中任何一个元素的值。 • =[] A i t1 []= A j t2 • &= y t2 t2 =[] A i t3 • A[i]并不是公共子表达式。 • 在处理对数组A的元素的赋值四元式的时候，应该注销所有以 =[]为标记，A为左节点的节点。从而不可能在此节点的标识符 表中再附上其他的标识符。 • 处理对指针所指空间的赋值的时候，同样要注销相应的节点。 如果不能确定指针指向的范围，那么，需要注销所有的节点。 A i =[] j t1 []= t2 y &= =[]
从DAG图到四元式序列 在DAG图中,有些运算已经进行了合并。 如果不考虑[和&=算符,可以依照DAG图中的拓扑排 序得到的次序进行。但是,有了[=和&=算符之后,计 算的次序必须修正。 实际上,我们可以按照各个节点生成的顺序来从DAG 图生成四元式序列
从DAG图到四元式序列 • 在DAG图中，有些运算已经进行了合并。 • 如果不考虑[]=和&=算符，可以依照DAG图中的拓扑排 序得到的次序进行。但是，有了[]=和&=算符之后，计 算的次序必须修正。 • 实际上，我们可以按照各个节点生成的顺序来从DAG 图生成四元式序列
从DAG重建四元式序列算法 按照DAG图中的各个节点生成的次序,对于每个节点作如 下处理: 若是叶子节点,且附加标识符表为空,不生成四元式 若是叶子节点,标记为x,附加标识符为z,生成=xz 若是内部节点,附加标识符为z,根据其标记op和子节点 数目,生成下列4种形式的四元式。 Op不是=或者=,也不是 relop,有两个子节点,生 成opx 如果是[或者=,生成op 如果是 relop,生成 relop x z,z是基本块 序号 只有一个子节点,生成opX
从DAG重建四元式序列算法 • 按照DAG图中的各个节点生成的次序，对于每个节点作如 下处理： – 若是叶子节点，且附加标识符表为空，不生成四元式。 – 若是叶子节点，标记为x，附加标识符为z，生成= x z。 – 若是内部节点，附加标识符为z，根据其标记op和子节点 数目，生成下列4种形式的四元式。 • Op不是=[]或者[]=，也不是relop，有两个子节点，生 成 op x y z • 如果是=[]或者[]=，生成op x y z。 • 如果是relop，生成 relop x y z，z是基本块 序号。 • 只有一个子节点，生成 op x _ z
从DAG重建四元式序列算法(续) 若是内部节点,且无附加标识符,则添加一个局部于本基 本块的临时性附加标识符,按照上一情况生成。 如果节点的标识符重包含多个附加标识符z1,Z2,水k时: 若是叶子节点,标记为z,生成一系列四元式 ZI Z z2 Z Zn 不是叶子节点,生成四元式序列: Z Z2 Z Zn
从DAG重建四元式序列算法(续) – 若是内部节点，且无附加标识符，则添加一个局部于本基 本块的临时性附加标识符，按照上一情况生成。 – 如果节点的标识符重包含多个附加标识符z1,z2,…,zk时： • 若是叶子节点，标记为z，生成一系列四元式 – = z z1 – = z z2 – … … … – = z zn • 不是叶子节点，生成四元式序列： – = z z2 – … … … – = z zn