0

I have C code in front of me that I have to translate into a MIPS assembly language.

I am not looking for a direct answer, but I want someone to correct the way I'm thinking about the problem.

The C code in front of me is:

x = ((++z) <= y);

I have in the given that the x, y, and z are respectively stored in the registers $6, $7, $8

The problem is I can't use an operator to compare directly less than or equal. I am limited to use the following comparing operands: bne, beq, ori, slt.

The way I approached the problem was as such:

      addi   $8,$8,1     # This will increment z by 1 to have ++z
      slt    $1,$8,$7    # Compares ++z to y if ++z is < than y. It
                         # will store 1 in $1
      beq    $8,$7,Label # Compares if $8 = $7. If so, the code
                         # jumps to Label
Label addi   $t0,$0,1    # If ++z = y, stores 1 in $t0
      ori    $6,$t0,$1   # Or's the t0 and t1 and accordingly stores
                         # 0 or 1 in x

Is this the right approach to this problem?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Ralph
  • 2,959
  • 9
  • 26
  • 49

1 Answers1

1

As usual, ask a compiler (e.g. on the Godbolt compiler explorer). See also How to remove "noise" from GCC/clang assembly output?

<= alone (without the increment) is best implemented with a reversed slt (to do b<a which is the opposite of a<=b) and then xori to flip the result.

int booleanize_le(int y, int z){
    return (z<=y);
}

# GCC5.4 -O3 -fno-delayed-branch
booleanize_le(int, int):
        slt     $2,$4,$5        # slt retval, y, z
        xori    $2,$2,0x1       # !retval, i.e. flip 0 <-> 1 since it was already boolean
        j       $31                       # return
  # (omitting the NOP in the branch-delay slot)

Fun fact: clang for RISC-V does the same thing, slt/xori, because RISC-V is like MIPS in only providing slt for compare-into-boolean. (Because you can booleanize any relation like ==, <=, >, or whatever into an integer register with at most 2 instructions.)

But in your case where you want to increment, and you're using addi so clearly z must be a signed int (otherwise your code would fault on increment from 0x7fffffffU to 0x80000000U; use addiu if you want well-defined wrap around).

C rules for signed-overflow being undefined behaviour basically match use of MIPS addi, which means compilers will also assume ++z doesn't wrap, and do the optimization we want. They and we we can just use the original z value. (z+1)<=y is the same thing as z<y if z+1 doesn't / can't wrap.

int booleanize_inc_le_signed(int y, int z){
    return ((++z)<=y);
}

booleanize_inc_le_signed(int, int):
        slt     $2,$5,$4             # z<y  before incrementing
        j       $31
    # increment optimized away in this function, but you'd do it with
    addiu   $5, $5, 1

If z had been unsigned, that optimization isn't possible and the compiler does just increment and then use the unsigned version of the 2-instruction <= slt/xori sequence:

int booleanize_inc_le_unsigned(unsigned int y, unsigned int z){
    return ((++z)<=y);
}

booleanize_inc_le_unsigned(unsigned int, unsigned int):
        addiu   $5,$5,1                # z++
        sltu    $2,$4,$5               # y<z (unsigned)
        xori    $2,$2,0x1              # return !(y<z)
        j       $31

Other relations

Exact equality, a == b

    xor     $2,$4,$5          # find bit-differences
    sltu    $2,$2,1           # (a^b) < 1U

Not equal, a != b

    xor     $2,$4,$5
    sltu    $2,$0,$2          # 0U < (a^b)

One integer being non-zero: a!=0, i.e. !!a

    sltu    $2,$0,$4          # 0U < a

Any others can obviously be derived, or just ask a compiler (use the Godbolt link).

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847