1=m-1 B1 j=n t1=4*n v a[t1] i=i+1 B2 t2=4*1 t3=a[t2] if t3<v goto B2 j=j-1 B3 t4=4*j t5=a[t4] if t5>v goto B3 if i>=j goto B BA t6=4*i B5 t11=4*i B6 x a[t6] x=a[t11] t7=4*i t12=4*i t8=4*j t13=4*n t9=a[t8] t14=a[t13] a[t7]=t9 a[t12]=t14 t10=4*j t15=4*n a[t10]=x a[t15]=x goto B2 6
CS308 Compiler Theory 6
Semantics-Preserving Transformations A number of ways in which a compiler can improve a program without changing the function it computes Common-sub expression elimination Copy propagation Dead-code elimination Constant folding CS308 Compiler Theory 7
Semantics-Preserving Transformations • A number of ways in which a compiler can improve a program without ch i hf i i hang ing t he funct ion it computes – Common-sub expression elimination – Copy propagation Copy propagation – Dead-code elimination – Constant folding CS308 Compiler Theory 7
Common Subexpressions Common subexpression Previously computed The values of the variables not changed ·Local:: t6=4*i B5 t6=4*1 B5 x a[t6] x a[t6] t7=4*1 t8=4*j t8=4*j t9=a[t8] t9=a[t8] a[t6]=t9 a[t7]=t9 a[t8]=x t10=4*j goto B2 a[t10]=x goto B2 (a)Before. (b)After. CS308 Compiler Theory 8
Common Subexpressions • Common subexpression – Previously compute d – The values of the variables not changed • Local: CS308 Compiler Theory 8
1=m-1 B1 j=n t1=4*n v=a[tl] ● Global i-i+1 B2 t2=4*1 t3=a[t2] if t3<v goto B2 j=j-1 B3 土4三4出子 t5=a[t4】 if t5>v goto B3 if i>mj goto B6 Ba t6=4*1 B5 t11=4*1 B6 X =a[t6] x=a[t11] t12=4*1 t8=4*j t13=4*n t9=aft8] t14=a[t13] a[t6]=t9 a[t12】=t14 a[t8]=x t15=4*n goto B2 a[t15】=× 9
Common Subexpressions • Global CS308 Compiler Theory 9
1"m-1 9、 j=n t1=4*n v=a[ti] 1=1+1 B2 t2■4*1 t3=a[t2] if t3<v goto B2 j=j-1 B3 t4=4*1 t5=a[t4] if t5>v goto B3 if i>= goto B6 BA ×=t3 B5 x t3 B6 a[t2】=t5 t14=a[t1] a[t4】=× a[t2]=t14 goto B2 a[t1]=× CS308 Compiler Theory 10
CS308 Compiler Theory 10