# HG changeset patch # User Windel Bouwman # Date 1394806469 -3600 # Node ID 818be710e13dd47b810d96a6a43d9eb2ae2734c3 # Parent 52492b304adfb942a7b53f25ff1bd81b5d0e9f58 Added acceptance function to burg diff -r 52492b304adf -r 818be710e13d doc/compiler.rst --- 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. + + diff -r 52492b304adf -r 818be710e13d kernel/kernel.c3 --- 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(); diff -r 52492b304adf -r 818be710e13d python/baselex.py --- 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:])) diff -r 52492b304adf -r 818be710e13d python/burg.x --- 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 }; diff -r 52492b304adf -r 818be710e13d python/ppci/target/arm/__init__.py --- 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: diff -r 52492b304adf -r 818be710e13d python/ppci/target/arm/arm.brg --- 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)' + diff -r 52492b304adf -r 818be710e13d python/ppci/target/thumb/arm.brg --- 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 '' diff -r 52492b304adf -r 818be710e13d python/pyburg.py --- 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: diff -r 52492b304adf -r 818be710e13d test/sample4.brg --- 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)'