Mercurial > lcfOS

annotate python/registerallocator.py @ 279:2ccd57b1d78c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix register allocator to do burn2 OK
author Windel Bouwman
date Sat, 12 Oct 2013 09:56:23 +0200
parents 9fca39eebe50
children 02385f62f250
rev   line source
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
1 from flowgraph import FlowGraph
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
2 from interferencegraph import InterferenceGraph
269
5f8c04a8d26b Towards better modularity
Windel Bouwman
parents: 175
diff changeset
3
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
4 # Nifty first function:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
5 first = lambda x: next(iter(x))
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
6
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
7 class RegisterAllocator:
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
8 """
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
9 Target independent register allocator.
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
10
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
11 Algorithm is iterated register coalescing by Appel and George.
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
12
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
13 Chaitin's algorithm: remove all nodes with less than K neighbours.
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
14 These nodes can be colored when added back.
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
15
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
16 The process consists of the following steps:
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
17 - build interference graph from the instruction list
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
18 - remove low degree non move related nodes.
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
19 - (optional) coalesc registers to remove redundant moves
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
20 - (optional) spill registers
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
21 - select registers
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
22 """
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
23
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
24 def InitData(self, f):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
25 self.f = f
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
26 # Register information:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
27 self.regs = set(f.regs)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
28 self.K = len(self.regs)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
29
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
30 # Move related sets:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
31 self.coalescedMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
32 self.constrainedMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
33 self.frozenMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
34 self.activeMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
35 self.worklistMoves = set()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
36
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
37 def printLive(self):
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
38 print('Liveness:')
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
39 for i in self.f.instructions:
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
40 cfgn = self.f.cfg._map[i]
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
41 print(i, cfgn.live_in)
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
42
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
43 def Build(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
44 """ 1. Construct interference graph from instruction list """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
45 self.f.cfg = FlowGraph(self.f.instructions)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
46 self.f.ig = InterferenceGraph(self.f.cfg)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
47 self.printLive()
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
48
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
49 self.Node = self.f.ig.getNode
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
50
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
51 # Divide nodes into pre-colored and initial:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
52 pre_tmp = list(self.f.tempMap.keys())
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
53 self.precolored = set(self.Node(tmp) for tmp in pre_tmp)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
54 self.workSet = set(self.f.ig.nodes - self.precolored)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
55
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
56 # Make degree table:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
57 for n in self.precolored:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
58 n.addDegree = 100 + len(self.f.ig.nodes) + self.K
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
59
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
60 # Initialize color map:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
61 self.color = {}
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
62 for tmp, c in self.f.tempMap.items():
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
63 self.color[self.Node(tmp)] = c
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
64 dict(self.f.tempMap) # start with pre-colored
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
65
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
66 self.moves = [i for i in self.f.instructions if i.ismove]
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
67 print(self.moves)
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
68 for mv in self.moves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
69 self.Node(mv.src[0]).moves.add(mv)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
70 self.Node(mv.dst[0]).moves.add(mv)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
71
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
72 def NodeMoves(self, n):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
73 return n.moves & (self.activeMoves | self.worklistMoves)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
74
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
75 def MoveRelated(self, n):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
76 return bool(self.NodeMoves(n))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
77
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
78 @property
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
79 def SpillWorkSet(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
80 c = lambda n: n.Degree >= self.K
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
81 return set(filter(c, self.workSet))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
82
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
83 @property
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
84 def FreezeWorkSet(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
85 c = lambda n: n.Degree < self.K and self.MoveRelated(n)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
86 return set(filter(c, self.workSet))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
87
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
88 @property
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
89 def SimplifyWorkSet(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
90 c = lambda n: n.Degree < self.K and not self.MoveRelated(n)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
91 return set(filter(c, self.workSet))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
92
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
93 def makeWorkList(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
94 """ Divide initial nodes into worklists """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
95 self.selectStack = []
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
96
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
97 # Fill initial move set:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
98 for m in self.moves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
99 self.worklistMoves.add(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
100
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
101 def Simplify(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
102 """ 2. Remove nodes from the graph """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
103 n = first(self.SimplifyWorkSet)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
104 self.workSet.remove(n)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
105 self.selectStack.append(n)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
106 # Pop out of graph:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
107 self.f.ig.delNode(n)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
108
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
109 def EnableMoves(self, nodes):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
110 for n in nodes:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
111 for m in self.NodeMoves(n):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
112 if m in self.activeMoves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
113 self.activeMoves.remove(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
114 self.worklistMoves.add(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
115
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
116 def Coalesc(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
117 """ Coalesc conservative. """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
118 m = first(self.worklistMoves)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
119 x = self.Node(m.dst[0])
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
120 y = self.Node(m.src[0])
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
121 u, v = (y, x) if y in self.precolored else (x, y)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
122 self.worklistMoves.remove(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
123 if u is v:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
124 self.coalescedMoves.add(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
125 elif v in self.precolored or self.f.ig.hasEdge(u, v):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
126 self.constrainedMoves.add(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
127 elif u not in self.precolored and self.Conservative(u, v):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
128 self.coalescedMoves.add(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
129 self.workSet.remove(v)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
130 self.f.ig.Combine(u, v)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
131 else:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
132 self.activeMoves.add(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
133
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
134 def Conservative(self, u, v):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
135 """ Briggs conservative criteria for coalesc """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
136 nodes = u.Adjecent | v.Adjecent
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
137 c = lambda n: n.Degree >= self.K
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
138 k = len(list(filter(c, nodes)))
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
139 return k < self.K
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
140
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
141 def Freeze(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
142 """ Give up coalescing on some node """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
143 u = first(self.FreezeWorkSet)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
144 self.freezeMoves(u)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
145
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
146 def freezeMoves(self, u):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
147 """ Freeze moves for node u """
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
148 for m in self.NodeMoves(u):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
149 if m in self.activeMoves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
150 self.activeMoves.remove(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
151 else:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
152 sekf.worklistMoves.remove(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
153 self.frozenMoves.add(m)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
154 # Check other part of the move for still being move related:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
155 v = m.src[0] if u is m.dst[0] else m.dst[0]
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
156
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
157 def SelectSpill(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
158 # TODO
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
159 pass
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
160
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
161 def AssignColors(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
162 """ Add nodes back to the graph to color it. """
270
cdc76d183bcc first register allocator
Windel Bouwman
parents: 269
diff changeset
163 # Add nodes back to the graph:
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
164 while self.selectStack:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
165 n = self.selectStack.pop(-1)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
166 self.f.ig.addNode(n)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
167 takenregs = set(self.color[m] for m in n.Adjecent)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
168 okColors = self.regs - takenregs
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
169 if okColors:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
170 self.color[n] = first(okColors)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
171 n.color = self.color[n]
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
172 else:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
173 raise NotImplementedError('Spill required here!')
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
174
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
175 def ApplyColors(self):
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
176 # Remove coalesced moves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
177 for mv in self.coalescedMoves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
178 self.f.instructions.remove(mv)
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
179
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
180 # Use allocated registers:
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
181 lookup = lambda t: self.color[self.Node(t)]
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
182 for i in self.f.instructions:
277
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
183 i.src = tuple(map(lookup, i.src))
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
184 i.dst = tuple(map(lookup, i.dst))
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
185
046017431c6a Started register allocator
Windel Bouwman
parents: 275
diff changeset
186 def allocFrame(self, f):
279
2ccd57b1d78c Fix register allocator to do burn2 OK
Windel Bouwman
parents: 278
diff changeset
187 """ Do iterated register allocation for a single stack frame. """
278
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
188 self.InitData(f)
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
189 self.Build()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
190 self.makeWorkList()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
191 while True:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
192 if self.SimplifyWorkSet:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
193 self.Simplify()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
194 elif self.worklistMoves:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
195 self.Coalesc()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
196 elif self.FreezeWorkSet:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
197 self.Freeze()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
198 elif self.SpillWorkSet:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
199 raise NotImplementedError('Spill not implemented')
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
200 else:
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
201 break # Done!
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
202 self.AssignColors()
9fca39eebe50 First implementation of regalloc with coalsesc
Windel Bouwman
parents: 277
diff changeset
203 self.ApplyColors()
173
c1d2b6b9f9a7 Rework into passes
Windel Bouwman
parents:
diff changeset
204