Bài giảng Trình biên dịch

Nội dung text: Bài giảng Trình biên dịch

1. 4 indirect *R contents (R) 0 register 5 inderect *c (R) contents (c + contents (R)) 1 indexed 6 literal # C hằng C 1 Giá chỉ thị (instruction cost) Giá chỉ thị được tính bằng một công giá kết hợp trong bảng mode địa chỉ nguồn và đích ở trên. Qua các thí dụ trên chúng ta thấy muốn sinh mã tốt thì làm sao phải hạ giá của các chỉ thị. Sinh mã để quản lý các bản ghi hoạt động trong thời gian thực thi. Các mã quản lý này phải đáp ứng được hai kỹ thuật quản lý bộ nhớ tĩnh và cấp phát bộ nhớ theo cơ chế stack. Việc cấp phát và giải tỏa vị trí nhớ cho bản ghi hoạt động là một phần trong chuỗi hành vi gọivà trở về của chương trình con.
2. Cấp phát tĩnh Phát biểu call được hiện thực bằng hai mã đối tượng MOV và GOTO. MOV # here + 20, callee.static - area GOTO callee. code – rea Thí dụ 9.1. Mô phỏng 9.1. Mã đối tượng cho chương trình con c và p /* mã cho c */ 100: action 120: MOV 140, 364 /* cất địa chỉ khứ hồi 140 */ 132: GOTO 200 /* gọi p */ 140: action2 160: halt /* mã cho p */
3. ADD # caller.recordsize, SP MOV # here + 16, * SP /* lưu địa chỉ khứ hồi */ GOTO callee.code-area Chuỗi trở về gồm hai chỉ thị: GOTO *0 (SP) /* trở về chương trình gọi */ SUB # callee.recordsize, SP Chỉ thị GOTO *0 (SP) Thí dụ 9.2 /* mã cho s */ /* mã cho q */ action1 action4 callq callp action2 action5 halt callq /* mã cho p */ action6 action3 callq return return Hình 9.3. Mã trung gian của chương trình ở mô phỏng 9.1
4. 344: SUB # qsize, SP 352: action5 372: ADD # qsize, SP 380: MOV 396, * SP /* cất địa chỉ khứ hồi */ 388: GOTO 300 /* gọi q */ 396: SUB # qsize, SP 304: action6 424: ADD # qsize, SP 432: MOV 440, * SP /* cất địa chỉ khứ hồi */ 440: GOTO 300 /* gọi q */ 448: SUB # qsize, SP 456: GOTO *0 (SP) /* trở về chương trình gọi */ 600: /* địa chỉ bắt đầu của stack trung tâm */
5. 9.3. Khối cơ bản và lưu đồ Khối cơ bản (basic block) t1 := a * a; t2 := a * b; t3 := 2 * t2 t4 := t1 + t2 t5 := b * b; t6 := t4 + t5 Giải thuật 9.1. Phân chia các khối cơ bản Nhập: các phát biểu ba địa chỉ Xuất: danh sách các khối cơ bản với từng chuỗi các phát biểu ba địa chỉ cho từng khối. Phương pháp: 1. Xác định tập các phát biểu dẫn đầu của các khối chúng ta dùng các quy tắc sau đây: i) Phát biểu đầu tiên là phát biểu dẫn đầu (leader) (từ đây ta sẽ dùng từ leader thay cho cụm từ tiếng Việt phát biểu dẫn đầu).
6. Mô phỏng 9.4. Mã trung gian để tính tích vectơ vô hướng (1) prod :=0 (2) i := 1 (3) t1 := 4 * i (4) t2 := a[t1] /* tính a[i] (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) Sự luân chuyển trên các khối Lưu chuyển bảo tồn cấu trúc
7. Lưu đồ (flow graph) Đồ thị trực tiếp được gọi là lưu đồ. Các nút của lưu đồ là khối cơ bản. Một nút được gọi là khối điểm, nếu nó có chứa phát biểu đầu tiên của chương trình. prod := 0 i := 1 B1 t1 := 4 * I t2 := a [t1] t3 := 4 * i t := b [t ] 4 3 B2 t5 := t2 * t4 t6 := prod + t5 prod := t6 Hình 9.4. Lưu đồ của t7 := i + 1 chương trình I := t7 if I < = 20 goto B2
8. Hàm getreg 1. Nếu y đang ở trong thanh ghi và y sẽ không được dùng nữa sau phát biểu x := y op z. 2. Ngược lại. 3. Nếu không có thanh ghi rỗng. 4. Nếu X sẽ không được dùng tiếp và cũng không thể tìm được một thanh ghi như đã nói ở bước 3. Thí dụ 9.3. Ta có phát biểu gán d := (a – b) + (a – c) + (a – c) Chuyển thành mã trung gian t := a – b; u := a – c; v := t + u; d := v + u
9. Sinh mã cho loại phát biểu khác Bảng 9.2. Chuỗi mã đối tượng cho phát biểu xác định chỉ số và gán. (1) (2) (3) Phát i trong thanh ghi R i trong bộ nhớ M i trên stack biểu 1 1 mã giá mã giá mã giá a := b[1] MOV b (Ri), R 2 MOV Mi , R 4 MOV Si (A), R 4 MOV b(R), R MOV b(R), R a[1] := b MOV b, a (R1) 3 MOV Mi , R 5 MOV Si (A), R 5 MOV b, a(R) MOV b, a(R)
10. Sinh mã cho phát biểu điều kiện if x y thì mã điều kiện sẽ được xác lập dương. Chỉ thị nhảy có điều kiện được thực thi nếu điều kiện được xác lập , > =, , < = chúng ta dùng chỉ thị nhảy có điều kiện CJ < = z. Như vậy phát biểu điều kiện if x < y goto z được dịch sang mã máy như sau: CMP x, y; CJ < z 9.5. Dag biểu diễn khối cơ bản Dag là cấu trúc dữ liệu rất thích hợp để hiện thực việc chuyển đổi các khối cơ bản. 1. Các lá được đặt tên bằng các danh biểu duy nhất, hoặc là tên biến hoặc hằng số. Hầu hết các lá là r-value. 2. Các nút trung gian được đặt tên bằng ký hiệu phép toán. 3. Các nút cũng có thể là chuỗi các danh biểu cho trước. Lưu ý phải phân biệt sự khác nhau giữa lưu đồ và dag.
11. t , prod 6 (1) + t 5 ⇐ ∗ t4 prod 0 [ ] 20 [ ] t , t + t , ∗ 1 3 7 i a 1 b i0 4 Hình 9.5. Dag cho khối B2 ở mô phỏng 9.5 Xây dựng dag Giải thuật 9.2. Xây dựng dag. Nhập: khối cơ bản Xuất: dag cho khối cơ bản, chứa các thông tin sau: 1. Tên cho từng nút. 2. Mỗi nút đều có danh sách các danh biểu gắn vào nó.
12. t5 t2 * t4 a) [ ] [ ] t , t a ∗ 1 3 b i 4 0 t6 + t5 ∗ t4 prod t2 0 [ ] [ ] b) t , t ∗ 1 3 a b i0 4
13. t6, prod + t5 t ∗ (1) prod0 2 t4 [ ] ⇐ [ ] t , i t1, t3 7 a ∗ + 20 b 4 i0 1 e) Hình 9.7. Các bước xây dựng dag của khối B2 ở thí dụ 9.5.
14. Nhưng khối (9.1) và (9.2) sẽ tính trị z khác nhau nếu j = I và y ≠ a[i]. Đối với con trỏ cũng xảy ra vấn đề khi ta có phát biểu gán * p := w. Nếu ta không biết p sẽ chỉ đến đối tượng nào, thì phải loại tất cả các nút có dạng trên. Việc gọi chương trình con sẽ giết tất cả các nút bởi vì ta chưa biết gì về chương trình bị gọi, nên ta buộc phải giả sử rằng bất cứ biến nào cũng có thể bị thay đổi trị do hiệu ứng lề. 9.6. Tạo mã đối tượng từ dag Sắp xếp lại thứ tự t1 := a + c t2 := c + d t3 := e – t2 t4 := t1 –t3 Ta có thể sắp xếp lại chuỗi mã trung gian sao cho việc tính toán t1 chỉ xảy ra ngay trước t4. t2 := c + d t1 := a + b t3 := e – t2 t4 := t1 – t3
15. Heuristics dùng để sắp xếp dag Mô phỏng 9.8. Giải thuật sắp xếp các nút của dag (1) While nếu còn các nút trung gian chưa được liệt kê ra do begin (2) Chọn nút chưa liệt kê n; tất cả các nút cha mẹ của nó đã liệt kê (3) liệt kê n; (4) While con m ở tận cùng bên trái của n, có các cha mẹ đã liệt kê và nó không phải là nút lá do begin (5) liệt kê m; (6) n := m; end; end
16. t8 := d + e t6 := a + b t5 := t6 -c t4 := t5 * t8 t3 := t4 -e t2 := t6 + t4 t1:= t2 * t3 Sắp xếp tối ưu cho cây Giải thuật có hai phần: phần đầu đánh tên cho các nút của cây, phần thứ hai của giải thuật miêu tả lộ trình trên cây. Mã đối tượng sẽ sinh ra trong quá trình thực hiện lộ trình trên cây. ƒ Giải thuật xác định nhãn của nút trên cây
17. Thí dụ 9.8. Chúng ta xét cây ở (H.9.8) 2 t4 2 t1 1 t3 a 1 1 b e t2 0 1 c d 1 0 Hình 9.10. Cây được xác định tên • Sinh mã đối tượng từ cây có tên
18. /* trường hợp thứ hai */ else if 1 ≤ label (n1) < label (n2) and label (n1) < r then begin swap (rstack); gencode (n2); R := pop (rstack); /* n2 đã được tính, nằm trong R */ gencode (n1); print op || R || ‘,’ || top (rstack); push (rstack, R); swap (rstack) end /* trường hợp thứ ba */ else if 1 ≤ label (n2) ≤ label (n1) and label (n2) < r then begin gencode (n1); R := pop (rstack); /* n1 đã được tính, nằm trong thanh ghi R*/
19. Mô phỏng 9.11. Chuỗi các lệnh gọi thủ tục gencode và các lệnh print của các trường hợp gencode (t4)[R1R0] /* trường hợp 2 */ gencode (t3)[R0R1] /* trường hợp 3 */ gencode (e) [R0R1] /* trường hợp 0 */ print MOV e, R1 gencode (t2)[R0) /* trường hợp 1 */ gencode (c) [R0] /* trường hợp 0 */ print MOV c, R0 print ADD d, R0 print SUB R0 , R1 gencode (t1)[R0] /* trường hợp 1 */ gencode (a) [R0] /* trường hợp 0 */ print MOV a, R0 print ADD b, R0 print SUB R1 , R0
20. + l + max (2, l) l 0 1 T 1 b) T1 a) + + + + ti4 T1 + + + ti3 T 4 d) Ti1 Ti3 T T 2 3 Hình 9.11. Chuyển đổi cây bằng phép hoán vị, c) kết hợp
21. CHƯƠNG 10 TỐI ƯU MÃ 10.1. Giới thiệu - Tiêu chuẩn chuyển mã tốt - Tổchứccủatrìnhbiêndịchtốiưu front end Bộ tối ưu mã Bộ sinh mã Phân tích dòng Phân tích Chuyển đổi điều khiển dòng dữ liệu Hình 10.1. Tổ chức của bộ tối ưu mã
22. (1) i = n - 1 (16) t10 = j + 1 (2) ij i i goto (29) (19) t13 = A [t12] (5) t1 = j - 1 (20) t4 = j - 1 (6) t2 = 4 * t1 (21) t15 = 4 * t14 (7) t3 = A [t2] (22) A [t5] = t13 (8) t4 = j + 1 (23) t16 = j + 1 (9) t5 = t4 -1 (24) t17 = t16 -1 (10) t6 = 4 * t5 (25) t18 = 4 * t17 (11) t7 = A [t6] (26) A [t18] = temp (12) ij t3 < t7 goto (27) (27) j = j + 1 (13) t8 = j - 1 (28) goto (4) (14) t9 = 4 * t8 (29) i = i - 1 (15) temp = A [t9] (30) goto 2
23. 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.
24. * 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
25. Thí dụ minh họa các nút rẽ nhánh và hợp. BB1 (1) i := 1 (2) if(I>n) goto (15) BB2 (3) t := 0 (4) j := 1 BB3 (5) if(j>n) goto (13) (6) tmp := te + ts BB4 (7) if(tmp < 0) goto (10) (8) t1 := t1 + ts BB5 (9) goto (11) BB6 BB7 (10) t1 := 4*j BB8 (11) j := j+1 (12) goto (5) BB9 (13) i := I+1 (14) goto (2) BB10 (15) t1 := 0
26. 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 ; Entry BB1 Ỉ BB2 ; BB1 Ỉ BB3 ; BB1 BB1 Ỉ BB4 BB2 Ỉ BB2 ; BB2 BB2 Ỉ BB3 ; BB2 Ỉ BB4 BB3 BB4 BB3 Ỉ BB3 BB Ỉ BB 4 4 Exit
27. Entry BB1 BB2 BB3 BB4 Hình 10.4. Cây dominate
28. 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.
29. 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’.
30. 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ẽ.
31. Thí dụ về tìm vòng lặp Entry Chograpnhưsau: BB1 BB2 BB3 BB4 BB5 BB6 BB7 BB8 BB9 BB10 Exit
32. 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
33. 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)]
34. 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)
35. 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.
36. 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 } }
37. 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.
38. 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)
39. 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 } }
40. Entry t1 := a+b c := t1 d := a*c BB1 e := d*d i := 1 f := t1 c := c*2 BB2 c > d ? d := c g := a*c BB BB 3 4 g := d*d i := i+1 BB i > 10 ? 5 Exit
41. 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 z = 1 x = 1 x = 2 z > y y = x+1 z = x-3 Exit
42. 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)
43. 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.
44. 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.
45. Thí dụ (điều kiện 2) Thí dụ (điều kiện 3) i :=1 BB1 i :=1 BB1 i :=3 BB2 if u <v goto BB3 BB2 if u <v goto BB i := 2 3 i := 2 BB BB u := u+1 3 u := u+1 3 v := v-1 k := I BB4 if v < =20 goto BB5 v := v-1 BB4 if v < =20 goto BB5 j := i BB5 j :=1 BB5
46. 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.
47. { chèn thêm sj := sj ± c * a } } thêm sj vào họ của i