annotate python/interferencegraph.py @ 277:046017431c6a

Started register allocator
author Windel Bouwman
date Thu, 26 Sep 2013 21:14:25 +0200
parents
children 9fca39eebe50
rev   line source
277
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
1 import graph
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
2
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
3
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
4 class InterferenceGraphNode(graph.Node):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
5 def __init__(self, g, varname):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
6 super().__init__(g)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
7 self.varname = varname
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
8
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
9 def __repr__(self):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
10 return '{}'.format(self.varname)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
11
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
12
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
13 class InterferenceGraph(graph.Graph):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
14 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
15 Interference graph.
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
16 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
17 def __init__(self, flowgraph):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
18 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
19 Create a new interference graph from a flowgraph
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
20 """
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
21 super().__init__(False)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
22 # Mapping from node to live set
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
23 self.liveMap = {}
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
24 self.tempMap = {}
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
25 # Calculate liveness in CFG:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
26 ###
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
27 # Liveness:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
28 # in[n] = use[n] UNION (out[n] - def[n])
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
29 # out[n] = for s in n.succ in union in[s]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
30 ###
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
31 for n in flowgraph.nodes:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
32 n.live_in = set()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
33 n.live_out = set()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
34
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
35 # Dataflow fixed point iteration:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
36 change = True
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
37 while change:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
38 change = False
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
39 for n in flowgraph.nodes:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
40 _in = n.live_in
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
41 _out = n.live_out
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
42 n.live_in = n.uses | (n.live_out - n.defs)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
43 if n.Succ:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
44 n.live_out = set.union(*(s.live_in for s in n.Succ))
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
45 else:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
46 n.live_out = set()
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
47 change = change or (_in != n.live_in) or (_out != n.live_out)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
48
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
49 # Construct interference graph:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
50 for n in flowgraph.nodes:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
51 for tmp in n.live_out:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
52 n1 = self.getNode(tmp)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
53 for tmp2 in (n.live_out - {tmp}):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
54 n2 = self.getNode(tmp2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
55 self.addEdge(n1, n2)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
56
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
57 def getNode(self, tmp):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
58 if tmp not in self.tempMap:
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
59 self.tempMap[tmp] = self.newNode(tmp)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
60 return self.tempMap[tmp]
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
61
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
62 def newNode(self, varname):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
63 n = InterferenceGraphNode(self, varname)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
64 self.addNode(n)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
65 return n
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
66
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
67 def combine(self, n, m):
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
68 self.nodes.remove(m)
046017431c6a Started register allocator
Windel Bouwman
parents:
diff changeset
69 n.varnames.extend(m.varnames)