Mercurial > lcfOS

comparison python/interferencegraph.py @ 277:046017431c6a

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