from __future__ import absolute_import
import srcgen
from constant_hash import compute_quadratic
from unique_table import UniqueSeqTable
from collections import OrderedDict, defaultdict
import math
from itertools import groupby
from cdsl.registers import RegClass, Register, Stack
from cdsl.predicates import FieldPredicate, TypePredicate
from cdsl.settings import SettingGroup
from cdsl.formats import instruction_context, InstructionFormat
try:
from typing import Sequence, Set, Tuple, List, Dict, Iterable, DefaultDict, TYPE_CHECKING if TYPE_CHECKING:
from cdsl.isa import TargetISA, OperandConstraint, Encoding, CPUMode, EncRecipe, RecipePred from cdsl.predicates import PredNode, PredLeaf from cdsl.types import ValueType from cdsl.instructions import Instruction from cdsl.xform import XFormGroup except ImportError:
pass
def emit_instp(instp, fmt, has_func=False):
iform = instp.predicate_context()
if iform == instruction_context:
fmt.line('let args = inst.arguments(&func.dfg.value_lists);')
fmt.line(instp.rust_predicate(0))
return
assert isinstance(iform, InstructionFormat)
has_type_check = False
leafs = set() instp.predicate_leafs(leafs)
fnames = set() for p in leafs:
if isinstance(p, FieldPredicate):
fnames.add(p.field.rust_destructuring_name())
else:
assert isinstance(p, TypePredicate)
has_type_check = True
fields = ', '.join(sorted(fnames))
with fmt.indented(
'if let ir::InstructionData::{} {{ {}, .. }} = *inst {{'
.format(iform.name, fields), '}'):
if has_type_check:
assert has_func, "Recipe predicates can't check type variables."
fmt.line('let args = inst.arguments(&func.dfg.value_lists);')
elif has_func:
fmt.line('let _ = func;')
fmt.format('return {};', instp.rust_predicate(0))
fmt.line('unreachable!();')
def emit_inst_predicates(instps, fmt):
for instp, number in instps.items():
name = 'inst_predicate_{}'.format(number)
with fmt.indented(
'fn {}(func: &ir::Function, inst: &ir::InstructionData)'
'-> bool {{'.format(name), '}'):
emit_instp(instp, fmt, has_func=True)
with fmt.indented(
'pub static INST_PREDICATES: [InstPredicate; {}] = ['
.format(len(instps)), '];'):
for instp, number in instps.items():
fmt.format('inst_predicate_{},', number)
def emit_recipe_predicates(isa, fmt):
pname = dict()
for rcp in isa.all_recipes:
p = rcp.recipe_pred()
if p is None or p in pname:
continue
name = 'recipe_predicate_{}'.format(rcp.name.lower())
pname[p] = name
isap, instp = p
with fmt.indented(
'fn {}({}: ::settings::PredicateView, '
'{}: &ir::InstructionData) -> bool {{'
.format(
name,
'isap' if isap else '_',
'inst' if instp else '_'), '}'):
if isap:
n = isa.settings.predicate_number[isap]
with fmt.indented('if !isap.test({}) {{'.format(n), '}'):
fmt.line('return false;')
if instp:
emit_instp(instp, fmt)
else:
fmt.line('true')
with fmt.indented(
'pub static RECIPE_PREDICATES: [RecipePredicate; {}] = ['
.format(len(isa.all_recipes)), '];'):
for rcp in isa.all_recipes:
p = rcp.recipe_pred()
if p is None:
fmt.line('None,')
else:
fmt.format('Some({}),', pname[p])
class Encoder:
def __init__(self, isa):
self.isa = isa
self.NR = len(isa.all_recipes)
self.NI = len(isa.instp_number)
self.words = list() self.docs = list()
CODE_BITS = 16
PRED_START = 0x1000
PRED_BITS = 12
PRED_MASK = (1 << PRED_BITS) - 1
def max_skip(self):
return (1 << (self.CODE_BITS - self.PRED_BITS)) - 1
def recipe(self, enc, final):
offset = len(self.words)
code = 2 * enc.recipe.number
doc = '--> {}'.format(enc)
if final:
code += 1
doc += ' and stop'
assert(code < self.PRED_START)
self.words.extend((code, enc.encbits))
self.docs.append((offset, doc))
def _pred(self, pred, skip, n):
assert n <= self.PRED_MASK
code = n | (skip << self.PRED_BITS)
code += self.PRED_START
assert code < (1 << self.CODE_BITS)
if skip == 0:
doc = 'stop'
else:
doc = 'skip ' + str(skip)
doc = '{} unless {}'.format(doc, pred)
self.docs.append((len(self.words), doc))
self.words.append(code)
def instp(self, pred, skip):
number = self.isa.instp_number[pred]
self._pred(pred, skip, number)
def isap(self, pred, skip):
n = self.isa.settings.predicate_number[pred]
self._pred(pred, skip, self.NI + n)
class EncNode(object):
def size(self):
raise NotImplementedError('EncNode.size() is abstract')
def encode(self, encoder, final):
raise NotImplementedError('EncNode.encode() is abstract')
def optimize(self):
return self
def predicate(self):
return None
class EncPred(EncNode):
def __init__(self, pred, children):
self.pred = pred
self.children = children
def size(self):
s = 1 if self.pred else 0
s += sum(c.size() for c in self.children)
return s
def encode(self, encoder, final):
if self.pred:
skip = 0 if final else self.size() - 1
ctx = self.pred.predicate_context()
if isinstance(ctx, SettingGroup):
encoder.isap(self.pred, skip)
else:
encoder.instp(self.pred, skip)
final_idx = len(self.children) - 1 if final else -1
for idx, node in enumerate(self.children):
node.encode(encoder, idx == final_idx)
def predicate(self):
return self.pred
def optimize(self):
cnodes = list() for pred, niter in groupby(
map(lambda c: c.optimize(), self.children),
key=lambda c: c.predicate()):
nodes = list(niter)
if pred is None or len(nodes) <= 1:
cnodes.extend(nodes)
continue
n0 = nodes[0]
assert isinstance(n0, EncPred)
for n in nodes[1:]:
assert isinstance(n, EncPred)
n0.children.extend(n.children)
cnodes.append(n0)
if self.pred is None and len(cnodes) == 1:
return cnodes[0]
else:
self.children = cnodes
return self
class EncLeaf(EncNode):
def __init__(self, encoding):
self.encoding = encoding
def size(self):
return 2
def encode(self, encoder, final):
encoder.recipe(self.encoding, final)
class EncList(object):
def __init__(self, inst, ty):
self.inst = inst
self.ty = ty
self.encodings = []
def name(self):
name = self.inst.name
if self.ty:
name = '{}.{}'.format(name, self.ty.name)
if self.encodings:
name += ' ({})'.format(self.encodings[0].cpumode)
return name
def encoder_tree(self):
forest = list() for enc in self.encodings:
n = EncLeaf(enc) if enc.instp:
n = EncPred(enc.instp, [n])
if enc.isap:
n = EncPred(enc.isap, [n])
forest.append(n)
return EncPred(None, forest).optimize()
def encode(self, seq_table, doc_table, isa):
encoder = Encoder(isa)
tree = self.encoder_tree()
tree.encode(encoder, True)
self.offset = seq_table.add(encoder.words)
doc_table[self.offset].append(
'{:06x}: {}'.format(self.offset, self.name()))
for pos, doc in encoder.docs:
doc_table[self.offset + pos].append(doc)
doc_table[self.offset + len(encoder.words)].insert(
0, 'end of: {}'.format(self.name()))
class Level2Table(object):
def __init__(self, ty, legalize):
self.ty = ty
self.legalize = legalize
self.lists = OrderedDict()
def __getitem__(self, inst):
ls = self.lists.get(inst)
if not ls:
ls = EncList(inst, self.ty)
self.lists[inst] = ls
return ls
def is_empty(self):
return len(self.lists) == 0
def enclists(self):
return iter(self.lists.values())
def layout_hashtable(self, level2_hashtables, level2_doc):
def hash_func(enclist):
return enclist.inst.number
hash_table = compute_quadratic(self.lists.values(), hash_func)
self.hash_table_offset = len(level2_hashtables)
self.hash_table_len = len(hash_table)
level2_doc[self.hash_table_offset].append(
'{:06x}: {}, {} entries'.format(
self.hash_table_offset,
self.ty,
self.hash_table_len))
level2_hashtables.extend(hash_table)
class Level1Table(object):
def __init__(self, cpumode):
self.cpumode = cpumode
self.tables = OrderedDict()
if cpumode.default_legalize is None:
raise AssertionError(
'CPU mode {}.{} needs a default legalize action'
.format(cpumode.isa, cpumode))
self.legalize_code = cpumode.isa.legalize_code(
cpumode.default_legalize)
def __getitem__(self, ty):
tbl = self.tables.get(ty)
if not tbl:
legalize = self.cpumode.get_legalize_action(ty)
self.cpumode.isa.legalize_code(legalize)
tbl = Level2Table(ty, legalize)
self.tables[ty] = tbl
return tbl
def l2tables(self):
return (l2 for l2 in self.tables.values() if not l2.is_empty())
def make_tables(cpumode):
table = Level1Table(cpumode)
for enc in cpumode.encodings:
ty = enc.ctrl_typevar()
inst = enc.inst
table[ty][inst].encodings.append(enc)
for ty in cpumode.type_legalize.keys():
table[ty]
return table
def encode_enclists(level1, seq_table, doc_table, isa):
for level2 in level1.l2tables():
for enclist in level2.enclists():
enclist.encode(seq_table, doc_table, isa)
def emit_enclists(seq_table, doc_table, fmt):
with fmt.indented(
'pub static ENCLISTS: [u16; {}] = ['.format(len(seq_table.table)),
'];'):
line = ''
for idx, entry in enumerate(seq_table.table):
if idx in doc_table:
if line:
fmt.line(line)
line = ''
for doc in doc_table[idx]:
fmt.comment(doc)
line += '{:#06x}, '.format(entry)
if line:
fmt.line(line)
def encode_level2_hashtables(level1, level2_hashtables, level2_doc):
for level2 in level1.l2tables():
level2.layout_hashtable(level2_hashtables, level2_doc)
def emit_level2_hashtables(level2_hashtables, offt, level2_doc, fmt):
with fmt.indented(
'pub static LEVEL2: [Level2Entry<{}>; {}] = ['
.format(offt, len(level2_hashtables)),
'];'):
for offset, entry in enumerate(level2_hashtables):
if offset in level2_doc:
for doc in level2_doc[offset]:
fmt.comment(doc)
if entry:
fmt.line(
'Level2Entry ' +
'{{ opcode: Some(ir::Opcode::{}), offset: {:#08x} }},'
.format(entry.inst.camel_name, entry.offset))
else:
fmt.line(
'Level2Entry ' +
'{ opcode: None, offset: 0 },')
def emit_level1_hashtable(cpumode, level1, offt, fmt):
def hash_func(level2):
return level2.ty.number if level2.ty is not None else 0
hash_table = compute_quadratic(level1.tables.values(), hash_func)
with fmt.indented(
'pub static LEVEL1_{}: [Level1Entry<{}>; {}] = ['
.format(cpumode.name.upper(), offt, len(hash_table)), '];'):
for level2 in hash_table:
if not level2:
fmt.format(
'Level1Entry {{ ty: ir::types::INVALID, log2len: !0, '
'offset: 0, legalize: {} }},',
level1.legalize_code)
continue
if level2.ty is not None:
tyname = level2.ty.rust_name()
else:
tyname = 'ir::types::INVALID'
lcode = cpumode.isa.legalize_code(level2.legalize)
if level2.is_empty():
fmt.format(
'Level1Entry {{ '
'ty: {}, log2len: 0, offset: !0 - 1, '
'legalize: {} }}, // {}',
tyname, lcode, level2.legalize)
continue
l2l = int(math.log(level2.hash_table_len, 2))
assert l2l > 0, "Level2 hash table too small"
fmt.format(
'Level1Entry {{ '
'ty: {}, log2len: {}, offset: {:#08x}, '
'legalize: {} }}, // {}',
tyname, l2l, level2.hash_table_offset,
lcode, level2.legalize)
def offset_type(length):
if length <= 0x10000:
return 'u16'
else:
assert length <= 0x100000000, "Table too big"
return 'u32'
def emit_recipe_names(isa, fmt):
with fmt.indented(
'static RECIPE_NAMES: [&str; {}] = ['
.format(len(isa.all_recipes)), '];'):
for r in isa.all_recipes:
fmt.line('"{}",'.format(r.name))
def emit_recipe_constraints(isa, fmt):
with fmt.indented(
'static RECIPE_CONSTRAINTS: [RecipeConstraints; {}] = ['
.format(len(isa.all_recipes)), '];'):
for r in isa.all_recipes:
fmt.comment('Constraints for recipe {}:'.format(r.name))
tied_i2o, tied_o2i = r.ties()
fixed_ins, fixed_outs = r.fixed_ops()
with fmt.indented('RecipeConstraints {', '},'):
emit_operand_constraints(
r, r.ins, 'ins', tied_i2o, fixed_outs, fmt)
emit_operand_constraints(
r, r.outs, 'outs', tied_o2i, fixed_ins, fmt)
fmt.format('fixed_ins: {},', str(bool(fixed_ins)).lower())
fmt.format('fixed_outs: {},', str(bool(fixed_outs)).lower())
fmt.format('tied_ops: {},', str(bool(tied_i2o)).lower())
fmt.format(
'clobbers_flags: {},',
str(bool(r.clobbers_flags)).lower())
def emit_operand_constraints(
recipe, seq, field, tied, fixops, fmt ):
if len(seq) == 0:
fmt.line('{}: &[],'.format(field))
return
with fmt.indented('{}: &['.format(field), '],'):
for n, cons in enumerate(seq):
with fmt.indented('OperandConstraint {', '},'):
if isinstance(cons, RegClass):
if n in tied:
fmt.format('kind: ConstraintKind::Tied({}),', tied[n])
else:
fmt.line('kind: ConstraintKind::Reg,')
fmt.format('regclass: &{}_DATA,', cons)
elif isinstance(cons, Register):
assert n not in tied, "Can't tie fixed register operand"
t = 'FixedTied' if cons in fixops else 'FixedReg'
fmt.format('kind: ConstraintKind::{}({}),', t, cons.unit)
fmt.format('regclass: &{}_DATA,', cons.regclass)
elif isinstance(cons, int):
assert cons == tied[n], "Invalid tied constraint"
fmt.format('kind: ConstraintKind::Tied({}),', cons)
fmt.format('regclass: &{}_DATA,', recipe.ins[cons])
elif isinstance(cons, Stack):
assert n not in tied, "Can't tie stack operand"
fmt.line('kind: ConstraintKind::Stack,')
fmt.format('regclass: &{}_DATA,', cons.regclass)
else:
raise AssertionError(
'Unsupported constraint {}'.format(cons))
def emit_recipe_sizing(isa, fmt):
with fmt.indented(
'static RECIPE_SIZING: [RecipeSizing; {}] = ['
.format(len(isa.all_recipes)), '];'):
for r in isa.all_recipes:
fmt.comment('Code size information for recipe {}:'.format(r.name))
with fmt.indented('RecipeSizing {', '},'):
fmt.format('base_size: {},', r.base_size)
fmt.format('compute_size: {},', r.compute_size)
if r.branch_range:
fmt.format(
'branch_range: '
'Some(BranchRange {{ origin: {}, bits: {} }}),',
*r.branch_range)
else:
fmt.line('branch_range: None,')
def gen_isa(isa, fmt):
emit_recipe_predicates(isa, fmt)
emit_inst_predicates(isa.instp_number, fmt)
level1_tables = dict()
seq_table = UniqueSeqTable()
doc_table = defaultdict(list)
level2_hashtables = list() level2_doc = defaultdict(list)
for cpumode in isa.cpumodes:
level2_doc[len(level2_hashtables)].append(cpumode.name)
level1 = make_tables(cpumode)
level1_tables[cpumode] = level1
encode_enclists(level1, seq_table, doc_table, isa)
encode_level2_hashtables(level1, level2_hashtables, level2_doc)
level1_offt = offset_type(len(level2_hashtables))
level2_offt = offset_type(len(seq_table.table))
emit_enclists(seq_table, doc_table, fmt)
emit_level2_hashtables(level2_hashtables, level2_offt, level2_doc, fmt)
for cpumode in isa.cpumodes:
emit_level1_hashtable(
cpumode, level1_tables[cpumode], level1_offt, fmt)
emit_recipe_names(isa, fmt)
emit_recipe_constraints(isa, fmt)
emit_recipe_sizing(isa, fmt)
with fmt.indented('pub static INFO: isa::EncInfo = isa::EncInfo {', '};'):
fmt.line('constraints: &RECIPE_CONSTRAINTS,')
fmt.line('sizing: &RECIPE_SIZING,')
fmt.line('names: &RECIPE_NAMES,')
def generate(isas, out_dir):
for isa in isas:
fmt = srcgen.Formatter()
gen_isa(isa, fmt)
fmt.update_file('encoding-{}.rs'.format(isa.name), out_dir)