Warm tip: This article is reproduced from serverfault.com, please click

recursion-x86汇编:递归函数的序幕弄乱了参数

(recursion - x86 Assembly: Prologue of recursive function messes up parameters)

发布于 2020-11-29 10:36:18

我正在尝试通过x86 Assembly中的递归实现Knapsack的算法,对以下Java代码进行建模。但是,当我运行程序时,似乎在递归调用之后(特别是在序言之后)更改了容纳包容量的参数(第4个参数)。

最初的电话是:

knapsack(weights, values, 2, 2, 0)

当我查看调试器时,最初所有参数都是正确输入的:

weights is the pointer to the correct array (0x5655b2f0) ($ebp + 8)
values is the pointer to the correct array (0x5655b300) ($ebp + 12)
num_items = 2 ($ebp + 16)
capacity = 2 ($ebp + 20)
cur_value = 0 ($ebp + 24)

但是,在maximumItemUsage执行的代码中,我执行以下递归调用:

knapsack(weights, values, 2, 1, 0)

但是,当我查看调试器时,在序言中的以下代码行之后(在背包中):

mov %esp, %ebp

我在参数中得到以下数据:

0 ($ebp + 8)
2 ($ebp + 12)
1 ($ebp + 16)
0x5655b300 ($ebp + 20)
0x5655b2f0 ($ebp + 24)

考虑到序言应该正确对齐堆栈,这似乎很奇怪。下面是我的代码:

# Function signature:
# int knapsack(int* w, int* v, int num_items,
#                       int capacity, int current);

.text
    # Define our macros, which store the location of the parameters and values
    # relative to the stack's base pointer (EBP)
    .equ weights, 8
    .equ values, 12
    .equ num_items, 16
    .equ capacity, 20
    .equ cur_value, 24

    .equ do_not_use, -4
    .equ use, -8

.global knapsack
knapsack:

    # solves the knapsack problem
    # @weights: an array containing how much each item weighs
    # @values: an array containing the value of each item
    # @num_items: how many items that we have
    # @capacity: the maximum amount of weight that can be carried
    # @cur_weight: the current weight
    # @cur_value: the current value of the items in the pack

    # Prologue (prepare the stack frame)
    push %ebp
    mov %esp, %ebp

    # Make space for local variables on the stack
    # 3 variables (4 bytes each)
    # Default values are 0
    #
    # 1. the value of the bag if we DO NOT use the current item
    # 2. the value of the bag if we USE the current item
    # 3. the maximum value of the bag currently
    sub $8, %esp
    movl $0, do_not_use(%ebp)
    movl $0, use(%ebp)

    # Base Case: we have utilized all the items or there is no more space left
    # in the bag (num_items = 0 or capacity = 0)
    cmpl $0, num_items(%ebp)
    jle emptyBag

    cmpl $0, capacity(%ebp)
    jle emptyBag

    # Case 1: We do not use the current element because adding it wil surpass capacity
    # weights[n - 1] > capacity
    # Push the new parameters in the stack (everything stays the same, except that
    # n -> n - 1 since we are no longer using the current element)

    # Compute weights[n - 1] (stored in ECX register)
    # Get the memory address of the values array
    movl weights(%ebp), %ecx

    # Move to the memory address of weights[n - 1]
    push %edx
    movl num_items(%ebp), %edx # num_items
    decl %edx # num_items - 1
    imul $4, %edx # 4(num_items - 1)
    addl %edx, %ecx # m_v + 4(num_items - 1)

    # Get the actual value of weights[n - 1]
    movl (%ecx), %ecx # Get value at address m_w + 4(num_items - 1)
    pop %edx

    # If weights[n - 1] > capacity
    cmpl %ecx, capacity(%ebp)
    # Shift to analyzing the previous items
    jl analyzePreviousItems

    # Case 2: We can use the current element (in this case, find the maximum of the values
    # we use the element or if we do not use the element
    jmp maximizeItemUsage

    # Solidify the EAX register data
    movl %eax, %eax

    # Epilogue (cleanup the stack frame)
    mov %ebp, %esp
    pop %ebp

    # Return the maximum possible weight of the bags :D
    ret

maximizeItemUsage:
    # knapsack(weights, values, num_items - 1, capacity, current_value)
    # All parameters remain the same (except that n > n - 1)
    push weights(%ebp)
    push values(%ebp)

    # num_items - 1
    movl num_items(%ebp), %edx
    decl %edx
    push %edx

    push capacity(%ebp)
    push cur_value(%ebp)

    # Call knapsack(weights, values, num_items - 1, capacity, cur_value)
    call knapsack

    # The value if we DO NOT use the current item
    movl %eax, do_not_use(%ebp)

    # knapsack(weights, values, n - 1, c - weights[n]) + values[n]
    # All parameters remain the same (except that n > n - 1 and c > c - weights[n])
    push weights(%ebp)
    push values(%ebp)

    # num_items - 1
    movl num_items(%ebp), %edx
    decl %edx

    # capacity - weights[n] (stored in the ECX register)
    # Get the memory address of the values array
    movl weights(%ebp), %ecx

    # Move to the memory address of weights[n]
    push %edx
    movl num_items(%ebp), %edx # num_items
    imul $4, %edx # 4(num_items)
    addl %edx, %ecx # m_w + 4(num_items)

    # Restore the value of the EDX register
    pop %edx

    # Get the actual value of weights[n]
    movl (%ecx), %ecx # Get value at address m_w + 4(num_items)

    # -weights[n]
    neg %ecx

    # capacity - weights[n]
    addl capacity(%ebp), %ecx
    push %ecx

    push cur_value(%ebp)

    # Call knapsack(weights, values, num_items - 1, capacity - weights[n], cur_value)
    call knapsack

    # The value if we USE the current item
    movl %eax, use(%ebp)

    # Compute the maximum value of knapsack(weights, values, num_items - 1, capacity, cur_value)
    # and knapsack(weights, values, n - 1, c - weights[n]) + values[n]
    movl use(%ebp), %ecx
    cmpl %ecx, do_not_use(%ebp)
    jl setUseAsMax
    movl do_not_use(%ebp), %eax

    # Epilogue (cleanup the stack frame)
    mov %ebp, %esp
    pop %ebp

    ret

