Kĩ thuật lập trình - Sinh mã

Nguyễn Phương TháiBộ môn Khoa học Máy tínhội dungChương trình đíchMáy tính ảoSinh mãChương trình đíchNgô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 ảoTên gọi: VIMChỉ có hai thanh ghi cùng với bộ nhớ và ngăn xếpBộ nhớ chương trình và bộ nhớ dữ liệu nằm tách rời nhauMọ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)stackdataprogspicMá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ếpLệ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ệuCá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ìnhMá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 bldcon caddstvar aGiả 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 storecác chỉ thị số học và logiccác chỉ thị so sánhchỉ thị không có điều kiệncác chỉ thị nhảy có điều kiệncác chỉ thị vào raMáy tính ảo (tiếp)chỉ thị Nạp và Lưuldcon intvalnạp giá trị số nguyên intval vào ngăn xếpldvar addresssao chép giá trị số nguyên từ địa chỉ bộ nhớ address vào ngăn xếpstvar addressloại bỏ giá trị số nguyên ở đỉnh ngăn xếp và ghi nó vào địa chỉ bộ nhớ addresschỉ thị Phép toán số học hai ngôiaddcộng hai số nguyên subtrừ hai số nguyênmulnhân hai số nguyênMáy tính ảo (tiếp)dvilấy thương của hai số nguyênmdllấy phần dư của hai số nguyênchỉ thị Phép toán số học một ngôineglưu giá trị số nguyên dạng –intval vào ngăn xếpabslưu giá trị tuyệt đối của intval vào ngăn xếpchỉ thị Phép so sánheqbằng (=)nekhác ()ltbé hơn ()gelớn hơn hoặc bằng (>=)Máy tính ảo (tiếp)chỉ thị Nhảyjump addressnhảy tới địa chỉ address mà không cần điều kiệnjift addressloại bỏ giá trị chân lý (gọi là truthval) ra khỏi ngăn xếp; nếu giá trị dó là true thì nhảy tới địa chỉ address, còn nếu trái lại thì chỉ thị tiếp theo sẽ được thực hiệnjiff addressloại bỏ giá trị chân lý (gọi là truthval) ra khỏi ngăn xếp; nếu giá trị dó là false thì nhảy tới địa chỉ address, còn nếu trái lại thì chỉ thị tiếp theo sẽ được thực hiệnchỉ thị Vào rardintđọc một giá trị số nguyên từ bàn phím và lưu nó vào ngăn xếpwrintloại giá trị nằm trên đỉnh ngăn xếp và ghi nó ra màn hìnhcác chỉ thị kháchalfdừng việc thực hiệnMột bộ sinh mã đơn giảnGiả 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,destinationADD source,destinationSUB source,destinationYêu cầuThiế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ữ đíchKết quả tính được có thể để lại trong thanh ghi càng lâu càng tốtVí 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,zVí dụ (tiếp)a := b + c d := a + esẽ đượ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ớiban đầ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 getregHàm getreg trả về vị trí L để giữ giá trị của x cho câu lệnh gán x := y op znế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 ynếu không tồn tại trường hợp (1), trả về một thanh ghi trống cho Lnế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 LVí 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 – bt2 := a – ct3 := t1 + t2d := t3 + t2Ví dụ (tiếp)câu lệnhmã sinh rathông tin thanh ghithông tin địa chỉt1 := a – bMOV a,R0 SUB b,R0R0 chứa t1 t1 trong R0t2 := a – c MOV a,R1 SUB c,R1R0 chứa t1R1 chứa t2t1 trong R0t2 trong R1t3 := t1 + t2ADD R1,R0 R0 chứa t3R1 chứa t2t3 trong R0t2 trong R1d := t3 + t2ADD R1,R0MOV R0,dR0 chứa dd trong R0Sinh mã cho các câu lệnh điều kiệnCá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à >=0CJ> z nhảy đến z nếu mã điều kiện là >0CJ= z nhảy đến z nếu mã điều kiện là =0CJ z nhảy đến z nếu mã điều kiện là 0Ví dụXét đoạn mã câu lệnh ba địa chỉ sau đây x := y+z if x<0 goto zMã máy như sau:MOV y,R0ADD z,R0MOV R0,xCJ< zChú ý: 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