GenArch: gen_arch.py

#! /usr/bin/env python2.4
# Yasm Architecture Generator
#
#  Copyright (C) 2006  Peter Johnson
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND OTHER CONTRIBUTORS ``AS IS''
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR OTHER CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.
"""
Generates architecture files based on an architectural description.

The architectural description is a full-fledged Python file that
is directly exec'ed by this script.

Note: this means the input file must be trusted!

The architecture file must set the following global variables:

    arch - A string containing the architecture name.  This name is used
        as the function prefix, as the arch keyword, and as the filename
        prefix, so it should be a short lowercase name with no punctuation
        or spaces.
    lsb_bit - The bit number of the least significant bit in the
        description of Fields.  The generator can handle both little and
        big bit endians.
    insn_bit_width - The number of bits in an instruction.
    machines - A list of strings (machine keywords).
    parsers - A list of strings (supported parser keywords).

After defining these globals, the architecture file should call the
functions in this module (particularly add_register, add_field, add_insn,
and add_derived_insn) to describe the ISA.
"""
import copy

_lsb_bit = None
_insn_bit_width = None
_machines = []
_parsers = []

def config_arch(lsb_bit, insn_bit_width, machines, parsers):
    global _lsb_bit, _insn_bit_width, _machines, _parsers
    _lsb_bit = lsb_bit
    _insn_bit_width = insn_bit_width
    _machines = machines
    _parsers = parsers

class _Struct(object):
    """A structure-like class that supports creation of arbitrary members
    and intelligent repr() via positional names."""
    _pos_names = []

    def __init__(self, **kwargs):
        for k,v in kwargs.iteritems():
            setattr(self, k, v)

    def __repr__(self):
        args = [repr(getattr(self, x)) for x in self._pos_names]
        args.extend(x+"="+repr(getattr(self, x)) for x in self.__dict__
                    if not x.startswith("_") and x not in self._pos_names)
        return self.__class__.__name__+"("+', '.join(args)+")"

class Register(_Struct):
    """A register class.  Register(name, reg_type, reg_index, **kwargs)"""
    _pos_names = ['name', 'reg_type', 'reg_index']

    def __init__(self, name, reg_type, reg_index, **kwargs):
        self.name = name
        self.reg_type = reg_type
        self.reg_index = reg_index
        for k,v in kwargs.iteritems():
            setattr(self, k, v)

registers = {}
def add_register(name, reg_type, reg_index, **kwargs):
    """Add a register to the global registry."""
    reg = Register(name, reg_type, reg_index, **kwargs)
    if name in registers:
        raise ValueError("duplicate register name")
    registers[name] = reg

class Field(_Struct):
    """
    An instruction field.  This can range in complexity:
        lsb/msb/width: The class will figure out the missing
            portion based on the other givens.
        ooo: Out-of-order or separated groups of bits making up a single
            field.  The constructor needs to be given a list of (msb, lsb)
            tuples; internally this is converted into a list of
            (msb, lsb, width) tuples.
        rshift: The field contents should be shifted right before being
            stored into the field bits.  The rshift value is the number
            of bits to shift right.  Defaults to 0.
        pc_rel: True if field contents are relative to the current PC
            rather than to the segment start (absolute).  Defaults to
            False.
        signed: True if field contents should be treated as signed number.
            Defaults to pc_rel.
    """
    def __init__(self, name, **kwargs):
        self.name = name
        self.rshift = 0
        self.pc_rel = False
        self.signed = False

        ooo = kwargs.pop("ooo", None)
        to_fields = kwargs.pop("to_fields", None)
        if ooo:
            self.ooo = [(msb, lsb, abs(msb-lsb)+1) for (msb, lsb) in ooo]
        elif to_fields:
            self.to_fields = to_fields
        else:
            width = kwargs.pop("width", None)
            msb = kwargs.pop("msb", None)
            lsb = kwargs.pop("lsb", None)

            # Make width/msb/lsb all jive
            if width is None:
                width = abs(msb-lsb)+1
            elif msb is None:
                if _lsb_bit == 0: msb = lsb+(width-1)
                else: msb = lsb-(width-1)
            elif lsb is None:
                if _lsb_bit == 0: lsb = msb-(width-1)
                else: lsb = msb+(width-1)
            elif width != abs(msb-lsb)+1:
                raise ValueError("width, msb, and lsb do not match")
            self.width = width
            self.msb = msb
            self.lsb = lsb
            if not _insn_bit_width:
                raise ValueError("instruction bit width not set")
            if msb < 0 or msb >= _insn_bit_width:
                raise ValueError("field extends past end of instruction")

        for k,v in kwargs.iteritems():
            setattr(self, k, v)
        if self.pc_rel and "signed" not in kwargs:
            self.signed = True

