上海交通大学：《编译原理》教学资源_教学资料_第八周讲义_Machine-Independent Optimizations Ⅰ

Machine-Independent Optimizations I CS308 Compiler Theory 1

Machine-Independent Optimizations Ⅰ CS308 Compiler Theory 1

Code optimization Elimination of unnecessary instructions Replacement of one sequence of instructions by a faster sequence of instructions ·Local optimization Global optimizations based on data flow analyses CS308 Compiler Theory 2

Code optimization • Elimination of unnecessary instructions • Replacement of one sequence of instructions by a faster sequence of instructions • Local optimization • Global optimizations – based on data flow analyses CS308 Compiler Theory 2

The Principal Sources of Optimization 。Optimization -Preserves the semantics of the original program -Applies relatively low-level semantic transformations CS308 Compiler Theory 3

The Principal Sources of Optimization • Optimization – Preserves the semantics of the original program – Applies relatively low-level semantic transformations CS308 Compiler Theory 3

Causes of redundancy Redundant operations are at the source level a side effect of having written the program in a high-level language Each of high-level data-structure accesses expands into a number of low-level arithmetic operations Programmers are not aware of these low-level operations and cannot eliminate the redundancies themselves. By having a compiler eliminate the redundancies The programs are both efficient and easy to maintain. CS308 Compiler Theory 4

Causes of Redundancy • Redundant operations are – at the source level – a side effect of having written the program in a high-level language • Each of high-level data-structure accesses expands into a number of low-level arithmetic operations • Programmers are not aware of these low-level operations and cannot eliminate the redundancies themselves. • By having a compiler eliminate the redundancies – The programs are both efficient and easy to maintain. CS308 Compiler Theory 4

A Running Example:Quicksort void quicksort(int m,int n) /recursively sorts a[m]through a[n]* { int i,j; int v,x; if（n=j)break; x =a[i];a[i]a[j];a[j]=x;/swap a[i],a[j]* x a[i];a[i]a[n];a[n]x;/swap a[i],a[n]* /fragment ends here * quicksort(m,j);quicksort(i+1,n); CS308 Compiler Theory 5

A Running Example: Quicksort CS308 Compiler Theory 5

1=m-1 B1 j=n t1=4*n v a[t1] i=i+1 B2 t2=4*1 t3=a[t2] if t3v 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 t3v 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 t3v 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