Organisasi Sistem Komputer. Prosedur. Sekolah Teknik Elektro dan Informatika ITB

Organisasi Sistem Komputer

Bagian 7 Prosedur

Sekolah Teknik Elektro dan Informatika ITB 2009 1

Pembahasan Stac 3 Stack pada IA32 Konvensi penyimpanan dalam register Membuat pointer pada variabel lokal

2

Stack pada IA32 Stack “Paling Bawah”

Bagian dari memori yang mengelola l l stack t k Stack bertambah pada alamat yang lebih rendah Register %esp menunjukkan alamat stack yang paling bawah

Alamat Bertambah B Besar

ƒ Alamat dari elemen paling atas Stack Pointer %esp

Stack Bertambah Ke Bawah

Stack “Paling Paling Atas Atas” 3

Push Stack Stack “Paling Bawah”

y p p Penyimpanan pada stack ƒ pushl Src Alamat Bertambah B Besar

ƒ Src adalah fetch operand ƒ %esp berkurang 4 ƒ Menyimpan operand pada alamat yang ditentukan oleh register %esp

Stack Pointer %esp

Stack Bertambah Ke Bawah -4

Stack “Paling Atas” 4

Pop Stack Stack “Paling Bawah”

Membaca dari stack ƒ popl Dest Alamat Bertambah B Besar

ƒ Membaca operand dari alamat yang ditentukan oleh %esp ƒ %esp bertambah 4 ƒ Disimpan ke Dest Stack Pointer %esp

+4

Stack Bertambah Ke Bawah

Stack “Paling Paling Atas Atas” 5

Contoh Operasi Stack pushl %eax

123

popl %edx

0x110

0x110

0x10c

0x10c

0x108

123

0x108

123

0x104

213

0x104

213

213

%eax

213

%eax

213

555

%edx

555

%edx

555 213

0x108

%esp

0x108 0x104

%esp

0x104 0x108

6

Aliran Kontrol Prosedur gg Prosedur call dan return menggunakan stack Prosedur call : ƒ Call label

Push return address ke stack; Jump ke label

Nil i return Nilai t address dd ƒ Alamat ketika instruksi call dipanggil ƒ Contoh dari disassemblyy 804854e : e8 3d 06 00 00 8048553 : 50

call 8048b90 <main> pushl eax

ƒ Return etu address add ess = 0 0x8048553 80 8553

Prosedur return : ƒ Ret

Pop alamat dari stack; Jump ke alamat tsb

7

Contoh Prosedur Call 804854e: 8048553:

e8 3d 06 00 00 50 call

call pushl

8048b90 <main> %eax

8048b90

0x110 0x10c 123

0x108

123

0x104 0x8048553 0x108

%esp

0x804854e

0x108 0x104

%eip p 0x8048b90 0x804854e

%eip adalah program counter 8

Contoh Prosedur Return 8048591:

c3

ret ret

0x110

0x110

0x10c

0x10c

0x108

123

0x108

0x104 0x8048553 %esp

0x104

%eip 0x8048591

123 0x8048553

%esp

0x104 0x108

%eip 0x8048553 0x8048591

%eip adalah program counter 9

Contoh Rangkaian Call Struktur Kode j ( ) ji(…) { • • sam(); () • • }

Urutan Call ji

sam(…) { • • • soe(); • • • soe(); • • • }

ƒ Prosedur soe adalah prosedur rekursi

sam soe soe(…) { • • soe(); • • }

soe

soe

soe

10

Stack Frame p stack frame Setiap berisi:

ji j sam

ƒ Variabel lokal ƒ Informasi return ƒ Temporary space

soe

Frame Pointer %ebp proc Stack Pointer %esp

Stack Top “Top” 11

Operasi Stack ji(…) { • • sam(); • • }

Urutan Call ji

Frame Pointer %ebp

• • • ji j

Stack Pointer %esp

12

Operasi Stack sam(…) { • • • soe(); • • • soe(); • • • }

• • •

Urutan Call ji

Frame F Pointer %ebp

ji j

sam sam

Stack Pointer %esp

13

Operasi Stack soe(…) { • • soe(); () • • }

• • •

Urutan Call

ji j

ji sam

Frame Pointer %ebp

sam

soe

soe Stack St k Pointer %esp

14

Operasi Stack soe(…) { • • soe(); () • • }

• • •

Urutan Call

ji j

ji sam sam soe soe

Frame Pointer %ebp

soe

soe Stack Pointer %esp

15

Operasi Stack soe(…) { • • soe(); () • • }

• • •

Urutan Call

ji j

ji sam sam soe

soe soe soe

Frame Pointer %ebp

soe

soe Stack Pointer %esp 16

Operasi Stack soe(…) { • • soe(); () • • }

