(THEMO~2.PDF

148 Chapter 2 Instructions: Language of the Computer FIGURE 2.27 Performance of two sort algorithms in C and Java using interpretation and optimizing compilers relative to unoptimized C version. The last column shows the advantage in performance of Quicksort over Bub...

148 Chapter 2 Instructions: Language of the Computer FIGURE 2.27 Performance of two sort algorithms in C and Java using interpretation and optimizing compilers relative to unoptimized C version. The last column shows the advantage in performance of Quicksort over Bubble Sort for each language and execution option. These programs were run on the same system as in Figure 2.29. The JVM is Sun version 1.3.1, and the JIT is Sun Hotspot version 1.3.1. 2.14 Arrays versus Pointers A challenge for any new C programmer is understanding pointers. Comparing assembly code that uses arrays and array indices to the assembly code that uses pointers offers insights about pointers. This section shows C and RISC-V assembly versions of two procedures to clear a sequence of words in memory: one using array indices and one with pointers. Figure 2.28 shows the two C procedures. The purpose of this section is to show how pointers map into RISC-V instructions, and not to endorse a dated programming style. We’ll see the impact of modern compiler optimization on these two procedures at the end of the section. FIGURE 2.28 Two C procedures for setting an array to all zeros. clear1 uses indices, while clear2 uses pointers. The second procedure needs some explanation for those unfamiliar with C. The address of a variable is indicated by &, and the object pointed to by a pointer is indicated by *. The declarations declare that array and p are pointers to integers. The first part of the for loop in clear2 assigns the address of the first element of array to the pointer p. The second part of the for loop tests to see if the pointer is pointing beyond the last element of array. Incrementing a pointer by one, in the bottom part of the for loop, means moving the pointer to the next sequential object of its declared size. Since p is a pointer to integers, the compiler will generate RISC-V instructions to increment p by four, the number of bytes in an RISC-V integer. The assignment in the loop places 0 in the object pointed to by p.  2.14 Arrays versus Pointers 149 Array Version of Clear Let’s start with the array version, clear1, focusing on the body of the loop and ignoring the procedure linkage code. We assume that the two parameters array and size are found in the registers x10 and x11, and that i is allocated to register x5. The initialization of i, the first part of the for loop, is straightforward: addi   x5, x0, 0   // i = 0 (register x5 = 0) To set array[i] to 0 we must first get its address. Start by multiplying i by 4 to get the byte address: loop1: slli   x6, x5, 2   // x6 = i * 4 Since the starting address of the array is in a register, we must add it to the index to get the address of array[i] using an add instruction: add x7, x10, x6   // x7 = address of array[i] Finally, we can store 0 in that address: sw x0, 0(x7)   // array[i] = 0 This instruction is the end of the body of the loop, so the next step is to increment i: addi x5, x5, 1   // i = i + 1 The loop test checks if i is less than size: blt x5, x11, loop1 // if (i < size) go to loop1 We have now seen all the pieces of the procedure. Here is the RISC-V code for clearing an array using indices: addi x5, x0, 0 // i = 0 loop1: slli x6, x5, 2 // x6 = i * 4 add x7, x10, x6 // x7 = address of array[i] sw x0, 0(x7) // array[i] = 0 addi x5, x5, 1 // i = i + 1 blt x5, x11, loop1 // if (i < size) go to loop1 (This code works as long as size is greater than 0; ANSI C requires a test of size before the loop, but we’ll skip that legality here.) Pointer Version of Clear The second procedure that uses pointers allocates the two parameters array and size to the registers x10 and x11 and allocates p to register x5. The code for the 150 Chapter 2 Instructions: Language of the Computer second procedure starts with assigning the pointer p to the address of the first element of the array: mv   x5, x10   // p = address of array The next code is the body of the for loop, which simply stores 0 into p: loop2: sw   x0, 0(x5)   // Memory[p] = 0 This instruction implements the body of the loop, so the next code is the iteration increment, which changes p to point to the next word: addi   x5, x5, 4   // p = p + 4 Incrementing a pointer by 1 means moving the pointer to the next sequential object in C. Since p is a pointer to integers declared as int, each of which uses 4 bytes, the compiler increments p by 4. The loop test is next. The first step is calculating the address of the last element of array. Start with multiplying size by 8 to get its byte address: slli   x6, x11, 2   // x6 = size * 4 and then we add the product to the starting address of the array to get the address of the first doubleword after the array: add   x7, x10, x6    //  x7 = address of array[size] The loop test is simply to see if p is less than the last element of array: bltu x5, x7, loop2    // if (p