Mercurial > lcfOS
changeset 357:818be710e13d
Added acceptance function to burg
| author | Windel Bouwman |
|---|---|
| date | Fri, 14 Mar 2014 15:14:29 +0100 |
| parents | 52492b304adf |
| children | 5ef1cb1bb54f |
| files | doc/compiler.rst kernel/kernel.c3 python/baselex.py python/burg.x python/ppci/target/arm/__init__.py python/ppci/target/arm/arm.brg python/ppci/target/thumb/arm.brg python/pyburg.py test/sample4.brg |
| diffstat | 9 files changed, 89 insertions(+), 58 deletions(-) [+] |
line wrap: on
line diff
--- a/doc/compiler.rst Fri Mar 14 13:02:16 2014 +0100 +++ b/doc/compiler.rst Fri Mar 14 15:14:29 2014 +0100 @@ -77,14 +77,27 @@ The back-end is more complicated. There are several steps to be taken here. -1. Instruction selection -2. register allocation -3. Peep hole optimization? -4. real code generation +1. Canonicalization +2. Tree creation +3. Instruction selection +4. register allocation +5. Instruction emission +6. TODO: Peep hole optimization? .. automodule:: ppci.codegen :members: +Canonicalize +~~~~~~~~~~~~ + +During this phase, the IR-code is made simpler. Function calls are pulled pulled +to top level and the frame pointer is introduced. + +Tree building +~~~~~~~~~~~~~ + +From IR-code a tree is generated which can be used to select instructions. + Instruction selection ~~~~~~~~~~~~~~~~~~~~~ @@ -97,3 +110,9 @@ // .. autoclass:: ppci.irmach.AbstractInstruction +Register allocation +~~~~~~~~~~~~~~~~~~~ + +The selected instructions are used to select correct registers. + +
--- a/kernel/kernel.c3 Fri Mar 14 13:02:16 2014 +0100 +++ b/kernel/kernel.c3 Fri Mar 14 15:14:29 2014 +0100 @@ -14,7 +14,7 @@ io.println("Welcome to lcfos!"); // io.print_int(0x1337); - process.init(); + // process.init(); //memory:init(); //Process proc = new process:Process();
--- a/python/baselex.py Fri Mar 14 13:02:16 2014 +0100 +++ b/python/baselex.py Fri Mar 14 15:14:29 2014 +0100 @@ -1,6 +1,6 @@ import re -from ppci import Token +from ppci import Token, CompilerError def tokenize(tok_spec, txt): tok_re = '|'.join('(?P<{}>{})'.format(pair[0], pair[1]) for pair in tok_spec) @@ -21,4 +21,4 @@ pos = mo.end() mo = gettok(line, pos) if len(line) != pos: - raise ParserException('Lex fault at {}'.format(line[pos:])) + raise CompilerError('Lex fault at {}'.format(line[pos:]))
--- a/python/burg.x Fri Mar 14 13:02:16 2014 +0100 +++ b/python/burg.x Fri Mar 14 15:14:29 2014 +0100 @@ -1,5 +1,5 @@ -%tokens ':' ';' '(' ')' ',' template id number '%%' '%terminal' header +%tokens ':' ';' '(' ')' ',' string id number '%%' '%terminal' header %% @@ -20,7 +20,8 @@ rules: | rules rule; -rule: id ':' tree cost template { self.system.add_rule($1.val, $3, $4, $5.val) }; +rule: id ':' tree cost string { self.system.add_rule($1.val, $3, $4, None, $5.val) }; +rule: id ':' tree cost string string { self.system.add_rule($1.val, $3, $4, $5.val, $6.val) }; cost: number { return $1.val };
--- a/python/ppci/target/arm/__init__.py Fri Mar 14 13:02:16 2014 +0100 +++ b/python/ppci/target/arm/__init__.py Fri Mar 14 15:14:29 2014 +0100 @@ -4,7 +4,7 @@ from ..arm.registers import R8, R9, R10, R11, R12, SP, LR, PC from ..arm.registers import register_range -from .instructions import Dcd, Mov, Add, Sub, Orr1, Mul, Mov2, Add1, Mul1 +from .instructions import Dcd, Mov, Mov1, Add, Sub, Orr1, Mul, Mov2, Add1, Mul1 from .instructions import Lsr1, Lsl1, And1, Sub1 from .instructions import B, Bl, Ble, Bgt, Beq, Blt, Cmp, Cmp2 from .instructions import Push, Pop, Str, Ldr, Ldr3, Str1, Ldr1, Adr @@ -29,6 +29,7 @@ self.add_lowering(Mul1, lambda im: Mul1(im.dst[0], im.src[0], im.src[1])) self.add_lowering(Lsr1, lambda im: Lsr1(im.dst[0], im.src[0], im.src[1])) self.add_lowering(And1, lambda im: And1(im.dst[0], im.src[0], im.src[1])) + self.add_lowering(Mov1, lambda im: Mov1(im.dst[0], im.others[0])) def make_parser(self): # Assembly grammar:
--- a/python/ppci/target/arm/arm.brg Fri Mar 14 13:02:16 2014 +0100 +++ b/python/ppci/target/arm/arm.brg Fri Mar 14 15:14:29 2014 +0100 @@ -1,7 +1,7 @@ from ppci.target.arm.instructions import Add1, Sub1, Mul1 from ppci.target.arm.instructions import Ldr1, Ldr3, Adr -from ppci.target.arm.instructions import And1, Lsr1, Lsl1 +from ppci.target.arm.instructions import And1, Lsr1, Lsl1, Mov1 %% @@ -12,22 +12,25 @@ %% -reg: ADDI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Add1, dst=[d], src=[$1, $2]); return d .) -reg: SUBI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Sub1, dst=[d], src=[$1, $2]); return d .) -reg: MULI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Mul1, dst=[d], src=[$1, $2]); return d .) -reg: ANDI32(reg, reg) 2 (. d = self.newTmp(); self.emit(And1, dst=[d], src=[$1, $2]); return d .) -reg: SHRI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Lsr1, dst=[d], src=[$1, $2]); return d .) +reg: ADDI32(reg, reg) 2 'd = self.newTmp(); self.emit(Add1, dst=[d], src=[c0, c1]); return d' +reg: SUBI32(reg, reg) 2 'd = self.newTmp(); self.emit(Sub1, dst=[d], src=[c0, c1]); return d' +reg: MULI32(reg, reg) 2 'd = self.newTmp(); self.emit(Mul1, dst=[d], src=[c0, c1]); return d' +reg: ANDI32(reg, reg) 2 'd = self.newTmp(); self.emit(And1, dst=[d], src=[c0, c1]); return d' +reg: SHRI32(reg, reg) 2 'd = self.newTmp(); self.emit(Lsr1, dst=[d], src=[c0, c1]); return d' -reg: MEMI32(ADDI32(reg, cn)) 2 (. d = self.newTmp(); self.emit(Ldr1, dst=[d], src=[$1], others=[$2]); return d .) -reg: MEMI32(reg) 2 (. d = self.newTmp(); self.emit(Ldr1, dst=[d], src=[$1], others=[0]); return d .) +reg: MEMI32(ADDI32(reg, cn)) 2 'd = self.newTmp(); self.emit(Ldr1, dst=[d], src=[c0], others=[c1]); return d' +reg: MEMI32(reg) 2 'd = self.newTmp(); self.emit(Ldr1, dst=[d], src=[c0], others=[0]); return d' -cn: CONSTI32 0 (. return $$.value .) +cn: CONSTI32 0 'return tree.value' -reg: CONSTI32 3 (. d = self.newTmp(); ln = self.selector.frame.add_constant($$.value); self.emit(Ldr3, dst=[d], others=[ln]); return d .) +reg: CONSTI32 6 'd = self.newTmp(); ln = self.selector.frame.add_constant(tree.value); self.emit(Ldr3, dst=[d], others=[ln]); return d' + +reg: CONSTI32 2 'return (type(tree.value) is int) and (tree.value < 256)' 'd = self.newTmp(); self.emit(Mov1, dst=[d], others=[tree.value]); return d' -reg: ADR(CONSTDATA) 2 (. d = self.newTmp(); ln = self.selector.frame.add_constant($$.children[0].value); self.emit(Adr, dst=[d], others=[ln]); return d .) +reg: ADR(CONSTDATA) 2 'd = self.newTmp(); ln = self.selector.frame.add_constant(tree.children[0].value); self.emit(Adr, dst=[d], others=[ln]); return d' -reg: REGI32 1 (. return $$.value .) +reg: REGI32 1 'return tree.value' -reg: CALL 1 (. return self.selector.munchCall($$.value) .) +reg: CALL 1 'return self.selector.munchCall(tree.value)' +
--- a/python/ppci/target/thumb/arm.brg Fri Mar 14 13:02:16 2014 +0100 +++ b/python/ppci/target/thumb/arm.brg Fri Mar 14 15:14:29 2014 +0100 @@ -14,18 +14,18 @@ %% -reg: ADDI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Add3, dst=[d], src=[$1, $2]); return d .) -reg: SUBI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Sub3, dst=[d], src=[$1, $2]); return d .) -reg: ORI32(reg, reg) 2 (. d = self.newTmp(); self.selector.move(d, $1); self.emit(Orr, dst=[], src=[d, $2]); return d .) -reg: SHLI32(reg, reg) 2 (. d = self.newTmp(); self.selector.move(d, $1); self.emit(Lsl, dst=[], src=[d, $2]); return d .) -reg: MULI32(reg, reg) 2 (. d = self.newTmp(); self.selector.move(d, $1); self.emit(Mul, dst=[d], src=[$2, d]); return d .) +reg: ADDI32(reg, reg) 2 'd = self.newTmp(); self.emit(Add3, dst=[d], src=[c0, c1]); return d' +reg: SUBI32(reg, reg) 2 'd = self.newTmp(); self.emit(Sub3, dst=[d], src=[c0, c1]); return d' +reg: ORI32(reg, reg) 2 'd = self.newTmp(); self.selector.move(d, c0); self.emit(Orr, dst=[], src=[d, c1]); return d' +reg: SHLI32(reg, reg) 2 'd = self.newTmp(); self.selector.move(d, c0); self.emit(Lsl, dst=[], src=[d, c1]); return d' +reg: MULI32(reg, reg) 2 'd = self.newTmp(); self.selector.move(d, c0); self.emit(Mul, dst=[d], src=[c1, d]); return d' -reg: CONSTI32 3 (. d = self.newTmp(); ln = self.selector.frame.addConstant($$.value); self.emit(Ldr3, dst=[d], others=[ln]); return d .) -reg: MEMI32(reg) 4 (. d = self.newTmp(); self.emit(Ldr2, dst=[d], src=[$1], others=[0]); return d .) -reg: REGI32 1 (. return $$.value .) -reg: CALL 1 (. return self.selector.munchCall($$.value) .) +reg: CONSTI32 3 'd = self.newTmp(); ln = self.selector.frame.addConstant(tree.value); self.emit(Ldr3, dst=[d], others=[ln]); return d' +reg: MEMI32(reg) 4 'd = self.newTmp(); self.emit(Ldr2, dst=[d], src=[c0], others=[0]); return d' +reg: REGI32 1 'return tree.value' +reg: CALL 1 'return self.selector.munchCall(tree.value)' -stmt: MOVI32(MEMI32(addr), reg) 3 (. self.emit(Str2, src=[$1, $2]) .) +stmt: MOVI32(MEMI32(addr), reg) 3 'self.emit(Str2, src=[c0, c1])' -addr: reg 2 (. .) +addr: reg 0 ''
--- a/python/pyburg.py Fri Mar 14 13:02:16 2014 +0100 +++ b/python/pyburg.py Fri Mar 14 15:14:29 2014 +0100 @@ -76,8 +76,7 @@ ('id', r'[A-Za-z][A-Za-z\d_]*', lambda typ, val: (typ, val)), ('kw', r'%[A-Za-z][A-Za-z\d_]*', lambda typ, val: (val, val)), ('number', r'\d+', lambda typ, val: (typ, int(val))), - ('STRING', r"'[^']*'", lambda typ, val: ('id', val[1:-1])), - ('template', r"\(\..*\.\)", lambda typ, val: (typ, val)), + ('STRING', r"'[^']*'", lambda typ, val: ('string', val[1:-1])), ('OTHER', r'[:;\|\(\),]', lambda typ, val: (val, val)), ('SKIP', r'[ ]', None) ] @@ -115,10 +114,11 @@ class Rule: """ A rewrite rule. Specifies a tree that can be rewritten into a result at a specific cost """ - def __init__(self, non_term, tree, cost, template): + def __init__(self, non_term, tree, cost, acceptance, template): self.non_term = non_term self.tree = tree self.cost = cost + self.acceptance = acceptance self.template = template self.nr = 0 @@ -154,11 +154,11 @@ non_terminals = property(lambda s: s.symType(Nonterm)) - def add_rule(self, non_term, tree, cost, template): - template = template[2:-2].strip() + def add_rule(self, non_term, tree, cost, acceptance, template): + template = template.strip() if not template: template = 'pass' - rule = Rule(non_term, tree, cost, template) + rule = Rule(non_term, tree, cost, acceptance, template) if len(tree.children) == 0 and tree.name not in self.terminals: self.non_term(tree.name).chain_rules.append(rule) self.non_term(rule.non_term) @@ -231,28 +231,35 @@ self.print() for rule in self.system.rules: if rule.num_nts > 0: - args = ', ' + ', '.join('nt{}'.format(x) for x in range(rule.num_nts)) + args = ', '.join('c{}'.format(x) for x in range(rule.num_nts)) + args = ', ' + args else: args = '' + # Create template function: self.print(' def P{}(self, tree{}):'.format(rule.nr, args)) template = rule.template - template = template.replace('$$', 'tree') - for i in range(rule.num_nts): - template = template.replace('${}'.format(i+1), 'nt{}'.format(i)) for t in template.split(';'): self.print(' {}'.format(t.strip())) + # Create acceptance function: + if rule.acceptance: + self.print(' def A{}(self, tree):'.format(rule.nr)) + for t in rule.acceptance.split(';'): + self.print(' {}'.format(t.strip())) self.emit_state() self.print(' def gen(self, tree):') self.print(' self.burm_label(tree)') self.print(' if not tree.state.has_goal("{}"):'.format(self.system.goal)) - self.print(' raise Exception("Tree {} not covered".format(tree))') + self.print(' raise Exception("Tree {} not covered".format(tree))') self.print(' return self.apply_rules(tree, "{}")'.format(self.system.goal)) def emit_record(self, rule, state_var): # TODO: check for rules fullfilled (by not using 999999) + acc = '' + if rule.acceptance: + acc = ' and self.A{}(tree)'.format(rule.nr) self.print(' nts = self.nts({})'.format(rule.nr)) self.print(' kids = self.kids(tree, {})'.format(rule.nr)) - self.print(' if all(x.state.has_goal(y) for x, y in zip(kids, nts)):') + self.print(' if all(x.state.has_goal(y) for x, y in zip(kids, nts)){}:'.format(acc)) self.print(' c = sum(x.state.get_cost(y) for x, y in zip(kids, nts)) + {}'.format(rule.cost)) self.print(' tree.state.set_cost("{}", c, {})'.format(rule.non_term, rule.nr)) for cr in self.system.symbols[rule.non_term].chain_rules:
--- a/test/sample4.brg Fri Mar 14 13:02:16 2014 +0100 +++ b/test/sample4.brg Fri Mar 14 15:14:29 2014 +0100 @@ -6,17 +6,17 @@ %% -stmt: ASGNI(disp, reg) 1 (. self.tr(1) .) -stmt: reg 0 (. self.tr(2).) -reg: ADDI(reg, rc) 1 (. self.tr(3) .) -reg: CVCI(INDIRC(disp)) 1 (. self.tr(4) .) -reg: IOI 0 (. self.tr(5).) -reg: disp 1 (. self.tr(6).) -disp: ADDI(reg, con) 1 (. self.tr(7).) -disp: ADDRLP 0 (. self.tr(8).) -rc: con 0 (. self.tr(9).) -rc: reg 0 (. self.tr(10).) -con: CNSTI 0 (. self.tr(11).) -con: IOI 0 (. self.tr(12).) +stmt: ASGNI(disp, reg) 1 'self.tr(1) ' +stmt: reg 0 ' self.tr(2)' +reg: ADDI(reg, rc) 1 'self.tr(3) ' +reg: CVCI(INDIRC(disp)) 1 'self.tr(4) ' +reg: IOI 0 'self.tr(5)' +reg: disp 1 'self.tr(6)' +disp: ADDI(reg, con) 1 'self.tr(7)' +disp: ADDRLP 0 ' self.tr(8)' +rc: con 0 ' self.tr(9)' +rc: reg 0 'self.tr(10)' +con: CNSTI 0 ' self.tr(11)' +con: IOI 0 ' self.tr(12)'