|
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 """
|
|
270
|
65 regMap = {}
|
|
269
|
66 regs = set(regs)
|
|
270
|
67 K = len(regs)
|
|
|
68 allvars = list(ig.nodes)
|
|
|
69
|
|
|
70 # Chaitin's algorithm:
|
|
|
71 # remove all nodes that have less than K neighbours:
|
|
|
72 worklist = []
|
|
|
73 while allvars:
|
|
|
74 less_k = [n for n in allvars if len(n.Adj - set(worklist)) < K]
|
|
|
75 if not less_k:
|
|
|
76 raise NotImplementedError('Spilling not implemented')
|
|
|
77 n = less_k[0]
|
|
|
78 worklist.append(n)
|
|
|
79 allvars.remove(n)
|
|
|
80
|
|
|
81 # Add nodes back to the graph:
|
|
|
82 while worklist:
|
|
|
83 n = worklist.pop(-1)
|
|
|
84 adj = n.Adj - set(worklist)
|
|
|
85 possibleregs = set(regs) - set(regMap[n.varname] for n in adj)
|
|
|
86 regMap[n.varname] = list(possibleregs)[0]
|
|
|
87 # We have a register mapping!
|
|
|
88 #print(self.regMap)
|
|
|
89 return regMap
|
|
173
|
90
|
|
269
|
91 # TODO: implement spilling
|
|
|
92 # TODO: implement coalescing
|
|
|
93
|
