Mercurial > lcfOS
changeset 322:44f336460c2a
Half of use of burg spec for arm
| author | Windel Bouwman |
|---|---|
| date | Mon, 27 Jan 2014 19:58:07 +0100 |
| parents | 8c569fbe60e4 |
| children | e9fe6988497c |
| files | doc/design.rst doc/index.rst doc/os.rst python/burg.x python/ppci/c3/lexer.py python/ppci/ir2tree.py python/pyburg.py python/target/__init__.py python/target/arm.brg python/target/armframe.py python/target/arminstructionselector.py python/target/armtarget.py python/target/armv7.lidl python/target/target_list.py python/tree.py python/yacc.py python/zcc.py test/sample4.brg test/testarmasm.py test/testcg.py test/testmsp430asm.py test/testzcc.py |
| diffstat | 22 files changed, 341 insertions(+), 169 deletions(-) [+] |
line wrap: on
line diff
--- a/doc/design.rst Sun Jan 19 18:48:45 2014 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,103 +0,0 @@ -Design -====== - -OS --- - -Processes / threads -~~~~~~~~~~~~~~~~~~~ - -Processes are completely seperated and fully pre-emptive. -This means a process can be unscheduled at any moment. - -Threads are co-operative. This means they yield control -voluntary. This means that mutexes and locks are not required. -This is done with the built-in language feature called tasks. - -If some heavy duty task must be performed, either way spawn -a new process, or yield frequently from this hard labour. - -tasks -~~~~~ - -Consider the following: - -.. code:: - - function int insanemath(int a) - { - while (a > 0) - { - a = a -1; - resume agent1; - } - return a - 1; - } - - task agent1() - { - start agent2; - } - - task agent2() - { - insanemath(55); - insanemath(44); - } - - task main() - { - start agent1; - join agent1; - } - - -Say to tasks are running in concurrent / parallel. - - - -Stack layout for tasks. -|| -|| -\/ -+---------+ -| return address -| locals -| -+------ -| return address -| locals -| -+--- - -Assembly code for the functions above: - -.. code:: - - .code - insanemath: - L1: - load r0, sp - 4 - cmp r0, 0 - jl L2 - dec r0 - store r0, sp - 4 - jmp L1 - L2: - ret - - agent1: - hlt? - - agent2: - hlt? - - main: - jmp agent1 - - .data - agent1_task: - dd 0 - agent2_task: - dd 0 -
--- a/doc/index.rst Sun Jan 19 18:48:45 2014 +0100 +++ b/doc/index.rst Mon Jan 27 19:58:07 2014 +0100 @@ -7,10 +7,12 @@ ================================= .. toctree:: - :maxdepth: 2 + :maxdepth: 1 readme_link - design compiler utils + os +.. include:: ../readme.rst +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/os.rst Mon Jan 27 19:58:07 2014 +0100 @@ -0,0 +1,103 @@ +OS +== + +Design +------ + +Processes / threads +~~~~~~~~~~~~~~~~~~~ + +Processes are completely seperated and fully pre-emptive. +This means a process can be unscheduled at any moment. + +Threads are co-operative. This means they yield control +voluntary. This means that mutexes and locks are not required. +This is done with the built-in language feature called tasks. + +If some heavy duty task must be performed, either way spawn +a new process, or yield frequently from this hard labour. + +tasks +~~~~~ + +Consider the following: + +.. code:: + + function int insanemath(int a) + { + while (a > 0) + { + a = a -1; + resume agent1; + } + return a - 1; + } + + task agent1() + { + start agent2; + } + + task agent2() + { + insanemath(55); + insanemath(44); + } + + task main() + { + start agent1; + join agent1; + } + + +Say to tasks are running in concurrent / parallel. + + + +Stack layout for tasks. +|| +|| +\/ ++---------+ +| return address +| locals +| ++------ +| return address +| locals +| ++--- + +Assembly code for the functions above: + +.. code:: + + .code + insanemath: + L1: + load r0, sp - 4 + cmp r0, 0 + jl L2 + dec r0 + store r0, sp - 4 + jmp L1 + L2: + ret + + agent1: + hlt? + + agent2: + hlt? + + main: + jmp agent1 + + .data + agent1_task: + dd 0 + agent2_task: + dd 0 +
--- a/python/burg.x Sun Jan 19 18:48:45 2014 +0100 +++ b/python/burg.x Mon Jan 27 19:58:07 2014 +0100 @@ -1,9 +1,9 @@ -%tokens ':' ';' '(' ')' ',' template id number '%%' '%terminal' +%tokens ':' ';' '(' ')' ',' template id number '%%' '%terminal' header %% -burgdef: directives '%%' rules; +burgdef: header '%%' directives '%%' rules { self.system.header_lines = $1.val }; directives: | directives directive;
--- a/python/ppci/c3/lexer.py Sun Jan 19 18:48:45 2014 +0100 +++ b/python/ppci/c3/lexer.py Mon Jan 27 19:58:07 2014 +0100 @@ -1,5 +1,6 @@ import re from ppci import CompilerError, SourceLocation, Token +import baselex """ Lexical analyzer part. Splits the input character stream into tokens.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/ppci/ir2tree.py Mon Jan 27 19:58:07 2014 +0100 @@ -0,0 +1,42 @@ +from tree import Tree +from . import ir + +f_map = {} # Mapping from types to tree creation functions + +def register(tp): + """ Register a function for type tp """ + def reg_f(f): + f_map[tp] = f + return f + return reg_f + +@register(ir.Binop) +def binop_to_tree(e): + names = {'+':'ADDI32', '-':'SUBI32', '|':'ORI32', '<<':'SHLI32', + '*':'MULI32'} + op = names[e.operation] + return Tree(op, makeTree(e.a), makeTree(e.b)) + +@register(ir.Temp) +def temp_to_tree(e): + t = Tree('REGI32') + t.value = e + return t + +@register(ir.Const) +def const_to_tree(e): + t = Tree('CONSTI32') + t.value = e.value + return t + +@register(ir.Mem) +def mem_to_tree(e): + return Tree('MEMI32', makeTree(e.e)) + +@register(ir.Call) +def call_to_tree(e): + return Tree('CALL') + +def makeTree(ir_node): + """ Transform an ir node into a tree usable for matching """ + return f_map[type(ir_node)](ir_node)
--- a/python/pyburg.py Sun Jan 19 18:48:45 2014 +0100 +++ b/python/pyburg.py Mon Jan 27 19:58:07 2014 +0100 @@ -1,39 +1,52 @@ #!/usr/bin/python """ -Bottom up rewrite generator. +Bottom up rewrite generator +--------------------------- This script takes as input a description of patterns and outputs a matcher class that can match trees given the patterns. - Patterns are specified as follows: +Patterns are specified as follows:: + reg -> ADDI32(reg, reg) 2 (. add NT0 NT1 .) reg -> MULI32(reg, reg) 3 (. .) - or a multiply add: - reg -> ADDI32(MULI32(reg, reg), reg) 4 (. muladd $1, $2, $3 .) - The general specification pattern is: - [result] -> [tree] [cost] [template code] + +or a multiply add:: + + reg -> ADDI32(MULI32(reg, reg), reg) 4 (. muladd $1, $2, $3 .) + +The general specification pattern is:: + + [result] -> [tree] [cost] [template code] Trees ----- A tree is described using parenthesis notation. For example a node X with three child nodes is described as: + X(a, b, b) + Trees can be nested: + X(Y(a, a), a) + The 'a' in the example above indicates an open connection to a next tree pattern. In the example above 'reg' is a non-terminal. ADDI32 is a terminal. non-terminals cannot have child nodes. A special case occurs in this case: -reg -> rc + + reg -> rc + where 'rc' is a non-terminal. This is an example of a chain rule. Chain rules can be used to allow several variants of non-terminals. The generated matcher uses dynamic programming to find the best match of the tree. This strategy consists of two steps: + - label: During this phase the given tree is traversed in a bottom up way. each node is labelled with a possible matching rule and the corresponding cost. - select: In this step, the tree is traversed again, selecting at each point @@ -43,6 +56,8 @@ import sys import os +import io +import types import argparse from ppci import Token from pyyacc import ParserException, EOF @@ -68,16 +83,24 @@ ] lines = txt.split('\n') + header_lines = [] def tokenize(): + section = 0 for line in lines: line = line.strip() if not line: continue # Skip empty lines elif line == '%%': + section += 1 + if section == 1: + yield Token('header', header_lines) yield Token('%%', '%%') else: - yield from baselex.tokenize(tok_spec, line) + if section == 0: + header_lines.append(line) + else: + yield from baselex.tokenize(tok_spec, line) yield Token(EOF, EOF) self.tokens = tokenize() self.token = self.tokens.__next__() @@ -188,6 +211,8 @@ self.print('#!/usr/bin/python') self.print('from tree import Tree, BaseMatcher, State') + for header in self.system.header_lines: + self.print(header) self.print() self.print('class Matcher(BaseMatcher):') self.print(' def __init__(self):') @@ -209,8 +234,13 @@ args = ', ' + ', '.join('nt{}'.format(x) for x in range(rule.num_nts)) else: args = '' - self.print(' def P{}(self{}):'.format(rule.nr, args)) - self.print(' {}'.format(rule.template)) + 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())) self.emit_state() self.print(' def gen(self, tree):') self.print(' self.burm_label(tree)') @@ -220,18 +250,18 @@ def emit_record(self, rule, state_var): # TODO: check for rules fullfilled (by not using 999999) - self.print(' nts = self.nts({})'.format(rule.nr)) - self.print(' kids = self.kids(tree, {})'.format(rule.nr)) - 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)) + self.print(' nts = self.nts({})'.format(rule.nr)) + self.print(' kids = self.kids(tree, {})'.format(rule.nr)) + 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: - self.print(' # Chain rule: {}'.format(cr)) - self.print(' tree.state.set_cost("{}", c + {}, {})'.format(cr.non_term, cr.cost, cr.nr)) + self.print(' # Chain rule: {}'.format(cr)) + self.print(' tree.state.set_cost("{}", c + {}, {})'.format(cr.non_term, cr.cost, cr.nr)) def emit_state(self): """ Emit a function that assigns a new state to a node """ self.print(' def burm_state(self, tree):') - self.print(' tree.state = State()') + self.print(' tree.state = State()') for term in self.system.terminals: self.emitcase(term) self.print() @@ -240,7 +270,7 @@ rules = [rule for rule in self.system.rules if rule.tree.name == term] for rule in rules: condition = self.emittest(rule.tree, 'tree') - self.print(' if {}:'.format(condition)) + self.print(' if {}:'.format(condition)) self.emit_record(rule, 'state') def compute_kids(self, t, root_name): @@ -278,6 +308,16 @@ default=sys.stdout) return parser +def load_as_module(filename): + """ Load a parser spec file, generate LR tables and create module """ + ob = io.StringIO() + args = argparse.Namespace(source=open(filename), output=ob) + main(args) + + matcher_mod = types.ModuleType('generated_matcher') + exec(ob.getvalue(), matcher_mod.__dict__) + return matcher_mod + def main(args): src = args.source.read()
--- a/python/target/__init__.py Sun Jan 19 18:48:45 2014 +0100 +++ b/python/target/__init__.py Mon Jan 27 19:58:07 2014 +0100 @@ -3,21 +3,6 @@ from .basetarget import Nop, Instruction, Label, Target, Comment, Alignment from .basetarget import Imm32, DebugInfo -from .armtarget import ArmTarget -from .armframe import ArmFrame -from .arminstructionselector import ArmInstructionSelector - -from .msp430 import msp430target - -# Instance: -armtarget = ArmTarget() -armtarget.ins_sel = ArmInstructionSelector() -armtarget.FrameClass = ArmFrame - -#from .msp430target import msp430target - -target_list = [armtarget] - class SimpleTarget(Target): def __init__(self):
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/target/arm.brg Mon Jan 27 19:58:07 2014 +0100 @@ -0,0 +1,25 @@ + +from target.arminstructions import Orr, Lsl, Str2, Ldr2, Ldr3 +from target.arminstructions import B, Bl, Bgt, Blt, Beq, Bne +from target.arminstructions import Mov2, Mov3 +from target.arminstructions import Add, Sub, Cmp, Sub2, Add2, Mul + +%% + +%terminal ADDI32 SUBI32 ORI32 SHLI32 +%terminal CONSTI32 MEMI32 REGI32 CALL + +%% + +reg: ADDI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Add, dst=[d], src=[$1, $2]); return d .) +reg: SUBI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Sub, dst=[d], src=[$1, $2]); return d .) +reg: ORI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Orr, dst=[d], src=[$1, $2]); return d .) +reg: SHLI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Lsl, dst=[d], src=[$1, $2]); return d .) +reg: MULI32(reg, reg) 2 (. d = self.newTmp(); self.emit(Mul, dst=[d], src=[$1, $2]); return d .) + +reg: CONSTI32 3 (. d = self.newTmp(); self.emit(Sub, dst=[d], src=[$$.value]); return d .) +reg: MEMI32(reg) 4 (. d = self.newTmp(); self.emit(Ldr2, dst=[d], src=[$1]); return d .) +reg: REGI32 1 (. pass .) +reg: CALL 1 (. pass .) + +
--- a/python/target/armframe.py Sun Jan 19 18:48:45 2014 +0100 +++ b/python/target/armframe.py Mon Jan 27 19:58:07 2014 +0100 @@ -57,22 +57,36 @@ self.constants.append((lab_name, value)) return lab_name + def prologue(self): + """ Returns prologue instruction sequence """ + pre = [ + Label(self.name), # Label indication function + Push({LR, R7}), + SubSp(SP, SP, Imm7(self.stacksize)), # Reserve stack space + Mov2(R7, SP) # Setup frame pointer + ] + return pre + + def epilogue(self): + """ Return epilogue sequence for a frame. Adjust frame pointer and add constant pool """ + post = [ + AddSp(SP, SP, Imm7(self.stacksize)), + Pop({PC, R7}), + Alignment(4) # Align at 4 bytes + ] + # Add constant literals: + for ln, v in self.constants: + post.extend([Label(ln), Dcd(v)]) + return post + def EntryExitGlue3(self): """ Add code for the prologue and the epilogue. Add a label, the return instruction and the stack pointer adjustment for the frame. """ - self.instructions.insert(0, makeIns(Label(self.name))) - self.instructions.insert(1, makeIns(Push({LR, R7}))) - # Reserve stack space for locals: - self.instructions.insert(2, makeIns(SubSp(SP, SP, Imm7(self.stacksize)))) - # Setup frame pointer: - self.instructions.insert(3, makeIns(Mov2(R7, SP))) - # Stack grows downwards - self.instructions.append(makeIns(AddSp(SP, SP, Imm7(self.stacksize)))) - self.instructions.append(makeIns(Pop({PC, R7}))) - # Add constant literals: - self.instructions.append(makeIns(Alignment(4))) # Align at 4 bytes - for ln, v in self.constants: - self.instructions.append(makeIns(Label(ln))) - self.instructions.append(makeIns(Dcd(v))) + for index, ins in enumerate(self.prologue()): + self.instructions.insert(index, makeIns(ins)) + + # Postfix code: + for ins in self.epilogue(): + self.instructions.append(makeIns(ins))
--- a/python/target/arminstructionselector.py Sun Jan 19 18:48:45 2014 +0100 +++ b/python/target/arminstructionselector.py Mon Jan 27 19:58:07 2014 +0100 @@ -1,5 +1,8 @@ +import os from ppci import ir from ppci.irmach import AbstractInstruction as makeIns +from ppci.ir2tree import makeTree +import pyburg from .basetarget import Label, Comment, Alignment, LabelRef, DebugInfo, Nop from .instructionselector import InstructionSelector from .arminstructions import Orr, Lsl, Str2, Ldr2, Ldr3 @@ -8,10 +11,33 @@ from .arminstructions import Add, Sub, Cmp, Sub2, Add2, Mul from .basetarget import Imm8, Imm7, Imm3 +# Import BURG spec for arm: +spec_file = os.path.join(os.path.dirname(os.path.abspath(__file__)), 'arm.brg') +arm_matcher = pyburg.load_as_module(spec_file) + +class ArmMatcher(arm_matcher.Matcher): + def __init__(self): + super().__init__() + + def newTmp(self): + pass + + def emit(self, *args, **kwargs): + pass + class ArmInstructionSelector(InstructionSelector): """ Instruction selector for the arm architecture """ + def __init__(self): + super().__init__() + self.matcher = ArmMatcher() + def munchExpr(self, e): + #t = makeTree(e) + #print(t) + #return self.matcher.gen(t) + + # TODO: below is obsolete: if isinstance(e, ir.Binop) and e.operation == '+' and \ isinstance(e.b, ir.Const) and e.b.value < 8: a = self.munchExpr(e.a)
--- a/python/target/armtarget.py Sun Jan 19 18:48:45 2014 +0100 +++ b/python/target/armtarget.py Mon Jan 27 19:58:07 2014 +0100 @@ -5,6 +5,8 @@ from .arminstructions import Dcd, B from .arminstructions import R0, R1, R2, R3, R4, R5, R6, R7, LR, PC, SP +from .armframe import ArmFrame +from .arminstructionselector import ArmInstructionSelector """ ARM target description. """ @@ -21,6 +23,8 @@ # TODO: fix this nicer? #setattr(self, i.__name__, i) self.check() + self.ins_sel = ArmInstructionSelector() + self.FrameClass = ArmFrame def startCode(self, outs): """ Emit some startup code in the output stream """
--- a/python/target/armv7.lidl Sun Jan 19 18:48:45 2014 +0100 +++ b/python/target/armv7.lidl Mon Jan 27 19:58:07 2014 +0100 @@ -1,16 +1,36 @@ +# This file specifies the encoding of the arm instruction set. -instruction yield { - encoding: 0xbf10 +fields { + word16 16 { + opcode 15:12 + top2 15:14 + top6 15:10 + data_opcode 9..6 + opB 11:9 + Rm 8:6 + Rn 5:3 + Rt 2:0 + } } -base rrr_base { - encoding: '' +patterns { + add = 0 + sub, mul = 1..2 + [r1, r2, r3, r4, r5] is todo = 1..5 + [STR, STRH, STRB, LDRSB, LDR, LDRH, LDRB, LDRSH] is opcode = 0b0101 & opB = {0 to 7} + + EQ, NE, CS, CC, MI, PL, VS, VC, HI, LS, GE, LT, GT, LE, AL = 0..14 + [AND, EOR, LSL, LSR, ASR, ADC, SBC, ROR, TST, RSB, CMP, CMN, ORR, MUL, BIC, MVN] is 0..15 + + memop is STR | STRH | STRB | LDRSB | LDR | LDR | LDRH | LDRB | LDRSH } -instruction add : rrr_base { - semantics: { - Rd = Rm + Rn; - } + +constructors +{ + alu rs1, reg_or_imm, rd + memop Rt, [Rn, Rm] is memop & Rt & Rn & Rm } +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/target/target_list.py Mon Jan 27 19:58:07 2014 +0100 @@ -0,0 +1,8 @@ + +from .armtarget import ArmTarget +from .msp430 import msp430target + +# Instance: +armtarget = ArmTarget() + +target_list = [armtarget]
--- a/python/tree.py Sun Jan 19 18:48:45 2014 +0100 +++ b/python/tree.py Mon Jan 27 19:58:07 2014 +0100 @@ -3,6 +3,7 @@ """ Tree node with a name and possibly some child nodes """ def __init__(self, name, *args): self.name = name + self.value = None self.children = args def __repr__(self): @@ -53,4 +54,4 @@ rule = tree.state.get_rule(goal) results = [self.apply_rules(kid_tree, kid_goal) for kid_tree, kid_goal in zip(self.kids(tree, rule), self.nts(rule))] - self.pat_f[rule](*results) + self.pat_f[rule](tree, *results)
--- a/python/yacc.py Sun Jan 19 18:48:45 2014 +0100 +++ b/python/yacc.py Mon Jan 27 19:58:07 2014 +0100 @@ -261,6 +261,7 @@ for n in range(M): semantics = semantics.replace('${}'.format(n + 1), 'arg{}'.format(n + 1)) self.print(' {}'.format(semantics)) + self.print('') def make_argument_parser(): @@ -270,6 +271,7 @@ help='the parser specification') parser.add_argument('-o', '--output', type=argparse.FileType('w'), \ default=sys.stdout) + return parser def load_as_module(filename):
--- a/python/zcc.py Sun Jan 19 18:48:45 2014 +0100 +++ b/python/zcc.py Mon Jan 27 19:58:07 2014 +0100 @@ -112,8 +112,7 @@ return s -target_list = [target.armtarget] -targets = {t.name: t for t in target_list} +targets = {t.name: t for t in target.target_list.target_list} targetnames = list(targets.keys()) # Parse arguments:
--- a/test/sample4.brg Sun Jan 19 18:48:45 2014 +0100 +++ b/test/sample4.brg Mon Jan 27 19:58:07 2014 +0100 @@ -1,3 +1,5 @@ + +%% %terminal ADDI ADDRLP ASGNI %terminal CNSTI CVCI IOI INDIRC
--- a/test/testarmasm.py Sun Jan 19 18:48:45 2014 +0100 +++ b/test/testarmasm.py Mon Jan 27 19:58:07 2014 +0100 @@ -2,7 +2,7 @@ import outstream from asm import Assembler from testasm import AsmTestCaseBase -from target import armtarget +from target.target_list import armtarget class AssemblerARMTestCase(AsmTestCaseBase):
--- a/test/testcg.py Sun Jan 19 18:48:45 2014 +0100 +++ b/test/testcg.py Mon Jan 27 19:58:07 2014 +0100 @@ -2,7 +2,7 @@ import ppci from ppci.codegen import CodeGenerator from ppci import ir -from target import armtarget +from target.target_list import armtarget import outstream
--- a/test/testmsp430asm.py Sun Jan 19 18:48:45 2014 +0100 +++ b/test/testmsp430asm.py Mon Jan 27 19:58:07 2014 +0100 @@ -4,7 +4,8 @@ from asmnodes import AInstruction, ABinop, AUnop, ASymbol, ALabel, ANumber from asm import tokenize, Assembler import outstream -from target import Label, msp430target +from target import Label +from target.target_list import msp430target from testasm import AsmTestCaseBase
--- a/test/testzcc.py Sun Jan 19 18:48:45 2014 +0100 +++ b/test/testzcc.py Mon Jan 27 19:58:07 2014 +0100 @@ -77,7 +77,7 @@ f = io.StringIO(src) diag = ppci.DiagnosticsManager() outs = outstream.TextOutputStream() - tg = target.armtarget + tg = target.target_list.armtarget self.assertTrue(zcc.zcc([f], [], tg, outs, diag)) code = outs.getSection('code') self.assertEqual(0x08000000, code.address)