• • •

Urutan Call

ji j

ji sam sam soe soe

Frame Pointer %ebp

soe

soe soe

Stack Pointer %esp

17

Operasi Stack soe(…) { • • soe(); () • • }

• • •

Urutan Call

ji j

ji sam

Frame Pointer %ebp

soe

soe soe

sam

Stack St k Pointer %esp

soe

18

Operasi Stack sam(…) { • • • soe(); • • • soe(); • • • }

• • •

Urutan Call ji

Frame F Pointer %ebp

ji j

sam sam soe

Stack Pointer %esp

soe soe

19

Operasi Stack soe(…) { • • • • }

• • •

Urutan Call

ji j

ji Frame Pointer %ebp

sam soe soe

sam

soe

soe Stack St k Pointer %esp

soe

20

Operasi Stack sam(…) { • • • soe(); • • • soe(); • • • }

• • •

Urutan Call Frame F Pointer %ebp

ji

ji j

sam sam soe

soe

Stack Pointer %esp

soe soe

21

Operasi Stack Urutan Call ji(…) { • • sam(); () • • }

Frame Pointer %ebp

• • • ji j

Stack Pointer %esp

ji sam soe

soe

soe soe

22

Stack Frame IA32/Linux Stack Frame terdiri dari: ƒ Parameter fungsi yang hendak dipanggil ƒ “Argument build”

Caller Frame Arguments

ƒ Variabel lokal ƒ Yang tidak dapat disimpan dalam register

ƒ Saved register ƒ Frame pointer sebelumnya Pemanggil Stack Frame ƒ Return address

Frame Pointer (%ebp)

Return Addr Old %ebp Saved Registers + L Local l Variables

ƒ Di-push oleh instruksi call

ƒ Argument pemanggil Stack Pointer (%esp)

Argument Build 23

Bahasa Berbasis Stack a asa ya g mendukung e du u g Rekursi e us Bahasa yang ƒ Contoh : C, Pascal, Java ƒ Kode harus “Reentrant” ƒ Perlu tempat untuk menyimpan kondisi setiap: ƒ Arguments ƒ Local variables ƒ Return pointer

Stack dialokasikan dalam frame-frame

24

