7.3基本块和流图 ·把三地址语句序列划分成基本块 (1)首先确定所有的入口语句 序列的第一个语句是入口语句 能由条件转移语句或无条件转移语句转到的语句 是入口语句 紧跟在条件转移语句或无条件转移语句后面的语 句是入口语句 (2)每个入口语句到下一个入口语句之前（或到 程序结束)的语句序列构成一个基本块
7 3. 基本块和流图 • 把三地址语句序列划分成基本块 (1) 首先确定所有的入口语句 – 序列的第一个语句是入口语句 – 能由条件转移语句或无条件转移语句转到的语句 是入口语句 – 紧跟在条件转移语句或无条件转移语句后面的语 句是入口语句 (2) 每个入口语句到下 个一 入口语句之前（或到 程序结束）的语句序列构成一个基本块
7.3基本块和流图 prod 0 (1)prod 0 i=1 （2)i=1 028H5608P10 t1=4*i1 t=alt l =4*i 74 a[ti] t4= b[t;l == 4*1 t2*t b[ts】 t=prod +t5 ts = 2* ts B2 prod prod t6 0 t6 t2=i+ t i +1 i=t7 i= ifi <= (12) ifi<=20 goto (3) 20goto(3)
7 3. 3 基本块和流图 (1) prod = 0 (2) i = 1 (1)prod = 0 ( 2 ) i=1 B 1 (3) t 1 = 4 i ( 4 ) t 2= a [ t 1 ] ( ) ( 3 ) t ( ) 1 = 4 i 2 [ 1 ] (5 ) t 3 = 4 i ( 6 ) t 4 = b[t 3 ] ( ) 1 (4) t 2= a[t 1 ] (5) t 3 = 4 i ( 6 ) t b[t ] ( 6 ) t 4 b[t 3 ] (7 ) t 5 = t 2 t 4 ( 8 ) t = prod + t ( 6 ) t 4 = b[t 3 ] (7) t 5 = t 2 t 4 ( 8 ) t = prod + t B 2 ( 8 ) t 6 prod + t 5 (9 ) prod = t 6 (10 ) t = i + 1 ( 8 ) t 6 = prod + t 5 (9) prod = t 6 (10 ) t (10 ) t 7 = i + 1 7 = i + 1 (11) i = t 7 (12 ) if i < 20 t ( 3 ) (10 ) t 7 i + 1 (11) i = t 7 (12 ) i f i <= 20 goto ( 3 ) (12 ) if i < = 20 go t o ( 3 ) ( ) g ( )
7.3基本块和流图 7.3.2基本块的优化 术语： 三地址语句x=y+z引用y和z并对x定值 个名字的值在基本块的某一点以后还要引用的话 则说这个名字在该点是活跃的 基本块的等价 两个基本块的出口点有同样的活跃变量集合 对其中每个活跃变量，代表其值的两个表达式相等 有很多等价变换可用于基本块 局部变换 全局变换
7 3. 3 基本块和流图 7.3.2 基本块的优化 • 术语 ： – 三地址语句x=y+z引用 y 和 z并对 x定值 – 一个名字的值在基本块的某 个名字的值在基本块的某 点以后还要引用的话 一点以后还要引用的话 ，则说这个名字在该点是活跃 的 • 基本块的等价 – 两个基本块的出口点有同样的活跃变量集合 – 对其中每个活跃变量 ，代表其值的两个表达式相等 • 有很多等价变换可用于基本块 – 局部变换 – 全局变换
7.3基本块和流图 删除局部公共子表达式 a=b+c a=b+c b=a-d b=a-d c=b+c c=b+c d a-d d=b ·删除死代码 定值x=y+z以后不再引用x,则称x为死变量
7 3. 基本块和流图 • 删除局部公共子表达式 a=b+c a=b+c b = a d b = a d c=b+c c=b+c d=a d d=b • 删除死代码 定值x=y + z以后不再引用x，则称x为死变量
7.3基本块和流图 交换相邻的独立语句 t b+c t=x+y t=x+y t b+c 当且仅当t和t,不相同，x和y都不是t1, 并且b和c都不是t2 。代数变换 X=X+0 可以删除 X=X*1 可以删除 X=y**2 改成x=y*y
7 3. 基本块和流图 • 交换相邻的独立语句 t1 = b + c t2 t = x + y 1 b + c t2 x + y t2 =x+y t1 =b+c 当且仅当t1和t2不相同，x和y都不是t 1 2 1， 并且b和c都不是t2 • 代数变换 x=x+0 可以删除 x=x 1 可以删除 x = y 2 改成x = y y