Steinar H. Gunderson

As promised, the last one (for now?), and this one blew my mind the first time I saw it:

    var_v0 = sp4014;
    if ((s32) sp4014 < 0) {
        var_v0 = sp4014 + 0x7FF;
    }
    temp_s1 = 0x800 - (sp4014 - (((s32) var_v0 >> 0xB) << 0xB));

There's actually two things going on here. First, the compiler is faking a signed division using shifting (which rounds down) as a building block: If the value is negative, then you add a bias to make shift into round-up. (The right-shift by 0xB, or 11, is exactly a division by 0x800.)

So this means what we're looking at is:

    var_v0 = (s32) sp4014 / 0x800;
    temp_s1 = 0x800 - (sp4014 - var_v0 * 0x800);

which reduces further to:

    temp_s1 = 0x800 - ((s32) sp4014 % 0x800);

Tada. That's it. Now you know all the tricks, except those that I don't know or that I forgot. You don't need the LLM. Have fun. :-)

Edit: Corrected a thinko; of course, MIPS has signed division. This is for power-of-two optimizations only.

Occasionally, you'll see code like this (after initial cleanup):

    var_v0_2 = crc & 0x80000000;
    do {
       if (var_v0_2 != 0) {
           crc = (crc << 1) ^ 0x1EDC6F41;
       } else {
           crc <<= 1;
       }
       var_a0 += 1;
       var_v0_2 = crc & 0x80000000;
    } while (var_a0 < 8U);

The thing with var_v0_2 is unnatural. GCC sometimes does these loop rotation tricks, seemingly to save registers (don't ask me how exactly it does). You want to un-rotate back into:

    do {
       var_v0_2 = crc & 0x80000000;
       if (var_v0_2 != 0) {
           crc = (crc << 1) ^ 0x1EDC6F41;
       } else {
           crc <<= 1;
       }
       var_a0 += 1;
    } while (var_a0 < 8U);

and then of course, you can clean up the rest:

for (i = 0; i < 8; ++i) {
    if (crc & 0x80000000) {
        crc = (crc << 1) ^ 0x1EDC6F41;
    } else {
        crc <<= 1;
    }
}

Last one tomorrow, I think.

We're nearing the end soon, I promise. Here's one that I see all the time:

     ...
         } else {
             var_t0_5 = temp_a0_3 - 0x140;
             var_a2_5 = 0xA0 - temp_a3_5;
             goto block_45;
         }
     } else {
         var_t0_5 = 0xA0 - temp_a0_3;
         var_a2_5 = temp_a3_5 - 0x118;
block_45:               
         var_v0_3 = var_t0_5 + 0xA0;
         var_v1_4 = var_a2_5 + 0x78;
     }

So, eh, what's that goto doing there? What happened was that the compiler helpfully figured it could help with some tail deduplication; someone wrote the same code twice, and the compiler figured taking the cost of a branch was better than keeping it duplicated. (In a sense, it's the opposite of inlining. Ish.) In most cases, it's as simple as copying the block and then you can remove the label:

     ...
         } else {
             var_t0_5 = temp_a0_3 - 0x140;
             var_a2_5 = 0xA0 - temp_a3_5;
             var_v0_3 = var_t0_5 + 0xA0;
             var_v1_4 = var_a2_5 + 0x78;
         }
     } else {
         var_t0_5 = 0xA0 - temp_a0_3;
         var_a2_5 = temp_a3_5 - 0x118;
         var_v0_3 = var_t0_5 + 0xA0;
         var_v1_4 = var_a2_5 + 0x78;
     }

Sometimes, these are nested, with multiple tails goto-ing into each other, so in that case, you'll need to reduplicate multiple times. Make sure you actually come out on the correct side afterwards, though.

As an extra complication, the code is deduplicated not on the C statement level, but on RTL instructions, so if you're calling functions with five parameters of more (which requires pushing parameters onto the stack), m2c can get really confused and start throwing M2C_ERROR() at you on the receiving side because it's not clear at all where the parameters would be coming from.

Yet another way of writing for loops:

    var_a2_4 = ...
    if (var_a2_4 < 0x78) {
        ...
        do {
            ...
            var_a2_4 += 1;
        } while (var_a2_4 < 0x78);
    }

This extra if is merely there because the compiler wasn't able to prove that the variable didn't start below the bound, so it can't rewrite the while-do to a do-while without that extra check. So the rewrite still reads:

for (var_a2_4 = ...; var_a2_4 < 0x78; ++var_a2_4) {
    ...
}

possibly with the initializer skipped, if it comes from something complex earlier.

Let's look at the entire loop from yesterday:

    u16 spE10;
    u16 *var_v0_2;

    ...

    var_t1_2 = 0x7F;
    var_v0_2 = &spE10 + 0xFE;
    do {
        *var_v0_2 = 0;
        var_t1_2 -= 1;
        var_v0_2 -= 2;
    } while (var_t1_2 >= 0);

What's going with the pointer arithmetic here? Why is it indexing out-of-bounds?

The first thing to notice is that m2c doesn't really take into account that arithmetic on pointers in C is multiplied by the size of the element. And obviously, spE10 is the root of some array. So corrected, this reads:

    u16 spE10[0x80];  // Modified.
    u16 *var_v0_2;

    ...

    var_t1_2 = 0x7F;
    var_v0_2 = spE10 + 0x7F;  // Modified.
    do {
        *var_v0_2 = 0;
        var_t1_2 -= 1;
        var_v0_2 -= 1;  // Modified.
    } while (var_t1_2 >= 0);

