Bài giảng môn học Trình biên dịch - Chương 10: Tối ưu mã

Bài giảng chương 10 trình bày những nội dung cơ bản như: Mã trung gian, phân tích dòng dữ liệu, phân tích dòng dữ liệu (Data Flow Analyst) – DFA, loại bỏ dư thừa, tối ưu vòng lặp. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng môn học Trình biên dịch - Chương 10: Tối ưu mãCHÖÔNG 10TOÁI ÖU MAÕ10.1. Giôùi thieäu- Tieâu chuaån chuyeån maõ toát- Toå chöùc cuûa trình bieân dòch toái öufront endBoä toái öu maõPhaân tích doøngñieàu khieånPhaân tíchdoøng döõ lieäuBoä sinh maõChuyeån ñoåiHình 10.1. Toå chöùc cuûa boä toái öu maõMaõ trung gianThí duï 10.1. Chuyeån ñoåi sang maõ trung gian ba ñòa chæ cho ñoaïnchöông trình trong ngoân ngöõ Pascalfor i := n – 1 down to 1 dofor j:= 1 to i doif A [j] > A [j + 1] thenbegintemp := A [j];A [j] := A [j + 1];A [j + 1] := temp;end;Giaû söû moãi oâ nhôù laø 4 byte. Ñòa chæ neàn cuûa daõy A vaäy ñòa chæ phaàn töûthöù j cuûa daõy A laø: addr(A[j]) = addr(A) + (j – 1) * 4.(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)i=n-1ij i < 1 goto (31)j=1if j > i goto (29)t1 = j - 1t 2 = 4 * t1t3 = A [t2]t4 = j + 1t5 = t4 - 1t 6 = 4 * t5t7 = A [t6]ij t3 < t7 goto (27)t8 = j - 1t 9 = 4 * t8temp = A [t9](16)(17)(18)(19)(20)(21)(22)(23)(24)(25)(26)(27)(28)(29)(30)t10 = j + 1t11 = t10 - 1t12 = 4 * t11t13 = A [t12]t4 = j - 1t15 = 4 * t14A [t5] = t13t16 = j + 1t17 = t16 - 1t18 = 4 * t17A [t18] = tempj=j+1goto (4)i=i-1goto 2* Khoái cô baûnThí duï 10.2. Ñoaïn maõ trung gian sau ñöôïc xaùc ñònh 4 khoái cô baûn(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)read Ln := 0k := 0m := 1k := k + mc := k > Lif (c) goto (11)n := n + 1m := m + 2goto (5)write nBB1BB2BB3BB410.2. Phaân tích doøng döõ lieäuCaùc caáu truùc ñieàu khieån nhö if, while, for gaây ra söï reõ nhaùnh cuûachöông trình. Xaùc ñònh ñöôïc söï reõ nhaùnh seõ xaùc ñònh ñöôïc söï thay ñoåitrò cuûa bieán trong chöông trình, töø ñoù söû duïng caùc bieán naøy trong quaùtrình toái öu hoùa.10.2.1. Muïc ñíchXaùc ñònh caáu truùc ñieàu khieån cuûa chöông trình laø:- moâ taû caùc con ñöôøng thöïc hieän chöông trình- xaùc ñònh caùc voøng laëp10.2.2. Ñoà thò doøng ñieàu khieån (Control Flow Graphs)Ñònh nghóa:Ñoà thò doøng ñieàu khieån (CFG) cuûa moät chöông trình laø moät ñoà thò coùhöôùng, ñöôïc kyù hieäu G = (N, E) maø trong ñoù N laø caùc khoái cô baûn, Elaø taäp caïnh theå hieän cho doøng ñieàu khieån giöõa caùc khoái cô baûn.