Sinh mã

Chia sẻ: Ho Quang Trung | Ngày: | Loại File: DOC | Số trang:12

Thêm vào BST

Báo xấu

82
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

1. Mục đích và nhiệm vụ - Sinh mã : là giai đoạn cuối của quá trình dịch, sinh mã tốt là rất khó và sinh mã ra thường gắn với một loại máy tính nào đó. - Tiêu chuẩn quan trọng đối với bộ sinh mã là phải tạo mã đúng, đặt tiêu chuẩn này lên hàng đầu còn giúp cho việc thiết kế xây dựng và bảo trì bộ sinh mã trở nên đinh hướng tốt hơn, dễ thực hiện hơn và tiết kiệm hơn. Trong thực tế sinh mã máy đòi hỏi nhiều kinh nghiệm, am hiểu về ngôn ngữ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sinh mã

III.Sinh m∙ 1.Môc ®Ých vµ nhiÖm vô Sinh m∙ : lµ giai ®o¹n cuèi cña qu¸ tr×nh dÞch, sinh m∙ tèt lµ rÊt khã vµ sinh m∙ ra th êng g¾n víi mét lo¹i m¸y tÝnh nµo ®ã. Tiªu chuÈn quan träng ®èi víi bé sinh m∙ lµ ph¶i t¹o m∙ ®óng, ®Æt tiªu chuÈn nµy lªn hµng ®Çu cßn gióp cho viÖc thiÕt kÕ x©y dùng vµ b¶o tr× bé sinh m∙ trë nªn ®inh híng tèt h¬n, dÔ thùc hiÖn h¬n vµ tiÕt kiÖm h¬n. Trong thùc tÕ sinh m∙ m¸y ®ßi hái nhiÒu kinh nghiÖm, am hiÓu vÒ ng«n ng÷ lËp tr×nh vµ kyc thuËt m¸y tÝnh. Sau khi hoµn thµnh ë møc ph©n tÝch, ch¬ng tr×nh dÞch chuyÓn sang giai ®o¹n sinh m∙ víi ®Çu vµo lµ ch¬ng tr×nh nguån ë d¹ng c©y có ph¸p hoÆc c©y m∙ trung gian. Giai ®o¹n sinh m∙ bao gåm : + Sinh m∙ trung gian + Tèi u m∙ + Sinh m∙ ®Ých Ch¬ng tr×nh ®Ých mµ chóng ta t¹o ra ë ®©y lµ ch¬ng tr×nh hîp ng÷ Assemble vµ nghiªn cøu ph ¬ng ph¸p sinh m∙ cho : + LÖnh g¸n + BiÓu thøc sè häc + CÊu tróc ®iÒu khiÓn 2.D¹ng m∙ ba ®Þa chØ D¹ng m∙ ba ®Þa chØ lµ lªnh cã d¹ng : x := y Operator z Trong ®ã : x, y, z lµ c¸c biÕn hoÆc bé nhí trung gian. Operator : lµ to¸n tö ( phÐp to¸n) D¹ng m∙ ba ®Þa chØ lµ c©u lÖnh cã hai ®ịa chØ cho to¸n h¹ng vµ mét ®Þa chØ cho to¸n tö. Nã ® îc sö dông ë bíc sinh m∙ trung gian. Mäi biÓu thøc sè häc hoÆc c©u lÖnh ®Òu cã thÓ ®îc biÔu diÔn díi d¹ng m∙ ba ®Þa chØ VÝ dô : Víi c©u lÖnh : A:= X + Y + Z *150
M∙ ba ® Þa chØ sÏ l : T1: Z*150 µ = T2: Y + T1 = A : X + T2 = • C¸c c© u l nh d¹ng m ∙ Ö ba ® Þa chØ : 1LÖ nh : X : Y O perator Z : l phÐ p to¸n sè = µ häc hai ng«i hoÆ c phÐ p to¸n l i og c VÝ dô: X : Y + Z hoÆ c : = B and C = A 2LÖ nh : X : O perator Y : l phÐ p to¸n m ét = µ ng«i , l phÐ p to¸n l sè © m hoÆ c ¶o og i µ Êy ® l c. VÝ dô: X : Y hoÆ c : Not B = A = 3LÖ nh : X : Y l phÐ p g¸n gi trÞ Y cho X (X = µ ¸ ®î g¸n bëi Y) c 4LÖ nh nh¸y kh«ng ® i u ki n: G o to Nhan(Pasca l) Ò Ö J P Nhan ( Assem bl M e) 5LÖ nh nh¸y cã ® i u ki n : Ò Ö If BT l i then G ot Nhan (Pasca l) og c o J , J , J , J , J , … (A ssem bl A B G E LE e) 6C¸c l nh l l i gäi hµm , gäi thñ tôc, l Ö µ ê ªnh l chØ sè m ∙ Êy ® Þa Êy , l chØ con trá… 3.C¸c vÊn ®Ò cña bé sinh m∙ a.§Çu vµo : lµ v¨n b¶n ch¬ng tr×nh nguån ®∙ qua giai ®o¹n ph©n tÝch cã thÓ biÓu diÔn díi d¹ng c©y ph©n tÝch. b.§Çu ra : Bé m∙ cña ch¬ng tr×nh ®èi tîng gåm: Mét ch¬ng tr×nh hoµn toµn b»ng ng«n ng÷ m¸y cã thÓ ch¹y ®îc trªn m¸y tÝnh Ch¬ng tr×nh ng«n ng÷ m¸y cã thÓ ®Þnh vÞ l¹i ®îc ( cã thÓ chÌn, thªm mét ®o¹n m∙). Ch¬ng tr×nh hîp ng÷ Assemble Mét ch¬ng tr×nh b»ng ng«n ng÷ lËp tr×nh kh¸c c. Qu¶n lý bé nhí ViÖc chuyÓn ®æi t¬ng øng tõ tªn biÕn, tªn h»ng trong ch¬ng tr×nh nguån thµnh ®Þa chØ d÷ liÖu trong lóc ch¹y cña ch¬ng tr×nh chÝnh ®îc thùc hiÖn phèi hîp gi÷a c¸c phÇn tríc vµ phÇn sinh m∙, th«ng qua b¶ng ký hiÖu cã thÓ x¸c ®Þnh ®îc mét ®Þa chØ t¬ng ®èi trong miÒn d÷ liÖu. d. Chän chØ thÞ lÖnh
- TÝnh chÊt cña tËp c¸c chØ thÞ lÖnh x¸c ®Þnh møc ®é phøc t ¹p cña viÖc chän chØ thÞ lÖnh. - TÝnh thèng nhÊt vµ tÝnh ®Çy ®ñ lµ nh©n tè quan träng - §èi ví i mçi c©u l ªnh d¹ng m· ba ®Þa chØ ta cã thÓ th iÕt kÕ bé khung ®Ó sinh m· cho nã. §Ó khi sinh m· ta chØ viÖc sö dông bé khung nµy ®Ó t ¹o ra m·. VD: Ví i c©u lÖnh : X:= Y + Z khung m· cña nã lµ Mov AL,Y Add AL,Z Mov X,AL Khi sinh m· cho c¸c lÖnh A:= B+ C, B:= C+D Khi ®ã chØ cÇn sö dông khung m· t rªn ®Ó cã ®o¹n m·, khi ®ã ta sÏ cã Mov AL,B Mov AL,C Add AL,Z Add AL,D Mov X,AL Mov B, AL - Sau khi t ¹o ra ®o¹n míi ta ph¶i thùc hiÖn tè i u b»ng c¸ch lo ¹ i bá c¸c m· l ªnh trung gian mang tÝnh chÊt chuyÓn ® mµ kh«ng ¶nh hëng ®Õn æi ch¬ng tr×nh. e. Sö dông thanh ghi - C¸c lÖnh tÝnh to¸n ®èi ví i thanh ghi th êng nhanh h¬n vµ gän h¬n tÝnh to¸n ví i bé nhí . Do vËy, viÖc sö dông thanh ghi cã hai vÊn ®Ò : + Trong khi dïng thanh ghi ta chän tËp c¸c biÕn sÏ ® ® trong c¸c thanh ghi t¹ i mét vÞ îc Æt t rÝ cña ch¬ng tr×nh + Trong gia i ®o¹n g¸n thanh ghi ta chØ thÞ mét thanh ghi ®Ó l u gi¸ trÞ mét biÕn tr¸nh tr - êng hîp g©y t ranh chÊp xung ®ét. f . M¸y ®Ých - M¸y ®Ých lµ m¸y sÏ ch¹y ch¬ng t r×nh ®Ých mµ bé sinh m· t ¹o ra ë ® ta sö dông m¸y thùc ®Ó ©y m« t¶ vµ m· do bé sinh m· t¹o ra lµ d¹ng m· Assemble. C¸c c©u lÖnh cã d¹ng Operator §Ých, nguån
Trong ®ã : Operator : lµ phÐp xö lý cã thÓ lµ Mov, Add, Sub, Cmp, Mul, Div,…. Nguån, ®Ých lµ c¸c ®Þa chØ d÷ l iÖu chÞu sù t¸c ®éng cña phÐp xö lý. §Ých vµ nguån cã thÓ lµ biÕn hoÆc h»ng. Nh ng tèi thiÓu ph¶i cã sù tham gia cña mét thanh ghi. 4.Sinh m∙ cho lÖnh g¸n vµ biÓu thøc sè häc Dùa vµo c©y có ph¸p ( lµ c©y m« t¶ lÖnh g¸n hoÆc biÓu thøc sè häc) ® x©y dùng trong qu¸ îc tr×nh ph©n tÝch có ph¸p. Tõ c©y nµy ta dÞch sacng m· ®Ých trong qu¸ tr×nh dÞch ph¶i tham kh¶o c¸c ký hiÖu trong b¶ng ký hiÖu. Ta cã thÓ xem c©y có ph¸p lµ c©y m· ch¬ng tr×nh trung gian. Mµ t¹ i nót thø n trªn c©y cã ®o¹n m· lªnh, kÝ hiÖu lµ C(n). Khi ®ã ®Ó sinh m· mét nót n cña c©y chóng ta ph¶i ghÐp c¸c ®o¹n m· con hoÆc ch¸u theo mét trËt tù nhÊt ®Þnh. TrËt tù ®ã lµ tÝnh tõ dí i lªn vµ tõ tr¸ i qua ph¶i cña c©y. Cã ba d¹ng nót trªn c©y := + * a) b) c) Trong ®ã : Ký hiÖu lµ mét nót (c©y con). Riªng nót tr¸ i cña d¹ng a lµ mét tªn biÕn VD1: Víi lÖnh g¸n A:= < id1> + + ta sÏ biÓu diÔn nh sau : n2 n1 A := n0 < d1> i < d2> i * < d3> i
- Nót d¹ng a, gi¸ trÞ c©y con bªn ph¶i ® ph¸t îc cho bªn biÕn bªn tr¸ i . - Nót d¹ng b, c, m· lÖnh C(n) lµ gi¸ trÞ cña c©y con bªn tr¸ i c«ng hoÆc nh©n gi¸ trÞ c©y con bªn ph¶i. §Ó t iÖn cho viÖc sinh m· ngêi ta quy ®Þnh bËc cña c©y BËc cña nót thø n trªn c©y, ký hiÖu lµ b(n) { B(n) = 0 nÕu n lµ nót l¸ Max (b (ni) )+1 nÕu nót n cã k con n1,n2,…nk i :=1,. . , k VD2: Víi vÝ dô 1 trªn ta cã b(n0) = 1 ; b(n1) = (1+1) = 2 ; b(n2) = (2+1) = 3 a. Gi¶i thuËt sinh m· cho lÖnh g¸n Vµo: C©y m· trung gian biÓu diÔn lÖnh g¸n x©u ω Ra : m· lÖnh Qu¸ tr×nh thùc hiÖn: Thùc hiÖn bíc 1 hoÆc 2 cho nót bËc 0. Bíc 1: + nót thø j trong b¶ng ký hiÖu gi¶ sö cã tªn lµ x th× Cj = x + Nót thø j trong b¶ng ký hiÖu gi¶ sö cã gi¸ trÞ k th× Ck = k Bíc2: Nót n thuéc c¸c nót : = , +, *, - , / , cã C(n) = φ Bíc 3: nót n lµ nót d¹ng a, cã 3 con n1, n2, n3, khi ®ã : C(n) lµ : Mov Ri, C(n3) Mov C(n) , Ri Ri lµ thanh ghi nµo ®ã Bíc 4: nót n lµ nót d¹ng b, cã 3 con n1, n2, n3, Khi ®ã C(n) lµ : Mov Ri, C(n1) Add Ri , C(n3) Mov C(n) , Ri Bíc 5: Nót n lµ nót d¹ng c, cã 3 con lµ n1, n2, n3 Khi ®ã C(n) lµ : Mov Ri, C(n1),
Mov Rj , C(n3) Nul Ri Mov C(n), Ri Víi Ri = Ri * Rj Ri= Work Rj= Byte VD: Sinh m· cho lÖnh g¸n A:= X + Y + Z *150 Ta cã c©y m· trung gian lµ : n3 n2 A := n1 x n0 y + Z * 150 Sinh m· : Bíc 1: + C(n01) = Z , C(n11) = Y , C(n21) = X , C(n31) = A + C(n03) = 150 , Bíc 2: C¸c nót n02, n12, n22, n32 cã m· b»ng φ Bíc 3: Nót n0 cã 3 con n01 ,n 02 ,n 03, m· lÖnh C(n0 ) lµ Mov AH,0 ; AL = C(n01) Mov AL, Z ; BL = C(n03) Mov BL, 150 Mul BL Mov Temp1, AL Bíc 4: Nót n1 cã 3 con n11, n12 , n13 m· lÖnh C(n1) lµ : Mov AL, Temp1 Add Al, Y Mov Temp2, AL Bíc 4 : Nót n2 cã 3 con n21, n22 , n23 m· lÖnh C(n) lµ Mov AL, Temp2 Add AL, X
M ov Tem p3, AL Bí 5 : Nót n3 cã 3 con n31 , n32 , n33 m∙ lÖnh lµ c Mov AL, Temp3 Mov A, AL VËy m∙ thu ®îc: Mov AH, 0 Mov Al,Z Mov BL, 150 Mul BL Mov Temp1, AL ;1 Mov AL, Temp1 ;2 Add AL, Y Mov Temp2, AL ; 3 Mov AL, TEMP2 ;4 Add AL,X Mov Temp3, AL ;5 Mov AL, Temp3 ;6 Mov A, AL • Tèi u m∙ : Ta thÊy c¸c cÆp lÖnh ( 1, 2) ; (3, 4); (5, 6); lµ d thõa v× vËy ta lo¹i bá c¸c lÖnh nµy. Ta cã m∙ lÖnh : Mov AH ,0 Mov AL, Z Mov BL, 150 Mul BL Add AL, Y Add AL, X Mov A, AL b. Gi¶i thuËt cho sinh m∙ cho biÓu thøc sè häc Vµo : X©u ω biÓu thøc sè häc Ra : M∙ lÖnh Assembly CÊu tróc d÷ liÖu : D÷ liÖu 2 Stack : + 1 Stack to¸n tö : STT + 1 Stack to¸n h¹ng : STH vµ 1 Buffer Khëi t¹o : STT vµ STH chøa $ (®¸y) Buffer chøa ω $ Repeat {Dùa vµo viÖc ph¸t hiÖn tõ c¸n vµ quan hÖ u tiªn}
- NÕu ký hiÖu t iÕp ®Õn trong Buffer lµ to¸n h¹ng th× dÞch chuyÓn vµo STH - NÕu ký hiÖu t iÕp ®Õn trong Buffer lµ to¸n tö th× ta so s¸nh ví i to¸n tö ë ®Ønh STT. NÕu l í n h¬n th× dÞch chuyÓn vµo STT. Ngîc l ¹ i nÕu nhá h¬n th× : Repeat Gì 2 to¸n h¹ng ë ®Ønh STH Gì 1 to¸n tö ë ®Ønh STT Thùc hiÖn sinh m· cho to¸n tö vµ hai to¸n h¹ng ®ã. §Èy kÕt qu¶ ®ã vµo STH. Unt i l §é u t i ªn ë ®Ønh STT < To¸n tö t iÕp ®Õn trong Buffer dÞch chuyÓn vµo STT - NÕu gÆp ngoÆc t r¸ i th× xem biÓu thøc trong m· cïng cÊp cÇn sinh m· lµ x©u míi cÇn sinh m·, ®Èy ngoÆc tr¸ i vµo STT lµm ®¸y míi . Ví i ký hiÖu kÕt thóc x©u míi lµ ngoÆc ph¶i cïng cÊp. - NÕu Buffer rçng Repeat Gì 2 to¸n h¹ng ë ®Ønh STH Gì 1 to¸n tù ë ®Ønh STT Sinh m· cho to¸n tö vµ 2 to¸n h¹ng ®ã ®Èy kÕt qu¶ vµo STH Unt i l STT= φ ( rçng) Unt i l STT = φ VD : Sinh m· nhËp biÓu thøc ω = “ a + b * ( c + d) “ LËp b¶ng Bíc STT STH Buffer Hµnh ®éng 0 $ $ a+b*(c+ DÞch chyÓn 1 $ $a d)$ STH 2 $+ $a +b*(c+d DÞch chyÓn 3 $+ $ab )$ STT 4 $+* $ab b*(c+d) DÞch chyÓn 5 $+*( $ab $ STH 6 $+*( $abc *(c+d)$ DÞch chyÓn 7 $+*(+ $abc (c+d)$ STT 8 $+*(+ $abcd c+d)$ DÞch chyÓn +d)$ STT
d)$ DÞch chuyÓn c )$ STH DÞch chyÓn+ 9 $+* $abt1 STT DÞch chyÓnd STH $ Gì d,c vµ gì + Mov AL, d Add AL, c 10 $+ $at2 Mov t1,AL Push (t1,STH) Gì T1,b; Gì * $ Mov AH, 0 Mov AL, t1 11 $ $t3 Mov BL,b M BL ul Mov t2, AX $ Push (t2, STH) Gì t2, a; gì + Mov AX t2 , Add AX, a Mov t3, AX Push (t3, STH) Dõng M· thu ® lµ îc Mov AL, d Add AL, c Mov t1, AL Mov AH, 0 Mov AL, t1 Mov BL, b Mul BL Mov t2, AX Mov AX, t2 Add AX, a
Mov t3, AX • Tèi u ho¸ Mov AL, d Add AL, c Mov AH, 0 Mov BL, b Mul BL Add AX, a Mov t3, AX 5. Sinh m∙ cho c¸c cÊu tróc ®iÒu khiÓn RÏ nh¸nh : + RÏ 2 nh¸nh : - i f….. then - i f …then…..else + RÏ nhiÒu nh¸nh : - Case …of …and - Case….of….else…and LÆp : + While … do + Repeat….Unti l + For chuyÓn sang d¹ng While vµ sinh m· theo While Mét sè vÝ dô : VD1: Sinh m· cho ®o¹n ch¬ng tr×nh sau: 1). I f a>b then a: = a-b 2). I f a+b >c then a:= a+c else b:= b+c Gi¶i: 1. Mov AL, a Cmp AL, b JLE Tiep Sub AL, b Mov a, AL Tiep 2. Mov AL,a Add AL,b Cmp AL,c JLE ELSE Mov AL,a Add AL,c Mov a, AL Jmp Tiep ELSE Mov AL,b
Add AL,c Mov b, AL Tiep: VD2: Sinh m· cho ®o¹n ch¬ng tr×nh sau : Case chon of 1: Begin S:= a*b; c:= (a+b)*2; End; 2: Begin S:= 3.14*R*R; c:= 2*3.14*R; End; End; Gi¶i: Mov CL,chon Cmp CL,1 JNE L1 Mov AH,0 Mov AL,a Mov BL,b Nul BL Mov S,AL Mov AL,a Add AL,b Mov BL,2 Mul BL Mov c,AL Jmp Tiep L1: Cmp CL,2 JNE Tiep Mov AL, 3.14 Mov BL,R Mul BL Mul BL Mov S,AL Mov AL, 3.14 Mul BL Mov BL,2
Mul BL Mov C,AL Tiep: Bµi tËp: 1. Sinh m· cho ®o¹n ch¬ng tr×nh sau : tt := csm- csc; Case dtt of 1..100: tt := dtt*5; 101..200: tt := 500 +(dtt- 100)*6.5 Else tt := 2300+(dtt- 200)*9.5 End; 2. While ab do I f a>b then a:= a-b Else b:= b-a; USCLN := a; 3. S1:= 0 ; S2:=0; i :=1; Repeat If i mod 2 = 0 then S2:= S2+i Else S1:= S1+i; I :=i+1; Unti l i>n; 3. KT:=1; I f x