Bài giảng "Xây dựng chương trình dịch - Bài 13: Tối ưu mã" cung cấp cho người học các kiến thức: Tối ưu hóa cục bộ, tối ưu trong từng khối cơ sở, tối ưu trên DAG, tối ưu vòng đơn giản, giải thuật phân chia các khối cơ bản. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên Công nghệ thông tin và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | 21/1/2010 Mở đầu Bài 13 Tối ưu mã 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 g chính Tối ưu cục bộ 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ữ 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í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 1 21/1/2010 Tối ưu cục bộ Giản Tối ưu trong từng khối cơ sở lược biểu thức đại số x := x + 0 Å Không cần Mã 1. chết 2. x := 32 Å x không được dùng trong những lệnh tiếp theo y := x + y Æ y := y + 32 3. 4. Loại bỏ biểu thức con chung Tính giá trị hằng Copy Propagation Loại mã chết Giảm chi phí tính toán x := x * 2 Æ x := x + x Æ x := x 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 pháp Chuyển những đoạn mã bất biến ra ngoài vòng lặp. Ví dụ: while (i 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 B5 B6 t6 = 4 * i t11 = 4 * i x = a[t6] x = a[t11] t2 = 4 * i t7 = 4 * i t12 = 4 * i t3 = a[t2] t8 = 4 * j t13 = 4 * n B2 i=i +1 B3 j=j–1 t4 = 4 * j t5 = a[t4] if t5 > v goto B3 t10 = 4 * j t15 = 4 * n a[t10] = x a[t15] = x goto B2 B4 if i >= j goto B6 4 21/1/2010 B1 B1 i=m-1 j=n i=m-1 Loại biểu thức con chung j=n t1 =4 * n v = a[t1] v = a[t1] B5 t6 = 4 * i B2 i=i +1 B3 Loại biểu thức
