c++assemblymipsqtspim

Store a value into every element of an array: converting a C do{}while loop to MIPS asm


I need to convert this C++ function into MIPS assembly:

int set(int a[], int n, int v)
{
    int i;
    i = 0;
    do {
      a[i++] = v;
    } while ( i < n);
    return i;
}

where the address of the array is in $a0, n is in $a1, and v is in $a2. This is my attempt at writing the function in MIPS, but I get "instruction references undefined symbol at 0x00400054." in main (provided by my professor) there is a call jal set which is supposed to call the set function and I'm pretty sure my error has something to do with that. I also don't know if I successfully converted the function. This is my attempt:

.text
set:
    li      $t0, 0
    addi    $t0, $t0, 0
    sll     $t1, $t0, 2
    add     $t1, $t1, $a0
L1: lw      $t1, 4($t1)
    sw      $a2, 0($t1)
    blt     $t0, $a1, L1

I'm using QTSPIM, if that matters at all. I appreciate any help and if you have any advice to pass along for MIPS programming, that would be great too.

UPDATE:

The files are being linked now, but I'm getting an infinite loop of "Exception occurred at PC=0x004000f0" and "Bad address in data/stack read: 0x00000000." This is my updated file:

.text
.globl set
set:    addi    $t0, $t0, 0     #i = 0;
         sll    $t1, $t0, 2     #offsets 4 * i
         add    $t1, $t1, $a0       #pointer to a[i]
L1:       lw    $t1, 4($t1)     #a[i++]
          sw    $a2, 0($t1)     #a[i++] = v
         blt    $t0, $a1, L1        #continue the loop as long as i < n

Why is it that my code has to be in .globl? And what's the purpose of .text?