We saw yesterday how we should rewrite the iteration back to a for loop, but also, most likely, the pointer arithmetic here came from strength reduction; the compiler took a multiplication operation and rewrote it to a “weaker” operation (subtraction) since that's typically cheaper, at the cost of making the values dependent, an easy trade. So we can rewrite it back into multiplication:

    var_t1_2 = 0x7F;
    do {
        var_v0_2 = spE10 + var_t1_2;
        *var_v0_2 = 0;
        var_t1_2 -= 1;
    } while (var_t1_2 >= 0);

and now it's easy to see that the loop should read:

    for (i = 0; i < 0x80; ++i) {
        spE10[i] = 0;
    }

and then, of course, the array should get a better name.

Sometimes the loop counter will go backwards while the pointer will go forwards, which is also completely normal, especially if there's side effects. The compiler will reverse one but not the other.

Anyone who's read “bro-coder” C from before that was a name will recognize this idiom:

    var_t1_2 = 0x7F;
    ...
    do {
        ...
        var_t1_2 -= 1;
    } while (var_t1_2 >= 0);

Why does the loop count backwards? It's because comparison with zero is cheaper on some (many) platforms. Some people would reverse the loop manually, but compilers quickly managed to do that themselves. So you want:

   for (i = 0; i < 0x80; ++i) {
      ...
   }

and tomorrow, we'll have a look at what's inside the loop as well.

Say you see this lovely chunk of decompiled code:

    var_v1 = &sp10;
    var_v0 = D_80010040;
    temp_s4 = var_v1;
    sp110 = &sp2C;
    sp114 = &sp30;
    do {
        var_v1->unk0 = (s32) var_v0->unk0;
        var_v1->unk4 = (s32) var_v0[1];
        var_v1->unk8 = (s32) var_v0[2];
        var_v1->unkC = (s32) var_v0[3];
        var_v0 += 0x10;
        var_v1 += 0x10;
    } while (var_v0 != &D_8001040[0x3C]);
    var_v1->unk0 = (s32) var_v0->unk0;
    var_v1->unk4 = (s32) var_v0[1];
    var_v1->unk8 = (s32) var_v0[2];

If you ignore the fact that m2c wrote ->unk0 for [0] (it has a bit of an annoying habit to do that), this is obviously something copying 16 bytes at a time and then 12 more bytes at the end. But would a programmer ever do this? Nope, this is an inlined, unrolled memcpy.

This is known in GCC as __builtin_memcpy, and it can happen either implicitly, or by some sort of lowering from a struct or array copy (e.g., through initialization of a stack array). Depending a bit on whether the variable is known to be aligned or not, you'll either get just lw or some evil lwr/lwl sequence; I'm always struggling a bit to change one to the other. In any case, what you want here is:

    __builtin_memcpy(&sp10, D_80010040, 0x4C);

and then make sp10 the right type instead of a scalar, ideally so that you can use sizeof() on it. Or, in some cases, a direct initialization:

    s32 foo[] = { 1, 2, 3, ...more data from D_80010040... };

Here's one that m2c usually gets right itself, but sometimes cannot:

    if (var_v1_7 != 1) {
        if (var_v1_7 < 2) { 
            if (var_v1_7 != 0) {
                spF0 = 40; 
            } else {
                vram_x = cmt46->vram_x;
                vram_y = cmt46->vram_y;
                spF0 = 40;
            }
        } else if (var_v1_7 != 2) {
            if (var_v1_7 != 3) {

Repeated comparisons against the same variable, especially in a nested form that could be binary search, should remind you of one thing: A switch. Usually, the compiler implements a switch with a jump table, but not always; if there are few conditions, or the range is too large for a reasonably-sized table, it will do some ifs instead (or, enough ifs to get within the range of a table). So what you want here is more like:

    switch (var_v1_7) {
    case 0:
       vram_x = cmt46->vram_x;
       vram_y = cmt46->vram_y;
       spF0 = 40;
       break;
    case 1:
       spF0 = 40;
       break;
    case 2:
       ...
    }

Remember that sometimes, you may need to insert cases that are not explicitly mentioned in the ifs (and/or a default case) to get everything to match back properly.

The v0 register on MIPS is special in that it is the return register (like rax is on x86-64), so when you see code like this:

if (x == 3) {
    var_v0 = 1;
} else if (y == 4) {
    ...
    var_v0 = 3;
}
var_v0 = 5;
return var_v0;

then you have to consider the possibility that the intended match is:

if (x == 3) {
    return 1;
} else if (y == 4) {
    ...
    return 3;
} else {
    return 5;
}

Whether you put the last return in an else block or not is irrelevant for the match, of course, it's purely a matter of taste.

Today, for something completely different:

s.x = (s16) ((s32) (temp_v0 << 0x10) >> 0x11);

MIPS has 16-bit loads and stores, but not 16-bit (signed) arithmetic, so if it wants to do that, it needs to sign-extend to 32-bit first. And it does that by first shifting up by 16 so that the 16-bit sign bit is at the 32-bit sign bit, and then it can do an arithmetic shift afterwards. So what you want is:

s16 temp_v0;

s.x = temp_v0 >> 1;

Sometimes, it can be pretty stubborn, and you'll need to go through memory or similar before GCC really inserts the shift patterns you want.