Optimization Examples and Quicksort in Algorithms

An Optimization Example 1

Roadmap Last time Path problems Shortest-distance problem Started on concrete semantics Showing you the how, but not the why Today: the why Via an optimization example 2

Quicksort* void quicksort(int m, int n) { int i, j, v, x; if (n <= m) return; 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; } x = a[i]; a[i] = a[n]; a[n] = x; quicksort(m,j); quicksort(i+1,n); } 3 *Example from Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986

Three-address code (IR) Roughly: assembly code but an unbounded number of registers no explicit manipulation of the stack, ARs, etc. Types of 3-address statements x := y copy statements x := op y unary op x := y op z binary op x := y[i] indexed fetch x[i] := y indexed copy goto P goto x := &y assign address x := *y assign indirect *x := y store indirect if x relop y goto P if-then param x1; param x2; ; param xn; call p,n call return y return 4

Three-address code (IR) Assign t1 := -c t2 := b * t1 t3 := -c t4 := b * t3 t5 := t2 + t4 a := t5 Id[a] t5 Plus t2 t4 Times Times Id[b] t1 t3 Id[b] UMinus UMinus Id[c] Id[c] 5

1) i := m-1 2) j := n 3) t1 := 4*n 4) v := a[t1] Quicksort 5) i := i+1 6) t2 := 4*i 7) t3 := a[t2] 8) if t3 < v goto (5) void quicksort(int m, int n) { int i, j, v, x; if (n <= m) return; 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; } x = a[i]; a[i] = a[n]; a[n] = x; quicksort(m,j); quicksort(i+1,n); } 9) j := j-1 10) t4 := 4*j 11) t5 :- a[t4] 12) if t5 > v goto (9) 14) t6 := 4*i 15) x := a[t6] 16) t7 := 4*i 17) t8 := 4*j 18) t9 := a[t8] 19) a[t7] := t9 20) t10 := 4*j 21) a[t10] := x 22) goto (5) 13) if i >= j goto (23) 23) t11 := 4*i 24) x := a[t11] 25) t12 := 4*i 26) t13 := 4*n 27) t14 := a[t13] 28) a[t12] = t14 29) t15 := 4*n 30) a[t15] := x 6

Scope of transformations Local transformations within a single basic block Intraprocedural transformations within a single procedure Interprocedural transformation across procedure boundaries 7

Kinds of optimizing transformations Remove redundant or useless computations common-subexpression elimination copy propagation unreachable-code elimination constant folding Loop optimizations code motion (move code outside loop) reduction in strength 8

Regardless of level Loop until done: Analyze program to gather facts Apply transformation Analyze program perform dataflow analysis on the program s CFG More precisely Analyze program to gather facts Loop until done: Apply transformation Update facts to reflect the new state of the code 9

What kinds of analyses? Possible values of variables v is a constant k v points only to vars in set S function pointer f can only hold the address of a procedure in set P label var l can only hold labels in set L can pointer p be NULL at point p? what are upper/lower bounds on the value of x at point p? does x == y hold at point p? Other execution properties var v may/may not be used subsequently (live/dead) value assigned at def-site d: x = may be used at use-site u: x (d reaches u) expression e has always already been computed ( is available ) whenever execution reaches point p can there be any overflows in the computation at point p 10

1) i := m-1 2) j := n 3) t1 := 4*n 4) v := a[t1] 5) i := i+1 6) t2 := 4*i 7) t3 := a[t2] 8) if t3 < v goto (5) 9) j := j-1 10) t4 := 4*j 11) t5 :- a[t4] 12) if t5 > v goto (9) 14) t6 := 4*i 15) x := a[t6] 16) t7 := 4*i 17) t8 := 4*j 18) t9 := a[t8] 19) a[t7] := t9 20) t10 := 4*j 21) a[t10] := x 22) goto (5) 13) if i >= j goto (23) 23) t11 := 4*i 24) x := a[t11] 25) t12 := 4*i 26) t13 := 4*n 27) t14 := a[t13] 28) a[t12] = t14 29) t15 := 4*n 30) a[t15] := x 11

1) i := m-1 2) j := n 3) t1 := 4*n 4) v := a[t1] 5) i := i+1 6) t2 := 4*i 7) t3 := a[t2] 8) if t3 < v goto (5) 9) j := j-1 10) t4 := 4*j 11) t5 :- a[t4] 12) if t5 > v goto (9) 14) t6 := 4*i 15) x := a[t6] 16) 17) t8 := 4*j 18) t9 := a[t8] 19) a[t6] := t9 20) 21) a[t8] := x 22) goto (5) 13) if i >= j goto (23) 23) t11 := 4*i 24) x := a[t11] 25) t12 := 4*i 26) t13 := 4*n 27) t14 := a[t13] 28) a[t12] = t14 29) t15 := 4*n 30) a[t15] := x 12

