upstream/mips/org/xwt/mips/Compiler.java

   1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
   2
   3 package org.xwt.mips;
   4
   5 import java.util.*;
   6 import java.io.*;
   7
   8 // FEATURE: progress indicator
   9 // FEATURE: emit bytecode rather than .java code (for on-the-fly classloading without javac present in "real" JVMs
  10
  11 public class Compiler implements Registers {
  12
  13     /** Stores the "case r XXX: ... run_YYYY();" blocks generated by the emitText method/ */
  14     private StringBuffer runs = new StringBuffer();
  15     /** Stores the "initData" and "cleadData" calls generated by the emitData and emitBSS methods */
  16     private StringBuffer inits = new StringBuffer();
  17     /** Stores lines to go in the class scope */
  18     private StringBuffer classLevel = new StringBuffer();
  19
  20     /** The stream to write the compiled output to */
  21     private PrintWriter out;
  22
  23     /** The ELF binary being read */
  24     private ELF elf;
  25
  26     /** The name of the class beging generated */
  27     private String fullClassName;
  28
  29     /** The name of the binary this class is begin generated from */
  30     private String mipsBinary;
  31
  32     /** Used by the p() method to add indentation */
  33     private int indent;
  34
  35     /** Prints a blank line to the output stream */
  36     private void p() { out.println(); }
  37     /** prints the given string (indented by <i>indent</i>*4 spaces) to the output stream */
  38     private void p(String s) { out.println(indents[indent] + s); }
  39     private void pblock(StringBuffer sb) { out.print(sb.toString()); }
  40
  41     private static String indents[] = new String[16];
  42     static { String s=""; for(int i=0;i<indents.length;i++,s=s+"    ") indents[i] = s; }
  43
  44     /** Thrown when the compilation fails for some reason */
  45     private static class CompilationException extends Exception { public CompilationException(String s) { super(s); } }
  46
  47     // Set this to true to enable fast memory access
  48     // When this is enabled a Java RuntimeException will be thrown when a page fault occures. When it is disabled
  49     // a FaultException will be throw which is easier to catch and deal with, however. as the name implies, this is slower
  50     private boolean fastMem = true;
  51
  52     // This MUST be a power of two. If it is not horrible things will happen
  53     // NOTE: This value can be much higher without breaking the classfile
  54     // specs (around 1024) but Hotstop seems to do much better with smaller
  55     // methods.
  56     private int maxInsnPerMethod = 128;
  57
  58     // non-configurable
  59     private int maxBytesPerMethod;
  60     private int methodMask;
  61     private int methodShift;
  62     private void maxInsnPerMethodInit() throws CompilationException {
  63         if((maxInsnPerMethod&(maxInsnPerMethod-1)) != 0) throw new CompilationException("maxBytesPerMethod is not a power of two");
  64         maxBytesPerMethod = maxInsnPerMethod*4;
  65         methodMask = ~(maxBytesPerMethod-1);
  66         while(maxBytesPerMethod>>>methodShift != 1) methodShift++;
  67     }
  68
  69     // Store frequently used registers in local variables
  70     // Unfortunately this doesn't seem to speed things up much
  71     private String[] freqRegs = { /*"r2", "r29", "r3", "r16", "r5", "r17", "r6", "r18", "r4", "r31", "r19"*/ };
  72
  73     // True to try to determine which case statement are needed and only include them
  74     private boolean pruneCases = true;
  75
  76     private boolean assumeTailCalls = true;
  77
  78     private boolean optimizedMemcpy = true;
  79
  80     // True to insert some code in the output to help diagnore compiler problems
  81     private boolean debugCompiler = false;
  82
  83     // True to print various statistics about the compilation
  84     private boolean printStats = false;
  85
  86     // True to generate runtime statistics that slow execution down significantly
  87     private boolean runtimeStats = false;
  88
  89     private boolean supportCall = true;
  90
  91     private boolean nullPointerCheck = false;
  92
  93     private String runtimeClass = "org.xwt.mips.Runtime";
  94
  95     private String hashClass = "java.util.HashMap";
  96
  97     private boolean unixRuntime;
  98
  99     private boolean lessConstants = true;
 100
 101     private int pageSize = 4096;
 102     private int totalPages = 65536;
 103     private int pageShift;
 104     private boolean onePage;
 105
 106     private void pageSizeInit() throws CompilationException {
 107         try {
 108             Runtime.checkPageSize(pageSize,totalPages);
 109         } catch(IllegalArgumentException e) {
 110             throw new CompilationException(e.getMessage());
 111         }
 112         while(pageSize>>>pageShift != 1) pageShift++;
 113     }
 114
 115     /** The address of the memcpy function in the binary (used for optimizedMemcpy) */
 116     private int memcpy;
 117
 118     /** The address of the memset function in the binary (used for optimizedMemcpy) */
 119     private int memset;
 120
 121     private static void usage() {
 122         System.err.println("Usage: java Compiler [-outfile output.java] [-o options] [-dumpoptions] <classname> <binary.mips>");
 123         System.err.println("-o takes mount(8) like options and can be specified multiple times");
 124         System.err.println("Available options:");
 125         for(int i=0;i<options.length;i+=2)
 126             System.err.print(options[i] + ": " + wrapAndIndent(options[i+1],18-2-options[i].length(),18,62));
 127         System.exit(1);
 128     }
 129
 130     public static void main(String[] args) throws Exception {
 131         String outfile = null;
 132         String o = null;
 133         String className = null;
 134         String mipsBinary = null;
 135         boolean dumpOptions = false;
 136         int arg = 0;
 137         while(args.length-arg > 0) {
 138             if(args[arg].equals("-outfile")) {
 139                 arg++;
 140                 if(arg==args.length) usage();
 141                 outfile = args[arg];
 142             } else if(args[arg].equals("-o")) {
 143                 arg++;
 144                 if(arg==args.length) usage();
 145                 if(o==null || o.length() == 0)
 146                     o = args[arg];
 147                 else if(args[arg].length() != 0)
 148                     o += "," + args[arg];
 149             } else if(args[arg].equals("-dumpoptions")) {
 150                 dumpOptions = true;
 151             } else if(className == null) {
 152                 className = args[arg];
 153             } else if(mipsBinary == null) {
 154                 mipsBinary = args[arg];
 155             } else {
 156                 usage();
 157             }
 158             arg++;
 159         }
 160         if(className == null || mipsBinary == null) usage();
 161
 162         Writer w = outfile == null ? new OutputStreamWriter(System.out): new FileWriter(outfile);
 163
 164         try {
 165             Compiler comp = new Compiler(mipsBinary,className,w,o);
 166             if(dumpOptions) {
 167                 System.err.println("== Options ==");
 168                 for(int i=0;i<options.length;i+=2)
 169                     System.err.println(options[i] + ": " + comp.getOption(options[i]).get());
 170                 System.err.println("== End Options ==");
 171             }
 172             comp.go();
 173         } catch(CompilationException e) {
 174             System.err.println("Compiler Error: " + e.getMessage());
 175             System.exit(1);
 176         } finally {
 177             w.close();
 178         }
 179     }
 180
 181     public Compiler(String mipsBinary, String fullClassName, Writer w, String options) throws CompilationException, IOException {
 182         this.fullClassName = fullClassName;
 183         this.mipsBinary = mipsBinary;
 184         out = new PrintWriter(w);
 185
 186         parseOptions(options);
 187
 188         if(onePage && pageSize <= 4096) pageSize = 4*1024*1024;
 189         if(nullPointerCheck && !fastMem) throw new CompilationException("fastMem must be enabled for nullPointerCheck to be of any use");
 190         if(onePage && !fastMem) throw new CompilationException("fastMem must be enabled for onePage to be of any use");
 191         if(totalPages == 1 && !onePage) throw new CompilationException("totalPages == 1 and onePage is not set");
 192         if(onePage) totalPages = 1;
 193
 194         maxInsnPerMethodInit();
 195         pageSizeInit();
 196
 197         elf = new ELF(mipsBinary);
 198         if(elf.header.type != ELF.ELFHeader.ET_EXEC) throw new CompilationException("Binary is not an executable");
 199         if(elf.header.machine != ELF.ELFHeader.EM_MIPS) throw new CompilationException("Binary is not for the MIPS I Architecture");
 200         if(elf.ident.data != ELF.ELFIdent.ELFDATA2MSB) throw new CompilationException("Binary is not big endian");
 201     }
 202
 203     private boolean used;
 204     public void go() throws CompilationException, IOException {
 205         if(used) throw new Error("Compiler instances are good for one shot only");
 206         used = true;
 207
 208         String packageName;
 209         String className;
 210         if (fullClassName.indexOf('.') != -1) {
 211             packageName = fullClassName.substring(0, fullClassName.lastIndexOf('.'));
 212             className = fullClassName.substring(fullClassName.lastIndexOf('.') + 1);
 213         } else {
 214             className = fullClassName;
 215             packageName = null;
 216         }
 217
 218         // Get a copy of the symbol table in the elf binary
 219         ELF.Symtab symtab = elf.getSymtab();
 220         if(symtab == null) throw new CompilationException("Binary has no symtab (did you strip it?)");
 221         ELF.Symbol sym;
 222
 223         // Check for some functions we can override
 224         sym = symtab.getGlobalSymbol("memcpy");
 225         memcpy = sym == null ? -1 : sym.addr;
 226
 227         sym = symtab.getGlobalSymbol("memset");
 228         memset = sym == null ? -1 : sym.addr;
 229
 230         ELF.Symbol userInfo = symtab.getGlobalSymbol("user_info");
 231         ELF.Symbol gp = symtab.getGlobalSymbol("_gp");
 232         if(gp == null) throw new CompilationException("no _gp symbol (did you strip the binary?)");
 233
 234         p("/* This file was generated from " + mipsBinary + " by Mips2Java on " + dateTime() + " */");
 235         if (packageName != null) p("package " + packageName + ";");
 236         if(runtimeStats) p("import java.util.*;");
 237         p();
 238         if(unixRuntime && runtimeClass.startsWith("org.xwt.mips.")) runtimeClass = "org.xwt.mips.UnixRuntime";
 239         p("public class " + className + " extends " + runtimeClass + " {");
 240         indent++;
 241
 242         p("/* program counter */");
 243         p("private int pc = 0;");
 244         if(debugCompiler)
 245             p("private int lastPC = 0;");
 246         p();
 247         p("/* General Purpose registers */");
 248         p("private final static int r0 = 0;");
 249         p("private int      r1,  r2,  r3,  r4,  r5,  r6,  r7,");
 250         p("            r8,  r9,  r10, r11, r12, r13, r14, r15,");
 251         p("            r16, r17, r18, r19, r20, r21, r22, r23,");
 252         p("            r24, r25, r26, r27, r28, r29, r30, r31,");
 253         p("            hi = 0, lo = 0;");
 254         p("/* FP registers */");
 255         p("private int f0,  f1,  f2,  f3,  f4,  f5,  f6,  f7,");
 256         p("            f8,  f9,  f10, f11, f12, f13, f14, f15,");
 257         p("            f16, f17, f18, f19, f20, f21, f22, f23,");
 258         p("            f24, f25, f26, f27, f28, f29, f30, f31;");
 259         p("/* FP Control Register */");
 260         p("private int fcsr = 0;");
 261         p();
 262
 263         if(onePage) p("int[] page = readPages[0];");
 264
 265         Set jumpableAddresses = null;
 266         if(pruneCases) {
 267             // Find all possible branches
 268             jumpableAddresses = new HashSet();
 269
 270             jumpableAddresses.add(new Integer(elf.header.entry));
 271
 272             ELF.SHeader text = elf.sectionWithName(".text");
 273             if(text == null) throw new CompilationException("No .text segment");
 274             findBranchesInText(text.addr,new DataInputStream(text.getInputStream()),text.size,jumpableAddresses);
 275
 276             findBranchesInSymtab(symtab,jumpableAddresses);
 277
 278             for(int i=0;i<elf.sheaders.length;i++) {
 279                 ELF.SHeader sheader = elf.sheaders[i];
 280                 String name = sheader.name;
 281                 // if this section doesn't get loaded into our address space don't worry about it
 282                 if(sheader.addr == 0x0) continue;
 283                 if(name.equals(".data") || name.equals(".sdata") || name.equals(".rodata") || name.equals(".ctors") || name.equals(".dtors"))
 284                     findBranchesInData(new DataInputStream(sheader.getInputStream()),sheader.size,jumpableAddresses,text.addr,text.addr+text.size);
 285             }
 286         }
 287
 288         // Generate main body functions (run_XXXX() blocks, _data[] arrays, etc)
 289         int highestAddr = 0;
 290
 291         for(int i=0;i<elf.sheaders.length;i++) {
 292             ELF.SHeader sheader = elf.sheaders[i];
 293             String name = sheader.name;
 294             // if this section doesn't get loaded into our address space don't worry about it
 295             if(sheader.addr == 0x0) continue;
 296
 297             highestAddr = Math.max(highestAddr, sheader.addr + sheader.size);
 298
 299             if(name.equals(".text"))
 300                 emitText(sheader.addr, new DataInputStream(sheader.getInputStream()),sheader.size,jumpableAddresses);
 301             else if(name.equals(".data") || name.equals(".sdata") || name.equals(".rodata") || name.equals(".ctors") || name.equals(".dtors"))
 302                 emitData(sheader.addr, new DataInputStream(sheader.getInputStream()), sheader.size,name.equals(".rodata"));
 303             else if(name.equals(".bss") || name.equals(".sbss"))
 304                 emitBSS(sheader.addr,sheader.size);
 305             else
 306                 throw new CompilationException("Unknown segment: " + name);
 307         }
 308         p();
 309
 310         pblock(classLevel);
 311         p();
 312
 313         // Trampoline (dispatch calls to the appropriate run_XXX() methods
 314         p("private final void trampoline() throws ExecutionException {");
 315         indent++;
 316         p("while(state == RUNNING) {");
 317         indent++;
 318         p("switch(pc>>>" + methodShift+ ") {");
 319         indent++;
 320         pblock(runs);
 321         p("default: throw new ExecutionException(\"invalid address 0x\" + Long.toString(this.pc&0xffffffffL,16));");
 322         indent--; p("}");
 323         indent--; p("}");
 324         indent--; p("}");
 325         p();
 326
 327         // Constructor
 328         p("public " + className + "() {");
 329         indent++;
 330         p("super(" + pageSize + "," + totalPages + "," + (fastMem?"false":"true") + ");");
 331         p("entryPoint = " + toHex(elf.header.entry) + ";");
 332         if(userInfo != null) {
 333             p("userInfoBase=" + toHex(userInfo.addr) + ";");
 334             p("userInfoSize=" + userInfo.size + ";");
 335         }
 336         p("gp = " + toHex(gp.addr) + ";");
 337         if(onePage)
 338             p("brkAddr = " + toHex((highestAddr+4095)&~4095) + ";");
 339         else
 340             p("brkAddr = " + toHex((highestAddr+pageSize-1)&~(pageSize-1)) + ";");
 341         pblock(inits);
 342         p("state = INITIALIZED;");
 343         indent--;
 344         p("}");
 345         p();
 346
 347         // main() function
 348         p("public static void main(String[] javaArgs) throws Exception {");
 349         indent++;
 350         p("String[] args = new String[javaArgs.length+1];");
 351         p("System.arraycopy(javaArgs,0,args,1,javaArgs.length);");
 352         p("args[0] = \"" + className + "\";");
 353         p(className + " me = new " + className + "();");
 354         p("int status = me.run(args);");
 355         p("System.err.println(\"Exit status: \" + status);");
 356         if(runtimeStats) p("me.printStats();");
 357         p("System.exit(status);");
 358         indent--;
 359         p("}");
 360         p();
 361
 362         // Runtime abstract methods
 363         p("protected void _execute() throws ExecutionException { trampoline(); }");
 364         p();
 365
 366         p("protected void setCPUState(CPUState state) {");
 367         indent++;
 368         for(int i=1;i<32;i++) p("r" + i + "=state.r[" + i + "];");
 369         for(int i=0;i<32;i++) p("f" + i + "=state.f[" + i + "];");
 370         p("hi=state.hi; lo=state.lo; fcsr=state.fcsr;");
 371         p("pc=state.pc;");
 372         indent--;
 373         p("}");
 374         p("protected CPUState getCPUState() {");
 375         indent++;
 376         p("CPUState state = new CPUState();");
 377         for(int i=1;i<32;i++) p("state.r[" + i + "]=r" + i+ ";");
 378         for(int i=0;i<32;i++) p("state.f[" + i + "]=f" + i +";");
 379         p("state.hi=hi; state.lo=lo; state.fcsr=fcsr;");
 380         p("state.pc=pc;");
 381         p("return state;");
 382         indent--;
 383         p("}");
 384         p();
 385
 386         if(supportCall) {
 387             p("private static " + hashClass + " symbols = new " + hashClass + "();");
 388             p("static {");
 389             indent++;
 390             ELF.Symbol[] symbols = symtab.symbols;
 391             for(int i=0;i<symbols.length;i++) {
 392                 ELF.Symbol s = symbols[i];
 393                 if(s.type == ELF.Symbol.STT_FUNC && s.binding == ELF.Symbol.STB_GLOBAL && (s.name.equals("_call_helper") || !s.name.startsWith("_")))
 394                     p("symbols.put(\"" + s.name + "\",new Integer(" + toHex(s.addr) + "));");
 395             }
 396             indent--;
 397             p("}");
 398             p("public int lookupSymbol(String symbol) { Integer i = (Integer) symbols.get(symbol); return i==null ? -1 : i.intValue(); }");
 399             p();
 400         }
 401
 402         // Runtime stats
 403         if(runtimeStats) {
 404             p("private HashMap counters = new HashMap();");
 405             p("private void inc(String k) { Long i = (Long)counters.get(k); counters.put(k,new Long(i==null ? 1 : i.longValue() + 1)); }");
 406             p("private void printStats() {");
 407             p(" Iterator i = new TreeSet(counters.keySet()).iterator();");
 408             p(" while(i.hasNext()) { Object o = i.next(); System.err.println(\"\" + o + \": \" + counters.get(o)); }");
 409             p("}");
 410             p();
 411         }
 412
 413         // Null pointer check helper function
 414         if(nullPointerCheck)  {
 415             p("private static void nullPointerCheck(int addr) throws ExecutionException {");
 416             indent++;
 417             if(onePage) p("if(addr < 65536)");
 418             else p(" if((addr>>>" + pageShift + ") < 16) ");
 419             indent++;
 420             p("throw new ExecutionException(\"Attempted to dereference a null pointer (0x\" + Long.toString(addr&0xffffffffL,16) + \")\");");
 421             indent-=2;
 422             p("}");
 423         }
 424
 425         indent--;
 426         p("}");
 427     }
 428
 429     private int startOfMethod = 0;
 430     private int endOfMethod = 0;
 431
 432     private void startMethod(int addr) {
 433         addr &= ~(maxBytesPerMethod-1);
 434         startOfMethod = addr;
 435         endOfMethod = addr + maxBytesPerMethod;
 436         String methodName = "run_" + Long.toString(addr & 0xffffffffL, 16);
 437         runs.append(indents[4] + "case " + toHex(addr>>>methodShift) + ": " + methodName + "(); break; \n");
 438         p("private final void " + methodName + "() throws ExecutionException { /"+"* " + toHex(addr) + " - " + toHex(endOfMethod) + " *" + "/");
 439         indent++;
 440         p("int addr, tmp;");
 441         for(int i=0;i<freqRegs.length;i++)
 442             p("int " + freqRegs[i] + " = this." + freqRegs[i] + ";");
 443         p("for(;;) {");
 444         indent++;
 445         p("switch(pc) {");
 446         indent++;
 447     }
 448
 449     private void endMethod() { endMethod(endOfMethod); }
 450     private void endMethod(int lastAddr) {
 451         if(startOfMethod == 0) return;
 452         // This isn't strictly necessary; its just here to work around unreachable code errors
 453         p("case " + toHex(lastAddr) + ":");
 454         indent++;
 455         p("pc=" + constant(lastAddr) + ";");
 456         leaveMethod();
 457         indent--;
 458         if(debugCompiler)
 459             p("default: throw new ExecutionException(\"invalid address 0x\" + Long.toString(pc&0xffffffffL,16)  + \" (got here from 0x\" + Long.toString(lastPC&0xffffffffL,16)+\")\");");
 460         else
 461             p("default: throw new ExecutionException(\"invalid address 0x\" + Long.toString(pc&0xffffffffL,16));");
 462         indent--;
 463         p("}"); // end switch
 464         p("/* NOT REACHED */");
 465         indent--;
 466         p("}"); // end for
 467         indent--;
 468         p("}"); // end method
 469         endOfMethod = startOfMethod = 0;
 470     }
 471
 472     private HashMap relativeAddrs = new HashMap();
 473     private String constant(int target) {
 474         if(target >= 4096 && lessConstants) {
 475             int n = target & ~1023;
 476             String var = "N_" + toHex8(n);
 477             if(relativeAddrs.get(new Integer(n)) == null) {
 478                 relativeAddrs.put(new Integer(n),Boolean.TRUE);
 479                 classLevel.append(indents[1] + "private static int " + var + " = " + toHex(n) + ";\n");
 480             }
 481             return "(" + var + " + " + toHex(target - n) + ")";
 482         } else {
 483             return toHex(target);
 484         }
 485     }
 486
 487     private void branch(int pc, int target) {
 488         if(debugCompiler) p("lastPC = " + toHex(pc) + ";");
 489         p("pc=" + constant(target) + ";");
 490         if(target == 0)
 491             p("throw new ExecutionException(\"Branch to addr 0x0\");");
 492         else if((pc&methodMask) == (target&methodMask))
 493             p("continue;");
 494         else if(assumeTailCalls)
 495             p("run_" +  Long.toString((target&methodMask)&0xffffffffL, 16) + "(); return;");
 496         else
 497             leaveMethod();
 498     }
 499
 500     private void leaveMethod() {
 501         for(int i=0;i<freqRegs.length;i++)
 502             p("this." + freqRegs[i] + " = " + freqRegs[i] + ";");
 503         p("return;");
 504     }
 505
 506     private boolean textDone;
 507     private void emitText(int addr, DataInputStream dis, int size, Set jumpableAddresses) throws CompilationException,IOException {
 508         if(textDone) throw new CompilationException("Multiple text segments");
 509         textDone = true;
 510
 511         if((addr&3)!=0 || (size&3)!=0) throw new CompilationException("Section on weird boundaries");
 512         int count = size/4;
 513         int nextInsn = dis.readInt();
 514         if(nextInsn == -1) throw new Error("Actually read -1 at " + toHex(addr));
 515         int insn;
 516
 517         for(int i=0;i<count;i++,addr+=4) {
 518             insn = nextInsn;
 519             nextInsn = (i == count-1) ? -1 : dis.readInt();
 520             if(addr >= endOfMethod) { endMethod(); startMethod(addr); }
 521             if(jumpableAddresses==null || addr == startOfMethod || jumpableAddresses.contains(new Integer(addr))) {
 522                 p("case " + toHex(addr) + ":");
 523                 unreachable = false;
 524             } else if(unreachable) {
 525                 continue;
 526             } else if(debugCompiler) {
 527                 p("/" + "* pc = " + toHex(addr) + "*" + "/");
 528             }
 529             indent++;
 530             emitInstruction(addr,insn,nextInsn);
 531             indent--;
 532         }
 533         endMethod(addr);
 534         p();
 535         dis.close();
 536     }
 537
 538     private int initDataCount = 0;
 539     private void emitData(int addr, DataInputStream dis, int size, boolean readOnly) throws CompilationException,IOException {
 540         if((addr&3)!=0 || (size&3)!=0) throw new CompilationException("Data section on weird boundaries");
 541         int last = addr + size;
 542         while(addr < last) {
 543             StringBuffer sb = new StringBuffer();
 544             int segSize = Math.min(size,28000); // must be a multiple of 56
 545             for(int i=0;i<segSize;i+=7) {
 546                 long l = 0;
 547                 for(int j=0;j<7;j++) {
 548                     l <<= 8;
 549                     byte b = (i+j < size) ? dis.readByte() : 1;
 550                     l |= (b & 0xffL);
 551                 }
 552                 for(int j=0;j<8;j++) {
 553                     char c = (char) ((l>>>(7*(7-j)))&0x7f);
 554                     if(c=='\n') sb.append("\\n");
 555                     else if(c=='\r') sb.append("\\r");
 556                     else if(c=='\\') sb.append("\\\\");
 557                     else if(c=='"') sb.append("\\\"");
 558                     else if(c >= 32 && c <= 126) sb.append(c);
 559                     else sb.append("\\" +  toOctal3(c));
 560                 }
 561             }
 562             String varname =  "_data" + (++initDataCount);
 563             p("private static final int[] " + varname + " = decodeData(\"" + sb.toString() + "\"," + toHex(segSize/4) + ");");
 564             inits.append(indents[2] + "initPages(" + varname +"," + toHex(addr) + "," + (readOnly?"true":"false") + ");\n");
 565             addr += segSize;
 566             size -= segSize;
 567         }
 568         dis.close();
 569     }
 570
 571     private void emitBSS(int addr, int size) throws CompilationException {
 572         if((addr&3)!=0) throw new CompilationException("BSS section on weird boundaries");
 573         size = (size+3)&~3;
 574         int count = size/4;
 575         inits.append(indents[2] + "clearPages(" + toHex(addr) + "," + toHex(count) + ");\n");
 576     }
 577
 578
 579     private void findBranchesInSymtab(ELF.Symtab symtab, Set jumps) {
 580         ELF.Symbol[] symbols = symtab.symbols;
 581         int n=0;
 582         for(int i=0;i<symbols.length;i++) {
 583             ELF.Symbol s = symbols[i];
 584             if(s.type == ELF.Symbol.STT_FUNC) {
 585                 //System.err.println("Adding symbol: " + s.name + " at " + toHex(s.addr));
 586                 if(jumps.add(new Integer(s.addr))) n++;
 587             }
 588         }
 589         if(printStats) System.err.println("Found " + n + " additional possible branch targets in Symtab");
 590     }
 591
 592     private void findBranchesInText(int addr, DataInputStream dis, int size, Set jumps) throws IOException {
 593         int count = size/4;
 594         int pc = addr;
 595         int n=0;
 596
 597         for(int i=0;i<count;i++,pc+=4) {
 598             int insn = dis.readInt();
 599             int op = (insn >>> 26) & 0xff;
 600             int rs = (insn >>> 21) & 0x1f;
 601             int rt = (insn >>> 16) & 0x1f;
 602             int signedImmediate = (insn << 16) >> 16;
 603             int branchTarget = signedImmediate;
 604             int jumpTarget = (insn & 0x03ffffff);
 605             int subcode = insn & 0x3f;
 606
 607             switch(op) {
 608                 case 0:
 609                     switch(subcode) {
 610                         case 9: // JALR
 611                             if(jumps.add(new Integer(pc+8))) n++; // return address
 612                             break;
 613                         case 12: // SYSCALL
 614                             if(jumps.add(new Integer(pc+4))) n++;
 615                             break;
 616                     }
 617                     break;
 618                 case 1:
 619                     switch(rt) {
 620                         case 16: // BLTZAL
 621                         case 17: // BGTZAL
 622                             if(jumps.add(new Integer(pc+8))) n++; // return address
 623                             // fall through
 624                         case 0: // BLTZ
 625                         case 1: // BGEZ
 626                             if(jumps.add(new Integer(pc+branchTarget*4+4))) n++;
 627                             break;
 628                     }
 629                     break;
 630                 case 3: // JAL
 631                     if(jumps.add(new Integer(pc+8))) n++; // return address
 632                     // fall through
 633                 case 2: // J
 634                     if(jumps.add(new Integer((pc&0xf0000000)|(jumpTarget << 2)))) n++;
 635                     break;
 636                 case 4: // BEQ
 637                 case 5: // BNE
 638                 case 6: // BLEZ
 639                 case 7: // BGTZ
 640                     if(jumps.add(new Integer(pc+branchTarget*4+4))) n++;
 641                     break;
 642                 case 17: // FPU Instructions
 643                     switch(rs) {
 644                         case 8: // BC1F, BC1T
 645                             if(jumps.add(new Integer(pc+branchTarget*4+4))) n++;
 646                             break;
 647                     }
 648                     break;
 649             }
 650         }
 651         dis.close();
 652         if(printStats) System.err.println("Found " + n + " additional possible branch targets in Text segment");
 653     }
 654
 655     private void findBranchesInData(DataInputStream dis, int size, Set jumps, int textStart, int textEnd) throws IOException {
 656         int count = size/4;
 657         int n=0;
 658         for(int i=0;i<count;i++) {
 659             int word = dis.readInt();
 660             if((word&3)==0 && word >= textStart && word < textEnd) {
 661                 if(jumps.add(new Integer(word))) n++;
 662             }
 663         }
 664         dis.close();
 665         if(n>0 && printStats) System.err.println("Found " + n + " additional possible branch targets in Data segment");
 666     }
 667
 668     // True if the current code path is unreachable (any instruction with a case statement is reachable)
 669     private boolean unreachable = false;
 670
 671     private void emitInstruction(int pc, int insn, int nextInsn) throws IOException,CompilationException {
 672         if(insn == -1) throw new Error("insn is -1");
 673
 674         int op = (insn >>> 26) & 0xff;                 // bits 26-31
 675         int rs = (insn >>> 21) & 0x1f;                 // bits 21-25
 676         int rt = (insn >>> 16) & 0x1f;                 // bits 16-20
 677         int ft = (insn >>> 16) & 0x1f;
 678         int rd = (insn >>> 11) & 0x1f;                 // bits 11-15
 679         int fs = (insn >>> 11) & 0x1f;
 680         int shamt = (insn >>> 6) & 0x1f;               // bits 6-10
 681         int fd = (insn >>> 6) & 0x1f;
 682         int subcode = insn & 0x3f;                     // bits 0-5
 683
 684         int jumpTarget = (insn & 0x03ffffff);          // bits 0-25
 685         int unsignedImmediate = insn & 0xffff;
 686         int signedImmediate = (insn << 16) >> 16;
 687         int branchTarget = signedImmediate;
 688
 689         int tmp; // temporaries
 690
 691         //if(pc%64==0) p("System.err.println(\"Executing: " + toHex(pc) + "\");");
 692         //p("/" + "*" + (pc == -1 ? "Delay Slot"  : toHex(pc)) + " *" + "/ ");
 693         if(pc==-1) p("/" + "* Next insn is delay slot *" + "/ ");
 694
 695         switch(op) {
 696             case 0: {
 697                 switch(subcode) {
 698                     case 0: // SLL
 699                         if(insn != 0)
 700                             p( "r"+rd+" = r"+rt+" << "+shamt+";");
 701                         break;
 702                     case 2: // SRL
 703                         p( "r"+rd+" = r"+rt+" >>> "+shamt+";");
 704                         break;
 705                     case 3: // SRA
 706                         p( "r"+rd+" = r"+rt+" >> "+shamt+";");
 707                         break;
 708                     case 4: // SLLV
 709                         p( "r"+rd+" = r"+rt+" << (r"+rs+"&0x1f);");
 710                         break;
 711                     case 6: // SRLV
 712                         p( "r"+rd+" = r"+rt+" >>> (r"+rs+"&0x1f);");
 713                         break;
 714                     case 7: // SRAV
 715                         p( "r"+rd+" = r"+rt+" >> (r"+rs+"&0x1f);");
 716                         break;
 717                     case 8: // JR
 718                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 719                         emitInstruction(-1,nextInsn,-1);
 720                         if(debugCompiler) p("lastPC = " + toHex(pc) + ";");
 721                         p("pc=r" + rs + ";");
 722                         leaveMethod();
 723                         unreachable = true;
 724                         break;
 725                     case 9: // JALR
 726                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 727                         emitInstruction(-1,nextInsn,-1);
 728                         if(debugCompiler) p("lastPC = " + toHex(pc) + ";");
 729                         p("pc=r" + rs + ";");
 730                         p("r" + RA + "=" + constant(pc+8 /*skip this insn and delay slot*/) + ";");
 731                         leaveMethod();
 732                         unreachable = true;
 733                         break;
 734                     case 12: // SYSCALL
 735                         p("pc = " + toHex(pc) + ";");
 736                         p( "r"+V0+" = syscall(r"+V0+",r"+A0+",r"+A1+",r"+A2+",r"+A3+");");
 737                         p("if (state != RUNNING) {");
 738                             indent++;
 739                             p("pc = " + toHex(pc+4) + ";");
 740                             leaveMethod();
 741                             indent--;
 742                         p("}");
 743                         break;
 744                     case 13: // BREAK
 745                         p( "throw new ExecutionException(\"Break\");");
 746                         break;
 747                     case 16: // MFHI
 748                         p( "r"+rd+" = hi;");
 749                         break;
 750                     case 17: // MTHI
 751                         p( "hi = r"+rs+";");
 752                         break;
 753                     case 18: // MFLO
 754                         p( "r"+rd+" = lo;");
 755                         break;
 756                     case 19: // MTLO
 757                         p( "lo = r"+rs+";");
 758                         break;
 759                     case 24: // MULT
 760                         p( "{ long hilo = (long)(r"+rs+") * ((long)r"+rt+"); " +
 761                              "hi = (int) (hilo >>> 32); " +
 762                              "lo = (int) hilo; }");
 763                         break;
 764                     case 25: // MULTU
 765                         p( "{ long hilo = (r"+rs+" & 0xffffffffL) * (r"+rt+" & 0xffffffffL); " +
 766                              "hi = (int) (hilo >>> 32); " +
 767                              "lo = (int) hilo; } ");
 768                         break;
 769                     case 26: // DIV
 770                         p( "hi = r"+rs+"%r"+rt+"; lo = r"+rs+"/r"+rt+";");
 771                         break;
 772                     case 27: // DIVU
 773                         p( "hi = (int)((r"+rs+" & 0xffffffffL) % (r"+rt+" & 0xffffffffL)); " +
 774                              "lo = (int)((r"+rs+" & 0xffffffffL) / (r"+rt+" & 0xffffffffL));");
 775                         break;
 776                     case 32: // ADD
 777                         throw new CompilationException("ADD (add with oveflow trap) not suported");
 778                         /*This must trap on overflow
 779                         p( "r"+rd+" = r"+rs+" + r"+rt+";");
 780                         break;*/
 781                     case 33: // ADDU
 782                         p( "r"+rd+" = r"+rs+" + r"+rt+";");
 783                         break;
 784                     case 34: // SUB
 785                         throw new CompilationException("SUB (add with oveflow trap) not suported");
 786                         /*This must trap on overflow
 787                         p( "r"+rd+" = r"+rs+" - r"+rt+";");
 788                         break;*/
 789                     case 35: // SUBU
 790                         p( "r"+rd+" = r"+rs+" - r"+rt+";");
 791                         break;
 792                     case 36: // AND
 793                         p( "r"+rd+" = r"+rs+" & r"+rt+";");
 794                         break;
 795                     case 37: // OR
 796                         p( "r"+rd+" = r"+rs+" | r"+rt+";");
 797                         break;
 798                     case 38: // XOR
 799                         p( "r"+rd+" = r"+rs+" ^ r"+rt+";");
 800                         break;
 801                     case 39: // NOR
 802                         p( "r"+rd+" = ~(r"+rs+" | r"+rt+");");
 803                         break;
 804                     case 42: // SLT
 805                         p( "r"+rd+" = r"+rs+" < r"+rt+" ? 1 : 0;");
 806                         break;
 807                     case 43: // SLTU
 808                         p( "r"+rd+" = ((r"+rs+" & 0xffffffffL) < (r"+rt+" & 0xffffffffL)) ? 1 : 0;");
 809                         break;
 810                     default:
 811                         throw new RuntimeException("Illegal instruction 0/" + subcode);
 812                 }
 813                 break;
 814             }
 815             case 1: {
 816                 switch(rt) {
 817                     case 0: // BLTZ
 818                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 819                         p("if(r" + rs + " < 0) {");
 820                             indent++;
 821                             emitInstruction(-1,nextInsn,-1);
 822                             branch(pc,pc+branchTarget*4+4);
 823                             indent--;
 824                         p("}");
 825                         break;
 826                     case 1: // BGEZ
 827                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 828                         p("if(r" + rs + " >= 0) {");
 829                             indent++;
 830                             emitInstruction(-1,nextInsn,-1);
 831                             branch(pc,pc+branchTarget*4+4);
 832                             indent--;
 833                         p("}");
 834                         break;
 835                     case 16: // BLTZAL
 836                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 837                         p("if(r" + rs + " < 0) {");
 838                             indent++;
 839                             emitInstruction(-1,nextInsn,-1);
 840                             p("r" + RA + "=" + constant(pc+8 /*skip this insn and delay slot*/) + ";");
 841                             branch(pc,pc+branchTarget*4+4);
 842                             indent--;
 843                         p("}");
 844                         break;
 845                     case 17: // BGEZAL
 846                         if(pc == -1) throw new Error("pc modifying insn in delay slot");
 847                         p("if(r" + rs + " >= 0) {");
 848                             indent++;
 849                             emitInstruction(-1,nextInsn,-1);
 850                             p("r" + RA + "=" + constant(pc+8 /*skip this insn and delay slot*/) + ";");
 851                             branch(pc,pc+branchTarget*4+4);
 852                             indent--;
 853                         p("}");
 854                         break;
 855                     default:
 856                         throw new RuntimeException("Illegal Instruction 1/" + rt);
 857                 }
 858                 break;
 859             }
 860             case 2: { // J
 861                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 862                 emitInstruction(-1,nextInsn,-1);
 863                 branch(pc,(pc&0xf0000000)|(jumpTarget << 2));
 864                 unreachable = true;
 865                 break;
 866             }
 867             case 3: { // JAL
 868                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 869                 int target = (pc&0xf0000000)|(jumpTarget << 2);
 870                 emitInstruction(-1,nextInsn,-1);
 871                 if(optimizedMemcpy && (target == memcpy || target == memset)) {
 872                     if(target == memcpy)
 873                         p("memcpy(r4,r5,r6);");
 874                     else if(target == memset)
 875                         p("memset(r4,r5,r6);");
 876                     p("r2 = r4;");
 877                     branch(pc,pc+8);
 878                 } else {
 879                     p("r" + RA + "=" + constant(pc+8 /*skip this insn and delay slot*/) + ";");
 880                     branch(pc, target);
 881                 }
 882                 unreachable = true;
 883                 break;
 884             }
 885             case 4: // BEQ
 886                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 887                 p("if(r" + rs + " == r" + rt + ") {");
 888                     indent++;
 889                     emitInstruction(-1,nextInsn,-1);
 890                     branch(pc,pc+branchTarget*4+4);
 891                     indent--;
 892                 p("}");
 893                 break;
 894             case 5: // BNE
 895                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 896                 p("if(r" + rs + " != r" + rt + ") {");
 897                     indent++;
 898                     emitInstruction(-1,nextInsn,-1);
 899                     branch(pc,pc+branchTarget*4+4);
 900                     indent--;
 901                 p("}");
 902                 break;
 903             case 6: //BLEZ
 904                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 905                 p("if(r" + rs + " <= 0) {");
 906                     indent++;
 907                     emitInstruction(-1,nextInsn,-1);
 908                     branch(pc,pc+branchTarget*4+4);
 909                     indent--;
 910                 p("}");
 911                 break;
 912             case 7: //BGTZ
 913                 if(pc == -1) throw new Error("pc modifying insn in delay slot");
 914                 p("if(r" + rs + " > 0) {");
 915                     indent++;
 916                     emitInstruction(-1,nextInsn,-1);
 917                     branch(pc,pc+branchTarget*4+4);
 918                     indent--;
 919                 p("}");
 920                 break;
 921             case 8: // ADDI
 922                 p( "r"+rt+" = r"+rs+" + "+signedImmediate +";");
 923                 break;
 924             case 9: // ADDIU
 925                 p( "r"+rt+" = r"+rs+" + "+signedImmediate+";");
 926                 break;
 927             case 10: // SLTI
 928                 p( "r"+rt+" = r"+rs+" < "+signedImmediate+" ? 1 : 0;");
 929                 break;
 930             case 11: // SLTIU
 931                 p( "r"+rt+" = (r"+rs+"&0xffffffffL) < ("+unsignedImmediate+"&0xffffffffL) ? 1 : 0;");
 932                 break;
 933             case 12: // ANDI
 934                 p( "r"+rt+" = r"+rs+" & "+unsignedImmediate+";");
 935                 break;
 936             case 13: // ORI
 937                 p( "r"+rt+" = r"+rs+" | "+unsignedImmediate+";");
 938                 break;
 939             case 14: // XORI
 940                 p( "r"+rt+" = r"+rs+" ^ "+unsignedImmediate+";");
 941                 break;
 942             case 15: // LUI
 943                 p( "r"+rt+" = "+unsignedImmediate+" << 16;");
 944                 break;
 945             case 16:
 946                 throw new CompilationException("TLB/Exception support not implemented");
 947             case 17: { // FPU
 948                 switch(rs) {
 949                     case 0: // MFC.1
 950                         p( "r"+rt+" = f"+rd+";");
 951                         break;
 952                     case 2: // CFC.1
 953                         if(fs != 31) throw new CompilationException("FCR " + fs + " unavailable");
 954                         p( "r"+rt+" = fcsr;");
 955                         break;
 956                     case 4: // MTC.1
 957                         p( "f"+rd+" = r"+rt+";");
 958                         break;
 959                     case 6: // CTC.1
 960                         if(fs != 31) throw new CompilationException("FCR " + fs + " unavailable");
 961                         p( "fcsr = r"+rt+";");
 962                         break;
 963                     case 8: {// BC1F, BC1T
 964                         tmp = (insn>>>16)&1;
 965                         p("if(((fcsr&0x800000)!=0) == (" + tmp + "!=0)) {");
 966                             indent++;
 967                             emitInstruction(-1,nextInsn,-1);
 968                             branch(pc,pc+branchTarget*4+4);
 969                             indent--;
 970                         p("}");
 971                         break;
 972                     }
 973                     case 16: {  // Single
 974                         switch(subcode) {
 975                             case 0: // ADD.S
 976                                 p(setFloat(fd,getFloat(fs)+"+"+getFloat(ft)));
 977                                 break;
 978                             case 1: // SUB.S
 979                                 p(setFloat(fd,getFloat(fs)+"-"+getFloat(ft)));
 980                                 break;
 981                             case 2: // MUL.S
 982                                 p(setFloat(fd,getFloat(fs)+"*"+getFloat(ft)));
 983                                 break;
 984                             case 3: // DIV.S
 985                                 p(setFloat(fd,getFloat(fs)+"/"+getFloat(ft)));
 986                                 break;
 987                             case 5: // ABS.S
 988                                 p(setFloat(fd,"Math.abs("+getFloat(fs)+")"));
 989                                 break;
 990                             case 6: // MOV.S
 991                                 p("f"+fd+" = f"+fs+"; // MOV.S");
 992                                 break;
 993                             case 7: // NEG.S
 994                                 p(setFloat(fd,"-"+getFloat(fs)));
 995                                 break;
 996                             case 33: // CVT.D.S
 997                                 p(setDouble(fd,"(float)"+getFloat(fs)));
 998                                 break;
 999                             case 36: // CVT.W.D
1000                                 p("switch(fcsr & 3) {");
1001                                     indent++;
1002                                     p("case 0: f"+fd+" = (int)Math.floor("+getFloat(fs)+"+0.5); break; // Round to nearest");
1003                                     p("case 1: f"+fd+" = (int)"+getFloat(fs)+"; break; // Round towards zero");
1004                                     p("case 2: f"+fd+" = (int)Math.ceil("+getFloat(fs)+"); break; // Round towards plus infinity");
1005                                     p("case 3: f"+fd+" = (int)Math.floor("+getFloat(fs)+"); break; // Round towards minus infinity");
1006                                     indent--;
1007                                 p("}");
1008                                 break;
1009                             case 50: // C.EQ.S
1010                                 p("fcsr = (fcsr&~0x800000) | (("+getFloat(fs)+"=="+getFloat(ft)+") ? 0x800000 : 0x000000);");
1011                                 break;
1012                             case 60: // C.LT.S
1013                                 p("fcsr = (fcsr&~0x800000) | (("+getFloat(fs)+"<"+getFloat(ft)+") ? 0x800000 : 0x000000);");
1014                                 break;
1015                             case 62: // C.LE.S
1016                                 p("fcsr = (fcsr&~0x800000) | (("+getFloat(fs)+"<="+getFloat(ft)+") ? 0x800000 : 0x000000);");
1017                                 break;
1018                             default: throw new CompilationException("Invalid Instruction 17/" + rs + "/" + subcode);
1019                         }
1020                         break;
1021                     }
1022                     case 17: { // Double
1023                         switch(subcode) {
1024                             case 0: // ADD.D
1025                                 p(setDouble(fd,getDouble(fs)+"+"+getDouble(ft)));
1026                                 break;
1027                             case 1: // SUB.D
1028                                 p(setDouble(fd,getDouble(fs)+"-"+getDouble(ft)));
1029                                 break;
1030                             case 2: // MUL.D
1031                                 p(setDouble(fd,getDouble(fs)+"*"+getDouble(ft)));
1032                                 break;
1033                             case 3: // DIV.D
1034                                 p(setDouble(fd,getDouble(fs)+"/"+getDouble(ft)));
1035                                 break;
1036                             case 5: // ABS.D
1037                                 p(setDouble(fd,"Math.abs("+getDouble(fs)+")"));
1038                                 break;
1039                             case 6: // MOV.D
1040                                 p("f"+fd+" = f"+fs+";");
1041                                 p("f"+(fd+1)+" = f"+(fs+1)+";");
1042                                 break;
1043                             case 7: // NEG.D
1044                                 p(setDouble(fd,"-"+getDouble(fs)));
1045                                 break;
1046                             case 32: // CVT.S.D
1047                                 p(setFloat(fd,"(float)"+getDouble(fs)));
1048                                 break;
1049                             case 36: // CVT.W.D
1050                                 p("switch(fcsr & 3) {");
1051                                     indent++;
1052                                     p("case 0: f"+fd+" = (int)Math.floor("+getDouble(fs)+"+0.5); break; // Round to nearest");
1053                                     p("case 1: f"+fd+" = (int)"+getDouble(fs)+"; break; // Round towards zero");
1054                                     p("case 2: f"+fd+" = (int)Math.ceil("+getDouble(fs)+"); break; // Round towards plus infinity");
1055                                     p("case 3: f"+fd+" = (int)Math.floor("+getDouble(fs)+"); break; // Round towards minus infinity");
1056                                     indent--;
1057                                 p("}");
1058                                 break;
1059                             case 50: // C.EQ.D
1060                                 p("fcsr = (fcsr&~0x800000) | (("+getDouble(fs)+"=="+getDouble(ft)+") ? 0x800000 : 0x000000);");
1061                                 break;
1062                             case 60: // C.LT.D
1063                                 p("fcsr = (fcsr&~0x800000) | (("+getDouble(fs)+"<"+getDouble(ft)+") ? 0x800000 : 0x000000);");
1064                                 break;
1065                             case 62: // C.LE.D
1066                                 p("fcsr = (fcsr&~0x800000) | (("+getDouble(fs)+"<="+getDouble(ft)+") ? 0x800000 : 0x000000);");
1067                                 break;
1068                             default: throw new CompilationException("Invalid Instruction 17/" + rs + "/" + subcode);
1069                         }
1070                         break;
1071                     }
1072                     case 20: { // Integer
1073                         switch(subcode) {
1074                             case 32: // CVT.S.W
1075                                 p(" // CVS.S.W");
1076                                 p(setFloat(fd,"((float)f"+fs+")"));
1077                                 break;
1078                             case 33: // CVT.D.W
1079                                 p(setDouble(fd,"((double)f"+fs+")"));
1080                                 break;
1081                             default: throw new CompilationException("Invalid Instruction 17/" + rs + "/" + subcode);
1082                         }
1083                         break;
1084                     }
1085                     default:
1086                         throw new CompilationException("Invalid Instruction 17/" + rs);
1087                 }
1088                 break;
1089             }
1090             case 18: case 19:
1091                 throw new CompilationException("coprocessor 2 and 3 instructions not available");
1092             case 32: { // LB
1093                 if(runtimeStats) p("inc(\"LB\");");
1094                 p("addr=r" + rs +"+"+signedImmediate + ";");
1095                 memRead("addr&~3","tmp");
1096                 p("tmp = (tmp>>>(((~addr)&3)<<3)) & 0xff;");
1097                 p("if((tmp&0x80)!=0) tmp |= 0xffffff00; /* sign extend */");
1098                 p("r"+rt+" = tmp;");
1099                 break;
1100             }
1101             case 33: { // LH
1102                 if(runtimeStats) p("inc(\"LH\");");
1103                 p("addr=r" + rs +"+"+signedImmediate + ";");
1104                 memRead("addr&~3","tmp");
1105                 p("tmp = (tmp>>>(((~addr)&2)<<3)) & 0xffff;");
1106                 p("if((tmp&0x8000)!=0) tmp |= 0xffff0000; /* sign extend */");
1107                 p("r"+rt+" = tmp;");
1108                 break;
1109             }
1110             case 34: { // LWL;
1111                 p("addr=r" + rs +"+"+signedImmediate + ";");
1112                 memRead("addr&~3","tmp");
1113                 p("switch(addr&3) {");
1114                     indent++;
1115                     p("case 0: r"+rt+" = (r"+rt+"&0x00000000)|(tmp<< 0); break;");
1116                     p("case 1: r"+rt+" = (r"+rt+"&0x000000ff)|(tmp<< 8); break;");
1117                     p("case 2: r"+rt+" = (r"+rt+"&0x0000ffff)|(tmp<<16); break;");
1118                     p("case 3: r"+rt+" = (r"+rt+"&0x00ffffff)|(tmp<<24); break;");
1119                     indent--;
1120                 p("}");
1121                 break;
1122             }
1123             case 35: // LW
1124                 if(runtimeStats) p("inc(\"LW\");");
1125                 memRead("r" + rs +"+"+signedImmediate,"r"+rt);
1126                 break;
1127             case 36: { // LBU
1128                 p("addr=r" + rs +"+"+signedImmediate + ";");
1129                 memRead("addr&~3","tmp");
1130                 p("tmp = (tmp>>>(((~addr)&3)<<3)) & 0xff;");
1131                 p("r"+rt+" = tmp;");
1132                 break;
1133             }
1134             case 37: { // LHU
1135                 p("addr=r" + rs +"+"+signedImmediate + ";");
1136                 memRead("addr&~3","tmp");
1137                 p("tmp = (tmp>>>(((~addr)&2)<<3)) & 0xffff;");
1138                 p("r"+rt+" = tmp;");
1139                 break;
1140             }
1141             case 38: { // LWR
1142                 p("addr=r" + rs +"+"+signedImmediate + ";");
1143                 memRead("addr&~3","tmp");
1144                 p("switch(addr&3) {");
1145                     indent++;
1146                     p("case 0: r"+rt+" = (r"+rt+"&0xffffff00)|(tmp>>>24); break;");
1147                     p("case 1: r"+rt+" = (r"+rt+"&0xffff0000)|(tmp>>>16); break;");
1148                     p("case 2: r"+rt+" = (r"+rt+"&0xff000000)|(tmp>>> 8); break;");
1149                     p("case 3: r"+rt+" = (r"+rt+"&0x00000000)|(tmp>>> 0); break;");
1150                     indent--;
1151                 p("}");
1152                 break;
1153             }
1154             case 40: { // SB
1155                 if(runtimeStats) p("inc(\"SB\");");
1156                 p("addr=r" + rs +"+"+signedImmediate + ";");
1157                 memRead("addr&~3","tmp");
1158                 p("tmp = (tmp&~(0xff000000>>>((addr&3)<<3)))|((r"+rt+"&0xff)<<(((~addr)&3)<<3));");
1159                 memWrite("addr&~3","tmp");
1160                 break;
1161             }
1162             case 41: { // SH
1163                 if(runtimeStats) p("inc(\"SH\");");
1164                 p("addr=r" + rs +"+"+signedImmediate + ";");
1165                 memRead("addr&~3","tmp");
1166                 p("tmp = (tmp&(0xffff<<((addr&2)<<3)))|((r" + rt + "&0xffff)<<(((~addr)&2)<<3));");
1167                 memWrite("addr&~3","tmp");
1168                 break;
1169             }
1170             case 42: { // SWL
1171                 p(" // SWL");
1172                 p("addr=r" + rs +"+"+signedImmediate + ";");
1173                 memRead("addr&~3","tmp");
1174                 p("switch(addr&3) {");
1175                     indent++;
1176                     p("case 0: tmp=(tmp&0x00000000)|(r"+rt+">>> 0); break;");
1177                     p("case 1: tmp=(tmp&0xff000000)|(r"+rt+">>> 8); break;");
1178                     p("case 2: tmp=(tmp&0xffff0000)|(r"+rt+">>>16); break;");
1179                     p("case 3: tmp=(tmp&0xffffff00)|(r"+rt+">>>24); break;");
1180                     indent--;
1181                 p("}");
1182                 memWrite("addr&~3","tmp");
1183                 break;
1184             }
1185             case 43: // SW
1186                 if(runtimeStats) p("inc(\"SW\");");
1187                 memWrite("r"+rs+"+"+signedImmediate,"r" + rt);
1188                 break;
1189             case 46: { // SWR
1190                 p(" // SWR");
1191                 p("addr=r" + rs +"+"+signedImmediate + ";");
1192                 memRead("addr&~3","tmp");
1193                 p("switch(addr&3) {");
1194                     indent++;
1195                     p("case 0: tmp=(tmp&0x00ffffff)|(r"+rt+"<<24); break;");
1196                     p("case 1: tmp=(tmp&0x0000ffff)|(r"+rt+"<<16); break;");
1197                     p("case 2: tmp=(tmp&0x000000ff)|(r"+rt+"<< 8); break;");
1198                     p("case 3: tmp=(tmp&0x00000000)|(r"+rt+"<< 0); break;");
1199                     indent--;
1200                 p("}");
1201                 memWrite("addr&~3","tmp");
1202                 break;
1203             }
1204             case 49: // LWC1
1205                 memRead("r"+rs+"+"+signedImmediate,"f"+rt);
1206                 break;
1207             case 57: // SWC1
1208                 memWrite("r"+rs+"+"+signedImmediate,"f"+rt);
1209                 break;
1210             default:
1211                 throw new CompilationException("Invalid Instruction: " + op + " at " + toHex(pc));
1212         }
1213     }
1214
1215     // Helper functions for emitText
1216     private void memWrite(String addr, String target) {
1217         if(nullPointerCheck) p("nullPointerCheck(" + addr + ");");
1218         if(onePage)
1219             p("page[(" + addr + ")>>>2] = " + target + ";");
1220         else if(fastMem)
1221             p("writePages[("+addr+")>>>"+pageShift+"][(("+addr+")>>>2)&"+toHex((pageSize>>2)-1)+"] = " + target + ";");
1222         else
1223             p("memWrite(" + addr + "," + target + ");");
1224     }
1225     private void memRead(String addr, String target) {
1226         if(nullPointerCheck) p("nullPointerCheck(" + addr + ");");
1227         if(onePage)
1228             p(target + "= page[(" + addr + ")>>>2];");
1229         else if(fastMem)
1230             p(target  + " = readPages[("+addr+")>>>"+pageShift+"][(("+addr+")>>>2)&"+toHex((pageSize>>2)-1)+"];");
1231         else
1232             p(target + " = memRead(" + addr + ");");
1233     }
1234     private static String getFloat(int r) { return "(Float.intBitsToFloat(f"+r+"))"; }
1235     private static String getDouble(int r) {
1236         return "(Double.longBitsToDouble(((f"+(r+1)+"&0xffffffffL) << 32) | (f"+r+"&0xffffffffL)))";
1237     }
1238     private static String setFloat(int r, String expr) { return "f"+r+"=Float.floatToRawIntBits("+expr+");"; }
1239     private static String setDouble(int r, String expr) {
1240         return "{ long l = Double.doubleToLongBits("+expr+"); "+
1241             "f"+(r+1)+" = (int)(l >>> 32); f"+r+" = (int)l; }";
1242     }
1243
1244     // Helper functions for pretty output
1245     private final static String toHex(int n) { return "0x" + Long.toString(n & 0xffffffffL, 16); }
1246     private final static String toHex8(int n) {
1247         String s = Long.toString(n & 0xffffffffL, 16);
1248         StringBuffer sb = new StringBuffer("0x");
1249         for(int i=8-s.length();i>0;i--) sb.append('0');
1250         sb.append(s);
1251         return sb.toString();
1252     }
1253
1254     private final static String toOctal3(int n) {
1255         char[] buf = new char[3];
1256         for(int i=2;i>=0;i--) {
1257             buf[i] = (char) ('0' + (n & 7));
1258             n >>= 3;
1259         }
1260         return new String(buf);
1261     }
1262
1263     // Option parsing
1264     private class Option {
1265         private java.lang.reflect.Field field;
1266         public Option(String name) throws NoSuchFieldException { field = name==null ? null : Compiler.class.getDeclaredField(name); }
1267         public void set(Object val) {
1268             if(field == null) return;
1269             try {
1270                 field.setAccessible(true);
1271                 field.set(Compiler.this,val);
1272             } catch(IllegalAccessException e) {
1273                 System.err.println(e);
1274             }
1275         }
1276         public Object get() {
1277             if(field == null) return null;
1278             try {
1279                 field.setAccessible(true);
1280                 return field.get(Compiler.this);
1281             } catch(IllegalAccessException e) {
1282                 System.err.println(e); return null;
1283             }
1284         }
1285         public Class getType() { return field == null ? null : field.getType(); }
1286     }
1287
1288     private static String[] options = {
1289         "fastMem",          "Enable fast memory access - RuntimeExceptions will be thrown on faults",
1290         "nullPointerCheck", "Enables checking at runtime for null pointer accessses (slows things down a bit, only applicable with fastMem)",
1291         "maxInsnPerMethod", "Maximum number of MIPS instructions per java method (128 is optimal with Hotspot)",
1292         "pruneCases",       "Remove unnecessary case 0xAABCCDD blocks from methods - may break some weird code",
1293         "assumeTailCalls",  "Assume the JIT optimizes tail calls",
1294         "optimizedMemcpy",  "Use an optimized java version of memcpy where possible",
1295         "debugCompiler",    "Output information in the generated code for debugging the compiler - will slow down generated code significantly",
1296         "printStats",       "Output some useful statistics about the compilation",
1297         "runtimeStats",     "Keep track of some statistics at runtime in the generated code - will slow down generated code significantly",
1298         "supportCall",      "Keep a stripped down version of the symbol table in the generated code to support the call() method",
1299         "runtimeClass",     "Full classname of the Runtime class (default: Runtime) - use this is you put Runtime in a package",
1300         "hashClass",        "Full classname of a Hashtable class (default: java.util.HashMap) - this must support get() and put()",
1301         "unixRuntime",      "Use the UnixRuntime (has support for fork, wai, du, pipe, etc)",
1302         "pageSize",         "The page size (must be a power of two)",
1303         "totalPages",       "Total number of pages (total mem = pageSize*totalPages, must be a power of two)",
1304         "onePage",          "One page hack (FIXME: document this better)",
1305         "lessConstants",    "Use less constants at the cost of speed (FIXME: document this better)"
1306     };
1307
1308     private Option getOption(String name) {
1309         name = name.toLowerCase();
1310         try {
1311             for(int i=0;i<options.length;i+=2)
1312                 if(options[i].toLowerCase().equals(name))
1313                     return new Option(options[i]);
1314             return null;
1315         } catch(NoSuchFieldException e) {
1316             return null;
1317         }
1318     }
1319
1320     private void parseOptions(String opts) {
1321         if(opts == null || opts.length() == 0) return;
1322         StringTokenizer st = new StringTokenizer(opts,",");
1323         while(st.hasMoreElements()) {
1324             String tok = st.nextToken();
1325             String key;
1326             String val;
1327             if(tok.indexOf("=") != -1) {
1328                 key = tok.substring(0,tok.indexOf("="));
1329                 val = tok.substring(tok.indexOf("=")+1);
1330             } else if(tok.startsWith("no")) {
1331                 key = tok.substring(2);
1332                 val = "false";
1333             } else {
1334                 key = tok;
1335                 val = "true";
1336             }
1337             Option opt = getOption(key);
1338             if(opt == null) {
1339                 System.err.println("WARNING: No such option: " + key);
1340                 continue;
1341             }
1342
1343             if(opt.getType() == String.class)
1344                 opt.set(val);
1345             else if(opt.getType() == Integer.TYPE)
1346                 try {
1347                     opt.set(parseInt(val));
1348                 } catch(NumberFormatException e) {
1349                     System.err.println("WARNING: " + val + " is not an integer");
1350                 }
1351             else if(opt.getType() == Boolean.TYPE)
1352                 opt.set(new Boolean(val.toLowerCase().equals("true")||val.toLowerCase().equals("yes")));
1353             else
1354                 throw new Error("Unknown type: " + opt.getType());
1355         }
1356     }
1357
1358     private static Integer parseInt(String s) {
1359         int mult = 1;
1360         s = s.toLowerCase();
1361         if(!s.startsWith("0x") && s.endsWith("m")) { s = s.substring(0,s.length()-1); mult = 1024*1024; }
1362         else if(!s.startsWith("0x") && s.endsWith("k")) { s = s.substring(0,s.length()-1); mult = 1024; }
1363         int n;
1364         if(s.length() > 2 && s.startsWith("0x")) n = Integer.parseInt(s.substring(2),16);
1365         else n = Integer.parseInt(s);
1366         return new Integer(n*mult);
1367     }
1368
1369     private static String wrapAndIndent(String s, int firstindent, int indent, int width) {
1370         StringTokenizer st = new StringTokenizer(s," ");
1371         StringBuffer sb = new StringBuffer();
1372         for(int i=0;i<firstindent;i++)
1373             sb.append(' ');
1374         int sofar = 0;
1375         while(st.hasMoreTokens()) {
1376             String tok = st.nextToken();
1377             if(tok.length() + sofar + 1 > width && sofar > 0) {
1378                 sb.append('\n');
1379                 for(int i=0;i<indent;i++) sb.append(' ');
1380                 sofar = 0;
1381             } else if(sofar > 0) {
1382                 sb.append(' ');
1383                 sofar++;
1384             }
1385             sb.append(tok);
1386             sofar += tok.length();
1387         }
1388         sb.append('\n');
1389         return sb.toString();
1390     }
1391
1392     // This ugliness is to work around a gcj static linking bug (Bug 12908)
1393     // The best solution is to force gnu.java.locale.Calendar to be linked in but this'll do
1394     private static String dateTime() {
1395         try {
1396             return new Date().toString();
1397         } catch(RuntimeException e) {
1398             return "<unknown>";
1399         }
1400     }
1401 }
1402