x86 程序集：递归函数的序言弄乱了参数
x86 Assembly: Prologue of recursive function messes up parameters
我正在尝试通过 x86 汇编中的递归实现 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)
然而，在 maximizeItemUsage 处执行的代码中，我执行了以下递归调用：
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 , %esp
movl [=15=], do_not_use(%ebp)
movl [=15=], 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 [=15=], num_items(%ebp)
jle emptyBag
cmpl [=15=], 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 , %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 , %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
# 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 , %esp
movl [=10=], do_not_use(%ebp)
movl [=10=], use(%ebp)
评论声称为3个变量（12字节）保留space，但代码只有sub , %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 , %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
在 analyzePreviousItems 中，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 变量即将终止。
我正在尝试通过 x86 汇编中的递归实现 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)
然而，在 maximizeItemUsage 处执行的代码中，我执行了以下递归调用：
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 , %esp
movl [=15=], do_not_use(%ebp)
movl [=15=], 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 [=15=], num_items(%ebp)
jle emptyBag
cmpl [=15=], 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 , %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 , %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
# 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 , %esp movl [=10=], do_not_use(%ebp) movl [=10=], use(%ebp)
评论声称为3个变量（12字节）保留space，但代码只有sub , %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 , %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
在 analyzePreviousItems 中，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 变量即将终止。