|
269
|
1
|
|
|
2 import graph
|
|
|
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 def __init__(self, flowgraph):
|
|
|
15 """ Create a new interference graph from a flowgraph """
|
|
|
16 super().__init__()
|
|
|
17 # Mapping from node to live set
|
|
|
18 self.liveMap = {}
|
|
|
19 self.tempMap = {}
|
|
|
20 # Calculate liveness in CFG:
|
|
|
21 ###
|
|
|
22 # Liveness:
|
|
|
23 # in[n] = use[n] UNION (out[n] - def[n])
|
|
|
24 # out[n] = for s in n.succ in union in[s]
|
|
|
25 ###
|
|
|
26 for n in flowgraph.nodes:
|
|
|
27 n.live_in = set()
|
|
|
28 n.live_out = set()
|
|
|
29 # Dataflow fixed point iteration:
|
|
|
30 change = True
|
|
|
31 while change:
|
|
|
32 change = False
|
|
|
33 for n in flowgraph.nodes:
|
|
|
34 _in = n.live_in
|
|
|
35 _out = n.live_out
|
|
|
36 n.live_in = n.uses | (n.live_out - n.defs)
|
|
|
37 if n.succ:
|
|
|
38 n.live_out = set.union(*(s.live_in for s in n.succ))
|
|
|
39 else:
|
|
|
40 n.live_out = set()
|
|
|
41 change = change or (_in != n.live_in) or (_out != n.live_out)
|
|
|
42 # Construct interference graph:
|
|
|
43 for n in flowgraph.nodes:
|
|
|
44 for tmp in n.live_out:
|
|
|
45 n1 = self.getNode(tmp)
|
|
|
46 for tmp2 in (n.live_out - {tmp}):
|
|
|
47 n2 = self.getNode(tmp2)
|
|
|
48 self.addEdge(n1, n2)
|
|
|
49
|
|
|
50 def getNode(self, tmp):
|
|
|
51 if tmp not in self.tempMap:
|
|
|
52 self.tempMap[tmp] = self.newNode(tmp)
|
|
|
53 return self.tempMap[tmp]
|
|
|
54
|
|
|
55 def newNode(self, varname):
|
|
|
56 n = InterferenceGraphNode(self, varname)
|
|
|
57 self.nodes.append(n)
|
|
|
58 return n
|
|
|
59
|
|
173
|
60
|
|
|
61 class RegisterAllocator:
|
|
269
|
62 """ Target independent register allocator """
|
|
|
63 def registerAllocate(self, ig, regs):
|
|
|
64 """ Color the given interference graph with the provided registers """
|
|
|
65 self.regMap = {}
|
|
|
66 # TODO: implement ;)
|
|
|
67 regs = set(regs)
|
|
|
68 for n in ig.nodes:
|
|
|
69 print(n)
|
|
173
|
70
|
|
269
|
71 # TODO: implement spilling
|
|
|
72 # TODO: implement coalescing
|
|
|
73
|
