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.
We start with the following C function:
int factorial(int x)
{
if (x <= 1) {
return 1;
} else {
return x * factorial(x-1);
}
}
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.)
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")
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.
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.
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
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
An inter-block analysis reveals that:
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
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
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.
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).