CS:APP第四章作业

发表于 分类于 ， ，

CS:APP第四章作业

4.45

(a) 不正确，当REG 表示 %rsp 时，因为先执行了 subq $8, %rsp，相当于把 %rsp 的指针已经动掉了，无法访问到应该被复制的东西，指令错误。

(b)

1
2
movq %rsp -8(%rsp)
subq $8 %rsp

4.47

image-20251210135010162

(a)

1
2
3
4
5
6
7
8
9
10
11
12
void bubble_sort(long* data, long* right) {
    long *i, *last;
    for (last = right; last != data; last--) {
        for (i = data; i != last; i++) {
            if (*(i + 1) < *i) {
                long t = *(i + 1);
                *(i + 1) = *i;
                *i = t;
            }
        }
    }
}

(b)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
bubble_sort:
    irmovq $1, %r8
    subq   %r8, %rsi
    addq   %rsi, %rsi
    addq   %rsi, %rsi
    addq   %rsi, %rsi 
    addq   %rdi, %rsi     # %rsi 存的是right
L1:
    rrmovq %rdi, %rax     # i = data
L2:
    rrmovq %rsi, %r10
    subq   %rax, %r10
    je     L4
    mrmovq (%rax), %r11   # *i
    mrmovq 8(%rax), %r12  # *(i+1)
    rrmovq %r12, %r9
    subq   %r11, %r9
    jge    L3
    rmmovq %r12, (%rax)
    rmmovq %r11, 8(%rax)
L3:
    irmovq $8, %r13
    addq   %r13, %rax
    jmp    L2
L4:
    irmovq $8, %r13
    subq   %r13, %rsi
    rrmovq %rsi, %r10
    subq   %rdi, %r10
    jg     L1
    ret

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Chapter4-YAS/sim/y86-code
❯ ../misc/yis bubble.yo
Stopped in 254 steps at PC = 0x13.  Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax:   0x0000000000000000      0x0000000000000020
%rsp:   0x0000000000000000      0x0000000000000200
%rsi:   0x0000000000000000      0x0000000000000018
%rdi:   0x0000000000000000      0x0000000000000018
%r8:    0x0000000000000000      0x0000000000000001
%r9:    0x0000000000000000      0xffffffffffffffff
%r11:   0x0000000000000000      0x0000000000000002
%r12:   0x0000000000000000      0x0000000000000001
%r13:   0x0000000000000000      0x0000000000000008

Changes to memory:
0x0018: 0x0000000000000006      0x0000000000000001
0x0020: 0x0000000000000005      0x0000000000000002
0x0028: 0x0000000000000004      0x0000000000000003
0x0030: 0x0000000000000003      0x0000000000000004
0x0038: 0x0000000000000002      0x0000000000000005
0x0040: 0x0000000000000001      0x0000000000000006
0x01f0: 0x0000000000000000      0x0000000000000065
0x01f8: 0x0000000000000000      0x0000000000000013

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
.pos 0
    irmovq stack, %rsp
    call main
    halt

    .align 8
Array:
    .quad 0x06
    .quad 0x05
    .quad 0x04
    .quad 0x03
    .quad 0x02
    .quad 0x01

main:
    irmovq Array, %rdi
    irmovq $6, %rsi
    call bubble_sort
    ret

bubble_sort:
    irmovq $1, %r8
    subq   %r8, %rsi
    addq   %rsi, %rsi
    addq   %rsi, %rsi
    addq   %rsi, %rsi
    addq   %rdi, %rsi
L1:
    rrmovq %rdi, %rax
L2:
    rrmovq %rsi, %r10
    subq   %rax, %r10
    je     L4
    mrmovq (%rax), %r11
    mrmovq 8(%rax), %r12
    rrmovq %r12, %r9
    subq   %r11, %r9
    jge    L3
    rmmovq %r12, (%rax)
    rmmovq %r11, 8(%rax)
L3:
    irmovq $8, %r13
    addq   %r13, %rax
    jmp    L2
L4:
    irmovq $8, %r13
    subq   %r13, %rsi
    rrmovq %rsi, %r10
    subq   %rdi, %r10
    jg     L1
    ret

    .pos 0x200
stack:

4.51

阶段 iaddq V, rB 解释
取指 icode:ifun ← M1[PC] rA:rB ← M1[PC+1] valC ← M8[PC+2] valP ← PC + 10 取出指令、寄存器ID和立即数，PC增加10字节。
译码 valB ← R[rB] 读出寄存器 rB 的旧值作为被加数。
执行 valE ← valB + valC Set CC ALU 计算 rB的值 + 立即数，并更新条件码。
访存 无内存访问。
写回 R[rB] ← valE 将加法结果写回寄存器 rB。
更新PC PC ← valP 更新程序计数器。