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<=m)return; /fragment begins here * i m-1;j=n;v=a[n]; while (1){ do i =i+1;while (a[i]v); do j=j-1;while (a[j]v); if (i>=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