1) i := m-1 2) j := n 3) t1 := 4*n 4) v := a[t1] 5) i := i+1 6) t2 := 4*i 7) t3 := a[t2] 8) if t3 < v goto (5) 9) j := j-1 10) t4 := 4*j 11) t5 :- a[t4] 12) if t5 > v goto (9) 14) 15) x := t3 16) 17) 18) 19) a[t2] := t5 20) 21) a[t4] := x 22) goto (5) 13) if i >= j goto (23) Copy propagation 23) t11 := 4*i 24) x := a[t11] 25) t12 := 4*i 26) t13 := 4*n 27) t14 := a[t13] 28) a[t12] = t14 29) t15 := 4*n 30) a[t15] := x 13

1) i := m-1 2) j := n 3) t1 := 4*n 4) v := a[t1] x always defined before (re)used 5) i := i+1 6) t2 := 4*i 7) t3 := a[t2] 8) if t3 < v goto (5) x is dead 9) j := j-1 10) t4 := 4*j 11) t5 :- a[t4] 12) if t5 > v goto (9) 14) 15) x := t3 16) 17) 18) 19) a[t2] := t5 20) 21) a[t4] := t3 22) goto (5) 13) if i >= j goto (23) 23) t11 := 4*i 24) x := a[t11] 25) t12 := 4*i 26) t13 := 4*n 27) t14 := a[t13] 28) a[t12] = t14 29) t15 := 4*n 30) a[t15] := x 14

1) i := m-1 2) j := n 3) t1 := 4*n 4) v := a[t1] 5) i := i+1 6) t2 := 4*i 7) t3 := a[t2] 8) if t3 < v goto (5) 9) j := j-1 10) t4 := 4*j 11) t5 :- a[t4] 12) if t5 > v goto (9) 14) 15) 16) 17) 18) 19) a[t2] := t5 20) 21) a[t4] := t3 22) goto (5) 13) if i >= j goto (23) 23) t11 := 4*i 24) x := a[t11] 25) t12 := 4*i 26) t13 := 4*n 27) t14 := a[t13] 28) a[t12] = t14 29) t15 := 4*n 30) a[t15] := x 15

Dead-code elimination A variable is live at a point p if its value can be used subsequently. A variable that is not live is dead. Idea: remove assignments to dead variables p: x := x is live just after p if goto q q: r: x x := 16

1) i := m-1 2) j := n 3) t1 := 4*n 4) v := a[t1] Reduction in strength: replace * with + E.g., replace j := j-1 t4 := 4*j with j := j-1 t4 := t4 - 4 5) i := i+1 6) t2 := 4*i 7) t3 := a[t2] 8) if t3 < v goto (5) 9) j := j-1 10) t4 := 4*j 11) t5 :- a[t4] 12) if t5 > v goto (9) 14) 15) 16) 17) 18) 19) a[t2] := t5 20) 21) a[t4] := t3 22) goto (5) 13) if i >= j goto (23) 23) t11 := 4*i 24) x := a[t11] 25) t12 := 4*i 26) t13 := 4*n 27) t14 := a[t13] 28) a[t12] = t14 29) t15 := 4*n 30) a[t15] := x 17

1) i := m-1 2) j := n 3) t1 := 4*n 4) v := a[t1] Reduction in strength: replace * with + E.g., replace j := j-1 t4 := 4*j with j := j-1 t4 := t4 - 4 5) i := i+1 6) t2 := 4*i 7) t3 := a[t2] 8) if t3 < v goto (5) t4 := 4*j 9) j := j-1 10) t4 := t4 - 4 11) t5 :- a[t4] 12) if t5 > v goto (9) 14) 15) 16) 17) 18) 19) a[t2] := t5 20) 21) a[t4] := t3 22) goto (5) 13) if i >= j goto (23) 23) t11 := 4*i 24) x := a[t11] 25) t12 := 4*i 26) t13 := 4*n 27) t14 := a[t13] 28) a[t12] = t14 29) t15 := 4*n 30) a[t15] := x 18

i := m-1 j := n t1 := 4*n v := a[t1] t2 := 4*i t4 := 4*j 1) 2) 3) 4) i := m-1 j := n t1 := 4*n v := a[t1] 5) 6) 7) 8) i := i+1 t2 := 4*i t3 := a[t2] if t3 < v goto (5) t2 := t2+4 t3 := a[t2] if t3 < v goto (5) 9) 10) 11) 12) j := j-1 t4 := 4*j t5 :- a[t4] if t5 > v goto (9) t4 := t4 - 4 t5 :- a[t4] if t5 > v goto (9) 14) 15) 16) 17) 18) 19) 20) 21) 22) t6 := 4*i x := a[t6] t7 := 4*i t8 := 4*j t9 := a[t8] a[t7] := t9 t10 := 4*j a[t10] := x goto (5) a[t2] := t5 a[t4] := t3 goto (5) 13) if i >= j goto (23) if t2 >= t4 goto (23) 23) 24) 25) 26) 27) 28) 29) 30) t11 := 4*i x := a[t11] t12 := 4*i t13 := 4*n t14 := a[t13] a[t12] = t14 t15 := 4*n a[t15] := x t14 := a[t1] a[t2] = t14 a[t1] := t3