Giáo trình Chương trình dịch - Bài 11: Sinh mãm đích - Nguyễn Thị Thu Hương

21/1/2010 1 Bài 12 Sinh mã đích 1 Nguyễn Thị Thu Hương Nội dung z Tổng quan về sinh mã đích z Máy ngăn xếp z Tổ chức bộ nhớ z Bộ lệnh Lớp KHMT K50 2 z Sinh mã cho các lệnh cơ bản z Xây dựng bảng ký hiệu z Biến z Tham số z Hàm, thủ tục và chương trình Chương trình đích „ Viết trên một ngôn ngữ trung gian „ Là dạng Assembly của máy giả định (máy ảo) „ Máy ảo làm việc với bộ nhớ stack 3 „ Việc thực hiện chương trình thông qua một interpreter „ Interpreter mô phỏng hành động của máy ảo thực hiện tập lệnh assembly của nó Chương trình đích được dịch từ „ Mã nguồn „ Mã trung gian 4 21/1/2010 2 Máy ngăn xếp z Máy ngăn xếp là một hệ thống tính toán z Sử dụng ngăn xếp để lưu trữ các kết quả trung gian của quá trình tính toán z Kiến trúc đơn giản Lớp KHMT K50 5 z Bộ lệnh đơn giản z Máy ngăn xếp có hai vùng bộ nhớ chính z Khối lệnh: chứa mã thực thi của chương trình z Ngăn xếp: sử dụng để lưu trữ các kết quả trung gian Máy ngăn xếp JMP 2 INC 4 LA 0,4 LC 1 RV DL RA SL Code buffer Stack PC B Lớp KHMT K50 6 ST P1 P2 V1 V2 tmp1 T T ↑ Máy ngăn xếp z Thanh ghi z PC (program counter): con trỏ lệnh trỏ tới lệnh hiện tại đang thực thi trên bộ đệm chương trình Lớp KHMT K50 7 z B (base) : con trỏ trỏ tới địa chỉ gốc của vùng nhớ cục bộ. Các biến cục bộ được truy xuất gián tiếp qua con trỏ này z T (top); trỏ tới đỉnh của ngăn xếp Máy ngăn xếp z Bản hoạt động (activation record/stack frame) z Không gian nhớ cấp phát cho mỗi chương trình con (hàm/thủ tục/chương trình chính) khi chúng được kích hoạt z Lưu giá trị tham số z Lưu giá trị biến cục bộ z Lưu các thông tin khác ề Lớp KHMT K50 8 z Giá trị trả v của hàm – RV z Địa chỉ cơ sở của bản hoạt động của chương trình con gọi tới (caller) – DL z Địa chỉ lệnh quay về khi kết thúc chương trình con – RA z Địa chỉ cơ sở của bản hoạt động của chương trình con bao ngoài – SL z Một chương trình con có thể có nhiều bản hoạt động 21/1/2010 3 Máy ngăn xếp RV DL RA SL Param I Local x Procedure P(I : integer); Var a : integer; Function Q; Var x : char; Begin return E d P frame Lớp KHMT K50 9 n ;Procedure R(X: integer); Var y : char; Begin y = Call Q; End; Begin Call R(1); End; RV DL RA SL Local x RV DL RA SL param x Local y R frame Q frame Máy ngăn xếp z RV (return value): Lưu trữ giá trị trả về cho mỗi hàm z DL (dynamic link): Sử dụng để hồi phục ngữ cảnh của chương trình gọi (caller) khi chương trình được gọi (callee) kết thúc Lớp KHMT K50 10 z RA (return address): Sử dụng để tìm tới lệnh tiếp theo của caller khi callee kết thúc z SL (static link): Sử dụng để truy nhập các biến phi cục bộ Máy ngăn xếp z Bộ lệnh LA Load Address t:=t+1; s[t]:=base(p)+q; LV Load Value t:=t+1; s[t]:=s[base(p)+q]; op p q Lớp KHMT K50 11 LC Load Constant t:=t+1; s[t]:=q; LI Load Indirect s[t]:=s[s[t]]; INT Increment T t:=t+q; DCT Decrement T t:=t-q; Máy ngăn xếp z Bộ lệnh J Jump pc:=q; FJ False Jump if s[t]=0 then pc:=q; t:=t-1; op p q Lớp KHMT K50 12 HL Halt Halt ST Store s[s[t-1]]:=s[t]; t:=t-2; CALL Call s[t+2]:=b; s[t+3]:=pc; s[t+4]:=base(p);b:=t+1; pc:=q; EP ExitProcedure t:=b-1; pc:=s[b+2]; b:=s[b+1]; EF ExitFunction t:=b; pc:=s[b+2]; b:=s[b+1]; 21/1/2010 4 Máy ngăn xếp z Bộ lệnh RC ReadCharacter read one character into s[s[t]]; t:=t-1; RI Read Integer read integer to s[s[t]]; t:=t-1; op p q Lớp KHMT K50 13 WRC WriteCharacter write one character from s[t]; t:=t-1; WRI Write Integer write integer from s[t]; t:=t-1; WLN New Line CR & LF Máy ngăn xếp z Bộ lệnh AD Add t:=t-1; s[t]:=s[t]+s[t+1]; SB Subtract t:=t-1; s[t]:=s[t]-s[t+1]; op p q Lớp KHMT K50 14 ML Multiply t:=t-1; s[t]:=s[t]*s[t+1]; DV Divide t:=t-1; s[t]:=s[t]/s[t+1]; NEG Negative s[t]:=-s[t]; CV Copy Top ofStack s[t+1]:=s[t]; t:=t+1; Máy ngăn xếp z Bộ lệnh EQ Equal t:=t-1; if s[t] = s[t+1] then s[t]:=1 elses[t]:=0; NE Not Equal t:=t-1; if s[t] != s[t+1] then s[t]:=1 elses[t]:=0; op p q Lớp KHMT K50 15 GT GreaterThan t:=t-1; if s[t] > s[t+1] then s[t]:=1 else s[t]:=0; LT Less Than t:=t-1; if s[t] < s[t+1] then s[t]:=1 elses[t]:=0; GE Greater orEqual t:=t-1; if s[t] >= s[t+1] then s[t]:=1 else s[t]:=0; LE Less orEqual t:=t-1; if s[t] <= s[t+1] then s[t]:=1 else s[t]:=0; Xây dựng bảng ký hiệu z Bổ sung thông tin cho biến z Vị trí trên frame z Phạm vi z Bổ sung thông tin cho tham số z Vị trí trên frame Lớp KHMT K50 16 z Phạm vi z Bổ sung thông tin cho hàm/thủ tục/chương trình z Địa chỉ bắt đầu z Kích thước của frame z Số lượng tham số của hàm/thủ tục 21/1/2010 5 Xây dựng bảng ký hiệu z Bổ sung thông tin cho biến z Vị trí trên frame (vị trí tính từ base của frame) z Phạm vi Lớp KHMT K50 17 struct VariableAttributes_ { Type *type; struct Scope_ *scope; int localOffset; }; Xây dựng bảng ký hiệu z Bổ sung thông tin cho tham số z Vị trí trên frame z Phạm vi Lớp KHMT K50 18 struct ParameterAttributes_ { enum ParamKind kind; Type* type; struct Scope_ *scope; int localOffset; }; Xây dựng bảng ký hiệu z Bổ sung thông tin cho phạm vi z Kích thước frame Lớp KHMT K50 19 struct Scope_ { ObjectNode *objList; Object *owner; struct Scope_ *outer; int frameSize; }; Xây dựng bảng ký hiệu z Bổ sung thông tin cho hàm z Vị trí z Số lượng tham số Lớp KHMT K50 20 struct FunctionAttributes_ { struct ObjectNode_ *paramList; Type* returnType; struct Scope_ *scope; int paramCount; CodeAddress codeAddress; }; 21/1/2010 6 Xây dựng bảng ký hiệu z Bổ sung thông tin cho thủ tục z Vị trí z Số lượng tham số Lớp KHMT K50 21 struct ProcedureAttributes_ { struct ObjectNode_ *paramList; struct Scope_* scope; int paramCount; CodeAddress codeAddress; }; Xây dựng bảng ký hiệu z Bổ sung thông tin cho chương trình z Vị trí Lớp KHMT K50 22 struct ProgramAttributes_ { struct Scope_ *scope; CodeAddress codeAddress; }; int sizeOfType(type* t) „ Trả về số ngăn nhớ trên stack mà một biến thuộc kiểu đó sẽ chiếm. Lớp KHMT K50 23 void declareObject(Object* obj) „ Đối tượng toàn cục …Đưa vào symtab->GlobalObjectList „ Đối tượng khác: …Đưa vào symtab->currentScope->objList Lớp KHMT K50 24 …Variable: „ Cập nhật scope = currentScope „ Cập nhật localOffset = currentScope- >frameSize „ Tăng kích thước frameSize 21/1/2010 7 void declareObject(Object* obj) „ Đối tượng khác: …Parameter „ Cập nhật scope = currentScope „ Cập nhật localOffset = currentScope->frameSize Lớp KHMT K50 25 „ Tăng kích thước frameSize „ Cập nhật paramList của owner „ Tăng paramCount của owner. void declareObject(Object* obj) „ Đối tượng khác: …Function „ Cập nhật outer = currentScope Lớp KHMT K50 26 …Procedure „ Cập nhật outer = currentScope kplrun z Là bộ thông dịch cho máy ngăn xếp $ kplrun [-s=stack-size] [-c=code-size] [-debug] [-dump] z Tùy chọn –s: định nghĩa kích thước stack Lớp KHMT K50 27 z Tùy chọn –c: định nghĩa kích thước tối đa của mã nguồn z Tùy chọn –dump: In mã ASM z Tùy chọn –debug: chế độ gỡ rối kplrun z Tùy chọn –debug: chế độ gỡ rối z a: địa chỉ tuyệt đối của địa chỉ tương đối (level, offset) Lớp KHMT K50 28 z v: giá trị tại địa chỉ tương đối (level,offset) z t: giá trị đầu ngăn xếp z c: thoát khỏi chế độ gỡ rối 21/1/2010 8 Instructions.c enum OpCode { OP_LA, // Load Address: OP_LV, // Load Value: OP_LC, // load Constant OP_LI, // Load Indirect OP_INT, // Increment t OP_DCT, // Decrement t OP J, // Jump OP_RC, // Read Char OP_RI, // Read Integer OP_WRC, // Write Char OP_WRI, // Write Int OP_WLN, // WriteLN OP_AD, // Add OP_SB, // Substract OP ML, // Multiple Lớp KHMT K50 29 _ OP_FJ, // False Jump OP_HL, // Halt OP_ST, // Store OP_CALL, // Call OP_EP, // Exit Procedure OP_EF, // Exit Function _ OP_DV, // Divide OP_NEG, // Negative OP_CV, // Copy Top OP_EQ, // Equal OP_NE, // Not Equal OP_GT, // Greater OP_LT, // Less OP_GE, // Greater or Equal OP_LE, // Less or Equal OP_BP // Break point. }; Instructions.c struct Instruction_ { enum OpCode op; WORD p; WORD q; }; struct CodeBlock_ { Instruction* code; CodeBlock* createCodeBlock(int maxSize); void freeCodeBlock(CodeBlock* codeBlock); void printInstruction(Instruction* instruction); void printCodeBlock(CodeBlock* codeBlock); void loadCode(CodeBlock* codeBlock, FILE* f); void saveCode(CodeBlock* codeBlock, FILE* f); int emitLA(CodeBlock* codeBlock, WORD p, WORD q); Lớp KHMT K50 30 int codeSize; int maxSize; }; int emitLV(CodeBlock* codeBlock, WORD p, WORD q); int emitLC(CodeBlock* codeBlock, WORD q); . int emitLT(CodeBlock* codeBlock); int emitGE(CodeBlock* codeBlock); int emitLE(CodeBlock* codeBlock); int emitBP(CodeBlock* codeBlock); codegen.c void initCodeBuffer(void); void printCodeBuffer(void); void cleanCodeBuffer(void); int serialize(char* fileName); int genLA(int level, int offset); int genLV(int level int offset); Lớp KHMT K50 31 , int genLC(WORD constant); . int genLT(void); int emitGE(void); int emitLE(void); Sinh mã lệnh gán V := exp // đẩy địa chỉ của v lên stack // đẩy giá trị của exp lên stack ST Lớp KHMT K50 32 21/1/2010 9 Sinh mã lệnh if If Then statement; // đẩy giá trị điều kiện dk lên stack FJ L L: Lớp KHMT K50 33 If Then st1 Else st2; // đẩy giá trị điều kiện dk lên stack FJ L1 J L2 L1: L2: Sinh mã lệnh while While Do statement L1: FJ L2 Lớp KHMT K50 34 co e o s a emen J L1 L2: Sinh mã lệnh for For v := exp1 to exp2 do statement CV // nhân đôi địa chỉ của v ST // lưu giá trị đầu của v L1: CV Lớp KHMT K50 35 LI // lấy giá trị của v LE FJ L2 CV;CV;LI;LC 1;AD;ST; // Tăng v lên 1 J L1 L2: DCT 1 Lấy địa chỉ/giá trị biến z Khi lấy địa chỉ/giá trị một biến cần tính đến phạm vi của biến z Biến cục bộ được lấy từ frame hiện tại Lớp KHMT K50 36 z Biến phi cục bộ được lấy theo các StaticLink với cấp độ lấy theo “độ sâu” của phạm vi hiện tại so với phạm vi của biến computeNestedLevel(Scope* scope) 21/1/2010 10 Lấy địa chỉ của tham số hình thức „ Khi LValue là tham số „ Cũng cần tính độ sâu như biến …Nếu là tham trị: địa chỉ cần lấy chính là địa chỉ Lớp KHMT K50 37 của tham trị …Nếu là tham biến: vì giá trị của tham biến chính là địa chỉ muốn truy nhập, địa chỉ cần lấy chính là giá trị của tham biến. Lấy giá trị của tham số hình thức „ Khi tính toán giá trị của Factor „ Cũng cần tính độ sâu như biến …Nếu là tham trị: giá trị của tham trị chính là giá Lớp KHMT K50 38 trị cần lấy. …Nếu là tham biến: giá trị của tham số là địa chỉ của giá trị cần lấy. Lấy địa chỉ của giá trị trả về của hàm z Giá trị trả về luôn nằm ở offset 0 trên frame z Chỉ cần tính độ sâu giống như với biến hay tham số hình thức Lớp KHMT K50 39 Sinh lời gọi hàm/thủ tục z Lời gọi z Hàm gặp trong sinh mã cho factor z Thủ tục gặp trong sinh mã lệnh CallSt ủ ầ ả Lớp KHMT K50 40 z Trước khi sinh lời gọi hàm/th tục c n ph i nạp giá trị cho các tham số hình thức bằng cách z Tăng giá trị T lên 4 (bỏ qua RV,DL,RA,SL) z Sinh mã cho k tham số thực tế z Giảm giá trị T đi 4 + k z Sinh lệnh CALL 21/1/2010 11 Sinh mã cho lệnh CALL (p, q) CALL (p, q) s[t+2]:=b; // Lưu lại dynamic link s[t+3]:=pc; // Lưu lại return address s[t+4]:=base(p); // Lưu lại static link b:=t+1; // Base mới và return value pc:=q; // địa chỉ lệnh mới Giả sử cần sinh lệnh CALL cho hàm/thủ tục A Lệnh CALL(p, q) có hai tham số: p: Độ sâu của lệnh CALL, chứa static link. Lớp KHMT K50 41 Base(p) = base của frame chương trình con chứa khai báo của A. q: Địa chỉ lệnh mới q + 1 = địa chỉ đầu tiên của dãy lệnh cần thực hiện khi gọi A. Hoạt động khi thực hiện lệnh CALL(p, q) 1. Điều khiển pc chuyển đến địa chỉ bắt đầu của chương trình con /* pc = p */ 2. pc tăng thêm 1 /* pc ++ */ 3. Lệnh đầu tiên thông thường là lệnh nhảy J để bỏ qua mã Lớp KHMT K50 42 lệnh của các khai báo hàm/ thủ tục cục bộ trên code buffer. 4. Lệnh tiếp theo là lệnh INT tăng T đúng bằng kích thước frame để bỏ qua frame chứa vùng nhớ của các tham số và biến cục bộ. Hoạt động khi thực hiện lệnh CALL(p, q) 5. Thực hiện các lệnh và stack biến đổi tương ứng. 6. Khi kết thúc 1. Thủ tục (lệnh EP): toàn bộ frame được giải phóng, con trỏ T đặt lên đỉnh frame cũ. Lớp KHMT K50 43 2. Hàm (lệnh EF): frame được giải phóng, chỉ chừa giá trị trả về tại offset 0, con trỏ T đặt lên đầu frame hiện thời (offset 0). Sinh mã đích từ mã ba địa chỉ „ Bộ sinh mã trung gian đưa ra mã ba địa chỉ „ Tối ưu trên mã ba địa chỉ 44 „ Từ mã ba địa chỉ đã tối ưu sinh ra mã đích phù hợp với một mô tả máy ảo