js/src/imacro_asm.py

   1 #!/usr/bin/env python
   2 # -*- Mode: Python; tab-width: 4; indent-tabs-mode: nil -*-
   3 # ***** BEGIN LICENSE BLOCK *****
   4 # Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5 #
   6 # The contents of this file are subject to the Mozilla Public License Version
   7 # 1.1 (the "License"); you may not use this file except in compliance with
   8 # the License. You may obtain a copy of the License at
   9 # http://www.mozilla.org/MPL/
  10 #
  11 # Software distributed under the License is distributed on an "AS IS" basis,
  12 # WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13 # for the specific language governing rights and limitations under the
  14 # License.
  15 #
  16 # The Original Code is the TraceMonkey IMacro Assembler.
  17 #
  18 # The Initial Developer of the Original Code is
  19 # Brendan Eich <brendan@mozilla.org>.
  20 # Portions created by the Initial Developer are Copyright (C) 2008
  21 # the Initial Developer. All Rights Reserved.
  22 #
  23 # Contributor(s):
  24 #
  25 # Alternatively, the contents of this file may be used under the terms of
  26 # either the GNU General Public License Version 2 or later (the "GPL"), or
  27 # the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28 # in which case the provisions of the GPL or the LGPL are applicable instead
  29 # of those above. If you wish to allow use of your version of this file only
  30 # under the terms of either the GPL or the LGPL, and not to allow others to
  31 # use your version of this file under the terms of the MPL, indicate your
  32 # decision by deleting the provisions above and replace them with the notice
  33 # and other provisions required by the GPL or the LGPL. If you do not delete
  34 # the provisions above, a recipient may use your version of this file under
  35 # the terms of any one of the MPL, the GPL or the LGPL.
  36 #
  37 # ***** END LICENSE BLOCK *****
  38
  39 # An imacro (interpreter-macro) assembler in Python.
  40 #
  41 # Filename suffix conventions, used by Makefile.in rules:
  42 #   .jsasm     SpiderMonkey JS assembly source, which could be input to other
  43 #              assemblers than imacro_asm.js, hence the generic suffix!
  44 #   .c.out     C source output by imacro_asm.js
  45
  46 import re
  47 import os
  48
  49 class Op:
  50     def __init__(self, jsop, opcode, opname, opsrc, oplen, pops, pushes, precedence, flags):
  51         self.jsop = jsop
  52         self.opcode = opcode
  53         self.opname = opname
  54         self.opsrc = opsrc
  55         self.oplen = oplen
  56         self.pops = pops
  57         self.pushes = pushes
  58         self.precedence = precedence
  59         self.flags = flags
  60
  61 def readFileLines(filename):
  62     f = open(filename)
  63     try:
  64         return f.readlines()
  65     finally:
  66         f.close()
  67
  68 def load_ops(filename):
  69     opdef_regexp = re.compile(r'''(?x)
  70         ^ OPDEF \( (JSOP_\w+),         \s*  # op
  71                    ([0-9]+),           \s*  # val
  72                    ("[^"]+" | [\w_]+), \s*  # name
  73                    ("[^"]+" | [\w_]+), \s*  # image
  74                    (-1|[0-9]+),        \s*  # len
  75                    (-1|[0-9]+),        \s*  # uses
  76                    (-1|[0-9]+),        \s*  # defs
  77                    ([0-9]+),           \s*  # prec
  78                    ([\w_| ]+)          \s*  # format
  79                 \) \s* $''')
  80
  81     def decode_string_expr(expr):
  82         if expr == 'NULL':
  83             return None
  84         if expr[0] == '"':
  85             assert expr[-1] == '"'
  86             return expr[1:-1]
  87         assert expr.startswith('js_') and expr.endswith('_str')
  88         return expr[3:-4]
  89
  90     opinfo = []
  91     for lineno, line in enumerate(readFileLines(filename)):
  92         if line.startswith('OPDEF'):
  93             m = opdef_regexp.match(line)
  94             if m is None:
  95                 raise ValueError("OPDEF line of wrong format in jsopcode.tbl at line %d" % (lineno + 1))
  96             jsop, opcode, opname, opsrc, oplen, pops, pushes, precedence, flags = m.groups()
  97             assert int(opcode) == len(opinfo)
  98             opinfo.append(Op(jsop, int(opcode), decode_string_expr(opname),
  99                              decode_string_expr(opsrc), int(oplen), int(pops), int(pushes),
 100                              int(precedence), flags.replace(' ', '').split('|')))
 101     return opinfo
 102
 103 opinfo = load_ops(os.path.join(os.path.dirname(__file__), "jsopcode.tbl"))
 104 opname2info = dict((info.opname, info) for info in opinfo)
 105 jsop2opcode = dict((info.jsop, info.opcode) for info in opinfo)
 106
 107 def to_uint8(s):
 108     try:
 109         n = int(s)
 110     except ValueError:
 111         n = -1
 112     if 0 <= n < (1<<8):
 113         return n
 114     raise ValueError("invalid 8-bit operand: " + s)
 115
 116 def to_uint16(s):
 117     try:
 118         n = int(s)
 119     except ValueError:
 120         n = -1
 121     if 0 <= n < (1<<16):
 122         return n
 123     raise ValueError("invalid 16-bit operand: " + s)
 124
 125 def immediate(op):
 126     info = op.info
 127     imm1Expr = op.imm1.startswith('(')
 128     if 'JOF_ATOM' in info.flags:
 129         if op.imm1 in ('void', 'object', 'function', 'string', 'number', 'boolean'):
 130             return "0, COMMON_TYPE_ATOM_INDEX(JSTYPE_%s)" % op.imm1.upper()
 131         return "0, COMMON_ATOM_INDEX(%s)" % op.imm1
 132     if 'JOF_JUMP' in info.flags:
 133         assert not imm1Expr
 134         return "%d, %d" % ((op.target >> 8) & 0xff, op.target & 0xff)
 135     if 'JOF_UINT8' in info.flags or 'JOF_INT8' in info.flags:
 136         if imm1Expr:
 137             return op.imm1
 138         return str(to_uint8(op.imm1))
 139     if 'JOF_UINT16' in info.flags:
 140         if imm1Expr:
 141             return '(%s & 0xff00) >> 8, (%s & 0xff)' % (op.imm1, op.imm1)
 142         v = to_uint16(op.imm1)
 143         return "%d, %d" % ((v & 0xff00) >> 8, v & 0xff)
 144     raise NotImplementedError(info.jsop + " format not yet implemented")
 145
 146 def simulate_cfg(igroup, imacro, depth, i):
 147     any_group_opcode = None
 148     expected_depth = None
 149     for opcode in igroup.ops:
 150         opi = opinfo[opcode]
 151         if any_group_opcode is None:
 152             any_group_opcode = opcode
 153             if opi.pops < 0:
 154                 expected_depth = None
 155             else:
 156                 expected_depth = opi.pushes - opi.pops
 157         elif expected_depth is None:
 158             if opi.pops >= 0:
 159                 raise ValueError("imacro shared by constant- and variable-stack-defs/uses instructions")
 160         else:
 161             if opi.pops < 0:
 162                 raise ValueError("imacro shared by constant- and variable-stack-defs/uses instructions")
 163             if opi.pushes - opi.pops != expected_depth:
 164                 raise ValueError("imacro shared by instructions with different stack depths")
 165
 166     for i in range(i, len(imacro.code)):
 167         op = imacro.code[i]
 168         opi = op.info
 169         if opi.opname == 'imacop':
 170             opi = opinfo[any_group_opcode]
 171
 172         if opi.pops < 0:
 173             depth -= 2 + int(op.imm1)
 174         else:
 175             depth -= opi.pops
 176         depth += opi.pushes
 177
 178         if i in imacro.depths and imacro.depths[i] != depth:
 179             raise ValueError("Mismatched depth at %s:%d" % (imacro.filename, op.line))
 180
 181         # Underflowing depth isn't necessarily fatal; most of the imacros
 182         # assume they are called with N>0 args so some assume it's ok to go
 183         # to some depth <N. We simulate starting from 0, as we've no idea
 184         # what else to do.
 185         #
 186         # if depth < 0:
 187         #     raise ValueError("Negative static-stack depth at %s:%d" % (imacro.filename, op.line))
 188         if depth > imacro.maxdepth:
 189             imacro.maxdepth = depth
 190         imacro.depths[i] = depth
 191
 192         if hasattr(op, "target_index"):
 193             if op.target_index <= i:
 194                 raise ValueError("Backward jump at %s:%d" % (imacro.filename, op.line))
 195             simulate_cfg(igroup, imacro, depth, op.target_index)
 196             if op.info.opname in ('goto', 'gotox'):
 197                 return
 198
 199     if expected_depth is not None and depth != expected_depth:
 200         raise ValueError("Expected depth %d, got %d" % (expected_depth, depth))
 201
 202
 203 # Syntax (spaces are significant only to delimit tokens):
 204 #
 205 #   Assembly   ::= (Directive? '\n')*
 206 #   Directive  ::= (name ':')? Operation
 207 #   Operation  ::= opname Operands?
 208 #   Operands   ::= Operand (',' Operand)*
 209 #   Operand    ::= name | number | '(' Expr ')'
 210 #   Expr       ::= a constant-expression in the C++ language
 211 #                  containing no parentheses
 212 #
 213 # We simplify given line structure and the maximum of one immediate operand,
 214 # by parsing using split and regexps.  For ease of parsing, parentheses are
 215 # banned in an Expr for now, even in quotes or a C++ comment.
 216 #
 217 # Pseudo-ops start with . and include .igroup and .imacro, terminated by .end.
 218 # .imacro must nest in .igroup, neither nests in itself. See imacros.jsasm for
 219 # examples.
 220 #
 221 line_regexp = re.compile(r'''(?x)
 222     ^
 223     (?: (\w+):                     )?  # optional label at start of line
 224         \s* (\.?\w+)                   # optional spaces, (pseudo-)opcode
 225     (?: \s+ ([+-]?\w+ | \([^)]*\)) )?  # optional first immediate operand
 226     (?: \s+ ([\w,-]+  | \([^)]*\)) )?  # optional second immediate operand
 227     (?: \s* (?:\#.*)               )?  # optional spaces and comment
 228     $''')
 229
 230 oprange_regexp = re.compile(r'^\w+(?:-\w+)?(?:,\w+(?:-\w+)?)*$')
 231
 232 class IGroup(object):
 233     def __init__(self, name, ops):
 234         self.name = name
 235         self.ops = ops
 236         self.imacros = []
 237
 238 class IMacro(object):
 239     def __init__(self, name, filename):
 240         self.name = name
 241         self.offset = 0
 242         self.code = []
 243         self.labeldefs = {}
 244         self.labeldef_indexes = {}
 245         self.labelrefs = {}
 246         self.filename = filename
 247         self.depths = {}
 248         self.initdepth = 0
 249
 250 class Instruction(object):
 251     def __init__(self, offset, info, imm1, imm2, lineno):
 252         self.offset = offset
 253         self.info = info
 254         self.imm1 = imm1
 255         self.imm2 = imm2
 256         self.lineno = lineno
 257
 258 def assemble(filename, outfile):
 259     write = outfile.write
 260     igroup = None
 261     imacro = None
 262     opcode2extra = {}
 263     igroups = []
 264
 265     write("/* GENERATED BY imacro_asm.js -- DO NOT EDIT!!! */\n")
 266
 267     def fail(msg, *args):
 268         raise ValueError("%s at %s:%d" % (msg % args, filename, lineno + 1))
 269
 270     for lineno, line in enumerate(readFileLines(filename)):
 271         # strip comments
 272         line = re.sub(r'#.*', '', line).rstrip()
 273         if line == "":
 274             continue
 275         m = line_regexp.match(line)
 276         if m is None:
 277             fail(line)
 278
 279         label, opname, imm1, imm2 = m.groups()
 280
 281         if opname.startswith('.'):
 282             if label is not None:
 283                 fail("invalid label %s before %s" % (label, opname))
 284
 285             if opname == '.igroup':
 286                 if imm1 is None:
 287                     fail("missing .igroup name")
 288                 if igroup is not None:
 289                     fail("nested .igroup " + imm1)
 290                 if oprange_regexp.match(imm2) is None:
 291                     fail("invalid igroup operator range " + imm2)
 292
 293                 ops = set()
 294                 for current in imm2.split(","):
 295                     split = current.split('-')
 296                     opcode = jsop2opcode[split[0]]
 297                     if len(split) == 1:
 298                         lastopcode = opcode
 299                     else:
 300                         assert len(split) == 2
 301                         lastopcode = jsop2opcode[split[1]]
 302                         if opcode >= lastopcode:
 303                             fail("invalid opcode range: " + current)
 304
 305                     for opcode in range(opcode, lastopcode + 1):
 306                         if opcode in ops:
 307                             fail("repeated opcode " + opinfo[opcode].jsop)
 308                         ops.add(opcode)
 309
 310                 igroup = IGroup(imm1, ops)
 311
 312             elif opname == '.imacro':
 313                 if igroup is None:
 314                     fail(".imacro outside of .igroup")
 315                 if imm1 is None:
 316                     fail("missing .imacro name")
 317                 if imacro:
 318                     fail("nested .imacro " + imm1)
 319                 imacro = IMacro(imm1, filename)
 320
 321             elif opname == '.fixup':
 322                 if imacro is None:
 323                     fail(".fixup outside of .imacro")
 324                 if len(imacro.code) != 0:
 325                     fail(".fixup must be first item in .imacro")
 326                 if imm1 is None:
 327                     fail("missing .fixup argument")
 328                 try:
 329                     fixup = int(imm1)
 330                 except ValueError:
 331                     fail(".fixup argument must be a nonzero integer")
 332                 if fixup == 0:
 333                     fail(".fixup argument must be a nonzero integer")
 334                 if imacro.initdepth != 0:
 335                     fail("more than one .fixup in .imacro")
 336                 imacro.initdepth = fixup
 337
 338             elif opname == '.end':
 339                 if imacro is None:
 340                     if igroup is None:
 341                         fail(".end without prior .igroup or .imacro")
 342                     if imm1 is not None and (imm1 != igroup.name or imm2 is not None):
 343                         fail(".igroup/.end name mismatch")
 344
 345                     maxdepth = 0
 346
 347                     write("static struct {\n")
 348                     for imacro in igroup.imacros:
 349                         write("    jsbytecode %s[%d];\n" % (imacro.name, imacro.offset))
 350                     write("} %s_imacros = {\n" % igroup.name)
 351
 352                     for imacro in igroup.imacros:
 353                         depth = 0
 354                         write("    {\n")
 355                         for op in imacro.code:
 356                             operand = ""
 357                             if op.imm1 is not None:
 358                                 operand = ", " + immediate(op)
 359                             write("/*%2d*/  %s%s,\n" % (op.offset, op.info.jsop, operand))
 360
 361                         imacro.maxdepth = imacro.initdepth
 362                         simulate_cfg(igroup, imacro, imacro.initdepth, 0)
 363                         if imacro.maxdepth > maxdepth:
 364                             maxdepth = imacro.maxdepth
 365
 366                         write("    },\n")
 367                     write("};\n")
 368
 369                     for opcode in igroup.ops:
 370                         opcode2extra[opcode] = maxdepth
 371                     igroups.append(igroup)
 372                     igroup = None
 373                 else:
 374                     assert igroup is not None
 375
 376                     if imm1 is not None and imm1 != imacro.name:
 377                         fail(".imacro/.end name mismatch")
 378
 379                     # Backpatch the forward references to labels that must now be defined.
 380                     for label in imacro.labelrefs:
 381                         if label not in imacro.labeldefs:
 382                             fail("label " + label + " used but not defined")
 383                         link = imacro.labelrefs[label]
 384                         assert link >= 0
 385                         while True:
 386                             op = imacro.code[link]
 387                             next = op.target
 388                             op.target = imacro.labeldefs[label] - op.offset
 389                             op.target_index = imacro.labeldef_indexes[label]
 390                             if next < 0:
 391                                 break
 392                             link = next
 393
 394                     igroup.imacros.append(imacro)
 395                 imacro = None
 396
 397             else:
 398                 fail("unknown pseudo-op " + opname)
 399             continue
 400
 401         if opname not in opname2info:
 402             fail("unknown opcode " + opname)
 403
 404         info = opname2info[opname]
 405         if info.oplen == -1:
 406             fail("unimplemented opcode " + opname)
 407
 408         if imacro is None:
 409             fail("opcode %s outside of .imacro", opname)
 410
 411         # Blacklist ops that may or must use an atomized double immediate.
 412         if info.opname in ('double', 'lookupswitch', 'lookupswitchx'):
 413             fail(op.opname + " opcode not yet supported")
 414
 415         if label:
 416             imacro.labeldefs[label] = imacro.offset
 417             imacro.labeldef_indexes[label] = len(imacro.code)
 418
 419         op = Instruction(imacro.offset, info, imm1, imm2, lineno + 1)
 420         if 'JOF_JUMP' in info.flags:
 421             if imm1 in imacro.labeldefs:
 422                 # Backward reference can be resolved right away, no backpatching needed.
 423                 op.target = imacro.labeldefs[imm1] - op.offset
 424                 op.target_index = imacro.labeldef_indexes[imm1]
 425             else:
 426                 # Link op into the .target-linked backpatch chain at labelrefs[imm1].
 427                 # The linked list terminates with a -1 sentinel.
 428                 if imm1 in imacro.labelrefs:
 429                     op.target = imacro.labelrefs[imm1]
 430                 else:
 431                     op.target = -1
 432                 imacro.labelrefs[imm1] = len(imacro.code)
 433
 434         imacro.code.append(op)
 435         imacro.offset += info.oplen
 436
 437     write("uint8 js_opcode2extra[JSOP_LIMIT] = {\n")
 438     for i in range(len(opinfo)):
 439         write("    %d,  /* %s */\n" % (opcode2extra.get(i, 0), opinfo[i].jsop))
 440     write("};\n")
 441
 442     write("#define JSOP_IS_IMACOP(x) (0 \\\n")
 443     for i in sorted(opcode2extra):
 444         write(" || x == %s \\\n" % opinfo[i].jsop)
 445     write(")\n")
 446
 447     write("jsbytecode*\njs_GetImacroStart(jsbytecode* pc) {\n")
 448     for g in igroups:
 449         for m in g.imacros:
 450             start = g.name + "_imacros." + m.name
 451             write("    if (size_t(pc - %s) < %d) return %s;\n" % (start, m.offset, start))
 452
 453     write("    return NULL;\n")
 454     write("}\n")
 455
 456 if __name__ == '__main__':
 457     import sys
 458     if len(sys.argv) != 3:
 459         print "usage: python imacro_asm.py infile.jsasm outfile.c.out"
 460         sys.exit(1)
 461
 462     f = open(sys.argv[2], 'w')
 463     try:
 464         assemble(sys.argv[1], f)
 465     finally:
 466         f.close()
 467