Bài giảng Chương trình dịch - Sinh mã

Nguyễn Phương Thái Bộ môn Khoa học Máy tính  Nội dung Chương trình đích Máy tính ảo Sinh mã Chương trình đích Ngôn ngữ máy tuyệt đối: Có thể được đặt trong một vị trí cố định của bộ nhớ và thực thi ngay được Ưu điểm: Chương trình nhỏ và chạy nhanh. Ngôn ngữ máy định vị: Cho phép biên dịch riêng rẽ các chương trình con, sau đó được liên kết lại với nhau và được tải vào để thực thi nhờ một công cụ tải và liên kết (linking loader). Ưu điểm: Các môđun chương trình độc lập và có dịch độc lập, sau đó kết hợp với nhau thành một chương trình đối tượng hoàn chỉnh nhờ việc liên kết và nạp. Chương trình đích (tiếp) Mã thông dịch: Chuỗi hoạt động của nó được biểu diễn không phải bằng các chỉ thị lệnh máy hoạt động trực tiếp mà bằng các câu lệnh thông dịch trừu tượng ở một dạng mã hoá nào đó. Chương trình biên dịch trong trường hợp này sẽ chuyển chương trình nguồn thành một chương trình với các lệnh ảo này. Chương trình đích này sau đó sẽ được hoạt động nhờ vào một chương trình thông dịch. Ưu điểm: Dễ viết chương trình dịch, có thể chạy trên nhiều nền tảng phần cứng và hệ điều hành. Nhược điểm: Chậm hơn mã máy tuyệt đối nhiều lần Máy đích Để thiết kế một bộ sinh mã, chúng ta phải thông hiểu về máy đích và tập chỉ thị của nó. Để đơn giản, chúng ta sẽ dùng một máy ảo làm máy đích.   Máy tính ảo Tên gọi: VIM Chỉ có hai thanh ghi cùng với bộ nhớ và ngăn xếp Bộ nhớ chương trình và bộ nhớ dữ liệu nằm tách rời nhau Mọi chỉ thị chiếm một ô trong bộ nhớ chương trình chương trình (địa chỉ các ô lệnh này là các số tự nhiên) Một thanh ghi là con trỏ chỉ thị ic có chứa địa chỉ của lệnh sẽ được thực hiện. Đỉnh ngăn xếp được chỉ bằng thanh ghi thứ hai sp. Máy tính ảo (tiếp) Cấu trúc máy tính VIM bao gồm hai thanh ghi ic, sp và bộ nhớ chia thành ba vùng ngăn xếp (stack), bộ nhớ dữ liệu (data), bộ nhớ chương trình (prog) stack data prog sp ic Máy tính ảo (tiếp) Các chỉ thị bao gồm một toán tử và nhiều nhất một tham số (có thể là một số hoặc một địa chỉ trong bộ nhớ chương trình hoặc dữ liệu) Các toán tử số học và quan hệ không có tham số. Chúng thực hiện trên một hoặc hai giá trị (toán hạng) đang nằm trên đỉnh ngăn xếp số học (gọi tắt là ngăn xếp). Các toán hạng này sẽ được thay thế bằng kết quả thu được nhờ áp dụng phép toán cho các toán hạng đó. Máy tính ảo (tiếp) Các chỉ thị nạp (load) và lưu (store), nhẩy (jump) đều có một tham số Lệnh nạp: sao chép dữ liệu của một biến nằm trong bộ nhớ dữ liệu vào đỉnh của ngăn xếp Lệnh lưu: loại bỏ giá trị trên đỉnh của ngăn xếp và đưa nó vào bộ nhớ dữ liệu Các chỉ thị vào ra: không có tham số, lệnh vào đọc một giá trị từ bàn phím và lưu nó vào trong ngăn xếp, lệnh ra loại bỏ giá trị đang ở đỉnh ngăn xếp và ghi nó ra màn hình Máy tính ảo (tiếp) câu lệnh trong ngôn ngữ nguồn SLANG “a := b + c” , với a, b là biến và c là hằng số sẽ được chuyển sang mã máy VIM như sau: ldvar b ldcon c add stvar a Giả sử giá trị b và c ban đầu là 37 và 2 thì quá trình thực hiện trên ngăn xếp như sau: Máy tính ảo (tiếp) Các chỉ thị lệnh của máy đích chia thành các loại: load and store các chỉ thị số học và logic các chỉ thị so sánh chỉ thị không có điều kiện các chỉ thị nhảy có điều kiện các chỉ thị vào ra Máy tính ảo (tiếp) Máy tính ảo (tiếp) Máy tính ảo (tiếp) Một bộ sinh mã đơn giản Giả sử máy đích của chúng ta có các đặc điểm sau: đánh địa chỉ theo byte với bốn byte cho một từ nhớ có n thanh ghi R0, R1, . . ., Rn-1 các chỉ thị hai địa chỉ có dạng op source, destination. Trong đó op là mã toán tử, còn source và destination là các trường dữ liệu. Với một số chỉ thị lệnh như sau: MOV source,destination ADD source,destination SUB source,destination Yêu cầu Thiết kế một bộ sinh mã để sinh ra mã đích cho một dãy câu lệnh ba địa chỉ Để đơn giản, chúng ta giả sử rằng: Mỗi toán tử trong một câu lệnh sẽ có một toán tử tương ứng trong ngôn ngữ đích Kết quả tính được có thể để lại trong thanh ghi càng lâu càng tốt Ví dụ x := y+z với x, y và z đều được cấp phát tĩnh có thể được dịch thành dãy mã ba địa chỉ sau: 	MOV	 y,R0 	ADD	 z,R0 	MOV 	R0,z Ví dụ (tiếp) a := b + c d := a + e sẽ được dịch thành: 	MOV 	b,R0 	ADD 	c,R0 	MOV	R0,a 	MOV	a,R0 	ADD	e,R0 	MOV	R0,d   Ở đây câu lệnh thứ tư là thừa, và câu lệnh thứ ba cũng thừa nếu a sau đó không được dùng. Bản diễn tả thông tin thanh ghi và địa chỉ Bản diễn tả thông tin thanh ghi (register descriptor) theo dõi xem mỗi thanh ghi hiện đang chứa giá trị nào được tham vấn mỗi khi cần đến một thanh ghi mới ban đầu bản diễn tả thông tin thanh ghi cho biết mọi thanh ghi đều rỗng (chưa chứa thông tin). Khi tiến hành sinh mã, mỗi thanh ghi sẽ giữ giá trị của không hoặc nhiều tên tại một thời điểm đã cho. Bản diễn tả địa chỉ (address descriptor) theo dõi vị trị (hoặc các vị trí) có thể tìm được giá trị hiện tại của tên (vị trí có thể là một thanh ghi, một vị trí ngăn xếp, một địa chỉ bộ nhớ hoặc một tập các vị trí này) thông tin này có thể được cất trong bảng ký hiệu và được dùng để xác định phương pháp truy xuất cho một tên. Thuật toán sinh mã Thuật toán sinh mã nhận đầu vào là một dãy câu lệnh ba địa chỉ cấu tạo nên một khối cơ bản. Với mỗi câu lệnh ba địa chỉ có dạng x := y op z chúng ta thực hiện các hành động sau: kích hoạt một hàm getreg để xác định vị trí L, nơi sẽ cất kết quả tính toán y op z với L thường là một thanh ghi, nhưng cũng có thể là một vị trí bộ nhớ. tham vấn bản diễn tả thông tin địa chỉ của y để xác định y’, là một trong các vị trí của y. Ưu tiên chọn thanh ghi cho y’ nếu giá trị của y ở cả trong bộ nhớ và thanh ghi. Nếu giá trị của y không có trong L, sinh chỉ thị lệnh MOV y’,L để đặt một bản sao của y vào L. sinh chỉ thị lệnh OP z’, L với z’ là vị trí hiện tại của z. Một lần nữa chúng ta ưu tiên chọn một thanh ghi hơn là bộ nhớ nếu z có ở cả hai nơi. Cập nhật bản diễn tả thông tin địa chỉ của x để chỉ ra rằng x nằm ở L. Nếu L là thanh ghi, cập nhật bản diễn tả thông tin thanh ghi để chỉ ra rằng nó chứa giá trị của x, và xoá x ra khỏi tất cả các bản tả thông tin thanh ghi. nếu giá trị hiện tại của y hoặc z không có lần dùng kế tiếp, không còn sống sau khi thoát khỏi khối và nằm trong thanh ghi, sửa lại bản diễn tả thông tin thanh ghi để chỉ ra rằng sau khi thực thi x := y op z, những thanh ghi này không còn chứa y và z. Hàm getreg Hàm getreg trả về vị trí L để giữ giá trị của x cho câu lệnh gán x := y op z nếu tên y có trong một thanh ghi và y không được sử dụng tiếp sau khi thực hiện phép toán x := y op z thì vị trí L chính là thanh ghi chứa giá trị của y nếu không tồn tại trường hợp (1), trả về một thanh ghi trống cho L nếu trường hợp (2) thất bại và x có lần dùng kế tiếp trong khối lệnh, chúng ta tìm một thanh ghi R đang bị chiếm. Cất giá trị của R vào một vị trí bộ nhớ bằng chỉ thị MOV R,M. Cập nhật bản diễn tả thông tin địa chỉ cho M và gán vị trí L chính là R. Chú ý trong trường hợp R giữ giá trị của nhiều biến, chúng ta cần sinh một chỉ thị MOV cho mỗi biến cần được lưu. Nếu x không được dùng trong khối, hoặc không có thanh ghi nào thích hợp, chọn vị trí bộ nhớ của x làm L Ví dụ Ví dụ: câu lệnh “d := (a-b)+(a-c)+(a-c)” có thể được dịch thành dãy mã ba địa chỉ như sau: t1 := a – b t2 := a – c t3 := t1 + t2 d := t3 + t2 Ví dụ (tiếp) Sinh mã cho các câu lệnh điều kiện Các máy cài đặt các lệnh nhảy có điều kiện bằng một trong hai cách: Cách 1: rẽ nhánh nếu giá trị của một thanh ghi đã chỉ định thoả một trong sáu điều kiện: âm, không âm, dương, không dương, bằng không, khác không. Ví dụ: câu lệnh ba địa chỉ if xy, x=	 z nhảy đến z nếu mã điều kiện là >=0 CJ>	 z nhảy đến z nếu mã điều kiện là >0 CJ=	 z nhảy đến z nếu mã điều kiện là =0 CJ	 z nhảy đến z nếu mã điều kiện là 0 Ví dụ Xét đoạn mã câu lệnh ba địa chỉ sau đây 	x := y+z 	if x<0 goto z Mã máy như sau: MOV	 y,R0 ADD	 z,R0 MOV 	R0,x CJ<	 z Chú ý: mã điều kiện xác định dựa vào giá trị trong R0 vì đại lượng cuối cùng được tải vào thanh ghi R0