annotate python/registerallocator.py @ 275:6f2423df0675

Fixed serve arm-as
author Windel Bouwman
date Sat, 14 Sep 2013 17:29:10 +0200
parents cdc76d183bcc
children 046017431c6a
rev   line source
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
1
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
2 import graph
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
3
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
4 class InterferenceGraphNode(graph.Node):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
5 def __init__(self, g, varname):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
6 super().__init__(g)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
7 self.varname = varname
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
8
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
9 def __repr__(self):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
10 return '{}'.format(self.varname)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
11
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
12
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
13 class InterferenceGraph(graph.Graph):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
14 def __init__(self, flowgraph):
275
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
15 """
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
16 Create a new interference graph from a flowgraph
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
17 """
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
18 super().__init__()
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
19 # Mapping from node to live set
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
20 self.liveMap = {}
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
21 self.tempMap = {}
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
22 # Calculate liveness in CFG:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
23 ###
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
24 # Liveness:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
25 # in[n] = use[n] UNION (out[n] - def[n])
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
26 # out[n] = for s in n.succ in union in[s]
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
27 ###
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
28 for n in flowgraph.nodes:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
29 n.live_in = set()
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
30 n.live_out = set()
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
31 # Dataflow fixed point iteration:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
32 change = True
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
33 while change:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
34 change = False
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
35 for n in flowgraph.nodes:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
36 _in = n.live_in
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
37 _out = n.live_out
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
38 n.live_in = n.uses | (n.live_out - n.defs)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
39 if n.succ:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
40 n.live_out = set.union(*(s.live_in for s in n.succ))
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
41 else:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
42 n.live_out = set()
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
43 change = change or (_in != n.live_in) or (_out != n.live_out)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
44 # Construct interference graph:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
45 for n in flowgraph.nodes:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
46 for tmp in n.live_out:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
47 n1 = self.getNode(tmp)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
48 for tmp2 in (n.live_out - {tmp}):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
49 n2 = self.getNode(tmp2)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
50 self.addEdge(n1, n2)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
51
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
52 def getNode(self, tmp):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
53 if tmp not in self.tempMap:
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
54 self.tempMap[tmp] = self.newNode(tmp)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
55 return self.tempMap[tmp]
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
56
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
57 def newNode(self, varname):
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
58 n = InterferenceGraphNode(self, varname)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
59 self.nodes.append(n)
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
60 return n
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
61
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
62
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
63 class RegisterAllocator:
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
64 """ Target independent register allocator """
275
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
65 def registerAllocate(self, ig, regs, precolored):
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
66 """
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
67 Color the given interference graph with the provided registers
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
68 """
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
69 regMap = dict(precolored)
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
70 regs = set(regs)
270
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
71 K = len(regs)
275
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
72 allvars = list(n for n in ig.nodes if n.varname not in regMap)
270
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
73
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
74 # Chaitin's algorithm:
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
75 # remove all nodes that have less than K neighbours:
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
76 worklist = []
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
77 while allvars:
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
78 less_k = [n for n in allvars if len(n.Adj - set(worklist)) < K]
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
79 if not less_k:
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
80 raise NotImplementedError('Spilling not implemented')
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
81 n = less_k[0]
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
82 worklist.append(n)
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
83 allvars.remove(n)
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
84
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
85 # Add nodes back to the graph:
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
86 while worklist:
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
87 n = worklist.pop(-1)
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
88 adj = n.Adj - set(worklist)
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
89 possibleregs = set(regs) - set(regMap[n.varname] for n in adj)
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
90 regMap[n.varname] = list(possibleregs)[0]
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
91 # We have a register mapping!
275
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
92 # print(regMap)
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
93 # TODO: implement spilling
6f2423df0675 Fixed serve arm-as
Windel Bouwman
parents: 270
diff changeset
94 # TODO: implement coalescing
270
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
95 return regMap
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
96
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
97