Mercurial > lcfOS

comparison python/codegen/interferencegraph.py @ 296:9417caea2eb3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Directorized some backend files
author Windel Bouwman
date Sun, 01 Dec 2013 13:36:58 +0100
parents python/interferencegraph.py@02385f62f250
children
comparison
equal deleted inserted replaced
295:917eab04b8b7 296:9417caea2eb3
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)