Problem 4.47: Let\'s start with a big-picture observation: the easiest way to ge

Question

Problem 4.47: Let's start with a big-picture observation: the easiest way to get from any C program to a working Y86-64 version of the same is to (a) alter the C code so it maps to the Y86-64 instruction set more efficiently, and then (b) hand translate the x86-64 assembly code that GCC produces into Y86-64 assembly code. Part A of this problem corresponds to (a) above: by revising the code to use pointers rather than array accesses, GCC's output will be closer to what you can do in the Y86-64 instruction set. When you think you have a pointer version that works, naturally you'll want to test it to ensure that the two versions of the code are equivalent before going on to the next step. Use something along the lines of the test code available here ( http://ece324web.groups.et.byu.net/hw/code/testbubble.c ) to make sure that both versions of the bubble sort function are equivalent. Your submission should include not only the C code in your new version of the function, but results from testing that show that the functions are equivalent.

The next step is to compile your source code (using the "-S" command line argument to GCC) and hand translate the bubble_p() function to Y86-64 code. Experiment with different optimization levels and choose a version of assembly code that will require the least amount of work to turn into Y86-64 code. Use the Y86-64 code framework here ( http://ece324web.groups.et.byu.net/hw/code/4_47.ys ) so you can run and test your solution using Y86-64 simulation tools. (Note that the data to be sorted in this code is the same as in the C test code above.)

Finally, run your code using the yas and yis programs (a Y86-64 assembler and instruction set emulator, respectively) that can be obtained by clicking here ( http://ece324web.groups.et.byu.net/hw/code/tools.tar ). Place the file tools.tar into a newly created directory and type "tar xvf *". This will create a tools subdirectory and place in it all the files required to build yas and yis. Now type "cd tools" and then type "make" and new yis and yas executables should be built. If your Y86-86 code is in the file bubble.ys in the parent directory, you can assemble it by typing "tools/yas bubble.ys" and then you should run the resulting object file on the simulator by typing "tools/yis bubble.yo". (Check the README file in the tools directory for a bit more information about the yas and yis programs.) In creating any Y86 program for the yis simulator, bear in mind that the largest allowed memory address is 0x0FFFF.

Make sure the results of execution are as you expected. Include the simulator output from the execution of your program in your submission with some brief annotation that explains how you know it is correct.

Your assignment will be to write a Y86-64 program to perform bubblesort. For reference, the following C function implements bubblesort using array refer encing. 1 Bubble sort Array version 2 void bubble long *data, long count) long i, last; for (last count-1; last 0; last--) t for (i 0; i last; i++) if (data [it datalil) swap adjacent elements long t a data Citi]; data lit1] data lij data [i] t; 70 12 13 A. Write and test a C version that references the array elements with pointers, rather than using array indexing. B. Write and test a Y86-64 program consisting of the function and test code. You may find it useful to pattern your implementation after x86-64 code generated by compiling your C code. Although pointer comparisons are normally done using unsigned arithmetic, you can use signed arithmetic for this exercise.

Explanation / Answer

A.
void bubble_a(long *data, long count)
{
   long i, last;
   for (last = count-1; last > 0; last--)
   {
       for (i = 0; i < last; i++)
       {
           if (*(data+i+1) < *(data+i))
           {
               long t = *(data+i+1);
               *(data+i+1) = *(data+i);
               *(data+i) = t;
           }
       }
   }
}

B.
   .pos 0
init:  
       irmovq $0x100, %rax
       rrmovq %rax, %rsp
       rrmovq %rax, %rbp
       xorq %rax, %rax
Main:  
       irmovq $0x1, %rbp
       irmovq $0x28, %rbx
       subq %rbx, %rsp
       irmovq $0x2, %rax                   #set count
       rmmovq %rax, %rsi
       irmovq $0x5, %rax                   #set value 1
       rmmovq %rax, (%rsp)
       irmovq $0x6, %rax                   #set value 2
       rmmovq %rax, 0x4(%rsp)
       irmovq $0x2, %rax                   #set value 3
       rmmovq %rax, 0x8(%rsp)
Loop1:      
       xorq %rax, %rax
Loop2:
       pushq %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rsp, %rax
       mrmovq 0x8(%rax),%rdx
       mrmovq (%rax),%rcx
       popq %rax
       pushq %rdx
       subq %rcx, %rdx
       popq %rdx
       jge Loop3
       pushq %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rax, %rax
       addq %rsp, %rax
       rmmovq %rcx,0x8(%rax)
       rmmovq %rdx,(%rax)
       popq %rax
Loop3:
       addq %rbp, %rax
       pushq %rax
       subq %rsi, %rax
       popq %rax
       jl Loop2
       subq %rbp, %rsi
       jne Loop1
       mrmovq 0x10(%rsp),%r8
       mrmovq 0x8(%rsp), %rcx
       irmovq $0x400654, %rsi
       mrmovq (%rsp), %rdx
       rrmovq %rbp, %rdi
       xorq %rax, %rax
       addq %rbx, %rsp
       halt

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.