vm/mterp/gen-mterp.py

   1 #!/usr/bin/env python
   2 #
   3 # Copyright (C) 2007 The Android Open Source Project
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #      http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 #
  18 # Using instructions from an architecture-specific config file, generate C
  19 # and assembly source files for the Dalvik interpreter.
  20 #
  21
  22 import sys, string, re, time
  23 from string import Template
  24
  25 interp_defs_file = "../../libdex/DexOpcodes.h" # need opcode list
  26 kNumPackedOpcodes = 512 # TODO: Derive this from DexOpcodes.h.
  27
  28 verbose = False
  29 handler_size_bits = -1000
  30 handler_size_bytes = -1000
  31 in_op_start = 0             # 0=not started, 1=started, 2=ended
  32 in_alt_op_start = 0         # 0=not started, 1=started, 2=ended
  33 default_op_dir = None
  34 default_alt_stub = None
  35 opcode_locations = {}
  36 alt_opcode_locations = {}
  37 asm_stub_text = []
  38 label_prefix = ".L"         # use ".L" to hide labels from gdb
  39 alt_label_prefix = ".L_ALT" # use ".L" to hide labels from gdb
  40 style = None                # interpreter style
  41 generate_alt_table = False
  42
  43 # Exception class.
  44 class DataParseError(SyntaxError):
  45     "Failure when parsing data file"
  46
  47 #
  48 # Set any omnipresent substitution values.
  49 #
  50 def getGlobalSubDict():
  51     return { "handler_size_bits":handler_size_bits,
  52              "handler_size_bytes":handler_size_bytes }
  53
  54 #
  55 # Parse arch config file --
  56 # Set interpreter style.
  57 #
  58 def setHandlerStyle(tokens):
  59     global style
  60     if len(tokens) != 2:
  61         raise DataParseError("handler-style requires one argument")
  62     style = tokens[1]
  63     if style != "computed-goto" and style != "jump-table" and style != "all-c":
  64         raise DataParseError("handler-style (%s) invalid" % style)
  65
  66 #
  67 # Parse arch config file --
  68 # Set handler_size_bytes to the value of tokens[1], and handler_size_bits to
  69 # log2(handler_size_bytes).  Throws an exception if "bytes" is not 0 or
  70 # a power of two.
  71 #
  72 def setHandlerSize(tokens):
  73     global handler_size_bits, handler_size_bytes
  74     if style != "computed-goto":
  75         print "Warning: handler-size valid only for computed-goto interpreters"
  76     if len(tokens) != 2:
  77         raise DataParseError("handler-size requires one argument")
  78     if handler_size_bits != -1000:
  79         raise DataParseError("handler-size may only be set once")
  80
  81     # compute log2(n), and make sure n is 0 or a power of 2
  82     handler_size_bytes = bytes = int(tokens[1])
  83     bits = -1
  84     while bytes > 0:
  85         bytes //= 2     # halve with truncating division
  86         bits += 1
  87
  88     if handler_size_bytes == 0 or handler_size_bytes != (1 << bits):
  89         raise DataParseError("handler-size (%d) must be power of 2" \
  90                 % orig_bytes)
  91     handler_size_bits = bits
  92
  93 #
  94 # Parse arch config file --
  95 # Copy a file in to the C or asm output file.
  96 #
  97 def importFile(tokens):
  98     if len(tokens) != 2:
  99         raise DataParseError("import requires one argument")
 100     source = tokens[1]
 101     if source.endswith(".c"):
 102         appendSourceFile(tokens[1], getGlobalSubDict(), c_fp, None)
 103     elif source.endswith(".S"):
 104         appendSourceFile(tokens[1], getGlobalSubDict(), asm_fp, None)
 105     else:
 106         raise DataParseError("don't know how to import %s (expecting .c/.S)"
 107                 % source)
 108
 109 #
 110 # Parse arch config file --
 111 # Copy a file in to the C or asm output file.
 112 #
 113 def setAsmStub(tokens):
 114     global asm_stub_text
 115     if style == "all-c":
 116         print "Warning: asm-stub ignored for all-c interpreter"
 117     if len(tokens) != 2:
 118         raise DataParseError("import requires one argument")
 119     try:
 120         stub_fp = open(tokens[1])
 121         asm_stub_text = stub_fp.readlines()
 122     except IOError, err:
 123         stub_fp.close()
 124         raise DataParseError("unable to load asm-stub: %s" % str(err))
 125     stub_fp.close()
 126
 127 #
 128 # Parse arch config file --
 129 # Record location of default alt stub
 130 #
 131 def setAsmAltStub(tokens):
 132     global default_alt_stub, generate_alt_table
 133     if style == "all-c":
 134         print "Warning: asm-alt-stub ingored for all-c interpreter"
 135     if len(tokens) != 2:
 136         raise DataParseError("import requires one argument")
 137     default_alt_stub = tokens[1]
 138     generate_alt_table = True
 139
 140 #
 141 # Parse arch config file --
 142 # Start of opcode list.
 143 #
 144 def opStart(tokens):
 145     global in_op_start
 146     global default_op_dir
 147     if len(tokens) != 2:
 148         raise DataParseError("opStart takes a directory name argument")
 149     if in_op_start != 0:
 150         raise DataParseError("opStart can only be specified once")
 151     default_op_dir = tokens[1]
 152     in_op_start = 1
 153
 154 #
 155 # Parse arch config file --
 156 # Set location of a single alt opcode's source file.
 157 #
 158 def altEntry(tokens):
 159     global generate_alt_table
 160     if len(tokens) != 3:
 161         raise DataParseError("alt requires exactly two arguments")
 162     if in_op_start != 1:
 163         raise DataParseError("alt statements must be between opStart/opEnd")
 164     try:
 165         index = opcodes.index(tokens[1])
 166     except ValueError:
 167         raise DataParseError("unknown opcode %s" % tokens[1])
 168     if alt_opcode_locations.has_key(tokens[1]):
 169         print "Warning: alt overrides earlier %s (%s -> %s)" \
 170                 % (tokens[1], alt_opcode_locations[tokens[1]], tokens[2])
 171     alt_opcode_locations[tokens[1]] = tokens[2]
 172     generate_alt_table = True
 173
 174 #
 175 # Parse arch config file --
 176 # Set location of a single opcode's source file.
 177 #
 178 def opEntry(tokens):
 179     #global opcode_locations
 180     if len(tokens) != 3:
 181         raise DataParseError("op requires exactly two arguments")
 182     if in_op_start != 1:
 183         raise DataParseError("op statements must be between opStart/opEnd")
 184     try:
 185         index = opcodes.index(tokens[1])
 186     except ValueError:
 187         raise DataParseError("unknown opcode %s" % tokens[1])
 188     if opcode_locations.has_key(tokens[1]):
 189         print "Warning: op overrides earlier %s (%s -> %s)" \
 190                 % (tokens[1], opcode_locations[tokens[1]], tokens[2])
 191     opcode_locations[tokens[1]] = tokens[2]
 192
 193 #
 194 # Emit jump table
 195 #
 196 def emitJmpTable(start_label, prefix):
 197     asm_fp.write("\n    .global %s\n" % start_label)
 198     asm_fp.write("    .text\n")
 199     asm_fp.write("%s:\n" % start_label)
 200     for i in xrange(kNumPackedOpcodes):
 201         op = opcodes[i]
 202         dict = getGlobalSubDict()
 203         dict.update({ "opcode":op, "opnum":i })
 204         asm_fp.write("    .long " + prefix + \
 205                      "_%(opcode)s /* 0x%(opnum)02x */\n" % dict)
 206
 207 #
 208 # Parse arch config file --
 209 # End of opcode list; emit instruction blocks.
 210 #
 211 def opEnd(tokens):
 212     global in_op_start
 213     if len(tokens) != 1:
 214         raise DataParseError("opEnd takes no arguments")
 215     if in_op_start != 1:
 216         raise DataParseError("opEnd must follow opStart, and only appear once")
 217     in_op_start = 2
 218
 219     loadAndEmitOpcodes()
 220
 221     if generate_alt_table:
 222         loadAndEmitAltOpcodes()
 223         if style == "jump-table":
 224             emitJmpTable("dvmAsmInstructionStart", label_prefix);
 225             emitJmpTable("dvmAsmAltInstructionStart", alt_label_prefix);
 226
 227
 228 #
 229 # Extract an ordered list of instructions from the VM sources.  We use the
 230 # "goto table" definition macro, which has exactly kNumPackedOpcodes
 231 # entries.
 232 #
 233 def getOpcodeList():
 234     opcodes = []
 235     opcode_fp = open(interp_defs_file)
 236     opcode_re = re.compile(r"^\s*H\(OP_(\w+)\),.*", re.DOTALL)
 237     for line in opcode_fp:
 238         match = opcode_re.match(line)
 239         if not match:
 240             continue
 241         opcodes.append("OP_" + match.group(1))
 242     opcode_fp.close()
 243
 244     if len(opcodes) != kNumPackedOpcodes:
 245         print "ERROR: found %d opcodes in Interp.h (expected %d)" \
 246                 % (len(opcodes), kNumPackedOpcodes)
 247         raise SyntaxError, "bad opcode count"
 248     return opcodes
 249
 250 def emitAlign():
 251     if style == "computed-goto":
 252         asm_fp.write("    .balign %d\n" % handler_size_bytes)
 253
 254 #
 255 # Load and emit opcodes for all kNumPackedOpcodes instructions.
 256 #
 257 def loadAndEmitOpcodes():
 258     sister_list = []
 259     assert len(opcodes) == kNumPackedOpcodes
 260     need_dummy_start = False
 261     if style == "jump-table":
 262         start_label = "dvmAsmInstructionStartCode"
 263         end_label = "dvmAsmInstructionEndCode"
 264     else:
 265         start_label = "dvmAsmInstructionStart"
 266         end_label = "dvmAsmInstructionEnd"
 267
 268     # point dvmAsmInstructionStart at the first handler or stub
 269     asm_fp.write("\n    .global %s\n" % start_label)
 270     asm_fp.write("    .type   %s, %%function\n" % start_label)
 271     asm_fp.write("%s = " % start_label + label_prefix + "_OP_NOP\n")
 272     asm_fp.write("    .text\n\n")
 273
 274     for i in xrange(kNumPackedOpcodes):
 275         op = opcodes[i]
 276
 277         if opcode_locations.has_key(op):
 278             location = opcode_locations[op]
 279         else:
 280             location = default_op_dir
 281
 282         if location == "c":
 283             loadAndEmitC(location, i)
 284             if len(asm_stub_text) == 0:
 285                 need_dummy_start = True
 286         else:
 287             loadAndEmitAsm(location, i, sister_list)
 288
 289     # For a 100% C implementation, there are no asm handlers or stubs.  We
 290     # need to have the dvmAsmInstructionStart label point at OP_NOP, and it's
 291     # too annoying to try to slide it in after the alignment psuedo-op, so
 292     # we take the low road and just emit a dummy OP_NOP here.
 293     if need_dummy_start:
 294         emitAlign()
 295         asm_fp.write(label_prefix + "_OP_NOP:   /* dummy */\n");
 296
 297     emitAlign()
 298     asm_fp.write("    .size   %s, .-%s\n" % (start_label, start_label))
 299     asm_fp.write("    .global %s\n" % end_label)
 300     asm_fp.write("%s:\n" % end_label)
 301
 302     if style == "computed-goto":
 303         emitSectionComment("Sister implementations", asm_fp)
 304         asm_fp.write("    .global dvmAsmSisterStart\n")
 305         asm_fp.write("    .type   dvmAsmSisterStart, %function\n")
 306         asm_fp.write("    .text\n")
 307         asm_fp.write("    .balign 4\n")
 308         asm_fp.write("dvmAsmSisterStart:\n")
 309         asm_fp.writelines(sister_list)
 310
 311         asm_fp.write("\n    .size   dvmAsmSisterStart, .-dvmAsmSisterStart\n")
 312         asm_fp.write("    .global dvmAsmSisterEnd\n")
 313         asm_fp.write("dvmAsmSisterEnd:\n\n")
 314
 315 #
 316 # Load an alternate entry stub
 317 #
 318 def loadAndEmitAltStub(source, opindex):
 319     op = opcodes[opindex]
 320     if verbose:
 321         print " alt emit %s --> stub" % source
 322     dict = getGlobalSubDict()
 323     dict.update({ "opcode":op, "opnum":opindex })
 324
 325     emitAsmHeader(asm_fp, dict, alt_label_prefix)
 326     appendSourceFile(source, dict, asm_fp, None)
 327
 328 #
 329 # Load and emit alternate opcodes for all kNumPackedOpcodes instructions.
 330 #
 331 def loadAndEmitAltOpcodes():
 332     assert len(opcodes) == kNumPackedOpcodes
 333     if style == "jump-table":
 334         start_label = "dvmAsmAltInstructionStartCode"
 335         end_label = "dvmAsmAltInstructionEndCode"
 336     else:
 337         start_label = "dvmAsmAltInstructionStart"
 338         end_label = "dvmAsmAltInstructionEnd"
 339
 340     # point dvmAsmInstructionStart at the first handler or stub
 341     asm_fp.write("\n    .global %s\n" % start_label)
 342     asm_fp.write("    .type   %s, %%function\n" % start_label)
 343     asm_fp.write("%s:\n" % start_label)
 344     asm_fp.write("    .text\n\n")
 345
 346     for i in xrange(kNumPackedOpcodes):
 347         op = opcodes[i]
 348         if alt_opcode_locations.has_key(op):
 349             source = "%s/ALT_%s.S" % (alt_opcode_locations[op], op)
 350         else:
 351             source = default_alt_stub
 352         loadAndEmitAltStub(source, i)
 353
 354     emitAlign()
 355     asm_fp.write("    .size   %s, .-%s\n" % (start_label, start_label))
 356     asm_fp.write("    .global %s\n" % end_label)
 357     asm_fp.write("%s:\n" % end_label)
 358
 359 #
 360 # Load a C fragment and emit it, then output an assembly stub.
 361 #
 362 def loadAndEmitC(location, opindex):
 363     op = opcodes[opindex]
 364     source = "%s/%s.c" % (location, op)
 365     if verbose:
 366         print " emit %s --> C" % source
 367     dict = getGlobalSubDict()
 368     dict.update({ "opcode":op, "opnum":opindex })
 369
 370     appendSourceFile(source, dict, c_fp, None)
 371
 372     if len(asm_stub_text) != 0:
 373         emitAsmStub(asm_fp, dict)
 374
 375 #
 376 # Load an assembly fragment and emit it.
 377 #
 378 def loadAndEmitAsm(location, opindex, sister_list):
 379     op = opcodes[opindex]
 380     source = "%s/%s.S" % (location, op)
 381     dict = getGlobalSubDict()
 382     dict.update({ "opcode":op, "opnum":opindex })
 383     if verbose:
 384         print " emit %s --> asm" % source
 385
 386     emitAsmHeader(asm_fp, dict, label_prefix)
 387     appendSourceFile(source, dict, asm_fp, sister_list)
 388
 389 #
 390 # Output the alignment directive and label for an assembly piece.
 391 #
 392 def emitAsmHeader(outfp, dict, prefix):
 393     outfp.write("/* ------------------------------ */\n")
 394     # The alignment directive ensures that the handler occupies
 395     # at least the correct amount of space.  We don't try to deal
 396     # with overflow here.
 397     emitAlign()
 398     # Emit a label so that gdb will say the right thing.  We prepend an
 399     # underscore so the symbol name doesn't clash with the Opcode enum.
 400     outfp.write(prefix + "_%(opcode)s: /* 0x%(opnum)02x */\n" % dict)
 401
 402 #
 403 # Output a generic instruction stub that updates the "glue" struct and
 404 # calls the C implementation.
 405 #
 406 def emitAsmStub(outfp, dict):
 407     emitAsmHeader(outfp, dict, label_prefix)
 408     for line in asm_stub_text:
 409         templ = Template(line)
 410         outfp.write(templ.substitute(dict))
 411
 412 #
 413 # Append the file specified by "source" to the open "outfp".  Each line will
 414 # be template-replaced using the substitution dictionary "dict".
 415 #
 416 # If the first line of the file starts with "%" it is taken as a directive.
 417 # A "%include" line contains a filename and, optionally, a Python-style
 418 # dictionary declaration with substitution strings.  (This is implemented
 419 # with recursion.)
 420 #
 421 # If "sister_list" is provided, and we find a line that contains only "&",
 422 # all subsequent lines from the file will be appended to sister_list instead
 423 # of copied to the output.
 424 #
 425 # This may modify "dict".
 426 #
 427 def appendSourceFile(source, dict, outfp, sister_list):
 428     outfp.write("/* File: %s */\n" % source)
 429     infp = open(source, "r")
 430     in_sister = False
 431     for line in infp:
 432         if line.startswith("%include"):
 433             # Parse the "include" line
 434             tokens = line.strip().split(' ', 2)
 435             if len(tokens) < 2:
 436                 raise DataParseError("malformed %%include in %s" % source)
 437
 438             alt_source = tokens[1].strip("\"")
 439             if alt_source == source:
 440                 raise DataParseError("self-referential %%include in %s"
 441                         % source)
 442
 443             new_dict = dict.copy()
 444             if len(tokens) == 3:
 445                 new_dict.update(eval(tokens[2]))
 446             #print " including src=%s dict=%s" % (alt_source, new_dict)
 447             appendSourceFile(alt_source, new_dict, outfp, sister_list)
 448             continue
 449
 450         elif line.startswith("%default"):
 451             # copy keywords into dictionary
 452             tokens = line.strip().split(' ', 1)
 453             if len(tokens) < 2:
 454                 raise DataParseError("malformed %%default in %s" % source)
 455             defaultValues = eval(tokens[1])
 456             for entry in defaultValues:
 457                 dict.setdefault(entry, defaultValues[entry])
 458             continue
 459
 460         elif line.startswith("%verify"):
 461             # more to come, someday
 462             continue
 463
 464         elif line.startswith("%break") and sister_list != None:
 465             # allow more than one %break, ignoring all following the first
 466             if style == "computed-goto" and not in_sister:
 467                 in_sister = True
 468                 sister_list.append("\n/* continuation for %(opcode)s */\n"%dict)
 469             continue
 470
 471         # perform keyword substitution if a dictionary was provided
 472         if dict != None:
 473             templ = Template(line)
 474             try:
 475                 subline = templ.substitute(dict)
 476             except KeyError, err:
 477                 raise DataParseError("keyword substitution failed in %s: %s"
 478                         % (source, str(err)))
 479             except:
 480                 print "ERROR: substitution failed: " + line
 481                 raise
 482         else:
 483             subline = line
 484
 485         # write output to appropriate file
 486         if in_sister:
 487             sister_list.append(subline)
 488         else:
 489             outfp.write(subline)
 490     outfp.write("\n")
 491     infp.close()
 492
 493 #
 494 # Emit a C-style section header comment.
 495 #
 496 def emitSectionComment(str, fp):
 497     equals = "========================================" \
 498              "==================================="
 499
 500     fp.write("\n/*\n * %s\n *  %s\n * %s\n */\n" %
 501         (equals, str, equals))
 502
 503
 504 #
 505 # ===========================================================================
 506 # "main" code
 507 #
 508
 509 #
 510 # Check args.
 511 #
 512 if len(sys.argv) != 3:
 513     print "Usage: %s target-arch output-dir" % sys.argv[0]
 514     sys.exit(2)
 515
 516 target_arch = sys.argv[1]
 517 output_dir = sys.argv[2]
 518
 519 #
 520 # Extract opcode list.
 521 #
 522 opcodes = getOpcodeList()
 523 #for op in opcodes:
 524 #    print "  %s" % op
 525
 526 #
 527 # Open config file.
 528 #
 529 try:
 530     config_fp = open("config-%s" % target_arch)
 531 except:
 532     print "Unable to open config file 'config-%s'" % target_arch
 533     sys.exit(1)
 534
 535 #
 536 # Open and prepare output files.
 537 #
 538 try:
 539     c_fp = open("%s/InterpC-%s.c" % (output_dir, target_arch), "w")
 540     asm_fp = open("%s/InterpAsm-%s.S" % (output_dir, target_arch), "w")
 541 except:
 542     print "Unable to open output files"
 543     print "Make sure directory '%s' exists and existing files are writable" \
 544             % output_dir
 545     # Ideally we'd remove the files to avoid confusing "make", but if they
 546     # failed to open we probably won't be able to remove them either.
 547     sys.exit(1)
 548
 549 print "Generating %s, %s" % (c_fp.name, asm_fp.name)
 550
 551 file_header = """/*
 552  * This file was generated automatically by gen-mterp.py for '%s'.
 553  *
 554  * --> DO NOT EDIT <--
 555  */
 556
 557 """ % (target_arch)
 558
 559 c_fp.write(file_header)
 560 asm_fp.write(file_header)
 561
 562 #
 563 # Process the config file.
 564 #
 565 failed = False
 566 try:
 567     for line in config_fp:
 568         line = line.strip()         # remove CRLF, leading spaces
 569         tokens = line.split(' ')    # tokenize
 570         #print "%d: %s" % (len(tokens), tokens)
 571         if len(tokens[0]) == 0:
 572             #print "  blank"
 573             pass
 574         elif tokens[0][0] == '#':
 575             #print "  comment"
 576             pass
 577         else:
 578             if tokens[0] == "handler-size":
 579                 setHandlerSize(tokens)
 580             elif tokens[0] == "import":
 581                 importFile(tokens)
 582             elif tokens[0] == "asm-stub":
 583                 setAsmStub(tokens)
 584             elif tokens[0] == "asm-alt-stub":
 585                 setAsmAltStub(tokens)
 586             elif tokens[0] == "op-start":
 587                 opStart(tokens)
 588             elif tokens[0] == "op-end":
 589                 opEnd(tokens)
 590             elif tokens[0] == "alt":
 591                 altEntry(tokens)
 592             elif tokens[0] == "op":
 593                 opEntry(tokens)
 594             elif tokens[0] == "handler-style":
 595                 setHandlerStyle(tokens)
 596             else:
 597                 raise DataParseError, "unrecognized command '%s'" % tokens[0]
 598             if style == None:
 599                 print "tokens[0] = %s" % tokens[0]
 600                 raise DataParseError, "handler-style must be first command"
 601 except DataParseError, err:
 602     print "Failed: " + str(err)
 603     # TODO: remove output files so "make" doesn't get confused
 604     failed = True
 605     c_fp.close()
 606     asm_fp.close()
 607     c_fp = asm_fp = None
 608
 609 config_fp.close()
 610
 611 #
 612 # Done!
 613 #
 614 if c_fp:
 615     c_fp.close()
 616 if asm_fp:
 617     asm_fp.close()
 618
 619 sys.exit(failed)