Mercurial > lcfOS
comparison python/interferencegraph.py @ 279:2ccd57b1d78c
Fix register allocator to do burn2 OK
author | Windel Bouwman |
---|---|
date | Sat, 12 Oct 2013 09:56:23 +0200 |
parents | 9fca39eebe50 |
children | 02385f62f250 |
comparison
equal
deleted
inserted
replaced
278:9fca39eebe50 | 279:2ccd57b1d78c |
---|---|
4 class InterferenceGraphNode(graph.Node): | 4 class InterferenceGraphNode(graph.Node): |
5 def __init__(self, g, varname): | 5 def __init__(self, g, varname): |
6 super().__init__(g) | 6 super().__init__(g) |
7 self.temps = [varname] | 7 self.temps = [varname] |
8 self.moves = set() | 8 self.moves = set() |
9 self.color = None | |
9 | 10 |
10 def __repr__(self): | 11 def __repr__(self): |
11 return 'IGN<{}>'.format(self.temps) | 12 return '{}({})'.format(self.temps, self.color) |
12 | 13 |
13 | 14 |
14 class InterferenceGraph(graph.Graph): | 15 class InterferenceGraph(graph.Graph): |
15 """ | 16 """ |
16 Interference graph. | 17 Interference graph. |
50 n1 = self.getNode(tmp) | 51 n1 = self.getNode(tmp) |
51 for tmp2 in (n.live_out - {tmp}): | 52 for tmp2 in (n.live_out - {tmp}): |
52 n2 = self.getNode(tmp2) | 53 n2 = self.getNode(tmp2) |
53 self.addEdge(n1, n2) | 54 self.addEdge(n1, n2) |
54 | 55 |
56 def to_dot(self, f): | |
57 """ Generate graphviz dot representation """ | |
58 for node in self.nodes: | |
59 print('{} [label="{}" shape=box3d];'.format(id(node), node), file=f) | |
60 for n, m in self.edges: | |
61 print('{} -> {};'.format(id(n), id(m)), file=f) | |
62 | |
63 def to_txt(self): | |
64 for node in self.nodes: | |
65 print('{} interferes: {}'.format(node, node.Adjecent)) | |
66 | |
55 def getNode(self, tmp): | 67 def getNode(self, tmp): |
56 # Linear search | 68 # Linear search |
57 # TODO: can be improved for speed! | 69 # TODO: can be improved for speed! |
58 for n in self.nodes: | 70 for n in self.nodes: |
59 if tmp in n.temps: | 71 if tmp in n.temps: |
60 return n | 72 return n |
73 print('new one!') | |
61 n = InterferenceGraphNode(self, tmp) | 74 n = InterferenceGraphNode(self, tmp) |
62 self.addNode(n) | 75 self.addNode(n) |
63 return n | 76 return n |
64 | 77 |
65 def Combine(self, n, m): | 78 def Combine(self, n, m): |
66 """ Combine n and m into n """ | 79 """ Combine n and m into n """ |
67 n.temps.extend(m.temps) | 80 n.temps.extend(m.temps) |
68 n.moves.update(m.moves) | 81 n.moves.update(m.moves) |
69 for t in m.Adjecent: | 82 # Reroute all edges: |
70 self.addEdge(n, t) | 83 e1 = [e for e in self.edges if e[0] is m] |
84 e2 = [e for e in self.edges if e[1] is m] | |
85 for e in e1: | |
86 self.edges.remove(e) | |
87 self.addEdge(n, e[1]) | |
88 for e in e2: | |
89 self.edges.remove(e) | |
90 self.addEdge(n, e[0]) | |
91 # Remove node m: | |
71 self.delNode(m) | 92 self.delNode(m) |
72 | 93 |