DAG图的例子 bd a t b do bO
DAG图的例子 • + b c a • - a d b • + b c c • - a d d + - + b0 c0 d0 b,d a
四元式的分类 0型: 1型: op X y(单目运算) 2型: op x y Z relopx y 2(z是序号)
四元式的分类 • 0型： = x _ y • 1型： op x _ y(单目运算） • 2型： op x y z relop x y z(z是序号)
基本块DAG图构造算法 输入:一个基本块 输出:相应DAG图 算法说明: 通过逐个扫描四元式来逐渐建立DAG图。 函数node(x)表示和标识符x相应的最近建立的节点。他代 表扫描到当前的四元式的时候,标识符x的值对应的节点。 步骤1:初始化:无任何节点,node对任何标识符无定义。 步骤2:依次对基本块中的每个四元式 op y zi行下面的步骤。 如果node(x)没有定义,建立叶子节点,标记为x,让node(x) 等于这个节点。如果node(y)没有定义,为y建立节点 如果四元式为0型,n node(x 如果四元式为1型,寻找标记为op且子节点为node(x)的节 点,如果找不到,建立这样的节点
基本块DAG图构造算法 • 输入：一个基本块 输出：相应DAG图 • 算法说明： – 通过逐个扫描四元式来逐渐建立DAG图。 – 函数node(x)表示和标识符x相应的最近建立的节点。他代 表扫描到当前的四元式的时候，标识符x的值对应的节点。 • 步骤1：初始化：无任何节点，node对任何标识符无定义。 • 步骤2：依次对基本块中的每个四元式op x y z执行下面的步骤。 – 如果node(x)没有定义，建立叶子节点，标记为x，让node(x) 等于这个节点。如果node(y)没有定义，为y建立节点。 – 如果四元式为0型，n=node(x); – 如果四元式为1型，寻找标记为op且子节点为node(x)的节 点，如果找不到，建立这样的节点
基本块DAG图构造算法(续) 对于2型四元式,查看是否存在标记为op的节点,且其左右 子节点分别为node(x)和node(y)。如果找不到,建立这样的 节点。 步骤3:如果z为标识符,从node(z)中删除标识符乙,并把z加入 到步骤4所找到或者建立的节点n的标识符表中,并设置nde(z) 为n 说明 处理2型四元式的时候,如果op是可交换的运算符, 可以其左右节点可以互换
基本块DAG图构造算法（续） – 对于2型四元式，查看是否存在标记为op的节点，且其左右 子节点分别为node(x)和node(y)。如果找不到，建立这样的 节点。 • 步骤3：如果z为标识符，从node(z)中删除标识符z，并把z加入 到步骤4所找到或者建立的节点n的标识符表中，并设置node(z) 为n。 • 说明： – 处理2型四元式的时候，如果op是可交换的运算符， 可以其左右节点可以互换
生成DAG图的例子 t2 t3=[b t3 w t2 t5 prod t5 t6 od+ t7 20(3) prodO 20
生成DAG图的例子 • * 4 i t1 =[] a t1 t2 • * 4 i t3 =[] b t3 t4 • * t2 t4 t5 + prod t5 t6 • = t6 prod + i 1 t7 • = t7 i <= i 20 (3) a 4 i * =[] =[] b * + prod0 1 + 20 <=