Giáo trình môn học Trình biên dịch - Chương 10: Tối ưu mã

CHƯƠNG 10 TỐI ƯU Mà 10.1. Giới thiệu - Tiêu chuẩn chuyển mã tốt - Tổ chức của trình biên dịch tối ưu Hình 10.1. Tổ chức của bộ tối ưu mã front end Bộ tối ưu mã Bộ sinh mã Chuyển đổiPhân tích dòng dữ liệu Phân tích dòng điều khiển Mã trung gian Thí dụ 10.1. Chuyển đổi sang mã trung gian ba địa chỉ cho đoạn chương trình trong ngôn ngữ Pascal for i := n – 1 down to 1 do for j:= 1 to i do if A [j] > A [j + 1] then begin temp := A [j]; A [j] := A [j + 1]; A [j + 1] := temp; end; Giả sử mỗi ô nhớ là 4 byte. Địa chỉ nền của dãy A vậy địa chỉ phần tử thứ j của dãy A là: addr(A[j]) = addr(A) + (j – 1) * 4. (1) i = n - 1 (2) ij i < 1 goto (31) (3) j = 1 (4) if j > i goto (29) (5) t1 = j - 1 (6) t2 = 4 * t1 (7) t3 = A [t2] (8) t4 = j + 1 (9) t5 = t4 - 1 (10) t6 = 4 * t5 (11) t7 = A [t6] (12) ij t3 < t7 goto (27) (13) t8 = j - 1 (14) t9 = 4 * t8 (15) temp = A [t9] (16) t10 = j + 1 (17) t11 = t10 - 1 (18) t12 = 4 * t11 (19) t13 = A [t12] (20) t4 = j - 1 (21) t15 = 4 * t14 (22) A [t5] = t13 (23) t16 = j + 1 (24) t17 = t16 - 1 (25) t18 = 4 * t17 (26) A [t18] = temp (27) j = j + 1 (28) goto (4) (29) i = i - 1 (30) goto 2 * Khối cơ bản Thí dụ 10.2. Đoạn mã trung gian sau được xác định 4 khối cơ bản (1) read L (2) n := 0 (3) k := 0 (4) m := 1 (5) k := k + m (6) c := k > L (7) if (c) goto (11) (8) n := n + 1 (9) m := m + 2 (10) goto (5) (11) write n BB2 BB3 BB4 BB1 10.2. Phân tích dòng dữ liệu Các cấu trúc điều khiển như if, while, for gây ra sự rẽ nhánh của chương trình. Xác định được sự rẽ nhánh sẽ xác định được sự thay đổi trị của biến trong chương trình, từ đó sử dụng các biến này trong quá trình tối ưu hóa. 10.2.1. Mục đích Xác định cấu trúc điều khiển của chương trình là: - mô tả các con đường thực hiện chương trình - xác định các vòng lặp 10.2.2. Đồ thị dòng điều khiển (Control Flow Graphs) Định nghĩa: Đồ thị dòng điều khiển (CFG) của một chương trình là một đồ thị có hướng, được ký hiệu G = (N, E) mà trong đó N là các khối cơ bản, E là tập cạnh thể hiện cho dòng điều khiển giữa các khối cơ bản. Thí dụ 10.3. Đoạn mã trung gian (gồm 4 khối cơ bản) ở thí dụ 10.2 được biểu diễn thành đồ thị dòng dữ liệu. BB1 BB2 BB3 BB4 Hình 10.2. Đồ thị dòng điều khiển 10.2.3. Successor, predcessor của một khối cơ bản Cho một đồ thị dòng điều khiển G = (N, E) và một khối cơ bản b ∈ N, xác định successor và predcessor cho khối cơ bản b như sau: * Successor của b, ký hiệu succ (b) là tập các khối cơ bản n, mà có thể đạt đến từ b trên 1 cạnh succ (b) = {n ∈ N | (b, n) ∈ E} như ở thí dụ 10.3: succ (BB1) = {BB2}; succ (BB2) = {BB3, BB4}, succ (BB3) = {BB2} * Predcessor của b, ký hiệu pred (b) là tập các khối cơ bản m, mà có thể đạt đến b trên 1 cạnh pred (b) = {m ∈ N | (m, b) ∈ E} như ở thí dụ 10.3: pred (BB2) = {BB1 , BB3} pred (BB3) = {BB2}, pred (BB4) = {BB2} ƒ Entry của G: là một nút không có predcessor ƒ Exit của G: là một nút không có successor ƒ nút rẽ (branch node) trong G là nút có nhiều hơn một successor ƒ nút hợp (join node) trong G là nút có nhiều hơn một predcessor Đồ thị dòng điều khiển ở thí dụ 10.3 được thêm 2 nút Entry, Exit. Entry Exit BB1 BB2 BB3 BB4 Hình 10.3. Nút Entry và Exit trong G Thí dụ minh họa các nút rẽ nhánh và hợp. BB1 BB5 BB6 BB7 BB8 BB9 BB10 BB2 BB3 BB4 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15) i := 1 if(I>n) goto (15) t := 0 j := 1 if(j>n) goto (13) tmp := te + ts if(tmp < 0) goto (10) t1 := t1 + ts goto (11) t1 := 4*j j := j+1 goto (5) i := I+1 goto (2) t1 := 0 BB1 BB5 BB6 BB7 BB8 BB9 BB10 BB2 BB3 BB4 BB1 BB5 BB6 BB7 BB8 BB9 BB10 BB2 BB3 BB4 Hình 10.4. Các nút rẽ nhánh và hợpjoin node branch node 10.2.4. Chi phối (dominater) ƒ Định nghĩa dominater: nút n của G chi phối nút n’ , ký hiệu n dom n’ (hay n Ỉ n’ ), nếu mọi con đường từ nút Entry của G đến n’ đều phải đi qua n. Với định nghĩa này thì mọi nút n chi phối chính nó. Nút là điểm vào vòng lặp sẽ chi phối các nút trong vòng lặp. BB1Ỉ BB1 ; BB1Ỉ BB2 ; BB1 Ỉ BB3 ; BB1Ỉ BB4 BB2Ỉ BB2 ; BB2Ỉ BB3 ; BB2Ỉ BB4 BB3Ỉ BB3 BB4Ỉ BB4 Entry Exit BB1 BB2 BB3 BB4 ƒ properdominate N là proper dominate n’ , ký hiệu n Ỉ p n’ , nếu n Ỉ n’ và n ≠ n’ như thí dụ ở trên thì BB1Ỉ p BB2 ; BB1Ỉ p BB3 ; BB1Ỉ p BB4 ; BB2Ỉ p BB3 ; BB2Ỉ p BB4 ƒ direct dominate Nút n được gọi là direct dominate n’ , ký hiệu n Ỉ d n’ , nếu n Ỉ p n’ và không tồn tại n” ∈ N mà n Ỉ p n”. BB1Ỉ d BB2 ; BB2Ỉ d BB3 ; BB2Ỉ d BB4 ƒ cây dominate (dominate tree); ký hiệu viết tắt DT, là cây mà nút gốc là Entry; nút thuộc G và cạnh là quan hệ direct dominator. Ở thí dụ trên DT có dạng: Entry BB1 BB2 BB3 BB4 Hình 10.4. Cây dominate Giải thuật 2.2: tìm các dominator. Nhập: đồ thị dòng điều khiển G. Xuất: tập dominator của mỗi nút thuộc G. Giải thuật: DOM (Entry) = Entry DOM (ν) = N ∀ ν ∈ N - {Entry, Exit} change = true while (change) {change = false for each ν ∈ N - {Entry, Exit} { old DOM = DOM (ν)’ DOM (ν) = {ν} ∪ ∩ OM (p) pepred (ν) if (DOM (ν) = old DOM) change = true } } 10.2.5. Direct dominator Direct dominator của một nút n. Giải thuật tìm direct dominator của một nút: - Khởi động tập proper dominator của nút n - Loại bỏ những nút mà nó là proper dominator những nút khác trong tập Giải thuật 10.3. Tìm direct dominator Nhập: đồ thị dòng G. Xuất: direct dominator của mỗi nút của G. Giải thuật: for với mỗi nút n ∈ N - {Entry} do DOMd (n) = DOM (n) - {n} for với mỗi nút n ∈ N - {Entry} do for với mỗi nút s ∈ DOMd (n) - {s} do if t ∈ DOMd (s) then DOMd (n) = DOMd (n) - {t}; Ở thí dụ ở hình 10.1, ta có: DOMd (1) = {Entry}; DOMd (2) = {1}; DOMd (3) = {2}; DOMd (4) = {2} 10.2.6. Post – dominator Định nghĩa: Cho đồ thị dòng điều khiển G = (N, E) và n, n’ ∈ N. - Nút n được gọi là post – dominator của nút n’, ký hiệu n Ỉ n’ nếu mọi con đường từ n đến nút Exit chứa n’. Ở thí dụ hình 10.3, ta có các post – dominator: 1 ← 1; 1 ← 2; 1 ← 3; 1 ← 4; 2 ← 2; 2 ← 3; 2 ← 4; 3 ← 3; 4 ← 4 - Nút n được gọi là direct post – dominator của nút n’, ký hiệu n ← n’, nếu n ← pn’ và không tồn tại n” ∈N mà n ← pn”← pn’. - Nút n được gọi là proper post – dominator của nút n’, ký hiệu là n ← pn’, nếu n ← n’ và n ≠ n’. Thí dụ về post – dominator trong G là dominator trong G-1 Entry Exit BB1 BB2 BB3 BB4 G1 G-1 Entry Exit BB1 BB2 BB3 BB4 10.2.7. Vòng lặp Các yếu tố xác định vòng lặp tự nhiên: - Một vòng lặp phải có 1 điểm vào đơn, gọi là header. - Điểm vào header dominate tất cả các nút còn lại trong vòng lặp. - Phải có ít nhất một cách lặp, nghĩa là phải có ít nhất một cạnh quay về header. Giải thuật 10.3. Tìm vòng lặp Nhập: đồ thị dòng G và một cạnh về t Ỉ h. Xuất: vòng lặp bao gồm tất cả các nút trong vòng lặp tự nhiên t Ỉ h. Phương pháp: - Tìm dominator của mỗi nút trong CFG. - Xác định cạnh vẽ. - Tìm tất cả những nút liên quan đến cạnh vẽ. - Để tìm cạnh vẽ: thực hiện duyệt cây CFG theo chiều sâu trước. Một cạnh lùi e = (t, h) ∈ E là cạnh lùi nếu h Ỉ t. Một cạnh lùi luôn là cạnh vẽ trong vòng lặp bằng cách sử dụng điều khiển có cấu trúc. Giải thuật: stack s = empty set loop = {h} insert – on – stack (t); /* stack s* while S is not empty do beg m = pop (s); for each pred (m) do insert – on – stack (p); end insert – on – stack (a) begin if (a ∈ loop) then begin loop = loop ∪ {a} push – on – stack (a); end Thí dụ về tìm vòng lặp Cho grap như sau: Entry BB3 BB4 BB7 BB8 BB1 BB2 BB5 BB9 BB6 BB10 Exit Đầu tiên xác định cạnh về h Ỉ t. Loop = {BB3 , BB8}, stack = {BB8} Loop = {BB3 , BB8}, stack = {} Loop = {BB3 , BB8 , BB7}, stack = {BB7} Loop = {BB3 , BB8 , BB7}, stack = {} Loop = {BB3 , BB8 , BB7 , BB5}, stack = {BB5} Loop = {BB3 , BB8 , BB7 , BB5 , BB6}, stack = {BB5 , BB6} Loop = {BB3 , BB8 , BB7 , BB5 , BB6}, stack = {BB5} Loop = {BB3 , BB8 , BB7 , BB5 , BB6 , BB4}, stack = {BB5 , BB4} Loop = {BB3 , BB8 , BB7 , BB5 , BB6 , BB4}, stack = {BB5} Loop = {BB3 , BB8 , BB7 , BB5 , BB6 , BB4}, stack = {} Vòng lặp tìm được là {BB3 , BB4 , BB5 , BB6 , BB7 , BB8}, BB3 là header, BB8 là node kết thúc. 10.3. Phân tích dòng dữ liệu (Data Flow Analyst) – DFA 10.3.1. Mục đích của phân tích dòng dữ liệu - Xác định dữ liệu được dùng trong chương trình. - Sử dụng dữ liệu để trình biên dịch quyết định tối ưu mã. - Trong một khối cơ bản: xác định tính hiệu quả trong câu lệnh, từ đầu đến cuối khối cơ bản. 10.3.2. Điểm và đường Điểm là vị trí giữa hai phát biểu liền nhau. Tồn tại điểm trước và sau phát biểu. Thí dụ đoạn chương trình: p0 • d1 i := m - 1 p1 • d2 j := n p2 • d3 a := u1 p3 • Ở đây có 4 điểm p0 trước d1 , p1 trước d2 , trước d3 , p3 sau d3 Đường: từ p1 đến pn là con đường đi từ p1 đến điểm pn trong chương trình. 10.3.3. Đạt đến sự định nghĩa (Reaching definition) Định nghĩa của một biến x là tác vụ gán trị cho biến x. Định nghĩa d cho một biến x được gọi là đạt đến một điểm p trong chương trình nếu tồn tại một con đường từ điểm ngay sau d đến p mà x không bị thay đổi trị bởi một định nghĩa của x dọc theo con đường này. 10.3.3.1. Tập Gen Gen (b) là tập các định nghĩa ở trong b và đạt đến điểm kết thúc của b. 10.3.3.2. Tập Kill Kill (b) là tập định nghĩa ở một khối cơ bản khác b nhưng bị thay đổi trong b (bởi một tác vụ trong b), ν là biến được định nghĩa trong b, tập kill chứa tất cả các định nghĩa của v trong các khối cơ bản khác. 10.3.3.3. Sự cân bằng dòng dữ liệu RDin (b): tập các định nghĩa mà đạt đến sự bắt đầu của b RDout (b): tập các định nghĩa mà đạt đến sự kết thúc của b. Công thức xác định: RDin (b) = ∪ RDout (i) i ∈ pred (b) RDout (b) = Gen (b) ∪ [RDin (b) – Kill (b)] Giải thuật: xác định việc đạt đến sự định nghĩa. Nhập: đồ thị dòng G với tập Gen (b) và kill (b) đã được tính toán trước cho mỗi khối cơ bản b. Xuất: RDin (b) và Rdout (b) cho mỗi khối cơ bản b Giải thuật: RDout (Entry) = ∅ RDout (b) = ∅ ∀ b ∈ N - {Entry, Exit} /* Gen (b) thì tốt hơn */ change = true while (change) { change = false for each b ∈ N - {Entry, Exit} { oldout = RDout (b) RDin (b) = ∪ RDout (i) i ∈ pred (b) RDout (b) = Gen (b) ∪ [RDin (b) – kill (b)] if (RDout (b) ≠ oldout) change = true } } RDin (Exit) = ∪ RDout (i) i ∈ pred (Exit) Thí dụ: d1 : i := m - 1 d2 : j := n d3 : a := u1 d4 : i := i + 1 d5 : j := j - 1 d6 : a := u2 d7 : a := u3 i := m -1 j := n a := u1 Entry a := u3 Exit BB1 {d4,d5, d3,d6} {d4,d5,d7} BB3 {d1,d2,d3,d4, d5,d6} {d4,d5,d3,d6} Φ BB2 BB4 Φ i := j + 1 j := j - 1 e1? {d1,d2,d3} a := u2 {d4,d5, d3,d6} BB Gen (BB) Kill(BB) 1 2 3 4 {d1,d2,d3} {d4,d5} {d6} {d7} {d4,d5,d6,d7} {d1,d2} {d3,d7} {d3,d6} RDin(b) = ∪ RDout(i) i ∈ pred(b) RDout(b) = Gen(b) ∪[RDin(b) - kill(b)] {d4,d5,d6} 10.3.4. Biến sống Biến ν được gọi là sống tại điểm p trong chương trình nếu giá trị hiện tại của ν được dùng trước khi ν được gán giá trị mới hoặc trước khi chương trình kết thúc, ngược lại gọi là biến chết. - Ứng dụng biến sống là xác định xem có cần lưu giữ trị của nó khi ra khỏi khối cơ bản, trong thanh ghi. - Cần xác định biến sống ở điểm vào và ra của mỗi khối cơ bản. 10.3.4.1. Tập Use Use (b) là tập các biến được sử dụng trước khi (hoặc có thể) được định nghĩa trong b. 10.3.4.2. Tập Def Def (b) là tập các biến được định nghĩa trong b. 10.3.4.3. Sự cân bằng dòng dữ liệu LVin (b): tập các biến sống tại điểm vào của b LVout (b): tập các biến sống tại điểm ra của b Công thức: LVout (b) = ∪ LVin (i) i ∈ succ (b) LVin (b) = Use (b) ∪ [LVout (b) – Def (b)] Giải thuật 3.2. Giải thuật tìm biến sống Nhập: đồ thị dòng G với Def (b) và Use (b) được xác định trước. Xuất: LVout (b) là tập biến sống tại điểm ra của khối cơ bản b. Giải thuật: LVin (Entry) = ∅ Lvin (b) = ∅ ∀ b ∈ N - {Entry, Exit} change = true while change {change = false} for each b ∈ N - {Entry, Exit} { oldin = LVin (b) LVout (b) = ∪ LVin (i) i ∈ succ (b) LVin (b) = Use (b) ∪ [LVout (b) - Def (b)] if (LVin (b) ≠ oldin) change = true } } Thí dụ: cho dòng điều khiển như sau, tìm tập các biến sống khi ra khỏi các khối cơ bản. a := 2 b := 3 d := c e := a g := c + 1 a < d ? print (b,d,e,g) Entry b := b + 1 d := 2 * d b > 10 d := d + 1 f := a + b g := e + g Exit {c} BB1 {a,b,d,e,g} {b,d,e,g}{b,d,e,g} {b,d,e,g} BB2 BB3 {a,b,d,e,g}{b,d,e,g} ΦΦ BB4 BB Use (BB) Def (BB) 1 2 3 4 {c} {b,d} {a,b,d,e,g} {b,d,e,g} {a,b,d,e,g} {b,d} {d,f,g} Φ LVout(b) = ∪ LVin(i) i ∈ succ(b) LVin(b) = Use(b) ∪[LVout(b) - Def(b)] 10.3.5. Biểu thức có sẵn (Avaible expression) ƒMột biểu thức x op y được gọi biểu thức có sẵn tại điểm p nếu mọi con đường từ nút khởi đầu đến p hoặc sau lần tính toán trước khi đạt đến p không có tác vụ gán cho x và y. ƒ Ứng dụng của biểu thức có sẵn là để loại bỏ biểu thức con dùng chung. ƒ Ta phải tìm tất cả biểu thức có sẵn tại điểm vào và ra của mỗi khối cơ bản. 10.3.5.1. Tập Eval Eval (b) là tập các biểu thức có sẵn được thực hiện trong b mà vẫn có sẵn tại điểm ra của b. 10.3.5.2. Tập Kill Kill (b) là tập các biểu thức bị thay đổi trong b. 10.3.5.3. Sự cân bằng dòng dữ liệu AEin (b): tập các biểu thức có sẵn tại điểm bắt đầu của b. AEout (b); tập biểu thức có sẵn chạm đến điểm kết thúc của b. Công thức: AEin (b) = ∩ AEout (i) i ∈ pred (b) AEout (b) = Eval (b) ∪ [AEin (b) – Kill (b)] Giải thuật: tìm tập các biểu thức có sẵn tại điểm vào và ra của mỗi khối cơ bản. Nhập: đồ thị dòng G với Eval (b) và Kill (b) được tính toán trước cho khối cơ bản b. Xuất: AEin (b) cho khối cơ bản b. Giải thuật: ∪: tập các biểu thức trong đồ thị dòng điều khiển AEout (Entry) = ∅ AEout (b) = Eval (b) ∪ [U – Kill (b)] ∀ b ∈ N - {Entry, Exit} change = true while (change) { change = false for each b ∈ N - {Entry, Exit} { oldout = AEout (b) AEin (b) = ∩ AEout (i) i ∈ pred (b) 10.4. Loại bỏ dư thừa Quá trình loại bỏ dư thừa bao gồm loại bỏ những biểu thức con chung, lan truyền những bản copy, di chuyển mã không đổi trong vòng lặp ra ngoài vòng lặp. 10.4.1. Loại bỏ biểu thức con chung Giải thuật: loại bỏ biểu thức con chung Nhập: mã ba địa chỉ của đồ thị dòng điều khiển với các AEin và AEout cho từng khối cơ bản. Xuất: đoạn mã ba địa chỉ đã loại bỏ biểu thức con chung. Giải thuật: for mỗi khối b ∈ N for mỗi lệnh ∈ b có dạng y = x op y mà x op y là có sẵn tại điểm vào của b { 1. Xác định nếu x op y có sẵn tại mỗi câu lệnh 2. Xác định việc tính toán x op y mà đạt đến z 3. Tạo một biến mới t 4. Thay thế sự định nghĩa w = x op y tìm thấy ở bước 2 bằng t = x op y; w = t 5. Thay z = x op y bằng z = t } } Thí dụ về loại bỏ biểu thức con dùng chung c := a+b d := a*c e := d*d i := 1 Entry Exit BB1 {a+b, d*d} BB3 {a+b, d*d} {a+b, d*d} BB2 BB4 f := a+b c := c*2 c > d ? g := a*c {a+b, d*d} d := c g := d*d i := i+1 i > 10 ? BB5 t1 := a+b c := t1 d := a*c e := d*d i := 1 Entry Exit BB1 BB3 BB2 BB4 f := t1 c := c*2 c > d ? g := a*c d := cg := d*d i := i+1 i > 10 ? BB5 10.4.2. Lan truyền bản copy 10.4.2.1. Định nghĩa sử dụng (use definition) Tập các định nghĩa đạt đến việc sử dụng của a như là một biến được gọi là dây xích sử dụng định nghĩa (ud - chain) cho biến đó. Thí dụ về ud – chain Entry Exit z = 1 x = 1 z > y x = 2 y = x+1 z = x-3 10.4.2.2. Dây xích định nghĩa sử dụng Tập tất cả các lần sử dụng mà đạt đến bởi một định nghĩa được gọi là dây xích định nghĩa sử dụng (du – chain). Thí dụ về du – chain và ud – chain Entry Exit z = 1 x = 1 z > y x = 2 y = x+1 z = x-3 10.4.2.3. Biểu thức copy có sẵn (Available Copy Expression) ƒ Tập copy Tập những câu lệnh copy u := v trong b mà u và v không được gán sau đó trong b, nghĩa là câu lệnh có sẵn tại điểm kết thúc của b. ƒ Tập kill Tập các câu lệnh copy bị thay đổi trong b, nghĩa là tập câu lệnh copy trong khối cơ bản khác mà có toán hạng của nó được gán cho b. ƒ Sự cân bằng dòng dữ liệu copyin: là tập lệnh copy có sẵn tại điểm vào b copyout: là tập lệnh copy có sẵn tại điểm kết thúc b công thức: copyin (b) = ∩ copyout (i) i ∈ pred (b) copyout (b) = copy (b) ∪ [copyin (b) – kill (b)] Giải thuật: tìm bản copy có sẵn Nhập: đồ thị dòng điều khiển G với kill (b) và copy (b) được tính sẵn cho mỗi khối cơ bản b. Xuất: copyin (b) cho mỗi khối cơ bản. Giải thuật: U : Tập tất cả các copy trong đồ thị dòng điều khiển copyout (Entry) = Φ copyout (b) = copy (b) ∪ [U - kill (b)] ∀ b ∈ N - {Entry, Exit} changed = true while (changed) { changed = false for each b ∈ N - {Entry, Exit} { oldout = copyout (b) copyin (b) = ∩ copyout (i) i ∈ pred (b) copyout (b) = copy (b) ∪ [copyin (b) – kill (b)] if (copyout (b) ≠ oldout) changed = true } } Aein (Exit) = ∩ Aeout (i) i ∈ pred (Exit) 10.4.2.4. Lan truyền bản copy • Câu lệnh copy là câu lệnh có dạng x = y. • Sự lan truyền bản copy là thay thế x bằng y mà không làm thay đổi trị của x hoặc y. Giải thuật: lan truyền bản copy Nhập: đồ thị dòng điều khiển G với du – chain. Xuất: đồ thị dòng điều khiển có sử dụng lan truyền bản copy. Giải thuật: for mỗi bản copy s: x := y thực hiện các bước sau: 1. Xác định tất cả các nơi mà sự định nghĩa của x được sử dụng. 2. for mỗi lần sử dụng u: a. s phải có một sự định nghĩa của x chạm đạt đến u và b. mọi con đường từ s đến u, không có tác vụ gán đến y. Thí dụ về sự lan truyền bản copy c := a+b d := c e := d*d Entry Exit BB1 {d := c} BB3 {d := c} {d:= c,g:= e} BB4 BB2 f := a+c g := e a := g+d a < c ? h := g+1 e := f+2 {d:= c,g:= e} f := d-g f > a ? b := g+a h < f ? BB6 c := 2 c := a+b d := c e := c*c Entry Exit BB1 BB2 BB3 BB4 f := a+c g := e a := e+c a < c ? h := e+1 e := f+2 f := c-e f > a ? b := g+a h < f ?BB5 BB5 BB6 c := 2 {d:= c,g:= e} 10.4.3. Di chuyển mã không đổi của vòng lặp (loop – invariant code motion) • Một sự tính toán trong vòng lặp được gọi là loop – invariant nếu sự tính toán của nó luôn luôn tạo ra cùng một giá trị. • Di chuyển code không đổi là di chuyển các loop – invariant ra bên ngoài vòng lặp. 10.4.3.1. Loop – Invariant Một tác vụ trong vòng lặp là loop – invariant nếu mỗi toán hạng trong tác vụ là: - hằng số hoặc - tất cả các định nghĩa của toán hạng đều ở bên ngoài vòng lặp hoặc - chỉ duy nhất có một định nghĩa trong vòng lặp cho toán hạng mà sự định nghĩa là loop – invariant. 10.4.3.2. Thực hiện di chuyển code Sự di chuyển code phải thỏa mãn 3 điều kiện ví dụ cho phát biểu s : x = y + z. 1. Khối cơ bản chứa s phải dominate tất cả các lối ra của vòng lặp. 2. Không có phát biểu nào khác gán cho x. 3. Tất cả các lần sử dụng x chỉ đạt đến sự định nghĩa x trong s. Thí dụ (điều kiện 1) if u <v goto BB3 i :=1 BB1 BB3 BB2 BB4 v := v-1 if v < =20 goto BB5 i := 2 u := u+1 j := i BB5 Thí dụ (điều kiện 2) if u <v goto BB3 j := i BB1 BB3 BB2 BB4 k := I v := v-1 if v < =20 goto BB5 i := 2 u := u+1 j :=1 BB5 i :=3 if u <v goto BB3 i :=1 BB1 BB3 BB2 BB4 v := v-1 if v < =20 goto BB5 i := 2 u := u+1 i :=1 BB5 Thí dụ (điều kiện 3) 10.5. Tối ưu vòng lặp Trong phần này chúng ta sẽ trình bày giải thuật tối ưu vòng lặp là strength reduction. Mục đích của giải thuật này là thay thế các câu lệnh đắt tiền bằng câu lệnh rẻ tiền hơn. 10.5.1. Biến thay đổi (Induction variable) Biến thay đổi trong vòng lặp L là x nếu mỗi lần thay đổi nó tăng hoặc giảm một hằng số nhất định. 10.5.2. Biến thay đổi cơ bản (Basic Induction Variable – BIV) Biến v được gọi là BIV trong L nếu nó có dạng v := v ± c với c là hằng số 10.5.3. Biến thay đổi dẫn xuất (Derived Induction Variable – DIV) Biến j được gọi là biến thay đổi dẫn xuất nếu nó có một trong các dạng sau xuất hiện trong vòng lặp: j := a * i hoặc j := i * a j := b + i hoặc j := a * i j := b – i hoặc j := i – a j := i / a trong đó i là biến thay đổi cơ bản (BIV) Giải thuật 6.1. Tìm biến thay đổi trong vòng lặp L. Nhập: vòng lặp L. Xuất: tất cả các BIV và DIV trong L. Giải thuật: 1. Tìm tất cả BIV trong L. 2. Tìm các DIV. 3. Lặp lại bước (2) cho đến khi nào không tìm thấy DIV khác. 10.5.4. Giải thuật strength Reduction Nhập: vòng lặp L và tập họ các biến thay đổi. Xuất: đoạn mã đã thực hiện thay thế các câu lệnh phức tạp bằng những câu lệnh ít phức tạp hơn từ vòng lặp L. Giải thuật: for mỗi biến BIV i { for mỗi biến j trong họ i Ỉ (I, a, b) { tạo ra một biến mới sj khởi động sj := a * i + b và đặt vào preheader của L thay thế câu lệnh gán j bằng j := sj sau mỗi phát biểu i := i ± c trong L { chèn thêm sj := sj ± c * a } } thêm sj vào họ của i