Solution

  • Okay, there were a few problems.

    The corrected code is at the bottom. There are actually two ways to do it, based upon how literal the translation from the C code needs to be. Part of your conceptual problem may have been that you were trying to combine parts from the two methods.

    You collapsed your first two instructions from your original code into one, based on comment feedback [as duplicate] (e.g. li then addi). But, if using only one, the li is correct because addi adds the register to itself but you can't rely on the initial value being zero.

    The sll is shifting a register that has a zero value in it, so the inst isn't doing anything.

    To load t1 with a0, you'd use add $t1,$a0,0 [or add $t1,$a0,$zero]

    The lw served no purpose [The C code does not load a, so why should asm?].

    But, I switched this all around a bit because the loop still wouldn't have worked correctly.

    There was no return after your blt so even if the loop worked, it would "fall off the edge of the world". Each called asm routine [one that is invoked like jal set] must have an explicit return statement, which is jr $ra

    NOTE: In MIPS asm, the a* [argument registers] can be modified by the callee, so loop on a0 rather than t1 (i.e. caller expects that they will be trashed)


    Anyway, here's the corrected code [please pardon the gratuitous style cleanup]:

        .text
    
        .globl  set
    set:
        li      $t0,0                   # i = 0
    L1:
        sw      $a2,0($a0)              # a[i] = v
        add     $a0,$a0,4               # advance pointer
        add     $t0,$t0,1               # ++i
        blt     $t0,$a1,L1              # continue the loop as long as i < n
        jr      $ra                     # return
    

    If your original C function had been something like:

    int
    set(int *a, int n, int v)
    {
        int *end;
    
        end = a + n;
        for (;  a < end;  ++a)
            *a = v;
    
        return n;
    }
    

    Then, this would have been a more literal translation:

        .text
    
        .globl  set
    set:
        sll     $a1,$a1,2               # convert int count to byte length
        add     $a1,$a0,$a1             # end = a + length
    
    L1:
        sw      $a2,0($a0)              # *a = v
        add     $a0,$a0,4               # ++a
        blt     $a0,$a1,L1              # continue the loop as long as a < end
    
        jr      $ra                     # return
    

    IMO, both methods are acceptable implementations of the original C function. The first is more literal in that it preserves the [concept of] the index variable i. But, it has an extra instruction that the second doesn't.

    An optimizer would probably produce the same code (i.e. the second asm) regardless of which C function it was translating (MIPS does not have the powerful index addressing modes that x86 asm does).

    So, which is "correct" may depend upon how much a stickler your prof is.


    Side note: Notice the style changes between my two examples. That is, code changes aside, adding some blank lines to improve clarity.


    Just for completeness, here's the main function I created when testing:

        .data
    arr:    .space  400                 # allocate more space than count
    
        .text
    
        .globl  main
    main:
        la      $a0,arr                 # get array pointer
        li      $a1,10                  # get count
        li      $a2,3257                # value to store
    
        jal     set
    
        li      $v0,1                   # exit syscall number
        syscall
    

    UPDATE:

    If in the loop a[i++] = v, would I place the add $t0, $t0, 1 line before the sw $a2, 0($a0)?

    No, you would do that if the C code was a[++i] = v. Perhaps, the best way to view this is to simplify the C code first.

    a[i++] = v is actually:

    a[i] = v;
    i += 1;
    

    And, a[++i] = v is actually:

    i += 1;
    a[i] = v;
    

    Now, there is a one-to-one correspondence between the lines of C code and asm instructions.

    When would I use the sll? I was reading examples and I noticed people usually do sll $t1, $t0, 2 when they're going to use a counter to go through an array.

    Yes. If you look closely at my second implementation, it uses sll in that manner. Also, it would be the way I would code the loop even when given the original C code.

    Would I use the lw if the C code said something like int x = a[0]?

    Yes, exactly.


    Another way to prototype asm is to convert the C code into "very dumb C".

    That is, only if of the simplest form: if (x >= y) goto label. Even if (x < y) j = 10 is off limits.

    No function scoped variables or function argument variables--only global variables that are the register names.

    No complex expressions. Only simple ones like x = y, x += y, or x = y + z. Thus, a = b + c + d would be too complex.

    Register variables function as both integer values and byte pointers. So, when adding to a register being used as a pointer, it's like adding to a byte pointer, so to increment through an int array, you have to add 4.

    The actual difference between a byte pointer and int pointer only matters when you do a load/store operation: lw/sw for int and lb/sb for byte.

    So, here's my second C function recoded as "dumb":

    // RETURNS: number of elements changed
    int
    set(void)
    // a0 -- "a" (pointer to int array)
    // a1 -- "n" (number of elements in "a")
    // a2 -- "v" (value to set into "a")
    {
    
        v0 = a1;                            // set return value
    
        a1 <<= 2;                           // convert int count to byte length
        a1 += a0;                           // point to one past end of array
    
    L1:
        *(int *)a0 = a2;                    // store v at current array location
        a0 += 4;                            // point to next array element
        if (a0 < a1) goto L1;               // loop back until done
    
        return;
    }
    

    UPDATE #2:

    In your first implementation, is add $a0, $a0, 4 the equivalent to using sll in the second implementation?

    Not quite. The key thing to remember is in C, when we add one to a pointer [or index it with i], the compiler will generate an increment/add instruction that adds the sizeof of the type the pointer is defined as.

    That is, for int *iptr, specifying iptr += 1 will generate add $a0,$a0,4 because sizeof(int) is 4. If we had double *dptr, dptr += 1, the compiler would generate add $a0,$a0,8 because sizeof(double) is 8

    This is a powerful "convenience" that the C compiler provides because it allows arrays, pointers, indexes to be used interchangeably.

    In asm, we must do manually what the C compiler would do for us automatically.

    Consider the following: We have a value that is the count of the number of elements in an array, call it count. Now, we want to know how many bytes the array will take up. We'll call that len. Here's the C code to determine that for various types:

    char *arr;
    len = count * sizeof(char);
    len = count * 1;
    len = count << 0;
    //  sll $a1,$a1,0
    
    short *arr;
    len = count * sizeof(short);
    len = count * 2;
    len = count << 1;
    //  sll $a1,$a1,1
    
    int *arr;
    len = count * sizeof(int);
    len = count * 4;
    len = count << 2;
    //  sll $a1,$a1,2
    
    double *arr;
    len = count * sizeof(double);
    len = count * 8;
    len = count << 3;
    //  sll $a1,$a1,3
    

    From what I understand, using sll sets i as a counter for ints so it increments i and also iterates the array

    No. sll is merely MIPS's "shift left logical" instruction and you use it when you need the equivalent of C's << operator.

    What you're thinking of is how sll can be used to achieve that effect.

    To iterate through an array of int, we increment the index by 1 but we must also increment the array pointer by 4. This is what my first asm example did. The termination condition was index >= count.

    In my second asm example, I eliminated the separate index variable by converting the element count into a byte length (via the ssl), adding in the array address. Now $a1 had the address of the last element of the array + 1, and the termination condition was current_address >= last_element_plus_1. Note that current_address ($a0) still had to be incremented by 4 (add $a0,$a0,4)

    One important thing to remember is that asm instructions [particularly MIPS] are simple (i.e. dumb). They do only one thing at a time. A single C assignment statement could generate some 20 instructions if the statement were complex enough. It's how the asm instructions get combined that produces the more complex results.