Bài giảng Xây dựng chương trình dịch: Bài 12 - Nguyễn Thị Thu Hương

21/1/2010

Nội dung

(cid:122) Tổng quan về sinh mã đích (cid:122) Máy ngăn xếp

(cid:122) Tổ chức bộ nhớ Bộ lệnh (cid:122) Bộ lệnh

Bài 12 Sinh mã đích Sinh mã đích

(cid:122) Sinh mã cho các lệnh cơ bản (cid:122) Xây dựng bảng ký hiệu

Nguyễn Thị Thu Hương

(cid:122) Biến (cid:122) Tham số (cid:122) Hàm, thủ tục và chương trình

Lớp KHMT K50

1

2

Chương trình đích

Chương trình đích được dịch từ

(cid:132) Mã nguồn (cid:132) Mã trung gian

ệ

y

(cid:132) Viết trên một ngôn ngữ trung gian (cid:132) Là dạng Assembly của máy giả định (máy ảo) (cid:132) Máy ảo làm việc với bộ nhớ stack ộ (cid:132) Việc thực hiện chương trình thông qua một

interpreter

(cid:132) Interpreter mô phỏng hành động của máy ảo

thực hiện tập lệnh assembly của nó

3

4

1

21/1/2010

Máy ngăn xếp

Máy ngăn xếp

(cid:122) Máy ngăn xếp là một hệ thống tính toán

(cid:122) 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

(cid:122) Kiến trúc đơn giản (cid:122) Bộ lệnh đơn giản

(cid:122) Máy ngăn xếp có hai vùng bộ nhớ chính

(cid:122) Khối lệnh: chứa mã thực thi của chương trình (cid:122) Ngăn xếp: sử dụng để lưu trữ các kết quả trung gian

Lớp KHMT K50

Lớp KHMT K50

5

6

Máy ngăn xếp

Máy ngăn xếp

Code buffer Stack B JMP 2 RV PC INC 4 DL LA 0,4 RA LC 1 LC 1 SL SL ST P1 T ↑ P2 V1 V2 tmp1 T

(cid:122) Thanh ghi

tục/chương trình chính) khi chúng được kích hoạt (cid:122) Lưu giá trị tham số (cid:122) Lưu giá trị biến cục bộ (cid:122) Lưu các thông tin khác

(cid:122) 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 chương trình

