Mercurial > lcfOS

comparison python/ppci/codegen/interferencegraph.py @ 301:6753763d3bec

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge codegen into ppci package
author Windel Bouwman
date Thu, 05 Dec 2013 17:02:38 +0100
parents python/codegen/interferencegraph.py@9417caea2eb3
children 04cf4d26a3bc
comparison
equal deleted inserted replaced
300:158068af716c 301:6753763d3bec
1 from .graph import Graph, Node
2
3
4 class InterferenceGraphNode(Node):
5 def __init__(self, g, varname):
6 super().__init__(g)
7 self.temps = [varname]
8 self.moves = set()
9 self.color = None
10
11 def __repr__(self):
12 return '{}({})'.format(self.temps, self.color)
13
14
15 class InterferenceGraph(Graph):
16 """
17 Interference graph.
18 """
19 def __init__(self, flowgraph):
20 """ Create a new interference graph from a flowgraph """
21 super().__init__()
22 # Calculate liveness in CFG:
23 ###
24 # Liveness:
25 # in[n] = use[n] UNION (out[n] - def[n])
26 # out[n] = for s in n.succ in union in[s]
27 ###
28 for n in flowgraph.nodes:
29 n.live_in = set()
30 n.live_out = set()
31
32 # Dataflow fixed point iteration:
33 change = True
34 while change:
35 change = False
36 for n in flowgraph.nodes:
37 _in = n.live_in
38 _out = n.live_out
39 n.live_in = n.uses | (n.live_out - n.defs)
40 if n.Succ:
41 n.live_out = set.union(*(s.live_in for s in n.Succ))
42 else:
43 n.live_out = set()
44 change = change or (_in != n.live_in) or (_out != n.live_out)
45
46 # Construct interference graph:
47 for n in flowgraph.nodes:
48 for tmp in n.live_out:
49 n1 = self.getNode(tmp)
50 for tmp2 in (n.live_out - {tmp}):
51 n2 = self.getNode(tmp2)
52 self.addEdge(n1, n2)
53
54 def to_dot(self, f):
55 """ Generate graphviz dot representation """
56 for n in self.nodes:
57 print('{} [label="{}" shape=box3d];'.format(id(n), n), file=f)
58 for n, m in self.edges:
59 print('{} -> {};'.format(id(n), id(m)), file=f)
60
61 def to_txt(self):
62 for node in self.nodes:
63 print('{} interferes: {}'.format(node, node.Adjecent))
64
65 def getNode(self, tmp):
66 # Linear search
67 # TODO: can be improved for speed!
68 for n in self.nodes:
69 if tmp in n.temps:
70 return n
71 n = InterferenceGraphNode(self, tmp)
72 self.addNode(n)
73 return n
74
75 def Combine(self, n, m):
76 """ Combine n and m into n """
77 n.temps.extend(m.temps)
78 n.moves.update(m.moves)
79 # Reroute all edges:
80 e1 = [e for e in self.edges if e[0] is m]
81 e2 = [e for e in self.edges if e[1] is m]
82 for e in e1:
83 self.edges.remove(e)
84 self.addEdge(n, e[1])
85 for e in e2:
86 self.edges.remove(e)
87 self.addEdge(n, e[0])
88 # Remove node m:
89 self.delNode(m)