fields = {}
def add_field(name, **kwargs):
    """Add a field to the global registry."""
    field = Field(name, **kwargs)
    if name in fields:
        raise ValueError("duplicate field name")
    fields[name] = field

class Instruction(_Struct):
    """
    An instruction format.  Consists of:
        - The instruction name (mnemonic)
        - A list of operands (names)
        - A matching list of operand types
        - A mapping of "fixed" field from field names to their fixed
          numeric values
        - A mapping from field names to operand names
        - Miscellaneous other data that can be stored via keyword args
    """
    _pos_names = ['name', 'operands', 'operand_types', 'fields_fixed',
                  'fields_operands']

    def __init__(self, name, descr, operands, operand_types, fields_fixed,
                 fields_operands=None, **kwargs):
        self.name = name
        self.__doc__ = descr
        self.operands = operands
        self.operand_types = operand_types
        self.fields_fixed = fields_fixed
        # Be nice and build a reasonable default for fields_operands
        if fields_operands is None:
            fields_operands = dict((x,x) for x in operands)
        self.fields_operands = fields_operands
        self.update(**kwargs)
        
    def update(self, **kwargs):
        """
        Updates instruction format contents based on keyword arguments.
        Keywords may either be member names (e.g. keywords passed to
        __init__) or one of the following special keywords:
            update_fields_fixed: A mapping that updates the
                fields_fixed mapping (e.g. retaining unupdated members).
            fix_operands: A mapping from operand name to fixed value;
                the corresponding operand is removed from the operands
                list and the fields_operands mapping and the operand name
                and fixed value are added to the fields_fixed mapping.
                Bug: For this to work properly the operand name and field
                name must match.
            del_operands: Delete an operand and remove it from the
                fields_operands mapping.
                Bug: For this to work properly the operand name and field
                name must match.

        If operands is changed and fields_operands is not, a reasonable
        default is generated for fields_operands (field name = operand
        name for all operands).
        """
        # Handle update_fields_fixed
        update_fields_fixed = kwargs.pop("update_fields_fixed", None)
        if update_fields_fixed is not None:
            self.fields_fixed.update(update_fields_fixed)

        # Handle fix_operands
        fix_operands = kwargs.pop("fix_operands", None)
        del_operands = kwargs.pop("del_operands", [])
        if fix_operands is not None:
            # Merge fixed operand values into fields_fixed
            self.fields_fixed.update(fix_operands)
            # Append to del_operands
            del_operands.extend(o for o in fix_operands)

        # Handle del_operands and the deletion portion of fix_operands
        if del_operands:
            # Delete from operands and operand_types
            new_operands = []
            new_operand_types = []
            for o, t in zip(self.operands, self.operand_types):
                if o not in fix_operands:
                    new_operands.append(o)
                    new_operand_types.append(t)
            self.operands = new_operands
            self.operand_types = new_operand_types

            # Delete from fields_operands
            for o in fix_operands:
                del self.fields_operands[o]

        # Update remaining keywords directly
        for k,v in kwargs.iteritems():
            setattr(self, k, v)

        self.num_operands = len(self.operands)
        self.operands = tuple(self.operands)
        self.operand_types = tuple(self.operand_types)

        # Be nice and update with a reasonable default for fields_operands
        if "operands" in kwargs and "fields_operands" not in kwargs:
            self.fields_operands = dict((x,x) for x in self.operands)

        # Do some sanity checks
        if len(self.operands) != len(self.operand_types):
            raise ValueError("mismatch between operands and types length")

        for (k,v) in self.fields_fixed.iteritems():
            if k not in fields:
                raise ValueError("unrecognized field name '%s'" % k)
        for (k,v) in self.fields_operands.iteritems():
            if k not in fields:
                raise ValueError("unrecognized field name '%s'" % k)
            if v not in self.operands:
                raise ValueError("field '%s' references nonexistent operand '%s'" % (k,v))

        # Check for duplicates in fields_fixed and fields_operands
        fset = set(x for x in self.fields_fixed)
        fset &= set(x for x in self.fields_operands)
        if fset:
            raise ValueError("Duplicate fixed and operands fields %s" %
                             str(fset))

        # Build an operand_fields mapping
        o2f = dict((o,f) for (f,o) in self.fields_operands.iteritems())
        self.operand_fields = tuple(o2f[x] for x in self.operands)

