Bài giảng Xây dựng chương trình dịch: Bài 13 - Nguyễn Thị Thu Hương

21/1/2010<br /> <br /> Mở đầu<br /> „<br /> <br /> Bài 13<br /> Tối ưu mã<br /> „<br /> <br /> Tối ưu cục bộ<br /> 1.<br /> <br /> Kỹ thuật để cải tiến mã đích một cách cục bộ.<br /> <br /> 2.<br /> <br /> Một phương pháp để cải tiến chương trình đích bằng cách xem xét một<br /> dãy lệnh trong mã đích và thay thế chúng bằng những đoạn mã ngắn hơn<br /> và hiệu quả hơn<br /> <br /> Xu hướng<br /> g chính<br /> <br /> Tối ưu cục bộ<br /> „<br /> <br /> „<br /> <br /> 1. Loại bỏ lệnh dư thừa<br /> 2. Thông tin dòng điều khiển<br /> 3. Giản lược biểu thức đại số<br /> 4. Sử dụng các đặc trưng ngôn ngữ<br /> <br /> Yêu cầu<br /> … Chương trình sau khi tối ưu phải tương<br /> đương<br /> … Tốc độ thực hiện trung bình tăng<br /> … Hiệu quả đạt được tương xứng với công sức<br /> bỏ ra<br /> Có thể tối ưu mã vào lúc nào<br /> … Mã nguồn- do người lập trình (giải thuật)<br /> … Mã trung gian<br /> … Mã đích<br /> <br /> „<br /> <br /> Tính toán biểu thức hằng<br /> x := 32<br /> trở thành<br /> x := 64<br /> x := x + 32<br /> Mã không đến được<br /> goto L2<br /> x := x + 1 Å Không cần<br /> Tối ưu dòng điều khiển<br /> goto L1<br /> trở thành<br /> goto L2<br /> …<br /> L1: goto L2 Å Không cần nếu không còn lệnh<br /> sau L2<br /> <br /> 1<br /> <br /> 21/1/2010<br /> <br /> Tối ưu cục bộ<br /> „ Giản<br /> <br /> Tối ưu trong từng khối cơ sở<br /> <br /> lược biểu thức đại số<br /> <br /> x := x + 0 Å Không cần<br /> „ Mã<br /> <br /> 1.<br /> <br /> chết<br /> <br /> 2.<br /> <br /> x := 32 Å x không được dùng trong<br /> những lệnh tiếp theo<br /> y := x + y<br /> Æ y := y + 32<br /> „<br /> <br /> 3.<br /> 4.<br /> <br /> Loại bỏ biểu thức con chung<br /> Tính giá trị hằng<br /> Copy Propagation<br /> Loại mã chết…<br /> <br /> Giảm chi phí tính toán<br /> x := x * 2<br /> <br /> Æ x := x + x<br /> Æ x := x v goto (9)<br /> <br /> 27<br /> <br /> t14 = a[t13]<br /> <br /> 13<br /> <br /> if i >= j goto (23)<br /> <br /> 28<br /> <br /> a[t12] = t14<br /> <br /> 14<br /> <br /> t6 = 4 * i<br /> <br /> 29<br /> <br /> t15 = 4 * n<br /> <br /> 15<br /> <br /> x = a[t6]<br /> <br /> 30<br /> <br /> a[t15] = x<br /> <br /> pháp<br /> <br /> Chuyển những đoạn mã bất biến ra ngoài vòng<br /> lặp.<br /> Ví dụ:<br /> while (i v goto B3<br /> <br /> t10 = 4 * j<br /> <br /> t15 = 4 * n<br /> <br /> a[t10] = x<br /> <br /> a[t15] = x<br /> <br /> goto B2<br /> <br /> B4<br /> if i >= j goto B6<br /> <br /> 4<br /> <br /> 21/1/2010<br /> <br /> B1<br /> <br /> B1<br /> i=m-1<br /> j=n<br /> <br /> i=m-1<br /> <br /> Loại biểu thức con chung<br /> <br /> j=n<br /> <br /> t1 =4 * n<br /> v = a[t1]<br /> <br /> v = a[t1]<br /> <br /> B5<br /> <br /> t6 = 4 * i<br /> <br /> B2<br /> i=i +1<br /> <br /> B3<br /> <br /> Loại biểu thức con chung<br /> <br /> t1 =4 * n<br /> <br /> B6<br /> t11 = 4 * i<br /> <br /> x = a[t6]<br /> <br /> x = a[t11]<br /> <br /> t2 = 4 * i<br /> <br /> t7 = 4 * i<br /> <br /> t12 = 4 * i<br /> <br /> t3 = a[t2]<br /> <br /> t8 = 4 * j<br /> <br /> if t3 < v goto B2<br /> <br /> t13 = 4 * n<br /> <br /> t9 = a[t8]<br /> <br /> t14 = a[t13]<br /> <br /> a[t7] = t9<br /> <br /> a[t12] = t14<br /> <br /> j=j–1<br /> t4 = 4 * j<br /> t5 = a[t4]<br /> <br /> t10 = 4 * j<br /> <br /> t15 = 4 * n<br /> <br /> a[t10] = x<br /> <br /> a[t15] = x<br /> <br /> i=i +1<br /> <br /> B6<br /> t6 = 4 * i<br /> <br /> t11 = 4 * i<br /> <br /> x = a[t6]<br /> <br /> x = a[t11]<br /> <br /> t2 = 4 * i<br /> <br /> t8 = 4 * j<br /> <br /> t12 = 4 * i<br /> <br /> t3 = a[t2]<br /> <br /> t9 = a[t8]<br /> <br /> if t3 < v goto B2<br /> <br /> t13 = 4 * n<br /> <br /> a[t6] = t9<br /> <br /> t14 = a[t13]<br /> <br /> t10= 4 * j<br /> <br /> a[t12] = t14<br /> <br /> B3<br /> j=j–1<br /> t4 = 4 * j<br /> t5 = a[t4]<br /> <br /> goto B2<br /> <br /> if t5 > v goto B3<br /> <br /> B5<br /> <br /> B2<br /> <br /> a[t10] = x<br /> <br /> t15 = 4 * n<br /> <br /> goto B2<br /> <br /> a[t15] = x<br /> <br /> if t5 > v goto B3<br /> <br /> B4<br /> <br /> B4<br /> if i >= j goto B6<br /> <br /> if i >= j goto B6<br /> <br /> B1<br /> <br /> B1<br /> i=m-1<br /> j=n<br /> <br /> i=m-1<br /> <br /> Loại biểu thức con chung<br /> <br /> j=n<br /> <br /> t1 =4 * n<br /> v = a[t1]<br /> <br /> B2<br /> i=i +1<br /> <br /> B5<br /> <br /> v = a[t1]<br /> <br /> B6<br /> t6 = 4 * i<br /> <br /> t11 = 4 *i<br /> <br /> x = a[t6]<br /> <br /> x = a[t11]<br /> <br /> t2 = 4 * i<br /> <br /> t8 = 4 * j<br /> <br /> t12 = 4 * i<br /> <br /> t3 = a[t2]<br /> <br /> t9 = a[t8]<br /> <br /> if t3 < v goto B2<br /> <br /> t13 = 4 * n<br /> <br /> a[t6] = t9<br /> <br /> t14 = a[t13]<br /> <br /> a[t8] = x<br /> <br /> a[t12] = t14<br /> <br /> B3<br /> j=j–1<br /> t4 = 4 * j<br /> t5 = a[t4]<br /> <br /> goto B2<br /> <br /> B2<br /> i=i +1<br /> <br /> B6<br /> t6 = 4 * i<br /> <br /> t11 = 4 * i<br /> <br /> x = a[t6]<br /> <br /> x = a[t11]<br /> <br /> t2 = 4 * i<br /> <br /> t8 = 4 * j<br /> <br /> t12 = 4 * i<br /> <br /> t9 = a[t8]<br /> <br /> if t3 < v goto B2<br /> <br /> t13 = 4 * n<br /> <br /> a[t6] = t9<br /> <br /> t14 = a[t13]<br /> <br /> a[t8] = x<br /> <br /> a[t12] = t14<br /> <br /> j=j–1<br /> <br /> t15 = 4 * n<br /> <br /> t4 = 4 * j<br /> <br /> a[t15] = x<br /> <br /> B5<br /> <br /> t3 = a[t2]<br /> <br /> B3<br /> <br /> t5 = a[t4]<br /> <br /> if t5 > v goto B3<br /> <br /> B4<br /> <br /> Loại biểu thức con chung<br /> <br /> t1 =4 * n<br /> <br /> goto B2<br /> <br /> t15 = 4 * n<br /> a[t15] = x<br /> <br /> if t5 > v goto B3<br /> <br /> B4<br /> if i >= j goto B6<br /> <br /> if i >= j goto B6<br /> <br /> 5<br /> <br />