(cid:122) Bản hoạt động (activation record/stack frame) (cid:122) Không gian nhớ cấp phát cho mỗi chương trình con (hàm/thủ

gọi tới (caller) – DL

(cid:122) 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

(cid:122) Giá trị trả về của hàm – RV ề (cid:122) Địa chỉ cơ sở của bản hoạt động của chương trình con

(cid:122) T (top); trỏ tới đỉnh của ngăn xếp

bao ngoài – SL

(cid:122) Địa chỉ lệnh quay về khi kết thúc chương trình con – RA (cid:122) Địa chỉ cơ sở của bản hoạt động của chương trình con

Lớp KHMT K50

Lớp KHMT K50

7

8

(cid:122) Một chương trình con có thể có nhiều bản hoạt động

2

21/1/2010

Máy ngăn xếp

Máy ngăn xếp

(cid:122) RV (return value): Lưu trữ giá trị trả về cho mỗi hàm (cid:122) 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

(cid:122) RA (return address): Sử dụng để tìm tới lệnh tiếp

theo của caller khi callee kết thúc

(cid:122) SL (static link): Sử dụng để truy nhập các biến phi

cục bộ

Procedure P(I : integer); … Var a : integer; Function Q; P frame Var x : char; Begin … return End; E d Procedure R(X: integer); R frame

Var y : char; Begin … y = Call Q; … End;

Lớp KHMT K50

Lớp KHMT K50

9

10

Máy ngăn xếp

Máy ngăn xếp

Q frame Begin … Call R(1); … End; RV DL RA SL Param I Local x … RV DL RA SL Local x … RV DL RA SL param x Local y …

(cid:122) Bộ lệnh

(cid:122) Bộ lệnh

Jump

pc:=q;

J

Load Address

t:=t+1; s[t]:=base(p)+q;

LA

FJ

False Jump

if s[t]=0 then pc:=q; t:=t-1;

LV

Load Value

t:=t+1; s[t]:=s[base(p)+q];

HL

Halt

Halt

LC

Load Constant

t:=t+1; s[t]:=q;

ST

Store

s[s[t-1]]:=s[t]; t:=t-2;

LI

Load Indirect

s[t]:=s[s[t]];

s[t+3]:=pc;

s[t+4]:=base(p);

CALL

Call

s[t+2]:=b; b:=t+1; pc:=q;

INT

Increment T

t:=t+q;

EP

t:=b-1; pc:=s[b+2]; b:=s[b+1];

DCT

Decrement T

t:=t-q;

EF

t:=b; pc:=s[b+2]; b:=s[b+1];

Exit Procedure Exit Function

Lớp KHMT K50

Lớp KHMT K50

11

12

op p q op p q

3

21/1/2010

Máy ngăn xếp

Máy ngăn xếp

(cid:122) Bộ lệnh

(cid:122) Bộ lệnh

read one character into s[s[t]]; t:=t-1;

RC

Add

t:=t-1; s[t]:=s[t]+s[t+1];

AD

Read Character

RI

Read Integer

read integer to s[s[t]]; t:=t-1;

SB

Subtract

t:=t-1; s[t]:=s[t]-s[t+1];

WRC

write one character from s[t]; t:=t-1;

Write Character

ML

Multiply

t:=t-1; s[t]:=s[t]*s[t+1];

WRI

Write Integer write integer from s[t]; t:=t-1;

DV

Divide

t:=t-1; s[t]:=s[t]/s[t+1];

WLN

New Line

CR & LF

NEG

Negative

s[t]:=-s[t];

s[t+1]:=s[t]; t:=t+1;

CV

Copy Top of Stack

Lớp KHMT K50

Lớp KHMT K50

13

14

Máy ngăn xếp

Xây dựng bảng ký hiệu

(cid:122) Bổ sung thông tin cho biến

op p q op p q

(cid:122) Bộ lệnh

if s[t] = s[t+1] then s[t]:=1 else

(cid:122) Vị trí trên frame (cid:122) Phạm vi

EQ

Equal

(cid:122) Bổ sung thông tin cho tham số

if s[t] != s[t+1] then s[t]:=1 else

NE

Not Equal

if s[t] > s[t+1] then s[t]:=1 else

(cid:122) Vị trí trên frame (cid:122) Vị trí trên frame (cid:122) Phạm vi

GT

Greater Than

(cid:122) Bổ sung thông tin cho hàm/thủ tục/chương trình

if s[t] < s[t+1] then s[t]:=1 else

LT

Less Than

or

if s[t] >= s[t+1] then s[t]:=1 else

GE

(cid:122) Địa chỉ bắt đầu (cid:122) Kích thước của frame (cid:122) Số lượng tham số của hàm/thủ tục

or

if s[t] <= s[t+1] then s[t]:=1 else

LE

Greater Equal Less Equal

t:=t-1; s[t]:=0; t:=t-1; s[t]:=0; s[t]:=0; t:=t-1; s[t]:=0; t:=t-1; s[t]:=0; t:=t-1; s[t]:=0; t:=t-1; s[t]:=0;

Lớp KHMT K50

Lớp KHMT K50

15

16

op p q

4

21/1/2010

Xây dựng bảng ký hiệu

Xây dựng bảng ký hiệu

(cid:122) Bổ sung thông tin cho biến

(cid:122) Bổ sung thông tin cho tham số

(cid:122) Vị trí trên frame (vị trí tính từ base của frame) (cid:122) Phạm vi

(cid:122) Vị trí trên frame (cid:122) Phạm vi

struct VariableAttributes_ { struct ParameterAttributes_ {

Lớp KHMT K50

Lớp KHMT K50

17

18

Xây dựng bảng ký hiệu

Xây dựng bảng ký hiệu

(cid:122) Bổ sung thông tin cho phạm vi

(cid:122) Bổ sung thông tin cho hàm

(cid:122) Kích thước frame

(cid:122) Vị trí (cid:122) Số lượng tham số

Type *type; struct Scope_ *scope; int localOffset; }; enum ParamKind kind; Type* type; struct Scope_ *scope; int localOffset; };

struct Scope_ { struct FunctionAttributes_ {

Lớp KHMT K50

Lớp KHMT K50

19

20

struct ObjectNode_ *paramList; Type* returnType; struct Scope_ *scope; ObjectNode *objList; Object *owner; struct Scope_ *outer; int frameSize; }; int paramCount; CodeAddress codeAddress; };

5

21/1/2010

Xây dựng bảng ký hiệu

Xây dựng bảng ký hiệu

(cid:122) Bổ sung thông tin cho thủ tục

(cid:122) Bổ sung thông tin cho chương trình

(cid:122) Vị trí

(cid:122) Vị trí (cid:122) Số lượng tham số

Lớp KHMT K50

Lớp KHMT K50

21

22

struct ProcedureAttributes_ { struct ProgramAttributes_ { struct ObjectNode_ *paramList; struct Scope_* scope; struct Scope_ *scope; CodeAddress codeAddress; }; int paramCount; CodeAddress codeAddress; };

int sizeOfType(type* t)

void declareObject(Object* obj)

(cid:132) Đối tượng toàn cục

(cid:133)Đưa vào symtab->GlobalObjectList

(cid:132) Trả về số ngăn nhớ trên stack mà một

biến thuộc kiểu đó sẽ chiếm.

(cid:132) Đối tượng khác:

(cid:133)Đưa vào symtab->currentScope->objList (cid:133)Đưa vào symtab->currentScope->objList (cid:133)Variable:

(cid:132) Cập nhật scope = currentScope (cid:132) Cập nhật localOffset = currentScope-

>frameSize

(cid:132) Tăng kích thước frameSize

Lớp KHMT K50

Lớp KHMT K50

23

24

6

21/1/2010

void declareObject(Object* obj)

(cid:132) Đối tượng khác:

void declareObject(Object* obj) (cid:132) Đối tượng khác: (cid:133)Parameter

(cid:133)Function

(cid:132) Cập nhật outer = currentScope

(cid:133)Procedure

(cid:132) Cập nhật outer = currentScope

(cid:132) Cập nhật scope = currentScope currentScope frameSize (cid:132) Cập nhật localOffset = currentScope->frameSize (cid:132) Cập nhật localOffset (cid:132) Tăng kích thước frameSize (cid:132) Cập nhật paramList của owner (cid:132) Tăng paramCount của owner.

Lớp KHMT K50

Lớp KHMT K50

25

26

kplrun

kplrun

(cid:122) Là bộ thông dịch cho máy ngăn xếp

$ kplrun [-s=stack-size] [-c=code-size] [-debug] [-dump]

(cid:122) Tùy chọn –debug: chế độ gỡ rối

(cid:122) Tùy chọn –s: định nghĩa kích thước

(cid:122) a: địa chỉ tuyệt đối của địa chỉ tương

stack

đối (level, offset) ) ,