instructions = {}
used_types = set()
max_operands = 0
def add_insn_base(name, parent=None, **kwargs):
    """Add an instruction format to the global registry."""
    global used_types, max_operands

    insns = instructions.setdefault(name, [])
    if parent:
        insn = copy.deepcopy(parent)
        insn.update(**kwargs)
    else:
        insn = Instruction(name, **kwargs)
    insns.append(insn)

    used_types |= set(insn.operand_types)
    if insn.num_operands > max_operands:
        max_operands = insn.num_operands

def add_insn(name, descr, operands, operand_types, fields_fixed,
             fields_operands=None, **kwargs):
    """
    Add an instruction format to the global registry, with positional
    arguments (name, descr, operands, operand_types, fields_fixed,
    fields_operands) as well as accepting additional keyword arguments.
    """
    kwargs["descr"] = descr
    kwargs["operands"] = operands
    kwargs["operand_types"] = operand_types
    kwargs["fields_fixed"] = fields_fixed
    kwargs["fields_operands"] = fields_operands
    add_insn_base(name, **kwargs)

def add_derived_insn(name, parent, **kwargs):
    """
    Add a derived instruction to the global registry.  This copies all
    instruction formats from the specified parent instruction (looked up
    by name) to a new name, possibly modifying via keyword arguments.
    """
    for x in instructions[parent]:
        add_insn_base(name, parent=x, **kwargs)

def add_derived_one_insn(name, parent, **kwargs):
    add_insn_base(name, parent=instructions[parent][0], **kwargs)

def add_macro_insn(name, descr, operands, operand_types, parent,
                   parent_operands):
    raise NotImplemented
    # Find a match on the parent with matching operands/operand_types.
    for insn in instructions[parent]:
        pass

def merge_fields(**fieldvals):
    """
    Merge a set of Fields into a single integer value.
    Checks for overlaps.
    """
    opcode = 0
    filled = 0
    for fname, v in fieldvals.iteritems():
        f = fields[fname]
        try:
            ooo = f.ooo
        except AttributeError:
            ooo = [(f.msb, f.lsb)]
        for g in ooo:
            width = abs(g[0]-g[1])+1
            if _lsb_bit == 0:
                pos = g[1]
            else:
                pos = _lsb_bit-g[1]
            mask = 0
            for x in range(width):
                mask |= 1<<x
            if filled & (mask<<pos):
                raise ValueError("field overlap (filled %x, want '%s' (%x))" %
                                 (filled, fname, mask<<pos))
            filled |= mask << pos
            opcode |= ((v>>f.rshift) & mask) << pos
            v >>= width
    return opcode

def get_insn_fixed(name, index):
    """Get the value of combining just the fixed fields for the
    corresponding instruction name and format index."""
    return merge_fields(**instructions[name][index]["fields_fixed"])

def get_groups():
    """
    Determine sets of instructions ("groups") that share the same operand
    lists and mapping from operand to fields.
    """
    groups = {}
    for iname in instructions:
        # First part of signature: operand types
        all_types = sorted(insn.operand_types
                           for insn in instructions[iname])
        sig1 = tuple(tuple(typelist) for typelist in all_types)

        # Second part of signature: operand->field mapping
        for insn in instructions[iname]:
            # Lookup from operand name to operand index
            # (this is needed because each instruction can have its own
            # naming for operands)
            oi = dict((y,x) for (x,y) in enumerate(insn.operands))
            sig2 = tuple(sorted((oi[op],f) for (f, op)
                                in insn.fields_operands.iteritems()))

        # Save instruction into field mapping
        groups.setdefault((sig1, sig2), []).append(iname)
    return groups

def get_msb(v):
    if v < 0:
        raise ValueError("does not support negative numbers")
    n = 0
    while v != 0:
        v >>= 1
        n += 1
    return n

def get_mask(v):
    msb = get_msb(v)
    if msb == 0: msb = 1
    return sum(1<<x for x in range(msb))

def gen_arch_h(out, arch):
    """Generate [arch]_arch.c output file."""
    pass

def gen_arch_c(out, arch):
    """Generate [arch]_arch.h output file."""
    pass

