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):
|
275
|
15 """
|
|
16 Create a new interference graph from a flowgraph
|
|
17 """
|
269
|
18 super().__init__()
|
|
19 # Mapping from node to live set
|
|
20 self.liveMap = {}
|
|
21 self.tempMap = {}
|
|
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 # Dataflow fixed point iteration:
|
|
32 change = True
|
|
33 while change:
|
|
34 change = False
|
|
35 for n in flowgraph.nodes:
|
|
36 _in = n.live_in
|
|
37 _out = n.live_out
|
|
38 n.live_in = n.uses | (n.live_out - n.defs)
|
|
39 if n.succ:
|
|
40 n.live_out = set.union(*(s.live_in for s in n.succ))
|
|
41 else:
|
|
42 n.live_out = set()
|
|
43 change = change or (_in != n.live_in) or (_out != n.live_out)
|
|
44 # Construct interference graph:
|
|
45 for n in flowgraph.nodes:
|
|
46 for tmp in n.live_out:
|
|
47 n1 = self.getNode(tmp)
|
|
48 for tmp2 in (n.live_out - {tmp}):
|
|
49 n2 = self.getNode(tmp2)
|
|
50 self.addEdge(n1, n2)
|
|
51
|
|
52 def getNode(self, tmp):
|
|
53 if tmp not in self.tempMap:
|
|
54 self.tempMap[tmp] = self.newNode(tmp)
|
|
55 return self.tempMap[tmp]
|
|
56
|
|
57 def newNode(self, varname):
|
|
58 n = InterferenceGraphNode(self, varname)
|
|
59 self.nodes.append(n)
|
|
60 return n
|
|
61
|
173
|
62
|
|
63 class RegisterAllocator:
|
269
|
64 """ Target independent register allocator """
|
275
|
65 def registerAllocate(self, ig, regs, precolored):
|
|
66 """
|
|
67 Color the given interference graph with the provided registers
|
|
68 """
|
|
69 regMap = dict(precolored)
|
269
|
70 regs = set(regs)
|
270
|
71 K = len(regs)
|
275
|
72 allvars = list(n for n in ig.nodes if n.varname not in regMap)
|
270
|
73
|
|
74 # Chaitin's algorithm:
|
|
75 # remove all nodes that have less than K neighbours:
|
|
76 worklist = []
|
|
77 while allvars:
|
|
78 less_k = [n for n in allvars if len(n.Adj - set(worklist)) < K]
|
|
79 if not less_k:
|
|
80 raise NotImplementedError('Spilling not implemented')
|
|
81 n = less_k[0]
|
|
82 worklist.append(n)
|
|
83 allvars.remove(n)
|
|
84
|
|
85 # Add nodes back to the graph:
|
|
86 while worklist:
|
|
87 n = worklist.pop(-1)
|
|
88 adj = n.Adj - set(worklist)
|
|
89 possibleregs = set(regs) - set(regMap[n.varname] for n in adj)
|
|
90 regMap[n.varname] = list(possibleregs)[0]
|
|
91 # We have a register mapping!
|
275
|
92 # print(regMap)
|
|
93 # TODO: implement spilling
|
|
94 # TODO: implement coalescing
|
270
|
95 return regMap
|
173
|
96
|
269
|
97
|