Mips2cs: Worked example

This page gives a worked example of how Mips2cs translates a simple factorial function into C#. It should be read in conjunction with How Mips2cs works.

C code

We start with the following C function:

int factorial(int x)
{
    if (x <= 1) {
        return 1;
    } else {
        return x * factorial(x-1);
    }
}

MIPS assembler code

GCC (at -O2) produces the following assembler code for this function:

0040015c <factorial>:
  40015c:       28820002        slti    v0,a0,2
  400160:       14400009        bnez    v0,400188 <factorial+0x2c>
  400164:       24050001        li      a1,1
  400168:       24020001        li      v0,1
  40016c:       00440018        mult    v0,a0
  400170:       2483ffff        addiu   v1,a0,-1
  400174:       00001012        mflo    v0
  400178:       1465fffc        bne     v1,a1,40016c <factorial+0x10>
  40017c:       00602021        move    a0,v1
  400180:       03e00008        jr      ra
  400184:       00000000        nop
  400188:       03e00008        jr      ra
  40018c:       24020001        li      v0,1

(Notice how GCC has transformed the recursion into a loop.)

Intermediate code

Mips2cs translates the above assembly code into Intermediate code, as well as splitting it up into basic blocks. This produces five basic blocks as follows:

BB0 <40015c>
        StoreReg "v0" (BinExpr SetIfLess (LoadRegExpr "a0") (LitExpr 2))
        Let "delay1" (LoadRegExpr "v0")
        Let "delay2" (LitExpr 0)
        StoreReg "a1" (BinExpr Add (LitExpr 0) (LitExpr 1))
        Jump (BinCond NotEqual (VarExpr "delay1") (VarExpr "delay2")) BB4 BB1

BB1 <400168>
        StoreReg "v0" (BinExpr Add (LitExpr 0) (LitExpr 1))
        Jump (LitCond True) BB2 BB2

BB2 <40016c>
        StoreReg "hi" (BinExpr MultHi (LoadRegExpr "v0") (LoadRegExpr "a0"))
        StoreReg "lo" (BinExpr Mult (LoadRegExpr "v0") (LoadRegExpr "a0"))
        StoreReg "v1" (BinExpr Add (LoadRegExpr "a0") (LitExpr (-1)))
        StoreReg "v0" (LoadRegExpr "lo")
        Let "delay1" (LoadRegExpr "v1")
        Let "delay2" (LoadRegExpr "a1")
        StoreReg "a0" (BinExpr Add (LoadRegExpr "v1") (LitExpr 0))
        Jump (BinCond NotEqual (VarExpr "delay1") (VarExpr "delay2")) BB2 BB3

BB3 <400180>
        Let "delay1" (LoadRegExpr "ra")
        IndirectJump (VarExpr "delay1")

BB4 <400188>
        Let "delay1" (LoadRegExpr "ra")
        StoreReg "v0" (BinExpr Add (LitExpr 0) (LitExpr 1))
        IndirectJump (VarExpr "delay1")

Translation into C# (without optimization)

If we disable the optimization passes (mips2cs -O0), the above Intermediate code would be translated directly into C# code:

        case 20:  // 0x0040015c
            v0 = (a0 < 2 ? 1 : 0);
            z0 = v0;
            z1 = 0;
            a1 = (0 + 1);
            if (z0 != z1) { goto case 24; } else { goto case 21; }

        case 21:  // 0x00400168
            v0 = (0 + 1);
            goto case 22;

        case 22:  // 0x0040016c
            hi = ( (int)(( (long)v0 * (long)a0 ) >> 32));
            lo = (v0 * a0);
            v1 = (a0 + -1);
            v0 = lo;
            z0 = v1;
            z1 = a1;
            a0 = (v1 + 0);
            if (z0 != z1) { goto case 22; } else { goto case 23; }

        case 23:  // 0x00400180
            z0 = ra;
            return case_table[z0];

        case 24:  // 0x00400188
            z0 = ra;
            v0 = (0 + 1);
            return case_table[z0];

This is a more-or-less literal translation of the MIPS assembly code, and is not particularly efficient.

Code Optimization for basic block BB0

If we run Mips2cs with maximum optimization (mips2cs -O2), then a number of transformation passes will be run on the Intermediate code, before converting it to C#.