def gen_id(out, arch):
    """Generate [arch]_id.c output file."""
    import pprint
    from textwrap import wrap
    pp = pprint.PrettyPrinter(indent=4)
    #pp.pprint(registers)
    #pp.pprint(fields)
    #pp.pprint(instructions)

    define_lines = []
    for n, v in enumerate(used_types):
        define_lines.append("#define OPT_%s\t%#x" % (v, n))
    define_lines.append("#define OPT_MASK\t%#x" % get_mask(n))
    shift = get_msb(n)

    define_lines.append("")

    for n, v in enumerate(fields):
        define_lines.append("#define OPA_%s\t(%#x<<%d)" % (v, n, shift))
    define_lines.append("#define OPA_MASK\t(%#x<<%d)" % (get_mask(n), shift))

    print >> out, '\n'.join(define_lines)
    print >> out

    groups = get_groups()
    #pp.pprint(groups)

    iname_grp = {}
    iname_needfields = {}
    group_lines = []
    for num, match in enumerate(sorted(groups)):
        # Determine field differences between instructions in group
        fields_common = {}
        fields_diff = {}
        for iname in groups[match]:
            for insn in instructions[iname]:
                common_def = dict((f,o) for (f,o)
                                  in insn.fields_fixed.iteritems())
                common = fields_common.setdefault(insn.operand_types,
                                                  common_def)
                diff = fields_diff.setdefault(insn.operand_types, set())
                for (field, operand) in insn.fields_fixed.iteritems():
                    if field not in common:
                        diff.add(field)
                    elif operand != common[field]:
                        del common[field]
                        diff.add(field)

        #pp.pprint(fields_diff)
        
        for iname in groups[match]:
            iname_grp[iname] = "grp%d" % num
            iname_needfields[iname] = set()
            for fieldset in fields_diff.itervalues():
                iname_needfields[iname] |= fieldset
                for field in fieldset:
                    for insn in instructions[iname]:
                        try: del fields_common[insn.operand_types][field]
                        except KeyError: pass

        #pp.pprint(fields_common)
        #pp.pprint(iname_needfields)

        group_lines.extend(wrap("/* %s */" % ', '.join(groups[match]),
                                subsequent_indent=" * "))
        group_lines.append("static const %s_insn_info grp%d = {" % (arch, num))
        insn_lines = []
        for insn in instructions[groups[match][0]]:
            insn_line = []
            insn_line.append("0x%0*x" % (_insn_bit_width/4,
                             merge_fields(**fields_common[insn.operand_types])))
            insn_line.append(str(insn.num_operands))
            
            operands = ["OPT_%s|OPA_%s" % (t, f) for (t, f)
                        in zip(insn.operand_types, insn.operand_fields)]
            operands.extend("0" for x in range(max_operands-insn.num_operands))
            insn_line.append("{"+', '.join(operands)+"}")
            insn_lines.append("    { "+', '.join(insn_line)+" }")
        group_lines.extend(',\n'.join(insn_lines).split('\n'))
        group_lines.append("};")
        group_lines.append("")
    print >> out, '\n'.join(group_lines)

    return iname_grp, iname_needfields

def gen_gap(out, arch, iname_grp, iname_needfields):
    """Generate [arch]_parse.gap output file."""
    print >> out, "ARCH\t%s" % arch
    print >> out, "PARSERS\t%s" % ' '.join(_parsers)

    insn_lines = []
    for iname in sorted(iname_grp):
        fields_fixed = instructions[iname][0].fields_fixed
        #print iname, fields_fixed, iname_needfields[iname]
        fvs = dict((f, fields_fixed[f]) for f in iname_needfields[iname]
                   if f in fields_fixed)
        insn_lines.append("INSN\t-\t%s\t%s\t0x%0*x" %
                          (iname, iname_grp[iname], _insn_bit_width/4,
                           merge_fields(**fvs)))
    print >> out, '\n'.join(insn_lines)
    print >> out

    reg_lines = []
    for regname in sorted(registers):
        reg = registers[regname]
        reg_lines.append("REG\t%s\t%s\t%d" %
                         (regname, reg.reg_type, reg.reg_index))
    print >> out, '\n'.join(reg_lines)+"\n"

def gen_code(arch):
    """Generate all output files."""
    iname_grp, iname_needfields = gen_id(open("%sid.c" % arch, "w"), arch)
    gen_gap(open("%sparse.gap" % arch, "w"), arch, iname_grp,
            iname_needfields)
    gen_arch_h(open("%sarch.h" % arch, "w"), arch)
    gen_arch_c(open("%sarch.c" % arch, "w"), arch)