|
277
|
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)
|
