x86 Assembly: Prologue of recursive function messes up parameters

Question

I am trying to implement Knapsack's algorithm through recursion in x86 Assembly, modeling the following Java code. However, when I run my program, it seems as if the parameter taking in the capacity of the bag (the 4th parameter) is changed following a recursive call (specifically following the prologue).

The initial call is:

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

When I look in the debugger, initially all the parameters are taken in as correctly:

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)

However, in the code executed at maximizeItemUsage, I execute the following recursive call:

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

However, when I look at my debugger, after the following line of code in the prologue (in knapsack):

mov %esp, %ebp

I get the following data in the parameters:

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

This seems quite strange, considering that the prologue is to supposed to align the stack properly. Below is my code:

# 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

Sep Roland · Accepted Answer

# 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)

The comments claim to reserve space for 3 variables (12 bytes) but the code only has 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

In all 3 recursive calls you have pushed the arguments in the wrong order!
This is the correct way:

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

In the 2nd recursive call, you have 1 argument too few! Why is there a 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

Please note that the code below the jmp maximizeItemUsage is unreachable. It will never run.

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

In analyzePreviousItems that movl %eax, do_not_use(%ebp) instruction is silly because the concerned local variable is just about to stop existing.

And an optimization for free

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

This part of your code gets much simpler if you don't reload the use variable to a different register when it is already present in %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

(*) Here also you don't need to store movl %eax, use(%ebp) because the use variable is about to get terminated.

x86 Assembly: Prologue of recursive function messes up parameters

Answers (1)

And an optimization for free

Related Questions