(

(cid:122) Tùy chọn –c: định nghĩa kích thước tối

(cid:122) v: giá trị tại địa chỉ tương đối

đa của mã nguồn

(level,offset)

(cid:122) Tùy chọn –dump: In mã ASM (cid:122) Tùy chọn –debug: chế độ gỡ rối

(cid:122) t: giá trị đầu ngăn xếp (cid:122) c: thoát khỏi chế độ gỡ rối

Lớp KHMT K50

Lớp KHMT K50

27

28

7

21/1/2010

Instructions.c

Instructions.c

struct Instruction_ { enum OpCode { enum OpCode op; WORD p; WORD q; 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); struct CodeBlock_ { // Jump Instruction* code; int codeSize; int maxSize; };

Lớp KHMT K50

Lớp KHMT K50

29

30

codegen.c

Sinh mã lệnh gán

int emitLA(CodeBlock* codeBlock, WORD p, WORD q); int emitLA(CodeBlock codeBlock, WORD p, WORD q); 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); 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, OP_J, // Jump OP_FJ, // False Jump OP_HL, // Halt OP_ST, // Store OP_CALL, // Call OP_EP, // Exit Procedure OP_EF, // Exit Function int emitBP(CodeBlock* codeBlock); 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, OP_ML, // Multiple // Multiple 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. };

V := exp

void initCodeBuffer(void); void printCodeBuffer(void); void cleanCodeBuffer(void); int serialize(char* fileName); // đẩy địa chỉ của v lên stack // đẩy giá trị của exp lên stack ST

Lớp KHMT K50

Lớp KHMT K50

31

32

int genLA(int level, int offset); int genLV(int level int offset); int genLV(int level, int offset); int genLC(WORD constant); …. int genLT(void); int emitGE(void); int emitLE(void);

8

21/1/2010

Sinh mã lệnh while

Sinh mã lệnh if

If Then statement;

While Do statement

// đẩy giá trị điều kiện dk lên stack FJ L

L:

L1: … FJ L2 < d t> f t t J L1

If Then st1 Else st2;

// đẩy giá trị điều kiện dk lên stack FJ L1 J L2

L1:

L2:

L2: …

Lớp KHMT K50

Lớp KHMT K50

33

34

Sinh mã lệnh for

Lấy địa chỉ/giá trị biến

…

For v := exp1 to exp2 do statement

(cid:122) Khi lấy địa chỉ/giá trị một biến cần tính

CV // nhân đôi địa chỉ của v ST // lưu giá trị đầu của v

L1:

ụ

ộ

y

đến phạm vi của biến (cid:122) Biến cục bộ được lấy từ frame hiện tại ạ ệ ợ (cid:122) Biến phi cục bộ được lấy theo các

CV CV 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:

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)

DCT 1 …

Lớp KHMT K50

Lớp KHMT K50

35

36

9

21/1/2010

Lấy địa chỉ của tham số hình thức

Lấy giá trị của tham số hình thức

(cid:132) Khi LValue là tham số (cid:132) Cũng cần tính độ sâu như biến

(cid:132) Khi tính toán giá trị của Factor (cid:132) Cũng cần tính độ sâu như biến

(cid:133)Nếu là tham trị: địa chỉ cần lấy chính là địa chỉ (cid:133)Nếu là tham trị: địa chỉ cần lấy chính là địa chỉ

(cid:133)Nếu là tham trị: giá trị của tham trị chính là giá (cid:133)Nếu là tham trị: giá trị của tham trị chính là giá

của tham trị

trị cần lấy.

(cid:133)Nếu là tham biến: vì giá trị của tham biến

(cid:133)Nếu là tham biến: giá trị của tham số là địa

chỉ của giá trị cần lấy.

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ớp KHMT K50

Lớp KHMT K50

37

38

Lấy địa chỉ của giá trị trả về của hàm

Sinh lời gọi hàm/thủ tục

(cid:122) Lời gọi

(cid:122) Giá trị trả về luôn nằm ở offset 0 trên frame (cid:122) Chỉ cần tính độ sâu giống như với biến hay

tham số hình thức

(cid:122) Hàm gặp trong sinh mã cho factor (cid:122) Thủ tục gặp trong sinh mã lệnh CallSt ả

(cid:122) 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

Lớp KHMT K50

Lớp KHMT K50

39

40

(cid:122) Tăng giá trị T lên 4 (bỏ qua RV,DL,RA,SL) (cid:122) Sinh mã cho k tham số thực tế (cid:122) Giảm giá trị T đi 4 + k (cid:122) Sinh lệnh CALL

10

21/1/2010

Hoạt động khi thực hiện lệnh CALL(p, q)

Sinh mã cho lệnh CALL (p, q)

1. Điều khiển pc chuyển đến địa chỉ bắt đầu của chương

CALL (p, q) // Lưu lại dynamic link // Lưu lại return address

trình con /* pc = p */

// Base mới và return value // địa chỉ lệnh mới s[t+2]:=b; s[t+3]:=pc; s[t+4]:=base(p); // Lưu lại static link b:=t+1; pc:=q;

ệ

q

g

y

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ã ệ g 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ộ.

Lớp KHMT K50

Lớp KHMT K50

41

42

Hoạt động khi thực hiện lệnh CALL(p, q)

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. 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.

Sinh mã đích từ mã ba địa chỉ

5. Thực hiện các lệnh và stack biến đổi tương ứng.

(cid:132) Bộ sinh mã trung gian đưa ra mã ba địa

6. Khi kết thúc

chỉ

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ũ.

(cid:132) Tối ưu trên mã ba địa chỉ (cid:132) Tối ưu trên mã ba địa chỉ (cid:132) Từ mã ba địa chỉ đã tối ưu sinh ra mã đích

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).

phù hợp với một mô tả máy ảo

Lớp KHMT K50

44

43

11