Mercurial > lcfOS
changeset 323:e9fe6988497c
Used burg for generating expressions
| author | Windel Bouwman |
|---|---|
| date | Thu, 30 Jan 2014 19:03:24 +0100 |
| parents | 44f336460c2a |
| children | ed6d0adaa626 |
| files | python/ppci/codegen/graph.py python/ppci/codegen/registerallocator.py python/ppci/ir2tree.py python/ppci/irmach.py python/pyburg.py python/target/arm.brg python/target/armframe.py python/target/arminstructionselector.py python/tree.py python/yacc.py python/zcc.py test/grind.py test/testgraph.py |
| diffstat | 13 files changed, 121 insertions(+), 141 deletions(-) [+] |
line wrap: on
line diff
--- 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):
--- 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:
--- 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 """
--- 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
--- 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)
--- 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 (. .)
--- 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 ]
--- 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):
--- 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)
--- 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()
--- 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:
--- 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)
--- 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):