Giáo trình Xây dựng chương trình dịch - Chương IX: Sinh mã đích

Nội dung text: Giáo trình Xây dựng chương trình dịch - Chương IX: Sinh mã đích

1. CHƯƠNG IX SINH MÃ ÐÍCH Nội dung chính: Giai đoạn cuối của quá trình biên dịch là sinh mã đích. Dữ liệu nhập của bộ sinh mã đích là biểu diễn trung gian của chương trình nguồn và dữ liệu xuất của nó là một chương trình đích (hình 9.1). Kỹ thuật sinh mã đích được trình bày trong chương này không phụ thuộc vào việc dùng hay không dùng giai đoạn tối ưu mã trung gian . Chương trình Biên dịch Mã trung Bộ tối ưu Mã trung Bộ sinh mã Chương nguồn kỳ đầu gian mã gian đích trình đích Bảng danh biểu Hình 9.1- Vị trí của bộ sinh mã đích Nhìn chung một bộ sinh mã đích phải đảm bảo chạy hiệu quả và phải tạo ra chương trình đích đúng sử dụng hiệu quả tài nguyên của máy đích. Về mặt lý thuyết, vấn đề sinh mã tối ưu là không thực hiện được. Trong thực tế, ta có thể chọn những kỹ thuật heuristic để tạo ra mã tốt nhưng không nhất thiết là mã tối ưu. Chương này đề cập đến các vấn đề cần quan tâm khi thiết kế một bộ sinh mã. Bên cạnh đó một bộ sinh mã đích đơn giản từ chuỗi các lệnh ba địa chỉ cũng được giới thiệu. Mục tiêu cần đạt: Sau khi học xong chương này, sinh viên phải: • Nắm được các vấn đề cần chú ý khi thiết kế bộ sinh mã đích. • Biết cách tạo ra một bộ sinh mã đích đơn giản từ chuỗi các mã lệnh ba điạ chỉ. Từ đó có thể mở rộng bộ sinh mã này cho phù hợp với ngôn ngữ lập trình cụ thể. Kiến thức cơ bản: Sinh viên phải có kiến thức về kiến trúc máy tính đặc biệt là phần hợp ngữ (assembly language) để thuận tiện cho việc tiếp nhận kiến thức về máy đích. Tài liệu tham khảo: [1] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [2] Design of Compilers : Techniques of Programming Language Translation - Karen A. Lemone - CRC Press, Inc, 1992. 187
2. ta chuyển sang mã đích: MOV b, Ro ADD c, Ro MOV Ro, a MOV a, R0 ADD e,Ro MOV Ro, d và ta nhận thấy rằng chỉ thị thứ tư là thừa. Chất lượng mã được tạo ra được xác định bằng tốc độ và kích thước của mã. Một máy đích có tập chỉ thị phong phú có thể sẽ cung cấp nhiều cách để hiện thực một tác vụ cho trước. Ðiều này có thể dẫn đến tốc độ thực hiện chỉ thị rất khác nhau. Chẳng hạn, nếu máy đích có chỉ thị INC thì câu lệnh ba địa chỉ a := a + 1 có thể được cài đặt chỉ bằng câu lệnh INC a. Cách này hiệu quả hơn là dùng chuỗi các chỉ thị sau: MOV a, Ro ADD # 1, Ro MOV Ro ,a Như ta đã nói, tốc độ của chỉ thị là một trong những yếu tố quan trọng để thiết kế chuỗi mã tốt. Nhưng, thông tin thời gian thường khó xác định. Việc quyết định chuỗi mã máy nào là tốt nhất cho câu lệnh ba điạ chỉ còn phụ thuộc vào ngữ cảnh của nơi chưá câu lệnh đó. 4. Cấp phát thanh ghi Các chỉ thị dùng toán hạng thanh ghi thường ngắn hơn và nhanh hơn các chỉ thị dùng toán hạng trong bộ nhớ. Vì thế, hiệu quả của thanh ghi đặc biệt quan trọng trong việc sinh mã tốt. Ta thường dùng thanh ghi trong hai trường hợp: 1. Trong khi cấp phát thanh ghi, ta lựa chọn tập các biến lưu trú trong các thanh ghi tại một thời điểm trong chương trình. 2. Trong khi gán thanh ghi, ta lấy ra thanh ghi đặc biệt mà biến sẽ thường trú trong đó. Việc tìm kiếm một lệnh gán tối ưu của thanh ghi, ngay với cả các giá trị thanh ghi đơn, cho các biến là một công việc khó khăn. Vấn đề càng trở nên phức tạp hơn vì phần cứng và / hoặc hệ điều hành của máy đích yêu cầu qui ước sử dụng thanh ghi. 1. Lựa chọn cho việc đánh giá thứ tự Thứ tự thực hiện tính toán có thể ảnh hưởng đến tính hiệu quả của mã đích . Một số thứ tự tính toán có thể cần ít thanh ghi để lưu giữ các kết quả trung gian hơn các thứ tự tính toán khác. Việc lựa chọn được thứ tự tốt nhất là một vấn đề khó. Ta nên tránh vấn đề này bằng cách sinh mã cho các lệnh ba địa chỉ theo thứ tự mà chúng đã được sinh ra bởi bộ mã trung gian. 2. Sinh mã Tiêu chuẩn quan trọng nhất của bộ sinh mã là phải tạo ra mã đúng. Tính đúng của mã có một ý nghĩa rất quan trọng. Với những quy định về tính đúng của mã, việc thiết kế bộ sinh mã sao cho nó được thực hiện, kiểm tra, bảo trì đơn giản là mục tiêu thiết kế quan trọng . 189
3. giờ cũng xảy ra trước thời gian thực hiện chỉ thị. Vì vậy, bằng việc tối thiểu hóa độ dài chỉ thị, ta còn tối thiểu hoá được thời gian cần để thực hiện chỉ thị. Một số minh họa việc tính giá của chỉ thị: 1. Chỉ thị MOV R0, R1 : Sao chép nội dung thanh ghi R0 vào thanh ghi R1. Chỉ thị này có giá là một vì nó chỉ chiếm một từ trong bộ nhớ . 2. MOV R5, M: Sao chép nội dung thanh ghi R5 vào vị trí nhớ M. Chỉ thị này có giá trị là hai vì địa chỉ của vị trí nhớ M là một từ sau chỉ thị. 3. Chỉ thị ADD #1, R3: cộng hằng 1 vào nội dung thanh ghi R3. Chỉ thị có giá là hai vì hằng 1 phải xuất hiện trong từ kế tiếp sau chỉ thị. 4. Chỉ thị SUB 4(R0), *12 (R1) : Lưu giá trị của contents (contents (12 + contents (R1))) - contents (4 + contents (R0)) vào đích *12( R1). Giá của chỉ thị này là ba vì hằng 4 và 12 được lưu trữ trong hai từ kế tiếp theo sau chỉ thị. Với mỗi câu lệnh ba địa chỉ, ta có thể có nhiều cách cài đặt khác nhau. Ví dụ câu lệnh a := b + c - trong đó b và c là biến đơn, được lưu trong các vị trí nhớ phân biệt có tên b, c - có những cách cài đặt sau: 1. MOV b, Ro ADD c, R0 giá = 6 MOV Ro, a 2. MOV b, a giá = 6 ADD c, a 3. Giả sử thanh ghi R0, R1, R2 giữ địa chỉ của a, b, c. Chúng ta có thể dùng hai địa chỉ sau cho việc sinh mã lệnh: a := b + c => MOV *R1, *Ro giá = 2 ADD * R2, *Ro 4. Giả sử thanh ghi R1 và R2 chứa giá trị của b và c và trị của b không cần lưu lại sau lệnh gán. Chúng ta có thể dùng hai chỉ thị sau: ADD R2, R1 giá = 3 MOV R1, a Như vậy, với mỗi cách cài đặt khác nhau ta có những giá khác nhau. Ta cũng thấy rằng muốn sinh mã tốt thì phải hạ giá của các chỉ thị . Tuy nhiên việc làm khó mà thực hiện được. Nếu có những quy ước trước cho thanh ghi, lưu giữ địa chỉ của vị trí nhớ chứa giá trị tính toán hay địa chỉ để đưa trị vào, thì việc lựa chọn chỉ thị sẽ dễ dàng hơn. III. QUẢN LÝ BỘ NHỚ TRONG THỜI GIAN THỰC HIỆN Trong phần này ta sẽ nói về việc sinh mã để quản lý các mẩu tin hoạt động trong thời gian thực hiện. Hai chiến lược cấp phát bộ nhớ chuẩn được trình bày trong chương VII là cấp phát tĩnh và cấp phát Stack. Với cấp phát tĩnh, vị trí của mẩu tin hoạt động trong bộ nhớ được xác định trong thời gian biên dịch. Với cấp phát Stack, một mẩu tin hoạt động được đưa vào Stack khi có sự thực hiện một thủ tục và được lấy ra khỏi Stack khi hoạt động kết thúc. Ở đây, ta sẽ xem xét cách thức mã đích của một thủ tục tham chiếu tới các đối tượng dữ liệu trong 191
4. Ví dụ 9.1: Mã đích trong chương trình sau được tạo ra từ các chương trình con c và p ở hình 9.2. Giả sử rằng: các mã đó được lưu tại địa chỉ bắt đầu là 100 và 200, mỗi chỉ thị action chiếm 20 byte, và các mẩu tin hoạt động cho c và p được cấp phát tĩnh bắt đầu tại các địa chỉ 300 và 364 . Ta dùng chỉ thị action để thực hiện câu lệnh action. Như vậy, mã đích cho các chương trình con: /* mã cho c*/ 100: ACTION1 120: MOV #140, 364 /* lưu địa chỉ trả về 140 */ 132: GOTO 200 /* gọi p */ 140: ACTION2 160: HALT /* mã cho p */ 200: ACTION3 220: GOTO *364 /* trả về địa chỉ được lưu tại vị trí 364 */ /* 300-364 lưu mẩu tin hoạt động của c */ 300: /* chứa địa chỉ trả về */ 304: /* dữ liệu cục bộ của c */ /* 364 - 451 chứa mẩu tin hoạt động của p */ 364: /* chứa địa chỉ trả về */ 368: /* dữ liệu cục bộ của p */ Hình 9.3 - Mã đích cho dữ liệu vào của hình 9.2 Sự thực hiện bắt đầu bằng chỉ thị action tại địa chỉ 100. Chỉ thị MOV ở địa chỉ 120 sẽ lưu địa chỉ trả về 140 vào trường trạng thái máy, là từ đầu tiên trong mẩu tin hoạt động của p. Chỉ thị GOTO 200 sẽ chuyển quyền điều khiển về chỉ thị đầu tiên trong đoạn mã của chương trình con p. Chỉ thị GOTO *364 tại địa chỉ 132 chuyển quyền điều khiển sang chỉ thị đầu tiên trong mã đích của chương trình con được gọi. Giá trị 140 được lưu vào địa chỉ 364, *364 biểu diễn giá trị 140 khi lệnh GOTO tại địa chỉ 220 được thực hiện. Vì thế quyền điều khiển trả về địa chỉ 140 và tiếp tục thực hiện chương trình con c. 2. Cấp phát theo cơ chế Stack Cấp phát tĩnh sẽ trở thành cấp phát Stack nếu ta sử dụng địa chỉ tương đối để lưu giữ các mẩu tin hoạt động. Vị trí mẩu tin hoạt động chỉ được xác định trong thời gian thực thi. Trong cấp phát Stack, vị trí này thường được lưu vào thanh ghi. Vì thế các ô nhớ của mẩu tin hoạt động được truy xuất như là độ dời (offset) so với giá trị trong thanh ghi đó. Thanh ghi SP chứa địa chỉ bắt đầu của mẩu tin hoạt động của chương trình con nằm trên đỉnh Stack. Khi lời gọi của chương trình con xuất hiện, chương trình bị gọi được cấp phát, SP được tăng lên một giá trị bằng kích thước mẩu tin hoạt động của chương trình gọi và chuyển quyền điều khiển cho chương trình con được gọi. Khi quyền điều khiển trả về cho chương trình gọi, SP giảm đi một khoảng bằng kích thước mẩu tin hoạt động của chương trình gọi. Vì thế, mẩu tin của chương trình con được gọi đã được giải phóng. Mã cho chương trình con đầu tiên có dạng: 193
5. Hình 9.4 - Mã ba địa chỉ minh hoạ cấp phát sử dụng Stack /* mã cho s */ action1 call q action2 halt /* mã cho p */ action3 return /* mã cho q */ action4 call p action5 call q action6 call q return /* mã cho s*/ 100: MOV # 600, SP /* khởi động Stack */ 108: ACTION1 128: ADD #ssize, SP /* chuỗi gọi bắt đầu */ 136: MOV #152, *SP /* lưu địa chỉ trả về */ 144: GOTO 300 /* gọi q */ 152: SUB #ssize, SP /* Lưu giữ SP */ 160: ACTION2 180: HALT /* mã cho p */ 200: ACTION3 220: GOTO *0(SP) /* trả về chương trình gọi */ /* mã cho q */ 300: ACTION4 /* nhảy có điều kiện về 456 */ 320: ADD #qsize, SP 328: MOV #344, *SP /* lưu địa chỉ trả về */ 336: GOTO 200 /* gọi p */ 344: SUB #qsize, SP 352: ACTION5 372: ADD #qsize, SP 380: MOV #396, *SP /* lưu địa chỉ trả về */ 195
6. IV. KHỐI CƠ BẢN VÀ LƯU ÐỒ Ðồ thị biểu diễn các lệnh ba địa chỉ, được gọi là lưu đồ, giúp ta hiểu các giải thuật sinh mã ngay cả khi đồ thị không được xác định cụ thể bằng giải thuật sinh mã. Các nút của lưu đồ biểu diễn sự tính toán, các cạnh biểu diễn dòng điều khiển. 1. Khối cơ bản Khối cơ bản (basic block) là chuỗi các lệnh kế tiếp nhau trong đó dòng điều khiển đi vào lệnh đầu tiên của khối và ra ở lệnh cuối cùng của khối mà không bị dừng hoặc rẽ nhánh. Ví dụ chuỗi lệnh ba địa chỉ sau tạo nên một khối cơ bản t1 := a * a t2 := a * b t3 := 2 * t2 t4 := t1 + t2 t5 := b * b t6 := t4 + t5 Lệnh ba địa chỉ x := y + z dùng các giá trị được chứa ở các vị trí nhớ của y, z để thực hiện phép cộng và xác định địa chỉ của x để lưu kết quả phép cộng vào. Một tên trong khối cơ bản được gọi là ‘sống‘ tại một điểm nào đó nếu giá trị của nó sẽ được sử dụng sau điểm đó trong chương trình hoặc được dùng ở khối cơ bản khác. Giải thuật sau đây phân chia chuỗi các lệnh ba địa chỉ sang các khối cơ bản. ‰ Giải thuật 9.1: Phân chia các khối cơ bản Input: Các lệnh ba địa chỉ. Output: Danh sách các khối cơ bản với từng chuỗi các lệnh ba địa chỉ cho từng khối. Phương pháp: 1. Xác định tập các lệnh dẫn đầu (leader), các lệnh đầu tiên của các khối cơ bản, ta dùng các quy tắc sau: i) Lệnh đầu tiên là lệnh dẫn đầu. ii) Bất kỳ lệnh nào là đích nhảy đến của lệnh GOTO có điều kiện hoặc không điều kiện đều là lệnh dẫn đầu. iii) Bất kỳ lệnh nào đi sau lệnh GOTO có điều kiện hoặc không điều kiện đều là lệnh dẫn đầu. 2. Với mỗi lệnh dẫn đầu, khối cơ bản gồm có nó và tất cả các lệnh tiếp theo nhưng không gồm một lệnh dẫn đầu nào khác hay là lệnh kết thúc chương trình. Ví dụ 9.3: Ðoạn chương trình sau tính tích vectơ vô hướng của hai vectơ a và b có độ dài 20. Begin prod := 0 i := 1 Repeat prod: = prod + a [i] * b[i]; 197
7. Khối cơ bản sau: a := b + c b := a - d c := b + c d := a - d Câu lệnh thứ hai và thứ tư tính cùng một biểu thức b + c - d. Vì vậy, khối cơ bản này được chuyển thành khối tương đương sau: a := b + c b := a - d c := b + c d := b 2. Loại bỏ mã lệnh chết Giả sử x không còn được sử dụng nữa. Nếu câu lệnh x := y + z xuất hiện trong khối cơ bản thì lệnh này sẽ bị loại mà không làm thay đổi giá trị của khối. 3. Ðặt lại tên cho biến tạm Giả sử ta có lệnh t := b + c với t là biến tạm. Nếu ta viết lại lệnh này thành u := b + c mà u là biến tạm mới và thay t bằng u ở bất cứ chỗ nào xuất hiện t thì giá trị của khối cơ bản sẽ không bị thay đổi. Thực tế, ta có thể chuyển một khối cơ bản sang một khối cơ bản tương đương. Và ta gọi khối cơ bản được tạo ra như vậy là dạng chuẩn. Giả sử chúng ta một khối với hai câu lệnh kế tiếp: t1 := b + c t2 := x + y Ta có thể hoán đổi hai lệnh này mà không làm thay đổi giá trị của khối nếu và chỉ nếu x và y đều không phải t1 cũng như b và c đều không phải là t2. Khối cơ bản có dạng chuẩn cho phép tất cả các lệnh có quyền hoán đổi nếu có thể. Chuyển đổi đại số Các biểu thức trong một khối cơ bản có thể được chuyển đổi sang các biểu thức tương đương. Phép chuyển đổi đại số này giúp ta đơn giản hoá các biểu thức hoặc thay thế các biểu thức có giá cao bằng các biểu thức có giá rẻ hơn. Chẳng hạn, câu lệnh x := x + 0 hoặc x := x * 1 có thể được loại bỏ khỏi khối mà không làm thay đối giá trị của biểu thức. Toán tử lũy thừa trong câu lệnh x := y 2 cần một lời gọi hàm để thực hiện. Tuy nhiên, lệnh này vẫn có thể được thay bằng lệnh tương đương có giá rẻ hơn mà không cần lời gọi hàm. 3. Lưu đồ Ta có thể thêm thông tin về dòng điều khiển vào tập các khối cơ bản bằng việc xây dựng các đồ thị trực tiếp được gọi là lưu đồ (flew graph). Các nút của lưu đồ là khối cơ bản. Một nút được gọi là khởi đầu nếu nó chứa lệnh đầu tiên của chương trình. Cạnh nối trực tiếp từ khối B1 đến khối B2 nếu B2 là khối đứng ngay sau B1 trong một chuỗi thực hiện nào đó. Nghĩa là, nếu: 1. Lệnh nhảy không hoặc có điều kiện từ lệnh cuối của B1 sẽ đi đến lệnh đầu tiên của B2B . 199
8. Trường hợp lệnh điều kiện, chẳng hạn if i <= 20 goto, ta coi là trường hợp (i) với x không được định nghĩa. 1. Nếu node (y) không được định nghĩa, tạo lá có tên y và node (y) chính là nút này. Trong trường hợp (i), nếu node(z) không được định nghĩa, ta tạo lá tên z và lá chính là node (z). 2. Trong trường hợp (i) , xác định xem trên DAG có nút nào có tên op mà con trái là node (y) và con phải là node (z). Nếu không thì tạo ra nút có tên op, ngược lại n là nút đã tìm thấy hoặc đã được tạo. Trong trường hợp (ii) , ta xác định xem có nút nào có tên op, mà nó chỉ có một con duy nhất là node (y). Nếu chưa có nút như trên ta sẽ tạo nút op và coi n là nút tìm thấy hoặc vừa được tạo ra. Trong trường hợp thứ (iii) thì đặt n là node(y). 3. Xoá x ra khỏi danh sách các danh biểu gán với nút node(x). Nối x vào danh sách các danh biểu gắn vào nút n được tìm ở bước (2) và đặt node(x) cho n. 5. Vòng lặp Vòng lặp (loop) là một tập hợp các nút trong lưu đồ sao cho: 1. Tất cả các nút trong tập hợp phải kết nối chặt chẽ với nhau, nghĩa là phải có con đường với kích thước bằng một hoặc lớn hơn đi từ một nút bất kỳ trong vòng lặp đến một nút bất kỳ khác và nó phải nằm hoàn toàn trong vòng lặp. 2. Các nút lựa chọn này chỉ có duy nhất một lối vào, nghĩa là con đường từ nút ngoài vòng lặp đi vào vòng lặp phải đi qua lối vào đó. Nếu một vòng lặp không chứa vòng lặp nào khác thì gọi là vòng lặp trong cùng. V. THÔNG TIN SỬ DỤNG TIẾP 1. Tính toán sử dụng tiếp Việc sử dụng tên trong lệnh ba địa chỉ được định nghĩa như sau: Giả sử lệnh ba địa chỉ i gán một giá trị cho x. Nếu x là một toán hạng trong lệnh j, dòng điều khiển đi từ lệnh i đến j đồng thời dọc đường đi này ta không xen vào các lệnh gán cho x, thì ta nói rằng lệnh j dùng giá trị của x được tính toán tại i. Trong chương này, ta chỉ đề cập đến việc tiếp tục sử dụng tên của một lệnh ba địa chỉ ngay trong khối chứa lệnh đó. Giải thuật xác định những sử dụng tiếp theo tạo nên sự duyệt lùi đi qua các khối cơ bản. Ta có thể dễ dàng xác định lệnh ba địa chỉ cuối cùng của mỗi khối cơ bản. Vì các chương trình con có những hiệu ứng lề tùy ý nên ta giả sử rằng mỗi lời gọi chương trình con bắt đầu tại mỗi khối cơ bản mới. Ðể tìm lệnh cuối cùng của một khối cơ bản, ta duyệt lùi tới phần đầu, lưu giữ các thông tin như: x có được tiếp tục sử dụng trong khối hay không? x có còn “sống” khi ra khỏi khối? Giả sử rằng ta tới được lệnh ba địa chỉ i: x := y op z trong khi duyệt lùi. Ta có thể làm theo các như sau: 1. Gán cho lệnh i các thông tin được tìm thấy trong bảng danh biểu. Ðó là những thông tin xác định x, y, z có được tiếp tục sử dụng? và còn “sống”? 2. Trong bảng danh biểu, đặt x không “sống” và không được dùng tiếp. 201
9. Nếu b ở trong Ri , c ở trong bộ nhớ , ta có thể tạo chỉ thị: ADD c, Ri giá = 2 Hoặc nếu b ở trong thanh ghi Ri và giá trị của c được đưa từ bộ nhớ vào Rj sau đó thực hiện phép cộng hai thanh ghi Ri, Rj, ta có thể tạo các chỉ thị: MOV c, Rj ADD Rj , Ri giá = 3 Qua các trường hợp trên chúng ta thấy rằng có nhiều khả năng để tạo ra mã đích cho một lệnh ba địa chỉ. Tuy nhiên, việc lựa chọn khả năng nào lại tuỳ thuộc vào ngữ cảnh của mỗi thời điểm cần tạo mã. 1. Mô tả thanh ghi và địa chỉ Giải thuật sinh mã đích dùng bộ mô tả (descriptor) để lưu giữ nội dung thanh ghi và địa chỉ của tên. 1. Bộ mô tả thanh ghi sẽ lưu giữ những gì tồn tại trong từng thanh ghi cũng như cho ta biết khi nào cần một thanh ghi mới. Ta giả sử rằng lúc đầu, bộ mô tả sẽ khởi động sao cho tất cả các thanh ghi đều rỗng. Khi sinh mã cho các khối cơ bản, mỗi thanh ghi sẽ giữ giá trị 0 hoặc các tên tại thời điểm thực hiện. 2. Bộ mô tả địa chỉ sẽ lưu giữ các vị trí nhớ nơi giá trị của tên có thể được tìm thấy tại thời điểm thực thi. Các vị trí đó có thể là thanh ghi, vị trí trên Stack, địa chỉ bộ nhớ. Tất cả các thông tin này được lưu trong bảng danh biểu và sẽ được dùng để xác định phương pháp truy xuất tên. 2. Giải thuật sinh mã đích Giải thuật sinh mã sẽ nhận vào chuỗi các lệnh ba địa chỉ của một khối cơ bản. Với mỗi lệnh ba địa chỉ dạng x := y op z ta thực hiện các bước sau: 1. Gọi hàm getreg để xác định vị trí L nơi lưu giữ kết quả của phép tính y op z. L thường là thanh ghi nhưng nó cũng có thể là một vị trí nhớ. 2. Xác định địa chỉ mô tả cho y để từ đó xác định y’, một trong những vị trí hiện hành của y. Chúng ta ưu tiên chọn thanh ghi cho y’nếu cả thanh ghi và vị trí nhớ đang giữ giá trị của y. Nếu giá trị của y chưa có trong L, ta tạo ra chỉ thị: MOV y', L để lưu bản sao của y vào L. 3. Tạo chỉ thị op z', L với z' là vị trí hiện hành của z. Ta ưu tiên chọn thanh ghi cho z' nếu giá trị của z được lưu giữ ở cả thanh ghi và bộ nhớ. Việc xác lập mô tả địa chỉ của x chỉ ra rằng x đang ở trong vị trí L. Nếu L là thanh ghi thì L là đang giữ trị của x và loại bỏ x ra khỏi tất cả các bộ mô tả thanh ghi khác. 4. Nếu giá trị hiện tại của y và/ hoặc z không còn được dùng nữa khi ra khỏi khối, và chúng đang ở trong thanh ghi thì sau khi ra khỏi khối ta phải xác lập mô tả thanh ghi để chỉ ra rằng các thanh ghi trên sẽ không giữ trị y và/hoặc z. Nếu mã ba địa chỉ có phép toán một ngôi thì các bước thực hiện sinh mã đích cũng tương tự như trên. Một trường hợp cần đặc biệt lưu ý là lệnh x := y. Nếu y ở trong thanh ghi, ta phải thay đổi thanh ghi và bộ mô tả địa chỉ, là giá trị của x được tìm thấy ở thanh ghi chứagiá trị của y. Nếu y không được dùng tiếp thì thanh ghi đó sẽ không còn lưu trị của y nữa. Nếu y ở trong bộ nhớ, ta dùng hàm getreg để tìm một thanh ghi tải giá trị của y và xác lập rằng thanh ghi đó là 203
10. Lần gọi đầu tiên của hàm getreg trả về R0 như một vị trí để xác định t. Vì a không ở trong R0 , ta tạo ra chỉ thỉ MOV a, R0 và SUB b, R0. Ta cập nhật lại bộ mô tả để chỉ ra rằng R0 chứa t. Việc sinh mã đích tiếp tục tiến hành theo cách này cho đến khi lệnh ba địa chỉ cuối cùng d := v + u được xử lý. Chú ý rằng R0 là rỗng vì u không còn được dùng nữa. Sau đó ta tạo ra chỉ thị, cuối cùng của khối, MOV R0, d để lưu biến “sống” d. Giá của chuỗi mã đích được sinh ra như ở trên là 12. Tuy nhiên, ta có thể giảm giá xuống còn 11 bằng cách thay chỉ thị MOV a, R1 bằng MOV R0, R1 và xếp chỉ thị này sau chỉ thị thứ nhất. 4. Sinh mã cho loại lệnh khác Các phép toán xác định chỉ số và con trỏ trong câu lệnh ba địa chỉ được thực hiện giống như các phép toán hai ngôi. Hình sau minh họa việc sinh mã đích cho các câu lệnh gán: a := b[i], a[i] := b và giả sử b được cấp phát tĩnh . Câu lệnh 3 i trong thanh ghi Ri i trong bộ nhớ Mi i trên Stack địa chỉ Mã Giá Mã Giá Mã Giá a:= b[ i ] MOV b(Ri ), R 2 MOV Mi, R 4 MOV Si(A), R 4 MOV b(R), R MOV b(R), R a[i]:=b MOV b, a(Ri) 3 MOV Mi , R 5 MOV Si(A), R 5 MOV b, a (R) MOV b, a (R) Hình 9.10 - Chuỗi mã đích cho phép gán chỉ mục Với mỗi câu lệnh ba địa chỉ trên ta có thể có nhiều đoạn mã đích khác nhau tuỳ thuộc vào i đang ở trong thanh ghi, hoặc trong vị trí nhớ Mi hoặc trên Stack tại vị trí Si và con trỏ trong thanh ghi A chỉ tới mẩu tin hoạt động của i. Thanh ghi R là kết quả trả về khi hàm getreg được gọi. Ðối với lệnh gán đầu tiên, ta đưa a vào trong R nếu a tiếp tục được dùng trong khối và có sẵn thanh ghi R. Trong câu lệnh thứ hai ta giả sử rằng a được cấp phát tĩnh. Sau đây là chuỗi mã đích được sinh ra cho các lệnh gán con trỏ dạng a := *p và *p := a. Vị trí nhớ p sẽ xác định chuỗi mã đích tương ứng. Câu p trong thanh ghi lệnh 3 p trong bộ nhớ Mi p trong Stack R địa chỉ p Mã Giá Mã Giá Mã Giá a:= *p MOV *Rp, a 2 MOV Mp, R 3 MOV Sp(A), R 3 MOV *R, R MOV *R, R *p:= a MOV a, *Rp 2 MOV Mp, R 4 MOV a, R 4 MOV a, *R MOV R, *Sp(A) Hình 9.11 - Mã đích cho phép gán con trỏ Ba chuỗi mã đích tuỳ thuộc vào p ở trong thanh ghi Rp, hoặc p trong vị trí nhớ Mp, hoặc p ở trong Stack tại offset là Sp và con trỏ, trong thanh ghi A, trỏ tới mẩu tin hoạt động của p. Thanh ghi R là kết quả trả về khi hàm getreg được gọi. Trong câu lệnh gán thứ hai ta giả sử rằng a được cấp phát tĩnh. 205