Nhập môn Chương trình dịch - Bài 13

Ngôn ngữ trung gian Là ngôn ngữ cho một loại máy trừu tượng Cho phép sinh mã không phụ thuộc vàomáy đích Cho phép tối ưu mã trước khi sinh mãmáy thật sựPentium
Nội dung trích xuất từ tài liệu:
Nhập môn Chương trình dịch - Bài 13Nhập môn Chương trình dịch Học kì II 2006-2007 Bài 13: Sinh mã trung gian Mô tả các bước dịch (1)Mã nguồn (dãy các kí tự) Phân tích từ vựngIf (a == 0) min = a;Dãy các từ tố (token)If ( Id:a == 0 ) Id:min = Id:a ; ifCây cú pháp Phân tích cú pháp == = ; a 0 min a Phân tích ngữ nghĩaCây cú pháp điều khiển if boolean int == = ; int int 0 int int a min a lvalue Mô tả các bước dịch (2) if Sinh mã trung gianboolean int == = ; int int 0 intint a min a lvalueSEQ(CJUMP(TEMP(a) == 0, L1, L2), Sinh mã assemblyLABEL(L1),TEMP(min) = TEMP(a)LABEL(L2)) Tối ưu mãcmp rb, 0jnz L2 cmp ecx, 0L1: mov ra, rb cmovz edx,ecxL2: Ngôn ngữ trung gian• Là ngôn ngữ cho một loại máy trừu tượng• Cho phép sinh mã không phụ thuộc vào máy đích• Cho phép tối ưu mã trước khi sinh mã máy thật sự Pentium Cây cú pháp Java bytecode + thông tin điều khiển AMD Ngôn ngữ trung gian Cây cú pháp (>40 nút)• Dễ sinh ra từ cây cú pháp• Dễ sinh mã máy Mã trung gian (13 nút)• Số lượng lệnh nhỏ, gọn Pentium (>200 lệnh) – Dễ tối ưu mã – Dễ chuyển sang loại mã máy khác Ngôn ngữ trung gian• Một dạng thể hiện của chương trình nằm giữa cây cú pháp điều khiển và mã máy• Sử dụng – Lệnh nhảy – Thanh ghi – Vị trí trên bộ nhớ Tối ưu mã Pentium Cây cú pháp Mã trung + Java bytecode gian thông tin điều khiển AMD Một ngôn ngữ trung gian• IR (Intermediate Representation) là một cây thể hiện các lệnh của một loại máy trừu tượng• Nút lệnh không trả lại giá trị, được thực hiện theo thứ tự nhất định – Ví dụ: MOVE, SEQ, CJUMP• Nút biểu thức trả lại giá trị, các nút con có thể thực hiện theo thứ tự bất kì – Ví dụ: ADD, SUB – Cho phép tối ưu mã Mô tả các nút biểu thức của IR• CONST(i): hằng số nguyên i• TEMP(t): thanh ghi t, máy trừu tượng có vô hạn thanh ghi.• OP(e1, e2): các phép toán – Số học: ADD, SUB, MUL, DIV, MOD – Logic: AND, OR, XOR, LSHIFT, RSHIFT – So sánh: EQ, NEQ, LT, GT, LEQ, GEQ• MEM(e): giá trị bộ nhớ ở vị trí e• CALL(f, a0, a1, …): giá trị của hàm f với các tham số a0, a1, …• NAME(n): địa chỉ của lệnh hoặc dữ liệu có tên là n• ESEQ(s, e): giá trị của e sau khi lệnh s được thực hiện CONST• Nút CONST đại diện cho hằng số CONST(i)• Giá trị của nút là i TEMP• Nút TEMP đại diện cho một thanh ghi trong số vô hạn các thanh ghi của máy trừu tượng TEMP(t)• Các biến cục bộ và các biến tạm• Để dễ viết, ký hiệu FP = TEMP(FP) là địa chỉ bắt đầu bộ nhớ của hàm• Giá trị của nút là giá trị của thanh ghi tại thời điểm tính toán Toán tử• Máy trừu tượng có nhiều phép toán OP(e1, e2) OP e1 e2• Tính giá trị của e1 và e2, sau đó áp dụng phép toán với các giá trị này• e1 và e2 phải là hai nút có giá trị• Có thể tính giá trị e1 và e2 theo thứ tự bất kì MEM• Nút MEM đại diện cho một vị trí trong bộ nhớ• Giá trị của nút là giá trị tại vị trí e trong bộ nhớ MEM MEM(e) e CALL• Nút CALL đại diện cho một lời gọi hàm CALL CALL(ef, e0, e1,…) … Tham số Địa chỉ của hàm ef e0 e1 e2• Không định nghĩa cách cài đặt việc truyền tham số, quản lý ngăn xếp• Giá trị của nút là giá trị của hàm NAME• Nút NAME đại diện cho địa chỉ của một tên trên bộ nhớ• VD: địa chỉ của một nhãn nhảy NAME(n) ESEQ• Nút ESEQ tính toán giá trị của biểu thức e sau khi thực hiện lệnh s ESEQ(s, e) ESEQ s e Mô tả các nút lệnh của IR• MOVE(dest, e): chuyển giá trị của e vào dest• EXP(e): tính toán giá trị của e, không cần lưu lại kết quả• SEQ(s1, s2, … sn): thực hiện các lệnh theo thứ tự• JUMP(e): nhảy đến địa chỉ e• CJUMP(e, l1, l2): nhảy đến l1 hoặc l2 tuỳ thuộc vào giá trị của e là true hoặc false• LABEL(n): tạo ra nhãn có tên n n = 0; Ví dụ while (n < 10) { n = n + 1; } SEQ( MOVE(TEMP(n), CONST(0)), LABEL(HEAD), CJUMP(LT(TEMP(n), CONST(10)), NAME(BODY), NAME(END)), LABEL(BODY), MOVE(TEMP(n), ADD(TEMP(n), CONST(1))), JUMP(NAME(HEAD)), LABEL(END) ) SEQ LABEL(END) LABEL(HEAD) CJUMP L ...