In this section we show what happens during the optimization of the first basic block, BB0.

Expression simplification

First of all, expression simplification is performed. In this case, Mips2cs detects that (BinExpr Add (LitExpr 0) (LitExpr 1)) (in the fourth line) can be transformed into (LitExpr 1). The code for BB0 becomes:

        StoreReg "v0" (BinExpr SetIfLess (LoadRegExpr "a0") (LitExpr 2))
        Let "delay1" (LoadRegExpr "v0")
        Let "delay2" (LitExpr 0)
        StoreReg "a1" (LitExpr 1)
        Jump (BinCond NotEqual (VarExpr "delay1") (VarExpr "delay2")) BB4 BB1

Substitution

We now run the substitution pass. In this case, Mips2cs decides that both Let statements are suitable for substitution. It substitutes their right-hand sides directly into the final Jump statement, and removes the Lets. The code is now:

        StoreReg "v0" (BinExpr SetIfLess (LoadRegExpr "a0") (LitExpr 2))
        StoreReg "a1" (LitExpr 1)
        Jump (BinCond NotEqual (LoadRegExpr "v0") (LitExpr 0)) BB4 BB1

Liveness analysis

An inter-block analysis reveals that:

  1. BB0 can jump to either BB1 or BB4.
  2. Both BB1 and BB4 write to v0 before they read from it.
  3. Therefore, v0 is dead on exit from BB0.

Recall that if a register is found to be dead on exit from a basic block, then Mips2cs will replace the corresponding StoreReg with a Let. This results in the following:

        Let "dead_var_1" (BinExpr SetIfLess (LoadRegExpr "a0") (LitExpr 2))
        StoreReg "a1" (LitExpr 1)
        Jump (BinCond NotEqual (VarExpr "dead_var_1") (LitExpr 0)) BB4 BB1

Substitution

Another round of substitution now runs. Mips2cs decides that it is appropriate to remove the Let and substitute its right-hand side into the Jump statement. This leads to:

        StoreReg "a1" (LitExpr 1)
        Jump (BinCond NotEqual (BinExpr SetIfLess (LoadRegExpr "a0") (LitExpr 2)) (LitExpr 0)) BB4 BB1

Expression simplification

Finally, another round of expression simplification takes place. The expression in the Jump statement can be simplified to the following:

        StoreReg "a1" (LitExpr 1)
        Jump (BinCond LessThan (LoadRegExpr "a0") (LitExpr 2)) BB4 BB1

This is the final optimized code for BB0.

Code Optimization for the other basic blocks

Optimization is also applied to the four other basic blocks, in a similar way to the above, although we will not go into the details here.

Suffice to say, the final optimized Intermediate code is as follows:

BB0 <40015c>
        StoreReg "a1" (LitExpr 1)
        Jump (BinCond LessThan (LoadRegExpr "a0") (LitExpr 2)) BB4 BB1

BB1 <400168>
        StoreReg "v0" (LitExpr 1)
        Jump (LitCond True) BB2 BB2

BB2 <40016c>
        StoreReg "v1" (BinExpr Add (LitExpr (-1)) (LoadRegExpr "a0"))
        StoreReg "v0" (BinExpr Mult (LoadRegExpr "v0") (LoadRegExpr "a0"))
        StoreReg "a0" (LoadRegExpr "v1")
        Jump (BinCond NotEqual (LoadRegExpr "v1") (LoadRegExpr "a1")) BB2 BB3

BB3 <400180>
        IndirectJump (LoadRegExpr "ra")

BB4 <400188>
        StoreReg "v0" (LitExpr 1)
        IndirectJump (LoadRegExpr "ra")

This translates into the following C# code:

        case 20:  // 0x0040015c
            a1 = 1;
            if (a0 < 2) { goto case 24; } else { goto case 21; }

        case 21:  // 0x00400168
            v0 = 1;
            goto case 22;

        case 22:  // 0x0040016c
            v1 = (-1 + a0);
            v0 = (v0 * a0);
            a0 = v1;
            if (v1 != a1) { goto case 22; } else { goto case 23; }

        case 23:  // 0x00400180
            return case_table[ra];

        case 24:  // 0x00400188
            v0 = 1;
            return case_table[ra];

This compares favourably with the non-optimized C# code (see above).