# HG changeset patch # User Windel Bouwman # Date 1391105004 -3600 # Node ID e9fe6988497c79c110993b8adbc680e87e3692fd # Parent 44f336460c2a83a6ea9ae6bbb68bc507d1f42c66 Used burg for generating expressions diff -r 44f336460c2a -r e9fe6988497c python/ppci/codegen/graph.py --- a/python/ppci/codegen/graph.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/ppci/codegen/graph.py Thu Jan 30 19:03:24 2014 +0100 @@ -7,9 +7,12 @@ def __init__(self): self.nodes = set() self.edges = set() + self.adj_map = {} def addNode(self, n): self.nodes.add(n) + if n not in self.adj_map: + self.adj_map[n] = set() def delNode(self, n): self.nodes.remove(n) @@ -18,6 +21,8 @@ """ Add an edge from n to m """ self.edges.add((n, m)) self.edges.add((m, n)) + self.adj_map[n].add(m) + self.adj_map[m].add(n) def hasEdge(self, n, m): return (n, m) in self.edges @@ -28,8 +33,7 @@ def adjecent(self, n): """ Return all nodes with edges to n """ - # TODO: this can be optimized for speed: - return set(m for m in self.nodes if self.hasEdge(n, m)) + return self.adj_map[n] & self.nodes def to_dot(self, f): """ Generate graphviz dot representation """ @@ -57,21 +61,37 @@ class DiGraph(Graph): - """ - Directed graph. - """ + """ Directed graph. """ + def __init__(self): + super().__init__() + self.suc_map = {} + self.pre_map = {} + def addEdge(self, n, m): - """ Add an edge from n to m """ + """ Add a directed edge from n to m """ + assert n in self.nodes + assert m in self.nodes self.edges.add((n, m)) + self.suc_map[n].add(m) + self.pre_map[m].add(n) + self.adj_map[n].add(m) + self.adj_map[m].add(n) + + def addNode(self, n): + super().addNode(n) + if n not in self.suc_map: + self.suc_map[n] = set() + if n not in self.pre_map: + self.pre_map[n] = set() def hasEdge(self, n, m): return (n, m) in self.edges def successors(self, n): - return set(m for m in self.nodes if self.hasEdge(n, m)) + return self.suc_map[n] & self.nodes def predecessors(self, n): - return set(m for m in self.nodes if self.hasEdge(m, n)) + return self.pre_map[n] & self.nodes class DiNode(Node): diff -r 44f336460c2a -r e9fe6988497c python/ppci/codegen/registerallocator.py --- a/python/ppci/codegen/registerallocator.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/ppci/codegen/registerallocator.py Thu Jan 30 19:03:24 2014 +0100 @@ -165,7 +165,7 @@ n.color = self.color[n] else: raise NotImplementedError('Spill required here!') - + def ApplyColors(self): # Remove coalesced moves: for mv in self.coalescedMoves: diff -r 44f336460c2a -r e9fe6988497c python/ppci/ir2tree.py --- a/python/ppci/ir2tree.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/ppci/ir2tree.py Thu Jan 30 19:03:24 2014 +0100 @@ -1,6 +1,8 @@ from tree import Tree from . import ir +""" Create a tree from ir code. """ + f_map = {} # Mapping from types to tree creation functions def register(tp): @@ -35,7 +37,9 @@ @register(ir.Call) def call_to_tree(e): - return Tree('CALL') + t = Tree('CALL') + t.value = e + return t def makeTree(ir_node): """ Transform an ir node into a tree usable for matching """ diff -r 44f336460c2a -r e9fe6988497c python/ppci/irmach.py --- a/python/ppci/irmach.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/ppci/irmach.py Thu Jan 30 19:03:24 2014 +0100 @@ -11,7 +11,7 @@ class Frame: - """ + """ Activation record abstraction. This class contains a flattened function. Instructions are selected and scheduled at this stage. Frames differ per machine. @@ -54,16 +54,12 @@ """ Substitutes source, dst and labels in the string """ - x = str(self.assem) - for i, s in enumerate(self.src): - p = '%s{}'.format(i) - x = x.replace(p, str(s)) - for i, d in enumerate(self.dst): - p = '%d{}'.format(i) - x = x.replace(p, str(d)) - for i, j in enumerate(self.jumps): - p = '%l{}'.format(i) - x = x.replace(p, str(j)) + if isinstance(self.assem, Instruction): + x = str(self.assem) + else: + cn = self.assem.__name__ + x = '{}, def={}, use={}, other={}' + x = x.format(cn, self.dst, self.src, self.others) return x diff -r 44f336460c2a -r e9fe6988497c python/pyburg.py --- a/python/pyburg.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/pyburg.py Thu Jan 30 19:03:24 2014 +0100 @@ -245,8 +245,8 @@ 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")') - self.print(' self.apply_rules(tree, "{}")'.format(self.system.goal)) + 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) diff -r 44f336460c2a -r e9fe6988497c python/target/arm.brg --- a/python/target/arm.brg Mon Jan 27 19:58:07 2014 +0100 +++ b/python/target/arm.brg Thu Jan 30 19:03:24 2014 +0100 @@ -1,4 +1,5 @@ +from target.basetarget import Label, Comment, Alignment, LabelRef, DebugInfo, Nop 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 @@ -6,20 +7,26 @@ %% -%terminal ADDI32 SUBI32 ORI32 SHLI32 +%terminal ADDI32 SUBI32 MULI32 +%terminal ORI32 SHLI32 %terminal CONSTI32 MEMI32 REGI32 CALL +%terminal MOVI32 %% + 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: 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: 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 .) +reg: CONSTI32 3 (. d = self.newTmp(); ln = LabelRef(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) .) +stmt: MOVI32(MEMI32(addr), reg) 3 (. self.emit(Str2, src=[$1, $2]) .) + +addr: reg 2 (. .) diff -r 44f336460c2a -r e9fe6988497c python/target/armframe.py --- a/python/target/armframe.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/target/armframe.py Thu Jan 30 19:03:24 2014 +0100 @@ -61,16 +61,21 @@ """ Returns prologue instruction sequence """ pre = [ Label(self.name), # Label indication function - Push({LR, R7}), - SubSp(SP, SP, Imm7(self.stacksize)), # Reserve stack space + Push({LR, R7}) + ] + if self.stacksize > 0: + pre.append(SubSp(SP, SP, Imm7(self.stacksize))) # Reserve stack space + pre += [ 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)), + post = [] + if self.stacksize > 0: + post.append(AddSp(SP, SP, Imm7(self.stacksize))) + post += [ Pop({PC, R7}), Alignment(4) # Align at 4 bytes ] diff -r 44f336460c2a -r e9fe6988497c python/target/arminstructionselector.py --- a/python/target/arminstructionselector.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/target/arminstructionselector.py Thu Jan 30 19:03:24 2014 +0100 @@ -15,116 +15,41 @@ 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): + """ Matcher that derives from a burg spec generated matcher """ + def __init__(self, selector): super().__init__() - - def newTmp(self): - pass - - def emit(self, *args, **kwargs): - pass + self.newTmp = selector.newTmp + self.emit = selector.emit + self.selector = selector class ArmInstructionSelector(InstructionSelector): """ Instruction selector for the arm architecture """ def __init__(self): super().__init__() - self.matcher = ArmMatcher() + self.matcher = ArmMatcher(self) def munchExpr(self, e): - #t = makeTree(e) - #print(t) - #return self.matcher.gen(t) + # Use BURG system here: + t = makeTree(e) + 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) - d = self.newTmp() - c = Imm3(e.b.value) - self.emit(Add2, others=[c], dst=[d], src=[a]) - return d - elif isinstance(e, ir.Binop) and e.operation == '+': - a = self.munchExpr(e.a) - b = self.munchExpr(e.b) - d = self.newTmp() - self.emit(Add, dst=[d], src=[a, b]) - return d - elif isinstance(e, ir.Binop) and e.operation == '-' and \ - isinstance(e.b, ir.Const) and e.b.value < 8: - a = self.munchExpr(e.a) - d = self.newTmp() - c = Imm3(e.b.value) - self.emit(Sub2, others=[c], dst=[d], src=[a]) - return d - elif isinstance(e, ir.Binop) and e.operation == '-': - a = self.munchExpr(e.a) - b = self.munchExpr(e.b) - d = self.newTmp() - self.emit(Sub, dst=[d], src=[a, b]) - return d - elif isinstance(e, ir.Binop) and e.operation == '|': - a = self.munchExpr(e.a) - b = self.munchExpr(e.b) - d = self.newTmp() - self.move(d, a) - self.emit(Orr, dst=[], src=[d, b]) - return d - elif isinstance(e, ir.Binop) and e.operation == '<<': - a = self.munchExpr(e.a) - b = self.munchExpr(e.b) - d = self.newTmp() - self.move(d, a) - self.emit(Lsl, dst=[], src=[d, b]) # TODO: is d a source variable? - return d - elif isinstance(e, ir.Binop) and e.operation == '*': - a = self.munchExpr(e.a) - b = self.munchExpr(e.b) - d = self.newTmp() - self.move(d, a) - # this mul instruction has operands swapped: - self.emit(Mul, dst=[d], src=[b, d]) - return d - elif isinstance(e, ir.Const) and e.value < 256: - d = self.newTmp() - self.emit(Mov3, others=[Imm8(e.value)], dst=[d]) - return d - elif isinstance(e, ir.Const) and e.value < (2**31): - d = self.newTmp() - ln = LabelRef(self.frame.addConstant(e.value)) - self.emit(Ldr3, others=[ln], dst=[d]) - return d - elif isinstance(e, ir.Mem) and isinstance(e.e, ir.Binop) and \ - e.e.operation == '+' and isinstance(e.e.b, ir.Const): - base = self.munchExpr(e.e.a) - d = self.newTmp() - c = e.e.b.value - self.emit(Ldr2, others=[c], src=[base], dst=[d]) - return d - elif isinstance(e, ir.Mem): - # Load from memory - base = self.munchExpr(e.e) - d = self.newTmp() - self.emit(Ldr2, others=[0], src=[base], dst=[d]) - return d - elif isinstance(e, ir.Temp): - return e - elif isinstance(e, ir.Call): - # Move arguments into proper locations: - reguses = [] - for i, a in enumerate(e.arguments): - loc = self.frame.argLoc(i) - m = ir.Move(loc, a) - self.munchStm(m) - if isinstance(loc, ir.Temp): - reguses.append(loc) - self.emit(Bl(LabelRef(e.f)), src=reguses, dst=[self.frame.rv]) - d = self.newTmp() - self.move(d, self.frame.rv) - return d - else: - raise NotImplementedError('Expr --> {}'.format(e)) + def munchCall(self, e): + """ Generate code for call sequence """ + # Move arguments into proper locations: + reguses = [] + for i, a in enumerate(e.arguments): + loc = self.frame.argLoc(i) + m = ir.Move(loc, a) + self.munchStm(m) + if isinstance(loc, ir.Temp): + reguses.append(loc) + self.emit(Bl(LabelRef(e.f)), src=reguses, dst=[self.frame.rv]) + d = self.newTmp() + self.move(d, self.frame.rv) + return d def munchStm(self, s): if isinstance(s, ir.Terminator): diff -r 44f336460c2a -r e9fe6988497c python/tree.py --- a/python/tree.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/tree.py Thu Jan 30 19:03:24 2014 +0100 @@ -53,5 +53,5 @@ def apply_rules(self, tree, goal): 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](tree, *results) + for kid_tree, kid_goal in zip(self.kids(tree, rule), self.nts(rule))] + return self.pat_f[rule](tree, *results) diff -r 44f336460c2a -r e9fe6988497c python/yacc.py --- a/python/yacc.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/yacc.py Thu Jan 30 19:03:24 2014 +0100 @@ -41,6 +41,7 @@ import datetime import types import io +import logging from pyyacc import Grammar, print_grammar @@ -201,12 +202,13 @@ class XaccGenerator: """ Generator that writes generated parser to file """ def __init__(self): - pass + self.logger = logging.getLogger('yacc') def generate(self, grammar, headers, output_file): self.output_file = output_file self.grammar = grammar self.headers = headers + self.logger.info('Generating parser for grammar {}'.format(grammar)) self.action_table, self.goto_table = grammar.doGenerate() self.generate_python_script() diff -r 44f336460c2a -r e9fe6988497c python/zcc.py --- a/python/zcc.py Mon Jan 27 19:58:07 2014 +0100 +++ b/python/zcc.py Thu Jan 30 19:03:24 2014 +0100 @@ -11,6 +11,7 @@ import outstream from utils import HexFile import target +from target.target_list import target_list from ppci import irutils import io from ppci.transform import CleanPass, RemoveAddZero @@ -112,7 +113,7 @@ return s -targets = {t.name: t for t in target.target_list.target_list} +targets = {t.name: t for t in target_list} targetnames = list(targets.keys()) # Parse arguments: diff -r 44f336460c2a -r e9fe6988497c test/grind.py --- a/test/grind.py Mon Jan 27 19:58:07 2014 +0100 +++ b/test/grind.py Thu Jan 30 19:03:24 2014 +0100 @@ -6,9 +6,16 @@ import sys import os +p = os.path.join(os.path.dirname(os.path.abspath(__file__)), '..', 'python') +sys.path.insert(0, p) + if __name__ == '__main__': suite = unittest.TestLoader().discover('.') def runtests(): unittest.TextTestRunner().run(suite) #s = cProfile.run('runtests()',sort='cumtime') - s = cProfile.run('runtests()',sort='tottime') + p = cProfile.Profile() + s = p.run('runtests()') + stats = pstats.Stats(p) + stats.sort_stats('tottime') + stats.print_stats(.1) diff -r 44f336460c2a -r e9fe6988497c test/testgraph.py --- a/test/testgraph.py Mon Jan 27 19:58:07 2014 +0100 +++ b/test/testgraph.py Thu Jan 30 19:03:24 2014 +0100 @@ -1,7 +1,7 @@ #!/usr/bin/python import unittest -from ppci.codegen.graph import Graph, Node +from ppci.codegen.graph import Graph, Node, DiGraph, DiNode from ppci.codegen.interferencegraph import InterferenceGraph from ppci.codegen.flowgraph import FlowGraph from ppci import ir @@ -39,7 +39,20 @@ class DigraphTestCase(unittest.TestCase): - pass + def testSuccessor(self): + g = DiGraph() + a = DiNode(g) + b = DiNode(g) + c = DiNode(g) + g.addNode(a) + g.addNode(b) + g.addNode(c) + g.addEdge(a, b) + g.addEdge(b, c) + self.assertEqual({b}, a.Succ) + self.assertEqual({b}, c.Pred) + g.delNode(c) + self.assertEqual(set(), b.Succ) class InterferenceGraphTestCase(unittest.TestCase):