setUseAsMax:
    movl use(%ebp), %eax

    # Epilogue (cleanup the stack frame)
    mov %ebp, %esp
    pop %ebp

    ret

analyzePreviousItems:
    # Recursive Call 1: knapsack(weights, values, n - 1, c)
    # All parameters remain the same (except that n -> n - 1)
    push weights(%ebp)
    push values(%ebp)

    # We use the EDX to contain the changed parameters since it is a
    # non-volatile register
    movl num_items(%ebp), %edx
    decl %edx
    push %edx

    push capacity(%ebp)
    push cur_value(%ebp)

    # Call knapsack(weights, values, num_items - 1, capacity, cur_value)
    call knapsack

    # The value if we DO NOT use the current item
    movl %eax, do_not_use(%ebp)

    # Epilogue (cleanup the stack frame)
    mov %ebp, %esp
    pop %ebp

    # Return knapsack(weights, values, n - 1, c)
    ret

emptyBag:
    movl 0, %eax

    # Epilogue (cleanup/realign the stack frame)
    mov %ebp, %esp
    pop %ebp

    # Return 0
    ret
Questioner
Adam Lee
Viewed
11
Sep Roland 2020-11-30 03:40:09
# 3 variables (4 bytes each)
# Default values are 0
#
# 1. the value of the bag if we DO NOT use the current item
# 2. the value of the bag if we USE the current item
# 3. the maximum value of the bag currently
sub $8, %esp
movl $0, do_not_use(%ebp)
movl $0, use(%ebp)

注释声称保留3个变量(12个字节)的空间,但是代码仅具有sub $8, %esp


push weights(%ebp)
push values(%ebp)

# num_items - 1
movl num_items(%ebp), %edx
decl %edx
push %edx

push capacity(%ebp)
push cur_value(%ebp)

# Call knapsack(weights, values, num_items - 1, capacity, cur_value)
call knapsack

在所有3个递归调用中,你以错误的顺序推送了参数!
这是正确的方法:

push cur_value(%ebp)
push capacity(%ebp)
movl num_items(%ebp), %edx
decl %edx
push %edx
push values(%ebp)
push weights(%ebp)
call knapsack

push %edx
movl num_items(%ebp), %edx # num_items
imul $4, %edx # 4(num_items)
addl %edx, %ecx # m_w + 4(num_items)

# Restore the value of the EDX register
pop %edx

在第二个递归调用中,你的1个参数太少了!为什么会有pop %edx


# Case 2: We can use the current element (in this case, find the maximum of the values
# we use the element or if we do not use the element
jmp maximizeItemUsage

# Solidify the EAX register data
movl %eax, %eax

# Epilogue (cleanup the stack frame)
mov %ebp, %esp
pop %ebp

# Return the maximum possible weight of the bags :D
ret

请注意,下面的代码jmp maximizeItemUsage无法访问。它永远不会运行。


call knapsack                   # -> %EAX

# The value if we DO NOT use the current item
movl %eax, do_not_use(%ebp)

# Epilogue (cleanup the stack frame)
mov %ebp, %esp
pop %ebp

# Return knapsack(weights, values, n - 1, c)
ret

analyzerPreviousItems中,该movl %eax, do_not_use(%ebp)指令很愚蠢,因为相关的局部变量即将停止存在。

以及免费的优化

call knapsack

# The value if we USE the current item
movl %eax, use(%ebp)

# Compute the maximum value of knapsack(weights, values, num_items - 1, capacity, cur_value)
# and knapsack(weights, values, n - 1, c - weights[n]) + values[n]
movl use(%ebp), %ecx
cmpl %ecx, do_not_use(%ebp)
jl setUseAsMax
movl do_not_use(%ebp), %eax

# Epilogue (cleanup the stack frame)
mov %ebp, %esp
pop %ebp

ret

setUseAsMax:
movl use(%ebp), %eax

# Epilogue (cleanup the stack frame)
mov %ebp, %esp
pop %ebp

ret

如果你没有将use变量重新存在于中的其他寄存器中,则这部分代码会变得更加简单%EAX

    call knapsack
    movl %eax, use(%ebp)              (*)
    cmpl %eax, do_not_use(%ebp)
    jl setUseAsMax
    movl do_not_use(%ebp), %eax
setUseAsMax:
    mov %ebp, %esp
    pop %ebp
    ret

(*)这里也不需要存储,movl %eax, use(%ebp)因为use变量即将终止。