Fungsi Swap int zip1 = 15213; int zip2 = 91125; void call_swap() { swap(&zip1 &zip2); swap(&zip1, }

void swap(int *xp, int *yp) { int t0 = *xp; xp; int t1 = *yp; *xp = t1; *yp = t0; }

Memanggil swap dari call_swap call_swap: call swap: • • • pushl $zip2 pushl $zip1 call swap • • • • • •

# Global Var # Global Var

Stack diperoleh

&zip2 &zip1 Rtn adr

%esp 25

Fungsi Swap

void swap(int *xp, int *yp) { int t0 = *xp; int t1 = *yp; *xp = t1; *yp yp = t0; }

swap: pushl %ebp movl %esp,%ebp pushl %ebx movl movl movl movl l movl movl

12(%ebp),%ecx 8(%ebp),%edx (%ecx),%eax (%edx),%ebx % %eax,(%edx) (% d ) %ebx,(%ecx)

movl -4(%ebp),%ebx ( p), movl %ebp,%esp popl %ebp ret

Set Up

Body

Finish

26

Swap Setup - 1 Masuk Stack

Stack diperoleh %ebp

% b %ebp

• • •

• • •

&zip2

yp

&zip1 p

xp p

Rtn adr

%esp

Rtn adr Old %ebp

%esp

swap: pushl %ebp movl %esp %esp,%ebp %ebp pushl %ebx 27

Swap Setup - 2 Masuk Stack

Stack diperoleh %ebp

• • •

• • •

&zip2

yp

&zip1 p

xp p

Rtn adr

%esp

Rtn adr Old %ebp

%ebp %esp

swap: pushl %ebp movl %esp %esp,%ebp %ebp pushl %ebx 28

Swap Setup - 3 Masuk Stack

Stack diperoleh %ebp

• • •

• • •

&zip2

yp

&zip1 p

xp p

Rtn adr

%esp

Rtn adr Old %ebp

%ebp

O %ebx Old

%esp

swap: pushl %ebp movl %esp %esp,%ebp %ebp pushl %ebx 29

Pengaruh Swap Setup Stack diperoleh p

%ebp • • •

Offset (relatif thd %ebp)

• • •

&zip2

12

yp

&zip1 p

8

xp p

4

Rtn adr

Rtn adr

%esp

movl 12(%ebp),%ecx # get yp movl 8(%ebp),%edx ( p), # g get xp p . . .

0 Old %ebp

%ebp

Old %ebx

%esp

Body y

30

Swap Finish - 1 Stack swap

• • •

Offset

Offset

• • •

12

yp

12

yp

8

xp

8

xp

4

Rtn adr

4

Rtn adr

0 Old %ebp

%ebp

0 Old %ebp

%ebp

-4 Old %ebx

%esp

-4 Old %ebx

%esp

Penjelasan : ƒ Menyimpan dan me-restore me restore register %ebx

movl -4(%ebp),%ebx movl %ebp,%esp popl %ebp ret 31

Swap Finish - 2 Stack swap Offset

Stack swap

• • •

Offset

• • •

12

yp

12

yp

8

xp

8

xp

4

Rtn adr

4

Rtn adr

0 Old %ebp

%ebp

-4 Old %ebx

%esp

0 Old %ebp

%ebp %esp

movl -4(%ebp),%ebx movl %ebp,%esp popl %ebp ret 32

Swap Finish - 3 Stack swap Offset

Stack swap

• • •

%ebp

Offset

• • •

12

yp

12

yp

8

xp

8

xp

4

Rtn adr

4

Rtn adr

0 Old %ebp

%ebp

0

%esp

%esp movl -4(%ebp),%ebx movl %ebp,%esp popl %ebp ret 33

Swap Finish - 4 %ebp

Stack swap

%ebp

• • •

• • •

12

yp

&zip2

8

xp

&zip1

4

Rtn adr

Offset

%esp

%esp

Penjelasan : ƒ Menyimpan dan me-restore register %ebx ƒ Tid Tidakk dilakukan dil k k pada d register i t %eax, %ecx, %edx

movl -4(%ebp),%ebx movl %ebp,%esp popl %ebp ret 34

Aturan Penyimpanan Register Ketika prosedur yoo memanggil who: ƒ yoo adalah pemanggil (caller), who yang dipanggil (callee)

Dapatkan register digunakan sebagai penyimpan sementara se e ta a ? yoo: • • • movl $15213 $15213, %edx call who addl %edx, %eax • • • ret

who: • • • movl 8(%ebp), %edx addl $91125, %edx • • • ret

ƒ Isi register %edx ditimpa oleh who

35

Aturan Penyimpanan Register Ketika prosedur yoo memanggil who: ƒ yoo adalah pemanggil (caller), who yang dipanggil (callee)

Dapatkan register digunakan sebagai penyimpan sementara ? Konvensi : ƒ “Caller Save” ƒ Caller menyimpan nilai sementara dalam frame sebelum melakukan pemanggilan

ƒ “Callee Save” ƒ Callee menyimpan nilai sementara sebelum register digunakan

36

Penggunaan Register IA32/Linux Register integer ƒ Penggunaan khusus %ebp, %esp

%eax Register Caller-Save

ƒ callee-save : %ebx, %esi, %edi ƒ Nilai sebelumnya disimpan dalam stack sebelum register digunakan

%ecx %ebx Register Callee-Save

%esi %edi

ƒ caller-save : %eax, %edx, %ecx ƒ Dapat dilakukan apa saja.

%edx

Register kh khusus

%esp %ebp

ƒ Register %eax juga menyimpan return value 37

Recursive Factorial int rfact(int x) { int rval; if (x <= 1) return 1; rval = rfact(x-1); return rval * x; }

Registers ƒ %eax digunakan tanpa disimpan lebih dahulu dah l ƒ %ebx digunakan, tetapi disimpan dahulu diawal dan dikembalikan lagi di akhir

.globl rfact .type rfact,@function , rfact: pushl %ebp movl %esp,%ebp pushl %ebx movl 8(%ebp),%ebx cmpl $1,%ebx jle .L78 leal -1(%ebx),%eax pushl %eax call rfact imull %ebx %eax %ebx,%eax jmp .L79 .align 4 .L78: movl $1,%eax .L79: movl -4(%ebp),%ebx movl %ebp,%esp popl %ebp ret 38

rfact - Stack Setup pre %ebp

%ebp

pre %ebx

Masuk stack

Caller

x %esp

Rtn adr

rfact: pushl %ebp movl %esp,%ebp pushl %ebx

pre %ebp Caller

Callee

pre %ebx 8

x

4

Rtn adr

0 Old %ebp

%ebp

-4 4 Old %ebx

%esp 39

Rfact Body

Recursion

int rfact(int x) { int rval; ; if (x <= 1) return 1; rval = rfact(x-1) ; return rval * x; }

movl mo l 8(%ebp) 8(%ebp),%ebx %eb cmpl $1,%ebx jle .L78 leal -1(%ebx),%eax pushl %eax call rfact imull %ebx,%eax jmp .L79 L79 .L78: # movl $1,%eax .L79: #

# eb ebx = x # Compare x : 1 # If <= goto Term # eax = x-1 # Push x-1 # rfact(x-1) # rval * x # Goto done Term: # return val = 1 Done:

Registers %ebx menyimpan nilai x % %eax ƒ Nilai sementara x-1 ƒ Return value dari rfact(x-1) ƒ Return R value l fungsi f i ini i i 40

rfact - Rekursi leal -1(%ebx),%eax pushl %eax

x Rtn adr

x

Old %ebp

%ebp

Rtn adr

Old %ebx

%esp

Old %ebp

call rfact %ebp

Rtn adr

Old %ebx x-1

x

%esp

Old %ebp

%ebp

Old %ebx %eax

x-1

%ebx

x

x-1 %eax

x-1

%ebx

x

Rtn adr %eax

x-1

%ebx

x

%esp

41

rfact - Hasil imull %ebx,%eax

Kembali dari call x

x

Rtn adr

Rtn adr

Old %ebp % b

% b %ebp

Old %ebp % b

Old %ebx x-1

% b %ebp

Old %ebx x-1

%esp p

%eax

(x-1)! (x 1)!

%eax

(x-1)! (x x! 1)!

%ebx

x

%ebx

x

%esp p

Diasumsikan rfact(x-1) mengembalikan (x-1)! dalam register %eax 42

rfact - Akhir mo l -4(%ebp),%ebx movl 4(%ebp) %eb movl %ebp,%esp popl %ebp ret

pre %ebp pre %ebx 8

x

pre %ebp

4

Rtn adr

pre %ebx

pre %ebp

8

x

pre %ebx

4

Rtn adr

x

0 Old %ebp

%ebp

-4 Old %ebx -8

x-1

%eax

x!

% b Old x %ebx % b %ebx

%esp p

0 Old %ebp

%eax

%ebp p %esp

Rtn adr

%ebp

%esp

x!

%ebx Old %ebx

%eax

x!

%ebx Old %ebx

43

Kode Pointer Prosedur Rekursif void s_helper (int x, int *accum) { if (x <= 1) return; else { i t z = * int *accum * x; *accum = z; s_helper (x-1,accum); } }

Top Le el Call Top-Level int sfact(int x) { int val = 1; s_helper(x, &val); return val; }

ƒ Melewatkan M l tk pointer i t untuk t k meng-update d t llokasi k i 44

Membuat dan Inisialisasi Pointer bagian inisialisasi sfact _sfact: sfact: pushl %ebp movl %esp,%ebp subl $16,%esp movl 8( 8(%ebp),%edx ) movl $1,-4(%ebp)

# # # # #

Save %ebp Set %ebp Add 16 bytes edx = x val = 1

Menggunakan gg stack untuk variabel lokal

8

x

4

Rtn adr

0 Old %ebp p -4 val = 1 -8 -12 12

Temp. USpaced Unused

ƒ Variabel val harus disimpan dalam stack

-16

ƒ Perlu membuat pointer

int sfact(int x) { int val = 1; s_helper(x, &val); return val; }

ƒ Perhitungan pointer -4(%ebp) ƒ Push stack sebagai argumen k d kedua

%ebp

%esp

45

Passing Pointer Memanggil s_helper dari sfact leal -4(%ebp),%eax pushl %eax pushl %edx p call s_helper movl -4(%ebp),%eax • • •

# # # # # #

Compute &val Push on stack Push x call Return val Finish

Stack pada waktu call 8

x

4

Rtn adr

0 Old %ebp % b -4 val =x! = 1 -8 -12

int sfact(int x) { int val = 1; s_helper(x, &val); return val; }

% b %ebp

Unused

-16 &val x

%esp

46

Menggunakan Pointer void s_helper (int x, int *accum) { • • • int z = *accum * x; *accum = z; • • • }

accum*x accum %eax

accum*x x

%ecx

x

%edx

• • • movl %ecx,%eax # z = x imull (%edx),%eax # z *= *accum movl %eax,(%edx) # *accum = z • • •

ƒ Register %ecx menyimpan x ƒ Register %edx menyimpan pointer ke accum ƒ Menggunakan akses (%edx) untuk referensi memori 47

Kesimpulan Stack dapat membuat rekursi bekerja ƒ Penyimpanan privat untuk setiap pemanggilan prosedur ƒ Tidak saling mengganggu satu sama lain ƒ Pengalamatan variabel lokal dan argumen relatif terhadap posisi stack t k

ƒ Dapat dikelola dengan stack ƒ Prosedur return dalam urutan call terbalik

K bi Kombinasi i instruksi i t k i dan d aturan t dalam d l prosedur d IA32 ƒ Instruksi Call / Ret ƒ Aturan penggunaan register ƒ Caller / Callee save ƒ %ebp dan %esp

ƒ Aturan pengelolaan stack frame

48