Targeting the MIPS

The Omega2 series of IoT devices have a MIPS32 processor in an attractively small and lightweight package, running a minimal version of Linux called OpenWRT that is often used as firmware for wireless routers. Perhaps the existence of this convenient platform will provide the impetus to make a compiler targetting the MIPS.

• You could retarget the Lab 4 compiler from the Compilers course, aiming to adapt the existing code so as much of it as possible can be shared by back ends for the ARM32 and the MIPS. A chapter of the (otherwise almost impenetrable) book, A retargetable C compiler: design and implementation by Fraser and Hanson, gives helpful information and a machine grammar for the MIPS.

• Alternatively, you could work on a JIT translator for Keiko (as used for the Oxford Oberon Compiler) along the lines of the existing JITs for x86/amd64 and ARM32. This idea might be complicated by the lack of a floating point unit on the Omega2, but it would be possible to copy what is done (via subroutine calls or emulation) by the Omega2 C compiler. The Keiko JIT has a portability interface based on assembly code for an invented, idealised RISC machine that fits well with the MIPS, so the task ought to be manageable. The work would include writing a dynamic assembler that would generate MIPS instructions in binary format, needing a result correct down to the last bit.

Work on either of these options would be aided by the existence of a MIPS emulator as part of QEMU, and a GCC-based cross compiler that runs under Linux on x86 machines. A debugging build using QEMU of the Keiko JIT for ARM already exists and can provide a guide.

All of the above could apply to the AARM64 architecture too, if we can find a stable hardware platform to act as a motivation. The RPi would do, given a usable Linux port that runs in 64 bit mode.

Keiko on MIPS

It's possible to build the Keiko bytecode interpreter under Debian/x86 using a MIPS cross-compiler, then run it using QEMU. It's also possible to install the OpenWRT build environment and use its cross-compiler to generate the flavour of MIPS code needed by the Omega2 and link with the appropriate C library. The resulting interpreter also runs on QEMU, and can be copied to the Omega2 and runs there. Thirdly, it's possible to build OBC on the Omega2+, after installing an SD card and building prerequisite software from source.

Generic MIPS build of Keiko

• Use Debian and install the packages gcc-mipsel-linux-gnu and qemu-user. (It's mipsel for the little-endian variant of MIPS, which is the one used in the Omega2.)
• Clone the OBC-3 repository.
• Configure and build OBC, then change to the mipstest directory and build there. The final step of the build is to run a small test case under QEMU.

OpenWRT toolchain

(Don't bother with this.)

• Install the OpenWRT toolchain using instructions here: https://github.com/OnionIoT/Onion-Docs/blob/master/Omega2/Documentation/Doing-Stuff/Advanced/Cross-Compile.md
• Then you need to make some symlinks and use a modified Makefile.in in mipstest.
• The resulting executable obx-mips will run under QEMU, and can also be copied (together with Fac.x) to the Omega2.
• Use chmod +x obx-mips then ./obx-mips ./Fac.x to run it.

Building on Omega2

• Use an Omega2+ with the 128MB RAM and the SD card slot. A 4GB SD card will be big enough.
• Migrate the root file system onto the SD card: https://docs.onion.io/omega2-docs/boot-from-external-storage.html
• Enable more package repositories, and install the C compiler and Make.
• Install the following from source:
  • Mercurial.
  • TCL (needed to build Keiko). Disable all add-on packages by removing the contents of the pkgs directory in the source.
  • OCaml.
• Clone the OBC repo, configure with --disable-debugger and build. Be patient!

Outline of a thunder back-end

1. Define symbolic names for the machine's registers, naming them according to assembly language conventions. On RPi, that means R0--R10, plus special names for FP, SP, PC, etc. On the MIPS, different classes of register have different naming schemes such as A0--A3, T0--T7, etc. Each symbolic name is a macro that expands to the relevant numeric value used in instruction encodings.
2. Establish the arrays of vm_reg structures that advertise available registers to the client. The Keiko translator rarely finds a use for more than half a dozen integer registers, and uses only one register as callee-save, so there's no need to provide access to every register if there are 32 of them.
3. For debugging, provide an array of register names, and routines that are capable of formatting addresses in various modes.
4. Define macros MNEM, etc., that are defined conditionally, and permit opcodes to be paired with a string for debugging. When debugging is turned off, the strings are silently removed during macro expansion. There are some tricks here related to the timing of macro expansion.
5. Define function op_rrr, etc., that both print the assembly language equivalent of an instruction and add it in binary form to the program. There will be one of these for each way of laying out the binary fields of an instruction: put another way, two instructions can share the same formatting routine if they differ only in the numeric value of the fixed parts of the instruction containing the opcode. Each of these routines starts with a call to vm_debug2 and ends with a call to vm_done. All code will be generated via one of these functions, so that for debugging we can generate a complete listing of the output code.
6. If, like the Pi, large constants are accessed by loading from an out-of-line table, then include here routines for managing the table. On a machine that develops large constants in a couple of instructions (lui / ori), there will be no need for such a table.
7. Routines that perform common functions in the way appropriate to the size of embedded constants: e.g., a routine move_immed that puts an arbitrary constant in a specified register, and const_reg that puts it in a scratch register such as ip on ARM or R1 on the MIPS. You can assume that const_reg won't be used twice in translating one instruction.
8. Routines like arith_signed that implement an operation with operands from a register and an arbitrary signed constant; this will put the constant in a register if it needs to do so, or will embed it an immediate field if it can.
9. Other routines that implement, e.g., loads and stores with unbounded offsets, using a scratch register if needed for a large offset.
10. Perhaps a register map that keeps track of what registers are used in a routine, to avoid saving registers that aren't used. This may not be needed for the MIPS, because there are relatively few callee-save registers anyway.
11. Implementation of the code generation interface. This consists of a family of routines with names like gen3rri – that one is for a three operand instruction where the operands are two registers and an integer constant. The heading of gen3rri is
    

void gen3rri(operation op, vmreg rega, vmreg regb, int c);

1. Inside each such routine, first access the fields rega->vr_reg to find the actual register numbers.
2. Use vm_debug1 to (optionally) print the Keiko instruction being assembled.
3. Use vm_space(0) to ensure space for an instruction. Using 0 as the argument makes sure of at least 32 bytes of space, which ought to be enough.
4. Next comes a big switch on the opcode, with each branch assembling a different kind of instruction, using the utility routines defined earlier to avoid repeated checking for special cases. Each arm of the switch should be a couple of lines at most.
5. Give the switch a default part so unimplemented instructions are caught, not silently ignored.
6. That completes each code generation routine.
7. There are routines vm_prelude and vm_postlude to generate the top and bottom of each function.
8. There's an additional routine vm_print that prints a target machine instruction in binary form (typically printing one word in hex in RISC machines), then returns the number of bytes printed. When debugging prints are on, the vm_done routine uses this to print the object code.

Note that, though they provide the interface for client code, the routines like vm_gen3rri are typically not called directly, but via the overload resolution code that appears at the end of vm.h. This allows the client to contain calls to an overloaded routine vm_gen, and calls the appropriate specific routine according to the number and types of the arguments. It uses a C11 (?) feature _Generic that is sparsely documented, as well as varargs macros for good measure. It's horrible, but I like it.

Resources

• The architecture manual describes the MIPS instruction set. Apparently, the Omega2 implements release 2 of the MIPS32 instruction set, but without the floating point instructions.
• A page describing the soft float library routines that come with GCC.
• The book See MIPS Run is a valuable guide to all things MIPS (LMGTFY).