src/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 import org.xwt.mips.util.SeekableData;
   9 import org.xwt.mips.util.SeekableFile;
  10
  11 public abstract class Compiler implements Registers {
  12     /** The ELF binary being read */
  13     protected ELF elf;
  14
  15     /** The name of the class beging generated */
  16     protected final String fullClassName;
  17
  18     /** The name of the binary this class is begin generated from */
  19     protected String source = "unknown.mips.binary";
  20     public void setSource(String source) { this.source = source; }
  21
  22     /** Thrown when the compilation fails for some reason */
  23     protected static class Exn extends Exception { public Exn(String s) { super(s); } }
  24
  25     // Set this to true to enable fast memory access
  26     // When this is enabled a Java RuntimeException will be thrown when a page fault occures. When it is disabled
  27     // a FaultException will be throw which is easier to catch and deal with, however. as the name implies, this is slower
  28     protected boolean fastMem = true;
  29
  30     // This MUST be a power of two. If it is not horrible things will happen
  31     // NOTE: This value can be much higher without breaking the classfile
  32     // specs (around 1024) but Hotstop seems to do much better with smaller
  33     // methods.
  34     protected int maxInsnPerMethod = 128;
  35
  36     // non-configurable
  37     protected int maxBytesPerMethod;
  38     protected int methodMask;
  39     protected int methodShift;
  40     protected void maxInsnPerMethodInit() throws Exn {
  41         if((maxInsnPerMethod&(maxInsnPerMethod-1)) != 0) throw new Exn("maxBytesPerMethod is not a power of two");
  42         maxBytesPerMethod = maxInsnPerMethod*4;
  43         methodMask = ~(maxBytesPerMethod-1);
  44         while(maxBytesPerMethod>>>methodShift != 1) methodShift++;
  45     }
  46
  47     // True to try to determine which case statement are needed and only include them
  48     protected boolean pruneCases = true;
  49
  50     protected boolean assumeTailCalls = true;
  51
  52     protected boolean optimizedMemcpy = true;
  53
  54     // True to insert some code in the output to help diagnore compiler problems
  55     protected boolean debugCompiler = false;
  56
  57     // True to print various statistics about the compilation
  58     protected boolean printStats = false;
  59
  60     // True to generate runtime statistics that slow execution down significantly
  61     protected boolean runtimeStats = false;
  62
  63     protected boolean supportCall = true;
  64
  65     protected boolean nullPointerCheck = false;
  66
  67     protected String runtimeClass = "org.xwt.mips.Runtime";
  68
  69     protected String hashClass = "java.util.Hashtable";
  70
  71     protected boolean unixRuntime;
  72
  73     protected boolean lessConstants = false;
  74
  75     protected int pageSize = 4096;
  76     protected int totalPages = 65536;
  77     protected int pageShift;
  78     protected boolean onePage;
  79
  80     protected void pageSizeInit() throws Exn {
  81         try {
  82             Runtime.checkPageSize(pageSize,totalPages);
  83         } catch(IllegalArgumentException e) {
  84             throw new Exn(e.getMessage());
  85         }
  86         while(pageSize>>>pageShift != 1) pageShift++;
  87     }
  88
  89     /** The address of the memcpy function in the binary (used for optimizedMemcpy) */
  90     protected int memcpy;
  91
  92     /** The address of the memset function in the binary (used for optimizedMemcpy) */
  93     protected int memset;
  94
  95     /** A set of all addresses that can be jumped too (only available if pruneCases == true) */
  96     protected Set jumpableAddresses;
  97
  98     /** Some important symbols */
  99     ELF.Symbol userInfo, gp;
 100
 101     private static void usage() {
 102         System.err.println("Usage: java Compiler [-outfile output.java] [-o options] [-dumpoptions] <classname> <binary.mips>");
 103         System.err.println("-o takes mount(8) like options and can be specified multiple times");
 104         System.err.println("Available options:");
 105         for(int i=0;i<options.length;i+=2)
 106             System.err.print(options[i] + ": " + wrapAndIndent(options[i+1],18-2-options[i].length(),18,62));
 107         System.exit(1);
 108     }
 109
 110     public static void main(String[] args) throws IOException {
 111         String outfile = null;
 112         String o = null;
 113         String className = null;
 114         String mipsBinaryFileName = null;
 115         String outformat = null;
 116         boolean dumpOptions = false;
 117         int arg = 0;
 118         while(args.length-arg > 0) {
 119             if(args[arg].equals("-outfile")) {
 120                 arg++;
 121                 if(arg==args.length) usage();
 122                 outfile = args[arg];
 123             } else if(args[arg].equals("-outformat")) {
 124                 arg++;
 125                 if(arg==args.length) usage();
 126                 outformat = args[arg];
 127             } else if(args[arg].equals("-o")) {
 128                 arg++;
 129                 if(arg==args.length) usage();
 130                 if(o==null || o.length() == 0)
 131                     o = args[arg];
 132                 else if(args[arg].length() != 0)
 133                     o += "," + args[arg];
 134             } else if(args[arg].equals("-dumpoptions")) {
 135                 dumpOptions = true;
 136             } else if(className == null) {
 137                 className = args[arg];
 138             } else if(mipsBinaryFileName == null) {
 139                 mipsBinaryFileName = args[arg];
 140             } else {
 141                 usage();
 142             }
 143             arg++;
 144         }
 145         if(className == null || mipsBinaryFileName == null) usage();
 146
 147         SeekableData mipsBinary = new SeekableFile(mipsBinaryFileName);
 148
 149         Writer w = null;
 150         OutputStream os = null;
 151         Compiler comp = null;
 152         if(outformat == null || outformat.equals("class")) {
 153             if(outfile == null) {
 154                 System.err.println("Refusing to write a classfile to stdout - use -outfile foo.class");
 155                 System.exit(1);
 156             }
 157             os = new FileOutputStream(outfile);
 158             comp = new ClassFileCompiler(mipsBinary,className,os);
 159         } else if(outformat.equals("javasource") || outformat .equals("java")) {
 160             w = outfile == null ? new OutputStreamWriter(System.out): new FileWriter(outfile);
 161             comp = new JavaSourceCompiler(mipsBinary,className,w);
 162         } else {
 163             System.err.println("Unknown output format: " + outformat);
 164             System.exit(1);
 165         }
 166
 167         comp.parseOptions(o);
 168         comp.setSource(mipsBinaryFileName);
 169
 170         if(dumpOptions) {
 171             System.err.println("== Options ==");
 172             for(int i=0;i<options.length;i+=2)
 173                 System.err.println(options[i] + ": " + comp.getOption(options[i]).get());
 174             System.err.println("== End Options ==");
 175         }
 176
 177         try {
 178             comp.go();
 179         } catch(Exn e) {
 180             System.err.println("Compiler Error: " + e.getMessage());
 181             System.exit(1);
 182         } finally {
 183             if(w != null) w.close();
 184             if(os != null) os.close();
 185         }
 186     }
 187
 188     public Compiler(SeekableData binary, String fullClassName) throws IOException {
 189         this.fullClassName = fullClassName;
 190         elf = new ELF(binary);
 191
 192         if(elf.header.type != ELF.ELFHeader.ET_EXEC) throw new IOException("Binary is not an executable");
 193         if(elf.header.machine != ELF.ELFHeader.EM_MIPS) throw new IOException("Binary is not for the MIPS I Architecture");
 194         if(elf.ident.data != ELF.ELFIdent.ELFDATA2MSB) throw new IOException("Binary is not big endian");
 195     }
 196
 197     protected abstract void _go() throws Exn, IOException;
 198
 199     private boolean used;
 200     public void go() throws Exn, IOException {
 201         if(used) throw new RuntimeException("Compiler instances are good for one shot only");
 202         used = true;
 203
 204         if(onePage && pageSize <= 4096) pageSize = 4*1024*1024;
 205         if(nullPointerCheck && !fastMem) throw new Exn("fastMem must be enabled for nullPointerCheck to be of any use");
 206         if(onePage && !fastMem) throw new Exn("fastMem must be enabled for onePage to be of any use");
 207         if(totalPages == 1 && !onePage) throw new Exn("totalPages == 1 and onePage is not set");
 208         if(onePage) totalPages = 1;
 209
 210         maxInsnPerMethodInit();
 211         pageSizeInit();
 212
 213         // Get a copy of the symbol table in the elf binary
 214         ELF.Symtab symtab = elf.getSymtab();
 215         if(symtab == null) throw new Exn("Binary has no symtab (did you strip it?)");
 216         ELF.Symbol sym;
 217
 218         // Check for some functions we can override
 219         sym = symtab.getGlobalSymbol("memcpy");
 220         memcpy = sym == null ? -1 : sym.addr;
 221
 222         sym = symtab.getGlobalSymbol("memset");
 223         memset = sym == null ? -1 : sym.addr;
 224
 225         userInfo = symtab.getGlobalSymbol("user_info");
 226         gp = symtab.getGlobalSymbol("_gp");
 227         if(gp == null) throw new Exn("no _gp symbol (did you strip the binary?)");
 228
 229         if(pruneCases) {
 230             // Find all possible branches
 231             jumpableAddresses = new HashSet();
 232
 233             jumpableAddresses.add(new Integer(elf.header.entry));
 234
 235             ELF.SHeader text = elf.sectionWithName(".text");
 236             if(text == null) throw new Exn("No .text segment");
 237
 238             findBranchesInSymtab(symtab,jumpableAddresses);
 239
 240             for(int i=0;i<elf.sheaders.length;i++) {
 241                 ELF.SHeader sheader = elf.sheaders[i];
 242                 String name = sheader.name;
 243                 // if this section doesn't get loaded into our address space don't worry about it
 244                 if(sheader.addr == 0x0) continue;
 245                 if(name.equals(".data") || name.equals(".sdata") || name.equals(".rodata") || name.equals(".ctors") || name.equals(".dtors"))
 246                     findBranchesInData(new DataInputStream(sheader.getInputStream()),sheader.size,jumpableAddresses,text.addr,text.addr+text.size);
 247             }
 248
 249             findBranchesInText(text.addr,new DataInputStream(text.getInputStream()),text.size,jumpableAddresses);
 250         }
 251
 252         if(unixRuntime && runtimeClass.startsWith("org.xwt.mips.")) runtimeClass = "org.xwt.mips.UnixRuntime";
 253
 254         for(int i=0;i<elf.sheaders.length;i++) {
 255             String name = elf.sheaders[i].name;
 256             if(elf.sheaders[i].addr != 0 && !(
 257                 name.equals(".text")|| name.equals(".data") || name.equals(".sdata") || name.equals(".rodata") ||
 258                 name.equals(".ctors") || name.equals(".dtors") || name.equals(".bss") || name.equals(".sbss")))
 259                     throw new Exn("Unknown section: " + name);
 260         }
 261         _go();
 262     }
 263
 264     private void findBranchesInSymtab(ELF.Symtab symtab, Set jumps) {
 265         ELF.Symbol[] symbols = symtab.symbols;
 266         int n=0;
 267         for(int i=0;i<symbols.length;i++) {
 268             ELF.Symbol s = symbols[i];
 269             if(s.type == ELF.Symbol.STT_FUNC) {
 270                 if(jumps.add(new Integer(s.addr))) {
 271                     //System.err.println("Adding symbol from symtab: " + s.name + " at " + toHex(s.addr));
 272                     n++;
 273                 }
 274             }
 275         }
 276         if(printStats) System.err.println("Found " + n + " additional possible branch targets in Symtab");
 277     }
 278
 279     private void findBranchesInText(int base, DataInputStream dis, int size, Set jumps) throws IOException {
 280         int count = size/4;
 281         int pc = base;
 282         int n=0;
 283         int[] lui_val = new int[32];
 284         int[] lui_pc = new int[32];
 285         //Interpreter inter = new Interpreter(source);
 286
 287         for(int i=0;i<count;i++,pc+=4) {
 288             int insn = dis.readInt();
 289             int op = (insn >>> 26) & 0xff;
 290             int rs = (insn >>> 21) & 0x1f;
 291             int rt = (insn >>> 16) & 0x1f;
 292             int signedImmediate = (insn << 16) >> 16;
 293             int unsignedImmediate = insn & 0xffff;
 294             int branchTarget = signedImmediate;
 295             int jumpTarget = (insn & 0x03ffffff);
 296             int subcode = insn & 0x3f;
 297
 298             switch(op) {
 299                 case 0:
 300                     switch(subcode) {
 301                         case 9: // JALR
 302                             if(jumps.add(new Integer(pc+8))) n++; // return address
 303                             break;
 304                         case 12: // SYSCALL
 305                             if(jumps.add(new Integer(pc+4))) n++;
 306                             break;
 307                     }
 308                     break;
 309                 case 1:
 310                     switch(rt) {
 311                         case 16: // BLTZAL
 312                         case 17: // BGTZAL
 313                             if(jumps.add(new Integer(pc+8))) n++; // return address
 314                             // fall through
 315                         case 0: // BLTZ
 316                         case 1: // BGEZ
 317                             if(jumps.add(new Integer(pc+branchTarget*4+4))) n++;
 318                             break;
 319                     }
 320                     break;
 321                 case 3: // JAL
 322                     if(jumps.add(new Integer(pc+8))) n++; // return address
 323                     // fall through
 324                 case 2: // J
 325                     if(jumps.add(new Integer((pc&0xf0000000)|(jumpTarget << 2)))) n++;
 326                     break;
 327                 case 4: // BEQ
 328                 case 5: // BNE
 329                 case 6: // BLEZ
 330                 case 7: // BGTZ
 331                     if(jumps.add(new Integer(pc+branchTarget*4+4))) n++;
 332                     break;
 333                 case 9: { // ADDIU
 334                     if(pc - lui_pc[rs] <= 4*32) {
 335                         int t = (lui_val[rs]<<16)+signedImmediate;
 336                         if((t&3)==0 && t >= base && t < base+size) {
 337                             if(jumps.add(new Integer(t))) {
 338                                 //System.err.println("Possible jump to " + toHex(t) + " (" + inter.sourceLine(t) + ") from " + toHex(pc) + " (" + inter.sourceLine(pc) + ")");
 339                                 n++;
 340                             }
 341                         }
 342                         // we just blew it away
 343                         if(rt == rs) lui_pc[rs] = 0;
 344                     }
 345                     break;
 346                 }
 347                 case 15: { // LUI
 348                     lui_val[rt] = unsignedImmediate;
 349                     lui_pc[rt] = pc;
 350                     break;
 351                 }
 352
 353                 case 17: // FPU Instructions
 354                     switch(rs) {
 355                         case 8: // BC1F, BC1T
 356                             if(jumps.add(new Integer(pc+branchTarget*4+4))) n++;
 357                             break;
 358                     }
 359                     break;
 360             }
 361         }
 362         dis.close();
 363         if(printStats) System.err.println("Found " + n + " additional possible branch targets in Text segment");
 364     }
 365
 366     private void findBranchesInData(DataInputStream dis, int size, Set jumps, int textStart, int textEnd) throws IOException {
 367         int count = size/4;
 368         int n=0;
 369         for(int i=0;i<count;i++) {
 370             int word = dis.readInt();
 371             if((word&3)==0 && word >= textStart && word < textEnd) {
 372                 if(jumps.add(new Integer(word))) {
 373                     //System.err.println("Added " + toHex(word) + " as possible branch target (fron data segment)");
 374                     n++;
 375                 }
 376             }
 377         }
 378         dis.close();
 379         if(n>0 && printStats) System.err.println("Found " + n + " additional possible branch targets in Data segment");
 380     }
 381
 382     // Helper functions for pretty output
 383     protected final static String toHex(int n) { return "0x" + Long.toString(n & 0xffffffffL, 16); }
 384     protected final static String toHex8(int n) {
 385         String s = Long.toString(n & 0xffffffffL, 16);
 386         StringBuffer sb = new StringBuffer("0x");
 387         for(int i=8-s.length();i>0;i--) sb.append('0');
 388         sb.append(s);
 389         return sb.toString();
 390     }
 391
 392     protected final static String toOctal3(int n) {
 393         char[] buf = new char[3];
 394         for(int i=2;i>=0;i--) {
 395             buf[i] = (char) ('0' + (n & 7));
 396             n >>= 3;
 397         }
 398         return new String(buf);
 399     }
 400
 401     // Option parsing
 402     private class Option {
 403         private java.lang.reflect.Field field;
 404         public Option(String name) throws NoSuchFieldException { field = name==null ? null : Compiler.class.getDeclaredField(name); }
 405         public void set(Object val) {
 406             if(field == null) return;
 407             try {
 408                 field.setAccessible(true);
 409                 field.set(Compiler.this,val);
 410             } catch(IllegalAccessException e) {
 411                 System.err.println(e);
 412             }
 413         }
 414         public Object get() {
 415             if(field == null) return null;
 416             try {
 417                 field.setAccessible(true);
 418                 return field.get(Compiler.this);
 419             } catch(IllegalAccessException e) {
 420                 System.err.println(e); return null;
 421             }
 422         }
 423         public Class getType() { return field == null ? null : field.getType(); }
 424     }
 425
 426     private static String[] options = {
 427         "fastMem",          "Enable fast memory access - RuntimeExceptions will be thrown on faults",
 428         "nullPointerCheck", "Enables checking at runtime for null pointer accessses (slows things down a bit, only applicable with fastMem)",
 429         "maxInsnPerMethod", "Maximum number of MIPS instructions per java method (128 is optimal with Hotspot)",
 430         "pruneCases",       "Remove unnecessary case 0xAABCCDD blocks from methods - may break some weird code",
 431         "assumeTailCalls",  "Assume the JIT optimizes tail calls",
 432         "optimizedMemcpy",  "Use an optimized java version of memcpy where possible",
 433         "debugCompiler",    "Output information in the generated code for debugging the compiler - will slow down generated code significantly",
 434         "printStats",       "Output some useful statistics about the compilation",
 435         "runtimeStats",     "Keep track of some statistics at runtime in the generated code - will slow down generated code significantly",
 436         "supportCall",      "Keep a stripped down version of the symbol table in the generated code to support the call() method",
 437         "runtimeClass",     "Full classname of the Runtime class (default: Runtime) - use this is you put Runtime in a package",
 438         "hashClass",        "Full classname of a Hashtable class (default: java.util.HashMap) - this must support get() and put()",
 439         "unixRuntime",      "Use the UnixRuntime (has support for fork, wai, du, pipe, etc)",
 440         "pageSize",         "The page size (must be a power of two)",
 441         "totalPages",       "Total number of pages (total mem = pageSize*totalPages, must be a power of two)",
 442         "onePage",          "One page hack (FIXME: document this better)",
 443         "lessConstants",    "Use less constants at the cost of speed (FIXME: document this better)"
 444     };
 445
 446     private Option getOption(String name) {
 447         name = name.toLowerCase();
 448         try {
 449             for(int i=0;i<options.length;i+=2)
 450                 if(options[i].toLowerCase().equals(name))
 451                     return new Option(options[i]);
 452             return null;
 453         } catch(NoSuchFieldException e) {
 454             return null;
 455         }
 456     }
 457
 458     public void parseOptions(String opts) {
 459         if(opts == null || opts.length() == 0) return;
 460         StringTokenizer st = new StringTokenizer(opts,",");
 461         while(st.hasMoreElements()) {
 462             String tok = st.nextToken();
 463             String key;
 464             String val;
 465             if(tok.indexOf("=") != -1) {
 466                 key = tok.substring(0,tok.indexOf("="));
 467                 val = tok.substring(tok.indexOf("=")+1);
 468             } else if(tok.startsWith("no")) {
 469                 key = tok.substring(2);
 470                 val = "false";
 471             } else {
 472                 key = tok;
 473                 val = "true";
 474             }
 475             Option opt = getOption(key);
 476             if(opt == null) {
 477                 System.err.println("WARNING: No such option: " + key);
 478                 continue;
 479             }
 480
 481             if(opt.getType() == String.class)
 482                 opt.set(val);
 483             else if(opt.getType() == Integer.TYPE)
 484                 try {
 485                     opt.set(parseInt(val));
 486                 } catch(NumberFormatException e) {
 487                     System.err.println("WARNING: " + val + " is not an integer");
 488                 }
 489             else if(opt.getType() == Boolean.TYPE)
 490                 opt.set(new Boolean(val.toLowerCase().equals("true")||val.toLowerCase().equals("yes")));
 491             else
 492                 throw new Error("Unknown type: " + opt.getType());
 493         }
 494     }
 495
 496     private static Integer parseInt(String s) {
 497         int mult = 1;
 498         s = s.toLowerCase();
 499         if(!s.startsWith("0x") && s.endsWith("m")) { s = s.substring(0,s.length()-1); mult = 1024*1024; }
 500         else if(!s.startsWith("0x") && s.endsWith("k")) { s = s.substring(0,s.length()-1); mult = 1024; }
 501         int n;
 502         if(s.length() > 2 && s.startsWith("0x")) n = Integer.parseInt(s.substring(2),16);
 503         else n = Integer.parseInt(s);
 504         return new Integer(n*mult);
 505     }
 506
 507     private static String wrapAndIndent(String s, int firstindent, int indent, int width) {
 508         StringTokenizer st = new StringTokenizer(s," ");
 509         StringBuffer sb = new StringBuffer();
 510         for(int i=0;i<firstindent;i++)
 511             sb.append(' ');
 512         int sofar = 0;
 513         while(st.hasMoreTokens()) {
 514             String tok = st.nextToken();
 515             if(tok.length() + sofar + 1 > width && sofar > 0) {
 516                 sb.append('\n');
 517                 for(int i=0;i<indent;i++) sb.append(' ');
 518                 sofar = 0;
 519             } else if(sofar > 0) {
 520                 sb.append(' ');
 521                 sofar++;
 522             }
 523             sb.append(tok);
 524             sofar += tok.length();
 525         }
 526         sb.append('\n');
 527         return sb.toString();
 528     }
 529
 530     // This ugliness is to work around a gcj static linking bug (Bug 12908)
 531     // The best solution is to force gnu.java.locale.Calendar to be linked in but this'll do
 532     protected static String dateTime() {
 533         try {
 534             return new Date().toString();
 535         } catch(RuntimeException e) {
 536             return "<unknown>";
 537         }
 538     }
 539 }
 540