21/1/2010
1
Bài 12
Sinh mã đích
1
Sinh
mã
đích
Nguyễn Thị Thu Hương
Nội dung
zTổng quan về sinh mã đích
zMáy ngăn xếp
zTổ chức bộ nhớ
z
Bộlệnh
Lớp KHMT K50
2
Bộ
lệnh
zSinh mã cho các lệnh cơ bản
zXây dựng bảng ký hiệu
zBiến
zTham số
zHà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
yệ ộ
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
zMáy ngăn xếp là một hệ thống tính toán
zSử 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
zKiến trúc đơn giản
Lớp KHMT K50
5
zBộ lệnh đơn giản
zMáy ngăn xếp có hai vùng bộ nhớ chính
zKhối lệnh: chứa mã thực thi của chương trình
zNgă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
LC
1
ST
SL
P1
P2
V1
V2
tmp1 T
T ↑
Máy ngăn xếp
zThanh ghi
zPC (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
chương
trình
zB (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
zT (top); trỏ tới đỉnh của ngăn xếp
Máy ngăn xếp
zBản hoạt động (activation record/stack frame)
zKhô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
zLưu giá trị tham số
zLưu giá trị biến cục bộ
zLưu các thông tin khác
ề
Lớp KHMT K50
8
zGiá 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
zMộ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
Procedure P(I : integer);
Var a : integer;
Function Q;
Var x : char;
Begin
…
return
Ed
P frame
Lớp KHMT K50
9
…
E
n
d
;
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
zRV (return value): Lưu trữ giá trị trả về cho mỗi hàm
zDL (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
1 0
zRA (return address): Sử dụng để tìm tới lệnh tiếp
theo của caller khi callee kết thúc
zSL (static link): Sử dụng để truy nhập các biến phi
cục bộ
Máy ngăn xếp
zBộ 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
1 1
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
zBộ lệnh
JJumppc:=q;
FJ False Jump if s[t]=0 then pc:=q; t:=t-1;
op p q
Lớp KHMT K50
1 2
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 Exit
Procedure t:=b-1; pc:=s[b+2]; b:=s[b+1];
EF Exit
Function t:=b; pc:=s[b+2]; b:=s[b+1];
21/1/2010
4
Máy ngăn xếp
zBộ lệnh
RC Read
Character 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
1 3
WRC Write
Character 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
zBộ 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
1 4
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 o
f
Stack s[t+1]:=s[t]; t:=t+1;
Máy ngăn xếp
zBộ lệnh
EQ Equal t:=t-1; if s[t] = s[t+1] then s[t]:=1 else
s[t]:=0;
NE Not Equal t:=t-1; if s[t] != s[t+1] then s[t]:=1 else
s[t]
:
=
0
;
op p q
Lớp KHMT K50
1 5
s[t]
:
=
0
;
GT Greater
Than
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 else
s[t]:=0;
GE Greater or
Equal
t:=t-1; if s[t] >= s[t+1] then s[t]:=1 else
s[t]:=0;
LE Less or
Equal
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
zBổ sung thông tin cho biến
zVị trí trên frame
zPhạm vi
zBổ sung thông tin cho tham số
z
Vịtrí trên frame
Lớp KHMT K50
1 6
z
Vị
trí
trên
frame
zPhạm vi
zBổ sung thông tin cho hàm/thủ tục/chương trình
zĐịa chỉ bắt đầu
zKích thước của frame
zSố lượng tham số của hàm/thủ tục
21/1/2010
5
Xây dựng bảng ký hiệu
zBổ sung thông tin cho biến
zVị trí trên frame (vị trí tính từ base của frame)
zPhạm vi
Lớp KHMT K50
1 7
struct VariableAttributes_ {
Type *type;
struct Scope_ *scope;
int localOffset;
};
Xây dựng bảng ký hiệu
zBổ sung thông tin cho tham số
zVị trí trên frame
zPhạm vi
Lớp KHMT K50
1 8
struct ParameterAttributes_ {
enum ParamKind kind;
Type* type;
struct Scope_ *scope;
int localOffset;
};
Xây dựng bảng ký hiệu
zBổ sung thông tin cho phạm vi
zKích thước frame
Lớp KHMT K50
1 9
struct Scope_ {
ObjectNode *objList;
Object *owner;
struct Scope_ *outer;
int frameSize;
};
Xây dựng bảng ký hiệu
zBổ sung thông tin cho hàm
zVị trí
zSố lượng tham số
Lớp KHMT K50
2 0
struct FunctionAttributes_ {
struct ObjectNode_ *paramList;
Type* returnType;
struct Scope_ *scope;
int paramCount;
CodeAddress codeAddress;
};