คลิกที่นี่

Report
สถาปัตยกรรมแบบ stack และ การผลิตโค๊ด
สถาปัตยกรรมแบบ stack
•
•
•
•
มี model การประมวลผลที่ง่าย
ไม่มีตวั แปรหรื อรี จิสเตอร์ มาเกี่ยวข้ อง
ค่า intermediate result ถูกเก็บอยูใ่ น stack
คาสัง่ แต่ละคาสัง่ ในสถาปั ตยกรรมแบบนี ้
– นา operands มาจากส่วนบนของ stack
– ดึง operands เหล่านันออกจาก
้
stack
– คานวณหาผลลัพธ์โดยใช้ ตวั ปฏิบตั ิการ (operation) ที่เลือกมา
– เก็บค่าผลลัพธ์โดยการ push ค่านี ้ลงไปที่ stack
การบวกโดยใช้ stack
ตัวอย่างโปรแกรมของสถาปัตยกรรมแบบ stack
• พิจารณาคาสัง่ 2 รูปแบบ
– push i : ใสค่าของ integer i ไปที่สว่ นบนสุดของ stack (top of
stack)
– add : นาค่าสองค่า (pop) ออกมาจากส่วนบนของ stack และบวกค่า
ทังสองเข้
้
าด้ วยกัน จากนัน้ push ผลลัพธ์ลงไปที่ stack
• ในการจะบวกเลข 7 + 5 ทาได้ ดงั นี ้
push 7
push 5
add
ข้อได้เปรี ยบของ stack machine
• Operation ต่างๆนา operand มาจาก stack และคานวณ
ผลลัพธ์ใส่กลับลงไปที่ stack
• Operand และผลลัพธ์มาจากที่เดียวกัน
– ง่ายต่อการคอมไพล์ ผลิตโค๊ ดคล้ ายๆกัน
– คอมไพล์ไม่มีความซับซ้ อนมาก
• ตาแหน่งที่จะนา operand มาคานวณไม่ต้องมีการระบุชดั เจน
– นามาจากส่วนบนของ stack เสมอ
ข้อได้เปรี ยบของ stack machine
• คาสัง่ ไม่ต้องมีการระบุ operand
• คาสัง่ ไม่ต้องมีการระบุตาแหน่งที่จะใช้ เก็บผลลัพธ์
• ตัวอย่างเช่นการใช้ คาสัง่ add แทนที่จะต้ องเป็ น add $1, $2, $3
– คาสัง่ แต่ละคาสัง่ ใช้ จานวนบิทในการ encode น้ อย
– โปรแกรม binary มีขนาดเล็ก
• ตัวอย่างของชุดคาสัง่ แบบ stack machine เช่น Java
Bytecodes
N-Register Stack Machine
• ลูกผสมระหว่าง register machine และ stack machine
• ตาแหน่ง n ตาแหน่งที่อยูส่ ว่ นบนของ stack จะถูกเก็บไว้ ใน
register
• เราจะสนใจและพิจารณา 1-register stack machine
– โดย register หนึง่ เดียวนี ้จะเรี ยกว่า accumulator
การบวกใน 1-register stack machine
• Stack machine เดิมต้ องติดต่อกับ memory ถึง 3 ครัง้
– อ่านค่าสองค่าจาก stack
– เขียนค่าผลลัพธ์ลง stack
• ถ้ ามี accumulator (acc) มาช่วย:
acc <- acc + top_of_stack
• ติดต่อกับ memory ครัง้ เดียว นอกนันติ
้ ดต่อผ่าน acc ที่เป็ น
register ซึง่ การอ่านและเขียนทาได้ เร็วกว่า memory มาก
การคานวณผ่าน stack machine
• พิจารณา expression op(e1, … , en) ที่มี operation คือ
op และมี operand n ตัว
– e1, …, en เป็ น sub-expression
• สาหรับแต่ละ ei (0 < i < n)
– คานวณหา ei
– ได้ ผลลัพธ์เก็บไว้ ที่ acc และ push ผลลัพธ์ลงบน stack
– คานวณหา enใส่คา่ ผลลัพธ์เข้ าที่ acc แต่ไม่ต้อง push ลง stack
• ค่อยๆไล่ pop ทัง้ n-1 ค่าออกจาก stack เพื่อจะคานวณหา
op(e1, … en-1, acc)
• acc  op(e1, … en-1, acc)
ตัวอย่างการคานวณ
ตัวอย่างการคานวณ
3 + (7 + 5)
คุณสมบัติในการคานวณโดย stack machine
• การคานวณ expression ทุกชนิดจะต้ องไม่ทาให้ stack เดิมที่มี
มาก่อนการคานวณนี ้เปลี่ยนแปลง
• นัน่ คือการคานวณ sub-expression ทังหลายจะต้
้
องคงสถานะ
ของ stack เดิมไว้ หลังจากการคานวณเสร็จสิ ้น
– เรี ยกว่าการคานวณหาผลลัพธ์ของ expression ใดๆ จะต้ อง
preserve stack
MIPS Assembly กับ Stack Machine
• สร้ างคอมไพเลอร์ ที่ผลิตโค๊ ด MIPS assembly สาหรับ 1register stack machine
• รันโค๊ ดใน SPIM ซึง่ เป็ น simulator ของ MIPS ISA
• ให้ accumulator อยูใ่ น $a0
• Stack อยูใ่ นหน่วยความจา
– เติบโตจาก high ไปที่ low address
– เป็ นไปตาม convention ของสถาปั ตยกรรมแบบ MIPS
• $sp เก็บตาแหน่งถัดไปจาก top of stack (tos)
– tos อยูท่ ี่ตาแหน่ง $sp + 4
ทบทวน MIPS ISA
[ตัดไปที่สไลด์เรื่ อง MIPS ISA ที่เราเคยเรี ยนกันในวิชาสถาปั ตยกรรมคอมพิวเตอร์ ]
โค๊ดสาหรับ 7 + 5
Stack machine assembly
MIPS assembly (จาลองการ
ทางานถ้ ารันบน stack machine)
แนวทางการผลิตโค๊ด
• สาหรับ expression e เราจะผลิตโค๊ ด MIPS ที่:
– ใส่ผลลัพธ์ของ e ไว้ ที่ $a0
– ทุกๆครัง้ ที่คานวณ e เราจะต้ อง preserve $sp และ stack (นัน่ คือ
สถานะของ $sp และ stack หลังจากคานวณ e จะต้ องเหมือนกับตอน
ก่อนคานวณ e)
• ให้ ฟังก์ชนั่ cgen(e) ให้ ผลลัพธ์เป็ นโค๊ ดที่ผลิตจาก input ที่เป็ น
expression e
โค๊ดสาหรับค่าคงที่
• ทาได้ ตรงไปตรงมาโดยที่ก๊อปปี ค้ า่ คงที่นนไปไว้
ั้
ที่ accumulator:
cgen(i) = li $a0 i
• เราจะใช้ สีแดงแทนส่วนของโค๊ ดที่อยูใ่ นช่วงเวลาคอมไพล์
• เราจะใช้ สีน ้าเงินแทนส่วนของโค๊ ดที่จะนาไปรัน ณ เวลาจริง
โค๊ดสาหรับการบวก
ความผิดพลาดในการพยายาม optimize
•
•
•
•
โค๊ ดด้ านล่างก๊ อปปี ผ้ ลลัพธ์จาก e1 เข้ าไปไว้ ที่ $t1
คานวณ e2 แล้ วนาผลลัพธ์มาบวกเข้ ากับค่าใน $t1
นาผลลัพธ์สดุ ท้ ายเก็บไว้ ใน accumulator
นิสติ หาข้ อผิดพลาดของการแปลแบบนี ้ได้ หรื อไม่
คุณสมบัติสาคัญในการผลิตโค๊ดแบบนี้
• มีลกั ษณะเหมือนการเติม template ที่สว่ นของโค๊ ด e1 และ e2
จะต้ องถูกเติมเพิ่มเข้ ามา
• การผลิตโค๊ ดสาหรับ stack machine ในลักษณะนี ้จึงเป็ นแบบ
recursive
• ดังนันเราสามารถท
้
าการผลิตโค๊ ดได้ โดย traverse AST แบบ
top-down และใช้ เทคนิค recursive-descent
โค๊ดสาหรับการลบ
โค๊ดสาหรับ control flow

similar documents