Y86架构冒泡排序程序排序异常问题排查与修正咨询
2026-7-23
Y86冒泡排序代码错误分析与修正
问题背景
将C语言冒泡排序转换为Y86汇编时，处理10个元素的数组无法正确排序，但元素数量少于5个时排序正常。
原始C代码
void bubbleSort2(long arr[], long len) { long i; // inner loop index long tmp; // temp for swapping long *arr_curr; // pointer to element in arr long *arr_next; // pointer to next element in arr while (len > 1) { arr_curr = arr; // begin at the start of arr i = 0; while (i < len-1) { arr_next = arr_curr + 1; // set next pointer if (*arr_curr > *arr_next) { // Swap the two elements // to bubble up the larger value tmp = *arr_curr; *arr_curr = *arr_next; *arr_next = tmp; } i++; arr_curr = arr_next; // move to the next element } len--; } }
现有Y86汇编代码
# Execution begins at address 0 .pos 0 irmovq stack, %rsp # Set up stack pointer call main # Execute main program halt # Terminate program # Array .align 8 arr: .quad 0x64 .quad 0x34 .quad 0x40 .quad 0x25 .quad 0x12 .quad 0x22 .quad 0x11 .quad 0x90 .quad 0x55 .quad 0x42 main: irmovq arr, %rdi irmovq $10, %rsi call bubble ret # start bubble bubble: irmovq $1, %rax outer_loop: rrmovq %rsi, %r8 subq %rax, %r8 irmovq $1, %r9 irmovq $0, %rcx inner_loop: rrmovq %rdi, %r10 addq %rcx, %r10 mrmovq (%r10), %r11 mrmovq 8(%r10), %r12 subq %r12, %r11 jle no_swap subq %r11, %r12 je no_swap jg swap swap: mrmovq (%r10), %r11 mrmovq 8(%r10), %r12 rmmovq %r11, 8(%r10) rmmovq %r12, (%r10) no_swap: irmovq $8, %r13 addq %r13, %rcx subq %rax, %r8 jg inner_loop rrmovq %rdi, %r10 subq %rax, %r8 jg outer_loop ret # end bubble # The stack starts here and grows to lower addresses .pos 0x200 stack:
运行后内存变化结果
Changes to memory: 0x0018: 0x0000000000000064 0x0000000000000034 0x0020: 0x0000000000000034 0x0000000000000040 0x0028: 0x0000000000000040 0x0000000000000025 0x0030: 0x0000000000000025 0x0000000000000012 0x0038: 0x0000000000000012 0x0000000000000022 0x0040: 0x0000000000000022 0x0000000000000011 0x0048: 0x0000000000000011 0x0000000000000064 0x0050: 0x0000000000000090 0x0000000000000055 0x0058: 0x0000000000000055 0x0000000000000042 0x0060: 0x0000000000000042 0x0000000000000090 0x01f0: 0x0000000000000000 0x0000000000000085 0x01f8: 0x0000000000000000 0x0000000000000013
错误原因
- 内外层循环终止逻辑混乱：
现有代码用r8同时控制内外层循环的终止，每次内层循环都会修改r8的值，导致循环次数计算完全偏离C代码逻辑。原C代码中内层循环是i < len-1，外层循环是len > 1，两者逻辑独立，不能共用同一个寄存器判断。 - 冗余比较操作：
subq %r11, %r12和je no_swap属于重复判断，之前的subq %r12, %r11和jle no_swap已经覆盖了*arr_curr <= *arr_next的所有情况（包括相等）。 - Swap操作重复读取内存：
进入swap块后再次执行mrmovq读取同一地址，完全可以复用之前已经读取到r11和r12的值，既浪费周期又容易出错。
修正后的Y86汇编代码
# Execution begins at address 0 .pos 0 irmovq stack, %rsp # Set up stack pointer call main # Execute main program halt # Terminate program # Array .align 8 arr: .quad 0x64 .quad 0x34 .quad 0x40 .quad 0x25 .quad 0x12 .quad 0x22 .quad 0x11 .quad 0x90 .quad 0x55 .quad 0x42 main: irmovq arr, %rdi irmovq $10, %rsi call bubble ret # start bubble bubble: # 保存调用者寄存器（Y86调用约定：rdi、rsi为调用者保存，需自行保存） pushq %rdi pushq %rsi outer_loop: # 恢复len和数组基地址，判断外层循环条件：len > 1 popq %rsi popq %rdi irmovq $1, %r8 cmpq %r8, %rsi jle bubble_end # len <=1，退出外层循环 # 保存当前len和基地址，准备内层循环 pushq %rdi pushq %rsi irmovq $0, %rcx # i=0，对应字节偏移量初始为0 subq %r8, %rsi # 计算len-1，用于内层循环终止判断 irmovq $8, %r9 mulq %r9, %rsi # 转换为字节偏移：(len-1)*8，即内层循环的最大偏移 rrmovq %rdi, %r10 # 缓存数组基地址，避免重复加载 inner_loop: cmpq %rsi, %rcx # 判断当前偏移是否小于最大偏移（i < len-1） jge inner_end # 达到终止条件，退出内层循环 # 读取当前元素和下一个元素 mrmovq (%r10, %rcx), %r11 mrmovq 8(%r10, %rcx), %r12 # 判断是否需要交换 subq %r12, %r11 jle no_swap # *arr_curr <= *arr_next，跳过交换 # 执行交换，复用已读取的寄存器值 rmmovq %r12, (%r10, %rcx) rmmovq %r11, 8(%r10, %rcx) no_swap: irmovq $8, %r8 addq %r8, %rcx # i++，偏移量加8 jmp inner_loop inner_end: # 外层循环：len--，重新进入外层判断 popq %rsi popq %rdi irmovq $1, %r8 subq %r8, %rsi # len = len -1 pushq %rdi pushq %rsi jmp outer_loop bubble_end: # 恢复调用者寄存器并返回 pushq %rdi pushq %rsi popq %rsi popq %rdi ret # end bubble # The stack starts here and grows to lower addresses .pos 0x200 stack:
关键修正说明
- 对齐C代码循环逻辑：
用栈保存每次的len和数组基地址，确保外层循环严格按照len >1判断，内层循环按照i < len-1执行，逻辑和C代码完全一致。 - 移除冗余操作：
删除重复的内存读取和比较判断，提升代码效率和可读性。 - 寄存器使用优化：
缓存数组基地址到r10，避免每次内层循环都重新加载rdi，减少指令周期。
内容的提问来源于stack exchange，提问作者chronkilo
相关产品推荐
相关产品推荐
