Kĩ thuật lập trình - Bài 13: Tối ưu mã

21/1/2010 1 Bài 13 Tối ưu mã Mở đầu „ Yêu cầu …Chương trình sau khi tối ưu phải tương đương …Tốc độ thực hiện trung bình tăng …Hiệu quả đạt được tương xứng với công sức bỏ ra „ Có thể tối ưu mã vào lúc nào …Mã nguồn- do người lập trình (giải thuật) …Mã trung gian …Mã đích Tối ưu cục bộ 1. Kỹ thuật để cải tiến mã đích một cách cục bộ. 2. Một phương pháp để cải tiến chương trình đích bằng cách xem xét một dãy lệnh trong mã đích và thay thế chúng bằng những đoạn mã ngắn hơn và hiệu quả hơn Xu hướng chính 1. Loại bỏ lệnh dư thừa 2. Thông tin dòng điều khiển 3. Giản lược biểu thức đại số 4. Sử dụng các đặc trưng ngôn ngữ Tối ưu cục bộ „ Tính toán biểu thức hằng x := 32 trở thành x := 64 x := x + 32 „ Mã không đến được goto L2 x := x + 1 Å Không cần „ Tối ưu dòng điều khiển goto L1 trở thành goto L2 L1: goto L2 Å Không cần nếu không còn lệnh sau L2 21/1/2010 2 Tối ưu cục bộ „Giản lược biểu thức đại số x := x + 0 Å Không cần „Mã chết x := 32 Å x không được dùng trong những lệnh tiếp theo y := x + y Æ y := y + 32 „ Giảm chi phí tính toán x := x * 2 Æ x := x + x Æ x := x << 2 Tối ưu trong từng khối cơ sở 1. Loại bỏ biểu thức con chung 2. Tính giá trị hằng 3. Copy Propagation 4. Loại mã chết Ví dụ: a[i+1] = b[i+1] Loại biểu thức con chung t1 = i+1 t2 = b[t1] t3 = i + 1 a[t3] = t2 t1 = i + 1 t2 = b[t1] t3 = i + 1 Å Không cần a[t1] = t2 i = 4 t1 = i+1 t2 = b[t1] [t1] t2 i = 4 t1 = 5 t2 = b[t1] [t1] t2 i là hằng i = 4 t1 = 5 t2 = b[5] a[5] = t2a = a = i = 4 t2 = b[5] a[5] = t2 Mã nhận được: 21/1/2010 3 Tối ưu trên DAG „ Vấn đề cần quan tâm …Loại bỏ biểu thức con chung …Tính các biểu thức hằng …Loại mã chết …Loại những dư thừa cục bộ „ Ứng dụng một phương pháp tối ưu dẫn đến việc tạo ra những đoạn mã có thể ứng dụng phương pháp tối ưu khác. Tối ưu vòng đơn giản „Phương pháp Chuyển những đoạn mã bất biến ra ngoài vòng lặp. Ví dụ: while (i <= limit - 2) Chuyển thành t := limit - 2 while (i <= t) Mã ba địa chỉ của Quick Sort i = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i 1 2 3 4 5 6 t7 = 4 * I t8 = 4 * j t9 = a[t8] a[t7] = t9 t10 = 4 * j a[t10] = x 16 17 18 19 20 21 t3 = a[t2] if t3 < v goto (5) j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto (9) if i >= j goto (23) t6 = 4 * i x = a[t6] 7 8 9 10 11 12 13 14 15 goto (5) t11 = 4 * I x = a[t11] t12 = 4 * i t13 = 4 * n t14 = a[t13] a[t12] = t14 t15 = 4 * n a[t15] = x 22 23 24 25 26 27 28 29 30 Khối cơ bản (basic block) Chuỗi các lệnh kế tiếp nhau trong đó ̣dòng điều khiển đi vào lệnh đầu tiên của khối và ra ở lệnh cuối cùng của khối mà không bị dừng hoặc rẽ nhánh. Ví dụ t1 := a * a t2 := a * b t3 := 2 * t2 t4 := t1 + t2 t5 := b * b t6 := t4 + t5 21/1/2010 4 Giải thuật phân chia các khối cơ bản Input: Dãy lệnh ba địa chỉ. Output: Danh sách các khối cơ bản với mã lệnh ba địa chỉ của từng khối Phương pháp: 1. Xác định tập các lệnh đầu (leader), của từng khối cơ bản i) Lệnh đầu tiên của chương trình là lệnh đầu. ii) Bất kỳ lệnh nào là đích nhảy đến của các lệnh GOTO có hoặc không có điều kiện là lệnh đầu iii) Bất kỳ lệnh nào đi sau lệnh GOTO có hoặc không có điều kiện là lệnh đầu 2. Với mỗi lệnh đầu, khối cơ bản bao gồm nó và tất cả các lệnh tiếp theo không phải là lệnh đầu hay lệnh kết thúc chương trình Ví dụ (1) prod := 0 (2) i := 1 (3) t1 := 4 * i (4) t2 := a[t1] „ Lệnh (1) là lệnh đầu theo quy tắc i, „ Lệnh (3) là lệnh đầu theo quy tắc ii (5) t3 := 4 * i (6) t4 := b[t3] (7) t5 := t2 * t4 (8) t6 := prod + t5 (9) prod := t6 (10) t7 := i + 1 (11) i := t7 (12) if i<=20 goto (3) „ Lệnh sau lệnh (12) là lệnh đầu theo quy tắc iii. „ Các lệnh (1)và (2) tạo nên khối cơ bản thứ nhất. „ Lệnh (3) đến (12) tạo nên khối cơ bản thứ hai. Xác định khối i = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] 1 2 3 4 5 6 7 t7 = 4 * I t8 = 4 * j t9 = a[t8] a[t7] = t9 t10 = 4 * j a[t10] = x goto (5) 16 17 18 19 20 21 22 cơ bản if t3 < v goto (5) j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto (9) if i >= j goto (23) t6 = 4 * i x = a[t6] 8 9 10 11 12 13 14 15 t11 = 4 * i x = a[t11] t12 = 4 * i t13 = 4 * n t14 = a[t13] a[t12] = t14 t15 = 4 * n a[t15] = x 23 24 25 26 27 28 29 30 DAGi = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] t6 = 4 * i x = a[t6] t7 = 4 * i t8 = 4 * j t11 = 4 * i x = a[t11] t12 = 4 * i t13 = 4 * n B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 t9 = a[t8] a[t7] = t9 t10 = 4 * j a[t10] = x goto B2 t14 = a[t13] a[t12] = t14 t15 = 4 * n a[t15] = x B3 B4 21/1/2010 5 Loại biểu thức con chung i = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] t6 = 4 * i x = a[t6] t7 = 4 * i t8 = 4 * j t11 = 4 * i x = a[t11] t12 = 4 * i t13 = 4 * n B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 t9 = a[t8] a[t7] = t9 t10 = 4 * j a[t10] = x goto B2 t14 = a[t13] a[t12] = t14 t15 = 4 * n a[t15] = x B3 B4 Loại biểu thức con chungi = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] t6 = 4 * i x = a[t6] t8 = 4 * j t9 = a[t8] t11 = 4 * i x = a[t11] t12 = 4 * i t13 = 4 * n B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a[t6] = t9 t10= 4 * j a[t10] = x goto B2 t14 = a[t13] a[t12] = t14 t15 = 4 * n a[t15] = x B3 B4 Loại biểu thức con chungi = m - 1j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] t6 = 4 * i x = a[t6] t8 = 4 * j t9 = a[t8] t11 = 4 *i x = a[t11] t12 = 4 * i t13 = 4 * n B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a[t6] = t9 a[t8] = x goto B2 t14 = a[t13] a[t12] = t14 t15 = 4 * n a[t15] = x B3 B4 Loại biểu thức con chungi = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] t6 = 4 * i x = a[t6] t8 = 4 * j t9 = a[t8] t11 = 4 * i x = a[t11] t12 = 4 * i t13 = 4 * n B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a[t6] = t9 a[t8] = x goto B2 t14 = a[t13] a[t12] = t14 t15 = 4 * n a[t15] = x B3 B4 21/1/2010 6 Loại biểu thức con chungi = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] t6 = 4 * i x = a[t6] t8 = 4 * j t9 = a[t8] t11 = 4 * i x = a[t11] t13 = 4 * n t14 = a[t13] B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a[t6] = t9 a[t8] = x goto B2 a[t11] = t14 t15 = 4 * n a[t15] = x B3 B4 Loại biểu thức con chungi = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] t6 = 4 * i x = a[t6] t8 = 4 * j t9 = a[t8] t11 = 4 * i x = a[t11] t13 = 4 * n t [t ] B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a[t6] = t9 a[t8] = x goto B2 14 = a 13 a[t11] = t14 a[t13] = x B3 B4 Loại biểu thức con chungi = m - 1j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] t6 = 4 * i x = a[t6] t8 = 4 * j t9 = a[t8] t11 = 4 * i x = a[t11] t13 = 4 * n t [t ] B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a[t6] = t9 a[t8] = x goto B2 14 = a 13 a[t11] = t14 a[t13] = x B3 B4 Loại biểu thức con chungi = m - 1j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] x = a[t2] t8 = 4 * j t9 = a[t8] a[t2] = t9 t11 = 4 * i x = a[t11] t13 = 4 * n t [t ] B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a[t8] = x goto B2 14 = a 13 a[t11] = t14 a[t13] = x B3 B4 21/1/2010 7 Loại biểu thức con chungi = m - 1j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] x = t3 t8 = 4 * j t9 = a[t8] a[t2] = t9 t11 = 4 * i x = a[t11] t13 = 4 * n t [t ] B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a[t8] = x goto B2 14 = a 13 a[t11] = t14 a[t13] = x B3 B4 Loại biểu thưc con chungi = m - 1j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] x = t3 t9 = a[t4] a[t2] = t9 a[t4] = x t11 = 4 * i x = a[t11] t13 = 4 * n t [t ] B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 goto B2 14 = a 13 a[t11] = t14 a[t13] = x B3 B4 Loại biểu thức con chungi = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] x = t3 a[t2] = t5 a[t4] = x goto B2 t11 = 4 * i x = a[t11] t13 = 4 * n t [t ] B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 14 = a 13 a[t11] = t14 a[t13] = x B3 B4 Common Subexpression Elimination i = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] x = t3 a[t2] = t5 a[t4] = x goto B2 x = t3 t14 = a[t1] a[t2] = t14 [t ] B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a 1 = x B3 B4 Similarly for B6 21/1/2010 8 Loại mã chếti = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] x = t3 a[t2] = t5 a[t4] = x goto B2 x = t3 t14 = a[t1] a[t2] = t14 [t ] B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 a 1 = x B3 B4 Loại mã chếti = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] a[t2] = t5 a[t4] = t3 goto B2 t14 = a[t1] a[t2] = t14 a[t1] = t3 B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 B3 B4 Giảm chi phíi = m - 1 j = n t1 =4 * n v = a[t1] i = i + 1 t2 = 4 * i t3 = a[t2] a[t2] = t5 a[t4] = t3 goto B2 t14 = a[t1] a[t2] = t14 a[t1] = t3 B1 B2 B5 B6 if t3 < v goto B2 j = j – 1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 B3 B4 Giảm chi phíi = m - 1 j = n t1 =4 * n v = a[t1] t2 = 4 * i t4 = 4 * j t2 = t2 + 4 a[t2] = t5 a[t4] = t3 goto B2 t14 = a[t1] a[t2] = t14 a[t1] = t3 B1 B2 B5 B6 t3 = a[t2] if t3 < v goto B2 t4 = t4 - 4 t5 = a[t4] if t5 > v goto B3 if i >= j goto B6 B3 B4