src/org/xwt/mips/Compiler.java

   1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt.mips;
   3
   4 import java.util.*;
   5 import java.io.*;
   6
   7 // FEATURE: progress indicator
   8 // FEATURE: emit bytecode rather than .java code (for on-the-fly classloading without javac present in "real" JVMs
   9
  10 public class Compiler implements Registers {
  11
  12     private static StringBuffer runs = new StringBuffer();
  13     private static StringBuffer inits = new StringBuffer();
  14
  15     private static PrintStream out = System.out;
  16
  17     private static int indent;
  18     private static String indents[] = new String[16];
  19     static { String s=""; for(int i=0;i<indents.length;i++,s=s+"    ") indents[i] = s; }
  20     private static final void p() { out.println(); }
  21     private static final void p(String s) { out.println(indents[indent] + s); }
  22
  23     // FEATURE: This should probably provide some detail about where the excpetion happened (address, line numbers, etc)
  24     private static class CompilationException extends Exception { public CompilationException(String s) { super(s); } }
  25
  26     // Set this to true to enable fast memory access
  27     // When this is enabled a Java RuntimeException will be thrown when a page fault occures. When it is disabled
  28     // a FaultException will be throw which is easier to catch and deal with, however. as the name implies, this is slower
  29     private static boolean fastMem = true;
  30
  31     // This MUST be a power of two. If it is not horrible things will happen
  32     // NOTE: This value can be much higher without breaking the classfile
  33     // specs (around 1024) but Hotstop seems to do much better with smaller
  34     // methods.
  35     private static int MAX_INSN_PER_METHOD = 32;
  36
  37     // Don't touch this
  38     private static int MAX_BYTES_PER_METHOD = MAX_INSN_PER_METHOD*4;
  39     private static int METHOD_MASK = ~(MAX_BYTES_PER_METHOD-1);
  40
  41     // Store frequently used registers in local variables
  42     // Unfortunately this doesn't seem to speed things up much
  43     private static String[] freqRegs = { /*"r2", "r29", "r3", "r16", "r5", "r17", "r6", "r18", "r4", "r31", "r19"*/ };
  44
  45     // True to try to determine which case statement are needed and only include them
  46     private static boolean pruneCases = true;
  47
  48     // True to insert some code in the output to help diagnore compiler problems
  49     private final static boolean debugCompiler = false;
  50
  51     // True to print various statistics about the compilation
  52     private final static boolean printStats = true;
  53
  54     public static void main(String[] s) throws Exception {
  55
  56         if (s.length != 2) {
  57             System.err.println("usage: java " + Compiler.class.getName() + " <classname> <binary.mips>");
  58             System.exit(1);
  59         }
  60
  61         String packageName = null;
  62         String className = s[0];
  63         if (s[0].indexOf('.') != -1) {
  64             packageName = s[0].substring(0, s[0].lastIndexOf('.'));
  65             className = s[0].substring(s[0].lastIndexOf('.') + 1);
  66         }
  67
  68         ELF elf = new ELF(s[1]);
  69         if(elf.header.type != ELF.ELFHeader.ET_EXEC) throw new IOException("Binary is not an executable");
  70         if(elf.header.machine != ELF.ELFHeader.EM_MIPS) throw new IOException("Binary is not for the MIPS I Architecture");
  71
  72         p("// This file was generated by MipsToJava");
  73         if (packageName != null) p("package " + packageName + ";");
  74         p("public class " + className + " extends org.xwt.mips.Runtime {");
  75         p("");
  76         p("    // program counter");
  77         p("    private int pc = 0;");
  78         if(debugCompiler)
  79             p("    private int lastPC = 0;");
  80         p("");
  81         p("    // General Purpose registers");
  82         p("    private final static int r0 = 0;");
  83         p("    int r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0, r6 = 0, r7 = 0,");
  84         p("        r8 = 0, r9 = 0, r10 = 0, r11 = 0, r12 = 0, r13 = 0, r14 = 0, r15 = 0,");
  85         p("        r16 = 0, r17 = 0, r18 = 0, r19 = 0, r20 = 0, r21 = 0, r22 = 0, r23 = 0,");
  86         p("        r24 = 0, r25 = 0, r26 = 0, r27 = 0, r28 = 0, r29 = 0, r30 = 0, r31 = 0,");
  87         p("        hi = 0, lo = 0;");
  88         p("    // FP registers");
  89         p("    private int f0 = 0, f1 = 0, f2 = 0, f3 = 0, f4 = 0, f5 = 0, f6 = 0, f7 = 0,");
  90         p("        f8 = 0, f9 = 0, f10 = 0, f11 = 0, f12 = 0, f13 = 0, f14 = 0, f15 = 0,");
  91         p("        f16 = 0, f17 = 0, f18 = 0, f19 = 0, f20 = 0, f21 = 0, f22 = 0, f23 = 0,");
  92         p("        f24 = 0, f25 = 0, f26 = 0, f27 = 0, f28 = 0, f29 = 0, f30 = 0, f31 = 0;");
  93         p("    // FP Control Register");
  94         p("    private int fcsr = 0;");
  95         p("");
  96         indent++;
  97         // These should all be inlind by javac
  98         p("private final void setFC(boolean b) { fcsr = (fcsr&~0x800000) | (b ? 0x800000 : 0x000000); }");
  99         p("private final int roundingMode() { return fcsr & 3; /* bits 0-1 */ }");
 100         indent--;
 101
 102         Set jumpableAddresses = null;
 103         if(pruneCases) {
 104             // Find all possible branches
 105             jumpableAddresses = new HashSet();
 106
 107             jumpableAddresses.add(new Integer(elf.header.entry));
 108
 109             ELF.SHeader text = elf.sectionWithName(".text");
 110             if(text == null) throw new Error("No .text segment");
 111             findBranchesInText(text.addr,new DataInputStream(text.getInputStream()),text.size,jumpableAddresses);
 112
 113             findBranchesInSymtab(elf.getSymtab(),jumpableAddresses);
 114
 115             for(int i=0;i<elf.sheaders.length;i++) {
 116                 ELF.SHeader sheader = elf.sheaders[i];
 117                 String name = sheader.name;
 118                 // if this section doesn't get loaded into our address space don't worry about it
 119                 if(sheader.addr == 0x0) continue;
 120                 if(name.equals(".data") || name.equals(".sdata") || name.equals(".rodata") || name.equals(".ctors") || name.equals(".dtors"))
 121                     findBranchesInData(new DataInputStream(sheader.getInputStream()),sheader.size,jumpableAddresses,text.addr,text.addr+text.size);
 122             }
 123         }
 124
 125         // Generate main body functions
 126         int highestAddr = 0;
 127         indent=1;
 128         for(int i=0;i<elf.sheaders.length;i++) {
 129             ELF.SHeader sheader = elf.sheaders[i];
 130             String name = sheader.name;
 131             // if this section doesn't get loaded into our address space don't worry about it
 132             if(sheader.addr == 0x0) continue;
 133
 134             highestAddr = Math.max(highestAddr, sheader.addr + sheader.size);
 135
 136             if(name.equals(".text")) {
 137                 emitText(sheader.addr, new DataInputStream(sheader.getInputStream()),sheader.size,jumpableAddresses);
 138                 endMethod(nextEmitTextAddr);
 139             } else if(name.equals(".data") || name.equals(".sdata") || name.equals(".rodata") || name.equals(".ctors") || name.equals(".dtors")) {
 140                 emitData(sheader.addr, new DataInputStream(sheader.getInputStream()), sheader.size,name.equals(".rodata"));
 141             } else if(name.equals(".bss") || name.equals(".sbss")) {
 142                 if(sheader.entsize != 0) throw new CompilationException("bss segment has data!");
 143                 emitBSS(sheader.addr,sheader.size);
 144             } else {
 145                 throw new CompilationException("Unknown segment: " + name);
 146             }
 147         }
 148         indent = 0;
 149
 150         p("    public " + className + "() throws FaultException {");
 151         if(fastMem) {
 152             p("        super(false); // don't allow empty pages");
 153             p("        if(PAGE_SIZE != " + toHex(Runtime.PAGE_SIZE) + ") throw new Error(\"Runtime.PAGE_SIZE mismatch\");");
 154         } else {
 155             p("        super(true); // allow empty pages");
 156         }
 157         p("        // init data");
 158         p("        entryPoint = " + toHex(elf.header.entry) + ";");
 159         p(inits.toString());
 160         p("        brk = (" + toHex(highestAddr) + "+PAGE_SIZE-1) >>> PAGE_SHIFT;");
 161         p("        state = INITIALIZED;");
 162         p("    }");
 163         p("");
 164         p();
 165         p("    public static void main(String[] javaArgs) throws Exception {");
 166         p("        String[] args = new String[javaArgs.length+1];");
 167         p("        System.arraycopy(javaArgs,0,args,1,javaArgs.length);");
 168         p("        args[0] = \"" + className + "\";");
 169         p("        " + className + " me = new " + className + "();");
 170         p("        // User data");
 171         p("        int addr = me.sbrk(PAGE_SIZE);");
 172         p("        for(int i=0;i<10;i++) {");
 173         p("            String s = \"User Info item: \" + (i+1) + \"\\0\";");
 174         p("            byte[] b = s.getBytes(\"US-ASCII\");");
 175         p("            me.copyout(b,addr,b.length);");
 176         p("            me.setUserInfo(i,addr);");
 177         p("            addr += b.length;");
 178         p("        }");
 179         p("        // End user data");
 180         p("        int status = me.run(args);");
 181         p("        System.err.println(\"Exit status: \" + status);");
 182         p("        System.exit(status);");
 183         p("        }");
 184         p();
 185         p("    protected void _start(int pc) {");
 186         p("        // set the stack pointer");
 187                 p("        r26 = STUFF_BASE;");
 188                 p("        r27 = PAGE_SIZE;");
 189         p("        r29 = INITIAL_SP;");
 190         p("        // set the \"return address\" from _start to point at the \"magic exit address\" (0xdeadbeef)");
 191         p("        r31 = 0xdeadbeef;");
 192         p("        this.pc = pc;");
 193         p("    }");
 194
 195         p();
 196         p("    protected void _execute() throws ExecutionException { trampoline(); }");
 197         p();
 198         p("    private final void trampoline() throws ExecutionException {");
 199         p("        boolean finished = false;");
 200         p("        while(!finished) {");
 201         p("            switch(this.pc & " + toHex(~(MAX_BYTES_PER_METHOD-1)) + ") {");
 202         p(runs.toString());
 203         p("                default: throw new Error(\"invalid address 0x\" + Long.toString(this.pc&0xffffffffL,16));");
 204         p("            }");
 205         p("        }");
 206         p("    }");
 207         p("}");
 208     }
 209
 210     private static int startOfMethod = 0;
 211     private static int endOfMethod = 0;
 212
 213     private static void startMethod(int addr) {
 214         addr &= ~(MAX_BYTES_PER_METHOD-1);
 215         endOfMethod = addr + MAX_BYTES_PER_METHOD;
 216         String methodName = "run_" + Long.toString(addr & 0xffffffffL, 16);
 217         runs.append(indents[4] + "case " + toHex(addr) + ": finished = !" + methodName + "(); break;\n");
 218         p("private final boolean " + methodName + "() throws ExecutionException { /"+"* " + toHex(addr) + " - " + toHex(endOfMethod) + " *" + "/");
 219         indent++;
 220         p("int addr, tmp;");
 221         for(int i=0;i<freqRegs.length;i++)
 222             p("int " + freqRegs[i] + " = this." + freqRegs[i] + ";");
 223         p("for(;;) {");
 224         indent++;
 225         p("switch(pc) {");
 226         indent++;
 227         startOfMethod = addr;
 228
 229     }
 230     private static void endMethod() { endMethod(endOfMethod); }
 231     private static void endMethod(int lastAddr) {
 232         if(startOfMethod == 0) return;
 233         // This isn't strictly necessary; its just here to work around unreachable code errors
 234         p("case " + toHex(lastAddr) + ":");
 235         indent++;
 236         p("pc=" + toHex(lastAddr) + ";");
 237         leaveMethod();
 238         indent--;
 239         if(debugCompiler)
 240             p("default: throw new Error(\"invalid address 0x\" + Long.toString(pc&0xffffffffL,16)  + \" (got here from 0x\" + Long.toString(lastPC&0xffffffffL,16)+\")\");");
 241         else
 242             p("default: throw new Error(\"invalid address 0x\" + Long.toString(pc&0xffffffffL,16));");
 243         indent--;
 244         p("}"); // end switch
 245         p("/* NOT REACHED */");
 246         indent--;
 247         p("}"); // end for
 248         indent--;
 249         p("}"); // end method
 250         endOfMethod = 0;
 251     }
 252
 253     private static void branch(int pc, int target) {
 254         if(debugCompiler)
 255             p("lastPC = " + toHex(pc) + ";");
 256         p("pc=" + toHex(target) + ";");
 257         if((pc&METHOD_MASK) == (target&METHOD_MASK))
 258             p("continue;");
 259         else
 260             leaveMethod();
 261     }
 262
 263     private static void leaveMethod() { leaveMethod(true); }
 264     private static void leaveMethod(boolean cont) {
 265         for(int i=0;i<freqRegs.length;i++)
 266             p("this." + freqRegs[i] + " = " + freqRegs[i] + ";");
 267         p("return " + (cont?"true":"false") + ";");
 268     }
 269
 270     private static int nextEmitTextAddr = -1;
 271     private static void emitText(int addr, DataInputStream dis, int size, Set jumpableAddresses) throws CompilationException,IOException {
 272         if(addr < nextEmitTextAddr) throw new CompilationException("Out of order sections");
 273         if((addr&3)!=0 || (size&3)!=0) throw new CompilationException("Section on weird boundaries");
 274         int count = size/4;
 275         int nextInsn = dis.readInt();
 276         if(nextInsn == -1) throw new Error("Actually read -1 at " + toHex(addr));
 277         int insn;
 278
 279         for(int i=0;i<count;i++,addr+=4) {
 280             insn = nextInsn;
 281             nextInsn = (i == count-1) ? -1 : dis.readInt();
 282             if(addr >= endOfMethod) { endMethod(); startMethod(addr); }
 283             if(jumpableAddresses==null || addr == startOfMethod || jumpableAddresses.contains(new Integer(addr))) {
 284                 p("case " + toHex(addr) + ":");
 285                 unreachable = false;
 286             } else if(unreachable) {
 287                 continue;
 288             } else if(debugCompiler) {
 289                 p("/" + "* pc = " + toHex(addr) + "*" + "/");
 290             }
 291             indent++;
 292             emitInstruction(addr,insn,nextInsn);
 293             indent--;
 294         }
 295         nextEmitTextAddr = addr;
 296         dis.close();
 297     }
 298
 299     private static int initDataCount = 0;
 300     private static void emitData(int addr, DataInputStream dis, int size, boolean readOnly) throws CompilationException,IOException {
 301         if((addr&3)!=0 || (size&3)!=0) throw new CompilationException("Section on weird boundaries");
 302         int count = size/4;
 303         String varname =  "_data" + (++initDataCount);
 304         p("private final static int[] " + varname +  " = {");
 305         indent++;
 306         for(int i=0;i<count;) {
 307             StringBuffer sb = new StringBuffer();
 308             for(int j=0;j<8 && i<count;j++,i++) {
 309                 sb.append(toHex8(dis.readInt()));
 310                 if(i!=count-1) sb.append(",");
 311             }
 312             p(sb.toString());
 313         }
 314         indent--;
 315         p("};");
 316         inits.append(indents[2] + "initPages(" + varname + "," + toHex(addr) + "," + (readOnly?"true":"false") + ");\n");
 317         dis.close();
 318     }
 319
 320     private static int initBSSCount = 0;
 321     private static void emitBSS(int addr, int size) throws CompilationException,IOException {
 322         if((addr&3)!=0 || (size&3)!=0) throw new CompilationException("Section on weird boundaries");
 323         int count = size/4;
 324         inits.append(indents[2] + "clearPages(" + toHex(addr) + "," + toHex(count) + ");\n");
 325     }
 326
 327     private static void findBranchesInSymtab(ELF.Symtab symtab, Set jumps) {
 328         ELF.Symbol[] symbols = symtab.symbols;
 329         int n=0;
 330         for(int i=0;i<symbols.length;i++) {
 331             ELF.Symbol s = symbols[i];
 332             if(s.type == ELF.Symbol.STT_FUNC) {
 333                 //System.err.println("Adding symbol: " + s.name + " at " + toHex(s.addr));
 334                 if(jumps.add(new Integer(s.addr))) n++;
 335             }
 336         }
 337         if(printStats) System.err.println("Found " + n + " additional possible branch targets in Symtab");
 338     }
 339
 340     private static void findBranchesInText(int addr, DataInputStream dis, int size, Set jumps) throws IOException {
 341         int count = size/4;
 342         int pc = addr;
 343         int n=0;
 344
 345         for(int i=0;i<count;i++,pc+=4) {
 346             int insn = dis.readInt();
 347             int op = (insn >>> 26) & 0xff;
 348             int rs = (insn >>> 21) & 0x1f;
 349             int rt = (insn >>> 16) & 0x1f;
 350             int signedImmediate = (insn << 16) >> 16;
 351             int branchTarget = signedImmediate;
 352             int jumpTarget = (insn & 0x03ffffff);
 353             int subcode = insn & 0x3f;
 354
 355             switch(op) {
 356                 case 0:
 357                     switch(subcode) {
 358                         case 9: // JALR
 359                             if(jumps.add(new Integer(pc+8))) n++; // return address
 360                             break;
 361                         case 12: // SYSCALL
 362                             if(jumps.add(new Integer(pc+4))) n++;
 363                             break;
 364                     }
 365                     break;
 366                 case 1:
 367                     switch(rt) {
 368                         case 16: // BLTZAL
 369                         case 17: // BGTZAL
 370                             if(jumps.add(new Integer(pc+8))) n++; // return address
 371                             // fall through
 372                         case 0: // BLTZ
 373                         case 1: // BGEZ
 374                             if(jumps.add(new Integer(pc+branchTarget*4+4))) n++;
 375                             break;
 376                     }
 377                     break;
 378                 case 3: // JAL
 379                     if(jumps.add(new Integer(pc+8))) n++; // return address
 380                     // fall through
 381                 case 2: // J
 382                     if(jumps.add(new Integer((pc&0xf0000000)|(jumpTarget << 2)))) n++;
 383                     break;
 384                 case 4: // BEQ
 385                 case 5: // BNE
 386                 case 6: // BLEZ
 387                 case 7: // BGTZ
 388                     if(jumps.add(new Integer(pc+branchTarget*4+4))) n++;
 389                     break;
 390                 case 17: // FPU Instructions
 391                     switch(rs) {
 392                         case 8: // BC1F, BC1T
 393                             if(jumps.add(new Integer(pc+branchTarget*4+4))) n++;
 394                             break;
 395                     }
 396                     break;
 397             }
 398         }
 399         dis.close();
 400         if(printStats) System.err.println("Found " + n + " additional possible branch targets in Text segment");
 401     }
 402
 403     private static void findBranchesInData(DataInputStream dis, int size, Set jumps, int textStart, int textEnd) throws IOException {
 404         int count = size/4;
 405         int n=0;
 406         for(int i=0;i<count;i++) {
 407             int word = dis.readInt();
 408             if((word&3)==0 && word >= textStart && word < textEnd) {
 409                 if(jumps.add(new Integer(word))) n++;
 410             }
 411         }
 412         dis.close();
 413         if(n>0 && printStats) System.err.println("Found " + n + " additional possible branch targets in Data segment");
 414     }
 415
 416     private static boolean unreachable = false;
 417
 418     private static void emitInstruction(int pc, int insn, int nextInsn) throws IOException,CompilationException {
 419         if(insn == -1) throw new Error("insn is -1");
 420
 421         int op = (insn >>> 26) & 0xff;                 // bits 26-31
 422         int rs = (insn >>> 21) & 0x1f;                 // bits 21-25
 423         int rt = (insn >>> 16) & 0x1f;                 // bits 16-20
 424         int ft = (insn >>> 16) & 0x1f;
 425         int rd = (insn >>> 11) & 0x1f;                 // bits 11-15
 426         int fs = (insn >>> 11) & 0x1f;
 427         int shamt = (insn >>> 6) & 0x1f;               // bits 6-10
 428         int fd = (insn >>> 6) & 0x1f;
 429         int subcode = insn & 0x3f;                     // bits 0-5
 430
 431         int jumpTarget = (insn & 0x03ffffff);          // bits 0-25
 432         int unsignedImmediate = insn & 0xffff;
 433         int signedImmediate = (insn << 16) >> 16;
 434         int branchTarget = signedImmediate;
 435
 436         int tmp, addr; // temporaries
 437
 438         //if(pc%64==0) p("System.err.println(\"Executing: " + toHex(pc) + "\");");
 439         //p("/" + "*" + (pc == -1 ? "Delay Slot"  : toHex(pc)) + " *" + "/ ");
 440         if(pc==-1) p("/" + "* Next insn is delay slot *" + "/ ");
 441
 442         switch(op) {
 443             case 0: {
 444                 switch(subcode) {
 445                     case 0: // SLL
 446                         if(insn == 0)
 447                             p("/* NOOP */");
 448                         else
 449                             p( "r"+rd+" = r"+rt+" << "+shamt+";");
 450                         break;
 451                     case 2: // SRL
 452                         p( "r"+rd+" = r"+rt+" >>> "+shamt+";");
 453                         break;
 454                     case 3: // SRA
 455                         p( "r"+rd+" = r"+rt+" >> "+shamt+";");
 456                         break;
 457                     case 4: // SLLV
 458                         p( "r"+rd+" = r"+rt+" << (r"+rs+"&0x1f);");
 459                         break;
 460                     case 6: // SRLV
 461                         p( "r"+rd+" = r"+rt+" >>> (r"+rs+"&0x1f);");
 462                         break;
 463                     case 7: // SRAV
 464                         p( "r"+rd+" = r"+rt+" >> (r"+rs+"&0x1f);");
 465                         break;
 466                     case 8: // JR
 467                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 468                         emitInstruction(-1,nextInsn,-1);
 469                         if(debugCompiler) p("lastPC = " + toHex(pc) + ";");
 470                         p("pc=r" + rs + ";");
 471                         leaveMethod();
 472                         unreachable = true;
 473                         break;
 474                     case 9: // JALR
 475                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 476                         emitInstruction(-1,nextInsn,-1);
 477                         if(debugCompiler) p("lastPC = " + toHex(pc) + ";");
 478                         p("pc=r" + rs + ";");
 479                         p("r" + RA + "=" + toHex(pc+8 /*skip this insn and delay slot*/) + ";");
 480                         leaveMethod();
 481                         unreachable = true;
 482                         break;
 483                     case 12: // SYSCALL
 484                         p( "r"+V0+" = syscall(r"+V0+",r"+A0+",r"+A1+",r"+A2+",r"+A3+");");
 485                         p("if (state != RUNNING) {");
 486                             indent++;
 487                             p("pc = " + toHex(pc+4) + ";");
 488                             leaveMethod(false);
 489                             indent--;
 490                         p("}");
 491                         break;
 492                     case 13: // BREAK
 493                         p( "throw new ExecutionException(\"Break\");");
 494                         break;
 495                     case 16: // MFHI
 496                         p( "r"+rd+" = hi;");
 497                         break;
 498                     case 17: // MTHI
 499                         p( "hi = r"+rs+";");
 500                         break;
 501                     case 18: // MFLO
 502                         p( "r"+rd+" = lo;");
 503                         break;
 504                     case 19: // MTLO
 505                         p( "lo = r"+rs+";");
 506                         break;
 507                     case 24: // MULT
 508                         p( "{ long hilo = (long)(r"+rs+") * ((long)r"+rt+"); " +
 509                              "hi = (int) (hilo >>> 32); " +
 510                              "lo = (int) hilo; }");
 511                         break;
 512                     case 25: // MULTU
 513                         p( "{ long hilo = (r"+rs+" & 0xffffffffL) * (r"+rt+" & 0xffffffffL); " +
 514                              "hi = (int) (hilo >>> 32); " +
 515                              "lo = (int) hilo; } ");
 516                         break;
 517                     case 26: // DIV
 518                         p( "hi = r"+rs+"%r"+rt+"; lo = r"+rs+"/r"+rt+";");
 519                         break;
 520                     case 27: // DIVU
 521                         p( "hi = (int)((r"+rs+" & 0xffffffffL) % (r"+rt+" & 0xffffffffL)); " +
 522                              "lo = (int)((r"+rs+" & 0xffffffffL) / (r"+rt+" & 0xffffffffL));");
 523                         break;
 524                     case 32: // ADD
 525                         throw new CompilationException("ADD (add with oveflow trap) not suported");
 526                         /*This must trap on overflow
 527                         p( "r"+rd+" = r"+rs+" + r"+rt+";");
 528                         break;*/
 529                     case 33: // ADDU
 530                         p( "r"+rd+" = r"+rs+" + r"+rt+";");
 531                         break;
 532                     case 34: // SUB
 533                         throw new CompilationException("SUB (add with oveflow trap) not suported");
 534                         /*This must trap on overflow
 535                         p( "r"+rd+" = r"+rs+" - r"+rt+";");
 536                         break;*/
 537                     case 35: // SUBU
 538                         p( "r"+rd+" = r"+rs+" - r"+rt+";");
 539                         break;
 540                     case 36: // AND
 541                         p( "r"+rd+" = r"+rs+" & r"+rt+";");
 542                         break;
 543                     case 37: // OR
 544                         p( "r"+rd+" = r"+rs+" | r"+rt+";");
 545                         break;
 546                     case 38: // XOR
 547                         p( "r"+rd+" = r"+rs+" ^ r"+rt+";");
 548                         break;
 549                     case 39: // NOR
 550                         p( "r"+rd+" = ~(r"+rs+" | r"+rt+");");
 551                         break;
 552                     case 42: // SLT
 553                         p( "r"+rd+" = r"+rs+" < r"+rt+" ? 1 : 0;");
 554                         break;
 555                     case 43: // SLTU
 556                         p( "r"+rd+" = ((r"+rs+" & 0xffffffffL) < (r"+rt+" & 0xffffffffL)) ? 1 : 0;");
 557                         break;
 558                     default:
 559                         throw new RuntimeException("Illegal instruction 0/" + subcode);
 560                 }
 561                 break;
 562             }
 563             case 1: {
 564                 switch(rt) {
 565                     case 0: // BLTZ
 566                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 567                         p("if(r" + rs + " < 0) {");
 568                             indent++;
 569                             emitInstruction(-1,nextInsn,-1);
 570                             branch(pc,pc+branchTarget*4+4);
 571                             indent--;
 572                         p("}");
 573                         break;
 574                     case 1: // BGEZ
 575                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 576                         p("if(r" + rs + " >= 0) {");
 577                             indent++;
 578                             emitInstruction(-1,nextInsn,-1);
 579                             branch(pc,pc+branchTarget*4+4);
 580                             indent--;
 581                         p("}");
 582                         break;
 583                     case 16: // BLTZAL
 584                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 585                         p("if(r" + rs + " < 0) {");
 586                             indent++;
 587                             emitInstruction(-1,nextInsn,-1);
 588                             p("r" + RA + "=" + toHex(pc+8 /*skip this insn and delay slot*/) + ";");
 589                             branch(pc,pc+branchTarget*4+4);
 590                             indent--;
 591                         p("}");
 592                         break;
 593                     case 17: // BGEZAL
 594                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 595                         p("if(r" + rs + " >= 0) {");
 596                             indent++;
 597                             emitInstruction(-1,nextInsn,-1);
 598                             p("r" + RA + "=" + toHex(pc+8 /*skip this insn and delay slot*/) + ";");
 599                             branch(pc,pc+branchTarget*4+4);
 600                             indent--;
 601                         p("}");
 602                         break;
 603                     default:
 604                         throw new RuntimeException("Illegal Instruction 1/" + rt);
 605                 }
 606                 break;
 607             }
 608             case 2: { // J
 609                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 610                 emitInstruction(-1,nextInsn,-1);
 611                 branch(pc,(pc&0xf0000000)|(jumpTarget << 2));
 612                 unreachable = true;
 613                 break;
 614             }
 615             case 3: { // JAL
 616                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 617                 emitInstruction(-1,nextInsn,-1);
 618                 p("r" + RA + "=" + toHex(pc+8 /*skip this insn and delay slot*/) + ";");
 619                 branch(pc, (pc&0xf0000000)|(jumpTarget << 2));
 620                 unreachable = true;
 621                 break;
 622             }
 623             case 4: // BEQ
 624                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 625                 p("// BEQ");
 626                 p("if(r" + rs + " == r" + rt + ") {");
 627                     indent++;
 628                     emitInstruction(-1,nextInsn,-1);
 629                     branch(pc,pc+branchTarget*4+4);
 630                     indent--;
 631                 p("}");
 632                 break;
 633             case 5: // BNE
 634                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 635                 p("if(r" + rs + " != r" + rt + ") {");
 636                     indent++;
 637                     emitInstruction(-1,nextInsn,-1);
 638                     branch(pc,pc+branchTarget*4+4);
 639                     indent--;
 640                 p("}");
 641                 break;
 642             case 6: //BLEZ
 643                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 644                 p("if(r" + rs + " <= 0) {");
 645                     indent++;
 646                     emitInstruction(-1,nextInsn,-1);
 647                     branch(pc,pc+branchTarget*4+4);
 648                     indent--;
 649                 p("}");
 650                 break;
 651             case 7: //BGTZ
 652                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 653                 p("if(r" + rs + " > 0) {");
 654                     indent++;
 655                     emitInstruction(-1,nextInsn,-1);
 656                     branch(pc,pc+branchTarget*4+4);
 657                     indent--;
 658                 p("}");
 659                 break;
 660             case 8: // ADDI
 661                 p( "r"+rt+" = r"+rs+" + "+signedImmediate +";");
 662                 break;
 663             case 9: // ADDIU
 664                 p( "r"+rt+" = r"+rs+" + "+signedImmediate+";");
 665                 break;
 666             case 10: // SLTI
 667                 p( "r"+rt+" = r"+rs+" < "+signedImmediate+" ? 1 : 0;");
 668                 break;
 669             case 11: // SLTIU
 670                 p( "r"+rt+" = (r"+rs+"&0xffffffffL) < ("+unsignedImmediate+"&0xffffffffL) ? 1 : 0;");
 671                 break;
 672             case 12: // ANDI
 673                 p( "r"+rt+" = r"+rs+" & "+unsignedImmediate+";");
 674                 break;
 675             case 13: // ORI
 676                 p( "r"+rt+" = r"+rs+" | "+unsignedImmediate+";");
 677                 break;
 678             case 14: // XORI
 679                 p( "r"+rt+" = r"+rs+" ^ "+unsignedImmediate+";");
 680                 break;
 681             case 15: // LUI
 682                 p( "r"+rt+" = "+unsignedImmediate+" << 16;");
 683                 break;
 684             case 16:
 685                 throw new CompilationException("TLB/Exception support not implemented");
 686             case 17: { // FPU
 687                 switch(rs) {
 688                     case 0: // MFC.1
 689                         p( "r"+rt+" = f"+rd+";");
 690                         break;
 691                     case 2: // CFC.1
 692                         if(fs != 31) throw new CompilationException("FCR " + fs + " unavailable");
 693                         p( "r"+rt+" = fcsr;");
 694                         break;
 695                     case 4: // MTC.1
 696                         p( "f"+rd+" = r"+rt+";");
 697                         break;
 698                     case 6: // CTC.1
 699                         if(fs != 31) throw new CompilationException("FCR " + fs + " unavailable");
 700                         p( "fcsr = r"+rt+";");
 701                         break;
 702                     case 8: {// BC1F, BC1T
 703                         tmp = (insn>>>16)&1;
 704                         p("//BC1F, BC1T");
 705                         p("if(((fcsr&0x800000)!=0) == (" + tmp + "!=0)) {");
 706                             indent++;
 707                             emitInstruction(-1,nextInsn,-1);
 708                             branch(pc,pc+branchTarget*4+4);
 709                             indent--;
 710                         p("}");
 711                         break;
 712                     }
 713                     case 16: {  // Single
 714                         switch(subcode) {
 715                             case 0: // ADD.S
 716                                 p(setFloat(fd,getFloat(fs)+"+"+getFloat(ft)));
 717                                 break;
 718                             case 1: // SUB.S
 719                                 p(setFloat(fd,getFloat(fs)+"-"+getFloat(ft)));
 720                                 break;
 721                             case 2: // MUL.S
 722                                 p(setFloat(fd,getFloat(fs)+"*"+getFloat(ft)));
 723                                 break;
 724                             case 3: // DIV.S
 725                                 p(setFloat(fd,getFloat(fs)+"/"+getFloat(ft)));
 726                                 break;
 727                             case 5: // ABS.S
 728                                 p(setFloat(fd,"Math.abs("+getFloat(fs)+")"));
 729                                 break;
 730                             case 6: // MOV.S
 731                                 p("f"+fd+" = f"+fs+"; // MOV.S");
 732                                 break;
 733                             case 7: // NEG.S
 734                                 p(setFloat(fd,"-"+getFloat(fs))); // FEATURE: just flip the sign bit
 735                                 break;
 736                             case 33: // CVT.D.S
 737                                 p(setDouble(fd,"(float)"+getFloat(fs)));
 738                                 break;
 739                             case 36: // CVT.W.D
 740                                 p("// CVT.W.D");
 741                                 p("switch(roundingMode()) {");
 742                                     indent++;
 743                                     p("case 0: f"+fd+" = (int)Math.floor("+getFloat(fs)+"+0.5); break; // Round to nearest");
 744                                     p("case 1: f"+fd+" = (int)"+getFloat(fs)+"; break; // Round towards zero");
 745                                     p("case 2: f"+fd+" = (int)Math.ceil("+getFloat(fs)+"); break; // Round towards plus infinity");
 746                                     p("case 3: f"+fd+" = (int)Math.floor("+getFloat(fs)+"); break; // Round towards minus infinity");
 747                                     indent--;
 748                                 p("}");
 749                                 break;
 750                             case 50: // C.EQ.D
 751                                 p("setFC("+getFloat(fs)+"=="+getFloat(ft)+");"); // FEATURE: just compare the ints, be sure things are normalized
 752                                 break;
 753                             case 60: // C.LT.D
 754                                 p("setFC("+getFloat(fs)+"<"+getFloat(ft)+");");
 755                                 break;
 756                             case 62: // C.LE.D
 757                                 p("setFC("+getFloat(fs)+"<="+getFloat(ft)+");");
 758                                 break;
 759                             default: throw new CompilationException("Invalid Instruction 17/" + rs + "/" + subcode);
 760                         }
 761                         break;
 762                     }
 763                     case 17: { // Double
 764                         switch(subcode) {
 765                             case 0: // ADD.D
 766                                 p(setDouble(fd,getDouble(fs)+"+"+getDouble(ft)));
 767                                 break;
 768                             case 1: // SUB.D
 769                                 p(setDouble(fd,getDouble(fs)+"-"+getDouble(ft)));
 770                                 break;
 771                             case 2: // MUL.D
 772                                 p(setDouble(fd,getDouble(fs)+"*"+getDouble(ft)));
 773                                 break;
 774                             case 3: // DIV.D
 775                                 p(setDouble(fd,getDouble(fs)+"/"+getDouble(ft)));
 776                                 break;
 777                             case 5: // ABS.D
 778                                 p(setDouble(fd,"Math.abs("+getDouble(fs)+")"));
 779                                 break;
 780                             case 6: // MOV.D
 781                                 p("f"+fd+" = f"+fs+";");
 782                                 p("f"+(fd+1)+" = f"+(fs+1)+";");
 783                                 break;
 784                             case 7: // NEG.D
 785                                 p(setDouble(fd,"-"+getDouble(fs))); // FEATURE: just flip the sign bit
 786                                 break;
 787                             case 32: // CVT.S.D
 788                                 p(setFloat(fd,"(float)"+getDouble(fs)));
 789                                 break;
 790                             case 36: // CVT.W.D
 791                                 p("// CVT.W.D");
 792                                 p("switch(roundingMode()) {");
 793                                     indent++;
 794                                     p("case 0: f"+fd+" = (int)Math.floor("+getDouble(fs)+"+0.5); break; // Round to nearest");
 795                                     p("case 1: f"+fd+" = (int)"+getDouble(fs)+"; break; // Round towards zero");
 796                                     p("case 2: f"+fd+" = (int)Math.ceil("+getDouble(fs)+"); break; // Round towards plus infinity");
 797                                     p("case 3: f"+fd+" = (int)Math.floor("+getDouble(fs)+"); break; // Round towards minus infinity");
 798                                     indent--;
 799                                 p("}");
 800                                 break;
 801                             case 50: // C.EQ.D
 802                                 p("setFC("+getDouble(fs)+"=="+getDouble(ft)+");"); // FEATURE: just compare the ints, be sure things are normalized
 803                                 break;
 804                             case 60: // C.LT.D
 805                                 p("setFC("+getDouble(fs)+"<"+getDouble(ft)+");");
 806                                 break;
 807                             case 62: // C.LE.D
 808                                 p("setFC("+getDouble(fs)+"<="+getDouble(ft)+");");
 809                                 break;
 810                             default: throw new CompilationException("Invalid Instruction 17/" + rs + "/" + subcode);
 811                         }
 812                         break;
 813                     }
 814                     case 20: { // Integer
 815                         switch(subcode) {
 816                             case 32: // CVT.S.W
 817                                 p(" // CVS.S.W");
 818                                 p(setFloat(fd,"((float)f"+fs+")"));
 819                                 break;
 820                             case 33: // CVT.D.W
 821                                 p("// CVT.D.W");
 822                                 p(setDouble(fd,"((double)f"+fs+")"));
 823                                 break;
 824                             default: throw new CompilationException("Invalid Instruction 17/" + rs + "/" + subcode);
 825                         }
 826                         break;
 827                     }
 828                     default:
 829                         throw new CompilationException("Invalid Instruction 17/" + rs);
 830                 }
 831                 break;
 832             }
 833             case 18: case 19:
 834                 throw new CompilationException("coprocessor 2 and 3 instructions not available");
 835             case 32: { // LB
 836                 p("addr=r" + rs +"+"+signedImmediate + ";");
 837                 memRead("addr&~3","tmp");
 838                 p("switch(addr&3) {");
 839                     indent++;
 840                     p("case 0: tmp = (tmp>>>24)&0xff; break;");
 841                     p("case 1: tmp = (tmp>>>16)&0xff; break;");
 842                     p("case 2: tmp = (tmp>>> 8)&0xff; break;");
 843                     p("case 3: tmp = (tmp>>> 0)&0xff; break;");
 844                     indent--;
 845                 p("}");
 846                 p("if((tmp&0x80)!=0) tmp |= 0xffffff00; // sign extend");
 847                 p("r"+rt+" = tmp;");
 848                 break;
 849             }
 850             case 33: { // LH
 851                 p("addr=r" + rs +"+"+signedImmediate + ";");
 852                 memRead("addr&~3","tmp");
 853                 p("switch(addr&2) {");
 854                     indent++;
 855                     p("case 0: tmp = (tmp>>>16)&0xffff; break;");
 856                     p("case 2: tmp = (tmp>>> 0)&0xffff; break;");
 857                     indent--;
 858                 p("}");
 859                 p("if((tmp&0x8000)!=0) tmp |= 0xffff0000; // sign extend");
 860                 p("r"+rt+" = tmp;");
 861                 break;
 862             }
 863             case 34: { // LWL;
 864                 p("addr=r" + rs +"+"+signedImmediate + ";");
 865                 memRead("addr&~3","tmp");
 866                 p("switch(addr&3) {");
 867                     indent++;
 868                     p("case 0: r"+rt+" = (r"+rt+"&0x00000000)|(tmp<< 0); break;");
 869                     p("case 1: r"+rt+" = (r"+rt+"&0x000000ff)|(tmp<< 8); break;");
 870                     p("case 2: r"+rt+" = (r"+rt+"&0x0000ffff)|(tmp<<16); break;");
 871                     p("case 3: r"+rt+" = (r"+rt+"&0x00ffffff)|(tmp<<24); break;");
 872                     indent--;
 873                 p("}");
 874                 break;
 875             }
 876             case 35: // LW
 877                 memRead("r" + rs +"+"+signedImmediate,"r"+rt);
 878                 break;
 879             case 36: { // LBU
 880                 p("addr=r" + rs +"+"+signedImmediate + ";");
 881                 memRead("addr&~3","tmp");
 882                 p("switch(addr&3) {");
 883                     indent++;
 884                     p("case 0: r"+rt+" = (tmp>>>24)&0xff; break;");
 885                     p("case 1: r"+rt+" = (tmp>>>16)&0xff; break;");
 886                     p("case 2: r"+rt+" = (tmp>>> 8)&0xff; break;");
 887                     p("case 3: r"+rt+" = (tmp>>> 0)&0xff; break;");
 888                     indent--;
 889                 p("}");
 890                 break;
 891             }
 892             case 37: { // LHU
 893                 p("addr=r" + rs +"+"+signedImmediate + ";");
 894                 memRead("addr&~3","tmp");
 895                 p("switch(addr&2) {");
 896                     indent++;
 897                     p("case 0: r"+rt+" = (tmp>>>16)&0xffff; break;");
 898                     p("case 2: r"+rt+" = (tmp>>> 0)&0xffff; break;");
 899                     indent--;
 900                 p("}");
 901                 break;
 902             }
 903             case 38: { // LWR
 904                 p("addr=r" + rs +"+"+signedImmediate + ";");
 905                 memRead("addr&~3","tmp");
 906                 p("switch(addr&3) {");
 907                     indent++;
 908                     p("case 0: r"+rt+" = (r"+rt+"&0xffffff00)|(tmp>>>24); break;");
 909                     p("case 1: r"+rt+" = (r"+rt+"&0xffff0000)|(tmp>>>16); break;");
 910                     p("case 2: r"+rt+" = (r"+rt+"&0xff000000)|(tmp>>> 8); break;");
 911                     p("case 3: r"+rt+" = (r"+rt+"&0x00000000)|(tmp>>> 0); break;");
 912                     indent--;
 913                 p("}");
 914                 break;
 915             }
 916             case 40: { // SB
 917                 p("// SB");
 918                 p("addr=r" + rs +"+"+signedImmediate + ";");
 919                 memRead("addr&~3","tmp");
 920                 p("switch(addr&3) {");
 921                     indent++;
 922                     p("case 0: tmp = (tmp&0x00ffffff) | ((r"+rt+"&0xff)<<24); break;");
 923                     p("case 1: tmp = (tmp&0xff00ffff) | ((r"+rt+"&0xff)<<16); break;");
 924                     p("case 2: tmp = (tmp&0xffff00ff) | ((r"+rt+"&0xff)<< 8); break;");
 925                     p("case 3: tmp = (tmp&0xffffff00) | ((r"+rt+"&0xff)<< 0); break;");
 926                     indent--;
 927                 p("}");
 928                 memWrite("addr&~3","tmp");
 929                 break;
 930             }
 931             case 41: { // SH
 932                 p("// SH");
 933                 p("addr=r" + rs +"+"+signedImmediate + ";");
 934                 memRead("addr&~3","tmp");
 935                 p("switch(addr&2) {");
 936                     indent++;
 937                     p("case 0: tmp = (tmp&0x0000ffff) | ((r"+rt+"&0xffff)<<16); break;");
 938                     p("case 2: tmp = (tmp&0xffff0000) | ((r"+rt+"&0xffff)<< 0); break;");
 939                     indent--;
 940                 p("}");
 941                 memWrite("addr&~3","tmp");
 942                 break;
 943             }
 944             case 42: { // SWL
 945                 p(" // SWL");
 946                 p("addr=r" + rs +"+"+signedImmediate + ";");
 947                 memRead("addr&~3","tmp");
 948                 p("switch(addr&3) {");
 949                     indent++;
 950                     p("case 0: tmp=(tmp&0x00000000)|(r"+rt+">>> 0); break;");
 951                     p("case 1: tmp=(tmp&0xff000000)|(r"+rt+">>> 8); break;");
 952                     p("case 2: tmp=(tmp&0xffff0000)|(r"+rt+">>>16); break;");
 953                     p("case 3: tmp=(tmp&0xffffff00)|(r"+rt+">>>24); break;");
 954                     indent--;
 955                 p("}");
 956                 memWrite("addr&~3","tmp");
 957                 break;
 958             }
 959             case 43: // SW
 960                 memWrite("r"+rs+"+"+signedImmediate,"r" + rt);
 961                 break;
 962             case 46: { // SWR
 963                 p(" // SWR");
 964                 p("addr=r" + rs +"+"+signedImmediate + ";");
 965                 memRead("addr&~3","tmp");
 966                 p("switch(addr&3) {");
 967                     indent++;
 968                     p("case 0: tmp=(tmp&0x00ffffff)|(r"+rt+"<<24); break;");
 969                     p("case 1: tmp=(tmp&0x0000ffff)|(r"+rt+"<<16); break;");
 970                     p("case 2: tmp=(tmp&0x000000ff)|(r"+rt+"<< 8); break;");
 971                     p("case 3: tmp=(tmp&0x00000000)|(r"+rt+"<< 0); break;");
 972                     indent--;
 973                 p("}");
 974                 memWrite("addr&~3","tmp");
 975                 break;
 976             }
 977             case 49: // LWC1
 978                 memRead("r"+rs+"+"+signedImmediate,"f"+rt);
 979                 break;
 980             case 57: // SWC1
 981                 memWrite("r"+rs+"+"+signedImmediate,"f"+rt);
 982                 break;
 983             default:
 984                 throw new CompilationException("Invalid Instruction: " + op + " at " + toHex(pc));
 985         }
 986     }
 987
 988     private static void memWrite(String addr, String target) {
 989         if(fastMem)
 990             p("writePages[("+addr+")>>>"+Runtime.PAGE_SHIFT+"][(("+addr+")>>>2)&"+toHex(Runtime.PAGE_WORDS-1)+"] = " + target + ";");
 991         else
 992             p("memWrite(" + addr + "," + target + ");");
 993
 994     }
 995
 996     private static void memRead(String addr, String target) {
 997         if(fastMem)
 998             p(target  + " = readPages[("+addr+")>>>"+Runtime.PAGE_SHIFT+"][(("+addr+")>>>2)&"+toHex(Runtime.PAGE_WORDS-1)+"];");
 999         else
1000             p(target + " = memRead(" + addr + ");");
1001     }
1002
1003     private static String getFloat(int r) { return "(Float.intBitsToFloat(f"+r+"))"; }
1004     private static String getDouble(int r) {
1005         return "(Double.longBitsToDouble(((f"+(r+1)+"&0xffffffffL) << 32) | (f"+r+"&0xffffffffL)))";
1006     }
1007     private static String setFloat(int r, String expr) { return "f"+r+"=Float.floatToRawIntBits("+expr+");"; }
1008     private static String setDouble(int r, String expr) {
1009         return "{ long l = Double.doubleToLongBits("+expr+"); "+
1010             "f"+(r+1)+" = (int)(l >>> 32); f"+r+" = (int)l; }";
1011     }
1012
1013     private final static String toHex(int n) { return "0x" + Long.toString(n & 0xffffffffL, 16); }
1014     private final static String toHex8(int n) {
1015         String s = Long.toString(n & 0xffffffffL, 16);
1016         StringBuffer sb = new StringBuffer("0x");
1017         for(int i=8-s.length();i>0;i--) sb.append('0');
1018         sb.append(s);
1019         return sb.toString();
1020     }
1021 }
1022