Mercurial > lcfOS

comparison python/interferencegraph.py @ 279:2ccd57b1d78c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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