Code Optimization
Kriteria transformasi:
- Tetap menjaga makna program
- Dapat mempercepat waktu eksekusi
- Proses transformasi tidak terlalu lama
Optimasi dapat dilakukan pada level
Struktur code optimizer
Di dalam optimizer, program dipresentasikan dalam flow graph.
Contoh
| (1) | i:=m-1 | (16) | t7 := 4 * i | |
|---|---|---|---|---|
| (2) | j:=n | (17) | t8 := 4 * j | |
| (3) | t1 := 4 * n | (18) | t9 := a[t8] | |
| (4) | v := a[t1] | (19) | a[t7] := t9 | |
| (5) | i := i + 1 | (20) | t10 := 4 * j | |
| (6) | t2 := 4 * i | (21) | a[t10] := x | |
| (7) | t3 := a[t2] | (22) | goto(5) | |
| (8) | if t3 < v goto (5) | (23) | t11 := 4 * i | |
| (9) | j := j - 1 | (24) | x := a[t11] | |
| (10) | t4 := 4 * j | (25) | t12 := 4 * i | |
| (11) | t5 := a[t4] | (26) | t13 := 4 * n | |
| (12) | if t5 < v goto (9) | (27) | t14 := a[t13] | |
| (13) | if i >= j goto (23) | (28) | a[t12] := t14 | |
| (14) | t6 := 4 * i | (29) | t15 := 4 * n | |
| (15) | x := a[t6] | (30) | a[t15] := x |
akan ditransformasikan dalam bentuk:
= flowchart =
Prinsip optimasi:
- Eliminasi ekspresi yang sama
- Copy propagation
- Dead code elimination
- Loop optimazation
- Code motion
Eliminasi lokal dan global menghasilkan
B5
Sebelum -> Sesudah
== || ==
Code MotionL
Copy propagation
Contoh:
=====
A:= d + e -> a:= d + e
B:= d + e -> b:= a
Dead Code Elimination:
Contoh:
:
: -> x := x - k
x := x + T1 y := x - k
y := x + T1
Optimasi Basic Block
Dengan menggunakan presentasi DAG
Contoh:
a:= b + c
b:= a - d
c:= b + c
d:= a - d
direpresentasikan dalam bentuk:
====
Ada 3 (tiga) node -> perlu 3 (tiga) statement.
Jika harga tidak diperlukan, selain di blok tersebut, disederhanakan menjadi
a=b+c
b=a-d
c=d+c
Jika harga b dan d masih dipakai makan presentasi DAG adalah:
Mula-mula:
a:= b + c
b:= b - d
c:= c + d
e:= b + c
===0=0=0=
dan penyederhanaannya
a := b + c
b := b - d
c := c + d
d := b + c
Operasi berdasarkan operasi aljabar
Contoh:
x + 0 = 0 + x = x
x - 0 = x
x *1 = 1*x = x
x/1 = x
-> penyederhanaan ekspresi
Optimasi dengan menggantikan operator.
Contoh:
x ** 2 = x * x
2.0* x = x + x
x/2 = x * 0.5
Optimasi looping.
00000000